| // Copyright 2013 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // +build !go1.5 |
| |
| package pointer |
| |
| import ( |
| "bytes" |
| "fmt" |
| "log" |
| "os" |
| "os/exec" |
| "runtime" |
| "time" |
| |
| "golang.org/x/tools/container/intsets" |
| "golang.org/x/tools/go/types" |
| ) |
| |
| // CanPoint reports whether the type T is pointerlike, |
| // for the purposes of this analysis. |
| func CanPoint(T types.Type) bool { |
| switch T := T.(type) { |
| case *types.Named: |
| if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" { |
| return true // treat reflect.Value like interface{} |
| } |
| return CanPoint(T.Underlying()) |
| |
| case *types.Pointer, *types.Interface, *types.Map, *types.Chan, *types.Signature, *types.Slice: |
| return true |
| } |
| |
| return false // array struct tuple builtin basic |
| } |
| |
| // CanHaveDynamicTypes reports whether the type T can "hold" dynamic types, |
| // i.e. is an interface (incl. reflect.Type) or a reflect.Value. |
| // |
| func CanHaveDynamicTypes(T types.Type) bool { |
| switch T := T.(type) { |
| case *types.Named: |
| if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" { |
| return true // reflect.Value |
| } |
| return CanHaveDynamicTypes(T.Underlying()) |
| case *types.Interface: |
| return true |
| } |
| return false |
| } |
| |
| func isInterface(T types.Type) bool { return types.IsInterface(T) } |
| |
| // mustDeref returns the element type of its argument, which must be a |
| // pointer; panic ensues otherwise. |
| func mustDeref(typ types.Type) types.Type { |
| return typ.Underlying().(*types.Pointer).Elem() |
| } |
| |
| // deref returns a pointer's element type; otherwise it returns typ. |
| func deref(typ types.Type) types.Type { |
| if p, ok := typ.Underlying().(*types.Pointer); ok { |
| return p.Elem() |
| } |
| return typ |
| } |
| |
| // A fieldInfo describes one subelement (node) of the flattening-out |
| // of a type T: the subelement's type and its path from the root of T. |
| // |
| // For example, for this type: |
| // type line struct{ points []struct{x, y int} } |
| // flatten() of the inner struct yields the following []fieldInfo: |
| // struct{ x, y int } "" |
| // int ".x" |
| // int ".y" |
| // and flatten(line) yields: |
| // struct{ points []struct{x, y int} } "" |
| // struct{ x, y int } ".points[*]" |
| // int ".points[*].x |
| // int ".points[*].y" |
| // |
| type fieldInfo struct { |
| typ types.Type |
| |
| // op and tail describe the path to the element (e.g. ".a#2.b[*].c"). |
| op interface{} // *Array: true; *Tuple: int; *Struct: *types.Var; *Named: nil |
| tail *fieldInfo |
| } |
| |
| // path returns a user-friendly string describing the subelement path. |
| // |
| func (fi *fieldInfo) path() string { |
| var buf bytes.Buffer |
| for p := fi; p != nil; p = p.tail { |
| switch op := p.op.(type) { |
| case bool: |
| fmt.Fprintf(&buf, "[*]") |
| case int: |
| fmt.Fprintf(&buf, "#%d", op) |
| case *types.Var: |
| fmt.Fprintf(&buf, ".%s", op.Name()) |
| } |
| } |
| return buf.String() |
| } |
| |
| // flatten returns a list of directly contained fields in the preorder |
| // traversal of the type tree of t. The resulting elements are all |
| // scalars (basic types or pointerlike types), except for struct/array |
| // "identity" nodes, whose type is that of the aggregate. |
| // |
| // reflect.Value is considered pointerlike, similar to interface{}. |
| // |
| // Callers must not mutate the result. |
| // |
| func (a *analysis) flatten(t types.Type) []*fieldInfo { |
| fl, ok := a.flattenMemo[t] |
| if !ok { |
| switch t := t.(type) { |
| case *types.Named: |
| u := t.Underlying() |
| if isInterface(u) { |
| // Debuggability hack: don't remove |
| // the named type from interfaces as |
| // they're very verbose. |
| fl = append(fl, &fieldInfo{typ: t}) |
| } else { |
| fl = a.flatten(u) |
| } |
| |
| case *types.Basic, |
| *types.Signature, |
| *types.Chan, |
| *types.Map, |
| *types.Interface, |
| *types.Slice, |
| *types.Pointer: |
| fl = append(fl, &fieldInfo{typ: t}) |
| |
| case *types.Array: |
| fl = append(fl, &fieldInfo{typ: t}) // identity node |
| for _, fi := range a.flatten(t.Elem()) { |
| fl = append(fl, &fieldInfo{typ: fi.typ, op: true, tail: fi}) |
| } |
| |
| case *types.Struct: |
| fl = append(fl, &fieldInfo{typ: t}) // identity node |
| for i, n := 0, t.NumFields(); i < n; i++ { |
| f := t.Field(i) |
| for _, fi := range a.flatten(f.Type()) { |
| fl = append(fl, &fieldInfo{typ: fi.typ, op: f, tail: fi}) |
| } |
| } |
| |
| case *types.Tuple: |
| // No identity node: tuples are never address-taken. |
| n := t.Len() |
| if n == 1 { |
| // Don't add a fieldInfo link for singletons, |
| // e.g. in params/results. |
| fl = append(fl, a.flatten(t.At(0).Type())...) |
| } else { |
| for i := 0; i < n; i++ { |
| f := t.At(i) |
| for _, fi := range a.flatten(f.Type()) { |
| fl = append(fl, &fieldInfo{typ: fi.typ, op: i, tail: fi}) |
| } |
| } |
| } |
| |
| default: |
| panic(t) |
| } |
| |
| a.flattenMemo[t] = fl |
| } |
| |
| return fl |
| } |
| |
| // sizeof returns the number of pointerlike abstractions (nodes) in the type t. |
| func (a *analysis) sizeof(t types.Type) uint32 { |
| return uint32(len(a.flatten(t))) |
| } |
| |
| // shouldTrack reports whether object type T contains (recursively) |
| // any fields whose addresses should be tracked. |
| func (a *analysis) shouldTrack(T types.Type) bool { |
| if a.track == trackAll { |
| return true // fast path |
| } |
| track, ok := a.trackTypes[T] |
| if !ok { |
| a.trackTypes[T] = true // break cycles conservatively |
| // NB: reflect.Value, reflect.Type are pre-populated to true. |
| for _, fi := range a.flatten(T) { |
| switch ft := fi.typ.Underlying().(type) { |
| case *types.Interface, *types.Signature: |
| track = true // needed for callgraph |
| case *types.Basic: |
| // no-op |
| case *types.Chan: |
| track = a.track&trackChan != 0 || a.shouldTrack(ft.Elem()) |
| case *types.Map: |
| track = a.track&trackMap != 0 || a.shouldTrack(ft.Key()) || a.shouldTrack(ft.Elem()) |
| case *types.Slice: |
| track = a.track&trackSlice != 0 || a.shouldTrack(ft.Elem()) |
| case *types.Pointer: |
| track = a.track&trackPtr != 0 || a.shouldTrack(ft.Elem()) |
| case *types.Array, *types.Struct: |
| // No need to look at field types since they will follow (flattened). |
| default: |
| // Includes *types.Tuple, which are never address-taken. |
| panic(ft) |
| } |
| if track { |
| break |
| } |
| } |
| a.trackTypes[T] = track |
| if !track && a.log != nil { |
| fmt.Fprintf(a.log, "\ttype not tracked: %s\n", T) |
| } |
| } |
| return track |
| } |
| |
| // offsetOf returns the (abstract) offset of field index within struct |
| // or tuple typ. |
| func (a *analysis) offsetOf(typ types.Type, index int) uint32 { |
| var offset uint32 |
| switch t := typ.Underlying().(type) { |
| case *types.Tuple: |
| for i := 0; i < index; i++ { |
| offset += a.sizeof(t.At(i).Type()) |
| } |
| case *types.Struct: |
| offset++ // the node for the struct itself |
| for i := 0; i < index; i++ { |
| offset += a.sizeof(t.Field(i).Type()) |
| } |
| default: |
| panic(fmt.Sprintf("offsetOf(%s : %T)", typ, typ)) |
| } |
| return offset |
| } |
| |
| // sliceToArray returns the type representing the arrays to which |
| // slice type slice points. |
| func sliceToArray(slice types.Type) *types.Array { |
| return types.NewArray(slice.Underlying().(*types.Slice).Elem(), 1) |
| } |
| |
| // Node set ------------------------------------------------------------------- |
| |
| type nodeset struct { |
| intsets.Sparse |
| } |
| |
| func (ns *nodeset) String() string { |
| var buf bytes.Buffer |
| buf.WriteRune('{') |
| var space [50]int |
| for i, n := range ns.AppendTo(space[:0]) { |
| if i > 0 { |
| buf.WriteString(", ") |
| } |
| buf.WriteRune('n') |
| fmt.Fprintf(&buf, "%d", n) |
| } |
| buf.WriteRune('}') |
| return buf.String() |
| } |
| |
| func (ns *nodeset) add(n nodeid) bool { |
| return ns.Sparse.Insert(int(n)) |
| } |
| |
| func (x *nodeset) addAll(y *nodeset) bool { |
| return x.UnionWith(&y.Sparse) |
| } |
| |
| // Profiling & debugging ------------------------------------------------------- |
| |
| var timers = make(map[string]time.Time) |
| |
| func start(name string) { |
| if debugTimers { |
| timers[name] = time.Now() |
| log.Printf("%s...\n", name) |
| } |
| } |
| |
| func stop(name string) { |
| if debugTimers { |
| log.Printf("%s took %s\n", name, time.Since(timers[name])) |
| } |
| } |
| |
| // diff runs the command "diff a b" and reports its success. |
| func diff(a, b string) bool { |
| var cmd *exec.Cmd |
| switch runtime.GOOS { |
| case "plan9": |
| cmd = exec.Command("/bin/diff", "-c", a, b) |
| default: |
| cmd = exec.Command("/usr/bin/diff", "-u", a, b) |
| } |
| cmd.Stdout = os.Stderr |
| cmd.Stderr = os.Stderr |
| return cmd.Run() == nil |
| } |