Recursively re-instantiate the expression, while applying all of the
    given `rules` to all encountered (sub-) expressions

    Args:
        expr:  Any Expression or scalar object
        rules (list, ~collections.OrderedDict): A list of rules dictionary
            mapping names to rules, where each rule is a tuple ``(pattern,
            replacement)`` where `pattern` is an instance of :class:`.Pattern`)
            and `replacement` is a callable. The pattern will be matched
            against any expression that is encountered during the
            re-instantiation. If the `pattern` matches, then the
            (sub-)expression is replaced by the result of calling `replacement`
            while passing any wildcards from `pattern` as keyword arguments. If
            `replacement` raises :exc:`.CannotSimplify`, it will be ignored

    Note:
        Instead of or in addition to passing `rules`, `simplify` can often be
        combined with e.g. `extra_rules` / `extra_binary_rules` context
        managers. If a simplification can be handled through these context
        managers, this is usually more efficient than an equivalent rule.
        However, both really are complementary: the rules defined in the
        context managers are applied *before* instantiation (hence these these
        patterns are instantiated through `pattern_head`). In contrast, the
        patterns defined in `rules` are applied against instantiated
        expressions.

def _apply_rules(expr, rules):
    """Recursively re-instantiate the expression, while applying all of the
    given `rules` to all encountered (sub-) expressions

    Args:
        expr:  Any Expression or scalar object
        rules (list, ~collections.OrderedDict): A list of rules dictionary
            mapping names to rules, where each rule is a tuple ``(pattern,
            replacement)`` where `pattern` is an instance of :class:`.Pattern`)
            and `replacement` is a callable. The pattern will be matched
            against any expression that is encountered during the
            re-instantiation. If the `pattern` matches, then the
            (sub-)expression is replaced by the result of calling `replacement`
            while passing any wildcards from `pattern` as keyword arguments. If
            `replacement` raises :exc:`.CannotSimplify`, it will be ignored

    Note:
        Instead of or in addition to passing `rules`, `simplify` can often be
        combined with e.g. `extra_rules` / `extra_binary_rules` context
        managers. If a simplification can be handled through these context
        managers, this is usually more efficient than an equivalent rule.
        However, both really are complementary: the rules defined in the
        context managers are applied *before* instantiation (hence these these
        patterns are instantiated through `pattern_head`). In contrast, the
        patterns defined in `rules` are applied against instantiated
        expressions.
    """
    if LOG:
        logger = logging.getLogger('QNET.create')
    stack = []
    path = []
    if isinstance(expr, Expression):
        stack.append(ProtoExpr.from_expr(expr))
        path.append(0)
        if LOG:
            logger.debug(
                "Starting at level 1: placing expr on stack: %s", expr)
        while True:
            i = path[-1]
            try:
                arg = stack[-1][i]
                if LOG:
                    logger.debug(
                        "At level %d: considering arg %d: %s",
                        len(stack), i+1, arg)
            except IndexError:
                # done at this level
                path.pop()
                expr = stack.pop().instantiate()
                expr = _apply_rules_no_recurse(expr, rules)
                if len(stack) == 0:
                    if LOG:
                        logger.debug(
                            "Complete level 1: returning simplified expr: %s",
                            expr)
                    return expr
                else:
                    stack[-1][path[-1]] = expr
                    path[-1] += 1
                    if LOG:
                        logger.debug(
                            "Complete level %d. At level %d, setting arg %d "
                            "to simplified expr: %s", len(stack)+1, len(stack),
                            path[-1], expr)
            else:
                if isinstance(arg, Expression):
                    stack.append(ProtoExpr.from_expr(arg))
                    path.append(0)
                    if LOG:
                        logger.debug("   placing arg on stack")
                else:  # scalar
                    stack[-1][i] = _apply_rules_no_recurse(arg, rules)
                    if LOG:
                        logger.debug(
                            "   arg is leaf, replacing with simplified expr: "
                            "%s", stack[-1][i])
                    path[-1] += 1
    else:
        return _apply_rules_no_recurse(expr, rules)