| 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 |
Members