src/go/build/deps_test.go

   1 // Copyright 2012 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // This file exercises the import parser but also checks that
   6 // some low-level packages do not have new dependencies added.
   7
   8 package build
   9
  10 import (
  11         "bytes"
  12         "fmt"
  13         "io/ioutil"
  14         "os"
  15         "path/filepath"
  16         "runtime"
  17         "sort"
  18         "strconv"
  19         "strings"
  20         "testing"
  21 )
  22
  23 // pkgDeps defines the expected dependencies between packages in
  24 // the Go source tree. It is a statement of policy.
  25 // Changes should not be made to this map without prior discussion.
  26 //
  27 // The map contains two kinds of entries:
  28 // 1) Lower-case keys are standard import paths and list the
  29 // allowed imports in that package.
  30 // 2) Upper-case keys define aliases for package sets, which can then
  31 // be used as dependencies by other rules.
  32 //
  33 // DO NOT CHANGE THIS DATA TO FIX BUILDS.
  34 //
  35 var pkgDeps = map[string][]string{
  36         // L0 is the lowest level, core, nearly unavoidable packages.
  37         "errors":                  {"runtime", "internal/reflectlite"},
  38         "io":                      {"errors", "sync", "sync/atomic"},
  39         "runtime":                 {"unsafe", "runtime/internal/atomic", "runtime/internal/sys", "runtime/internal/math", "internal/cpu", "internal/bytealg"},
  40         "runtime/internal/sys":    {},
  41         "runtime/internal/atomic": {"unsafe", "internal/cpu"},
  42         "runtime/internal/math":   {"runtime/internal/sys"},
  43         "internal/race":           {"runtime", "unsafe"},
  44         "sync":                    {"internal/race", "runtime", "sync/atomic", "unsafe"},
  45         "sync/atomic":             {"unsafe"},
  46         "unsafe":                  {},
  47         "internal/cpu":            {},
  48         "internal/bytealg":        {"unsafe", "internal/cpu"},
  49         "internal/reflectlite":    {"runtime", "unsafe"},
  50
  51         "L0": {
  52                 "errors",
  53                 "io",
  54                 "runtime",
  55                 "runtime/internal/atomic",
  56                 "sync",
  57                 "sync/atomic",
  58                 "unsafe",
  59                 "internal/cpu",
  60                 "internal/bytealg",
  61                 "internal/reflectlite",
  62         },
  63
  64         // L1 adds simple functions and strings processing,
  65         // but not Unicode tables.
  66         "math":          {"internal/cpu", "unsafe", "math/bits"},
  67         "math/bits":     {"unsafe"},
  68         "math/cmplx":    {"math", "math/bits"},
  69         "math/rand":     {"L0", "math"},
  70         "strconv":       {"L0", "unicode/utf8", "math", "math/bits"},
  71         "unicode/utf16": {},
  72         "unicode/utf8":  {},
  73
  74         "L1": {
  75                 "L0",
  76                 "math",
  77                 "math/bits",
  78                 "math/cmplx",
  79                 "math/rand",
  80                 "sort",
  81                 "strconv",
  82                 "unicode/utf16",
  83                 "unicode/utf8",
  84         },
  85
  86         // L2 adds Unicode and strings processing.
  87         "bufio":   {"L0", "unicode/utf8", "bytes"},
  88         "bytes":   {"L0", "unicode", "unicode/utf8"},
  89         "path":    {"L0", "unicode/utf8", "strings"},
  90         "strings": {"L0", "unicode", "unicode/utf8"},
  91         "unicode": {},
  92
  93         "L2": {
  94                 "L1",
  95                 "bufio",
  96                 "bytes",
  97                 "path",
  98                 "strings",
  99                 "unicode",
 100         },
 101
 102         // L3 adds reflection and some basic utility packages
 103         // and interface definitions, but nothing that makes
 104         // system calls.
 105         "crypto":                 {"L2", "hash"}, // interfaces
 106         "crypto/cipher":          {"L2", "crypto/subtle", "crypto/internal/subtle", "encoding/binary"},
 107         "crypto/internal/subtle": {"unsafe", "reflect"}, // reflect behind a appengine tag
 108         "crypto/subtle":          {},
 109         "encoding/base32":        {"L2"},
 110         "encoding/base64":        {"L2", "encoding/binary"},
 111         "encoding/binary":        {"L2", "reflect"},
 112         "hash":                   {"L2"}, // interfaces
 113         "hash/adler32":           {"L2", "hash"},
 114         "hash/crc32":             {"L2", "hash"},
 115         "hash/crc64":             {"L2", "hash"},
 116         "hash/fnv":               {"L2", "hash"},
 117         "hash/maphash":           {"L2", "hash"},
 118         "image":                  {"L2", "image/color"}, // interfaces
 119         "image/color":            {"L2"},                // interfaces
 120         "image/color/palette":    {"L2", "image/color"},
 121         "internal/fmtsort":       {"reflect", "sort"},
 122         "reflect":                {"L2"},
 123         "sort":                   {"internal/reflectlite"},
 124
 125         "L3": {
 126                 "L2",
 127                 "crypto",
 128                 "crypto/cipher",
 129                 "crypto/internal/subtle",
 130                 "crypto/subtle",
 131                 "encoding/base32",
 132                 "encoding/base64",
 133                 "encoding/binary",
 134                 "hash",
 135                 "hash/adler32",
 136                 "hash/crc32",
 137                 "hash/crc64",
 138                 "hash/fnv",
 139                 "image",
 140                 "image/color",
 141                 "image/color/palette",
 142                 "internal/fmtsort",
 143                 "internal/oserror",
 144                 "reflect",
 145         },
 146
 147         // End of linear dependency definitions.
 148
 149         // Operating system access.
 150         "syscall":                           {"L0", "internal/oserror", "internal/race", "internal/syscall/windows/sysdll", "syscall/js", "unicode/utf16"},
 151         "syscall/js":                        {"L0"},
 152         "internal/oserror":                  {"L0"},
 153         "internal/syscall/unix":             {"L0", "syscall"},
 154         "internal/syscall/windows":          {"L0", "syscall", "internal/syscall/windows/sysdll", "unicode/utf16"},
 155         "internal/syscall/windows/registry": {"L0", "syscall", "internal/syscall/windows/sysdll", "unicode/utf16"},
 156         "internal/syscall/execenv":          {"L0", "syscall", "internal/syscall/windows", "unicode/utf16"},
 157         "time": {
 158                 // "L0" without the "io" package:
 159                 "errors",
 160                 "runtime",
 161                 "runtime/internal/atomic",
 162                 "sync",
 163                 "sync/atomic",
 164                 "unsafe",
 165                 // Other time dependencies:
 166                 "internal/syscall/windows/registry",
 167                 "syscall",
 168                 "syscall/js",
 169         },
 170
 171         "internal/cfg":     {"L0"},
 172         "internal/poll":    {"L0", "internal/oserror", "internal/race", "syscall", "time", "unicode/utf16", "unicode/utf8", "internal/syscall/windows", "internal/syscall/unix"},
 173         "internal/testlog": {"L0"},
 174         "os":               {"L1", "os", "syscall", "time", "internal/oserror", "internal/poll", "internal/syscall/windows", "internal/syscall/unix", "internal/syscall/execenv", "internal/testlog"},
 175         "path/filepath":    {"L2", "os", "syscall", "internal/syscall/windows"},
 176         "io/ioutil":        {"L2", "os", "path/filepath", "time"},
 177         "os/exec":          {"L2", "os", "context", "path/filepath", "syscall", "internal/syscall/execenv"},
 178         "os/signal":        {"L2", "os", "syscall"},
 179
 180         // OS enables basic operating system functionality,
 181         // but not direct use of package syscall, nor os/signal.
 182         "OS": {
 183                 "io/ioutil",
 184                 "os",
 185                 "os/exec",
 186                 "path/filepath",
 187                 "time",
 188         },
 189
 190         // Formatted I/O: few dependencies (L1) but we must add reflect and internal/fmtsort.
 191         "fmt": {"L1", "os", "reflect", "internal/fmtsort"},
 192         "log": {"L1", "os", "fmt", "time"},
 193
 194         // Packages used by testing must be low-level (L2+fmt).
 195         "regexp":         {"L2", "regexp/syntax"},
 196         "regexp/syntax":  {"L2"},
 197         "runtime/debug":  {"L2", "fmt", "io/ioutil", "os", "time"},
 198         "runtime/pprof":  {"L2", "compress/gzip", "context", "encoding/binary", "fmt", "io/ioutil", "os", "syscall", "text/tabwriter", "time"},
 199         "runtime/trace":  {"L0", "context", "fmt"},
 200         "text/tabwriter": {"L2"},
 201
 202         "testing":                  {"L2", "flag", "fmt", "internal/race", "io/ioutil", "os", "runtime/debug", "runtime/pprof", "runtime/trace", "time"},
 203         "testing/iotest":           {"L2", "log"},
 204         "testing/quick":            {"L2", "flag", "fmt", "reflect", "time"},
 205         "internal/obscuretestdata": {"L2", "OS", "encoding/base64"},
 206         "internal/testenv":         {"L2", "OS", "flag", "testing", "syscall", "internal/cfg"},
 207         "internal/lazyregexp":      {"L2", "OS", "regexp"},
 208         "internal/lazytemplate":    {"L2", "OS", "text/template"},
 209
 210         // L4 is defined as L3+fmt+log+time, because in general once
 211         // you're using L3 packages, use of fmt, log, or time is not a big deal.
 212         "L4": {
 213                 "L3",
 214                 "fmt",
 215                 "log",
 216                 "time",
 217         },
 218
 219         // Go parser.
 220         "go/ast":     {"L4", "OS", "go/scanner", "go/token"},
 221         "go/doc":     {"L4", "OS", "go/ast", "go/token", "regexp", "internal/lazyregexp", "text/template"},
 222         "go/parser":  {"L4", "OS", "go/ast", "go/scanner", "go/token"},
 223         "go/printer": {"L4", "OS", "go/ast", "go/scanner", "go/token", "text/tabwriter"},
 224         "go/scanner": {"L4", "OS", "go/token"},
 225         "go/token":   {"L4"},
 226
 227         "GOPARSER": {
 228                 "go/ast",
 229                 "go/doc",
 230                 "go/parser",
 231                 "go/printer",
 232                 "go/scanner",
 233                 "go/token",
 234         },
 235
 236         "go/format":       {"L4", "GOPARSER", "internal/format"},
 237         "internal/format": {"L4", "GOPARSER"},
 238
 239         // Go type checking.
 240         "go/constant":               {"L4", "go/token", "math/big"},
 241         "go/importer":               {"L4", "go/build", "go/internal/gccgoimporter", "go/internal/gcimporter", "go/internal/srcimporter", "go/token", "go/types"},
 242         "go/internal/gcimporter":    {"L4", "OS", "go/build", "go/constant", "go/token", "go/types", "text/scanner"},
 243         "go/internal/gccgoimporter": {"L4", "OS", "debug/elf", "go/constant", "go/token", "go/types", "internal/xcoff", "text/scanner"},
 244         "go/internal/srcimporter":   {"L4", "OS", "fmt", "go/ast", "go/build", "go/parser", "go/token", "go/types", "path/filepath"},
 245         "go/types":                  {"L4", "GOPARSER", "container/heap", "go/constant"},
 246
 247         // One of a kind.
 248         "archive/tar":                    {"L4", "OS", "syscall", "os/user"},
 249         "archive/zip":                    {"L4", "OS", "compress/flate"},
 250         "container/heap":                 {"sort"},
 251         "compress/bzip2":                 {"L4"},
 252         "compress/flate":                 {"L4"},
 253         "compress/gzip":                  {"L4", "compress/flate"},
 254         "compress/lzw":                   {"L4"},
 255         "compress/zlib":                  {"L4", "compress/flate"},
 256         "context":                        {"errors", "internal/reflectlite", "sync", "sync/atomic", "time"},
 257         "database/sql":                   {"L4", "container/list", "context", "database/sql/driver", "database/sql/internal"},
 258         "database/sql/driver":            {"L4", "context", "time", "database/sql/internal"},
 259         "debug/dwarf":                    {"L4"},
 260         "debug/elf":                      {"L4", "OS", "debug/dwarf", "compress/zlib"},
 261         "debug/gosym":                    {"L4"},
 262         "debug/macho":                    {"L4", "OS", "debug/dwarf", "compress/zlib"},
 263         "debug/pe":                       {"L4", "OS", "debug/dwarf", "compress/zlib"},
 264         "debug/plan9obj":                 {"L4", "OS"},
 265         "encoding":                       {"L4"},
 266         "encoding/ascii85":               {"L4"},
 267         "encoding/asn1":                  {"L4", "math/big"},
 268         "encoding/csv":                   {"L4"},
 269         "encoding/gob":                   {"L4", "OS", "encoding"},
 270         "encoding/hex":                   {"L4"},
 271         "encoding/json":                  {"L4", "encoding"},
 272         "encoding/pem":                   {"L4"},
 273         "encoding/xml":                   {"L4", "encoding"},
 274         "flag":                           {"L4", "OS"},
 275         "go/build":                       {"L4", "OS", "GOPARSER", "internal/goroot", "internal/goversion"},
 276         "html":                           {"L4"},
 277         "image/draw":                     {"L4", "image/internal/imageutil"},
 278         "image/gif":                      {"L4", "compress/lzw", "image/color/palette", "image/draw"},
 279         "image/internal/imageutil":       {"L4"},
 280         "image/jpeg":                     {"L4", "image/internal/imageutil"},
 281         "image/png":                      {"L4", "compress/zlib"},
 282         "index/suffixarray":              {"L4", "regexp"},
 283         "internal/goroot":                {"L4", "OS"},
 284         "internal/singleflight":          {"sync"},
 285         "internal/trace":                 {"L4", "OS", "container/heap"},
 286         "internal/xcoff":                 {"L4", "OS", "debug/dwarf"},
 287         "math/big":                       {"L4"},
 288         "mime":                           {"L4", "OS", "syscall", "internal/syscall/windows/registry"},
 289         "mime/quotedprintable":           {"L4"},
 290         "net/internal/socktest":          {"L4", "OS", "syscall", "internal/syscall/windows"},
 291         "net/url":                        {"L4"},
 292         "plugin":                         {"L0", "OS", "CGO"},
 293         "runtime/pprof/internal/profile": {"L4", "OS", "compress/gzip", "regexp"},
 294         "testing/internal/testdeps":      {"L4", "internal/testlog", "runtime/pprof", "regexp"},
 295         "text/scanner":                   {"L4", "OS"},
 296         "text/template/parse":            {"L4"},
 297
 298         "html/template": {
 299                 "L4", "OS", "encoding/json", "html", "text/template",
 300                 "text/template/parse",
 301         },
 302         "text/template": {
 303                 "L4", "OS", "net/url", "text/template/parse",
 304         },
 305
 306         // Cgo.
 307         // If you add a dependency on CGO, you must add the package to
 308         // cgoPackages in cmd/dist/test.go.
 309         "runtime/cgo": {"L0", "C"},
 310         "CGO":         {"C", "runtime/cgo"},
 311
 312         // Fake entry to satisfy the pseudo-import "C"
 313         // that shows up in programs that use cgo.
 314         "C": {},
 315
 316         // Race detector/MSan uses cgo.
 317         "runtime/race": {"C"},
 318         "runtime/msan": {"C"},
 319
 320         // Plan 9 alone needs io/ioutil and os.
 321         "os/user": {"L4", "CGO", "io/ioutil", "os", "syscall", "internal/syscall/windows", "internal/syscall/windows/registry"},
 322
 323         // Internal package used only for testing.
 324         "os/signal/internal/pty": {"CGO", "fmt", "os", "syscall"},
 325
 326         // Basic networking.
 327         // Because net must be used by any package that wants to
 328         // do networking portably, it must have a small dependency set: just L0+basic os.
 329         "net": {
 330                 "L0", "CGO",
 331                 "context", "math/rand", "os", "sort", "syscall", "time",
 332                 "internal/nettrace", "internal/poll", "internal/syscall/unix",
 333                 "internal/syscall/windows", "internal/singleflight", "internal/race",
 334                 "golang.org/x/net/dns/dnsmessage", "golang.org/x/net/lif", "golang.org/x/net/route",
 335         },
 336
 337         // NET enables use of basic network-related packages.
 338         "NET": {
 339                 "net",
 340                 "mime",
 341                 "net/textproto",
 342                 "net/url",
 343         },
 344
 345         // Uses of networking.
 346         "log/syslog":    {"L4", "OS", "net"},
 347         "net/mail":      {"L4", "NET", "OS", "mime"},
 348         "net/textproto": {"L4", "OS", "net"},
 349
 350         // Core crypto.
 351         "crypto/aes":               {"L3"},
 352         "crypto/des":               {"L3"},
 353         "crypto/hmac":              {"L3"},
 354         "crypto/internal/randutil": {"io", "sync"},
 355         "crypto/md5":               {"L3"},
 356         "crypto/rc4":               {"L3"},
 357         "crypto/sha1":              {"L3"},
 358         "crypto/sha256":            {"L3"},
 359         "crypto/sha512":            {"L3"},
 360
 361         "CRYPTO": {
 362                 "crypto/aes",
 363                 "crypto/des",
 364                 "crypto/hmac",
 365                 "crypto/internal/randutil",
 366                 "crypto/md5",
 367                 "crypto/rc4",
 368                 "crypto/sha1",
 369                 "crypto/sha256",
 370                 "crypto/sha512",
 371                 "golang.org/x/crypto/chacha20poly1305",
 372                 "golang.org/x/crypto/curve25519",
 373                 "golang.org/x/crypto/poly1305",
 374         },
 375
 376         // Random byte, number generation.
 377         // This would be part of core crypto except that it imports
 378         // math/big, which imports fmt.
 379         "crypto/rand": {"L4", "CRYPTO", "OS", "math/big", "syscall", "syscall/js", "internal/syscall/unix"},
 380
 381         // Not part of CRYPTO because it imports crypto/rand and crypto/sha512.
 382         "crypto/ed25519":                       {"L3", "CRYPTO", "crypto/rand", "crypto/ed25519/internal/edwards25519"},
 383         "crypto/ed25519/internal/edwards25519": {"encoding/binary"},
 384
 385         // Mathematical crypto: dependencies on fmt (L4) and math/big.
 386         // We could avoid some of the fmt, but math/big imports fmt anyway.
 387         "crypto/dsa": {"L4", "CRYPTO", "math/big"},
 388         "crypto/ecdsa": {
 389                 "L4", "CRYPTO", "crypto/elliptic", "math/big",
 390                 "golang.org/x/crypto/cryptobyte", "golang.org/x/crypto/cryptobyte/asn1",
 391         },
 392         "crypto/elliptic": {"L4", "CRYPTO", "math/big"},
 393         "crypto/rsa":      {"L4", "CRYPTO", "crypto/rand", "math/big"},
 394
 395         "CRYPTO-MATH": {
 396                 "CRYPTO",
 397                 "crypto/dsa",
 398                 "crypto/ecdsa",
 399                 "crypto/elliptic",
 400                 "crypto/rand",
 401                 "crypto/rsa",
 402                 "encoding/asn1",
 403                 "math/big",
 404         },
 405
 406         // SSL/TLS.
 407         "crypto/tls": {
 408                 "L4", "CRYPTO-MATH", "OS", "golang.org/x/crypto/cryptobyte", "golang.org/x/crypto/hkdf",
 409                 "container/list", "crypto/x509", "encoding/pem", "net", "syscall", "crypto/ed25519",
 410         },
 411         "crypto/x509": {
 412                 "L4", "CRYPTO-MATH", "OS", "CGO", "crypto/ed25519",
 413                 "crypto/x509/pkix", "encoding/pem", "encoding/hex", "net", "os/user", "syscall", "net/url",
 414                 "golang.org/x/crypto/cryptobyte", "golang.org/x/crypto/cryptobyte/asn1",
 415         },
 416         "crypto/x509/pkix": {"L4", "CRYPTO-MATH", "encoding/hex"},
 417
 418         // Simple net+crypto-aware packages.
 419         "mime/multipart": {"L4", "OS", "mime", "crypto/rand", "net/textproto", "mime/quotedprintable"},
 420         "net/smtp":       {"L4", "CRYPTO", "NET", "crypto/tls"},
 421
 422         // HTTP, kingpin of dependencies.
 423         "net/http": {
 424                 "L4", "NET", "OS",
 425                 "compress/gzip",
 426                 "container/list",
 427                 "context",
 428                 "crypto/rand",
 429                 "crypto/tls",
 430                 "golang.org/x/net/http/httpguts",
 431                 "golang.org/x/net/http/httpproxy",
 432                 "golang.org/x/net/http2/hpack",
 433                 "golang.org/x/net/idna",
 434                 "golang.org/x/text/unicode/norm",
 435                 "golang.org/x/text/width",
 436                 "internal/nettrace",
 437                 "mime/multipart",
 438                 "net/http/httptrace",
 439                 "net/http/internal",
 440                 "runtime/debug",
 441                 "syscall/js",
 442         },
 443         "net/http/internal":  {"L4"},
 444         "net/http/httptrace": {"context", "crypto/tls", "internal/nettrace", "net", "net/textproto", "reflect", "time"},
 445
 446         // HTTP-using packages.
 447         "expvar":             {"L4", "OS", "encoding/json", "net/http"},
 448         "net/http/cgi":       {"L4", "NET", "OS", "crypto/tls", "net/http", "regexp"},
 449         "net/http/cookiejar": {"L4", "NET", "net/http"},
 450         "net/http/fcgi":      {"L4", "NET", "OS", "context", "net/http", "net/http/cgi"},
 451         "net/http/httptest": {
 452                 "L4", "NET", "OS", "crypto/tls", "flag", "net/http", "net/http/internal", "crypto/x509",
 453                 "golang.org/x/net/http/httpguts",
 454         },
 455         "net/http/httputil": {"L4", "NET", "OS", "context", "net/http", "net/http/internal", "golang.org/x/net/http/httpguts"},
 456         "net/http/pprof":    {"L4", "OS", "html/template", "net/http", "runtime/pprof", "runtime/trace"},
 457         "net/rpc":           {"L4", "NET", "encoding/gob", "html/template", "net/http", "go/token"},
 458         "net/rpc/jsonrpc":   {"L4", "NET", "encoding/json", "net/rpc"},
 459 }
 460
 461 // isMacro reports whether p is a package dependency macro
 462 // (uppercase name).
 463 func isMacro(p string) bool {
 464         return 'A' <= p[0] && p[0] <= 'Z'
 465 }
 466
 467 func allowed(pkg string) map[string]bool {
 468         m := map[string]bool{}
 469         var allow func(string)
 470         allow = func(p string) {
 471                 if m[p] {
 472                         return
 473                 }
 474                 m[p] = true // set even for macros, to avoid loop on cycle
 475
 476                 // Upper-case names are macro-expanded.
 477                 if isMacro(p) {
 478                         for _, pp := range pkgDeps[p] {
 479                                 allow(pp)
 480                         }
 481                 }
 482         }
 483         for _, pp := range pkgDeps[pkg] {
 484                 allow(pp)
 485         }
 486         return m
 487 }
 488
 489 // listStdPkgs returns the same list of packages as "go list std".
 490 func listStdPkgs(goroot string) ([]string, error) {
 491         // Based on cmd/go's matchPackages function.
 492         var pkgs []string
 493
 494         src := filepath.Join(goroot, "src") + string(filepath.Separator)
 495         walkFn := func(path string, fi os.FileInfo, err error) error {
 496                 if err != nil || !fi.IsDir() || path == src {
 497                         return nil
 498                 }
 499
 500                 base := filepath.Base(path)
 501                 if strings.HasPrefix(base, ".") || strings.HasPrefix(base, "_") || base == "testdata" {
 502                         return filepath.SkipDir
 503                 }
 504
 505                 name := filepath.ToSlash(path[len(src):])
 506                 if name == "builtin" || name == "cmd" || strings.Contains(name, "golang.org/x/") {
 507                         return filepath.SkipDir
 508                 }
 509
 510                 pkgs = append(pkgs, name)
 511                 return nil
 512         }
 513         if err := filepath.Walk(src, walkFn); err != nil {
 514                 return nil, err
 515         }
 516         return pkgs, nil
 517 }
 518
 519 func TestDependencies(t *testing.T) {
 520         iOS := runtime.GOOS == "darwin" && runtime.GOARCH == "arm64"
 521         if iOS {
 522                 // Tests run in a limited file system and we do not
 523                 // provide access to every source file.
 524                 t.Skipf("skipping on %s/%s, missing full GOROOT", runtime.GOOS, runtime.GOARCH)
 525         }
 526
 527         ctxt := Default
 528         all, err := listStdPkgs(ctxt.GOROOT)
 529         if err != nil {
 530                 t.Fatal(err)
 531         }
 532         sort.Strings(all)
 533
 534         sawImport := map[string]map[string]bool{} // from package => to package => true
 535
 536         for _, pkg := range all {
 537                 imports, err := findImports(pkg)
 538                 if err != nil {
 539                         t.Error(err)
 540                         continue
 541                 }
 542                 if sawImport[pkg] == nil {
 543                         sawImport[pkg] = map[string]bool{}
 544                 }
 545                 ok := allowed(pkg)
 546                 var bad []string
 547                 for _, imp := range imports {
 548                         sawImport[pkg][imp] = true
 549                         if !ok[imp] {
 550                                 bad = append(bad, imp)
 551                         }
 552                 }
 553                 if bad != nil {
 554                         t.Errorf("unexpected dependency: %s imports %v", pkg, bad)
 555                 }
 556         }
 557
 558         // depPath returns the path between the given from and to packages.
 559         // It returns the empty string if there's no dependency path.
 560         var depPath func(string, string) string
 561         depPath = func(from, to string) string {
 562                 if sawImport[from][to] {
 563                         return from + " => " + to
 564                 }
 565                 for pkg := range sawImport[from] {
 566                         if p := depPath(pkg, to); p != "" {
 567                                 return from + " => " + p
 568                         }
 569                 }
 570                 return ""
 571         }
 572
 573         // Also test some high-level policy goals are being met by not finding
 574         // these dependency paths:
 575         badPaths := []struct{ from, to string }{
 576                 {"net", "unicode"},
 577                 {"os", "unicode"},
 578         }
 579
 580         for _, path := range badPaths {
 581                 if how := depPath(path.from, path.to); how != "" {
 582                         t.Errorf("policy violation: %s", how)
 583                 }
 584         }
 585
 586 }
 587
 588 var buildIgnore = []byte("\n// +build ignore")
 589
 590 func findImports(pkg string) ([]string, error) {
 591         dir := filepath.Join(Default.GOROOT, "src", pkg)
 592         files, err := ioutil.ReadDir(dir)
 593         if err != nil {
 594                 return nil, err
 595         }
 596         var imports []string
 597         var haveImport = map[string]bool{}
 598         for _, file := range files {
 599                 name := file.Name()
 600                 if name == "slice_go14.go" || name == "slice_go18.go" {
 601                         // These files are for compiler bootstrap with older versions of Go and not built in the standard build.
 602                         continue
 603                 }
 604                 if !strings.HasSuffix(name, ".go") || strings.HasSuffix(name, "_test.go") {
 605                         continue
 606                 }
 607                 f, err := os.Open(filepath.Join(dir, name))
 608                 if err != nil {
 609                         return nil, err
 610                 }
 611                 var imp []string
 612                 data, err := readImports(f, false, &imp)
 613                 f.Close()
 614                 if err != nil {
 615                         return nil, fmt.Errorf("reading %v: %v", name, err)
 616                 }
 617                 if bytes.Contains(data, buildIgnore) {
 618                         continue
 619                 }
 620                 for _, quoted := range imp {
 621                         path, err := strconv.Unquote(quoted)
 622                         if err != nil {
 623                                 continue
 624                         }
 625                         if !haveImport[path] {
 626                                 haveImport[path] = true
 627                                 imports = append(imports, path)
 628                         }
 629                 }
 630         }
 631         sort.Strings(imports)
 632         return imports, nil
 633 }