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