diff options
Diffstat (limited to 'vendor/golang.org/x/tools/go/ssa/ssautil')
| -rw-r--r-- | vendor/golang.org/x/tools/go/ssa/ssautil/load.go | 214 | ||||
| -rw-r--r-- | vendor/golang.org/x/tools/go/ssa/ssautil/switch.go | 230 | ||||
| -rw-r--r-- | vendor/golang.org/x/tools/go/ssa/ssautil/visit.go | 157 |
3 files changed, 0 insertions, 601 deletions
diff --git a/vendor/golang.org/x/tools/go/ssa/ssautil/load.go b/vendor/golang.org/x/tools/go/ssa/ssautil/load.go deleted file mode 100644 index 3daa67a..0000000 --- a/vendor/golang.org/x/tools/go/ssa/ssautil/load.go +++ /dev/null @@ -1,214 +0,0 @@ -// Copyright 2015 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package ssautil - -// This file defines utility functions for constructing programs in SSA form. - -import ( - "go/ast" - "go/token" - "go/types" - - "golang.org/x/tools/go/loader" - "golang.org/x/tools/go/packages" - "golang.org/x/tools/go/ssa" - "golang.org/x/tools/internal/versions" -) - -// Packages creates an SSA program for a set of packages. -// -// The packages must have been loaded from source syntax using the -// [packages.Load] function in [packages.LoadSyntax] or -// [packages.LoadAllSyntax] mode. -// -// Packages creates an SSA package for each well-typed package in the -// initial list, plus all their dependencies. The resulting list of -// packages corresponds to the list of initial packages, and may contain -// a nil if SSA code could not be constructed for the corresponding initial -// package due to type errors. -// -// Code for bodies of functions is not built until [Program.Build] is -// called on the resulting Program. SSA code is constructed only for -// the initial packages with well-typed syntax trees. -// -// The mode parameter controls diagnostics and checking during SSA construction. -func Packages(initial []*packages.Package, mode ssa.BuilderMode) (*ssa.Program, []*ssa.Package) { - // TODO(adonovan): opt: this calls CreatePackage far more than - // necessary: for all dependencies, not just the (non-initial) - // direct dependencies of the initial packages. - // - // But can it reasonably be changed without breaking the - // spirit and/or letter of the law above? Clients may notice - // if we call CreatePackage less, as methods like - // Program.FuncValue will return nil. Or must we provide a new - // function (and perhaps deprecate this one)? Is it worth it? - // - // Tim King makes the interesting point that it would be - // possible to entirely alleviate the client from the burden - // of calling CreatePackage for non-syntax packages, if we - // were to treat vars and funcs lazily in the same way we now - // treat methods. (In essence, try to move away from the - // notion of ssa.Packages, and make the Program answer - // all reasonable questions about any types.Object.) - - return doPackages(initial, mode, false) -} - -// AllPackages creates an SSA program for a set of packages plus all -// their dependencies. -// -// The packages must have been loaded from source syntax using the -// [packages.Load] function in [packages.LoadAllSyntax] mode. -// -// AllPackages creates an SSA package for each well-typed package in the -// initial list, plus all their dependencies. The resulting list of -// packages corresponds to the list of initial packages, and may contain -// a nil if SSA code could not be constructed for the corresponding -// initial package due to type errors. -// -// Code for bodies of functions is not built until Build is called on -// the resulting Program. SSA code is constructed for all packages with -// well-typed syntax trees. -// -// The mode parameter controls diagnostics and checking during SSA construction. -func AllPackages(initial []*packages.Package, mode ssa.BuilderMode) (*ssa.Program, []*ssa.Package) { - return doPackages(initial, mode, true) -} - -func doPackages(initial []*packages.Package, mode ssa.BuilderMode, deps bool) (*ssa.Program, []*ssa.Package) { - - var fset *token.FileSet - if len(initial) > 0 { - fset = initial[0].Fset - } - - prog := ssa.NewProgram(fset, mode) - - isInitial := make(map[*packages.Package]bool, len(initial)) - for _, p := range initial { - isInitial[p] = true - } - - ssamap := make(map[*packages.Package]*ssa.Package) - packages.Visit(initial, nil, func(p *packages.Package) { - if p.Types != nil && !p.IllTyped { - var files []*ast.File - var info *types.Info - if deps || isInitial[p] { - files = p.Syntax - info = p.TypesInfo - } - ssamap[p] = prog.CreatePackage(p.Types, files, info, true) - } - }) - - var ssapkgs []*ssa.Package - for _, p := range initial { - ssapkgs = append(ssapkgs, ssamap[p]) // may be nil - } - return prog, ssapkgs -} - -// CreateProgram returns a new program in SSA form, given a program -// loaded from source. An SSA package is created for each transitively -// error-free package of lprog. -// -// Code for bodies of functions is not built until Build is called -// on the result. -// -// The mode parameter controls diagnostics and checking during SSA construction. -// -// Deprecated: Use [golang.org/x/tools/go/packages] and the [Packages] -// function instead; see ssa.Example_loadPackages. -func CreateProgram(lprog *loader.Program, mode ssa.BuilderMode) *ssa.Program { - prog := ssa.NewProgram(lprog.Fset, mode) - - for _, info := range lprog.AllPackages { - if info.TransitivelyErrorFree { - prog.CreatePackage(info.Pkg, info.Files, &info.Info, info.Importable) - } - } - - return prog -} - -// BuildPackage builds an SSA program with SSA intermediate -// representation (IR) for all functions of a single package. -// -// It populates pkg by type-checking the specified file syntax trees. All -// dependencies are loaded using the importer specified by tc, which -// typically loads compiler export data; SSA code cannot be built for -// those packages. BuildPackage then constructs an [ssa.Program] with all -// dependency packages created, and builds and returns the SSA package -// corresponding to pkg. -// -// The caller must have set pkg.Path to the import path. -// -// The operation fails if there were any type-checking or import errors. -// -// See ../example_test.go for an example. -func BuildPackage(tc *types.Config, fset *token.FileSet, pkg *types.Package, files []*ast.File, mode ssa.BuilderMode) (*ssa.Package, *types.Info, error) { - if fset == nil { - panic("no token.FileSet") - } - if pkg.Path() == "" { - panic("package has no import path") - } - - info := &types.Info{ - Types: make(map[ast.Expr]types.TypeAndValue), - Defs: make(map[*ast.Ident]types.Object), - Uses: make(map[*ast.Ident]types.Object), - Implicits: make(map[ast.Node]types.Object), - Instances: make(map[*ast.Ident]types.Instance), - Scopes: make(map[ast.Node]*types.Scope), - Selections: make(map[*ast.SelectorExpr]*types.Selection), - } - versions.InitFileVersions(info) - if err := types.NewChecker(tc, fset, pkg, info).Files(files); err != nil { - return nil, nil, err - } - - prog := ssa.NewProgram(fset, mode) - - // Create SSA packages for all imports. - // Order is not significant. - created := make(map[*types.Package]bool) - var createAll func(pkgs []*types.Package) - createAll = func(pkgs []*types.Package) { - for _, p := range pkgs { - if !created[p] { - created[p] = true - prog.CreatePackage(p, nil, nil, true) - createAll(p.Imports()) - } - } - } - createAll(pkg.Imports()) - - // TODO(adonovan): we could replace createAll with just: - // - // // Create SSA packages for all imports. - // for _, p := range pkg.Imports() { - // prog.CreatePackage(p, nil, nil, true) - // } - // - // (with minor changes to changes to ../builder_test.go as - // shown in CL 511715 PS 10.) But this would strictly violate - // the letter of the doc comment above, which says "all - // dependencies created". - // - // Tim makes the good point with some extra work we could - // remove the need for any CreatePackage calls except the - // ones with syntax (i.e. primary packages). Of course - // You wouldn't have ssa.Packages and Members for as - // many things but no-one really uses that anyway. - // I wish I had done this from the outset. - - // Create and build the primary package. - ssapkg := prog.CreatePackage(pkg, files, info, false) - ssapkg.Build() - return ssapkg, info, nil -} diff --git a/vendor/golang.org/x/tools/go/ssa/ssautil/switch.go b/vendor/golang.org/x/tools/go/ssa/ssautil/switch.go deleted file mode 100644 index dd4b04e..0000000 --- a/vendor/golang.org/x/tools/go/ssa/ssautil/switch.go +++ /dev/null @@ -1,230 +0,0 @@ -// Copyright 2013 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package ssautil - -// This file implements discovery of switch and type-switch constructs -// from low-level control flow. -// -// Many techniques exist for compiling a high-level switch with -// constant cases to efficient machine code. The optimal choice will -// depend on the data type, the specific case values, the code in the -// body of each case, and the hardware. -// Some examples: -// - a lookup table (for a switch that maps constants to constants) -// - a computed goto -// - a binary tree -// - a perfect hash -// - a two-level switch (to partition constant strings by their first byte). - -import ( - "bytes" - "fmt" - "go/token" - "go/types" - - "golang.org/x/tools/go/ssa" -) - -// A ConstCase represents a single constant comparison. -// It is part of a Switch. -type ConstCase struct { - Block *ssa.BasicBlock // block performing the comparison - Body *ssa.BasicBlock // body of the case - Value *ssa.Const // case comparand -} - -// A TypeCase represents a single type assertion. -// It is part of a Switch. -type TypeCase struct { - Block *ssa.BasicBlock // block performing the type assert - Body *ssa.BasicBlock // body of the case - Type types.Type // case type - Binding ssa.Value // value bound by this case -} - -// A Switch is a logical high-level control flow operation -// (a multiway branch) discovered by analysis of a CFG containing -// only if/else chains. It is not part of the ssa.Instruction set. -// -// One of ConstCases and TypeCases has length >= 2; -// the other is nil. -// -// In a value switch, the list of cases may contain duplicate constants. -// A type switch may contain duplicate types, or types assignable -// to an interface type also in the list. -// TODO(adonovan): eliminate such duplicates. -type Switch struct { - Start *ssa.BasicBlock // block containing start of if/else chain - X ssa.Value // the switch operand - ConstCases []ConstCase // ordered list of constant comparisons - TypeCases []TypeCase // ordered list of type assertions - Default *ssa.BasicBlock // successor if all comparisons fail -} - -func (sw *Switch) String() string { - // We represent each block by the String() of its - // first Instruction, e.g. "print(42:int)". - var buf bytes.Buffer - if sw.ConstCases != nil { - fmt.Fprintf(&buf, "switch %s {\n", sw.X.Name()) - for _, c := range sw.ConstCases { - fmt.Fprintf(&buf, "case %s: %s\n", c.Value, c.Body.Instrs[0]) - } - } else { - fmt.Fprintf(&buf, "switch %s.(type) {\n", sw.X.Name()) - for _, c := range sw.TypeCases { - fmt.Fprintf(&buf, "case %s %s: %s\n", - c.Binding.Name(), c.Type, c.Body.Instrs[0]) - } - } - if sw.Default != nil { - fmt.Fprintf(&buf, "default: %s\n", sw.Default.Instrs[0]) - } - fmt.Fprintf(&buf, "}") - return buf.String() -} - -// Switches examines the control-flow graph of fn and returns the -// set of inferred value and type switches. A value switch tests an -// ssa.Value for equality against two or more compile-time constant -// values. Switches involving link-time constants (addresses) are -// ignored. A type switch type-asserts an ssa.Value against two or -// more types. -// -// The switches are returned in dominance order. -// -// The resulting switches do not necessarily correspond to uses of the -// 'switch' keyword in the source: for example, a single source-level -// switch statement with non-constant cases may result in zero, one or -// many Switches, one per plural sequence of constant cases. -// Switches may even be inferred from if/else- or goto-based control flow. -// (In general, the control flow constructs of the source program -// cannot be faithfully reproduced from the SSA representation.) -func Switches(fn *ssa.Function) []Switch { - // Traverse the CFG in dominance order, so we don't - // enter an if/else-chain in the middle. - var switches []Switch - seen := make(map[*ssa.BasicBlock]bool) // TODO(adonovan): opt: use ssa.blockSet - for _, b := range fn.DomPreorder() { - if x, k := isComparisonBlock(b); x != nil { - // Block b starts a switch. - sw := Switch{Start: b, X: x} - valueSwitch(&sw, k, seen) - if len(sw.ConstCases) > 1 { - switches = append(switches, sw) - } - } - - if y, x, T := isTypeAssertBlock(b); y != nil { - // Block b starts a type switch. - sw := Switch{Start: b, X: x} - typeSwitch(&sw, y, T, seen) - if len(sw.TypeCases) > 1 { - switches = append(switches, sw) - } - } - } - return switches -} - -func valueSwitch(sw *Switch, k *ssa.Const, seen map[*ssa.BasicBlock]bool) { - b := sw.Start - x := sw.X - for x == sw.X { - if seen[b] { - break - } - seen[b] = true - - sw.ConstCases = append(sw.ConstCases, ConstCase{ - Block: b, - Body: b.Succs[0], - Value: k, - }) - b = b.Succs[1] - if len(b.Instrs) > 2 { - // Block b contains not just 'if x == k', - // so it may have side effects that - // make it unsafe to elide. - break - } - if len(b.Preds) != 1 { - // Block b has multiple predecessors, - // so it cannot be treated as a case. - break - } - x, k = isComparisonBlock(b) - } - sw.Default = b -} - -func typeSwitch(sw *Switch, y ssa.Value, T types.Type, seen map[*ssa.BasicBlock]bool) { - b := sw.Start - x := sw.X - for x == sw.X { - if seen[b] { - break - } - seen[b] = true - - sw.TypeCases = append(sw.TypeCases, TypeCase{ - Block: b, - Body: b.Succs[0], - Type: T, - Binding: y, - }) - b = b.Succs[1] - if len(b.Instrs) > 4 { - // Block b contains not just - // {TypeAssert; Extract #0; Extract #1; If} - // so it may have side effects that - // make it unsafe to elide. - break - } - if len(b.Preds) != 1 { - // Block b has multiple predecessors, - // so it cannot be treated as a case. - break - } - y, x, T = isTypeAssertBlock(b) - } - sw.Default = b -} - -// isComparisonBlock returns the operands (v, k) if a block ends with -// a comparison v==k, where k is a compile-time constant. -func isComparisonBlock(b *ssa.BasicBlock) (v ssa.Value, k *ssa.Const) { - if n := len(b.Instrs); n >= 2 { - if i, ok := b.Instrs[n-1].(*ssa.If); ok { - if binop, ok := i.Cond.(*ssa.BinOp); ok && binop.Block() == b && binop.Op == token.EQL { - if k, ok := binop.Y.(*ssa.Const); ok { - return binop.X, k - } - if k, ok := binop.X.(*ssa.Const); ok { - return binop.Y, k - } - } - } - } - return -} - -// isTypeAssertBlock returns the operands (y, x, T) if a block ends with -// a type assertion "if y, ok := x.(T); ok {". -func isTypeAssertBlock(b *ssa.BasicBlock) (y, x ssa.Value, T types.Type) { - if n := len(b.Instrs); n >= 4 { - if i, ok := b.Instrs[n-1].(*ssa.If); ok { - if ext1, ok := i.Cond.(*ssa.Extract); ok && ext1.Block() == b && ext1.Index == 1 { - if ta, ok := ext1.Tuple.(*ssa.TypeAssert); ok && ta.Block() == b { - // hack: relies upon instruction ordering. - if ext0, ok := b.Instrs[n-3].(*ssa.Extract); ok { - return ext0, ta.X, ta.AssertedType - } - } - } - } - } - return -} diff --git a/vendor/golang.org/x/tools/go/ssa/ssautil/visit.go b/vendor/golang.org/x/tools/go/ssa/ssautil/visit.go deleted file mode 100644 index b4feb42..0000000 --- a/vendor/golang.org/x/tools/go/ssa/ssautil/visit.go +++ /dev/null @@ -1,157 +0,0 @@ -// Copyright 2013 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package ssautil // import "golang.org/x/tools/go/ssa/ssautil" - -import ( - "go/ast" - "go/types" - - "golang.org/x/tools/go/ssa" - - _ "unsafe" // for linkname hack -) - -// This file defines utilities for visiting the SSA representation of -// a Program. -// -// TODO(adonovan): test coverage. - -// AllFunctions finds and returns the set of functions potentially -// needed by program prog, as determined by a simple linker-style -// reachability algorithm starting from the members and method-sets of -// each package. The result may include anonymous functions and -// synthetic wrappers. -// -// Precondition: all packages are built. -// -// TODO(adonovan): this function is underspecified. It doesn't -// actually work like a linker, which computes reachability from main -// using something like go/callgraph/cha (without materializing the -// call graph). In fact, it treats all public functions and all -// methods of public non-parameterized types as roots, even though -// they may be unreachable--but only in packages created from syntax. -// -// I think we should deprecate AllFunctions function in favor of two -// clearly defined ones: -// -// 1. The first would efficiently compute CHA reachability from a set -// of main packages, making it suitable for a whole-program -// analysis context with InstantiateGenerics, in conjunction with -// Program.Build. -// -// 2. The second would return only the set of functions corresponding -// to source Func{Decl,Lit} syntax, like SrcFunctions in -// go/analysis/passes/buildssa; this is suitable for -// package-at-a-time (or handful of packages) context. -// ssa.Package could easily expose it as a field. -// -// We could add them unexported for now and use them via the linkname hack. -func AllFunctions(prog *ssa.Program) map[*ssa.Function]bool { - seen := make(map[*ssa.Function]bool) - - var function func(fn *ssa.Function) - function = func(fn *ssa.Function) { - if !seen[fn] { - seen[fn] = true - var buf [10]*ssa.Value // avoid alloc in common case - for _, b := range fn.Blocks { - for _, instr := range b.Instrs { - for _, op := range instr.Operands(buf[:0]) { - if fn, ok := (*op).(*ssa.Function); ok { - function(fn) - } - } - } - } - } - } - - // TODO(adonovan): opt: provide a way to share a builder - // across a sequence of MethodValue calls. - - methodsOf := func(T types.Type) { - if !types.IsInterface(T) { - mset := prog.MethodSets.MethodSet(T) - for i := 0; i < mset.Len(); i++ { - function(prog.MethodValue(mset.At(i))) - } - } - } - - // Historically, Program.RuntimeTypes used to include the type - // of any exported member of a package loaded from syntax that - // has a non-parameterized type, plus all types - // reachable from that type using reflection, even though - // these runtime types may not be required for them. - // - // Rather than break existing programs that rely on - // AllFunctions visiting extra methods that are unreferenced - // by IR and unreachable via reflection, we moved the logic - // here, unprincipled though it is. - // (See doc comment for better ideas.) - // - // Nonetheless, after the move, we no longer visit every - // method of any type recursively reachable from T, only the - // methods of T and *T themselves, and we only apply this to - // named types T, and not to the type of every exported - // package member. - exportedTypeHack := func(t *ssa.Type) { - if isSyntactic(t.Package()) && - ast.IsExported(t.Name()) && - !types.IsInterface(t.Type()) { - // Consider only named types. - // (Ignore aliases and unsafe.Pointer.) - if named, ok := t.Type().(*types.Named); ok { - if named.TypeParams() == nil { - methodsOf(named) // T - methodsOf(types.NewPointer(named)) // *T - } - } - } - } - - for _, pkg := range prog.AllPackages() { - for _, mem := range pkg.Members { - switch mem := mem.(type) { - case *ssa.Function: - // Visit all package-level declared functions. - function(mem) - - case *ssa.Type: - exportedTypeHack(mem) - } - } - } - - // Visit all methods of types for which runtime types were - // materialized, as they are reachable through reflection. - for _, T := range prog.RuntimeTypes() { - methodsOf(T) - } - - return seen -} - -// MainPackages returns the subset of the specified packages -// named "main" that define a main function. -// The result may include synthetic "testmain" packages. -func MainPackages(pkgs []*ssa.Package) []*ssa.Package { - var mains []*ssa.Package - for _, pkg := range pkgs { - if pkg.Pkg.Name() == "main" && pkg.Func("main") != nil { - mains = append(mains, pkg) - } - } - return mains -} - -// TODO(adonovan): propose a principled API for this. One possibility -// is a new field, Package.SrcFunctions []*Function, which would -// contain the list of SrcFunctions described in point 2 of the -// AllFunctions doc comment, or nil if the package is not from syntax. -// But perhaps overloading nil vs empty slice is too subtle. -// -//go:linkname isSyntactic golang.org/x/tools/go/ssa.isSyntactic -func isSyntactic(pkg *ssa.Package) bool |