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 requestors, 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