1 // Copyright 2020 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 // IR visitors for walking the IR tree. 6 // 7 // The lowest level helpers are DoChildren and EditChildren, which 8 // nodes help implement and provide control over whether and when 9 // recursion happens during the walk of the IR. 10 // 11 // Although these are both useful directly, two simpler patterns 12 // are fairly common and also provided: Visit and Any. 13 14 package ir 15 16 // DoChildren calls do(x) on each of n's non-nil child nodes x. 17 // If any call returns true, DoChildren stops and returns true. 18 // Otherwise, DoChildren returns false. 19 // 20 // Note that DoChildren(n, do) only calls do(x) for n's immediate children. 21 // If x's children should be processed, then do(x) must call DoChildren(x, do). 22 // 23 // DoChildren allows constructing general traversals of the IR graph 24 // that can stop early if needed. The most general usage is: 25 // 26 // var do func(ir.Node) bool 27 // do = func(x ir.Node) bool { 28 // ... processing BEFORE visiting children ... 29 // if ... should visit children ... { 30 // ir.DoChildren(x, do) 31 // ... processing AFTER visiting children ... 32 // } 33 // if ... should stop parent DoChildren call from visiting siblings ... { 34 // return true 35 // } 36 // return false 37 // } 38 // do(root) 39 // 40 // Since DoChildren does not return true itself, if the do function 41 // never wants to stop the traversal, it can assume that DoChildren 42 // itself will always return false, simplifying to: 43 // 44 // var do func(ir.Node) bool 45 // do = func(x ir.Node) bool { 46 // ... processing BEFORE visiting children ... 47 // if ... should visit children ... { 48 // ir.DoChildren(x, do) 49 // } 50 // ... processing AFTER visiting children ... 51 // return false 52 // } 53 // do(root) 54 // 55 // The Visit function illustrates a further simplification of the pattern, 56 // only processing before visiting children and never stopping: 57 // 58 // func Visit(n ir.Node, visit func(ir.Node)) { 59 // if n == nil { 60 // return 61 // } 62 // var do func(ir.Node) bool 63 // do = func(x ir.Node) bool { 64 // visit(x) 65 // return ir.DoChildren(x, do) 66 // } 67 // do(n) 68 // } 69 // 70 // The Any function illustrates a different simplification of the pattern, 71 // visiting each node and then its children, recursively, until finding 72 // a node x for which cond(x) returns true, at which point the entire 73 // traversal stops and returns true. 74 // 75 // func Any(n ir.Node, cond(ir.Node) bool) bool { 76 // if n == nil { 77 // return false 78 // } 79 // var do func(ir.Node) bool 80 // do = func(x ir.Node) bool { 81 // return cond(x) || ir.DoChildren(x, do) 82 // } 83 // return do(n) 84 // } 85 // 86 // Visit and Any are presented above as examples of how to use 87 // DoChildren effectively, but of course, usage that fits within the 88 // simplifications captured by Visit or Any will be best served 89 // by directly calling the ones provided by this package. 90 func DoChildren(n Node, do func(Node) bool) bool { 91 if n == nil { 92 return false 93 } 94 return n.doChildren(do) 95 } 96 97 // Visit visits each non-nil node x in the IR tree rooted at n 98 // in a depth-first preorder traversal, calling visit on each node visited. 99 func Visit(n Node, visit func(Node)) { 100 if n == nil { 101 return 102 } 103 var do func(Node) bool 104 do = func(x Node) bool { 105 visit(x) 106 return DoChildren(x, do) 107 } 108 do(n) 109 } 110 111 // VisitList calls Visit(x, visit) for each node x in the list. 112 func VisitList(list Nodes, visit func(Node)) { 113 for _, x := range list { 114 Visit(x, visit) 115 } 116 } 117 118 // VisitFuncAndClosures calls visit on each non-nil node in fn.Body, 119 // including any nested closure bodies. 120 func VisitFuncAndClosures(fn *Func, visit func(n Node)) { 121 VisitList(fn.Body, func(n Node) { 122 visit(n) 123 if n, ok := n.(*ClosureExpr); ok && n.Op() == OCLOSURE { 124 VisitFuncAndClosures(n.Func, visit) 125 } 126 }) 127 } 128 129 // Any looks for a non-nil node x in the IR tree rooted at n 130 // for which cond(x) returns true. 131 // Any considers nodes in a depth-first, preorder traversal. 132 // When Any finds a node x such that cond(x) is true, 133 // Any ends the traversal and returns true immediately. 134 // Otherwise Any returns false after completing the entire traversal. 135 func Any(n Node, cond func(Node) bool) bool { 136 if n == nil { 137 return false 138 } 139 var do func(Node) bool 140 do = func(x Node) bool { 141 return cond(x) || DoChildren(x, do) 142 } 143 return do(n) 144 } 145 146 // AnyList calls Any(x, cond) for each node x in the list, in order. 147 // If any call returns true, AnyList stops and returns true. 148 // Otherwise, AnyList returns false after calling Any(x, cond) 149 // for every x in the list. 150 func AnyList(list Nodes, cond func(Node) bool) bool { 151 for _, x := range list { 152 if Any(x, cond) { 153 return true 154 } 155 } 156 return false 157 } 158 159 // EditChildren edits the child nodes of n, replacing each child x with edit(x). 160 // 161 // Note that EditChildren(n, edit) only calls edit(x) for n's immediate children. 162 // If x's children should be processed, then edit(x) must call EditChildren(x, edit). 163 // 164 // EditChildren allows constructing general editing passes of the IR graph. 165 // The most general usage is: 166 // 167 // var edit func(ir.Node) ir.Node 168 // edit = func(x ir.Node) ir.Node { 169 // ... processing BEFORE editing children ... 170 // if ... should edit children ... { 171 // EditChildren(x, edit) 172 // ... processing AFTER editing children ... 173 // } 174 // ... return x ... 175 // } 176 // n = edit(n) 177 // 178 // EditChildren edits the node in place. To edit a copy, call Copy first. 179 // As an example, a simple deep copy implementation would be: 180 // 181 // func deepCopy(n ir.Node) ir.Node { 182 // var edit func(ir.Node) ir.Node 183 // edit = func(x ir.Node) ir.Node { 184 // x = ir.Copy(x) 185 // ir.EditChildren(x, edit) 186 // return x 187 // } 188 // return edit(n) 189 // } 190 // 191 // Of course, in this case it is better to call ir.DeepCopy than to build one anew. 192 func EditChildren(n Node, edit func(Node) Node) { 193 if n == nil { 194 return 195 } 196 n.editChildren(edit) 197 } 198 199 // EditChildrenWithHidden is like EditChildren, but also edits 200 // Node-typed fields tagged with `mknode:"-"`. 201 // 202 // TODO(mdempsky): Remove the `mknode:"-"` tags so this function can 203 // go away. 204 func EditChildrenWithHidden(n Node, edit func(Node) Node) { 205 if n == nil { 206 return 207 } 208 n.editChildrenWithHidden(edit) 209 } 210