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 5package pointer 6 7import ( 8 "bytes" 9 "fmt" 10 "go/types" 11 exec "golang.org/x/sys/execabs" 12 "log" 13 "os" 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. 22func 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// 39func 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 52func 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. 56func 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. 61func 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// 83type 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// 93func (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// 117func (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. 183func (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. 189func (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. 231func (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. 251func sliceToArray(slice types.Type) *types.Array { 252 return types.NewArray(slice.Underlying().(*types.Slice).Elem(), 1) 253} 254 255// Node set ------------------------------------------------------------------- 256 257type nodeset struct { 258 intsets.Sparse 259} 260 261func (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 276func (ns *nodeset) add(n nodeid) bool { 277 return ns.Sparse.Insert(int(n)) 278} 279 280func (ns *nodeset) addAll(y *nodeset) bool { 281 return ns.UnionWith(&y.Sparse) 282} 283 284// Profiling & debugging ------------------------------------------------------- 285 286var timers = make(map[string]time.Time) 287 288func start(name string) { 289 if debugTimers { 290 timers[name] = time.Now() 291 log.Printf("%s...\n", name) 292 } 293} 294 295func 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. 302func 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} 314