QPID-4621: Arithmetic operations for C++ broker selectors

- Rearranged Syntax and parser to support arithmetic
- Implemented arithmetic syntax
- Implemented arithmetic operators
- Added some tests for arithmetic operations
- Added explicit lexical tokens for all the comparison and arithmetic operations
- Added the missing ',' token for us in the 'IN' comparison
- Rearranged the lexer so that everything is not uniformly inside the
  hand crafted state machine.
- Moved a bunch of testing code from the tokeniser to the unit test
  (much of this code might actually not be very useful anymore)

git-svn-id: https://svn.apache.org/repos/asf/qpid/trunk/qpid@1457912 13f79535-47bb-0310-9956-ffa450edef68

1 files changed, 314 insertions, 98 deletions

diff --git a/cpp/src/qpid/broker/SelectorExpression.cpp b/cpp/src/qpid/broker/SelectorExpression.cpp
index 8c6d82cc6f..58ab756a12 100644
--- a/cpp/src/qpid/broker/SelectorExpression.cpp
+++ b/cpp/src/qpid/broker/SelectorExpression.cpp
@@ -63,21 +63,32 @@
  *
  * OrExpression ::= AndExpression  ( "OR" AndExpression )*
  *
- * AndExpression :: = EqualityExpression ( "AND" EqualityExpression  )*
+ * AndExpression :: = ComparisonExpression ( "AND" ComparisonExpression )*
  *
- * ComparisonExpression ::= PrimaryExpression "IS" "NULL" |
- *                          PrimaryExpression "IS" "NOT" "NULL" |
- *                          PrimaryExpression "LIKE" LiteralString [ "ESCAPE" LiteralString ] |
- *                          PrimaryExpression "NOT" "LIKE" LiteralString [ "ESCAPE" LiteralString ] |
- *                          PrimaryExpression "BETWEEN" PrimaryExpression "AND" PrimaryExpression |
- *                          PrimaryExpression "NOT" "BETWEEN" PrimaryExpression "AND" PrimaryExpression |
- *                          PrimaryExpression ComparisonOpsOps PrimaryExpression |
+ * ComparisonExpression ::= AddExpression "IS" "NULL" |
+ *                          AddExpression "IS" "NOT" "NULL" |
+ *                          AddExpression "LIKE" LiteralString [ "ESCAPE" LiteralString ] |
+ *                          AddExpression "NOT" "LIKE" LiteralString [ "ESCAPE" LiteralString ] |
+ *                          AddExpression "BETWEEN" AddExpression "AND" AddExpression |
+ *                          AddExpression "NOT" "BETWEEN" AddExpression "AND" AddExpression |
+ *                          AddExpression ComparisonOps AddExpression |
  *                          "NOT" ComparisonExpression |
- *                          "(" OrExpression ")"
+ *                          AddExpression
+ *
+ * AddOps ::= "+" | "-"
+ *
+ * MultiplyOps ::= "*" | "-"
+ *
+ * AddExpression :: = MultiplyExpression (  AddOps MultiplyExpression )*
+ *
+ * MultiplyExpression :: = UnaryArithExpression ( MultiplyOps UnaryArithExpression )*
+ *
+ * UnaryArithExpression ::= AddOps AddExpression |
+ *                          "(" OrExpression ")" |
+ *                          PrimaryExpression
  *
  * PrimaryExpression :: = Identifier |
  *                        Literal
- *
  */
 
 
@@ -92,6 +103,12 @@ public:
     virtual ~Expression() {}
     virtual void repr(std::ostream&) const = 0;
     virtual Value eval(const SelectorEnv&) const = 0;
+
+    virtual BoolOrNone eval_bool(const SelectorEnv& env) const {
+        Value v = eval(env);
+        if (v.type==Value::T_BOOL) return BoolOrNone(v.b);
+        else return BN_UNKNOWN;
+    }
 };
 
 class BoolExpression : public Expression {
@@ -122,6 +139,20 @@ public:
     virtual BoolOrNone eval(T&, const SelectorEnv&) const = 0;
 };
 
+class ArithmeticOperator {
+public:
+    virtual ~ArithmeticOperator() {}
+    virtual void repr(ostream&) const = 0;
+    virtual Value eval(Expression&, Expression&, const SelectorEnv&) const = 0;
+};
+
+class UnaryArithmeticOperator {
+public:
+    virtual ~UnaryArithmeticOperator() {}
+    virtual void repr(ostream&) const = 0;
+    virtual Value eval(Expression&, const SelectorEnv&) const = 0;
+};
+
 ////////////////////////////////////////////////////
 
 // Convenience outputters
