1 // Copyright 2013 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 ssa
6 7 // This file implements the CREATE phase of SSA construction.
8 // See builder.go for explanation.
9 10 import (
11 "fmt"
12 "go/ast"
13 "go/token"
14 "go/types"
15 "os"
16 "sync"
17 18 "golang.org/x/tools/internal/versions"
19 )
20 21 // NewProgram returns a new SSA Program.
22 //
23 // mode controls diagnostics and checking during SSA construction.
24 //
25 // To construct an SSA program:
26 //
27 // - Call NewProgram to create an empty Program.
28 // - Call CreatePackage providing typed syntax for each package
29 // you want to build, and call it with types but not
30 // syntax for each of those package's direct dependencies.
31 // - Call [Package.Build] on each syntax package you wish to build,
32 // or [Program.Build] to build all of them.
33 //
34 // See the Example tests for simple examples.
35 func NewProgram(fset *token.FileSet, mode BuilderMode) *Program {
36 return &Program{
37 Fset: fset,
38 imported: make(map[string]*Package),
39 packages: make(map[*types.Package]*Package),
40 mode: mode,
41 canon: newCanonizer(),
42 ctxt: types.NewContext(),
43 }
44 }
45 46 // memberFromObject populates package pkg with a member for the
47 // typechecker object obj.
48 //
49 // For objects from Go source code, syntax is the associated syntax
50 // tree (for funcs and vars only) and goversion defines the
51 // appropriate interpretation; they will be used during the build
52 // phase.
53 func memberFromObject(pkg *Package, obj types.Object, syntax ast.Node, goversion string) {
54 name := obj.Name()
55 switch obj := obj.(type) {
56 case *types.Builtin:
57 if pkg.Pkg != types.Unsafe {
58 panic("unexpected builtin object: " + obj.String())
59 }
60 61 case *types.TypeName:
62 if name != "_" {
63 pkg.Members[name] = &Type{
64 object: obj,
65 pkg: pkg,
66 }
67 }
68 69 case *types.Const:
70 c := &NamedConst{
71 object: obj,
72 Value: NewConst(obj.Val(), obj.Type()),
73 pkg: pkg,
74 }
75 pkg.objects[obj] = c
76 if name != "_" {
77 pkg.Members[name] = c
78 }
79 80 case *types.Var:
81 g := &Global{
82 Pkg: pkg,
83 name: name,
84 object: obj,
85 typ: types.NewPointer(obj.Type()), // address
86 pos: obj.Pos(),
87 }
88 pkg.objects[obj] = g
89 if name != "_" {
90 pkg.Members[name] = g
91 }
92 93 case *types.Func:
94 sig := obj.Type().(*types.Signature)
95 if sig.Recv() == nil && name == "init" {
96 pkg.ninit++
97 name = fmt.Sprintf("init#%d", pkg.ninit)
98 }
99 fn := createFunction(pkg.Prog, obj, name, syntax, pkg.info, goversion)
100 fn.Pkg = pkg
101 pkg.created = append(pkg.created, fn)
102 pkg.objects[obj] = fn
103 if name != "_" && sig.Recv() == nil {
104 pkg.Members[name] = fn // package-level function
105 }
106 107 default: // (incl. *types.Package)
108 panic("unexpected Object type: " + obj.String())
109 }
110 }
111 112 // createFunction creates a function or method. It supports both
113 // CreatePackage (with or without syntax) and the on-demand creation
114 // of methods in non-created packages based on their types.Func.
115 func createFunction(prog *Program, obj *types.Func, name string, syntax ast.Node, info *types.Info, goversion string) *Function {
116 sig := obj.Type().(*types.Signature)
117 118 // Collect type parameters.
119 var tparams *types.TypeParamList
120 if rtparams := sig.RecvTypeParams(); rtparams.Len() > 0 {
121 tparams = rtparams // method of generic type
122 } else if sigparams := sig.TypeParams(); sigparams.Len() > 0 {
123 tparams = sigparams // generic function
124 }
125 126 /* declared function/method (from syntax or export data) */
127 fn := &Function{
128 name: name,
129 object: obj,
130 Signature: sig,
131 build: (*builder).buildFromSyntax,
132 syntax: syntax,
133 info: info,
134 goversion: goversion,
135 pos: obj.Pos(),
136 Pkg: nil, // may be set by caller
137 Prog: prog,
138 typeparams: tparams,
139 }
140 if fn.syntax == nil {
141 fn.Synthetic = "from type information"
142 fn.build = (*builder).buildParamsOnly
143 }
144 if tparams.Len() > 0 {
145 fn.generic = new(generic)
146 }
147 return fn
148 }
149 150 // membersFromDecl populates package pkg with members for each
151 // typechecker object (var, func, const or type) associated with the
152 // specified decl.
153 func membersFromDecl(pkg *Package, decl ast.Decl, goversion string) {
154 switch decl := decl.(type) {
155 case *ast.GenDecl: // import, const, type or var
156 switch decl.Tok {
157 case token.CONST:
158 for _, spec := range decl.Specs {
159 for _, id := range spec.(*ast.ValueSpec).Names {
160 memberFromObject(pkg, pkg.info.Defs[id], nil, "")
161 }
162 }
163 164 case token.VAR:
165 for _, spec := range decl.Specs {
166 for _, rhs := range spec.(*ast.ValueSpec).Values {
167 pkg.initVersion[rhs] = goversion
168 }
169 for _, id := range spec.(*ast.ValueSpec).Names {
170 memberFromObject(pkg, pkg.info.Defs[id], spec, goversion)
171 }
172 }
173 174 case token.TYPE:
175 for _, spec := range decl.Specs {
176 id := spec.(*ast.TypeSpec).Name
177 memberFromObject(pkg, pkg.info.Defs[id], nil, "")
178 }
179 }
180 181 case *ast.FuncDecl:
182 id := decl.Name
183 memberFromObject(pkg, pkg.info.Defs[id], decl, goversion)
184 }
185 }
186 187 // CreatePackage creates and returns an SSA Package from the
188 // specified type-checked, error-free file ASTs, and populates its
189 // Members mapping.
190 //
191 // importable determines whether this package should be returned by a
192 // subsequent call to ImportedPackage(pkg.Path()).
193 //
194 // The real work of building SSA form for each function is not done
195 // until a subsequent call to Package.Build.
196 func (prog *Program) CreatePackage(pkg *types.Package, files []*ast.File, info *types.Info, importable bool) *Package {
197 if pkg == nil {
198 panic("nil pkg") // otherwise pkg.Scope below returns types.Universe!
199 }
200 p := &Package{
201 Prog: prog,
202 Members: make(map[string]Member),
203 objects: make(map[types.Object]Member),
204 Pkg: pkg,
205 syntax: info != nil,
206 // transient values (cleared after Package.Build)
207 info: info,
208 files: files,
209 initVersion: make(map[ast.Expr]string),
210 }
211 212 /* synthesized package initializer */
213 p.init = &Function{
214 name: "init",
215 Signature: new(types.Signature),
216 Synthetic: "package initializer",
217 Pkg: p,
218 Prog: prog,
219 build: (*builder).buildPackageInit,
220 info: p.info,
221 goversion: "", // See Package.build for details.
222 }
223 p.Members[p.init.name] = p.init
224 p.created = append(p.created, p.init)
225 226 // Allocate all package members: vars, funcs, consts and types.
227 if len(files) > 0 {
228 // Go source package.
229 for _, file := range files {
230 goversion := versions.Lang(versions.FileVersion(p.info, file))
231 for _, decl := range file.Decls {
232 membersFromDecl(p, decl, goversion)
233 }
234 }
235 } else {
236 // GC-compiled binary package (or "unsafe")
237 // No code.
238 // No position information.
239 scope := p.Pkg.Scope()
240 for _, name := range scope.Names() {
241 obj := scope.Lookup(name)
242 memberFromObject(p, obj, nil, "")
243 if obj, ok := obj.(*types.TypeName); ok {
244 // No Unalias: aliases should not duplicate methods.
245 if named, ok := obj.Type().(*types.Named); ok {
246 for i, n := 0, named.NumMethods(); i < n; i++ {
247 memberFromObject(p, named.Method(i), nil, "")
248 }
249 }
250 }
251 }
252 }
253 254 if prog.mode&BareInits == 0 {
255 // Add initializer guard variable.
256 initguard := &Global{
257 Pkg: p,
258 name: "init$guard",
259 typ: types.NewPointer(tBool),
260 }
261 p.Members[initguard.Name()] = initguard
262 }
263 264 if prog.mode&GlobalDebug != 0 {
265 p.SetDebugMode(true)
266 }
267 268 if prog.mode&PrintPackages != 0 {
269 printMu.Lock()
270 p.WriteTo(os.Stdout)
271 printMu.Unlock()
272 }
273 274 if importable {
275 prog.imported[p.Pkg.Path()] = p
276 }
277 prog.packages[p.Pkg] = p
278 279 return p
280 }
281 282 // printMu serializes printing of Packages/Functions to stdout.
283 var printMu sync.Mutex
284 285 // AllPackages returns a new slice containing all packages created by
286 // prog.CreatePackage in unspecified order.
287 func (prog *Program) AllPackages() []*Package {
288 pkgs := make([]*Package, 0, len(prog.packages))
289 for _, pkg := range prog.packages {
290 pkgs = append(pkgs, pkg)
291 }
292 return pkgs
293 }
294 295 // ImportedPackage returns the importable Package whose PkgPath
296 // is path, or nil if no such Package has been created.
297 //
298 // A parameter to CreatePackage determines whether a package should be
299 // considered importable. For example, no import declaration can resolve
300 // to the ad-hoc main package created by 'go build foo.go'.
301 //
302 // TODO(adonovan): rethink this function and the "importable" concept;
303 // most packages are importable. This function assumes that all
304 // types.Package.Path values are unique within the ssa.Program, which is
305 // false---yet this function remains very convenient.
306 // Clients should use (*Program).Package instead where possible.
307 // SSA doesn't really need a string-keyed map of packages.
308 //
309 // Furthermore, the graph of packages may contain multiple variants
310 // (e.g. "p" vs "p as compiled for q.test"), and each has a different
311 // view of its dependencies.
312 func (prog *Program) ImportedPackage(path string) *Package {
313 return prog.imported[path]
314 }
315 316 // SetNoReturn sets the predicate used when building the ssa.Program
317 // prog that reports whether a given function cannot return.
318 // This may be used to prune spurious control flow edges
319 // after (e.g.) log.Fatal, improving the precision of analyses.
320 //
321 // A typical implementation is the [ctrlflow.CFGs.NoReturn] method from
322 // [golang.org/x/tools/go/analysis/passes/ctrlflow].
323 func (prog *Program) SetNoReturn(noReturn func(*types.Func) bool) {
324 prog.noReturn = noReturn
325 }
326