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