[gostls13.git] / src / go / build / deps_test.go

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file exercises the import parser but also checks that
// some low-level packages do not have new dependencies added.

package build

import (
        "bytes"
        "fmt"
        "go/token"
        "internal/testenv"
        "io/fs"
        "os"
        "path/filepath"
        "runtime"
        "sort"
        "strings"
        "testing"
)

// depsRules defines the expected dependencies between packages in
// the Go source tree. It is a statement of policy.
//
// DO NOT CHANGE THIS DATA TO FIX BUILDS.
// Existing packages should not have their constraints relaxed
// without prior discussion.
// Negative assertions should almost never be removed.
//
// The general syntax of a rule is:
//
//              a, b < c, d;
//
// which means c and d come after a and b in the partial order
// (that is, c and d can import a and b),
// but doesn't provide a relative order between a vs b or c vs d.
//
// The rules can chain together, as in:
//
//              e < f, g < h;
//
// which is equivalent to
//
//              e < f, g;
//              f, g < h;
//
// Except for the special bottom element "NONE", each name
// must appear exactly once on the right-hand side of a rule.
// That rule serves as the definition of the allowed dependencies
// for that name. The definition must appear before any uses
// of the name on the left-hand side of a rule. (That is, the
// rules themselves must be ordered according to the partial
// order, for easier reading by people.)
//
// Negative assertions double-check the partial order:
//
//              i !< j
//
// means that it must NOT be the case that i < j.
// Negative assertions may appear anywhere in the rules,
// even before i and j have been defined.
//
// Comments begin with #.
//
// All-caps names are pseudo-names for specific points
// in the dependency lattice.
//
var depsRules = `
        # No dependencies allowed for any of these packages.
        NONE
        < container/list, container/ring,
          internal/cfg, internal/cpu, internal/goexperiment,
          internal/goversion, internal/nettrace,
          unicode/utf8, unicode/utf16, unicode,
          unsafe;

        # These packages depend only on unsafe.
        unsafe
        < internal/abi;

        # RUNTIME is the core runtime group of packages, all of them very light-weight.
        internal/abi, internal/cpu, internal/goexperiment, unsafe
        < internal/bytealg
        < internal/itoa
        < internal/unsafeheader
        < runtime/internal/sys
        < runtime/internal/atomic
        < runtime/internal/math
        < runtime
        < sync/atomic
        < internal/race
        < sync
        < internal/reflectlite
        < errors
        < internal/oserror, math/bits
        < RUNTIME;

        RUNTIME
        < sort
        < container/heap;

        RUNTIME
        < io;

        syscall !< io;
        reflect !< sort;

        RUNTIME, unicode/utf8
        < path;

        unicode !< path;

        # SYSCALL is RUNTIME plus the packages necessary for basic system calls.
        RUNTIME, unicode/utf8, unicode/utf16
        < internal/syscall/windows/sysdll, syscall/js
        < syscall
        < internal/syscall/unix, internal/syscall/windows, internal/syscall/windows/registry
        < internal/syscall/execenv
        < SYSCALL;

        # TIME is SYSCALL plus the core packages about time, including context.
        SYSCALL
        < time/tzdata
        < time
        < context
        < TIME;

        TIME, io, path, sort
        < io/fs;

        # MATH is RUNTIME plus the basic math packages.
        RUNTIME
        < math
        < MATH;

        unicode !< math;

        MATH
        < math/cmplx;

        MATH
        < math/rand;

        MATH
        < runtime/metrics;

        MATH, unicode/utf8
        < strconv;

        unicode !< strconv;

        # STR is basic string and buffer manipulation.
        RUNTIME, io, unicode/utf8, unicode/utf16, unicode
        < bytes, strings
        < bufio;

        bufio, path, strconv
        < STR;

        # OS is basic OS access, including helpers (path/filepath, os/exec, etc).
        # OS includes string routines, but those must be layered above package os.
        # OS does not include reflection.
        io/fs
        < internal/testlog
        < internal/poll
        < os
        < os/signal;

        io/fs
        < embed;

        unicode, fmt !< os, os/signal;

        os/signal, STR
        < path/filepath
        < io/ioutil, os/exec;

        io/ioutil, os/exec, os/signal
        < OS;

        reflect !< OS;

        OS
        < golang.org/x/sys/cpu;

        # FMT is OS (which includes string routines) plus reflect and fmt.
        # It does not include package log, which should be avoided in core packages.
        strconv, unicode
        < reflect;

        os, reflect
        < internal/fmtsort
        < fmt;

        OS, fmt
        < FMT;

        log !< FMT;

        OS, FMT
        < internal/execabs;

        OS, internal/execabs
        < internal/goroot;

        # Misc packages needing only FMT.
        FMT
        < flag,
          html,
          mime/quotedprintable,
          net/internal/socktest,
          net/url,
          runtime/debug,
          runtime/trace,
          text/scanner,
          text/tabwriter;

        # encodings
        # core ones do not use fmt.
        io, strconv
        < encoding;

        encoding, reflect
        < encoding/binary
        < encoding/base32, encoding/base64;

        fmt !< encoding/base32, encoding/base64;

        FMT, encoding/base32, encoding/base64
        < encoding/ascii85, encoding/csv, encoding/gob, encoding/hex,
          encoding/json, encoding/pem, encoding/xml, mime;

        # hashes
        io
        < hash
        < hash/adler32, hash/crc32, hash/crc64, hash/fnv, hash/maphash;

        # math/big
        FMT, encoding/binary, math/rand
        < math/big;

        # compression
        FMT, encoding/binary, hash/adler32, hash/crc32
        < compress/bzip2, compress/flate, compress/lzw
        < archive/zip, compress/gzip, compress/zlib;

        # templates
        FMT
        < text/template/parse;

        net/url, text/template/parse
        < text/template
        < internal/lazytemplate;

        encoding/json, html, text/template
        < html/template;

        # regexp
        FMT
        < regexp/syntax
        < regexp
        < internal/lazyregexp;

        # suffix array
        encoding/binary, regexp
        < index/suffixarray;

        # executable parsing
        FMT, encoding/binary, compress/zlib
        < debug/dwarf
        < debug/elf, debug/gosym, debug/macho, debug/pe, debug/plan9obj, internal/xcoff
        < DEBUG;

        # go parser and friends.
        FMT
        < go/token
        < go/scanner
        < go/ast
        < go/internal/typeparams
        < go/parser;

        FMT
        < go/build/constraint;

        go/build/constraint, go/parser, text/tabwriter
        < go/printer
        < go/format;

        go/parser, internal/lazyregexp, text/template
        < go/doc;

        math/big, go/token
        < go/constant;

        container/heap, go/constant, go/parser, regexp
        < go/types;

        go/build/constraint, go/doc, go/parser, internal/goroot, internal/goversion
        < go/build;

        DEBUG, go/build, go/types, text/scanner
        < go/internal/gcimporter, go/internal/gccgoimporter, go/internal/srcimporter
        < go/importer;

        # databases
        FMT
        < database/sql/internal
        < database/sql/driver
        < database/sql;

        # images
        FMT, compress/lzw, compress/zlib
        < image/color
        < image, image/color/palette
        < image/internal/imageutil
        < image/draw
        < image/gif, image/jpeg, image/png;

        # cgo, delayed as long as possible.
        # If you add a dependency on CGO, you must add the package
        # to cgoPackages in cmd/dist/test.go as well.
        RUNTIME
        < C
        < runtime/cgo
        < CGO
        < runtime/race, runtime/msan;

        # Bulk of the standard library must not use cgo.
        # The prohibition stops at net and os/user.
        C !< fmt, go/types, CRYPTO-MATH;

        CGO, OS
        < plugin;

        CGO, FMT
        < os/user
        < archive/tar;

        sync
        < internal/singleflight;

        os
        < golang.org/x/net/dns/dnsmessage,
          golang.org/x/net/lif,
          golang.org/x/net/route;

        # net is unavoidable when doing any networking,
        # so large dependencies must be kept out.
        # This is a long-looking list but most of these
        # are small with few dependencies.
        CGO,
        golang.org/x/net/dns/dnsmessage,
        golang.org/x/net/lif,
        golang.org/x/net/route,
        internal/nettrace,
        internal/poll,
        internal/singleflight,
        internal/race,
        os
        < net;

        fmt, unicode !< net;
        math/rand !< net; # net uses runtime instead

        # NET is net plus net-helper packages.
        FMT, net
        < net/textproto;

        mime, net/textproto, net/url
        < NET;

        # logging - most packages should not import; http and up is allowed
        FMT
        < log;

        log !< crypto/tls, database/sql, go/importer, testing;

        FMT, log, net
        < log/syslog;

        NET, log
        < net/mail;

        # CRYPTO is core crypto algorithms - no cgo, fmt, net.
        # Unfortunately, stuck with reflect via encoding/binary.
        encoding/binary, golang.org/x/sys/cpu, hash
        < crypto
        < crypto/subtle
        < crypto/internal/subtle
        < crypto/cipher
        < crypto/aes, crypto/des, crypto/hmac, crypto/md5, crypto/rc4,
          crypto/sha1, crypto/sha256, crypto/sha512
        < CRYPTO;

        CGO, fmt, net !< CRYPTO;

        # CRYPTO-MATH is core bignum-based crypto - no cgo, net; fmt now ok.
        CRYPTO, FMT, math/big
        < crypto/rand
        < crypto/internal/randutil
        < crypto/ed25519/internal/edwards25519
        < crypto/ed25519
        < encoding/asn1
        < golang.org/x/crypto/cryptobyte/asn1
        < golang.org/x/crypto/cryptobyte
        < golang.org/x/crypto/curve25519
        < crypto/dsa, crypto/elliptic, crypto/rsa
        < crypto/ecdsa
        < CRYPTO-MATH;

        CGO, net !< CRYPTO-MATH;

        # TLS, Prince of Dependencies.
        CRYPTO-MATH, NET, container/list, encoding/hex, encoding/pem
        < golang.org/x/crypto/internal/subtle
        < golang.org/x/crypto/chacha20
        < golang.org/x/crypto/poly1305
        < golang.org/x/crypto/chacha20poly1305
        < golang.org/x/crypto/hkdf
        < crypto/x509/internal/macos
        < crypto/x509/pkix
        < crypto/x509
        < crypto/tls;

        # crypto-aware packages

        NET, crypto/rand, mime/quotedprintable
        < mime/multipart;

        crypto/tls
        < net/smtp;

        # HTTP, King of Dependencies.

        FMT
        < golang.org/x/net/http2/hpack, net/http/internal;

        FMT, NET, container/list, encoding/binary, log
        < golang.org/x/text/transform
        < golang.org/x/text/unicode/norm
        < golang.org/x/text/unicode/bidi
        < golang.org/x/text/secure/bidirule
        < golang.org/x/net/idna
        < golang.org/x/net/http/httpguts, golang.org/x/net/http/httpproxy;

        NET, crypto/tls
        < net/http/httptrace;

        compress/gzip,
        golang.org/x/net/http/httpguts,
        golang.org/x/net/http/httpproxy,
        golang.org/x/net/http2/hpack,
        net/http/internal,
        net/http/httptrace,
        mime/multipart,
        log
        < net/http;

        # HTTP-aware packages

        encoding/json, net/http
        < expvar;

        net/http
        < net/http/cookiejar, net/http/httputil;

        net/http, flag
        < net/http/httptest;

        net/http, regexp
        < net/http/cgi
        < net/http/fcgi;

        # Profiling
        FMT, compress/gzip, encoding/binary, text/tabwriter
        < runtime/pprof;

        OS, compress/gzip, regexp
        < internal/profile;

        html, internal/profile, net/http, runtime/pprof, runtime/trace
        < net/http/pprof;

        # RPC
        encoding/gob, encoding/json, go/token, html/template, net/http
        < net/rpc
        < net/rpc/jsonrpc;

        # System Information
        internal/cpu, sync
        < internal/sysinfo;

        # Test-only
        log
        < testing/iotest
        < testing/fstest;

        FMT, flag, math/rand
        < testing/quick;

        FMT, flag, runtime/debug, runtime/trace, internal/sysinfo
        < testing;

        internal/testlog, runtime/pprof, regexp
        < testing/internal/testdeps;

        OS, flag, testing, internal/cfg
        < internal/testenv;

        OS, encoding/base64
        < internal/obscuretestdata;

        CGO, OS, fmt
        < os/signal/internal/pty;

        NET, testing, math/rand
        < golang.org/x/net/nettest;

        FMT, container/heap, math/rand
        < internal/trace;
`

