graph.go

Documentation: golang.org/x/tools/go/callgraph/vta

     1  // Copyright 2021 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 vta
     6  
     7  import (
     8  	"fmt"
     9  	"go/token"
    10  	"go/types"
    11  
    12  	"golang.org/x/tools/go/callgraph"
    13  	"golang.org/x/tools/go/ssa"
    14  	"golang.org/x/tools/go/types/typeutil"
    15  )
    16  
    17  // node interface for VTA nodes.
    18  type node interface {
    19  	Type() types.Type
    20  	String() string
    21  }
    22  
    23  // constant node for VTA.
    24  type constant struct {
    25  	typ types.Type
    26  }
    27  
    28  func (c constant) Type() types.Type {
    29  	return c.typ
    30  }
    31  
    32  func (c constant) String() string {
    33  	return fmt.Sprintf("Constant(%v)", c.Type())
    34  }
    35  
    36  // pointer node for VTA.
    37  type pointer struct {
    38  	typ *types.Pointer
    39  }
    40  
    41  func (p pointer) Type() types.Type {
    42  	return p.typ
    43  }
    44  
    45  func (p pointer) String() string {
    46  	return fmt.Sprintf("Pointer(%v)", p.Type())
    47  }
    48  
    49  // mapKey node for VTA, modeling reachable map key types.
    50  type mapKey struct {
    51  	typ types.Type
    52  }
    53  
    54  func (mk mapKey) Type() types.Type {
    55  	return mk.typ
    56  }
    57  
    58  func (mk mapKey) String() string {
    59  	return fmt.Sprintf("MapKey(%v)", mk.Type())
    60  }
    61  
    62  // mapValue node for VTA, modeling reachable map value types.
    63  type mapValue struct {
    64  	typ types.Type
    65  }
    66  
    67  func (mv mapValue) Type() types.Type {
    68  	return mv.typ
    69  }
    70  
    71  func (mv mapValue) String() string {
    72  	return fmt.Sprintf("MapValue(%v)", mv.Type())
    73  }
    74  
    75  // sliceElem node for VTA, modeling reachable slice and array element types.
    76  type sliceElem struct {
    77  	typ types.Type
    78  }
    79  
    80  func (s sliceElem) Type() types.Type {
    81  	return s.typ
    82  }
    83  
    84  func (s sliceElem) String() string {
    85  	return fmt.Sprintf("Slice([]%v)", s.Type())
    86  }
    87  
    88  // channelElem node for VTA, modeling reachable channel element types.
    89  type channelElem struct {
    90  	typ types.Type
    91  }
    92  
    93  func (c channelElem) Type() types.Type {
    94  	return c.typ
    95  }
    96  
    97  func (c channelElem) String() string {
    98  	return fmt.Sprintf("Channel(chan %v)", c.Type())
    99  }
   100  
   101  // field node for VTA.
   102  type field struct {
   103  	StructType types.Type
   104  	index      int // index of the field in the struct
   105  }
   106  
   107  func (f field) Type() types.Type {
   108  	s := f.StructType.Underlying().(*types.Struct)
   109  	return s.Field(f.index).Type()
   110  }
   111  
   112  func (f field) String() string {
   113  	s := f.StructType.Underlying().(*types.Struct)
   114  	return fmt.Sprintf("Field(%v:%s)", f.StructType, s.Field(f.index).Name())
   115  }
   116  
   117  // global node for VTA.
   118  type global struct {
   119  	val *ssa.Global
   120  }
   121  
   122  func (g global) Type() types.Type {
   123  	return g.val.Type()
   124  }
   125  
   126  func (g global) String() string {
   127  	return fmt.Sprintf("Global(%s)", g.val.Name())
   128  }
   129  
   130  // local node for VTA modeling local variables
   131  // and function/method parameters.
   132  type local struct {
   133  	val ssa.Value
   134  }
   135  
   136  func (l local) Type() types.Type {
   137  	return l.val.Type()
   138  }
   139  
   140  func (l local) String() string {
   141  	return fmt.Sprintf("Local(%s)", l.val.Name())
   142  }
   143  
   144  // indexedLocal node for VTA node. Models indexed locals
   145  // related to the ssa extract instructions.
   146  type indexedLocal struct {
   147  	val   ssa.Value
   148  	index int
   149  	typ   types.Type
   150  }
   151  
   152  func (i indexedLocal) Type() types.Type {
   153  	return i.typ
   154  }
   155  
   156  func (i indexedLocal) String() string {
   157  	return fmt.Sprintf("Local(%s[%d])", i.val.Name(), i.index)
   158  }
   159  
   160  // function node for VTA.
   161  type function struct {
   162  	f *ssa.Function
   163  }
   164  
   165  func (f function) Type() types.Type {
   166  	return f.f.Type()
   167  }
   168  
   169  func (f function) String() string {
   170  	return fmt.Sprintf("Function(%s)", f.f.Name())
   171  }
   172  
   173  // nestedPtrInterface node represents all references and dereferences
   174  // of locals and globals that have a nested pointer to interface type.
   175  // We merge such constructs into a single node for simplicity and without
   176  // much precision sacrifice as such variables are rare in practice. Both
   177  // a and b would be represented as the same PtrInterface(I) node in:
   178  //
   179  //	type I interface
   180  //	var a ***I
   181  //	var b **I
   182  type nestedPtrInterface struct {
   183  	typ types.Type
   184  }
   185  
   186  func (l nestedPtrInterface) Type() types.Type {
   187  	return l.typ
   188  }
   189  
   190  func (l nestedPtrInterface) String() string {
   191  	return fmt.Sprintf("PtrInterface(%v)", l.typ)
   192  }
   193  
   194  // nestedPtrFunction node represents all references and dereferences of locals
   195  // and globals that have a nested pointer to function type. We merge such
   196  // constructs into a single node for simplicity and without much precision
   197  // sacrifice as such variables are rare in practice. Both a and b would be
   198  // represented as the same PtrFunction(func()) node in:
   199  //
   200  //	var a *func()
   201  //	var b **func()
   202  type nestedPtrFunction struct {
   203  	typ types.Type
   204  }
   205  
   206  func (p nestedPtrFunction) Type() types.Type {
   207  	return p.typ
   208  }
   209  
   210  func (p nestedPtrFunction) String() string {
   211  	return fmt.Sprintf("PtrFunction(%v)", p.typ)
   212  }
   213  
   214  // panicArg models types of all arguments passed to panic.
   215  type panicArg struct{}
   216  
   217  func (p panicArg) Type() types.Type {
   218  	return nil
   219  }
   220  
   221  func (p panicArg) String() string {
   222  	return "Panic"
   223  }
   224  
   225  // recoverReturn models types of all return values of recover().
   226  type recoverReturn struct{}
   227  
   228  func (r recoverReturn) Type() types.Type {
   229  	return nil
   230  }
   231  
   232  func (r recoverReturn) String() string {
   233  	return "Recover"
   234  }
   235  
   236  // vtaGraph remembers for each VTA node the set of its successors.
   237  // Tailored for VTA, hence does not support singleton (sub)graphs.
   238  type vtaGraph map[node]map[node]bool
   239  
   240  // addEdge adds an edge x->y to the graph.
   241  func (g vtaGraph) addEdge(x, y node) {
   242  	succs, ok := g[x]
   243  	if !ok {
   244  		succs = make(map[node]bool)
   245  		g[x] = succs
   246  	}
   247  	succs[y] = true
   248  }
   249  
   250  // successors returns all of n's immediate successors in the graph.
   251  // The order of successor nodes is arbitrary.
   252  func (g vtaGraph) successors(n node) []node {
   253  	var succs []node
   254  	for succ := range g[n] {
   255  		succs = append(succs, succ)
   256  	}
   257  	return succs
   258  }
   259  
   260  // typePropGraph builds a VTA graph for a set of `funcs` and initial
   261  // `callgraph` needed to establish interprocedural edges. Returns the
   262  // graph and a map for unique type representatives.
   263  func typePropGraph(funcs map[*ssa.Function]bool, callgraph *callgraph.Graph) (vtaGraph, *typeutil.Map) {
   264  	b := builder{graph: make(vtaGraph), callGraph: callgraph}
   265  	b.visit(funcs)
   266  	return b.graph, &b.canon
   267  }
   268  
   269  // Data structure responsible for linearly traversing the
   270  // code and building a VTA graph.
   271  type builder struct {
   272  	graph     vtaGraph
   273  	callGraph *callgraph.Graph // initial call graph for creating flows at unresolved call sites.
   274  
   275  	// Specialized type map for canonicalization of types.Type.
   276  	// Semantically equivalent types can have different implementations,
   277  	// i.e., they are different pointer values. The map allows us to
   278  	// have one unique representative. The keys are fixed and from the
   279  	// client perspective they are types. The values in our case are
   280  	// types too, in particular type representatives. Each value is a
   281  	// pointer so this map is not expected to take much memory.
   282  	canon typeutil.Map
   283  }
   284  
   285  func (b *builder) visit(funcs map[*ssa.Function]bool) {
   286  	// Add the fixed edge Panic -> Recover
   287  	b.graph.addEdge(panicArg{}, recoverReturn{})
   288  
   289  	for f, in := range funcs {
   290  		if in {
   291  			b.fun(f)
   292  		}
   293  	}
   294  }
   295  
   296  func (b *builder) fun(f *ssa.Function) {
   297  	for _, bl := range f.Blocks {
   298  		for _, instr := range bl.Instrs {
   299  			b.instr(instr)
   300  		}
   301  	}
   302  }
   303  
   304  func (b *builder) instr(instr ssa.Instruction) {
   305  	switch i := instr.(type) {
   306  	case *ssa.Store:
   307  		b.addInFlowAliasEdges(b.nodeFromVal(i.Addr), b.nodeFromVal(i.Val))
   308  	case *ssa.MakeInterface:
   309  		b.addInFlowEdge(b.nodeFromVal(i.X), b.nodeFromVal(i))
   310  	case *ssa.MakeClosure:
   311  		b.closure(i)
   312  	case *ssa.UnOp:
   313  		b.unop(i)
   314  	case *ssa.Phi:
   315  		b.phi(i)
   316  	case *ssa.ChangeInterface:
   317  		// Although in change interface a := A(b) command a and b are
   318  		// the same object, the only interesting flow happens when A
   319  		// is an interface. We create flow b -> a, but omit a -> b.
   320  		// The latter flow is not needed: if a gets assigned concrete
   321  		// type later on, that cannot be propagated back to b as b
   322  		// is a separate variable. The a -> b flow can happen when
   323  		// A is a pointer to interface, but then the command is of
   324  		// type ChangeType, handled below.
   325  		b.addInFlowEdge(b.nodeFromVal(i.X), b.nodeFromVal(i))
   326  	case *ssa.ChangeType:
   327  		// change type command a := A(b) results in a and b being the
   328  		// same value. For concrete type A, there is no interesting flow.
   329  		//
   330  		// Note: When A is an interface, most interface casts are handled
   331  		// by the ChangeInterface instruction. The relevant case here is
   332  		// when converting a pointer to an interface type. This can happen
   333  		// when the underlying interfaces have the same method set.
   334  		//   type I interface{ foo() }
   335  		//   type J interface{ foo() }
   336  		//   var b *I
   337  		//   a := (*J)(b)
   338  		// When this happens we add flows between a <--> b.
   339  		b.addInFlowAliasEdges(b.nodeFromVal(i), b.nodeFromVal(i.X))
   340  	case *ssa.TypeAssert:
   341  		b.tassert(i)
   342  	case *ssa.Extract:
   343  		b.extract(i)
   344  	case *ssa.Field:
   345  		b.field(i)
   346  	case *ssa.FieldAddr:
   347  		b.fieldAddr(i)
   348  	case *ssa.Send:
   349  		b.send(i)
   350  	case *ssa.Select:
   351  		b.selekt(i)
   352  	case *ssa.Index:
   353  		b.index(i)
   354  	case *ssa.IndexAddr:
   355  		b.indexAddr(i)
   356  	case *ssa.Lookup:
   357  		b.lookup(i)
   358  	case *ssa.MapUpdate:
   359  		b.mapUpdate(i)
   360  	case *ssa.Next:
   361  		b.next(i)
   362  	case ssa.CallInstruction:
   363  		b.call(i)
   364  	case *ssa.Panic:
   365  		b.panic(i)
   366  	case *ssa.Return:
   367  		b.rtrn(i)
   368  	case *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeSlice, *ssa.BinOp,
   369  		*ssa.Alloc, *ssa.DebugRef, *ssa.Convert, *ssa.Jump, *ssa.If,
   370  		*ssa.Slice, *ssa.SliceToArrayPointer, *ssa.Range, *ssa.RunDefers:
   371  		// No interesting flow here.
   372  		// Notes on individual instructions:
   373  		// SliceToArrayPointer: t1 = slice to array pointer *[4]T <- []T (t0)
   374  		// No interesting flow as sliceArrayElem(t1) == sliceArrayElem(t0).
   375  		return
   376  	default:
   377  		panic(fmt.Sprintf("unsupported instruction %v\n", instr))
   378  	}
   379  }
   380  
   381  func (b *builder) unop(u *ssa.UnOp) {
   382  	switch u.Op {
   383  	case token.MUL:
   384  		// Multiplication operator * is used here as a dereference operator.
   385  		b.addInFlowAliasEdges(b.nodeFromVal(u), b.nodeFromVal(u.X))
   386  	case token.ARROW:
   387  		t := u.X.Type().Underlying().(*types.Chan).Elem()
   388  		b.addInFlowAliasEdges(b.nodeFromVal(u), channelElem{typ: t})
   389  	default:
   390  		// There is no interesting type flow otherwise.
   391  	}
   392  }
   393  
   394  func (b *builder) phi(p *ssa.Phi) {
   395  	for _, edge := range p.Edges {
   396  		b.addInFlowAliasEdges(b.nodeFromVal(p), b.nodeFromVal(edge))
   397  	}
   398  }
   399  
   400  func (b *builder) tassert(a *ssa.TypeAssert) {
   401  	if !a.CommaOk {
   402  		b.addInFlowEdge(b.nodeFromVal(a.X), b.nodeFromVal(a))
   403  		return
   404  	}
   405  	// The case where a is <a.AssertedType, bool> register so there
   406  	// is a flow from a.X to a[0]. Here, a[0] is represented as an
   407  	// indexedLocal: an entry into local tuple register a at index 0.
   408  	tup := a.Type().Underlying().(*types.Tuple)
   409  	t := tup.At(0).Type()
   410  
   411  	local := indexedLocal{val: a, typ: t, index: 0}
   412  	b.addInFlowEdge(b.nodeFromVal(a.X), local)
   413  }
   414  
   415  // extract instruction t1 := t2[i] generates flows between t2[i]
   416  // and t1 where the source is indexed local representing a value
   417  // from tuple register t2 at index i and the target is t1.
   418  func (b *builder) extract(e *ssa.Extract) {
   419  	tup := e.Tuple.Type().Underlying().(*types.Tuple)
   420  	t := tup.At(e.Index).Type()
   421  
   422  	local := indexedLocal{val: e.Tuple, typ: t, index: e.Index}
   423  	b.addInFlowAliasEdges(b.nodeFromVal(e), local)
   424  }
   425  
   426  func (b *builder) field(f *ssa.Field) {
   427  	fnode := field{StructType: f.X.Type(), index: f.Field}
   428  	b.addInFlowEdge(fnode, b.nodeFromVal(f))
   429  }
   430  
   431  func (b *builder) fieldAddr(f *ssa.FieldAddr) {
   432  	t := f.X.Type().Underlying().(*types.Pointer).Elem()
   433  
   434  	// Since we are getting pointer to a field, make a bidirectional edge.
   435  	fnode := field{StructType: t, index: f.Field}
   436  	b.addInFlowEdge(fnode, b.nodeFromVal(f))
   437  	b.addInFlowEdge(b.nodeFromVal(f), fnode)
   438  }
   439  
   440  func (b *builder) send(s *ssa.Send) {
   441  	t := s.Chan.Type().Underlying().(*types.Chan).Elem()
   442  	b.addInFlowAliasEdges(channelElem{typ: t}, b.nodeFromVal(s.X))
   443  }
   444  
   445  // selekt generates flows for select statement
   446  //
   447  //	a = select blocking/nonblocking [c_1 <- t_1, c_2 <- t_2, ..., <- o_1, <- o_2, ...]
   448  //
   449  // between receiving channel registers c_i and corresponding input register t_i. Further,
   450  // flows are generated between o_i and a[2 + i]. Note that a is a tuple register of type
   451  // <int, bool, r_1, r_2, ...> where the type of r_i is the element type of channel o_i.
   452  func (b *builder) selekt(s *ssa.Select) {
   453  	recvIndex := 0
   454  	for _, state := range s.States {
   455  		t := state.Chan.Type().Underlying().(*types.Chan).Elem()
   456  
   457  		if state.Dir == types.SendOnly {
   458  			b.addInFlowAliasEdges(channelElem{typ: t}, b.nodeFromVal(state.Send))
   459  		} else {
   460  			// state.Dir == RecvOnly by definition of select instructions.
   461  			tupEntry := indexedLocal{val: s, typ: t, index: 2 + recvIndex}
   462  			b.addInFlowAliasEdges(tupEntry, channelElem{typ: t})
   463  			recvIndex++
   464  		}
   465  	}
   466  }
   467  
   468  // index instruction a := b[c] on slices creates flows between a and
   469  // SliceElem(t) flow where t is an interface type of c. Arrays and
   470  // slice elements are both modeled as SliceElem.
   471  func (b *builder) index(i *ssa.Index) {
   472  	et := sliceArrayElem(i.X.Type())
   473  	b.addInFlowAliasEdges(b.nodeFromVal(i), sliceElem{typ: et})
   474  }
   475  
   476  // indexAddr instruction a := &b[c] fetches address of a index
   477  // into the field so we create bidirectional flow a <-> SliceElem(t)
   478  // where t is an interface type of c. Arrays and slice elements are
   479  // both modeled as SliceElem.
   480  func (b *builder) indexAddr(i *ssa.IndexAddr) {
   481  	et := sliceArrayElem(i.X.Type())
   482  	b.addInFlowEdge(sliceElem{typ: et}, b.nodeFromVal(i))
   483  	b.addInFlowEdge(b.nodeFromVal(i), sliceElem{typ: et})
   484  }
   485  
   486  // lookup handles map query commands a := m[b] where m is of type
   487  // map[...]V and V is an interface. It creates flows between `a`
   488  // and MapValue(V).
   489  func (b *builder) lookup(l *ssa.Lookup) {
   490  	t, ok := l.X.Type().Underlying().(*types.Map)
   491  	if !ok {
   492  		// No interesting flows for string lookups.
   493  		return
   494  	}
   495  	b.addInFlowAliasEdges(b.nodeFromVal(l), mapValue{typ: t.Elem()})
   496  }
   497  
   498  // mapUpdate handles map update commands m[b] = a where m is of type
   499  // map[K]V and K and V are interfaces. It creates flows between `a`
   500  // and MapValue(V) as well as between MapKey(K) and `b`.
   501  func (b *builder) mapUpdate(u *ssa.MapUpdate) {
   502  	t, ok := u.Map.Type().Underlying().(*types.Map)
   503  	if !ok {
   504  		// No interesting flows for string updates.
   505  		return
   506  	}
   507  
   508  	b.addInFlowAliasEdges(mapKey{typ: t.Key()}, b.nodeFromVal(u.Key))
   509  	b.addInFlowAliasEdges(mapValue{typ: t.Elem()}, b.nodeFromVal(u.Value))
   510  }
   511  
   512  // next instruction <ok, key, value> := next r, where r
   513  // is a range over map or string generates flow between
   514  // key and MapKey as well value and MapValue nodes.
   515  func (b *builder) next(n *ssa.Next) {
   516  	if n.IsString {
   517  		return
   518  	}
   519  	tup := n.Type().Underlying().(*types.Tuple)
   520  	kt := tup.At(1).Type()
   521  	vt := tup.At(2).Type()
   522  
   523  	b.addInFlowAliasEdges(indexedLocal{val: n, typ: kt, index: 1}, mapKey{typ: kt})
   524  	b.addInFlowAliasEdges(indexedLocal{val: n, typ: vt, index: 2}, mapValue{typ: vt})
   525  }
   526  
   527  // addInFlowAliasEdges adds an edge r -> l to b.graph if l is a node that can
   528  // have an inflow, i.e., a node that represents an interface or an unresolved
   529  // function value. Similarly for the edge l -> r with an additional condition
   530  // of that l and r can potentially alias.
   531  func (b *builder) addInFlowAliasEdges(l, r node) {
   532  	b.addInFlowEdge(r, l)
   533  
   534  	if canAlias(l, r) {
   535  		b.addInFlowEdge(l, r)
   536  	}
   537  }
   538  
   539  func (b *builder) closure(c *ssa.MakeClosure) {
   540  	f := c.Fn.(*ssa.Function)
   541  	b.addInFlowEdge(function{f: f}, b.nodeFromVal(c))
   542  
   543  	for i, fv := range f.FreeVars {
   544  		b.addInFlowAliasEdges(b.nodeFromVal(fv), b.nodeFromVal(c.Bindings[i]))
   545  	}
   546  }
   547  
   548  // panic creates a flow from arguments to panic instructions to return
   549  // registers of all recover statements in the program. Introduces a
   550  // global panic node Panic and
   551  //  1. for every panic statement p: add p -> Panic
   552  //  2. for every recover statement r: add Panic -> r (handled in call)
   553  //
   554  // TODO(zpavlinovic): improve precision by explicitly modeling how panic
   555  // values flow from callees to callers and into deferred recover instructions.
   556  func (b *builder) panic(p *ssa.Panic) {
   557  	// Panics often have, for instance, strings as arguments which do
   558  	// not create interesting flows.
   559  	if !canHaveMethods(p.X.Type()) {
   560  		return
   561  	}
   562  
   563  	b.addInFlowEdge(b.nodeFromVal(p.X), panicArg{})
   564  }
   565  
   566  // call adds flows between arguments/parameters and return values/registers
   567  // for both static and dynamic calls, as well as go and defer calls.
   568  func (b *builder) call(c ssa.CallInstruction) {
   569  	// When c is r := recover() call register instruction, we add Recover -> r.
   570  	if bf, ok := c.Common().Value.(*ssa.Builtin); ok && bf.Name() == "recover" {
   571  		if v, ok := c.(ssa.Value); ok {
   572  			b.addInFlowEdge(recoverReturn{}, b.nodeFromVal(v))
   573  		}
   574  		return
   575  	}
   576  
   577  	for _, f := range siteCallees(c, b.callGraph) {
   578  		addArgumentFlows(b, c, f)
   579  	}
   580  }
   581  
   582  func addArgumentFlows(b *builder, c ssa.CallInstruction, f *ssa.Function) {
   583  	// When f has no paremeters (including receiver), there is no type
   584  	// flow here. Also, f's body and parameters might be missing, such
   585  	// as when vta is used within the golang.org/x/tools/go/analysis
   586  	// framework (see github.com/golang/go/issues/50670).
   587  	if len(f.Params) == 0 {
   588  		return
   589  	}
   590  	cc := c.Common()
   591  
   592  	offset := 0
   593  	if cc.Method != nil {
   594  		// We don't add interprocedural flows for receiver objects.
   595  		// At a call site, the receiver object is interface while the
   596  		// callee object is concrete. The flow from interface to
   597  		// concrete type does not make sense. The flow other way around
   598  		// would bake in information from the initial call graph.
   599  		offset = 1
   600  	}
   601  	for i, v := range cc.Args {
   602  		// Parameters of f might not be available, as in the case
   603  		// when vta is used within the golang.org/x/tools/go/analysis
   604  		// framework (see github.com/golang/go/issues/50670).
   605  		//
   606  		// TODO: investigate other cases of missing body and parameters
   607  		if len(f.Params) <= i+offset {
   608  			return
   609  		}
   610  		b.addInFlowAliasEdges(b.nodeFromVal(f.Params[i+offset]), b.nodeFromVal(v))
   611  	}
   612  }
   613  
   614  // rtrn produces flows between values of r and c where
   615  // c is a call instruction that resolves to the enclosing
   616  // function of r based on b.callGraph.
   617  func (b *builder) rtrn(r *ssa.Return) {
   618  	n := b.callGraph.Nodes[r.Parent()]
   619  	// n != nil when b.callgraph is sound, but the client can
   620  	// pass any callgraph, including an underapproximate one.
   621  	if n == nil {
   622  		return
   623  	}
   624  
   625  	for _, e := range n.In {
   626  		if cv, ok := e.Site.(ssa.Value); ok {
   627  			addReturnFlows(b, r, cv)
   628  		}
   629  	}
   630  }
   631  
   632  func addReturnFlows(b *builder, r *ssa.Return, site ssa.Value) {
   633  	results := r.Results
   634  	if len(results) == 1 {
   635  		// When there is only one return value, the destination register does not
   636  		// have a tuple type.
   637  		b.addInFlowEdge(b.nodeFromVal(results[0]), b.nodeFromVal(site))
   638  		return
   639  	}
   640  
   641  	tup := site.Type().Underlying().(*types.Tuple)
   642  	for i, r := range results {
   643  		local := indexedLocal{val: site, typ: tup.At(i).Type(), index: i}
   644  		b.addInFlowEdge(b.nodeFromVal(r), local)
   645  	}
   646  }
   647  
   648  // addInFlowEdge adds s -> d to g if d is node that can have an inflow, i.e., a node
   649  // that represents an interface or an unresolved function value. Otherwise, there
   650  // is no interesting type flow so the edge is omitted.
   651  func (b *builder) addInFlowEdge(s, d node) {
   652  	if hasInFlow(d) {
   653  		b.graph.addEdge(b.representative(s), b.representative(d))
   654  	}
   655  }
   656  
   657  // Creates const, pointer, global, func, and local nodes based on register instructions.
   658  func (b *builder) nodeFromVal(val ssa.Value) node {
   659  	if p, ok := val.Type().(*types.Pointer); ok && !types.IsInterface(p.Elem()) && !isFunction(p.Elem()) {
   660  		// Nested pointer to interfaces are modeled as a special
   661  		// nestedPtrInterface node.
   662  		if i := interfaceUnderPtr(p.Elem()); i != nil {
   663  			return nestedPtrInterface{typ: i}
   664  		}
   665  		// The same goes for nested function types.
   666  		if f := functionUnderPtr(p.Elem()); f != nil {
   667  			return nestedPtrFunction{typ: f}
   668  		}
   669  		return pointer{typ: p}
   670  	}
   671  
   672  	switch v := val.(type) {
   673  	case *ssa.Const:
   674  		return constant{typ: val.Type()}
   675  	case *ssa.Global:
   676  		return global{val: v}
   677  	case *ssa.Function:
   678  		return function{f: v}
   679  	case *ssa.Parameter, *ssa.FreeVar, ssa.Instruction:
   680  		// ssa.Param, ssa.FreeVar, and a specific set of "register" instructions,
   681  		// satisifying the ssa.Value interface, can serve as local variables.
   682  		return local{val: v}
   683  	default:
   684  		panic(fmt.Errorf("unsupported value %v in node creation", val))
   685  	}
   686  }
   687  
   688  // representative returns a unique representative for node `n`. Since
   689  // semantically equivalent types can have different implementations,
   690  // this method guarantees the same implementation is always used.
   691  func (b *builder) representative(n node) node {
   692  	if n.Type() == nil {
   693  		// panicArg and recoverReturn do not have
   694  		// types and are unique by definition.
   695  		return n
   696  	}
   697  	t := canonicalize(n.Type(), &b.canon)
   698  
   699  	switch i := n.(type) {
   700  	case constant:
   701  		return constant{typ: t}
   702  	case pointer:
   703  		return pointer{typ: t.(*types.Pointer)}
   704  	case sliceElem:
   705  		return sliceElem{typ: t}
   706  	case mapKey:
   707  		return mapKey{typ: t}
   708  	case mapValue:
   709  		return mapValue{typ: t}
   710  	case channelElem:
   711  		return channelElem{typ: t}
   712  	case nestedPtrInterface:
   713  		return nestedPtrInterface{typ: t}
   714  	case nestedPtrFunction:
   715  		return nestedPtrFunction{typ: t}
   716  	case field:
   717  		return field{StructType: canonicalize(i.StructType, &b.canon), index: i.index}
   718  	case indexedLocal:
   719  		return indexedLocal{typ: t, val: i.val, index: i.index}
   720  	case local, global, panicArg, recoverReturn, function:
   721  		return n
   722  	default:
   723  		panic(fmt.Errorf("canonicalizing unrecognized node %v", n))
   724  	}
   725  }
   726  
   727  // canonicalize returns a type representative of `t` unique subject
   728  // to type map `canon`.
   729  func canonicalize(t types.Type, canon *typeutil.Map) types.Type {
   730  	rep := canon.At(t)
   731  	if rep != nil {
   732  		return rep.(types.Type)
   733  	}
   734  	canon.Set(t, t)
   735  	return t
   736  }
   737
View as plain text