@@ -145,6 +176,18 @@ ostream& operator<<(ostream& os, const UnaryBooleanOperator<T>& e)
     return os;
 }
 
+ostream& operator<<(ostream& os, const ArithmeticOperator& e)
+{
+    e.repr(os);
+    return os;
+}
+
+ostream& operator<<(ostream& os, const UnaryArithmeticOperator& e)
+{
+    e.repr(os);
+    return os;
+}
+
 // Boolean Expression types...
 
 class ComparisonExpression : public BoolExpression {
@@ -169,11 +212,11 @@ public:
 };
 
 class OrExpression : public BoolExpression {
-    boost::scoped_ptr<BoolExpression> e1;
-    boost::scoped_ptr<BoolExpression> e2;
+    boost::scoped_ptr<Expression> e1;
+    boost::scoped_ptr<Expression> e2;
 
 public:
-    OrExpression(BoolExpression* e, BoolExpression* e_):
+    OrExpression(Expression* e, Expression* e_):
         e1(e),
         e2(e_)
     {}
@@ -193,11 +236,11 @@ public:
 };
 
 class AndExpression : public BoolExpression {
-    boost::scoped_ptr<BoolExpression> e1;
-    boost::scoped_ptr<BoolExpression> e2;
+    boost::scoped_ptr<Expression> e1;
+    boost::scoped_ptr<Expression> e2;
 
 public:
-    AndExpression(BoolExpression* e, BoolExpression* e_):
+    AndExpression(Expression* e, Expression* e_):
         e1(e),
         e2(e_)
     {}
@@ -336,6 +379,48 @@ public:
     }
 };
 
+// Arithmetic Expression types
+
+class ArithmeticExpression : public Expression {
+    ArithmeticOperator* op;
+    boost::scoped_ptr<Expression> e1;
+    boost::scoped_ptr<Expression> e2;
+
+public:
+    ArithmeticExpression(ArithmeticOperator* o, Expression* e, Expression* e_):
+        op(o),
+        e1(e),
+        e2(e_)
+    {}
+
+    void repr(ostream& os) const {
+        os << "(" << *e1 << *op << *e2 << ")";
+    }
+
+    Value eval(const SelectorEnv& env) const {
+        return op->eval(*e1, *e2, env);
+    }
+};
+
+class UnaryArithExpression : public Expression {
+    UnaryArithmeticOperator* op;
+    boost::scoped_ptr<Expression> e1;
+
+public:
+    UnaryArithExpression(UnaryArithmeticOperator* o, Expression* e) :
+        op(o),
+        e1(e)
+    {}
+
+    void repr(ostream& os) const {
+        os << *op << "(" << *e1 << ")";
+    }
+
+    Value eval(const SelectorEnv& env) const {
+        return op->eval(*e1, env);
+    }
+};
+
 // Expression types...
 
 class Literal : public Expression {
@@ -496,18 +581,68 @@ class IsNonNull : public UnaryBooleanOperator<Expression> {
 };
 
 // "NOT"
-class Not : public UnaryBooleanOperator<BoolExpression> {
+class Not : public UnaryBooleanOperator<Expression> {
     void repr(ostream& os) const {
         os << "NOT";
     }
 
-    BoolOrNone eval(BoolExpression& e, const SelectorEnv& env) const {
+    BoolOrNone eval(Expression& e, const SelectorEnv& env) const {
         BoolOrNone bn = e.eval_bool(env);
         if (bn==BN_UNKNOWN) return bn;
         else return BoolOrNone(!bn);
     }
 };
 
+class Negate : public UnaryArithmeticOperator {
+    void repr(ostream& os) const {
+        os << "-";
+    }
+
+    Value eval(Expression& e, const SelectorEnv& env) const {
+        return -e.eval(env);
+    }
+};
+
+class Add : public ArithmeticOperator {
+    void repr(ostream& os) const {
+        os << "+";
+    }
+
+    Value eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env)+e2.eval(env);
+    }
+};
+
+class Sub : public ArithmeticOperator {
+    void repr(ostream& os) const {
+        os << "-";
+    }
+
+    Value eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env)-e2.eval(env);
+    }
+};
+
+class Mult : public ArithmeticOperator {
+    void repr(ostream& os) const {
+        os << "*";
+    }
+
+    Value eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env)*e2.eval(env);
+    }
+};
+
+class Div : public ArithmeticOperator {
+    void repr(ostream& os) const {
+        os << "/";
+    }
+
+    Value eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env)/e2.eval(env);
+    }
+};
+
 Eq eqOp;
 Neq neqOp;
 Ls lsOp;
