QPID-4622: Implement 'LIKE' string matching operations in selector

- This implements <expression> [NOT] LIKE <string> [ESCAPE <character>]
- The implementation uses the posix regex library (in BRE mode) on
  Unix systems
- It uses std::tr1::regex on Visual Studio (in std::tr1::regex::basic mode)

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

4 files changed, 227 insertions, 18 deletions

diff --git a/qpid/cpp/src/Makefile.am b/qpid/cpp/src/Makefile.am
index 9ec883839e..1b2d0fcbb4 100644
--- a/qpid/cpp/src/Makefile.am
+++ b/qpid/cpp/src/Makefile.am
@@ -497,6 +497,7 @@ libqpidcommon_la_SOURCES +=			\
   qpid/sys/PollableQueue.h			\
   qpid/sys/Poller.h				\
   qpid/sys/Probes.h				\
+  qpid/sys/regex.h				\
   qpid/sys/Runnable.cpp				\
   qpid/sys/ScopedIncrement.h			\
   qpid/sys/SecurityLayer.h			\
diff --git a/qpid/cpp/src/qpid/broker/SelectorExpression.cpp b/qpid/cpp/src/qpid/broker/SelectorExpression.cpp
index 8fcafeb2a1..5b8621b518 100644
--- a/qpid/cpp/src/qpid/broker/SelectorExpression.cpp
+++ b/qpid/cpp/src/qpid/broker/SelectorExpression.cpp
@@ -25,6 +25,7 @@
 #include "qpid/broker/SelectorToken.h"
 #include "qpid/broker/SelectorValue.h"
 #include "qpid/sys/IntegerTypes.h"
+#include "qpid/sys/regex.h"
 
 #include <string>
 #include <memory>
@@ -65,22 +66,25 @@
  * AndExpression :: = EqualityExpression ( "AND" EqualityExpression  )*
  *
  * ComparisonExpression ::= PrimaryExpression "IS" "NULL" |
- *                        PrimaryExpression "IS" "NOT" "NULL" |
- *                        PrimaryExpression ComparisonOpsOps PrimaryExpression |
- *                        "NOT" ComparisonExpression |
- *                        "(" OrExpression ")"
+ *                          PrimaryExpression "IS" "NOT" "NULL" |
+ *                          PrimaryExpression "LIKE" LiteralString [ "ESCAPE" LiteralString ]
+ *                          PrimaryExpression "NOT" "LIKE" LiteralString [ "ESCAPE" LiteralString ]
+ *                          PrimaryExpression ComparisonOpsOps PrimaryExpression |
+ *                          "NOT" ComparisonExpression |
+ *                          "(" OrExpression ")"
  *
  * PrimaryExpression :: = Identifier |
  *                        Literal
  *
  */
 