// listStdPkgs returns the same list of packages as "go list std".
func listStdPkgs(goroot string) ([]string, error) {
        // Based on cmd/go's matchPackages function.
        var pkgs []string

        src := filepath.Join(goroot, "src") + string(filepath.Separator)
        walkFn := func(path string, d fs.DirEntry, err error) error {
                if err != nil || !d.IsDir() || path == src {
                        return nil
                }

                base := filepath.Base(path)
                if strings.HasPrefix(base, ".") || strings.HasPrefix(base, "_") || base == "testdata" {
                        return filepath.SkipDir
                }

                name := filepath.ToSlash(path[len(src):])
                if name == "builtin" || name == "cmd" {
                        return filepath.SkipDir
                }

                pkgs = append(pkgs, strings.TrimPrefix(name, "vendor/"))
                return nil
        }
        if err := filepath.WalkDir(src, walkFn); err != nil {
                return nil, err
        }
        return pkgs, nil
}

func TestDependencies(t *testing.T) {
        if !testenv.HasSrc() {
                // Tests run in a limited file system and we do not
                // provide access to every source file.
                t.Skipf("skipping on %s/%s, missing full GOROOT", runtime.GOOS, runtime.GOARCH)
        }

        ctxt := Default
        all, err := listStdPkgs(ctxt.GOROOT)
        if err != nil {
                t.Fatal(err)
        }
        sort.Strings(all)

        sawImport := map[string]map[string]bool{} // from package => to package => true
        policy := depsPolicy(t)

        for _, pkg := range all {
                imports, err := findImports(pkg)
                if err != nil {
                        t.Error(err)
                        continue
                }
                if sawImport[pkg] == nil {
                        sawImport[pkg] = map[string]bool{}
                }
                ok := policy[pkg]
                var bad []string
                for _, imp := range imports {
                        sawImport[pkg][imp] = true
                        if !ok[imp] {
                                bad = append(bad, imp)
                        }
                }
                if bad != nil {
                        t.Errorf("unexpected dependency: %s imports %v", pkg, bad)
                }
        }

        // depPath returns the path between the given from and to packages.
        // It returns the empty string if there's no dependency path.
        var depPath func(string, string) string
        depPath = func(from, to string) string {
                if sawImport[from][to] {
                        return from + " => " + to
                }
                for pkg := range sawImport[from] {
                        if p := depPath(pkg, to); p != "" {
                                return from + " => " + p
                        }
                }
                return ""
        }
}

