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 pointer 6 7 import ( 8 "bytes" 9 "fmt" 10 "go/token" 11 "io" 12 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" 17 ) 18 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 21 // reused. 22 type Config struct { 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. 26 // 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 30 // thus methods. 31 // 32 // TODO(adonovan): investigate whether this is desirable. 33 // 34 // Calls to generic functions will be unsound unless packages 35 // are built using the ssa.InstantiateGenerics builder mode. 36 Mains []*ssa.Package 37 38 // Reflection determines whether to handle reflection 39 // operators soundly, which is currently rather slow since it 40 // causes constraint to be generated during solving 41 // proportional to the number of constraint variables, which 42 // has not yet been reduced by presolver optimisation. 43 Reflection bool 44 45 // BuildCallGraph determines whether to construct a callgraph. 46 // If enabled, the graph will be available in Result.CallGraph. 47 BuildCallGraph bool 48 49 // The client populates Queries[v] or IndirectQueries[v] 50 // for each ssa.Value v of interest, to request that the 51 // points-to sets pts(v) or pts(*v) be computed. If the 52 // client needs both points-to sets, v may appear in both 53 // maps. 54 // 55 // (IndirectQueries is typically used for Values corresponding 56 // to source-level lvalues, e.g. an *ssa.Global.) 57 // 58 // The analysis populates the corresponding 59 // Result.{Indirect,}Queries map when it creates the pointer 60 // variable for v or *v. Upon completion the client can 61 // inspect that map for the results. 62 // 63 // TODO(adonovan): this API doesn't scale well for batch tools 64 // that want to dump the entire solution. Perhaps optionally 65 // populate a map[*ssa.DebugRef]Pointer in the Result, one 66 // entry per source expression. 67 // 68 Queries map[ssa.Value]struct{} 69 IndirectQueries map[ssa.Value]struct{} 70 extendedQueries map[ssa.Value][]*extendedQuery 71 72 // If Log is non-nil, log messages are written to it. 73 // Logging is extremely verbose. 74 Log io.Writer 75 } 76 77 type track uint32 78 79 const ( 80 trackChan track = 1 << iota // track 'chan' references 81 trackMap // track 'map' references 82 trackPtr // track regular pointers 83 trackSlice // track slice references 84 85 trackAll = ^track(0) 86 ) 87 88 // AddQuery adds v to Config.Queries. 89 // Precondition: CanPoint(v.Type()). 90 func (c *Config) AddQuery(v ssa.Value) { 91 if !CanPoint(v.Type()) { 92 panic(fmt.Sprintf("%s is not a pointer-like value: %s", v, v.Type())) 93 } 94 if c.Queries == nil { 95 c.Queries = make(map[ssa.Value]struct{}) 96 } 97 c.Queries[v] = struct{}{} 98 } 99 100 // AddQuery adds v to Config.IndirectQueries. 101 // Precondition: CanPoint(v.Type().Underlying().(*types.Pointer).Elem()). 102 func (c *Config) AddIndirectQuery(v ssa.Value) { 103 if c.IndirectQueries == nil { 104 c.IndirectQueries = make(map[ssa.Value]struct{}) 105 } 106 if !CanPoint(mustDeref(v.Type())) { 107 panic(fmt.Sprintf("%s is not the address of a pointer-like value: %s", v, v.Type())) 108 } 109 c.IndirectQueries[v] = struct{}{} 110 } 111 112 // AddExtendedQuery adds an extended, AST-based query on v to the 113 // analysis. The query, which must be a single Go expression, allows 114 // destructuring the value. 115 // 116 // The query must operate on a variable named 'x', which represents 117 // the value, and result in a pointer-like object. Only a subset of 118 // Go expressions are permitted in queries, namely channel receives, 119 // pointer dereferences, field selectors, array/slice/map/tuple 120 // indexing and grouping with parentheses. The specific indices when 121 // indexing arrays, slices and maps have no significance. Indices used 122 // on tuples must be numeric and within bounds. 123 // 124 // All field selectors must be explicit, even ones usually elided 125 // due to promotion of embedded fields. 126 // 127 // The query 'x' is identical to using AddQuery. The query '*x' is 128 // identical to using AddIndirectQuery. 129 // 130 // On success, AddExtendedQuery returns a Pointer to the queried 131 // value. This Pointer will be initialized during analysis. Using it 132 // before analysis has finished has undefined behavior. 133 // 134 // Example: 135 // 136 // // given v, which represents a function call to 'fn() (int, []*T)', and 137 // // 'type T struct { F *int }', the following query will access the field F. 138 // c.AddExtendedQuery(v, "x[1][0].F") 139 func (c *Config) AddExtendedQuery(v ssa.Value, query string) (*Pointer, error) { 140 ops, _, err := parseExtendedQuery(v.Type(), query) 141 if err != nil { 142 return nil, fmt.Errorf("invalid query %q: %s", query, err) 143 } 144 if c.extendedQueries == nil { 145 c.extendedQueries = make(map[ssa.Value][]*extendedQuery) 146 } 147 148 ptr := &Pointer{} 149 c.extendedQueries[v] = append(c.extendedQueries[v], &extendedQuery{ops: ops, ptr: ptr}) 150 return ptr, nil 151 } 152 153 func (c *Config) prog() *ssa.Program { 154 for _, main := range c.Mains { 155 return main.Prog 156 } 157 panic("empty scope") 158 } 159 160 type Warning struct { 161 Pos token.Pos 162 Message string 163 } 164 165 // A Result contains the results of a pointer analysis. 166 // 167 // See Config for how to request the various Result components. 168 type Result struct { 169 CallGraph *callgraph.Graph // discovered call graph 170 Queries map[ssa.Value]Pointer // pts(v) for each v in Config.Queries. 171 IndirectQueries map[ssa.Value]Pointer // pts(*v) for each v in Config.IndirectQueries. 172 Warnings []Warning // warnings of unsoundness 173 } 174 175 // A Pointer is an equivalence class of pointer-like values. 176 // 177 // A Pointer doesn't have a unique type because pointers of distinct 178 // types may alias the same object. 179 type Pointer struct { 180 a *analysis 181 n nodeid 182 } 183 184 // A PointsToSet is a set of labels (locations or allocations). 185 type PointsToSet struct { 186 a *analysis // may be nil if pts is nil 187 pts *nodeset 188 } 189 190 func (s PointsToSet) String() string { 191 var buf bytes.Buffer 192 buf.WriteByte('[') 193 if s.pts != nil { 194 var space [50]int 195 for i, l := range s.pts.AppendTo(space[:0]) { 196 if i > 0 { 197 buf.WriteString(", ") 198 } 199 buf.WriteString(s.a.labelFor(nodeid(l)).String()) 200 } 201 } 202 buf.WriteByte(']') 203 return buf.String() 204 } 205 206 // PointsTo returns the set of labels that this points-to set 207 // contains. 208 func (s PointsToSet) Labels() []*Label { 209 var labels []*Label 210 if s.pts != nil { 211 var space [50]int 212 for _, l := range s.pts.AppendTo(space[:0]) { 213 labels = append(labels, s.a.labelFor(nodeid(l))) 214 } 215 } 216 return labels 217 } 218 219 // If this PointsToSet came from a Pointer of interface kind 220 // or a reflect.Value, DynamicTypes returns the set of dynamic 221 // types that it may contain. (For an interface, they will 222 // always be concrete types.) 223 // 224 // The result is a mapping whose keys are the dynamic types to which 225 // it may point. For each pointer-like key type, the corresponding 226 // map value is the PointsToSet for pointers of that type. 227 // 228 // The result is empty unless CanHaveDynamicTypes(T). 229 func (s PointsToSet) DynamicTypes() *typeutil.Map { 230 var tmap typeutil.Map 231 tmap.SetHasher(s.a.hasher) 232 if s.pts != nil { 233 var space [50]int 234 for _, x := range s.pts.AppendTo(space[:0]) { 235 ifaceObjID := nodeid(x) 236 if !s.a.isTaggedObject(ifaceObjID) { 237 continue // !CanHaveDynamicTypes(tDyn) 238 } 239 tDyn, v, indirect := s.a.taggedValue(ifaceObjID) 240 if indirect { 241 panic("indirect tagged object") // implement later 242 } 243 pts, ok := tmap.At(tDyn).(PointsToSet) 244 if !ok { 245 pts = PointsToSet{s.a, new(nodeset)} 246 tmap.Set(tDyn, pts) 247 } 248 pts.pts.addAll(&s.a.nodes[v].solve.pts) 249 } 250 } 251 return &tmap 252 } 253 254 // Intersects reports whether this points-to set and the 255 // argument points-to set contain common members. 256 func (s PointsToSet) Intersects(y PointsToSet) bool { 257 if s.pts == nil || y.pts == nil { 258 return false 259 } 260 // This takes Θ(|x|+|y|) time. 261 var z intsets.Sparse 262 z.Intersection(&s.pts.Sparse, &y.pts.Sparse) 263 return !z.IsEmpty() 264 } 265 266 func (p Pointer) String() string { 267 return fmt.Sprintf("n%d", p.n) 268 } 269 270 // PointsTo returns the points-to set of this pointer. 271 func (p Pointer) PointsTo() PointsToSet { 272 if p.n == 0 { 273 return PointsToSet{} 274 } 275 return PointsToSet{p.a, &p.a.nodes[p.n].solve.pts} 276 } 277 278 // MayAlias reports whether the receiver pointer may alias 279 // the argument pointer. 280 func (p Pointer) MayAlias(q Pointer) bool { 281 return p.PointsTo().Intersects(q.PointsTo()) 282 } 283 284 // DynamicTypes returns p.PointsTo().DynamicTypes(). 285 func (p Pointer) DynamicTypes() *typeutil.Map { 286 return p.PointsTo().DynamicTypes() 287 } 288