.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/api.go

   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         // TODO(adonovan): investigate whether this is desirable.
  32         Mains []*ssa.Package
  33
  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.
  39         Reflection bool
  40
  41         // BuildCallGraph determines whether to construct a callgraph.
  42         // If enabled, the graph will be available in Result.CallGraph.
  43         BuildCallGraph bool
  44
  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
  49         // maps.
  50         //
  51         // (IndirectQueries is typically used for Values corresponding
  52         // to source-level lvalues, e.g. an *ssa.Global.)
  53         //
  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.
  58         //
  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.
  63         //
  64         Queries         map[ssa.Value]struct{}
  65         IndirectQueries map[ssa.Value]struct{}
  66         extendedQueries map[ssa.Value][]*extendedQuery
  67
  68         // If Log is non-nil, log messages are written to it.
  69         // Logging is extremely verbose.
  70         Log io.Writer
  71 }
  72
  73 type track uint32
  74
  75 const (
  76         trackChan  track = 1 << iota // track 'chan' references
  77         trackMap                     // track 'map' references
  78         trackPtr                     // track regular pointers
  79         trackSlice                   // track slice references
  80
  81         trackAll = ^track(0)
  82 )
  83
  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()))
  89         }
  90         if c.Queries == nil {
  91                 c.Queries = make(map[ssa.Value]struct{})
  92         }
  93         c.Queries[v] = struct{}{}
  94 }
  95
  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{})
 101         }
 102         if !CanPoint(mustDeref(v.Type())) {
 103                 panic(fmt.Sprintf("%s is not the address of a pointer-like value: %s", v, v.Type()))
 104         }
 105         c.IndirectQueries[v] = struct{}{}
 106 }
 107
 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.
 111 //
 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.
 119 //
 120 // All field selectors must be explicit, even ones usually elided
 121 // due to promotion of embedded fields.
 122 //
 123 // The query 'x' is identical to using AddQuery. The query '*x' is
 124 // identical to using AddIndirectQuery.
 125 //
 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.
 129 //
 130 // Example:
 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)
 136         if err != nil {
 137                 return nil, fmt.Errorf("invalid query %q: %s", query, err)
 138         }
 139         if c.extendedQueries == nil {
 140                 c.extendedQueries = make(map[ssa.Value][]*extendedQuery)
 141         }
 142
 143         ptr := &Pointer{}
 144         c.extendedQueries[v] = append(c.extendedQueries[v], &extendedQuery{ops: ops, ptr: ptr})
 145         return ptr, nil
 146 }
 147
 148 func (c *Config) prog() *ssa.Program {
 149         for _, main := range c.Mains {
 150                 return main.Prog
 151         }
 152         panic("empty scope")
 153 }
 154
 155 type Warning struct {
 156         Pos     token.Pos
 157         Message string
 158 }
 159
 160 // A Result contains the results of a pointer analysis.
 161 //
 162 // See Config for how to request the various Result components.
 163 //
 164 type Result struct {
 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
 169 }
 170
 171 // A Pointer is an equivalence class of pointer-like values.
 172 //
 173 // A Pointer doesn't have a unique type because pointers of distinct
 174 // types may alias the same object.
 175 //
 176 type Pointer struct {
 177         a *analysis
 178         n nodeid
 179 }
 180
 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
 184         pts *nodeset
 185 }
 186
 187 func (s PointsToSet) String() string {
 188         var buf bytes.Buffer
 189         buf.WriteByte('[')
 190         if s.pts != nil {
 191                 var space [50]int
 192                 for i, l := range s.pts.AppendTo(space[:0]) {
 193                         if i > 0 {
 194                                 buf.WriteString(", ")
 195                         }
 196                         buf.WriteString(s.a.labelFor(nodeid(l)).String())
 197                 }
 198         }
 199         buf.WriteByte(']')
 200         return buf.String()
 201 }
 202
 203 // PointsTo returns the set of labels that this points-to set
 204 // contains.
 205 func (s PointsToSet) Labels() []*Label {
 206         var labels []*Label
 207         if s.pts != nil {
 208                 var space [50]int
 209                 for _, l := range s.pts.AppendTo(space[:0]) {
 210                         labels = append(labels, s.a.labelFor(nodeid(l)))
 211                 }
 212         }
 213         return labels
 214 }
 215
 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.)
 220 //
 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.
 224 //
 225 // The result is empty unless CanHaveDynamicTypes(T).
 226 //
 227 func (s PointsToSet) DynamicTypes() *typeutil.Map {
 228         var tmap typeutil.Map
 229         tmap.SetHasher(s.a.hasher)
 230         if s.pts != nil {
 231                 var space [50]int
 232                 for _, x := range s.pts.AppendTo(space[:0]) {
 233                         ifaceObjID := nodeid(x)
 234                         if !s.a.isTaggedObject(ifaceObjID) {
 235                                 continue // !CanHaveDynamicTypes(tDyn)
 236                         }
 237                         tDyn, v, indirect := s.a.taggedValue(ifaceObjID)
 238                         if indirect {
 239                                 panic("indirect tagged object") // implement later
 240                         }
 241                         pts, ok := tmap.At(tDyn).(PointsToSet)
 242                         if !ok {
 243                                 pts = PointsToSet{s.a, new(nodeset)}
 244                                 tmap.Set(tDyn, pts)
 245                         }
 246                         pts.pts.addAll(&s.a.nodes[v].solve.pts)
 247                 }
 248         }
 249         return &tmap
 250 }
 251
 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 {
 256                 return false
 257         }
 258         // This takes Θ(|x|+|y|) time.
 259         var z intsets.Sparse
 260         z.Intersection(&s.pts.Sparse, &y.pts.Sparse)
 261         return !z.IsEmpty()
 262 }
 263
 264 func (p Pointer) String() string {
 265         return fmt.Sprintf("n%d", p.n)
 266 }
 267
 268 // PointsTo returns the points-to set of this pointer.
 269 func (p Pointer) PointsTo() PointsToSet {
 270         if p.n == 0 {
 271                 return PointsToSet{}
 272         }
 273         return PointsToSet{p.a, &p.a.nodes[p.n].solve.pts}
 274 }
 275
 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())
 280 }
 281
 282 // DynamicTypes returns p.PointsTo().DynamicTypes().
 283 func (p Pointer) DynamicTypes() *typeutil.Map {
 284         return p.PointsTo().DynamicTypes()
 285 }