QPID-4558: Selectors for C++ broker

- Initial Selectors implemented:
* Only string values supported (no numerics or bools)
- Parses and executes the forms:
*  A=B
*  A<>B
*  I IS NULL
*  I IS NOT NULL
- where A, B are strings or identifiers
-       I is an identifier
* Conditional expressions can include the AND, OR and NOT
  operators and use parentheses.
- Only limited special identifiers return useful values (although
  they are all recognised)
- Unit tests for selector language

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

11 files changed, 1166 insertions, 5 deletions

diff --git a/cpp/src/CMakeLists.txt b/cpp/src/CMakeLists.txt
index c44bb8d999..a85c32b8e1 100644
--- a/cpp/src/CMakeLists.txt
+++ b/cpp/src/CMakeLists.txt
@@ -1207,6 +1207,10 @@ set (qpidbroker_SOURCES
      qpid/broker/SecureConnectionFactory.cpp
      qpid/broker/Selector.h
      qpid/broker/Selector.cpp
+     qpid/broker/SelectorExpression.h
+     qpid/broker/SelectorExpression.cpp
+     qpid/broker/SelectorToken.h
+     qpid/broker/SelectorToken.cpp
      qpid/broker/SemanticState.h
      qpid/broker/SemanticState.cpp
      qpid/broker/SessionAdapter.cpp
diff --git a/cpp/src/Makefile.am b/cpp/src/Makefile.am
index 7d03cd1d26..7fb210ef7c 100644
--- a/cpp/src/Makefile.am
+++ b/cpp/src/Makefile.am
@@ -715,6 +715,10 @@ libqpidbroker_la_SOURCES = \
   qpid/broker/SecureConnectionFactory.h \
   qpid/broker/Selector.cpp \
   qpid/broker/Selector.h \
+  qpid/broker/SelectorExpression.cpp \
+  qpid/broker/SelectorExpression.h \
+  qpid/broker/SelectorToken.cpp \
+  qpid/broker/SelectorToken.h \
   qpid/broker/SemanticState.cpp \
   qpid/broker/SemanticState.h \
   qpid/broker/SessionAdapter.cpp \
diff --git a/cpp/src/qpid/broker/Selector.cpp b/cpp/src/qpid/broker/Selector.cpp
index 805bcdbba1..0880285692 100644
--- a/cpp/src/qpid/broker/Selector.cpp
+++ b/cpp/src/qpid/broker/Selector.cpp
@@ -22,8 +22,14 @@
 #include "qpid/broker/Selector.h"
 
 #include "qpid/broker/Message.h"
+#include "qpid/broker/SelectorExpression.h"
+#include "qpid/log/Statement.h"
+
+#include <string>
+#include <sstream>
 
 #include <boost/make_shared.hpp>
+#include <boost/lexical_cast.hpp>
 
 namespace qpid {
 namespace broker {
@@ -31,8 +37,16 @@ namespace broker {
 using std::string;
 
 Selector::Selector(const string& e) :
+    parse(parseTopBoolExpression(e)),
     expression(e)
 {
+    bool debugOut;
+    QPID_LOG_TEST(debug, debugOut);
+    if (debugOut) {
+        std::stringstream ss;
+        parse->repr(ss);
+        QPID_LOG(debug, "Selector parsed[" << e << "] into: " << ss.str());
+    }
 }
 
 Selector::~Selector()
@@ -41,8 +55,7 @@ Selector::~Selector()
 
 bool Selector::eval(const SelectorEnv& env)
 {
-    // Simple test - return true if expression is a non-empty property
-    return env.present(expression);
+    return parse->eval(env);
 }
 
 bool Selector::filter(const Message& msg)
@@ -61,10 +74,61 @@ bool MessageSelectorEnv::present(const string& identifier) const
     return !msg.getProperty(identifier).isVoid();
 }
 
+/**
+ * Identifier  (amqp.)  | JMS...       | amqp 1.0 equivalent
+ * durable              |              | durable              header section
+ * delivery_mode        | DeliveryMode | [durable ? 'PERSISTENT' : 'NON_PERSISTENT'] (computed value)
+ * priority             | Priority     | priority             header section
+ * delivery_count       |              | delivery-count       header section
+ * redelivered          |[Redelivered] | (delivery_count>0)  (computed value)
+ * correlation_id       | CorrelationID| correlation-id       properties section
+ * to                   |[Destination] | to                   properties section
+ * absolute_expiry_time |[Expiration]  | absolute-expiry-time properties section
+ * message_id           | MessageID    | message-id           properties section
+ * reply_to             |[ReplyTo]     | reply-to             properties section
+ * creation_time        | Timestamp    | creation-time        properties section
+ * jms_type             | Type         | jms-type             message-annotations section
+ */
+
+string specialValue(const Message& msg, const string& id)
+{
+    // TODO: Just use a simple if chain for now - improve this later
+    if ( id=="delivery_mode" ) {
+        return msg.getEncoding().isPersistent() ? "PERSISTENT" : "NON_PERSISTENT";
+    } else if ( id=="redelivered" ) {
+        return msg.getDeliveryCount()>0 ? "TRUE" : "FALSE";
+    } else if ( id=="priority" ) {
+        return boost::lexical_cast<string>(static_cast<uint32_t>(msg.getEncoding().getPriority()));
+    } else if ( id=="correlation_id" ) {
+        return ""; // Needs an indirection in getEncoding().
+    } else if ( id=="message_id" ) {
+        return ""; // Needs an indirection in getEncoding().
+    } else if ( id=="to" ) {
+        return msg.getRoutingKey(); // This is good for 0-10, not sure about 1.0
+    } else if ( id=="reply_to" ) {
+        return ""; // Needs an indirection in getEncoding().
+    } else if ( id=="absolute_expiry_time" ) {
+        return ""; // Needs an indirection in getEncoding().
+    } else if ( id=="creation_time" ) {
+        return ""; // Needs an indirection in getEncoding().
+    } else if ( id=="jms_type" ) {
+        return msg.getAnnotation("jms-type");
+    } else return "";
+}
+
 string MessageSelectorEnv::value(const string& identifier) const
 {
-    // Just return property as string
-    return msg.getPropertyAsString(identifier);
+    string v;
+
+    // Check for amqp prefix and strip it if present
+    if (identifier.substr(0, 5) == "amqp.") {
+        v = specialValue(msg, identifier.substr(5));
+    } else {
+        // Just return property as string
+        v = msg.getPropertyAsString(identifier);
+    }
+    QPID_LOG(debug, "Selector identifier: " << identifier << "->" << v);
+    return v;
 }
 
 
@@ -78,5 +142,4 @@ boost::shared_ptr<Selector> returnSelector(const string& e)
     return boost::make_shared<Selector>(e);
 }
 
-
 }}
