visit.go

     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  // DoChildrenWithHidden is like DoChildren, but also visits
    98  // Node-typed fields tagged with `mknode:"-"`.
    99  //
   100  // TODO(mdempsky): Remove the `mknode:"-"` tags so this function can
   101  // go away.
   102  func DoChildrenWithHidden(n Node, do func(Node) bool) bool {
   103  	if n == nil {
   104  		return false
   105  	}
   106  	return n.doChildrenWithHidden(do)
   107  }
   108  
   109  // Visit visits each non-nil node x in the IR tree rooted at n
   110  // in a depth-first preorder traversal, calling visit on each node visited.
   111  func Visit(n Node, visit func(Node)) {
   112  	if n == nil {
   113  		return
   114  	}
   115  	var do func(Node) bool
   116  	do = func(x Node) bool {
   117  		visit(x)
   118  		return DoChildren(x, do)
   119  	}
   120  	do(n)
   121  }
   122  
   123  // VisitList calls Visit(x, visit) for each node x in the list.
   124  func VisitList(list Nodes, visit func(Node)) {
   125  	for _, x := range list {
   126  		Visit(x, visit)
   127  	}
   128  }
   129  
   130  // VisitFuncAndClosures calls visit on each non-nil node in fn.Body,
   131  // including any nested closure bodies.
   132  func VisitFuncAndClosures(fn *Func, visit func(n Node)) {
   133  	VisitList(fn.Body, func(n Node) {
   134  		visit(n)
   135  		if n, ok := n.(*ClosureExpr); ok && n.Op() == OCLOSURE {
   136  			VisitFuncAndClosures(n.Func, visit)
   137  		}
   138  	})
   139  }
   140  
   141  // Any looks for a non-nil node x in the IR tree rooted at n
   142  // for which cond(x) returns true.
   143  // Any considers nodes in a depth-first, preorder traversal.
   144  // When Any finds a node x such that cond(x) is true,
   145  // Any ends the traversal and returns true immediately.
   146  // Otherwise Any returns false after completing the entire traversal.
   147  func Any(n Node, cond func(Node) bool) bool {
   148  	if n == nil {
   149  		return false
   150  	}
   151  	var do func(Node) bool
   152  	do = func(x Node) bool {
   153  		return cond(x) || DoChildren(x, do)
   154  	}
   155  	return do(n)
   156  }
   157  
   158  // AnyList calls Any(x, cond) for each node x in the list, in order.
   159  // If any call returns true, AnyList stops and returns true.
   160  // Otherwise, AnyList returns false after calling Any(x, cond)
   161  // for every x in the list.
   162  func AnyList(list Nodes, cond func(Node) bool) bool {
   163  	for _, x := range list {
   164  		if Any(x, cond) {
   165  			return true
   166  		}
   167  	}
   168  	return false
   169  }
   170  
   171  // EditChildren edits the child nodes of n, replacing each child x with edit(x).
   172  //
   173  // Note that EditChildren(n, edit) only calls edit(x) for n's immediate children.
   174  // If x's children should be processed, then edit(x) must call EditChildren(x, edit).
   175  //
   176  // EditChildren allows constructing general editing passes of the IR graph.
   177  // The most general usage is:
   178  //
   179  //	var edit func(ir.Node) ir.Node
   180  //	edit = func(x ir.Node) ir.Node {
   181  //		... processing BEFORE editing children ...
   182  //		if ... should edit children ... {
   183  //			EditChildren(x, edit)
   184  //			... processing AFTER editing children ...
   185  //		}
   186  //		... return x ...
   187  //	}
   188  //	n = edit(n)
   189  //
   190  // EditChildren edits the node in place. To edit a copy, call Copy first.
   191  // As an example, a simple deep copy implementation would be:
   192  //
   193  //	func deepCopy(n ir.Node) ir.Node {
   194  //		var edit func(ir.Node) ir.Node
   195  //		edit = func(x ir.Node) ir.Node {
   196  //			x = ir.Copy(x)
   197  //			ir.EditChildren(x, edit)
   198  //			return x
   199  //		}
   200  //		return edit(n)
   201  //	}
   202  //
   203  // Of course, in this case it is better to call ir.DeepCopy than to build one anew.
   204  func EditChildren(n Node, edit func(Node) Node) {
   205  	if n == nil {
   206  		return
   207  	}
   208  	n.editChildren(edit)
   209  }
   210  
   211  // EditChildrenWithHidden is like EditChildren, but also edits
   212  // Node-typed fields tagged with `mknode:"-"`.
   213  //
   214  // TODO(mdempsky): Remove the `mknode:"-"` tags so this function can
   215  // go away.
   216  func EditChildrenWithHidden(n Node, edit func(Node) Node) {
   217  	if n == nil {
   218  		return
   219  	}
   220  	n.editChildrenWithHidden(edit)
   221  }
   222
View as plain text