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