]> Cypherpunks.ru repositories - gostls13.git/blob - src/go/build/deps_test.go
slices: add sorting and comparison functions
[gostls13.git] / src / go / build / deps_test.go
1 // Copyright 2022 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         "go/token"
14         "internal/dag"
15         "internal/testenv"
16         "io/fs"
17         "os"
18         "path/filepath"
19         "runtime"
20         "sort"
21         "strings"
22         "testing"
23 )
24
25 // depsRules defines the expected dependencies between packages in
26 // the Go source tree. It is a statement of policy.
27 //
28 // DO NOT CHANGE THIS DATA TO FIX BUILDS.
29 // Existing packages should not have their constraints relaxed
30 // without prior discussion.
31 // Negative assertions should almost never be removed.
32 //
33 // "a < b" means package b can import package a.
34 //
35 // See `go doc internal/dag' for the full syntax.
36 //
37 // All-caps names are pseudo-names for specific points
38 // in the dependency lattice.
39 var depsRules = `
40         # No dependencies allowed for any of these packages.
41         NONE
42         < cmp, container/list, container/ring,
43           internal/cfg, internal/coverage, internal/coverage/rtcov,
44           internal/coverage/uleb128, internal/coverage/calloc,
45           internal/cpu, internal/goarch, internal/godebugs,
46           internal/goexperiment, internal/goos,
47           internal/goversion, internal/nettrace, internal/platform,
48           log/internal,
49           unicode/utf8, unicode/utf16, unicode,
50           unsafe;
51
52         # These packages depend only on internal/goarch and unsafe.
53         internal/goarch, unsafe
54         < internal/abi;
55
56         unsafe < maps;
57
58         # RUNTIME is the core runtime group of packages, all of them very light-weight.
59         internal/abi, internal/cpu, internal/goarch,
60         internal/coverage/rtcov, internal/godebugs, internal/goexperiment,
61         internal/goos, unsafe
62         < internal/bytealg
63         < internal/itoa
64         < internal/unsafeheader
65         < runtime/internal/sys
66         < runtime/internal/syscall
67         < runtime/internal/atomic
68         < runtime/internal/math
69         < runtime
70         < sync/atomic
71         < internal/race
72         < sync
73         < internal/bisect
74         < internal/godebug
75         < internal/reflectlite
76         < errors
77         < internal/oserror, math/bits
78         < RUNTIME;
79
80         RUNTIME
81         < sort
82         < container/heap;
83
84         RUNTIME
85         < io;
86
87         RUNTIME
88         < arena;
89
90         syscall !< io;
91         reflect !< sort;
92
93         RUNTIME, unicode/utf8
94         < path;
95
96         unicode !< path;
97
98         # SYSCALL is RUNTIME plus the packages necessary for basic system calls.
99         RUNTIME, unicode/utf8, unicode/utf16
100         < internal/syscall/windows/sysdll, syscall/js
101         < syscall
102         < internal/syscall/unix, internal/syscall/windows, internal/syscall/windows/registry
103         < internal/syscall/execenv
104         < SYSCALL;
105
106         # TIME is SYSCALL plus the core packages about time, including context.
107         SYSCALL
108         < time/tzdata
109         < time
110         < context
111         < TIME;
112
113         TIME, io, path, sort
114         < io/fs;
115
116         # MATH is RUNTIME plus the basic math packages.
117         RUNTIME
118         < math
119         < MATH;
120
121         unicode !< math;
122
123         MATH
124         < math/cmplx;
125
126         MATH
127         < math/rand;
128
129         MATH
130         < runtime/metrics;
131
132         MATH, unicode/utf8
133         < strconv;
134
135         unicode !< strconv;
136
137         # STR is basic string and buffer manipulation.
138         RUNTIME, io, unicode/utf8, unicode/utf16, unicode
139         < bytes, strings
140         < bufio;
141
142         bufio, path, strconv
143         < STR;
144
145         # OS is basic OS access, including helpers (path/filepath, os/exec, etc).
146         # OS includes string routines, but those must be layered above package os.
147         # OS does not include reflection.
148         io/fs
149         < internal/testlog
150         < internal/poll
151         < internal/safefilepath
152         < os
153         < os/signal;
154
155         io/fs
156         < embed;
157
158         unicode, fmt !< net, os, os/signal;
159
160         os/signal, STR
161         < path/filepath
162         < io/ioutil;
163
164         path/filepath, internal/godebug < os/exec;
165
166         io/ioutil, os/exec, os/signal
167         < OS;
168
169         reflect !< OS;
170
171         OS
172         < golang.org/x/sys/cpu;
173
174         # FMT is OS (which includes string routines) plus reflect and fmt.
175         # It does not include package log, which should be avoided in core packages.
176         arena, strconv, unicode
177         < reflect;
178
179         os, reflect
180         < internal/fmtsort
181         < fmt;
182
183         OS, fmt
184         < FMT;
185
186         log !< FMT;
187
188         # Misc packages needing only FMT.
189         FMT
190         < html,
191           internal/dag,
192           internal/goroot,
193           internal/types/errors,
194           mime/quotedprintable,
195           net/internal/socktest,
196           net/url,
197           runtime/trace,
198           text/scanner,
199           text/tabwriter;
200
201         io, reflect
202         < internal/saferio;
203
204         # encodings
205         # core ones do not use fmt.
206         io, strconv
207         < encoding;
208
209         encoding, reflect
210         < encoding/binary
211         < encoding/base32, encoding/base64;
212
213         FMT, encoding < flag;
214
215         fmt !< encoding/base32, encoding/base64;
216
217         FMT, encoding/base32, encoding/base64, internal/saferio
218         < encoding/ascii85, encoding/csv, encoding/gob, encoding/hex,
219           encoding/json, encoding/pem, encoding/xml, mime;
220
221         # hashes
222         io
223         < hash
224         < hash/adler32, hash/crc32, hash/crc64, hash/fnv;
225
226         # slices depends on unsafe for overlapping check, cmp for comparison
227         # semantics, and math/bits for # calculating bitlength of numbers.
228         unsafe, cmp, math/bits
229         < slices;
230
231         # math/big
232         FMT, encoding/binary, math/rand
233         < math/big;
234
235         # compression
236         FMT, encoding/binary, hash/adler32, hash/crc32
237         < compress/bzip2, compress/flate, compress/lzw, internal/zstd
238         < archive/zip, compress/gzip, compress/zlib;
239
240         # templates
241         FMT
242         < text/template/parse;
243
244         net/url, text/template/parse
245         < text/template
246         < internal/lazytemplate;
247
248         encoding/json, html, text/template
249         < html/template;
250
251         # regexp
252         FMT
253         < regexp/syntax
254         < regexp
255         < internal/lazyregexp;
256
257         # suffix array
258         encoding/binary, regexp
259         < index/suffixarray;
260
261         # executable parsing
262         FMT, encoding/binary, compress/zlib, internal/saferio, internal/zstd
263         < runtime/debug
264         < debug/dwarf
265         < debug/elf, debug/gosym, debug/macho, debug/pe, debug/plan9obj, internal/xcoff
266         < debug/buildinfo
267         < DEBUG;
268
269         # go parser and friends.
270         FMT
271         < go/token
272         < go/scanner
273         < go/ast
274         < go/internal/typeparams;
275
276         FMT
277         < go/build/constraint, go/doc/comment;
278
279         go/internal/typeparams, go/build/constraint
280         < go/parser;
281
282         go/doc/comment, go/parser, text/tabwriter
283         < go/printer
284         < go/format;
285
286         math/big, go/token
287         < go/constant;
288
289         container/heap, go/constant, go/parser, internal/types/errors
290         < go/types;
291
292         # The vast majority of standard library packages should not be resorting to regexp.
293         # go/types is a good chokepoint. It shouldn't use regexp, nor should anything
294         # that is low-enough level to be used by go/types.
295         regexp !< go/types;
296
297         go/doc/comment, go/parser, internal/lazyregexp, text/template
298         < go/doc;
299
300         FMT, internal/goexperiment
301         < internal/buildcfg;
302
303         go/build/constraint, go/doc, go/parser, internal/buildcfg, internal/goroot, internal/goversion, internal/platform
304         < go/build;
305
306         # databases
307         FMT
308         < database/sql/internal
309         < database/sql/driver
310         < database/sql;
311
312         # images
313         FMT, compress/lzw, compress/zlib
314         < image/color
315         < image, image/color/palette
316         < image/internal/imageutil
317         < image/draw
318         < image/gif, image/jpeg, image/png;
319
320         # cgo, delayed as long as possible.
321         # If you add a dependency on CGO, you must add the package
322         # to cgoPackages in cmd/dist/test.go as well.
323         RUNTIME
324         < C
325         < runtime/cgo
326         < CGO
327         < runtime/msan, runtime/asan;
328
329         # runtime/race
330         NONE < runtime/race/internal/amd64v1;
331         NONE < runtime/race/internal/amd64v3;
332         CGO, runtime/race/internal/amd64v1, runtime/race/internal/amd64v3 < runtime/race;
333
334         # Bulk of the standard library must not use cgo.
335         # The prohibition stops at net and os/user.
336         C !< fmt, go/types, CRYPTO-MATH, log/slog;
337
338         CGO, OS
339         < plugin;
340
341         CGO, FMT
342         < os/user
343         < archive/tar;
344
345         sync
346         < internal/singleflight;
347
348         os
349         < golang.org/x/net/dns/dnsmessage,
350           golang.org/x/net/lif,
351           golang.org/x/net/route;
352
353         os, runtime, strconv, sync, unsafe,
354         internal/godebug
355         < internal/intern;
356
357         internal/bytealg, internal/intern, internal/itoa, math/bits, sort, strconv
358         < net/netip;
359
360         # net is unavoidable when doing any networking,
361         # so large dependencies must be kept out.
362         # This is a long-looking list but most of these
363         # are small with few dependencies.
364         CGO,
365         golang.org/x/net/dns/dnsmessage,
366         golang.org/x/net/lif,
367         golang.org/x/net/route,
368         internal/godebug,
369         internal/nettrace,
370         internal/poll,
371         internal/singleflight,
372         internal/race,
373         net/netip,
374         os
375         < net;
376
377         fmt, unicode !< net;
378         math/rand !< net; # net uses runtime instead
379
380         # NET is net plus net-helper packages.
381         FMT, net
382         < net/textproto;
383
384         mime, net/textproto, net/url
385         < NET;
386
387         # logging - most packages should not import; http and up is allowed
388         FMT, log/internal
389         < log;
390
391         log, log/slog !< crypto/tls, database/sql, go/importer, testing;
392
393         FMT, log, net
394         < log/syslog;
395
396         RUNTIME
397         < log/slog/internal, log/slog/internal/buffer;
398
399         FMT,
400         encoding, encoding/json,
401         log, log/internal,
402         log/slog/internal, log/slog/internal/buffer,
403         slices
404         < log/slog
405         < log/slog/internal/slogtest, log/slog/internal/benchmarks;
406
407         NET, log
408         < net/mail;
409
410         NONE < crypto/internal/boring/sig, crypto/internal/boring/syso;
411         sync/atomic < crypto/internal/boring/bcache, crypto/internal/boring/fipstls;
412         crypto/internal/boring/sig, crypto/internal/boring/fipstls < crypto/tls/fipsonly;
413
414         # CRYPTO is core crypto algorithms - no cgo, fmt, net.
415         # Unfortunately, stuck with reflect via encoding/binary.
416         crypto/internal/boring/sig,
417         crypto/internal/boring/syso,
418         encoding/binary,
419         golang.org/x/sys/cpu,
420         hash, embed
421         < crypto
422         < crypto/subtle
423         < crypto/internal/alias
424         < crypto/cipher;
425
426         crypto/cipher,
427         crypto/internal/boring/bcache
428         < crypto/internal/boring
429         < crypto/boring;
430
431         crypto/internal/alias
432         < crypto/internal/randutil
433         < crypto/internal/nistec/fiat
434         < crypto/internal/nistec
435         < crypto/internal/edwards25519/field
436         < crypto/internal/edwards25519;
437
438         crypto/boring
439         < crypto/aes, crypto/des, crypto/hmac, crypto/md5, crypto/rc4,
440           crypto/sha1, crypto/sha256, crypto/sha512;
441
442         crypto/boring, crypto/internal/edwards25519/field
443         < crypto/ecdh;
444
445         crypto/aes,
446         crypto/des,
447         crypto/ecdh,
448         crypto/hmac,
449         crypto/internal/edwards25519,
450         crypto/md5,
451         crypto/rc4,
452         crypto/sha1,
453         crypto/sha256,
454         crypto/sha512
455         < CRYPTO;
456
457         CGO, fmt, net !< CRYPTO;
458
459         # CRYPTO-MATH is core bignum-based crypto - no cgo, net; fmt now ok.
460         CRYPTO, FMT, math/big
461         < crypto/internal/boring/bbig
462         < crypto/rand
463         < crypto/ed25519
464         < encoding/asn1
465         < golang.org/x/crypto/cryptobyte/asn1
466         < golang.org/x/crypto/cryptobyte
467         < crypto/internal/bigmod
468         < crypto/dsa, crypto/elliptic, crypto/rsa
469         < crypto/ecdsa
470         < CRYPTO-MATH;
471
472         CGO, net !< CRYPTO-MATH;
473
474         # TLS, Prince of Dependencies.
475         CRYPTO-MATH, NET, container/list, encoding/hex, encoding/pem
476         < golang.org/x/crypto/internal/alias
477         < golang.org/x/crypto/internal/subtle
478         < golang.org/x/crypto/chacha20
479         < golang.org/x/crypto/internal/poly1305
480         < golang.org/x/crypto/chacha20poly1305
481         < golang.org/x/crypto/hkdf
482         < crypto/x509/internal/macos
483         < crypto/x509/pkix;
484
485         crypto/internal/boring/fipstls, crypto/x509/pkix
486         < crypto/x509
487         < crypto/tls;
488
489         # crypto-aware packages
490
491         DEBUG, go/build, go/types, text/scanner, crypto/md5
492         < internal/pkgbits
493         < go/internal/gcimporter, go/internal/gccgoimporter, go/internal/srcimporter
494         < go/importer;
495
496         NET, crypto/rand, mime/quotedprintable
497         < mime/multipart;
498
499         crypto/tls
500         < net/smtp;
501
502         crypto/rand
503         < hash/maphash; # for purego implementation
504
505         # HTTP, King of Dependencies.
506
507         FMT
508         < golang.org/x/net/http2/hpack
509         < net/http/internal, net/http/internal/ascii, net/http/internal/testcert;
510
511         FMT, NET, container/list, encoding/binary, log
512         < golang.org/x/text/transform
513         < golang.org/x/text/unicode/norm
514         < golang.org/x/text/unicode/bidi
515         < golang.org/x/text/secure/bidirule
516         < golang.org/x/net/idna
517         < golang.org/x/net/http/httpguts, golang.org/x/net/http/httpproxy;
518
519         NET, crypto/tls
520         < net/http/httptrace;
521
522         compress/gzip,
523         golang.org/x/net/http/httpguts,
524         golang.org/x/net/http/httpproxy,
525         golang.org/x/net/http2/hpack,
526         net/http/internal,
527         net/http/internal/ascii,
528         net/http/internal/testcert,
529         net/http/httptrace,
530         mime/multipart,
531         log
532         < net/http;
533
534         # HTTP-aware packages
535
536         encoding/json, net/http
537         < expvar;
538
539         net/http, net/http/internal/ascii
540         < net/http/cookiejar, net/http/httputil;
541
542         net/http, flag
543         < net/http/httptest;
544
545         net/http, regexp
546         < net/http/cgi
547         < net/http/fcgi;
548
549         # Profiling
550         FMT, compress/gzip, encoding/binary, text/tabwriter
551         < runtime/pprof;
552
553         OS, compress/gzip, internal/lazyregexp
554         < internal/profile;
555
556         html, internal/profile, net/http, runtime/pprof, runtime/trace
557         < net/http/pprof;
558
559         # RPC
560         encoding/gob, encoding/json, go/token, html/template, net/http
561         < net/rpc
562         < net/rpc/jsonrpc;
563
564         # System Information
565         internal/cpu, sync
566         < internal/sysinfo;
567
568         # Test-only
569         log
570         < testing/iotest
571         < testing/fstest;
572
573         log/slog
574         < testing/slogtest;
575
576         FMT, flag, math/rand
577         < testing/quick;
578
579         FMT, DEBUG, flag, runtime/trace, internal/sysinfo, math/rand
580         < testing;
581
582         FMT, crypto/sha256, encoding/json, go/ast, go/parser, go/token,
583         internal/godebug, math/rand, encoding/hex, crypto/sha256
584         < internal/fuzz;
585
586         internal/fuzz, internal/testlog, runtime/pprof, regexp
587         < testing/internal/testdeps;
588
589         OS, flag, testing, internal/cfg, internal/platform, internal/goroot
590         < internal/testenv;
591
592         OS, encoding/base64
593         < internal/obscuretestdata;
594
595         CGO, OS, fmt
596         < internal/testpty;
597
598         NET, testing, math/rand
599         < golang.org/x/net/nettest;
600
601         syscall
602         < os/exec/internal/fdtest;
603
604         FMT, container/heap, math/rand
605         < internal/trace;
606
607         FMT
608         < internal/diff, internal/txtar;
609
610         FMT, crypto/md5, encoding/binary, regexp, sort, text/tabwriter, unsafe,
611         internal/coverage, internal/coverage/uleb128
612         < internal/coverage/cmerge,
613           internal/coverage/pods,
614           internal/coverage/slicereader,
615           internal/coverage/slicewriter;
616
617         internal/coverage/slicereader, internal/coverage/slicewriter
618         < internal/coverage/stringtab
619         < internal/coverage/decodecounter, internal/coverage/decodemeta,
620           internal/coverage/encodecounter, internal/coverage/encodemeta;
621
622         internal/coverage/cmerge
623         < internal/coverage/cformat;
624
625     encoding/json,
626         runtime/debug,
627         internal/coverage/calloc,
628         internal/coverage/cformat,
629         internal/coverage/decodecounter, internal/coverage/decodemeta,
630         internal/coverage/encodecounter, internal/coverage/encodemeta,
631         internal/coverage/pods
632         < runtime/coverage;
633 `
634
635 // listStdPkgs returns the same list of packages as "go list std".
636 func listStdPkgs(goroot string) ([]string, error) {
637         // Based on cmd/go's matchPackages function.
638         var pkgs []string
639
640         src := filepath.Join(goroot, "src") + string(filepath.Separator)
641         walkFn := func(path string, d fs.DirEntry, err error) error {
642                 if err != nil || !d.IsDir() || path == src {
643                         return nil
644                 }
645
646                 base := filepath.Base(path)
647                 if strings.HasPrefix(base, ".") || strings.HasPrefix(base, "_") || base == "testdata" {
648                         return filepath.SkipDir
649                 }
650
651                 name := filepath.ToSlash(path[len(src):])
652                 if name == "builtin" || name == "cmd" {
653                         return filepath.SkipDir
654                 }
655
656                 pkgs = append(pkgs, strings.TrimPrefix(name, "vendor/"))
657                 return nil
658         }
659         if err := filepath.WalkDir(src, walkFn); err != nil {
660                 return nil, err
661         }
662         return pkgs, nil
663 }
664
665 func TestDependencies(t *testing.T) {
666         if !testenv.HasSrc() {
667                 // Tests run in a limited file system and we do not
668                 // provide access to every source file.
669                 t.Skipf("skipping on %s/%s, missing full GOROOT", runtime.GOOS, runtime.GOARCH)
670         }
671
672         ctxt := Default
673         all, err := listStdPkgs(ctxt.GOROOT)
674         if err != nil {
675                 t.Fatal(err)
676         }
677         sort.Strings(all)
678
679         sawImport := map[string]map[string]bool{} // from package => to package => true
680         policy := depsPolicy(t)
681
682         for _, pkg := range all {
683                 imports, err := findImports(pkg)
684                 if err != nil {
685                         t.Error(err)
686                         continue
687                 }
688                 if sawImport[pkg] == nil {
689                         sawImport[pkg] = map[string]bool{}
690                 }
691                 var bad []string
692                 for _, imp := range imports {
693                         sawImport[pkg][imp] = true
694                         if !policy.HasEdge(pkg, imp) {
695                                 bad = append(bad, imp)
696                         }
697                 }
698                 if bad != nil {
699                         t.Errorf("unexpected dependency: %s imports %v", pkg, bad)
700                 }
701         }
702 }
703
704 var buildIgnore = []byte("\n//go:build ignore")
705
706 func findImports(pkg string) ([]string, error) {
707         vpkg := pkg
708         if strings.HasPrefix(pkg, "golang.org") {
709                 vpkg = "vendor/" + pkg
710         }
711         dir := filepath.Join(Default.GOROOT, "src", vpkg)
712         files, err := os.ReadDir(dir)
713         if err != nil {
714                 return nil, err
715         }
716         var imports []string
717         var haveImport = map[string]bool{}
718         if pkg == "crypto/internal/boring" {
719                 haveImport["C"] = true // kludge: prevent C from appearing in crypto/internal/boring imports
720         }
721         fset := token.NewFileSet()
722         for _, file := range files {
723                 name := file.Name()
724                 if name == "slice_go14.go" || name == "slice_go18.go" {
725                         // These files are for compiler bootstrap with older versions of Go and not built in the standard build.
726                         continue
727                 }
728                 if !strings.HasSuffix(name, ".go") || strings.HasSuffix(name, "_test.go") {
729                         continue
730                 }
731                 info := fileInfo{
732                         name: filepath.Join(dir, name),
733                         fset: fset,
734                 }
735                 f, err := os.Open(info.name)
736                 if err != nil {
737                         return nil, err
738                 }
739                 err = readGoInfo(f, &info)
740                 f.Close()
741                 if err != nil {
742                         return nil, fmt.Errorf("reading %v: %v", name, err)
743                 }
744                 if info.parsed.Name.Name == "main" {
745                         continue
746                 }
747                 if bytes.Contains(info.header, buildIgnore) {
748                         continue
749                 }
750                 for _, imp := range info.imports {
751                         path := imp.path
752                         if !haveImport[path] {
753                                 haveImport[path] = true
754                                 imports = append(imports, path)
755                         }
756                 }
757         }
758         sort.Strings(imports)
759         return imports, nil
760 }
761
762 // depsPolicy returns a map m such that m[p][d] == true when p can import d.
763 func depsPolicy(t *testing.T) *dag.Graph {
764         g, err := dag.Parse(depsRules)
765         if err != nil {
766                 t.Fatal(err)
767         }
768         return g
769 }
770
771 // TestStdlibLowercase tests that all standard library package names are
772 // lowercase. See Issue 40065.
773 func TestStdlibLowercase(t *testing.T) {
774         if !testenv.HasSrc() {
775                 t.Skipf("skipping on %s/%s, missing full GOROOT", runtime.GOOS, runtime.GOARCH)
776         }
777
778         ctxt := Default
779         all, err := listStdPkgs(ctxt.GOROOT)
780         if err != nil {
781                 t.Fatal(err)
782         }
783
784         for _, pkgname := range all {
785                 if strings.ToLower(pkgname) != pkgname {
786                         t.Errorf("package %q should not use upper-case path", pkgname)
787                 }
788         }
789 }
790
791 // TestFindImports tests that findImports works.  See #43249.
792 func TestFindImports(t *testing.T) {
793         imports, err := findImports("go/build")
794         if err != nil {
795                 t.Fatal(err)
796         }
797         t.Logf("go/build imports %q", imports)
798         want := []string{"bytes", "os", "path/filepath", "strings"}
799 wantLoop:
800         for _, w := range want {
801                 for _, imp := range imports {
802                         if imp == w {
803                                 continue wantLoop
804                         }
805                 }
806                 t.Errorf("expected to find %q in import list", w)
807         }
808 }