| // 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 pointer |
| |
| import ( |
| "bytes" |
| "fmt" |
| "go/token" |
| "io" |
| |
| "golang.org/x/tools/container/intsets" |
| "golang.org/x/tools/go/callgraph" |
| "golang.org/x/tools/go/ssa" |
| "golang.org/x/tools/go/types/typeutil" |
| ) |
| |
| // A Config formulates a pointer analysis problem for Analyze. It is |
| // only usable for a single invocation of Analyze and must not be |
| // reused. |
| type Config struct { |
| // Mains contains the set of 'main' packages to analyze |
| // Clients must provide the analysis with at least one |
| // package defining a main() function. |
| // |
| // Non-main packages in the ssa.Program that are not |
| // dependencies of any main package may still affect the |
| // analysis result, because they contribute runtime types and |
| // thus methods. |
| // |
| // TODO(adonovan): investigate whether this is desirable. |
| // |
| // Calls to generic functions will be unsound unless packages |
| // are built using the ssa.InstantiateGenerics builder mode. |
| Mains []*ssa.Package |
| |
| // Reflection determines whether to handle reflection |
| // operators soundly, which is currently rather slow since it |
| // causes constraint to be generated during solving |
| // proportional to the number of constraint variables, which |
| // has not yet been reduced by presolver optimisation. |
| Reflection bool |
| |
| // BuildCallGraph determines whether to construct a callgraph. |
| // If enabled, the graph will be available in Result.CallGraph. |
| BuildCallGraph bool |
| |
| // The client populates Queries[v] or IndirectQueries[v] |
| // for each ssa.Value v of interest, to request that the |
| // points-to sets pts(v) or pts(*v) be computed. If the |
| // client needs both points-to sets, v may appear in both |
| // maps. |
| // |
| // (IndirectQueries is typically used for Values corresponding |
| // to source-level lvalues, e.g. an *ssa.Global.) |
| // |
| // The analysis populates the corresponding |
| // Result.{Indirect,}Queries map when it creates the pointer |
| // variable for v or *v. Upon completion the client can |
| // inspect that map for the results. |
| // |
| // TODO(adonovan): this API doesn't scale well for batch tools |
| // that want to dump the entire solution. Perhaps optionally |
| // populate a map[*ssa.DebugRef]Pointer in the Result, one |
| // entry per source expression. |
| // |
| Queries map[ssa.Value]struct{} |
| IndirectQueries map[ssa.Value]struct{} |
| extendedQueries map[ssa.Value][]*extendedQuery |
| |
| // If Log is non-nil, log messages are written to it. |
| // Logging is extremely verbose. |
| Log io.Writer |
| } |
| |
| type track uint32 |
| |
| const ( |
| trackChan track = 1 << iota // track 'chan' references |
| trackMap // track 'map' references |
| trackPtr // track regular pointers |
| trackSlice // track slice references |
| |
| trackAll = ^track(0) |
| ) |
| |
| // AddQuery adds v to Config.Queries. |
| // Precondition: CanPoint(v.Type()). |
| func (c *Config) AddQuery(v ssa.Value) { |
| if !CanPoint(v.Type()) { |
| panic(fmt.Sprintf("%s is not a pointer-like value: %s", v, v.Type())) |
| } |
| if c.Queries == nil { |
| c.Queries = make(map[ssa.Value]struct{}) |
| } |
| c.Queries[v] = struct{}{} |
| } |
| |
| // AddQuery adds v to Config.IndirectQueries. |
| // Precondition: CanPoint(v.Type().Underlying().(*types.Pointer).Elem()). |
| func (c *Config) AddIndirectQuery(v ssa.Value) { |
| if c.IndirectQueries == nil { |
| c.IndirectQueries = make(map[ssa.Value]struct{}) |
| } |
| if !CanPoint(mustDeref(v.Type())) { |
| panic(fmt.Sprintf("%s is not the address of a pointer-like value: %s", v, v.Type())) |
| } |
| c.IndirectQueries[v] = struct{}{} |
| } |
| |
| // AddExtendedQuery adds an extended, AST-based query on v to the |
| // analysis. The query, which must be a single Go expression, allows |
| // destructuring the value. |
| // |
| // The query must operate on a variable named 'x', which represents |
| // the value, and result in a pointer-like object. Only a subset of |
| // Go expressions are permitted in queries, namely channel receives, |
| // pointer dereferences, field selectors, array/slice/map/tuple |
| // indexing and grouping with parentheses. The specific indices when |
| // indexing arrays, slices and maps have no significance. Indices used |
| // on tuples must be numeric and within bounds. |
| // |
| // All field selectors must be explicit, even ones usually elided |
| // due to promotion of embedded fields. |
| // |
| // The query 'x' is identical to using AddQuery. The query '*x' is |
| // identical to using AddIndirectQuery. |
| // |
| // On success, AddExtendedQuery returns a Pointer to the queried |
| // value. This Pointer will be initialized during analysis. Using it |
| // before analysis has finished has undefined behavior. |
| // |
| // Example: |
| // |
| // // given v, which represents a function call to 'fn() (int, []*T)', and |
| // // 'type T struct { F *int }', the following query will access the field F. |
| // c.AddExtendedQuery(v, "x[1][0].F") |
| func (c *Config) AddExtendedQuery(v ssa.Value, query string) (*Pointer, error) { |
| ops, _, err := parseExtendedQuery(v.Type(), query) |
| if err != nil { |
| return nil, fmt.Errorf("invalid query %q: %s", query, err) |
| } |
| if c.extendedQueries == nil { |
| c.extendedQueries = make(map[ssa.Value][]*extendedQuery) |
| } |
| |
| ptr := &Pointer{} |
| c.extendedQueries[v] = append(c.extendedQueries[v], &extendedQuery{ops: ops, ptr: ptr}) |
| return ptr, nil |
| } |
| |
| func (c *Config) prog() *ssa.Program { |
| for _, main := range c.Mains { |
| return main.Prog |
| } |
| panic("empty scope") |
| } |
| |
| type Warning struct { |
| Pos token.Pos |
| Message string |
| } |
| |
| // A Result contains the results of a pointer analysis. |
| // |
| // See Config for how to request the various Result components. |
| type Result struct { |
| CallGraph *callgraph.Graph // discovered call graph |
| Queries map[ssa.Value]Pointer // pts(v) for each v in Config.Queries. |
| IndirectQueries map[ssa.Value]Pointer // pts(*v) for each v in Config.IndirectQueries. |
| Warnings []Warning // warnings of unsoundness |
| } |
| |
| // A Pointer is an equivalence class of pointer-like values. |
| // |
| // A Pointer doesn't have a unique type because pointers of distinct |
| // types may alias the same object. |
| type Pointer struct { |
| a *analysis |
| n nodeid |
| } |
| |
| // A PointsToSet is a set of labels (locations or allocations). |
| type PointsToSet struct { |
| a *analysis // may be nil if pts is nil |
| pts *nodeset |
| } |
| |
| func (s PointsToSet) String() string { |
| var buf bytes.Buffer |
| buf.WriteByte('[') |
| if s.pts != nil { |
| var space [50]int |
| for i, l := range s.pts.AppendTo(space[:0]) { |
| if i > 0 { |
| buf.WriteString(", ") |
| } |
| buf.WriteString(s.a.labelFor(nodeid(l)).String()) |
| } |
| } |
| buf.WriteByte(']') |
| return buf.String() |
| } |
| |
| // PointsTo returns the set of labels that this points-to set |
| // contains. |
| func (s PointsToSet) Labels() []*Label { |
| var labels []*Label |
| if s.pts != nil { |
| var space [50]int |
| for _, l := range s.pts.AppendTo(space[:0]) { |
| labels = append(labels, s.a.labelFor(nodeid(l))) |
| } |
| } |
| return labels |
| } |
| |
| // If this PointsToSet came from a Pointer of interface kind |
| // or a reflect.Value, DynamicTypes returns the set of dynamic |
| // types that it may contain. (For an interface, they will |
| // always be concrete types.) |
| // |
| // The result is a mapping whose keys are the dynamic types to which |
| // it may point. For each pointer-like key type, the corresponding |
| // map value is the PointsToSet for pointers of that type. |
| // |
| // The result is empty unless CanHaveDynamicTypes(T). |
| func (s PointsToSet) DynamicTypes() *typeutil.Map { |
| var tmap typeutil.Map |
| tmap.SetHasher(s.a.hasher) |
| if s.pts != nil { |
| var space [50]int |
| for _, x := range s.pts.AppendTo(space[:0]) { |
| ifaceObjID := nodeid(x) |
| if !s.a.isTaggedObject(ifaceObjID) { |
| continue // !CanHaveDynamicTypes(tDyn) |
| } |
| tDyn, v, indirect := s.a.taggedValue(ifaceObjID) |
| if indirect { |
| panic("indirect tagged object") // implement later |
| } |
| pts, ok := tmap.At(tDyn).(PointsToSet) |
| if !ok { |
| pts = PointsToSet{s.a, new(nodeset)} |
| tmap.Set(tDyn, pts) |
| } |
| pts.pts.addAll(&s.a.nodes[v].solve.pts) |
| } |
| } |
| return &tmap |
| } |
| |
| // Intersects reports whether this points-to set and the |
| // argument points-to set contain common members. |
| func (s PointsToSet) Intersects(y PointsToSet) bool { |
| if s.pts == nil || y.pts == nil { |
| return false |
| } |
| // This takes Θ(|x|+|y|) time. |
| var z intsets.Sparse |
| z.Intersection(&s.pts.Sparse, &y.pts.Sparse) |
| return !z.IsEmpty() |
| } |
| |
| func (p Pointer) String() string { |
| return fmt.Sprintf("n%d", p.n) |
| } |
| |
| // PointsTo returns the points-to set of this pointer. |
| func (p Pointer) PointsTo() PointsToSet { |
| if p.n == 0 { |
| return PointsToSet{} |
| } |
| return PointsToSet{p.a, &p.a.nodes[p.n].solve.pts} |
| } |
| |
| // MayAlias reports whether the receiver pointer may alias |
| // the argument pointer. |
| func (p Pointer) MayAlias(q Pointer) bool { |
| return p.PointsTo().Intersects(q.PointsTo()) |
| } |
| |
| // DynamicTypes returns p.PointsTo().DynamicTypes(). |
| func (p Pointer) DynamicTypes() *typeutil.Map { |
| return p.PointsTo().DynamicTypes() |
| } |