util.go

Documentation: golang.org/x/tools/go/pointer

     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
View as plain text