[maybe bug] Nested matching always chooses first case

[forflo]

given the following class hierarchy

struct Expression {};

struct ExpBinary : Expression {
    Expression *left, *right;

    ExpBinary(Expression *o1, Expression *o2)
        : left(o1)
        , right(o2) {}
};

struct ExpArith : ExpBinary {
    enum function { 
        SUB, ADD, MUL, DIV 
    };

    function arithOp;

    ExpArith(function f, Expression *l, Expression *r)
        : ExpBinary(l, r)
        , arithOp(f) {}
};

struct ExpLogical : ExpBinary {
    enum function_log { 
        GT, LT, EQ 
    };

    function_log logicalOp;

    ExpLogical(function_log f, Expression *l, Expression *r)
        : ExpBinary(l, r)
        , logicalOp(f) {}
};

struct ExpInteger : Expression {
    int value;
    ExpInteger(int v) : value(v) {}
};

The following evaluator somehow does not work:

int evaluate(const Expression& exp){
    var<Expression&> left, right;
    var<ExpLogical::function_log> lOp;
    var<ExpArith::function> aOp;
    int val;

    Match(exp){
        Case(C<ExpBinary>(&left, &right)) {
            Match(exp) {
                // cout << typeid(exp).name() << endl;
                Case(C<ExpArith>(aOp)) {
                    //cout << "exparith!\n";
                    Match(aOp) {
                        Case(ExpArith::ADD) {
                            return evaluate(left) + evaluate(right);
                        }
                        Case(ExpArith::SUB) {
                            return evaluate(left) - evaluate(right);
                        }
                        Case(ExpArith::MUL) {
                            return evaluate(left) * evaluate(right);
                        }
                        Case(ExpArith::DIV) {
                            return evaluate(left) / evaluate(right);
                        }
                        Otherwise() {
                            return 0;
                        }
                    } EndMatch
                }
                Case(C<ExpLogical>(lOp)) {
                    cout << "explogical!\n"; //never reached, but it should
                    Match(lOp) {
                        Case(ExpLogical::GT) {
                            return evaluate(left) > evaluate(right);
                        }
                        Case(ExpLogical::LT) {
                            return evaluate(left) < evaluate(right);
                        }
                        Case(ExpLogical::EQ) {
                            return evaluate(left) == evaluate(right);
                        }
                        Otherwise() {
                            return 0;
                        }
                    } EndMatch
                }
                Otherwise() {
                    cout << "Error in exp arith/logical matching!\n";
                    return 0;
                }
            } EndMatch
        }
        Case(C<ExpInteger>(val)) {
            return val;
        }
        Otherwise() {
            cout << "Error in evaluate!\n";
            return 0;
        }
    } EndMatch
}

If I build the expression

Expression *log =
        new ExpLogical(ExpLogical::GT,
                       new ExpInteger(3),
                       new ExpInteger(4));

and try to evaluate it using the statement,

cout << evaluate(*log) << endl;

the program outputs -1 which is wrong. Somehow the statement Case(C<ExpLogical>(lOp)) is not reached, instead the second Match(exp) chooses Case(C<ExpArith>(aOp)). I don't understand why, since the patterns against which the subjecting values are being matched are clearly different. Do you have any idea? Is it disallowed to nest Match statements?

I also provided the whole (compilable) example as a gist.

Best regards

[forflo]

I should add a concrete reason for the above situation! In my current project, I have to deal with a rather large and complex class hierarchy resembling ASTs for the language VHDL. Of course, in contrast to the above solution, I could specialize the bindings template as follows.

template <> struct bindings<ExpInteger> {
    Members(ExpInteger::value);
};

template <> struct bindings<ExpArith> {
    Members(ExpArith::arithOp, ExpArith::left, ExpArith::right);
};

template <> struct bindings<ExpLogical> {
    Members(ExpLogical::logicalOp, ExpLogical::left, ExpLogical::right);
};

With these specializations, I'm repeating myself as I have to give the same member names to bindings<ExpArith> and bindings<ExpLogical>. This is the only reason why I chose to rely on nested matching.

Of course this only makes sense on a larger scale.

I cannot use nested Patterns, because I need to first match on the more general class in order to extract the common members that the two more special objects share.

[forflo]

The error also occurs when I build with flag -O0 and with --std=c++1z. Furthermore, if I change the order of the Case(C<ExpLogical>(lOp)) and Case(C<ExpArith>(aOp)) blocks, the semantics does not change. Like before only the first block is reached no matter what dynamic type exp currently possesses.

[solodon4]

OK, the problem is in the very first line, if you turn it into:

struct Expression { virtual ~Expression(){} };

your example will magically start working. The reason for this is that the type switching functionality underneath the Match statement expects polymorphic class hierarchy in order to work properly. The details of this are described in our OOPSLA'12 paper. The reason I don't have a static assert inside C's instantiation for that is that in a some other cases the ability to have there non-polymorphic types is also useful, e.g. it is used for n+k patterns.

I'd have to come up with a more clever condition to check at compile time to prevent this mistake from happening in the future, so in the meantime I'll mark it as a bug for myself. I'd probably have to revisit the cases where I originally needed this functionality and see if I can do them differently.

The library can work however with non-polymorphic class hierarchies like yours where a certain member of the base class has an integral value that uniquely identifies the derived class. Search for all the examples that use KS macro to define that member of a class (Kind Selector) and KV macro that defines the value that uniquely identifies a given derive class. One of the examples is here. The important bit about working with kind selectors is that you need to include a different header to enable pattern matching functionality: mach7/match.hpp. You can't mix and match with the header you are using now (mach7/type_switchN-patterns-xtl.hpp) because they define almost the same surface interface but make different assumptions and use entirely different implementations. The Match statement will be slightly more efficient with mach7/match.hpp, however it won't support matching on 2 or more subjects at the same time and you'll have to use extra definitions (see BCS macros) to enable matching of derived classes agains base classes in Case clauses. You can find more details about these 2 parts of the library in my thesis. Right now, my general recommendation is to stick with mach7/type_switchN-patterns-xtl.hpp which is what library will be moving forward with as it is more powerful.

[forflo]

Thank you for the fix and the very good links providing background information!