var buildIgnore = []byte("\n// +build ignore")

func findImports(pkg string) ([]string, error) {
        vpkg := pkg
        if strings.HasPrefix(pkg, "golang.org") {
                vpkg = "vendor/" + pkg
        }
        dir := filepath.Join(Default.GOROOT, "src", vpkg)
        files, err := os.ReadDir(dir)
        if err != nil {
                return nil, err
        }
        var imports []string
        var haveImport = map[string]bool{}
        fset := token.NewFileSet()
        for _, file := range files {
                name := file.Name()
                if name == "slice_go14.go" || name == "slice_go18.go" {
                        // These files are for compiler bootstrap with older versions of Go and not built in the standard build.
                        continue
                }
                if !strings.HasSuffix(name, ".go") || strings.HasSuffix(name, "_test.go") {
                        continue
                }
                info := fileInfo{
                        name: filepath.Join(dir, name),
                        fset: fset,
                }
                f, err := os.Open(info.name)
                if err != nil {
                        return nil, err
                }
                err = readGoInfo(f, &info)
                f.Close()
                if err != nil {
                        return nil, fmt.Errorf("reading %v: %v", name, err)
                }
                if bytes.Contains(info.header, buildIgnore) {
                        continue
                }
                for _, imp := range info.imports {
                        path := imp.path
                        if !haveImport[path] {
                                haveImport[path] = true
                                imports = append(imports, path)
                        }
                }
        }
        sort.Strings(imports)
        return imports, nil
}

