reapack

commit 9a04357da6ce3e27babe3e186b937f460e2942bc
parent 77ca71712b3c6f5b58e3ef3da64c9e653ea7178a
Author: cfillion <cfillion@users.noreply.github.com>
Date:   Fri,  2 Sep 2016 02:58:40 -0400

filter: implement AND grouping ( with parenthesis )

Diffstat:
M
src/filter.cpp
 | 
157
++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------
M
src/filter.hpp
 | 
60
+++++++++++++++++++++++++++++++++++++++++++++++++-----------
M
test/filter.cpp
 | 
30
+++++++++++++++++++++++++++---

3 files changed, 183 insertions(+), 64 deletions(-)
diff --git a/src/filter.cpp b/src/filter.cpp
@@ -22,58 +22,72 @@
 
 using namespace std;
 
+Filter::Filter(const string &input)
+  : m_root(Group::MatchAll)
+{
+  set(input);
+}
+
 void Filter::set(const string &input)
 {
   enum State { Default, DoubleQuote, SingleQuote };
 
   m_input = input;
-  m_tokens.clear();
+  m_root.clear();
 
-  Token token{};
-  vector<Token> group;
+  Group *group = &m_root;
+  auto token = make_shared<Token>();
   State state = Default;
 
-  bool append = false;
-
   auto push = [&] {
-    size_t size = token.buf.size();
+    size_t size = token->buf.size();
 
     if(!size)
       return;
 
-    if(!token.test(QuotedFlag)) {
-      if(token.buf == "OR") {
-        token = Token();
-        append = true;
+    if(!token->test(Token::QuotedFlag)) {
+      if(token->buf == "NOT") {
+        token->buf.clear();
+        token->flags ^= Token::NotFlag;
+        return;
+      }
+      else if(token->buf == "OR") {
+        token->buf.clear();
+        if(!group->empty())
+          group = group->subgroup_any();
+        return;
+      }
+      else if(token->buf == "(") {
+        token->buf.clear();
+        group = group->subgroup_all();
         return;
       }
-      else if(token.buf == "NOT") {
-        token.buf.clear();
-        token.flags ^= NotFlag;
+      else if(token->buf == ")") {
+        token->buf.clear();
+        if(group != &m_root)
+          group = group->parent();
         return;
       }
     }
 
-    if(size > 1 && token.buf[0] == '^') {
-      token.flags |= StartAnchorFlag;
-      token.buf.erase(0, 1);
+    if(size > 1 && token->buf[0] == '^') {
+      token->flags |= Token::StartAnchorFlag;
+      token->buf.erase(0, 1);
       size--;
     }
-    if(size > 1 && token.buf[size - 1] == '$') {
-      token.flags |= EndAnchorFlag;
-      token.buf.erase(size - 1, 1);
+    if(size > 1 && token->buf[size - 1] == '$') {
+      token->flags |= Token::EndAnchorFlag;
+      token->buf.erase(size - 1, 1);
       size--;
     }
 
-    if(append)
-      append = false;
-    else if(!group.empty()) {
-      m_tokens.emplace_back(group);
-      group = vector<Token>();
-    }
+    group->push(token);
+
+    // close previous OR group
+    if(!group->open())
+      group = group->parent();
 
-    group.emplace_back(token);
-    token = Token();
+    token = make_shared<Token>();
   };
 
   for(const char c : input) {
@@ -83,7 +97,7 @@ void Filter::set(const string &input)
       else
         state = DoubleQuote;
 
-      token.flags |= QuotedFlag;
+      token->flags |= Token::QuotedFlag;
     }
     else if(c == '\'' && state != DoubleQuote) {
       if(state == SingleQuote)
@@ -91,47 +105,90 @@ void Filter::set(const string &input)
       else
         state = SingleQuote;
 
-      token.flags |= QuotedFlag;
+      token->flags |= Token::QuotedFlag;
     }
     else if(c == '\x20' && state == Default)
       push();
     else
-      token.buf += c;
+      token->buf += c;
   }
 
   push();
-
-  if(!group.empty())
-    m_tokens.emplace_back(group);
 }
 
 bool Filter::match(const vector<string> &rows) const
 {
-  for(const vector<Token> &group : m_tokens) {
-    bool match = false;
-
-    for(const Token &token : group) {
-      for(const string &str : rows) {
-        if(token.match(str))
-          match = true;
-        else if(token.test(NotFlag)) {
-          match = false;
-          break;
-        }
-      }
+  return m_root.match(rows);
+}
+
+Filter::Group *Filter::Group::subgroup_any()
+{
+  if(m_type == Group::MatchAny) {
+    m_open = true;
+    return this;
+  }
+
+  NodePtr prev;
+  if(!m_nodes.empty()) {
+    prev = m_nodes.back();
+    m_nodes.pop_back();
+  }
+
+  auto newGroup = make_shared<Group>(Group::MatchAny, this);
+  m_nodes.push_back(newGroup);
 
-      if(match)
-        break;
+  if(prev)
+    newGroup->m_nodes.push_back(prev);
+
+  return newGroup.get();
+}
+
+Filter::Group *Filter::Group::subgroup_all()
+{
+  // always make a subgroup of this type
+
+  auto newGroup = make_shared<Group>(Group::MatchAll, this);
+  m_nodes.push_back(newGroup);
+  return newGroup.get();
+}
+
+void Filter::Group::push(const NodePtr &node)
+{
+  m_nodes.push_back(node);
+
+  if(m_type == MatchAny)
+    m_open = false;
+}
+
+bool Filter::Group::match(const vector<string> &rows) const
+{
+  for(const NodePtr &node : m_nodes) {
+    if(node->match(rows)) {
+      if(m_type == MatchAny)
+        return true;
     }
+    else if(m_type == MatchAll)
+      return false;
+  }
+
+  return m_type == MatchAll;
+}
+
+bool Filter::Token::match(const vector<string> &rows) const
+{
+  bool match = false;
 
-    if(!match)
+  for(const string &row : rows) {
+    if(matchRow(row))
+      match = true;
+    else if(test(NotFlag))
       return false;
   }
 
-  return true;
+  return match;
 }
 
-bool Filter::Token::match(const string &str) const
+bool Filter::Token::matchRow(const string &str) const
 {
   bool match = true;
 
diff --git a/src/filter.hpp b/src/filter.hpp
@@ -23,8 +23,7 @@
 
 class Filter {
 public:
-  Filter() {}
-  Filter(const std::string &input) { set(input); }
+  Filter(const std::string & = {});
 
   const std::string get() const { return m_input; }
   void set(const std::string &);
@@ -36,23 +35,62 @@ public:
   bool operator!=(const std::string &f) const { return !(*this == f); }
 
 private:
-  enum Flag {
-    StartAnchorFlag = 1<<0,
-    EndAnchorFlag   = 1<<1,
-    QuotedFlag      = 1<<2,
-    NotFlag         = 1<<3,
+  class Node {
+  public:
+    virtual bool match(const std::vector<std::string> &) const = 0;
   };
 
-  struct Token {
-    std::string buf;
+  typedef std::shared_ptr<Node> NodePtr;
+
+  class Group : public Node {
+  public:
+    enum Type {
+      MatchAll,
+      MatchAny,
+    };
+
+    Group(Type type, Group *parent = nullptr)
+      : m_parent(parent), m_type(type), m_open(true) {}
+
+    Group *parent() const { return m_parent; }
+    Group *subgroup_any();
+    Group *subgroup_all();
+
+    bool empty() const { return m_nodes.empty(); }
+    void clear() { m_nodes.clear(); }
+    void push(const NodePtr &);
+
+    bool open() const { return m_open; }
+    bool match(const std::vector<std::string> &) const override;
+
+  private:
+    Group *m_parent;
+    Type m_type;
+    bool m_open;
+    std::vector<NodePtr> m_nodes;
+  };
+
+  class Token : public Node {
+  public:
+    enum Flag {
+      StartAnchorFlag = 1<<0,
+      EndAnchorFlag   = 1<<1,
+      QuotedFlag      = 1<<2,
+      NotFlag         = 1<<3,
+    };
+
+    Token() : flags(0) {}
+
     int flags;
+    std::string buf;
 
-    bool match(const std::string &) const;
+    bool match(const std::vector<std::string> &) const override;
+    bool matchRow(const std::string &) const;
     bool test(Flag f) const { return (flags & f) != 0; }
   };
 
   std::string m_input;
-  std::vector<std::vector<Token> > m_tokens;
+  Group m_root;
 };
 
 #endif
diff --git a/test/filter.cpp b/test/filter.cpp
@@ -8,6 +8,7 @@ static const char *M = "[filter]";
 
 TEST_CASE("basic matching", M) {
   Filter f;
+  REQUIRE(f.match({}));
   REQUIRE(f.match({"world"}));
 
   f.set("hello");
@@ -201,6 +202,19 @@ TEST_CASE("OR operator", M) {
     REQUIRE_FALSE(f.match({"hello world"}));
     REQUIRE(f.match({"hello OR bacon"}));
   }
+
+  SECTION("reset") {
+    f.set("hello OR bacon world");
+
+    REQUIRE_FALSE(f.match({"world"}));
+    REQUIRE(f.match({"hello world"}));
+    REQUIRE(f.match({"bacon world"}));
+  }
+
+  SECTION("single") {
+    f.set("OR");
+    REQUIRE(f.match({"anything"}));
+  }
 }
 
 TEST_CASE("NOT operator", M) {
@@ -240,8 +254,18 @@ TEST_CASE("NOT operator", M) {
   }
 }
 
-TEST_CASE("empty filter", M) {
-  const Filter f("");
+TEST_CASE("AND grouping", M) {
+  Filter f;
 
-  REQUIRE(f.match({"hello world"}));
+  SECTION("normal") {
+    f.set("( hello world ) OR ( NOT hello bacon )");
+
+    REQUIRE(f.match({"hello world"}));
+    REQUIRE(f.match({"chunky bacon"}));
+    REQUIRE_FALSE(f.match({"hello chunky bacon"}));
+  }
+
+  SECTION("close without opening") {
+    f.set(") test");
+  }
 }