Movimentum - The solver algorithm gets a few cleanups

The hard work of the solver right now happens in the method FindBestRewrite, where constraints are matched against two templates. I expect the number of templates to grow significantly—one can imagine templates for quadratic equations, templates to handle formal square roots, templates to solve single-variable constraints (e.g., using Newton's algorithm) etc. If we put all that into FindBestRewrite, that method will become a mess of if-then-elses and local variables and other what-have-you-nots. So I attempt to separate the "rules" (what should be tried on constraints in what order) from the actual matching. What we need at least, is some class that holds a pair of items:

• Something that we try to match.
• What happens when the match succeeds.

I'd like to just call a constructor of this class with that information to set up a new rule. And because the set of rules will not change during runtime (I hope, or decree), I want to put these constructor calls into some static constructor, e.g. of SolverNode. The following is a first attempt for that code—already the result of some copying around and making it compilable.

The class MatcherRuleAction holds the two pieces of information from above:

private class MatcherRuleAction {
    public readonly ScalarConstraintTemplate Template;
    public readonly Func<SolverNode,  
                         ScalarConstraintMatcher,  
                         AbstractConstraint,  
                         IEnumerable<SolverNode>> OnMatch;
    public MatcherRuleAction(ScalarConstraintTemplate template,
                             Func<SolverNode,  
                                  ScalarConstraintMatcher,
                                  AbstractConstraint,  
                                  IEnumerable<SolverNode>> onMatch) {
        Template = template;
        OnMatch = onMatch;
    }
}

I made this a private inner class of SolverNode, as it should not be used anywhere else (and therefore, I did not bother with perfect encapsulation via properties, but just used public readonly fields).
A static list, also private, inside SolverNode will hold all the MatcherRuleActions:

    private static readonly List<MatcherRuleAction> _ruleActions =
        new List<MatcherRuleAction>();

Finally, in the static constructor of SolverNode, we add new RuleActions to this list. For some more cleanliness, I put these declarations into a separate file, i.e., I split SolverNode into two partial classes. Here is now the MatcherRuleAction for matching 0 = V + E:

public partial class SolverNode {
    static SolverNode() {
        {
            // 0 = V + C
            var v = new TypeMatchTemplate<Variable>();
            var e = new TypeMatchTemplate<Constant>();
            _ruleActions.Add(new MatcherRuleAction(
                new EqualsZeroConstraintTemplate(v + e),
                (currNode, matcher, matchedConstraint) => {
                    var variable = matcher.Match(v);
                    var value = -matcher.Match(e).Value;
                    currNode._variableInRangeKnowledges.Add(
                        variable, new VariableValueRestriction(variable, value));
                    return SubstituteVariable(currNode, variable,  
                                              new Constant(value));
                }));
        }
    }
}

(I like to put additional braces {...} around code blocks that use their own local variables. This has saved me from referencing wrong local variables quite a number of times. Some people claim that this alone is reason enough to put the code into a separate method—certainly also a valid way to go.)

I already factored out a method SubstituteVariable, because the chunk of code in the action part is getting too large (and because I am quite sure that variable subtitution will be needed more often later—oops, up-front-design ...):

    private static IEnumerable<SolverNode> SubstituteVariable(
            SolverNode currNode,
            Variable variable,
            AbstractExpr expr) {
        var rewriter = new RewritingVisitor(
            new Dictionary<AbstractExpr, AbstractExpr> { { variable, expr } });
        IEnumerable<AbstractConstraint> rewrittenConstraints =
            currNode.Constraints.Select(c2 => c2.Accept(rewriter, Ig.nore));
        return new[] { new SolverNode(rewrittenConstraints, currNode) };
    }

Here is the corresponding code for our second template, the 0 = C case:

    {
        // 0 = C
        var z = new TypeMatchTemplate<Constant>();
        _ruleActions.Add(new MatcherRuleAction(
            new EqualsZeroConstraintTemplate(z),
            (currNode, matcher, matchedConstraint) =>
                matcher.Match(z).Value == 0
                    ? new[] {
                        new SolverNode(
                            currNode.Constraints
                                    .Except(new[] { matchedConstraint }),
                            currNode)
                      }
                    : new SolverNode[0]));
    }

A few more cleanups reduce repeated code:

• First, I put the call to Add inside the MatcherRuleAction constructor. This is a little bit risky, as the constructor now has a side effect, but I know that I will use these constructors only in the static setup, where this is ok (ideally, I should check that design rule: "The MatcherRuleAction constructors are used only in the static SolverNode constructor." Tools like NDepend or my .Net Architecture Checker could enforce this).
• Then, that big anonymous delegate from the first RuleAction is extracted into a method RememberAndSubstituteVariable in the SolverNode class.
• Finally, instead of creating singleton and empty arrays in the first rule, there is an additional constructor for a MatcherRuleAction which allows for a Func that returns a single SolverNode or null.

Here is the supporting code that is the result of these refactorings in the SolverNode class:

    private class MatcherRuleAction {
        public readonly ScalarConstraintTemplate Template;
        public readonly Func<SolverNode,
                             ScalarConstraintMatcher,
                             AbstractConstraint,
                             IEnumerable<SolverNode>> OnMatch;
        public MatcherRuleAction(ScalarConstraintTemplate template,
                Func<SolverNode,
                     ScalarConstraintMatcher,
                     AbstractConstraint,
                     IEnumerable<SolverNode>> onMatch) {
            Template = template;
            OnMatch = onMatch;
            _ruleActions.Add(this); // Add rule to static list.
        }

        // Constructor with Func<..., SolverNode> as onMatch.
        public MatcherRuleAction(ScalarConstraintTemplate template,
                Func<SolverNode,
                     ScalarConstraintMatcher,
                     AbstractConstraint,
                     SolverNode> onMatch)
            : this(template, (n, m, c) => {
                SolverNode v = onMatch(n, m, c);
                return v == null ? new SolverNode[0] : new[] { v };
            }) {
        }
    }

    // Factored out RememberAndSubstituteVariable
    private static IEnumerable<SolverNode> RememberAndSubstituteVariable(
            SolverNode currNode,
            Variable variable,
            double value) {
        currNode._variableInRangeKnowledges.Add(variable,  
             new VariableValueRestriction(variable, value));
        return SubstituteVariable(currNode, variable, new Constant(value));
    }

The RuleAction declarations now contain their information in quite tightly packed form:

public partial class SolverNode {
    static SolverNode() {
        {
            // 1. 0 = C
            var z = new TypeMatchTemplate<Constant>();
            new MatcherRuleAction(
                new EqualsZeroConstraintTemplate(z),
                (currNode, matcher, matchedConstraint) =>
                    matcher.Match(z).Value == 0
                        ? new SolverNode(
                            currNode.Constraints
                                    .Except(new[] { matchedConstraint }),
                            currNode)
                        : null);
        }
        {
            // 2. 0 = V + C
            var v = new TypeMatchTemplate<Variable>();
            var e = new TypeMatchTemplate<Constant>();
            new MatcherRuleAction(
                new EqualsZeroConstraintTemplate(v + e),
                (currNode, matcher, matchedConstraint) =>
                    RememberAndSubstituteVariable(currNode,
                        matcher.Match(v),
                        -matcher.Match(e).Value));
        }
    }
}

This should be an acceptable base for writing more rules.