// depsPolicy returns a map m such that m[p][d] == true when p can import d.
func depsPolicy(t *testing.T) map[string]map[string]bool {
        allowed := map[string]map[string]bool{"NONE": {}}
        disallowed := [][2][]string{}

        parseDepsRules(t, func(deps []string, op string, users []string) {
                if op == "!<" {
                        disallowed = append(disallowed, [2][]string{deps, users})
                        return
                }
                for _, u := range users {
                        if allowed[u] != nil {
                                t.Errorf("multiple deps lists for %s", u)
                        }
                        allowed[u] = make(map[string]bool)
                        for _, d := range deps {
                                if allowed[d] == nil {
                                        t.Errorf("use of %s before its deps list", d)
                                }
                                allowed[u][d] = true
                        }
                }
        })

        // Check for missing deps info.
        for _, deps := range allowed {
                for d := range deps {
                        if allowed[d] == nil {
                                t.Errorf("missing deps list for %s", d)
                        }
                }
        }

        // Complete transitive allowed deps.
        for k := range allowed {
                for i := range allowed {
                        for j := range allowed {
                                if i != k && k != j && allowed[i][k] && allowed[k][j] {
                                        if i == j {
                                                // Can only happen along with a "use of X before deps" error above,
                                                // but this error is more specific - it makes clear that reordering the
                                                // rules will not be enough to fix the problem.
                                                t.Errorf("deps policy cycle: %s < %s < %s", j, k, i)
                                        }
                                        allowed[i][j] = true
                                }
                        }
                }
        }

        // Check negative assertions against completed allowed deps.
        for _, bad := range disallowed {
                deps, users := bad[0], bad[1]
                for _, d := range deps {
                        for _, u := range users {
                                if allowed[u][d] {
                                        t.Errorf("deps policy incorrect: assertion failed: %s !< %s", d, u)
                                }
                        }
                }
        }

        if t.Failed() {
                t.FailNow()
        }

        return allowed
}