@@ -518,16 +653,25 @@ IsNull isNullOp;
 IsNonNull isNonNullOp;
 Not notOp;
 
+Negate negate;
+Add add;
+Sub sub;
+Mult mult;
+Div div;
+
 ////////////////////////////////////////////////////
 
-BoolExpression* parseOrExpression(Tokeniser&);
-BoolExpression* parseAndExpression(Tokeniser&);
-BoolExpression* parseComparisonExpression(Tokeniser&);
+Expression* parseOrExpression(Tokeniser&);
+Expression* parseAndExpression(Tokeniser&);
+Expression* parseComparisonExpression(Tokeniser&);
+Expression* parseAddExpression(Tokeniser&);
+Expression* parseMultiplyExpression(Tokeniser&);
+Expression* parseUnaryArithExpression(Tokeniser&);
 Expression* parsePrimaryExpression(Tokeniser&);
 
 // Top level parser
 class TopBoolExpression : public TopExpression {
-    boost::scoped_ptr<BoolExpression> expression;
+    boost::scoped_ptr<Expression> expression;
 
     void repr(ostream& os) const {
         expression->repr(os);
@@ -540,7 +684,7 @@ class TopBoolExpression : public TopExpression {
     }
 
 public:
-    TopBoolExpression(BoolExpression* be) :
+    TopBoolExpression(Expression* be) :
         expression(be)
     {}
 };
@@ -550,19 +694,19 @@ TopExpression* TopExpression::parse(const string& exp)
     string::const_iterator s = exp.begin();
     string::const_iterator e = exp.end();
     Tokeniser tokeniser(s,e);
-    std::auto_ptr<BoolExpression> b(parseOrExpression(tokeniser));
+    std::auto_ptr<Expression> b(parseOrExpression(tokeniser));
     if (!b.get()) throw std::range_error("Illegal selector: couldn't parse");
     if (tokeniser.nextToken().type != T_EOS) throw std::range_error("Illegal selector: too much input");
     return new TopBoolExpression(b.release());
 }
 
-BoolExpression* parseOrExpression(Tokeniser& tokeniser)
+Expression* parseOrExpression(Tokeniser& tokeniser)
 {
-    std::auto_ptr<BoolExpression> e(parseAndExpression(tokeniser));
+    std::auto_ptr<Expression> e(parseAndExpression(tokeniser));
     if (!e.get()) return 0;
     while ( tokeniser.nextToken().type==T_OR ) {
-        std::auto_ptr<BoolExpression> e1(e);
-        std::auto_ptr<BoolExpression> e2(parseAndExpression(tokeniser));
+        std::auto_ptr<Expression> e1(e);
+        std::auto_ptr<Expression> e2(parseAndExpression(tokeniser));
         if (!e2.get()) return 0;
         e.reset(new OrExpression(e1.release(), e2.release()));
     }
@@ -570,13 +714,13 @@ BoolExpression* parseOrExpression(Tokeniser& tokeniser)
     return e.release();
 }
 
