apply_rule.py

def find_matching_node(expr, matching_fn, parent_node=None, parent_rel=None):
      if isinstance(expr, Expression) and matching_fn(expr):
            return (expr, parent_node, parent_rel)
      
      if isinstance(expr, Term):
            return
                
      left_match = find_matching_node(expr.left, parent_node=expr, parent_rel='left')
      right_match = find_matching_node(expr.right, parent_node=expr, parent_rel='right')
      if left_match:
            return left_match
      elif right_match:
            return right_match
      else:
            return False
            
def apply_rule(expr, rewrite_rule, matching_fn):
      """
      Recursively apply rule until it can't be applied any more.
      """
      try:
          found_node, found_parent_node, found_parent_rel = find_matching_node(expr, matching_fn)
      except:
          # found_node = find_matching_node(expr, matching_fn)                                 
          return expr
                                      
      if found_parent_node is None:                                                   
          return rewrite_rule(found_node)                                             
      else:                                                                           
          set_attr(found_parent_node, found_parent_rel, rewrite_rule(found_node))  
          return apply_rule(expr, rerwrite_rule, matching_fn)