.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/go/pointer/util.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/types"
  11         "log"
  12         "os"
  13         "os/exec"
  14         "runtime"
  15         "time"
  16
  17         "golang.org/x/tools/container/intsets"
  18 )
  19
  20 // CanPoint reports whether the type T is pointerlike,
  21 // for the purposes of this analysis.
  22 func CanPoint(T types.Type) bool {
  23         switch T := T.(type) {
  24         case *types.Named:
  25                 if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" {
  26                         return true // treat reflect.Value like interface{}
  27                 }
  28                 return CanPoint(T.Underlying())
  29         case *types.Pointer, *types.Interface, *types.Map, *types.Chan, *types.Signature, *types.Slice:
  30                 return true
  31         }
  32
  33         return false // array struct tuple builtin basic
  34 }
  35
  36 // CanHaveDynamicTypes reports whether the type T can "hold" dynamic types,
  37 // i.e. is an interface (incl. reflect.Type) or a reflect.Value.
  38 //
  39 func CanHaveDynamicTypes(T types.Type) bool {
  40         switch T := T.(type) {
  41         case *types.Named:
  42                 if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" {
  43                         return true // reflect.Value
  44                 }
  45                 return CanHaveDynamicTypes(T.Underlying())
  46         case *types.Interface:
  47                 return true
  48         }
  49         return false
  50 }
  51
  52 func isInterface(T types.Type) bool { return types.IsInterface(T) }
  53
  54 // mustDeref returns the element type of its argument, which must be a
  55 // pointer; panic ensues otherwise.
  56 func mustDeref(typ types.Type) types.Type {
  57         return typ.Underlying().(*types.Pointer).Elem()
  58 }
  59
  60 // deref returns a pointer's element type; otherwise it returns typ.
  61 func deref(typ types.Type) types.Type {
  62         if p, ok := typ.Underlying().(*types.Pointer); ok {
  63                 return p.Elem()
  64         }
  65         return typ
  66 }
  67
  68 // A fieldInfo describes one subelement (node) of the flattening-out
  69 // of a type T: the subelement's type and its path from the root of T.
  70 //
  71 // For example, for this type:
  72 //     type line struct{ points []struct{x, y int} }
  73 // flatten() of the inner struct yields the following []fieldInfo:
  74 //    struct{ x, y int }                      ""
  75 //    int                                     ".x"
  76 //    int                                     ".y"
  77 // and flatten(line) yields:
  78 //    struct{ points []struct{x, y int} }     ""
  79 //    struct{ x, y int }                      ".points[*]"
  80 //    int                                     ".points[*].x
  81 //    int                                     ".points[*].y"
  82 //
  83 type fieldInfo struct {
  84         typ types.Type
  85
  86         // op and tail describe the path to the element (e.g. ".a#2.b[*].c").
  87         op   interface{} // *Array: true; *Tuple: int; *Struct: *types.Var; *Named: nil
  88         tail *fieldInfo
  89 }
  90
  91 // path returns a user-friendly string describing the subelement path.
  92 //
  93 func (fi *fieldInfo) path() string {
  94         var buf bytes.Buffer
  95         for p := fi; p != nil; p = p.tail {
  96                 switch op := p.op.(type) {
  97                 case bool:
  98                         fmt.Fprintf(&buf, "[*]")
  99                 case int:
 100                         fmt.Fprintf(&buf, "#%d", op)
 101                 case *types.Var:
 102                         fmt.Fprintf(&buf, ".%s", op.Name())
 103                 }
 104         }
 105         return buf.String()
 106 }
 107
 108 // flatten returns a list of directly contained fields in the preorder
 109 // traversal of the type tree of t.  The resulting elements are all
 110 // scalars (basic types or pointerlike types), except for struct/array
 111 // "identity" nodes, whose type is that of the aggregate.
 112 //
 113 // reflect.Value is considered pointerlike, similar to interface{}.
 114 //
 115 // Callers must not mutate the result.
 116 //
 117 func (a *analysis) flatten(t types.Type) []*fieldInfo {
 118         fl, ok := a.flattenMemo[t]
 119         if !ok {
 120                 switch t := t.(type) {
 121                 case *types.Named:
 122                         u := t.Underlying()
 123                         if isInterface(u) {
 124                                 // Debuggability hack: don't remove
 125                                 // the named type from interfaces as
 126                                 // they're very verbose.
 127                                 fl = append(fl, &fieldInfo{typ: t})
 128                         } else {
 129                                 fl = a.flatten(u)
 130                         }
 131
 132                 case *types.Basic,
 133                         *types.Signature,
 134                         *types.Chan,
 135                         *types.Map,
 136                         *types.Interface,
 137                         *types.Slice,
 138                         *types.Pointer:
 139                         fl = append(fl, &fieldInfo{typ: t})
 140
 141                 case *types.Array:
 142                         fl = append(fl, &fieldInfo{typ: t}) // identity node
 143                         for _, fi := range a.flatten(t.Elem()) {
 144                                 fl = append(fl, &fieldInfo{typ: fi.typ, op: true, tail: fi})
 145                         }
 146
 147                 case *types.Struct:
 148                         fl = append(fl, &fieldInfo{typ: t}) // identity node
 149                         for i, n := 0, t.NumFields(); i < n; i++ {
 150                                 f := t.Field(i)
 151                                 for _, fi := range a.flatten(f.Type()) {
 152                                         fl = append(fl, &fieldInfo{typ: fi.typ, op: f, tail: fi})
 153                                 }
 154                         }
 155
 156                 case *types.Tuple:
 157                         // No identity node: tuples are never address-taken.
 158                         n := t.Len()
 159                         if n == 1 {
 160                                 // Don't add a fieldInfo link for singletons,
 161                                 // e.g. in params/results.
 162                                 fl = append(fl, a.flatten(t.At(0).Type())...)
 163                         } else {
 164                                 for i := 0; i < n; i++ {
 165                                         f := t.At(i)
 166                                         for _, fi := range a.flatten(f.Type()) {
 167                                                 fl = append(fl, &fieldInfo{typ: fi.typ, op: i, tail: fi})
 168                                         }
 169                                 }
 170                         }
 171
 172                 default:
 173                         panic(fmt.Sprintf("cannot flatten unsupported type %T", t))
 174                 }
 175
 176                 a.flattenMemo[t] = fl
 177         }
 178
 179         return fl
 180 }
 181
 182 // sizeof returns the number of pointerlike abstractions (nodes) in the type t.
 183 func (a *analysis) sizeof(t types.Type) uint32 {
 184         return uint32(len(a.flatten(t)))
 185 }
 186
 187 // shouldTrack reports whether object type T contains (recursively)
 188 // any fields whose addresses should be tracked.
 189 func (a *analysis) shouldTrack(T types.Type) bool {
 190         if a.track == trackAll {
 191                 return true // fast path
 192         }
 193         track, ok := a.trackTypes[T]
 194         if !ok {
 195                 a.trackTypes[T] = true // break cycles conservatively
 196                 // NB: reflect.Value, reflect.Type are pre-populated to true.
 197                 for _, fi := range a.flatten(T) {
 198                         switch ft := fi.typ.Underlying().(type) {
 199                         case *types.Interface, *types.Signature:
 200                                 track = true // needed for callgraph
 201                         case *types.Basic:
 202                                 // no-op
 203                         case *types.Chan:
 204                                 track = a.track&trackChan != 0 || a.shouldTrack(ft.Elem())
 205                         case *types.Map:
 206                                 track = a.track&trackMap != 0 || a.shouldTrack(ft.Key()) || a.shouldTrack(ft.Elem())
 207                         case *types.Slice:
 208                                 track = a.track&trackSlice != 0 || a.shouldTrack(ft.Elem())
 209                         case *types.Pointer:
 210                                 track = a.track&trackPtr != 0 || a.shouldTrack(ft.Elem())
 211                         case *types.Array, *types.Struct:
 212                                 // No need to look at field types since they will follow (flattened).
 213                         default:
 214                                 // Includes *types.Tuple, which are never address-taken.
 215                                 panic(ft)
 216                         }
 217                         if track {
 218                                 break
 219                         }
 220                 }
 221                 a.trackTypes[T] = track
 222                 if !track && a.log != nil {
 223                         fmt.Fprintf(a.log, "\ttype not tracked: %s\n", T)
 224                 }
 225         }
 226         return track
 227 }
 228
 229 // offsetOf returns the (abstract) offset of field index within struct
 230 // or tuple typ.
 231 func (a *analysis) offsetOf(typ types.Type, index int) uint32 {
 232         var offset uint32
 233         switch t := typ.Underlying().(type) {
 234         case *types.Tuple:
 235                 for i := 0; i < index; i++ {
 236                         offset += a.sizeof(t.At(i).Type())
 237                 }
 238         case *types.Struct:
 239                 offset++ // the node for the struct itself
 240                 for i := 0; i < index; i++ {
 241                         offset += a.sizeof(t.Field(i).Type())
 242                 }
 243         default:
 244                 panic(fmt.Sprintf("offsetOf(%s : %T)", typ, typ))
 245         }
 246         return offset
 247 }
 248
 249 // sliceToArray returns the type representing the arrays to which
 250 // slice type slice points.
 251 func sliceToArray(slice types.Type) *types.Array {
 252         return types.NewArray(slice.Underlying().(*types.Slice).Elem(), 1)
 253 }
 254
 255 // Node set -------------------------------------------------------------------
 256
 257 type nodeset struct {
 258         intsets.Sparse
 259 }
 260
 261 func (ns *nodeset) String() string {
 262         var buf bytes.Buffer
 263         buf.WriteRune('{')
 264         var space [50]int
 265         for i, n := range ns.AppendTo(space[:0]) {
 266                 if i > 0 {
 267                         buf.WriteString(", ")
 268                 }
 269                 buf.WriteRune('n')
 270                 fmt.Fprintf(&buf, "%d", n)
 271         }
 272         buf.WriteRune('}')
 273         return buf.String()
 274 }
 275
 276 func (ns *nodeset) add(n nodeid) bool {
 277         return ns.Sparse.Insert(int(n))
 278 }
 279
 280 func (ns *nodeset) addAll(y *nodeset) bool {
 281         return ns.UnionWith(&y.Sparse)
 282 }
 283
 284 // Profiling & debugging -------------------------------------------------------
 285
 286 var timers = make(map[string]time.Time)
 287
 288 func start(name string) {
 289         if debugTimers {
 290                 timers[name] = time.Now()
 291                 log.Printf("%s...\n", name)
 292         }
 293 }
 294
 295 func stop(name string) {
 296         if debugTimers {
 297                 log.Printf("%s took %s\n", name, time.Since(timers[name]))
 298         }
 299 }
 300
 301 // diff runs the command "diff a b" and reports its success.
 302 func diff(a, b string) bool {
 303         var cmd *exec.Cmd
 304         switch runtime.GOOS {
 305         case "plan9":
 306                 cmd = exec.Command("/bin/diff", "-c", a, b)
 307         default:
 308                 cmd = exec.Command("/usr/bin/diff", "-u", a, b)
 309         }
 310         cmd.Stdout = os.Stderr
 311         cmd.Stderr = os.Stderr
 312         return cmd.Run() == nil
 313 }