-BoolExpression* parseAndExpression(Tokeniser& tokeniser)
+Expression* parseAndExpression(Tokeniser& tokeniser)
 {
-    std::auto_ptr<BoolExpression> e(parseComparisonExpression(tokeniser));
+    std::auto_ptr<Expression> e(parseComparisonExpression(tokeniser));
     if (!e.get()) return 0;
     while ( tokeniser.nextToken().type==T_AND ) {
-        std::auto_ptr<BoolExpression> e1(e);
-        std::auto_ptr<BoolExpression> e2(parseComparisonExpression(tokeniser));
+        std::auto_ptr<Expression> e1(e);
+        std::auto_ptr<Expression> e2(parseComparisonExpression(tokeniser));
         if (!e2.get()) return 0;
         e.reset(new AndExpression(e1.release(), e2.release()));
     }
@@ -586,94 +730,166 @@ BoolExpression* parseAndExpression(Tokeniser& tokeniser)
 
 BoolExpression* parseSpecialComparisons(Tokeniser& tokeniser, std::auto_ptr<Expression> e1) {
     switch (tokeniser.nextToken().type) {
-        case T_LIKE: {
-            const Token t = tokeniser.nextToken();
-            if ( t.type!=T_STRING ) return 0;
-            // Check for "ESCAPE"
-            if ( tokeniser.nextToken().type==T_ESCAPE ) {
-                const Token e = tokeniser.nextToken();
-                if ( e.type!=T_STRING ) return 0;
-                return new LikeExpression(e1.release(), t.val, e.val);
-            } else {
-                tokeniser.returnTokens();
-                return new LikeExpression(e1.release(), t.val);
-            }
-        }
-        case T_BETWEEN: {
-            std::auto_ptr<Expression> lower(parsePrimaryExpression(tokeniser));
-            if ( !lower.get() ) return 0;
-            if ( tokeniser.nextToken().type!=T_AND ) return 0;
-            std::auto_ptr<Expression> upper(parsePrimaryExpression(tokeniser));
-            if ( !upper.get() ) return 0;
-            return new BetweenExpression(e1.release(), lower.release(), upper.release());
+    case T_LIKE: {
+        const Token t = tokeniser.nextToken();
+        if ( t.type!=T_STRING ) return 0;
+        // Check for "ESCAPE"
+        if ( tokeniser.nextToken().type==T_ESCAPE ) {
+            const Token e = tokeniser.nextToken();
+            if ( e.type!=T_STRING ) return 0;
+            return new LikeExpression(e1.release(), t.val, e.val);
+        } else {
+            tokeniser.returnTokens();
+            return new LikeExpression(e1.release(), t.val);
         }
-        default:
-            return 0;
+    }
+    case T_BETWEEN: {
+        std::auto_ptr<Expression> lower(parseAddExpression(tokeniser));
+        if ( !lower.get() ) return 0;
+        if ( tokeniser.nextToken().type!=T_AND ) return 0;
+        std::auto_ptr<Expression> upper(parseAddExpression(tokeniser));
+        if ( !upper.get() ) return 0;
+        return new BetweenExpression(e1.release(), lower.release(), upper.release());
+    }
+    default:
+        return 0;
     }
 }
 
-BoolExpression* parseComparisonExpression(Tokeniser& tokeniser)
+Expression* parseComparisonExpression(Tokeniser& tokeniser)
 {
     const Token t = tokeniser.nextToken();
-    if ( t.type==T_LPAREN ) {
-        std::auto_ptr<BoolExpression> e(parseOrExpression(tokeniser));
-        if (!e.get()) return 0;
-        if ( tokeniser.nextToken().type!=T_RPAREN ) return 0;
-        return e.release();
-    } else if ( t.type==T_NOT ) {
-        std::auto_ptr<BoolExpression> e(parseComparisonExpression(tokeniser));
+    if ( t.type==T_NOT ) {
+        std::auto_ptr<Expression> e(parseComparisonExpression(tokeniser));
         if (!e.get()) return 0;
-        return new UnaryBooleanExpression<BoolExpression>(&notOp, e.release());
+        return new UnaryBooleanExpression<Expression>(&notOp, e.release());
     }
 
     tokeniser.returnTokens();
-    std::auto_ptr<Expression> e1(parsePrimaryExpression(tokeniser));
+    std::auto_ptr<Expression> e1(parseAddExpression(tokeniser));
     if (!e1.get()) return 0;
 
     switch (tokeniser.nextToken().type) {
-        // Check for "IS NULL" and "IS NOT NULL"
-        case T_IS:
-            // The rest must be T_NULL or T_NOT, T_NULL
-            switch (tokeniser.nextToken().type) {
-                case T_NULL:
-                    return new UnaryBooleanExpression<Expression>(&isNullOp, e1.release());
-                case T_NOT:
-                    if ( tokeniser.nextToken().type == T_NULL)
-                        return new UnaryBooleanExpression<Expression>(&isNonNullOp, e1.release());
-                default:
-                    return 0;
-            }
-        case T_NOT: {
-            std::auto_ptr<BoolExpression> e(parseSpecialComparisons(tokeniser, e1));
-            if (!e.get()) return 0;
-            return new UnaryBooleanExpression<BoolExpression>(&notOp, e.release());
-        }
-        case T_BETWEEN:
-        case T_LIKE: {
-            tokeniser.returnTokens();
-            return parseSpecialComparisons(tokeniser, e1);
+    // Check for "IS NULL" and "IS NOT NULL"
+    case T_IS:
+        // The rest must be T_NULL or T_NOT, T_NULL
+        switch (tokeniser.nextToken().type) {
+            case T_NULL:
+                return new UnaryBooleanExpression<Expression>(&isNullOp, e1.release());
+            case T_NOT:
+                if ( tokeniser.nextToken().type == T_NULL)
+                    return new UnaryBooleanExpression<Expression>(&isNonNullOp, e1.release());
+            default:
+                return 0;
         }
+    case T_NOT: {
+        std::auto_ptr<BoolExpression> e(parseSpecialComparisons(tokeniser, e1));
+        if (!e.get()) return 0;
+        return new UnaryBooleanExpression<Expression>(&notOp, e.release());
+    }
+    case T_BETWEEN:
+    case T_LIKE: {
+        tokeniser.returnTokens();
+        return parseSpecialComparisons(tokeniser, e1);
+    }
+    default:
+        break;
+    }
+    tokeniser.returnTokens();
+
+    ComparisonOperator* op;
+    switch (tokeniser.nextToken().type) {
+    case T_EQUAL: op = &eqOp; break;
+    case T_NEQ: op = &neqOp; break;
+    case T_LESS: op = &lsOp; break;
+    case T_GRT: op = &grOp; break;
+    case T_LSEQ: op = &lseqOp; break;
+    case T_GREQ: op = &greqOp; break;
+    default:
+        tokeniser.returnTokens();
+        return e1.release();
+    }
+
+    std::auto_ptr<Expression> e2(parseAddExpression(tokeniser));
+    if (!e2.get()) return 0;
+
+    return new ComparisonExpression(op, e1.release(), e2.release());
+}
+
+Expression* parseAddExpression(Tokeniser& tokeniser)
+{
+    std::auto_ptr<Expression> e(parseMultiplyExpression(tokeniser));
+    if (!e.get()) return 0;
+
+    Token t = tokeniser.nextToken();
+    while (t.type==T_PLUS || t.type==T_MINUS ) {
+        ArithmeticOperator* op;
+        switch (t.type) {
+        case T_PLUS: op = &add; break;
+        case T_MINUS: op = &sub; break;
         default:
-            break;
+            return 0;
+        }
+        std::auto_ptr<Expression> e1(e);
+        std::auto_ptr<Expression> e2(parseMultiplyExpression(tokeniser));
+        if (!e2.get()) return 0;
+        e.reset(new ArithmeticExpression(op, e1.release(), e2.release()));
+        t = tokeniser.nextToken();
     }
+
     tokeniser.returnTokens();
+    return e.release();
+}
 
-    const Token op = tokeniser.nextToken();
-    if (op.type != T_OPERATOR) {
-        return 0;
+Expression* parseMultiplyExpression(Tokeniser& tokeniser)
+{
+    std::auto_ptr<Expression> e(parseUnaryArithExpression(tokeniser));
+    if (!e.get()) return 0;
+
+    Token t = tokeniser.nextToken();
+    while (t.type==T_MULT || t.type==T_DIV ) {
+        ArithmeticOperator* op;
+        switch (t.type) {
+        case T_MULT: op = &mult; break;
+        case T_DIV: op = &div; break;
+        default:
+            return 0;
+        }
+        std::auto_ptr<Expression> e1(e);
+        std::auto_ptr<Expression> e2(parseMultiplyExpression(tokeniser));
+        if (!e2.get()) return 0;
+        e.reset(new ArithmeticExpression(op, e1.release(), e2.release()));
+        t = tokeniser.nextToken();
     }
 
-    std::auto_ptr<Expression> e2(parsePrimaryExpression(tokeniser));
-    if (!e2.get()) return 0;
+    tokeniser.returnTokens();
+    return e.release();
+}
 
-    if (op.val == "=") return new ComparisonExpression(&eqOp, e1.release(), e2.release());
-    if (op.val == "<>") return new ComparisonExpression(&neqOp, e1.release(), e2.release());
-    if (op.val == "<") return new ComparisonExpression(&lsOp, e1.release(), e2.release());
-    if (op.val == ">") return new ComparisonExpression(&grOp, e1.release(), e2.release());
-    if (op.val == "<=") return new ComparisonExpression(&lseqOp, e1.release(), e2.release());
-    if (op.val == ">=") return new ComparisonExpression(&greqOp, e1.release(), e2.release());
+Expression* parseUnaryArithExpression(Tokeniser& tokeniser)
+{
+    const Token t = tokeniser.nextToken();
+    switch (t.type) {
+    case T_LPAREN: {
+        std::auto_ptr<Expression> e(parseOrExpression(tokeniser));
+        if (!e.get()) return 0;
+        if ( tokeniser.nextToken().type!=T_RPAREN ) return 0;
+        return e.release();
+    }
+    case T_PLUS:
+        break; // Unary + is no op
+    case T_MINUS: {
+        std::auto_ptr<Expression> e(parseUnaryArithExpression(tokeniser));
+        if (!e.get()) return 0;
+        return new UnaryArithExpression(&negate, e.release());
+    }
+    default:
+        break;
+    }
 
-    return 0;
+    tokeniser.returnTokens();
+    std::auto_ptr<Expression> e(parsePrimaryExpression(tokeniser));
+    return e.release();
 }
 
 Expression* parsePrimaryExpression(Tokeniser& tokeniser)