commit 3757ac72991202f18c674b423ed94186f4f3d562
parent 9a04357da6ce3e27babe3e186b937f460e2942bc
Author: cfillion <cfillion@users.noreply.github.com>
Date: Fri, 2 Sep 2016 18:11:24 -0400
filter: implement NOT ( ) behavior and refactoring
Diffstat:
3 files changed, 107 insertions(+), 110 deletions(-)
diff --git a/src/filter.cpp b/src/filter.cpp
@@ -35,60 +35,10 @@ void Filter::set(const string &input)
m_input = input;
m_root.clear();
- Group *group = &m_root;
- auto token = make_shared<Token>();
+ string buf;
+ int flags = 0;
State state = Default;
-
- auto push = [&] {
- size_t size = token->buf.size();
-
- if(!size)
- return;
-
- 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 == ")") {
- token->buf.clear();
- if(group != &m_root)
- group = group->parent();
- return;
- }
- }
-
- 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 |= Token::EndAnchorFlag;
- token->buf.erase(size - 1, 1);
- size--;
- }
-
- group->push(token);
-
- // close previous OR group
- if(!group->open())
- group = group->parent();
-
- token = make_shared<Token>();
- };
+ Group *group = &m_root;
for(const char c : input) {
if(c == '"' && state != SingleQuote) {
@@ -97,7 +47,7 @@ void Filter::set(const string &input)
else
state = DoubleQuote;
- token->flags |= Token::QuotedFlag;
+ flags |= Node::QuotedFlag;
}
else if(c == '\'' && state != DoubleQuote) {
if(state == SingleQuote)
@@ -105,51 +55,88 @@ void Filter::set(const string &input)
else
state = SingleQuote;
- token->flags |= Token::QuotedFlag;
+ flags |= Node::QuotedFlag;
+ }
+ else if(c == '\x20' && state == Default) {
+ group = group->push(buf, &flags);
+ buf.clear();
}
- else if(c == '\x20' && state == Default)
- push();
else
- token->buf += c;
+ buf += c;
}
- push();
+ group->push(buf, &flags);
}
-bool Filter::match(const vector<string> &rows) const
+Filter::Group::Group(Type type, int flags, Group *parent)
+ : Node(flags), m_parent(parent), m_type(type), m_open(true)
{
- return m_root.match(rows);
}
-Filter::Group *Filter::Group::subgroup_any()
+Filter::Group *Filter::Group::push(string buf, int *flags)
{
- if(m_type == Group::MatchAny) {
- m_open = true;
+ size_t size = buf.size();
+
+ if(!size)
return this;
- }
- NodePtr prev;
- if(!m_nodes.empty()) {
- prev = m_nodes.back();
- m_nodes.pop_back();
+ if((*flags & QuotedFlag) == 0) {
+ if(buf == "NOT") {
+ *flags ^= Token::NotFlag;
+ return this;
+ }
+ else if(buf == "OR") {
+ if(m_nodes.empty())
+ return this;
+ else 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, 0, this);
+ m_nodes.push_back(newGroup);
+
+ if(prev)
+ newGroup->m_nodes.push_back(prev);
+
+ return newGroup.get();
+ }
+ else if(buf == "(") {
+ auto newGroup = make_shared<Group>(Group::MatchAll, *flags, this);
+ m_nodes.push_back(newGroup);
+ *flags = 0;
+ return newGroup.get();
+ }
+ else if(buf == ")")
+ return m_parent ? m_parent : this;
}
- auto newGroup = make_shared<Group>(Group::MatchAny, this);
- m_nodes.push_back(newGroup);
+ if(size > 1 && buf[0] == '^') {
+ *flags |= Node::StartAnchorFlag;
+ buf.erase(0, 1);
+ size--;
+ }
+ if(size > 1 && buf[size - 1] == '$') {
+ *flags |= Node::EndAnchorFlag;
+ buf.erase(size - 1, 1);
+ size--;
+ }
- if(prev)
- newGroup->m_nodes.push_back(prev);
+ Group *group = this;
- return newGroup.get();
-}
+ while(!group->m_open)
+ group = group->m_parent;
-Filter::Group *Filter::Group::subgroup_all()
-{
- // always make a subgroup of this type
+ group->push(make_shared<Token>(buf, *flags));
+ *flags = 0;
- auto newGroup = make_shared<Group>(Group::MatchAll, this);
- m_nodes.push_back(newGroup);
- return newGroup.get();
+ return group;
}
void Filter::Group::push(const NodePtr &node)
@@ -163,7 +150,7 @@ void Filter::Group::push(const NodePtr &node)
bool Filter::Group::match(const vector<string> &rows) const
{
for(const NodePtr &node : m_nodes) {
- if(node->match(rows)) {
+ if(node->match(rows) ^ test(NotFlag)) {
if(m_type == MatchAny)
return true;
}
@@ -174,6 +161,11 @@ bool Filter::Group::match(const vector<string> &rows) const
return m_type == MatchAll;
}
+Filter::Token::Token(const std::string &buf, int flags)
+ : Node(flags), m_buf(buf)
+{
+}
+
bool Filter::Token::match(const vector<string> &rows) const
{
bool match = false;
@@ -193,11 +185,11 @@ bool Filter::Token::matchRow(const string &str) const
bool match = true;
if(test(StartAnchorFlag))
- match = match && boost::istarts_with(str, buf);
+ match = match && boost::istarts_with(str, m_buf);
if(test(EndAnchorFlag))
- match = match && boost::iends_with(str, buf);
+ match = match && boost::iends_with(str, m_buf);
- match = match && boost::icontains(str, buf);
+ match = match && boost::icontains(str, m_buf);
return match ^ test(NotFlag);
}
diff --git a/src/filter.hpp b/src/filter.hpp
@@ -28,7 +28,7 @@ public:
const std::string get() const { return m_input; }
void set(const std::string &);
- bool match(const std::vector<std::string> &) const;
+ bool match(const std::vector<std::string> &rows) const { return m_root.match(rows); }
Filter &operator=(const std::string &f) { set(f); return *this; }
bool operator==(const std::string &f) const { return m_input == f; }
@@ -37,7 +37,20 @@ public:
private:
class Node {
public:
+ enum Flag {
+ StartAnchorFlag = 1<<0,
+ EndAnchorFlag = 1<<1,
+ QuotedFlag = 1<<2,
+ NotFlag = 1<<3,
+ };
+
+ Node(int flags) : m_flags(flags) {}
+
virtual bool match(const std::vector<std::string> &) const = 0;
+ bool test(Flag f) const { return (m_flags & f) != 0; }
+
+ private:
+ int m_flags;
};
typedef std::shared_ptr<Node> NodePtr;
@@ -49,21 +62,14 @@ private:
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(); }
+ Group(Type type, int flags = 0, Group *parent = nullptr);
void clear() { m_nodes.clear(); }
- void push(const NodePtr &);
-
- bool open() const { return m_open; }
+ Group *push(std::string, int *flags);
bool match(const std::vector<std::string> &) const override;
private:
+ void push(const NodePtr &);
+
Group *m_parent;
Type m_type;
bool m_open;
@@ -72,21 +78,12 @@ private:
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;
-
+ Token(const std::string &buf, int flags);
bool match(const std::vector<std::string> &) const override;
bool matchRow(const std::string &) const;
- bool test(Flag f) const { return (flags & f) != 0; }
+
+ private:
+ std::string m_buf;
};
std::string m_input;
diff --git a/test/filter.cpp b/test/filter.cpp
@@ -268,4 +268,12 @@ TEST_CASE("AND grouping", M) {
SECTION("close without opening") {
f.set(") test");
}
+
+ SECTION("NOT + AND grouping") {
+ f.set("NOT ( apple OR orange )");
+
+ REQUIRE_FALSE(f.match({"apple"}));
+ REQUIRE_FALSE(f.match({"orange"}));
+ REQUIRE(f.match({"test"}));
+ }
}