// parseDepsRules parses depsRules, calling save(deps, op, users)
// for each deps < users or deps !< users rule
// (op is "<" or "!<").
func parseDepsRules(t *testing.T, save func(deps []string, op string, users []string)) {
        p := &depsParser{t: t, lineno: 1, text: depsRules}

        var prev []string
        var op string
        for {
                list, tok := p.nextList()
                if tok == "" {
                        if prev == nil {
                                break
                        }
                        p.syntaxError("unexpected EOF")
                }
                if prev != nil {
                        save(prev, op, list)
                }
                prev = list
                if tok == ";" {
                        prev = nil
                        op = ""
                        continue
                }
                if tok != "<" && tok != "!<" {
                        p.syntaxError("missing <")
                }
                op = tok
        }
}

// A depsParser parses the depsRules syntax described above.
type depsParser struct {
        t        *testing.T
        lineno   int
        lastWord string
        text     string
}

// syntaxError reports a parsing error.
func (p *depsParser) syntaxError(msg string) {
        p.t.Fatalf("deps:%d: syntax error: %s near %s", p.lineno, msg, p.lastWord)
}

// nextList parses and returns a comma-separated list of names.
func (p *depsParser) nextList() (list []string, token string) {
        for {
                tok := p.nextToken()
                switch tok {
                case "":
                        if len(list) == 0 {
                                return nil, ""
                        }
                        fallthrough
                case ",", "<", "!<", ";":
                        p.syntaxError("bad list syntax")
                }
                list = append(list, tok)

                tok = p.nextToken()
                if tok != "," {
                        return list, tok
                }
        }
}

// nextToken returns the next token in the deps rules,
// one of ";" "," "<" "!<" or a name.
func (p *depsParser) nextToken() string {
        for {
                if p.text == "" {
                        return ""
                }
                switch p.text[0] {
                case ';', ',', '<':
                        t := p.text[:1]
                        p.text = p.text[1:]
                        return t

                case '!':
                        if len(p.text) < 2 || p.text[1] != '<' {
                                p.syntaxError("unexpected token !")
                        }
                        p.text = p.text[2:]
                        return "!<"

                case '#':
                        i := strings.Index(p.text, "\n")
                        if i < 0 {
                                i = len(p.text)
                        }
                        p.text = p.text[i:]
                        continue

                case '\n':
                        p.lineno++
                        fallthrough
                case ' ', '\t':
                        p.text = p.text[1:]
                        continue

                default:
                        i := strings.IndexAny(p.text, "!;,<#\n \t")
                        if i < 0 {
                                i = len(p.text)
                        }
                        t := p.text[:i]
                        p.text = p.text[i:]
                        p.lastWord = t
                        return t
                }
        }
}

// TestStdlibLowercase tests that all standard library package names are
// lowercase. See Issue 40065.
func TestStdlibLowercase(t *testing.T) {
        if !testenv.HasSrc() {
                t.Skipf("skipping on %s/%s, missing full GOROOT", runtime.GOOS, runtime.GOARCH)
        }

        ctxt := Default
        all, err := listStdPkgs(ctxt.GOROOT)
        if err != nil {
                t.Fatal(err)
        }

        for _, pkgname := range all {
                if strings.ToLower(pkgname) != pkgname {
                        t.Errorf("package %q should not use upper-case path", pkgname)
                }
        }
}

// TestFindImports tests that findImports works.  See #43249.
func TestFindImports(t *testing.T) {
        imports, err := findImports("go/build")
        if err != nil {
                t.Fatal(err)
        }
        t.Logf("go/build imports %q", imports)
        want := []string{"bytes", "os", "path/filepath", "strings"}
wantLoop:
        for _, w := range want {
                for _, imp := range imports {
                        if imp == w {
                                continue wantLoop
                        }
                }
                t.Errorf("expected to find %q in import list", w)
        }
}