1 // Copyright 2015 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 // Package loader loads a complete Go program from source code, parsing
6 // and type-checking the initial packages plus their transitive closure
7 // of dependencies. The ASTs and the derived facts are retained for
8 // later use.
9 //
10 // Deprecated: This is an older API and does not have support
11 // for modules. Use golang.org/x/tools/go/packages instead.
12 //
13 // The package defines two primary types: Config, which specifies a
14 // set of initial packages to load and various other options; and
15 // Program, which is the result of successfully loading the packages
16 // specified by a configuration.
17 //
18 // The configuration can be set directly, but *Config provides various
19 // convenience methods to simplify the common cases, each of which can
20 // be called any number of times. Finally, these are followed by a
21 // call to Load() to actually load and type-check the program.
22 //
23 // var conf loader.Config
24 //
25 // // Use the command-line arguments to specify
26 // // a set of initial packages to load from source.
27 // // See FromArgsUsage for help.
28 // rest, err := conf.FromArgs(os.Args[1:], wantTests)
29 //
30 // // Parse the specified files and create an ad hoc package with path "foo".
31 // // All files must have the same 'package' declaration.
32 // conf.CreateFromFilenames("foo", "foo.go", "bar.go")
33 //
34 // // Create an ad hoc package with path "foo" from
35 // // the specified already-parsed files.
36 // // All ASTs must have the same 'package' declaration.
37 // conf.CreateFromFiles("foo", parsedFiles)
38 //
39 // // Add "runtime" to the set of packages to be loaded.
40 // conf.Import("runtime")
41 //
42 // // Adds "fmt" and "fmt_test" to the set of packages
43 // // to be loaded. "fmt" will include *_test.go files.
44 // conf.ImportWithTests("fmt")
45 //
46 // // Finally, load all the packages specified by the configuration.
47 // prog, err := conf.Load()
48 //
49 // See examples_test.go for examples of API usage.
50 //
51 // # CONCEPTS AND TERMINOLOGY
52 //
53 // The WORKSPACE is the set of packages accessible to the loader. The
54 // workspace is defined by Config.Build, a *build.Context. The
55 // default context treats subdirectories of $GOROOT and $GOPATH as
56 // packages, but this behavior may be overridden.
57 //
58 // An AD HOC package is one specified as a set of source files on the
59 // command line. In the simplest case, it may consist of a single file
60 // such as $GOROOT/src/net/http/triv.go.
61 //
62 // EXTERNAL TEST packages are those comprised of a set of *_test.go
63 // files all with the same 'package foo_test' declaration, all in the
64 // same directory. (go/build.Package calls these files XTestFiles.)
65 //
66 // An IMPORTABLE package is one that can be referred to by some import
67 // spec. Every importable package is uniquely identified by its
68 // PACKAGE PATH or just PATH, a string such as "fmt", "encoding/json",
69 // or "cmd/vendor/golang.org/x/arch/x86/x86asm". A package path
70 // typically denotes a subdirectory of the workspace.
71 //
72 // An import declaration uses an IMPORT PATH to refer to a package.
73 // Most import declarations use the package path as the import path.
74 //
75 // Due to VENDORING (https://golang.org/s/go15vendor), the
76 // interpretation of an import path may depend on the directory in which
77 // it appears. To resolve an import path to a package path, go/build
78 // must search the enclosing directories for a subdirectory named
79 // "vendor".
80 //
81 // ad hoc packages and external test packages are NON-IMPORTABLE. The
82 // path of an ad hoc package is inferred from the package
83 // declarations of its files and is therefore not a unique package key.
84 // For example, Config.CreatePkgs may specify two initial ad hoc
85 // packages, both with path "main".
86 //
87 // An AUGMENTED package is an importable package P plus all the
88 // *_test.go files with same 'package foo' declaration as P.
89 // (go/build.Package calls these files TestFiles.)
90 //
91 // The INITIAL packages are those specified in the configuration. A
92 // DEPENDENCY is a package loaded to satisfy an import in an initial
93 // package or another dependency.
94 package loader
95 96 // IMPLEMENTATION NOTES
97 //
98 // 'go test', in-package test files, and import cycles
99 // ---------------------------------------------------
100 //
101 // An external test package may depend upon members of the augmented
102 // package that are not in the unaugmented package, such as functions
103 // that expose internals. (See bufio/export_test.go for an example.)
104 // So, the loader must ensure that for each external test package
105 // it loads, it also augments the corresponding non-test package.
106 //
107 // The import graph over n unaugmented packages must be acyclic; the
108 // import graph over n-1 unaugmented packages plus one augmented
109 // package must also be acyclic. ('go test' relies on this.) But the
110 // import graph over n augmented packages may contain cycles.
111 //
112 // First, all the (unaugmented) non-test packages and their
113 // dependencies are imported in the usual way; the loader reports an
114 // error if it detects an import cycle.
115 //
116 // Then, each package P for which testing is desired is augmented by
117 // the list P' of its in-package test files, by calling
118 // (*types.Checker).Files. This arrangement ensures that P' may
119 // reference definitions within P, but P may not reference definitions
120 // within P'. Furthermore, P' may import any other package, including
121 // ones that depend upon P, without an import cycle error.
122 //
123 // Consider two packages A and B, both of which have lists of
124 // in-package test files we'll call A' and B', and which have the
125 // following import graph edges:
126 // B imports A
127 // B' imports A
128 // A' imports B
129 // This last edge would be expected to create an error were it not
130 // for the special type-checking discipline above.
131 // Cycles of size greater than two are possible. For example:
132 // compress/bzip2/bzip2_test.go (package bzip2) imports "io/ioutil"
133 // io/ioutil/tempfile_test.go (package ioutil) imports "regexp"
134 // regexp/exec_test.go (package regexp) imports "compress/bzip2"
135 //
136 //
137 // Concurrency
138 // -----------
139 //
140 // Let us define the import dependency graph as follows. Each node is a
141 // list of files passed to (Checker).Files at once. Many of these lists
142 // are the production code of an importable Go package, so those nodes
143 // are labelled by the package's path. The remaining nodes are
144 // ad hoc packages and lists of in-package *_test.go files that augment
145 // an importable package; those nodes have no label.
146 //
147 // The edges of the graph represent import statements appearing within a
148 // file. An edge connects a node (a list of files) to the node it
149 // imports, which is importable and thus always labelled.
150 //
151 // Loading is controlled by this dependency graph.
152 //
153 // To reduce I/O latency, we start loading a package's dependencies
154 // asynchronously as soon as we've parsed its files and enumerated its
155 // imports (scanImports). This performs a preorder traversal of the
156 // import dependency graph.
157 //
158 // To exploit hardware parallelism, we type-check unrelated packages in
159 // parallel, where "unrelated" means not ordered by the partial order of
160 // the import dependency graph.
161 //
162 // We use a concurrency-safe non-blocking cache (importer.imported) to
163 // record the results of type-checking, whether success or failure. An
164 // entry is created in this cache by startLoad the first time the
165 // package is imported. The first goroutine to request an entry becomes
166 // responsible for completing the task and broadcasting completion to
167 // subsequent requesters, which block until then.
168 //
169 // Type checking occurs in (parallel) postorder: we cannot type-check a
170 // set of files until we have loaded and type-checked all of their
171 // immediate dependencies (and thus all of their transitive
172 // dependencies). If the input were guaranteed free of import cycles,
173 // this would be trivial: we could simply wait for completion of the
174 // dependencies and then invoke the typechecker.
175 //
176 // But as we saw in the 'go test' section above, some cycles in the
177 // import graph over packages are actually legal, so long as the
178 // cycle-forming edge originates in the in-package test files that
179 // augment the package. This explains why the nodes of the import
180 // dependency graph are not packages, but lists of files: the unlabelled
181 // nodes avoid the cycles. Consider packages A and B where B imports A
182 // and A's in-package tests AT import B. The naively constructed import
183 // graph over packages would contain a cycle (A+AT) --> B --> (A+AT) but
184 // the graph over lists of files is AT --> B --> A, where AT is an
185 // unlabelled node.
186 //
187 // Awaiting completion of the dependencies in a cyclic graph would
188 // deadlock, so we must materialize the import dependency graph (as
189 // importer.graph) and check whether each import edge forms a cycle. If
190 // x imports y, and the graph already contains a path from y to x, then
191 // there is an import cycle, in which case the processing of x must not
192 // wait for the completion of processing of y.
193 //
194 // When the type-checker makes a callback (doImport) to the loader for a
195 // given import edge, there are two possible cases. In the normal case,
196 // the dependency has already been completely type-checked; doImport
197 // does a cache lookup and returns it. In the cyclic case, the entry in
198 // the cache is still necessarily incomplete, indicating a cycle. We
199 // perform the cycle check again to obtain the error message, and return
200 // the error.
201 //
202 // The result of using concurrency is about a 2.5x speedup for stdlib_test.
203