utils.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  	"go/types"
     9  
    10  	"golang.org/x/tools/go/callgraph"
    11  	"golang.org/x/tools/go/ssa"
    12  	"golang.org/x/tools/internal/aliases"
    13  	"golang.org/x/tools/internal/typeparams"
    14  )
    15  
    16  func canAlias(n1, n2 node) bool {
    17  	return isReferenceNode(n1) && isReferenceNode(n2)
    18  }
    19  
    20  func isReferenceNode(n node) bool {
    21  	if _, ok := n.(nestedPtrInterface); ok {
    22  		return true
    23  	}
    24  	if _, ok := n.(nestedPtrFunction); ok {
    25  		return true
    26  	}
    27  
    28  	if _, ok := aliases.Unalias(n.Type()).(*types.Pointer); ok {
    29  		return true
    30  	}
    31  
    32  	return false
    33  }
    34  
    35  // hasInFlow checks if a concrete type can flow to node `n`.
    36  // Returns yes iff the type of `n` satisfies one the following:
    37  //  1. is an interface
    38  //  2. is a (nested) pointer to interface (needed for, say,
    39  //     slice elements of nested pointers to interface type)
    40  //  3. is a function type (needed for higher-order type flow)
    41  //  4. is a (nested) pointer to function (needed for, say,
    42  //     slice elements of nested pointers to function type)
    43  //  5. is a global Recover or Panic node
    44  func hasInFlow(n node) bool {
    45  	if _, ok := n.(panicArg); ok {
    46  		return true
    47  	}
    48  	if _, ok := n.(recoverReturn); ok {
    49  		return true
    50  	}
    51  
    52  	t := n.Type()
    53  
    54  	if i := interfaceUnderPtr(t); i != nil {
    55  		return true
    56  	}
    57  	if f := functionUnderPtr(t); f != nil {
    58  		return true
    59  	}
    60  
    61  	return types.IsInterface(t) || isFunction(t)
    62  }
    63  
    64  func isFunction(t types.Type) bool {
    65  	_, ok := t.Underlying().(*types.Signature)
    66  	return ok
    67  }
    68  
    69  // interfaceUnderPtr checks if type `t` is a potentially nested
    70  // pointer to interface and if yes, returns the interface type.
    71  // Otherwise, returns nil.
    72  func interfaceUnderPtr(t types.Type) types.Type {
    73  	seen := make(map[types.Type]bool)
    74  	var visit func(types.Type) types.Type
    75  	visit = func(t types.Type) types.Type {
    76  		if seen[t] {
    77  			return nil
    78  		}
    79  		seen[t] = true
    80  
    81  		p, ok := t.Underlying().(*types.Pointer)
    82  		if !ok {
    83  			return nil
    84  		}
    85  
    86  		if types.IsInterface(p.Elem()) {
    87  			return p.Elem()
    88  		}
    89  
    90  		return visit(p.Elem())
    91  	}
    92  	return visit(t)
    93  }
    94  
    95  // functionUnderPtr checks if type `t` is a potentially nested
    96  // pointer to function type and if yes, returns the function type.
    97  // Otherwise, returns nil.
    98  func functionUnderPtr(t types.Type) types.Type {
    99  	seen := make(map[types.Type]bool)
   100  	var visit func(types.Type) types.Type
   101  	visit = func(t types.Type) types.Type {
   102  		if seen[t] {
   103  			return nil
   104  		}
   105  		seen[t] = true
   106  
   107  		p, ok := t.Underlying().(*types.Pointer)
   108  		if !ok {
   109  			return nil
   110  		}
   111  
   112  		if isFunction(p.Elem()) {
   113  			return p.Elem()
   114  		}
   115  
   116  		return visit(p.Elem())
   117  	}
   118  	return visit(t)
   119  }
   120  
   121  // sliceArrayElem returns the element type of type `t` that is
   122  // expected to be a (pointer to) array, slice or string, consistent with
   123  // the ssa.Index and ssa.IndexAddr instructions. Panics otherwise.
   124  func sliceArrayElem(t types.Type) types.Type {
   125  	switch u := t.Underlying().(type) {
   126  	case *types.Pointer:
   127  		switch e := u.Elem().Underlying().(type) {
   128  		case *types.Array:
   129  			return e.Elem()
   130  		case *types.Interface:
   131  			return sliceArrayElem(e) // e is a type param with matching element types.
   132  		default:
   133  			panic(t)
   134  		}
   135  	case *types.Array:
   136  		return u.Elem()
   137  	case *types.Slice:
   138  		return u.Elem()
   139  	case *types.Basic:
   140  		return types.Typ[types.Byte]
   141  	case *types.Interface: // type param.
   142  		terms, err := typeparams.InterfaceTermSet(u)
   143  		if err != nil || len(terms) == 0 {
   144  			panic(t)
   145  		}
   146  		return sliceArrayElem(terms[0].Type()) // Element types must match.
   147  	default:
   148  		panic(t)
   149  	}
   150  }
   151  
   152  // siteCallees computes a set of callees for call site `c` given program `callgraph`.
   153  func siteCallees(c ssa.CallInstruction, callgraph *callgraph.Graph) []*ssa.Function {
   154  	var matches []*ssa.Function
   155  
   156  	node := callgraph.Nodes[c.Parent()]
   157  	if node == nil {
   158  		return nil
   159  	}
   160  
   161  	for _, edge := range node.Out {
   162  		if edge.Site == c {
   163  			matches = append(matches, edge.Callee.Func)
   164  		}
   165  	}
   166  	return matches
   167  }
   168  
   169  func canHaveMethods(t types.Type) bool {
   170  	t = aliases.Unalias(t)
   171  	if _, ok := t.(*types.Named); ok {
   172  		return true
   173  	}
   174  
   175  	u := t.Underlying()
   176  	switch u.(type) {
   177  	case *types.Interface, *types.Signature, *types.Struct:
   178  		return true
   179  	default:
   180  		return false
   181  	}
   182  }
   183  
   184  // calls returns the set of call instructions in `f`.
   185  func calls(f *ssa.Function) []ssa.CallInstruction {
   186  	var calls []ssa.CallInstruction
   187  	for _, bl := range f.Blocks {
   188  		for _, instr := range bl.Instrs {
   189  			if c, ok := instr.(ssa.CallInstruction); ok {
   190  				calls = append(calls, c)
   191  			}
   192  		}
   193  	}
   194  	return calls
   195  }
   196  
   197  // intersect produces an intersection of functions in `fs1` and `fs2`.
   198  func intersect(fs1, fs2 []*ssa.Function) []*ssa.Function {
   199  	m := make(map[*ssa.Function]bool)
   200  	for _, f := range fs1 {
   201  		m[f] = true
   202  	}
   203  
   204  	var res []*ssa.Function
   205  	for _, f := range fs2 {
   206  		if m[f] {
   207  			res = append(res, f)
   208  		}
   209  	}
   210  	return res
   211  }
   212
View as plain text