-namespace qpid {
-namespace broker {
 
 using std::string;
 using std::ostream;
 
+namespace qpid {
+namespace broker {
+
 class Expression {
 public:
     virtual ~Expression() {}
@@ -237,11 +241,83 @@ public:
         os << *op << "(" << *e1 << ")";
     }
 
-    virtual BoolOrNone eval_bool(const SelectorEnv& env) const {
+    BoolOrNone eval_bool(const SelectorEnv& env) const {
         return op->eval(*e1, env);
     }
 };
 
+class LikeExpression : public BoolExpression {
+    boost::scoped_ptr<Expression> e;
+    string reString;
+    qpid::sys::regex regexBuffer;
+
+    static string toRegex(const string& s, const string& escape) {
+        string regex("^");
+        if (escape.size()>1) throw std::range_error("Illegal escape char");
+        char e = 0;
+        if (escape.size()==1) {
+            e = escape[0];
+        }
+        // Translate % -> .*, _ -> ., . ->\. *->\*
+        bool doEscape = false;
+        for (string::const_iterator i = s.begin(); i!=s.end(); ++i) {
+            if ( e!=0 && *i==e ) {
+                doEscape = true;
+                continue;
+            }
+            switch(*i) {
+                case '%':
+                    if (doEscape) regex += *i;
+                    else regex += ".*";
+                    break;
+                case '_':
+                    if (doEscape) regex += *i;
+                    else regex += ".";
+                    break;
+                case ']':
+                    regex += "[]]";
+                    break;
+                case '-':
+                    regex += "[-]";
+                    break;
+                // Don't add any more cases here: these are sufficient,
+                // adding more might turn on inadvertent matching
+                case '\\':
+                case '^':
+                case '$':
+                case '.':
+                case '*':
+                case '[':
+                    regex += "\\";
+                    // Fallthrough
+                default:
+                    regex += *i;
+                    break;
+            }
+            doEscape = false;
+        }
+        regex += "$";
+        return regex;
+    }
+
+public:
+    LikeExpression(Expression* e_, const string& like, const string& escape="") :
+        e(e_),
+        reString(toRegex(like, escape)),
+        regexBuffer(reString)
+    {}
+
+    void repr(ostream& os) const {
+        os << *e << " REGEX_MATCH '" << reString << "'";
+    }
+
+    BoolOrNone eval_bool(const SelectorEnv& env) const {
+        Value v(e->eval(env));
+        if ( v.type!=Value::T_STRING ) return BN_UNKNOWN;
+        return BoolOrNone(qpid::sys::regex_match(*v.s, regexBuffer));
+    }
+};
+
 // Expression types...
 
 class Literal : public Expression {
@@ -490,6 +566,32 @@ BoolExpression* parseAndExpression(Tokeniser& tokeniser)
     return e.release();
 }
 
+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 ) {
+                // Check for "ESCAPE"
+                if ( tokeniser.nextToken().type==T_ESCAPE ) {
+                    const Token e = tokeniser.nextToken();
+                    if ( e.type==T_STRING ) {
+                        return new LikeExpression(e1.release(), t.val, e.val);
+                    } else {
+                        return 0;
+                    }
+                } else {
+                    tokeniser.returnTokens();
+                    return new LikeExpression(e1.release(), t.val);
+                }
+            } else {
+                return 0;
+            }
+        }
+        default:
+            return 0;
+    }
+}
+
 BoolExpression* parseComparisonExpression(Tokeniser& tokeniser)
 {
     const Token t = tokeniser.nextToken();
@@ -508,18 +610,32 @@ BoolExpression* parseComparisonExpression(Tokeniser& tokeniser)
     std::auto_ptr<Expression> e1(parsePrimaryExpression(tokeniser));
     if (!e1.get()) return 0;
 
-    // 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<Expression>(&isNullOp, e1.release());
-            case T_NOT:
-                if ( tokeniser.nextToken().type == T_NULL)
-                    return new UnaryBooleanExpression<Expression>(&isNonNullOp, e1.release());
-            default:
-                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_LIKE: {
+            tokeniser.returnTokens();
+            std::auto_ptr<BoolExpression> e(parseSpecialComparisons(tokeniser, e1));
+            if (!e.get()) return 0;
+            return e.release();
+        }
+        default:
+            break;
     }
     tokeniser.returnTokens();
 
