propagation.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/vta/internal/trie"
    11  	"golang.org/x/tools/go/ssa"
    12  
    13  	"golang.org/x/tools/go/types/typeutil"
    14  )
    15  
    16  // scc computes strongly connected components (SCCs) of `g` using the
    17  // classical Tarjan's algorithm for SCCs. The result is a pair <m, id>
    18  // where m is a map from nodes to unique id of their SCC in the range
    19  // [0, id). The SCCs are sorted in reverse topological order: for SCCs
    20  // with ids X and Y s.t. X < Y, Y comes before X in the topological order.
    21  func scc(g vtaGraph) (map[node]int, int) {
    22  	// standard data structures used by Tarjan's algorithm.
    23  	var index uint64
    24  	var stack []node
    25  	indexMap := make(map[node]uint64)
    26  	lowLink := make(map[node]uint64)
    27  	onStack := make(map[node]bool)
    28  
    29  	nodeToSccID := make(map[node]int)
    30  	sccID := 0
    31  
    32  	var doSCC func(node)
    33  	doSCC = func(n node) {
    34  		indexMap[n] = index
    35  		lowLink[n] = index
    36  		index = index + 1
    37  		onStack[n] = true
    38  		stack = append(stack, n)
    39  
    40  		for s := range g[n] {
    41  			if _, ok := indexMap[s]; !ok {
    42  				// Analyze successor s that has not been visited yet.
    43  				doSCC(s)
    44  				lowLink[n] = min(lowLink[n], lowLink[s])
    45  			} else if onStack[s] {
    46  				// The successor is on the stack, meaning it has to be
    47  				// in the current SCC.
    48  				lowLink[n] = min(lowLink[n], indexMap[s])
    49  			}
    50  		}
    51  
    52  		// if n is a root node, pop the stack and generate a new SCC.
    53  		if lowLink[n] == indexMap[n] {
    54  			for {
    55  				w := stack[len(stack)-1]
    56  				stack = stack[:len(stack)-1]
    57  				onStack[w] = false
    58  				nodeToSccID[w] = sccID
    59  				if w == n {
    60  					break
    61  				}
    62  			}
    63  			sccID++
    64  		}
    65  	}
    66  
    67  	index = 0
    68  	for n := range g {
    69  		if _, ok := indexMap[n]; !ok {
    70  			doSCC(n)
    71  		}
    72  	}
    73  
    74  	return nodeToSccID, sccID
    75  }
    76  
    77  func min(x, y uint64) uint64 {
    78  	if x < y {
    79  		return x
    80  	}
    81  	return y
    82  }
    83  
    84  // propType represents type information being propagated
    85  // over the vta graph. f != nil only for function nodes
    86  // and nodes reachable from function nodes. There, we also
    87  // remember the actual *ssa.Function in order to more
    88  // precisely model higher-order flow.
    89  type propType struct {
    90  	typ types.Type
    91  	f   *ssa.Function
    92  }
    93  
    94  // propTypeMap is an auxiliary structure that serves
    95  // the role of a map from nodes to a set of propTypes.
    96  type propTypeMap struct {
    97  	nodeToScc  map[node]int
    98  	sccToTypes map[int]*trie.MutMap
    99  }
   100  
   101  // propTypes returns a list of propTypes associated with
   102  // node `n`. If `n` is not in the map `ptm`, nil is returned.
   103  func (ptm propTypeMap) propTypes(n node) []propType {
   104  	id, ok := ptm.nodeToScc[n]
   105  	if !ok {
   106  		return nil
   107  	}
   108  	var pts []propType
   109  	for _, elem := range trie.Elems(ptm.sccToTypes[id].M) {
   110  		pts = append(pts, elem.(propType))
   111  	}
   112  	return pts
   113  }
   114  
   115  // propagate reduces the `graph` based on its SCCs and
   116  // then propagates type information through the reduced
   117  // graph. The result is a map from nodes to a set of types
   118  // and functions, stemming from higher-order data flow,
   119  // reaching the node. `canon` is used for type uniqueness.
   120  func propagate(graph vtaGraph, canon *typeutil.Map) propTypeMap {
   121  	nodeToScc, sccID := scc(graph)
   122  
   123  	// We also need the reverse map, from ids to SCCs.
   124  	sccs := make(map[int][]node, sccID)
   125  	for n, id := range nodeToScc {
   126  		sccs[id] = append(sccs[id], n)
   127  	}
   128  
   129  	// propTypeIds are used to create unique ids for
   130  	// propType, to be used for trie-based type sets.
   131  	propTypeIds := make(map[propType]uint64)
   132  	// Id creation is based on == equality, which works
   133  	// as types are canonicalized (see getPropType).
   134  	propTypeId := func(p propType) uint64 {
   135  		if id, ok := propTypeIds[p]; ok {
   136  			return id
   137  		}
   138  		id := uint64(len(propTypeIds))
   139  		propTypeIds[p] = id
   140  		return id
   141  	}
   142  	builder := trie.NewBuilder()
   143  	// Initialize sccToTypes to avoid repeated check
   144  	// for initialization later.
   145  	sccToTypes := make(map[int]*trie.MutMap, sccID)
   146  	for i := 0; i <= sccID; i++ {
   147  		sccToTypes[i] = nodeTypes(sccs[i], builder, propTypeId, canon)
   148  	}
   149  
   150  	for i := len(sccs) - 1; i >= 0; i-- {
   151  		nextSccs := make(map[int]struct{})
   152  		for _, node := range sccs[i] {
   153  			for succ := range graph[node] {
   154  				nextSccs[nodeToScc[succ]] = struct{}{}
   155  			}
   156  		}
   157  		// Propagate types to all successor SCCs.
   158  		for nextScc := range nextSccs {
   159  			sccToTypes[nextScc].Merge(sccToTypes[i].M)
   160  		}
   161  	}
   162  	return propTypeMap{nodeToScc: nodeToScc, sccToTypes: sccToTypes}
   163  }
   164  
   165  // nodeTypes returns a set of propTypes for `nodes`. These are the
   166  // propTypes stemming from the type of each node in `nodes` plus.
   167  func nodeTypes(nodes []node, builder *trie.Builder, propTypeId func(p propType) uint64, canon *typeutil.Map) *trie.MutMap {
   168  	typeSet := builder.MutEmpty()
   169  	for _, n := range nodes {
   170  		if hasInitialTypes(n) {
   171  			pt := getPropType(n, canon)
   172  			typeSet.Update(propTypeId(pt), pt)
   173  		}
   174  	}
   175  	return &typeSet
   176  }
   177  
   178  // hasInitialTypes check if a node can have initial types.
   179  // Returns true iff `n` is not a panic, recover, nestedPtr*
   180  // node, nor a node whose type is an interface.
   181  func hasInitialTypes(n node) bool {
   182  	switch n.(type) {
   183  	case panicArg, recoverReturn, nestedPtrFunction, nestedPtrInterface:
   184  		return false
   185  	default:
   186  		return !types.IsInterface(n.Type())
   187  	}
   188  }
   189  
   190  // getPropType creates a propType for `node` based on its type.
   191  // propType.typ is always node.Type(). If node is function, then
   192  // propType.val is the underlying function; nil otherwise.
   193  func getPropType(node node, canon *typeutil.Map) propType {
   194  	t := canonicalize(node.Type(), canon)
   195  	if fn, ok := node.(function); ok {
   196  		return propType{f: fn.f, typ: t}
   197  	}
   198  	return propType{f: nil, typ: t}
   199  }
   200
View as plain text