diff --git a/cpp/src/qpid/broker/Selector.h b/cpp/src/qpid/broker/Selector.h
index dc0a5719b7..352d9c8e02 100644
--- a/cpp/src/qpid/broker/Selector.h
+++ b/cpp/src/qpid/broker/Selector.h
@@ -31,6 +31,7 @@ namespace qpid {
 namespace broker {
 
 class Message;
+class BoolExpression;
 
 /**
  * Interface to provide values to a Selector evaluation
@@ -56,6 +57,7 @@ public:
 };
 
 class Selector {
+    boost::scoped_ptr<BoolExpression> parse;
     const std::string expression;
 
 public:
diff --git a/cpp/src/qpid/broker/SelectorExpression.cpp b/cpp/src/qpid/broker/SelectorExpression.cpp
new file mode 100644
index 0000000000..4593b21c83
--- /dev/null
+++ b/cpp/src/qpid/broker/SelectorExpression.cpp
@@ -0,0 +1,419 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/broker/SelectorExpression.h"
+
+#include "qpid/broker/Selector.h"
+#include "qpid/broker/SelectorToken.h"
+
+#include <string>
+#include <memory>
+#include <ostream>
+
+#include <boost/scoped_ptr.hpp>
+
+/*
+ * Syntax for JMS style selector expressions (informal):
+ *
+ * Alpha ::= "a".."z" | "A".."Z"
+ * Digit ::= "0".."9"
+ * IdentifierInitial ::= Alpha | "_" | "$"
+ * IdentifierPart ::= IdentifierInitial | Digit | "."
+ * Identifier ::= IdentifierInitial IdentifierPart*
+ * Constraint : Identifier NOT IN ("NULL", "TRUE", "FALSE", "NOT", "AND", "OR", "BETWEEN", "LIKE", "IN", "IS") // Case insensitive
+ *
+ * LiteralString ::= ("'" ~[']* "'")+ // Repeats to cope with embedded single quote
+ *
+ * // Currently no numerics at all
+ * //LiteralExactNumeric ::= Digit+
+ * //LiteralApproxNumeric ::= ( Digit "." Digit* [ "E" LiteralExactNumeric ] ) |
+ * //                         ( "." Digit+ [ "E" LiteralExactNumeric ] ) |
+ * //                         ( Digit+ "E" LiteralExactNumeric )
+ * //LiteralBool ::= "TRUE" | "FALSE"
+ * //
+ *
+ * Literal ::= LiteralBool | LiteralString | LiteralApproxNumeric | LiteralExactNumeric
+ *
+ * // Currently only simple string comparison expressions + IS NULL or IS NOT NULL
+ * EqOps ::= "=" | "<>"
+ *
+ * ComparisonOps ::= EqOps | ">" | ">=" | "<" | "<="
+ *
+ * BoolExpression ::= OrExpression
+ *
+ * OrExpression ::= AndExpression  ( "OR" AndExpression )*
+ *
+ * AndExpression :: = EqualityExpression ( "AND" EqualityExpression  )*
+ *
+ * EqualityExpression ::= Identifier "IS" "NULL" |
+ *                        Identifier "IS "NOT" "NULL" |
+ *                        PrimaryExpression EqOps PrimaryExpression |
+ *                        "NOT" EqualityExpression |
+ *                        "(" OrExpression ")"
+ *
+ * PrimaryExpression :: = Identifier |
+ *                        LiteralString
+ *
+ */
+
+namespace qpid {
+namespace broker {
+
+class Expression;
+
+using std::string;
+using std::ostream;
+
+// Operators
+
+class EqualityOperator {
+public:
+    virtual void repr(ostream&) const = 0;
+    virtual bool eval(Expression&, Expression&, const SelectorEnv&) const = 0;
+};
+
+template <typename T>
+class UnaryBooleanOperator {
+public:
+    virtual void repr(ostream&) const = 0;
+    virtual bool eval(T&, const SelectorEnv&) const = 0;
+};
+
+////////////////////////////////////////////////////
+
+// Convenience outputters
+
+ostream& operator<<(ostream& os, const Expression& e)
+{
+    e.repr(os);
+    return os;
+}
+
+ostream& operator<<(ostream& os, const BoolExpression& e)
+{
+    e.repr(os);
+    return os;
+}
+
+ostream& operator<<(ostream& os, const EqualityOperator& e)
+{
+    e.repr(os);
+    return os;
+}
+
+template <typename T>
+ostream& operator<<(ostream& os, const UnaryBooleanOperator<T>& e)
+{
+    e.repr(os);
+    return os;
+}
+
+// Boolean Expression types...
+
+class EqualityExpression : public BoolExpression {
+    EqualityOperator* op;
+    boost::scoped_ptr<Expression> e1;
+    boost::scoped_ptr<Expression> e2;
+
+public:
+    EqualityExpression(EqualityOperator* o, Expression* e, Expression* e_):
+        op(o),
+        e1(e),
+        e2(e_)
+    {}
+
+    void repr(ostream& os) const {
+        os << "(" << *e1 << *op << *e2 << ")";
+    }
+
+    bool eval(const SelectorEnv& env) const {
+        return op->eval(*e1, *e2, env);
+    }
+};
+
+class OrExpression : public BoolExpression {
+    boost::scoped_ptr<BoolExpression> e1;
+    boost::scoped_ptr<BoolExpression> e2;
+
+public:
+    OrExpression(BoolExpression* e, BoolExpression* e_):
+        e1(e),
+        e2(e_)
+    {}
+
+    void repr(ostream& os) const {
+        os << "(" << *e1 << " OR " << *e2 << ")";
+    }
+
+    // We can use the regular C++ short-circuiting operator||
+    bool eval(const SelectorEnv& env) const {
+        return e1->eval(env) || e2->eval(env);
+    }
+};
+
+class AndExpression : public BoolExpression {
+    boost::scoped_ptr<BoolExpression> e1;
+    boost::scoped_ptr<BoolExpression> e2;
+
+public:
+    AndExpression(BoolExpression* e, BoolExpression* e_):
+        e1(e),
+        e2(e_)
+    {}
+
+    void repr(ostream& os) const {
+        os << "(" << *e1 << " AND " << *e2 << ")";
+    }
+
+    // We can use the regular C++ short-circuiting operator&&
+    bool eval(const SelectorEnv& env) const {
+        return e1->eval(env) && e2->eval(env);
+    }
+};
+
+template <typename T>
+class UnaryBooleanExpression : public BoolExpression {
+    UnaryBooleanOperator<T>* op;
+    boost::scoped_ptr<T> e1;
+
+public:
+    UnaryBooleanExpression(UnaryBooleanOperator<T>* o, T* e) :
+        op(o),
+        e1(e)
+    {}
+
+    void repr(ostream& os) const {
+        os << *op << "(" << *e1 << ")";
+    }
+
+    virtual bool eval(const SelectorEnv& env) const {
+        return op->eval(*e1, env);
+    }
+};
+
+// Expression types...
+
+class Literal : public Expression {
+    string value;
+
+public:
+    Literal(const string& v) :
+        value(v)
+    {}
+
+    void repr(ostream& os) const {
+        os << "'" << value << "'";
+    }
+
+    string eval(const SelectorEnv&) const {
+        return value;
+    }
+};
+
+class Identifier : public Expression {
+    string identifier;
+
+public:
+    Identifier(const string& i) :
+        identifier(i)
+    {}
+
+    void repr(ostream& os) const {
+        os << "I:" << identifier;
+    }
+
+    string eval(const SelectorEnv& env) const {
+        return env.value(identifier);
+    }
+
+    bool present(const SelectorEnv& env) const {
+        return env.present(identifier);
+    }
+};
+
+////////////////////////////////////////////////////
+
+// Some operators...
+
+// "="
+class Eq : public EqualityOperator {
+    void repr(ostream& os) const {
+        os << "=";
+    }
+
+    bool eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env) == e2.eval(env);
+    }
+};
+
+// "<>"
+class Neq : public EqualityOperator {
+    void repr(ostream& os) const {
+        os << "<>";
+    }
+
+    bool eval(Expression& e1, Expression& e2, const SelectorEnv& env) const {
+        return e1.eval(env) != e2.eval(env);
+    }
+};
+
+// "IS NULL"
+class IsNull : public UnaryBooleanOperator<Identifier> {
+    void repr(ostream& os) const {
+        os << "IsNull";
+    }
+
+    bool eval(Identifier& i, const SelectorEnv& env) const {
+        return !i.present(env);
+    }
+};
+
+// "IS NOT NULL"
+class IsNonNull : public UnaryBooleanOperator<Identifier> {
+    void repr(ostream& os) const {
+        os << "IsNonNull";
+    }
+
+    bool eval(Identifier& i, const SelectorEnv& env) const {
+        return i.present(env);
+    }
+};
+
+// "NOT"
+class Not : public UnaryBooleanOperator<BoolExpression> {
+    void repr(ostream& os) const {
+        os << "NOT";
+    }
+
+    bool eval(BoolExpression& e, const SelectorEnv& env) const {
+        return !e.eval(env);
+    }
+};
+
+Eq eqOp;
+Neq neqOp;
+IsNull isNullOp;
+IsNonNull isNonNullOp;
+Not notOp;
+
+////////////////////////////////////////////////////
+
+// Top level parser
+BoolExpression* parseTopBoolExpression(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));
+    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 b.release();
+}
+
+BoolExpression* parseOrExpression(Tokeniser& tokeniser)
+{
+    std::auto_ptr<BoolExpression> 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));
+        if (!e2.get()) return 0;
+        e.reset(new OrExpression(e1.release(), e2.release()));
+    }
+    tokeniser.returnTokens();
+    return e.release();
+}
+
+BoolExpression* parseAndExpression(Tokeniser& tokeniser)
+{
+    std::auto_ptr<BoolExpression> e(parseEqualityExpression(tokeniser));
+    if (!e.get()) return 0;
+    while ( tokeniser.nextToken().type==T_AND ) {
+        std::auto_ptr<BoolExpression> e1(e);
+        std::auto_ptr<BoolExpression> e2(parseEqualityExpression(tokeniser));
+        if (!e2.get()) return 0;
+        e.reset(new AndExpression(e1.release(), e2.release()));
+    }
+    tokeniser.returnTokens();
+    return e.release();
+}
+
+BoolExpression* parseEqualityExpression(Tokeniser& tokeniser)
+{
+    const Token t = tokeniser.nextToken();
+    if ( t.type==T_IDENTIFIER ) {
+        // Check for "IS NULL" and "IS NOT NULL"
+        if ( tokeniser.nextToken().type==T_IS ) {
+            // The rest must be T_NULL or T_NOT, T_NULL
+            switch (tokeniser.nextToken().type) {
+            case T_NULL:
+                return new UnaryBooleanExpression<Identifier>(&isNullOp, new Identifier(t.val));
+            case T_NOT:
+                if ( tokeniser.nextToken().type == T_NULL)
+                    return new UnaryBooleanExpression<Identifier>(&isNonNullOp, new Identifier(t.val));
+            default:
+                return 0;
+            }
+        }
+        tokeniser.returnTokens();
+    } else 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(parseEqualityExpression(tokeniser));
+        if (!e.get()) return 0;
+        return new UnaryBooleanExpression<BoolExpression>(&notOp, e.release());
+    }
+
+    tokeniser.returnTokens();
+    std::auto_ptr<Expression> e1(parsePrimaryExpression(tokeniser));
+    if (!e1.get()) return 0;
+
+    const Token op = tokeniser.nextToken();
+    if (op.type != T_OPERATOR) {
+        return 0;
+    }
+
+    std::auto_ptr<Expression> e2(parsePrimaryExpression(tokeniser));
+    if (!e2.get()) return 0;
+
+    if (op.val == "=") return new EqualityExpression(&eqOp, e1.release(), e2.release());
+    if (op.val == "<>") return new EqualityExpression(&neqOp, e1.release(), e2.release());
+
+    return 0;
+}
+
+Expression* parsePrimaryExpression(Tokeniser& tokeniser)
+{
+    const Token& t = tokeniser.nextToken();
+    switch (t.type) {
+        case T_IDENTIFIER:
+            return new Identifier(t.val);
+        case T_STRING:
+            return new Literal(t.val);
+        default:
+            return 0;
+    }
+}
+
+}}
diff --git a/cpp/src/qpid/broker/SelectorExpression.h b/cpp/src/qpid/broker/SelectorExpression.h
new file mode 100644
index 0000000000..be73d4876c
--- /dev/null
+++ b/cpp/src/qpid/broker/SelectorExpression.h
@@ -0,0 +1,58 @@
+#ifndef QPID_BROKER_SELECTOREXPRESSION_H
+#define QPID_BROKER_SELECTOREXPRESSION_H
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <iosfwd>
+#include <string>
+
+namespace qpid {
+namespace broker {
+
+class SelectorEnv;
+class Tokeniser;
+
+class Expression {
+public:
+    virtual ~Expression() {}
+    virtual void repr(std::ostream&) const = 0;
+    virtual std::string eval(const SelectorEnv&) const = 0;
+};
+
+class BoolExpression {
+public:
+    virtual ~BoolExpression() {};
+    virtual void repr(std::ostream&) const = 0;
+    virtual bool eval(const SelectorEnv&) const = 0;
+};
+
+BoolExpression* parseTopBoolExpression(const std::string& exp);
+BoolExpression* parseBoolExpression(Tokeniser&);
+BoolExpression* parseOrExpression(Tokeniser&);
+BoolExpression* parseAndExpression(Tokeniser&);
+BoolExpression* parseNotExpression(Tokeniser&);
+BoolExpression* parseEqualityExpression(Tokeniser&);
+Expression* parsePrimaryExpression(Tokeniser&);
+
+}}
+
+#endif
diff --git a/cpp/src/qpid/broker/SelectorToken.cpp b/cpp/src/qpid/broker/SelectorToken.cpp
new file mode 100644
index 0000000000..6215f169d3
--- /dev/null
+++ b/cpp/src/qpid/broker/SelectorToken.cpp
@@ -0,0 +1,273 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/broker/SelectorToken.h"
+
+#include <string>
+#include <algorithm>
+#include <iostream>
+#include <cassert>
+
+namespace qpid {
+namespace broker {
+
+// Tokeniserss always take string const_iterators to mark the beginning and end of the string being tokenised
+// if the tokenise is successful then the start iterator is advanced, if the tokenise fails then the start
+// iterator is unchanged.
+
+std::ostream& operator<<(std::ostream& os, const Token& t)
+{
+    os << "T<" << t.type << ", " << t.val << ">";
+    return os;
+}
+
+TokenException::TokenException(const std::string& msg) :
+    range_error(msg)
+{}
+
+// Not much of a parser...
+void skipWS(std::string::const_iterator& s, std::string::const_iterator& e)
+{
+    while ( s!=e && std::isspace(*s) ) {
+        ++s;
+    }
+}
+
+bool tokeniseEos(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    if ( s!=e ) return false;
+
+    tok = Token(T_EOS, "");
+    return true;
+}
+
+inline bool isIdentifierStart(char c)
+{
+    return std::isalpha(c) || c=='_' || c=='$';
+}
+
+inline bool isIdentifierPart(char c)
+{
+    return std::isalnum(c) || c=='_' || c=='$' || c=='.';
+}
+
+bool tokeniseIdentifier(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    // Be sure that first char is alphanumeric or _ or $
+    if ( s==e || !isIdentifierStart(*s) ) return false;
+
+    std::string::const_iterator t = s;
+
+    while ( s!=e && isIdentifierPart(*++s) );
+
+    tok = Token(T_IDENTIFIER, t, s);
+
+    return true;
+}
+
+// Lexically, reserved words are a subset of identifiers
+// so we parse an identifier first then check if it is a reserved word and
+// convert it if it is a reserved word
+namespace {
+
+struct RWEntry {
+    const char* word;
+    TokenType type;
+};
+
+bool caseless(const char* s1, const char* s2)
+{
+    do {
+        char ls1 = std::tolower(*s1);
+        char ls2 = std::tolower(*s2);
+        if (ls1<ls2)
+            return true;
+        else if (ls1>ls2)
+            return false;
+    } while ( *s1++ && *s2++ );
+    // Equal
+    return false;
+}
+
+bool operator<(const RWEntry& r, const char* rhs) {
+    return caseless(r.word, rhs);
+}
+
+bool operator<(const char* rhs, const RWEntry& r) {
+    return caseless(rhs, r.word);
+}
+
+}
+
+bool tokeniseReservedWord(Token& tok)
+{
+    // This must be sorted!!
+    static const RWEntry reserved[] = {
+        {"and", T_AND},
+        {"between", T_BETWEEN},
+        {"escape", T_ESCAPE},
+        {"false", T_FALSE},
+        {"in", T_IN},
+        {"is", T_IS},
+        {"like", T_LIKE},
+        {"not", T_NOT},
+        {"null", T_NULL},
+        {"or", T_OR},
+        {"true", T_TRUE}
+    };
+
+    const int reserved_size = sizeof(reserved)/sizeof(RWEntry);
+
+    if ( tok.type != T_IDENTIFIER ) return false;
+
+    std::pair<const RWEntry*, const RWEntry*> entry = std::equal_range(&reserved[0], &reserved[reserved_size], tok.val.c_str());
+
+    if ( entry.first==entry.second ) return false;
+
+    tok.type = entry.first->type;
+    return true;
+}
+
+// This is really only used for testing
+bool tokeniseReservedWord(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    std::string::const_iterator p = s;
+    bool r = tokeniseIdentifier(p, e, tok) && tokeniseReservedWord(tok);
+    if (r) s = p;
+    return r;
+}
+
+bool tokeniseIdentifierOrReservedWord(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    bool r = tokeniseIdentifier(s, e, tok);
+    if (r) (void) tokeniseReservedWord(tok);
+    return r;
+}
+
+// parsing strings is complicated by the need to allow "''" as an embedded single quote
+bool tokeniseString(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    if ( s==e || *s != '\'' ) return false;
+
+    std::string::const_iterator q = std::find(s+1, e, '\'');
+    if ( q==e ) return false;
+
+    std::string content(s+1, q);
+    ++q;
+
+    while ( q!=e && *q=='\'' ) {
+        std::string::const_iterator p = q;
+        q = std::find(p+1, e, '\'');
+        if ( q==e ) return false;
+        content += std::string(p, q);
+        ++q;
+    }
+
+    s = q;
+    tok = Token(T_STRING, content);
+    return true;
+}
+
+bool tokeniseParens(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    if ( s==e) return false;
+    if ( *s=='(' ) {
+        tok = Token (T_LPAREN, s, s+1);
+        ++s;
+        return true;
+    }
+    if ( *s==')' ) {
+        tok = Token (T_RPAREN, s, s+1);
+        ++s;
+        return true;
+    }
+    return false;
+}
+
+inline bool isOperatorPart(char c)
+{
+    return !std::isalnum(c) && !std::isspace(c) && c!='_' && c!='$' && c!='(' && c!=')' && c!= '\'';
+}
+
+// These lexical tokens contain no alphanumerics - this is broader than actual operators but
+// works.
+bool tokeniseOperator(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok)
+{
+    if ( s==e || !isOperatorPart(*s) ) return false;
+
+    std::string::const_iterator t = s;
+
+    while (s!=e && isOperatorPart(*++s));
+
+    tok = Token(T_OPERATOR, t, s);
+    return true;
+}
+
+// Can't parse numerics yet
+bool tokeniseNumeric(std::string::const_iterator& /*s*/, std::string::const_iterator& /*e*/, Token& /*tok*/)
+{
+    return false;
+}
+
+Tokeniser::Tokeniser(const std::string::const_iterator& s, const std::string::const_iterator& e) :
+    tokp(0),
+    inp(s),
+    inEnd(e)
+{
+}
+
+/**
+ * Skip any whitespace then look for a token, throwing an exception if no valid token
+ * is found.
+ *
+ * Advance the string iterator past the parsed token on success. On failure the string iterator is 
+ * in an undefined location.
+ */
+const Token& Tokeniser::nextToken()
+{
+    if ( tokens.size()>tokp ) return tokens[tokp++];
+
+    // Don't extend stream of tokens further than the end of stream;
+    if ( tokp>0 && tokens[tokp-1].type==T_EOS ) return tokens[tokp-1];
+
+    skipWS(inp, inEnd);
+
+    tokens.push_back(Token());
+    Token& tok = tokens[tokp++];
+
+    if (tokeniseEos(inp, inEnd, tok)) return tok;
+    if (tokeniseIdentifierOrReservedWord(inp, inEnd, tok)) return tok;
+    if (tokeniseNumeric(inp, inEnd, tok)) return tok;
+    if (tokeniseString(inp, inEnd, tok)) return tok;
+    if (tokeniseParens(inp, inEnd, tok)) return tok;
+    if (tokeniseOperator(inp, inEnd, tok)) return tok;
+
+    throw TokenException("Found illegal character");
+}
+
+void Tokeniser::returnTokens(unsigned int n)
+{
+    assert( n<=tokp );
+    tokp-=n;
+}
+
+
+}}
diff --git a/cpp/src/qpid/broker/SelectorToken.h b/cpp/src/qpid/broker/SelectorToken.h
new file mode 100644
index 0000000000..03a7ca63cc
--- /dev/null
+++ b/cpp/src/qpid/broker/SelectorToken.h
@@ -0,0 +1,116 @@
+#ifndef QPID_BROKER_SELECTORTOKEN_H
+#define QPID_BROKER_SELECTORTOKEN_H
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <iosfwd>
+#include <string>
+#include <stdexcept>
+#include <vector>
+
+namespace qpid {
+namespace broker {
+
+typedef enum {
+    T_EOS,
+    T_NULL,
+    T_TRUE,
+    T_FALSE,
+    T_NOT,
+    T_AND,
+    T_OR,
+    T_IN,
+    T_IS,
+    T_BETWEEN,
+    T_LIKE,
+    T_ESCAPE,
+    T_IDENTIFIER,
+    T_STRING,
+    T_NUMERIC_EXACT,
+    T_NUMERIC_APPROX,
+    T_LPAREN,
+    T_RPAREN,
+    T_OPERATOR
+} TokenType;
+
+struct Token {
+    TokenType type;
+    std::string val;
+
+    Token()
+    {}
+
+    Token(TokenType t, const std::string& v) :
+        type(t),
+        val(v)
+    {}
+
+    Token(TokenType t, const std::string::const_iterator& s, const std::string::const_iterator& e) :
+    type(t),
+    val(std::string(s,e))
+    {}
+
+    bool operator==(const Token& r) const
+    {
+        return type == r.type && val == r.val;
+    }
+};
+
+std::ostream& operator<<(std::ostream& os, const Token& t);
+
+class TokenException : public std::range_error {
+public:
+    TokenException(const std::string&);
+};
+
+bool tokeniseEos(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseIdentifier(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseReservedWord(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseIdentifierOrReservedWord(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseString(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseParens(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseOperator(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+bool tokeniseNumeric(std::string::const_iterator& s, std::string::const_iterator& e, Token& tok);
+
+class Tokeniser {
+    std::vector<Token> tokens;
+    unsigned int tokp;
+
+    std::string::const_iterator inp;
+    std::string::const_iterator inEnd;
+
+public:
+    Tokeniser(const std::string::const_iterator& s, const std::string::const_iterator& e);
+    void returnTokens(unsigned int n = 1);
+    const Token& nextToken();
+};
+
+}}
+
+#endif
\ No newline at end of file
diff --git a/cpp/src/tests/CMakeLists.txt b/cpp/src/tests/CMakeLists.txt
index 1c357eeec2..973421ed61 100644
--- a/cpp/src/tests/CMakeLists.txt
+++ b/cpp/src/tests/CMakeLists.txt
@@ -135,6 +135,7 @@ set(all_unit_tests
     RangeSet
     RefCounted
     RetryList
+    Selector
     SequenceNumberTest
     SequenceSet
     SessionState
diff --git a/cpp/src/tests/Makefile.am b/cpp/src/tests/Makefile.am
index 3513e0a6d6..69ca01a934 100644
--- a/cpp/src/tests/Makefile.am
+++ b/cpp/src/tests/Makefile.am
@@ -121,6 +121,7 @@ unit_test_SOURCES= unit_test.cpp unit_test.h \
 	ClientMessage.cpp \
 	Qmf2.cpp \
 	BrokerOptions.cpp \
+	Selector.cpp \
 	SystemInfo.cpp
 
 if HAVE_XML
diff --git a/cpp/src/tests/Selector.cpp b/cpp/src/tests/Selector.cpp
new file mode 100644
index 0000000000..25080f3482
--- /dev/null
+++ b/cpp/src/tests/Selector.cpp
@@ -0,0 +1,220 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/broker/SelectorToken.h"
+#include "qpid/broker/Selector.h"
+
+#include "unit_test.h"
+
+#include <string>
+#include <map>
+
+using std::string;
+using std::map;
+
+namespace qb = qpid::broker;
+
+using qpid::broker::Token;
+using qpid::broker::TokenType;
+using qpid::broker::Tokeniser;
+using qpid::broker::tokeniseEos;
+using qpid::broker::tokeniseIdentifier;
+using qpid::broker::tokeniseIdentifierOrReservedWord;
+using qpid::broker::tokeniseReservedWord;
+using qpid::broker::tokeniseOperator;
+using qpid::broker::tokeniseParens;
+using qpid::broker::tokeniseNumeric;
+using qpid::broker::tokeniseString;
+
+namespace qpid {
+namespace tests {
+
+QPID_AUTO_TEST_SUITE(SelectorSuite)
+
+typedef bool (*TokeniseF)(string::const_iterator&,string::const_iterator&,Token&);
+
+void verifyTokeniserSuccess(TokeniseF t, const char* ss, TokenType tt, const char* tv, const char* fs) {
+    Token tok;
+    string s(ss);
+    string::const_iterator sb = s.begin();
+    string::const_iterator se = s.end();
+    BOOST_CHECK(t(sb, se, tok));
+    BOOST_CHECK_EQUAL(tok, Token(tt, tv));
+    BOOST_CHECK_EQUAL(string(sb, se), fs);
+}
+
+void verifyTokeniserFail(TokeniseF t, const char* c) {
+    Token tok;
+    string s(c);
+    string::const_iterator sb = s.begin();
+    string::const_iterator se = s.end();
+    BOOST_CHECK(!t(sb, se, tok));
+    BOOST_CHECK_EQUAL(string(sb, se), c);
+}
+
+QPID_AUTO_TEST_CASE(tokeniseSuccess)
+{
+    verifyTokeniserSuccess(&tokeniseEos, "", qb::T_EOS, "", "");
+    verifyTokeniserSuccess(&tokeniseIdentifier, "null_123+blah", qb::T_IDENTIFIER, "null_123", "+blah");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "null_123+blah", qb::T_IDENTIFIER, "null_123", "+blah");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "null+blah", qb::T_NULL, "null", "+blah");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "null+blah", qb::T_NULL, "null", "+blah");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "Is nOt null", qb::T_IS, "Is", " nOt null");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "nOt null", qb::T_NOT, "nOt", " null");
+    verifyTokeniserSuccess(&tokeniseIdentifierOrReservedWord, "Is nOt null", qb::T_IS, "Is", " nOt null");
+    verifyTokeniserSuccess(&tokeniseString, "'Hello World'", qb::T_STRING, "Hello World", "");
+    verifyTokeniserSuccess(&tokeniseString, "'Hello World''s end'a bit more", qb::T_STRING, "Hello World's end", "a bit more");
+    verifyTokeniserSuccess(&tokeniseOperator, "=blah", qb::T_OPERATOR, "=", "blah");
+    verifyTokeniserSuccess(&tokeniseOperator, "<> Identifier", qb::T_OPERATOR, "<>", " Identifier");
+    verifyTokeniserSuccess(&tokeniseParens, "(a and b) not c", qb::T_LPAREN, "(", "a and b) not c");
+    verifyTokeniserSuccess(&tokeniseParens, ") not c", qb::T_RPAREN, ")", " not c");
+}
+
+QPID_AUTO_TEST_CASE(tokeniseFailure)
+{
+    verifyTokeniserFail(&tokeniseEos, "hb23");
+    verifyTokeniserFail(&tokeniseIdentifier, "123");
+    verifyTokeniserFail(&tokeniseIdentifier, "'Embedded 123'");
+    verifyTokeniserFail(&tokeniseReservedWord, "1.2e5");
+    verifyTokeniserFail(&tokeniseReservedWord, "'Stringy thing'");
+    verifyTokeniserFail(&tokeniseReservedWord, "oR_andsomething");
+    verifyTokeniserFail(&tokeniseString, "'Embedded 123");
+    verifyTokeniserFail(&tokeniseString, "'This isn''t fair");
+    verifyTokeniserFail(&tokeniseOperator, "123");
+    verifyTokeniserFail(&tokeniseOperator, "'Stringy thing'");
+    verifyTokeniserFail(&tokeniseOperator, "NoT");
+    verifyTokeniserFail(&tokeniseOperator, "(a and b)");
+    verifyTokeniserFail(&tokeniseOperator, ")");
+    verifyTokeniserFail(&tokeniseParens, "=");
+    verifyTokeniserFail(&tokeniseParens, "what ho!");
+}
+
+QPID_AUTO_TEST_CASE(tokenString)
+{
+
+    string exp("  a =b");
+    string::const_iterator s = exp.begin();
+    string::const_iterator e = exp.end();
+    Tokeniser t(s, e);
+
+    BOOST_CHECK_EQUAL(t.nextToken(), Token(qb::T_IDENTIFIER, "a"));
+    BOOST_CHECK_EQUAL(t.nextToken(), Token(qb::T_OPERATOR, "="));
+    BOOST_CHECK_EQUAL(t.nextToken(), Token(qb::T_IDENTIFIER, "b"));
+    BOOST_CHECK_EQUAL(t.nextToken(), Token(qb::T_EOS, ""));
+
+    exp = " not 'hello kitty''s friend' = Is null       ";
+    s = exp.begin();
+    e = exp.end();
+    Tokeniser u(s, e);
+
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_NOT, "not"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_STRING, "hello kitty's friend"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_OPERATOR, "="));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_IS, "Is"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_NULL, "null"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_EOS, ""));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_EOS, ""));
+
+    u.returnTokens(3);
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_IS, "Is"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_NULL, "null"));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_EOS, ""));
+    BOOST_CHECK_EQUAL(u.nextToken(), Token(qb::T_EOS, ""));
+}
+
+QPID_AUTO_TEST_CASE(parseStringFail)
+{
+    BOOST_CHECK_THROW(qb::Selector e("'Daft' is not null"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A is null not"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A is null or not"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A is null or and"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A is null and 'hello out there'"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A is null and (B='hello out there'"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("in='hello kitty'"), std::range_error);
+}
+
+class TestSelectorEnv : public qpid::broker::SelectorEnv {
+    map<string, string> values;
+
+    bool present(const std::string& v) const {
+        return values.find(v)!=values.end();
+    }
+
+    std::string value(const std::string& v) const {
+        return present(v) ? values.at(v) : "";
+    }
+
+public:
+    void set(const string& id, const string& value) {
+        values[id] = value;
+    }
+};
+
+QPID_AUTO_TEST_CASE(parseString)
+{
+    qb::Selector a("A is not null");
+    qb::Selector a1("A is null");
+    qb::Selector a2("A = C");
+    qb::Selector a3("A <> C");
+    qb::Selector c("C is not null");
+    qb::Selector c1("C is null");
+    qb::Selector d("A='hello kitty'");
+    qb::Selector e("A<>'hello kitty'");
+    qb::Selector f("A=B");
+    qb::Selector g("A<>B");
+    qb::Selector h("A='hello kitty' OR B='Bye, bye cruel world'");
+    qb::Selector i("B='hello kitty' OR A='Bye, bye cruel world'");
+    qb::Selector j("B='hello kitty' AnD A='Bye, bye cruel world'");
+    qb::Selector k("B='hello kitty' AnD B='Bye, bye cruel world'");
+    qb::Selector a4("A is null or A='Bye, bye cruel world'");
+    qb::Selector a5("Z is null OR A is not null and A<>'Bye, bye cruel world'");
+    qb::Selector a6("(Z is null OR A is not null) and A<>'Bye, bye cruel world'");
+    qb::Selector t("NOT C is not null OR C is null");
+    qb::Selector n("Not A='' or B=z");
+
+    TestSelectorEnv env;
+    env.set("A", "Bye, bye cruel world");
+    env.set("B", "hello kitty");
+
+    BOOST_CHECK(a.eval(env));
+    BOOST_CHECK(!a1.eval(env));
+    BOOST_CHECK(!a2.eval(env));
+    BOOST_CHECK(a3.eval(env));
+    BOOST_CHECK(!c.eval(env));
+    BOOST_CHECK(c1.eval(env));
+    BOOST_CHECK(!d.eval(env));
+    BOOST_CHECK(e.eval(env));
+    BOOST_CHECK(!f.eval(env));
+    BOOST_CHECK(g.eval(env));
+    BOOST_CHECK(!h.eval(env));
+    BOOST_CHECK(i.eval(env));
+    BOOST_CHECK(j.eval(env));
+    BOOST_CHECK(!k.eval(env));
+    BOOST_CHECK(a4.eval(env));
+    BOOST_CHECK(a5.eval(env));
+    BOOST_CHECK(!a6.eval(env));
+    BOOST_CHECK(t.eval(env));
+    BOOST_CHECK(n.eval(env));
+}
+
+QPID_AUTO_TEST_SUITE_END()
+
+}}