Movimentum - Three basic algorithms: Expression replacement.

We want to replace a variable with a constant. Here is a visitor that can do a little more: Replace subexpressions with other expressions. We pass in a set of replacements, using a dictionary:

class RewritingVisitor :
        ISolverModelConstraintVisitor<AbstractConstraint>,
        ISolverModelExprVisitor<AbstractExpr> {
    private readonly IDictionary<AbstractExpr, AbstractExpr> _rewrites;

    public RewritingVisitor(
            IDictionary<AbstractExpr, AbstractExpr> rewrites) {
        _rewrites = rewrites;
    }

    // ...
}

For the three simple expressions—NamedVariables, AnchorVariables, and Constants—we return the replacement from the dictionary; or the original expression, if there is no replacement:

    private AbstractExpr RewriteSimpleExpr(AbstractExpr expr) {
        AbstractExpr result;
        return _rewrites.TryGetValue(expr, out result) ? result : expr;
    }

    public AbstractExpr Visit(Constant constant, Ignore p) {
        return RewriteSimpleExpr(constant);
    }

    public AbstractExpr Visit(NamedVariable namedVariable, Ignore p) {
        return RewriteSimpleExpr(namedVariable);
    }

    public AbstractExpr Visit(AnchorVariable anchorVariable, Ignore p) {
        return RewriteSimpleExpr(anchorVariable);
    }

The code for unary and binary epxressions looks somewhat similar to the constant folding visitor. But as we do not need any operator-specific behavior, it consists only of these two methods:

    public AbstractExpr Visit(UnaryExpression unaryExpression, Ignore p) {
        AbstractExpr result;
        if (_rewrites.TryGetValue(unaryExpression, out result)) {
            return result;
        } else {
            AbstractExpr oldInner = unaryExpression.Inner;
            AbstractExpr newInner = oldInner.Accept(this, Ig.nore);
            if (newInner != oldInner) {
                return new UnaryExpression(newInner, unaryExpression.Op);
            } else {
                return unaryExpression;
            }
        }
    }

    public AbstractExpr Visit(BinaryExpression binaryExpression, Ignore p) {
        AbstractExpr result;
        if (_rewrites.TryGetValue(binaryExpression, out result)) {
            return result;
        } else {
            AbstractExpr oldLhs = binaryExpression.Lhs;
            AbstractExpr oldRhs = binaryExpression.Rhs;
            AbstractExpr newLhs = oldLhs.Accept(this, Ig.nore);
            AbstractExpr newRhs = oldRhs.Accept(this, Ig.nore);
            if (newLhs != oldLhs | newRhs != oldRhs) {
                return new BinaryExpression(
                    newLhs, binaryExpression.Op, newRhs);
            } else {
                return binaryExpression;
            }
        }
    }

Oh yes—test cases. I forgot to present them here. But I wrote a few of them!