diff --git a/qpid/cpp/src/qpid/sys/regex.h b/qpid/cpp/src/qpid/sys/regex.h
new file mode 100644
index 0000000000..2c5206112a
--- /dev/null
+++ b/qpid/cpp/src/qpid/sys/regex.h
@@ -0,0 +1,81 @@
+#ifndef QPID_SYS_REGEX_H
+#define QPID_SYS_REGEX_H
+
+/*
+ *
+ * Copyright (c) 2006 The Apache Software Foundation
+ *
+ * Licensed 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.
+ *
+ */
+
+#ifdef _POSIX_SOURCE
+# include <stdexcept>
+# include <string>
+# include <regex.h>
+#elif defined(_MSC_VER)
+# include <regex>
+#else
+#error "No known regex implementation"
+#endif
+
+// This is a very simple wrapper for Basic Regular Expression facilities either
+// provided by POSIX or C++ tr1
+//
+// Matching expressions are not supported and so the only useful operation is
+// a simple boolean match indicator.
+
+namespace qpid {
+namespace sys {
+
+#ifdef _POSIX_SOURCE
+
+class regex {
+    ::regex_t re;
+
+public:
+    regex(const std::string& s) {
+        int rc = ::regcomp(&re, s.c_str(), REG_NOSUB);
+        if (rc != 0) throw std::logic_error("Regular expression compilation error");
+    }
+
+    ~regex() {
+        ::regfree(&re);
+    }
+
+    friend bool regex_match(const std::string& s, const regex& re);
+};
+
+bool regex_match(const std::string& s, const regex& re) {
+    return ::regexec(&(re.re), s.c_str(), 0, 0, 0)==0;
+}
+
+#elif defined(_MSC_VER)
+
+class regex : public std::tr1::regex {
+public:
+    regex(const std::string& s) :
+        std::tr1::regex(s, std::tr1::regex::basic)
+    {}
+};
+
+using std::tr1::regex_match;
+
+#else
+#error "No known regex implementation"
+#endif
+
+}}
+
+
+#endif
diff --git a/qpid/cpp/src/tests/Selector.cpp b/qpid/cpp/src/tests/Selector.cpp
index ba99c9e3f0..7208f80e85 100644
--- a/qpid/cpp/src/tests/Selector.cpp
+++ b/qpid/cpp/src/tests/Selector.cpp
@@ -182,6 +182,10 @@ QPID_AUTO_TEST_CASE(parseStringFail)
     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);
+    BOOST_CHECK_THROW(qb::Selector e("A like 234"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A not 234 escape"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A not like 'eclecti_' escape 'happy'"), std::range_error);
+    BOOST_CHECK_THROW(qb::Selector e("A not like 'eclecti_' escape happy"), std::range_error);
 }
 
 class TestSelectorEnv : public qpid::broker::SelectorEnv {
@@ -233,6 +237,9 @@ QPID_AUTO_TEST_CASE(parseString)
     BOOST_CHECK_NO_THROW(qb::Selector e("Not A='' or B=z"));
     BOOST_CHECK_NO_THROW(qb::Selector e("Not A=17 or B=5.6"));
     BOOST_CHECK_NO_THROW(qb::Selector e("A<>17 and B=5.6e17"));
+    BOOST_CHECK_NO_THROW(qb::Selector e("A LIKE 'excep%ional'"));
+    BOOST_CHECK_NO_THROW(qb::Selector e("B NOT LIKE 'excep%ional'"));
+    BOOST_CHECK_NO_THROW(qb::Selector e("A LIKE 'excep%ional' EScape '\'"));
 }
 
 QPID_AUTO_TEST_CASE(simpleEval)
@@ -267,6 +274,10 @@ QPID_AUTO_TEST_CASE(simpleEval)
     BOOST_CHECK(!qb::Selector("C=D").eval(env));
     BOOST_CHECK(qb::Selector("13 is not null").eval(env));
     BOOST_CHECK(!qb::Selector("'boo!' is null").eval(env));
+    BOOST_CHECK(qb::Selector("A LIKE '%cru_l%'").eval(env));
+    BOOST_CHECK(qb::Selector("'_%%_hello.th_re%' LIKE 'z_%.%z_%z%' escape 'z'").eval(env));
+    BOOST_CHECK(qb::Selector("A NOT LIKE 'z_%.%z_%z%' escape 'z'").eval(env));
+    BOOST_CHECK(qb::Selector("'{}[]<>,.!\"$%^&*()_-+=?/|\\' LIKE '{}[]<>,.!\"$z%^&*()z_-+=?/|\\' escape 'z'").eval(env));
 }
 
 QPID_AUTO_TEST_CASE(numericEval)