| 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 |
Members