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.
13 "golang.org/x/tools/container/intsets"
14 "golang.org/x/tools/go/callgraph"
15 "golang.org/x/tools/go/ssa"
16 "golang.org/x/tools/go/types/typeutil"
19 // A Config formulates a pointer analysis problem for Analyze. It is
20 // only usable for a single invocation of Analyze and must not be
23 // Mains contains the set of 'main' packages to analyze
24 // Clients must provide the analysis with at least one
25 // package defining a main() function.
27 // Non-main packages in the ssa.Program that are not
28 // dependencies of any main package may still affect the
29 // analysis result, because they contribute runtime types and
31 // TODO(adonovan): investigate whether this is desirable.
34 // Reflection determines whether to handle reflection
35 // operators soundly, which is currently rather slow since it
36 // causes constraint to be generated during solving
37 // proportional to the number of constraint variables, which
38 // has not yet been reduced by presolver optimisation.
41 // BuildCallGraph determines whether to construct a callgraph.
42 // If enabled, the graph will be available in Result.CallGraph.
45 // The client populates Queries[v] or IndirectQueries[v]
46 // for each ssa.Value v of interest, to request that the
47 // points-to sets pts(v) or pts(*v) be computed. If the
48 // client needs both points-to sets, v may appear in both
51 // (IndirectQueries is typically used for Values corresponding
52 // to source-level lvalues, e.g. an *ssa.Global.)
54 // The analysis populates the corresponding
55 // Result.{Indirect,}Queries map when it creates the pointer
56 // variable for v or *v. Upon completion the client can
57 // inspect that map for the results.
59 // TODO(adonovan): this API doesn't scale well for batch tools
60 // that want to dump the entire solution. Perhaps optionally
61 // populate a map[*ssa.DebugRef]Pointer in the Result, one
62 // entry per source expression.
64 Queries map[ssa.Value]struct{}
65 IndirectQueries map[ssa.Value]struct{}
66 extendedQueries map[ssa.Value][]*extendedQuery
68 // If Log is non-nil, log messages are written to it.
69 // Logging is extremely verbose.
76 trackChan track = 1 << iota // track 'chan' references
77 trackMap // track 'map' references
78 trackPtr // track regular pointers
79 trackSlice // track slice references
84 // AddQuery adds v to Config.Queries.
85 // Precondition: CanPoint(v.Type()).
86 func (c *Config) AddQuery(v ssa.Value) {
87 if !CanPoint(v.Type()) {
88 panic(fmt.Sprintf("%s is not a pointer-like value: %s", v, v.Type()))
91 c.Queries = make(map[ssa.Value]struct{})
93 c.Queries[v] = struct{}{}
96 // AddQuery adds v to Config.IndirectQueries.
97 // Precondition: CanPoint(v.Type().Underlying().(*types.Pointer).Elem()).
98 func (c *Config) AddIndirectQuery(v ssa.Value) {
99 if c.IndirectQueries == nil {
100 c.IndirectQueries = make(map[ssa.Value]struct{})
102 if !CanPoint(mustDeref(v.Type())) {
103 panic(fmt.Sprintf("%s is not the address of a pointer-like value: %s", v, v.Type()))
105 c.IndirectQueries[v] = struct{}{}
108 // AddExtendedQuery adds an extended, AST-based query on v to the
109 // analysis. The query, which must be a single Go expression, allows
110 // destructuring the value.
112 // The query must operate on a variable named 'x', which represents
113 // the value, and result in a pointer-like object. Only a subset of
114 // Go expressions are permitted in queries, namely channel receives,
115 // pointer dereferences, field selectors, array/slice/map/tuple
116 // indexing and grouping with parentheses. The specific indices when
117 // indexing arrays, slices and maps have no significance. Indices used
118 // on tuples must be numeric and within bounds.
120 // All field selectors must be explicit, even ones usually elided
121 // due to promotion of embedded fields.
123 // The query 'x' is identical to using AddQuery. The query '*x' is
124 // identical to using AddIndirectQuery.
126 // On success, AddExtendedQuery returns a Pointer to the queried
127 // value. This Pointer will be initialized during analysis. Using it
128 // before analysis has finished has undefined behavior.
131 // // given v, which represents a function call to 'fn() (int, []*T)', and
132 // // 'type T struct { F *int }', the following query will access the field F.
133 // c.AddExtendedQuery(v, "x[1][0].F")
134 func (c *Config) AddExtendedQuery(v ssa.Value, query string) (*Pointer, error) {
135 ops, _, err := parseExtendedQuery(v.Type(), query)
137 return nil, fmt.Errorf("invalid query %q: %s", query, err)
139 if c.extendedQueries == nil {
140 c.extendedQueries = make(map[ssa.Value][]*extendedQuery)
144 c.extendedQueries[v] = append(c.extendedQueries[v], &extendedQuery{ops: ops, ptr: ptr})
148 func (c *Config) prog() *ssa.Program {
149 for _, main := range c.Mains {
155 type Warning struct {
160 // A Result contains the results of a pointer analysis.
162 // See Config for how to request the various Result components.
165 CallGraph *callgraph.Graph // discovered call graph
166 Queries map[ssa.Value]Pointer // pts(v) for each v in Config.Queries.
167 IndirectQueries map[ssa.Value]Pointer // pts(*v) for each v in Config.IndirectQueries.
168 Warnings []Warning // warnings of unsoundness
171 // A Pointer is an equivalence class of pointer-like values.
173 // A Pointer doesn't have a unique type because pointers of distinct
174 // types may alias the same object.
176 type Pointer struct {
181 // A PointsToSet is a set of labels (locations or allocations).
182 type PointsToSet struct {
183 a *analysis // may be nil if pts is nil
187 func (s PointsToSet) String() string {
192 for i, l := range s.pts.AppendTo(space[:0]) {
194 buf.WriteString(", ")
196 buf.WriteString(s.a.labelFor(nodeid(l)).String())
203 // PointsTo returns the set of labels that this points-to set
205 func (s PointsToSet) Labels() []*Label {
209 for _, l := range s.pts.AppendTo(space[:0]) {
210 labels = append(labels, s.a.labelFor(nodeid(l)))
216 // If this PointsToSet came from a Pointer of interface kind
217 // or a reflect.Value, DynamicTypes returns the set of dynamic
218 // types that it may contain. (For an interface, they will
219 // always be concrete types.)
221 // The result is a mapping whose keys are the dynamic types to which
222 // it may point. For each pointer-like key type, the corresponding
223 // map value is the PointsToSet for pointers of that type.
225 // The result is empty unless CanHaveDynamicTypes(T).
227 func (s PointsToSet) DynamicTypes() *typeutil.Map {
228 var tmap typeutil.Map
229 tmap.SetHasher(s.a.hasher)
232 for _, x := range s.pts.AppendTo(space[:0]) {
233 ifaceObjID := nodeid(x)
234 if !s.a.isTaggedObject(ifaceObjID) {
235 continue // !CanHaveDynamicTypes(tDyn)
237 tDyn, v, indirect := s.a.taggedValue(ifaceObjID)
239 panic("indirect tagged object") // implement later
241 pts, ok := tmap.At(tDyn).(PointsToSet)
243 pts = PointsToSet{s.a, new(nodeset)}
246 pts.pts.addAll(&s.a.nodes[v].solve.pts)
252 // Intersects reports whether this points-to set and the
253 // argument points-to set contain common members.
254 func (s PointsToSet) Intersects(y PointsToSet) bool {
255 if s.pts == nil || y.pts == nil {
258 // This takes Θ(|x|+|y|) time.
260 z.Intersection(&s.pts.Sparse, &y.pts.Sparse)
264 func (p Pointer) String() string {
265 return fmt.Sprintf("n%d", p.n)
268 // PointsTo returns the points-to set of this pointer.
269 func (p Pointer) PointsTo() PointsToSet {
273 return PointsToSet{p.a, &p.a.nodes[p.n].solve.pts}
276 // MayAlias reports whether the receiver pointer may alias
277 // the argument pointer.
278 func (p Pointer) MayAlias(q Pointer) bool {
279 return p.PointsTo().Intersects(q.PointsTo())
282 // DynamicTypes returns p.PointsTo().DynamicTypes().
283 func (p Pointer) DynamicTypes() *typeutil.Map {
284 return p.PointsTo().DynamicTypes()