summaryrefslogtreecommitdiff
path: root/drivers/nrex/nrex.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/nrex/nrex.cpp')
-rw-r--r--drivers/nrex/nrex.cpp910
1 files changed, 910 insertions, 0 deletions
diff --git a/drivers/nrex/nrex.cpp b/drivers/nrex/nrex.cpp
new file mode 100644
index 0000000000..696d46240e
--- /dev/null
+++ b/drivers/nrex/nrex.cpp
@@ -0,0 +1,910 @@
+// NREX: Node RegEx
+//
+// Copyright (c) 2015, Zher Huei Lee
+// All rights reserved.
+//
+// This software is provided 'as-is', without any express or implied
+// warranty. In no event will the authors be held liable for any damages
+// arising from the use of this software.
+//
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+//
+// 1. The origin of this software must not be misrepresented; you must not
+// claim that you wrote the original software. If you use this software
+// in a product, an acknowledgment in the product documentation would
+// be appreciated but is not required.
+//
+// 2. Altered source versions must be plainly marked as such, and must not
+// be misrepresented as being the original software.
+//
+// 3. This notice may not be removed or altered from any source
+// distribution.
+//
+
+#include "nrex.hpp"
+
+#ifdef NREX_UNICODE
+#include <wctype.h>
+#include <wchar.h>
+#define NREX_ISALPHANUM iswalnum
+#define NREX_STRLEN wcslen
+#else
+#include <ctype.h>
+#include <string.h>
+#define NREX_ISALPHANUM isalnum
+#define NREX_STRLEN strlen
+#endif
+
+#ifdef NREX_THROW_ERROR
+#define NREX_COMPILE_ERROR(M) throw nrex_compile_error(M)
+#else
+#define NREX_COMPILE_ERROR(M) reset(); return false
+#endif
+
+#ifndef NREX_NEW
+#define NREX_NEW(X) new X
+#define NREX_NEW_ARRAY(X, N) new X[N]
+#define NREX_DELETE(X) delete X
+#define NREX_DELETE_ARRAY(X) delete[] X
+#endif
+
+template<typename T>
+class nrex_array
+{
+ private:
+ T* _data;
+ unsigned int _reserved;
+ unsigned int _size;
+ public:
+ nrex_array()
+ : _data(NREX_NEW_ARRAY(T, 2))
+ , _reserved(2)
+ , _size(0)
+ {
+ }
+
+ ~nrex_array()
+ {
+ NREX_DELETE_ARRAY(_data);
+ }
+
+ unsigned int size() const
+ {
+ return _size;
+ }
+
+ void reserve(unsigned int size)
+ {
+ T* old = _data;
+ _data = NREX_NEW_ARRAY(T, size);
+ _reserved = size;
+ for (unsigned int i = 0; i < _size; ++i)
+ {
+ _data[i] = old[i];
+ }
+ NREX_DELETE_ARRAY(old);
+ }
+
+ void push(T item)
+ {
+ if (_size == _reserved)
+ {
+ reserve(_reserved * 2);
+ }
+ _data[_size] = item;
+ _size++;
+ }
+
+ T& top()
+ {
+ return _data[_size - 1];
+ }
+
+ const T& operator[] (unsigned int i) const
+ {
+ return _data[i];
+ }
+
+ void pop()
+ {
+ if (_size > 0)
+ {
+ --_size;
+ }
+ }
+};
+
+static nrex_char nrex_unescape(nrex_char repr)
+{
+ switch (repr)
+ {
+ case '^': return '^';
+ case '$': return '$';
+ case '(': return '(';
+ case ')': return ')';
+ case '\\': return '\\';
+ case '.': return '.';
+ case '+': return '+';
+ case '*': return '*';
+ case '?': return '?';
+ case '-': return '-';
+ case 'a': return '\a';
+ case 'e': return '\e';
+ case 'f': return '\f';
+ case 'n': return '\n';
+ case 'r': return '\r';
+ case 't': return '\t';
+ case 'v': return '\v';
+ }
+ return 0;
+}
+
+struct nrex_search
+{
+ public:
+ const nrex_char* str;
+ nrex_result* captures;
+ int end;
+ bool complete;
+
+ nrex_char at(int pos)
+ {
+ return str[pos];
+ }
+
+ nrex_search(const nrex_char* str, nrex_result* captures)
+ : str(str)
+ , captures(captures)
+ , end(0)
+ {
+ }
+};
+
+struct nrex_node
+{
+ nrex_node* next;
+ nrex_node* previous;
+ nrex_node* parent;
+ bool quantifiable;
+
+ nrex_node(bool quantify = false)
+ : next(NULL)
+ , previous(NULL)
+ , parent(NULL)
+ , quantifiable(quantify)
+ {
+ }
+
+ virtual ~nrex_node()
+ {
+ if (next)
+ {
+ NREX_DELETE(next);
+ }
+ }
+
+ virtual int test(nrex_search* s, int pos) const
+ {
+ return next ? next->test(s, pos) : -1;
+ }
+
+ virtual int test_parent(nrex_search* s, int pos) const
+ {
+ if (next)
+ {
+ pos = next->test(s, pos);
+ }
+ if (parent && pos >= 0)
+ {
+ pos = parent->test_parent(s, pos);
+ }
+ if (pos >= 0)
+ {
+ s->complete = true;
+ }
+ return pos;
+ }
+};
+
+struct nrex_node_group : public nrex_node
+{
+ int capturing;
+ bool negate;
+ nrex_array<nrex_node*> childset;
+ nrex_node* back;
+
+ nrex_node_group(int capturing)
+ : nrex_node(true)
+ , capturing(capturing)
+ , negate(false)
+ , back(NULL)
+ {
+ }
+
+ virtual ~nrex_node_group()
+ {
+ for (unsigned int i = 0; i < childset.size(); ++i)
+ {
+ NREX_DELETE(childset[i]);
+ }
+
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ if (capturing >= 0)
+ {
+ s->captures[capturing].start = pos;
+ }
+ for (unsigned int i = 0; i < childset.size(); ++i)
+ {
+ s->complete = false;
+ int res = childset[i]->test(s, pos);
+ if (s->complete)
+ {
+ return res;
+ }
+ if (negate)
+ {
+ if (res < 0)
+ {
+ res = pos + 1;
+ }
+ else
+ {
+ return -1;
+ }
+ }
+ if (res >= 0)
+ {
+ if (capturing >= 0)
+ {
+ s->captures[capturing].length = res - pos;
+ }
+ return next ? next->test(s, res) : res;
+ }
+ }
+ return -1;
+ }
+
+ virtual int test_parent(nrex_search* s, int pos) const
+ {
+ if (capturing >= 0)
+ {
+ s->captures[capturing].length = pos - s->captures[capturing].start;
+ }
+ return nrex_node::test_parent(s, pos);
+ }
+
+ void add_childset()
+ {
+ back = NULL;
+ }
+
+ void add_child(nrex_node* node)
+ {
+ node->parent = this;
+ node->previous = back;
+ if (back)
+ {
+ back->next = node;
+ }
+ else
+ {
+ childset.push(node);
+ }
+ back = node;
+ }
+
+ nrex_node* swap_back(nrex_node* node)
+ {
+ if (!back)
+ {
+ add_child(node);
+ return NULL;
+ }
+ nrex_node* old = back;
+ if (!old->previous)
+ {
+ childset.pop();
+ }
+ back = old->previous;
+ add_child(node);
+ return old;
+ }
+};
+
+struct nrex_node_char : public nrex_node
+{
+ nrex_char ch;
+
+ nrex_node_char(nrex_char c)
+ : nrex_node(true)
+ , ch(c)
+ {
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ if (s->end == pos || s->at(pos) != ch)
+ {
+ return -1;
+ }
+ return next ? next->test(s, pos + 1) : pos + 1;
+ }
+};
+
+struct nrex_node_range : public nrex_node
+{
+ nrex_char start;
+ nrex_char end;
+
+ nrex_node_range(nrex_char s, nrex_char e)
+ : nrex_node(true)
+ , start(s)
+ , end(e)
+ {
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ if (s->end == pos)
+ {
+ return -1;
+ }
+ nrex_char c = s->at(pos);
+ if (c < start || end < c)
+ {
+ return -1;
+ }
+ return next ? next->test(s, pos + 1) : pos + 1;
+ }
+};
+
+static bool nrex_is_whitespace(nrex_char repr)
+{
+ switch (repr)
+ {
+ case ' ':
+ case '\t':
+ case '\r':
+ case '\n':
+ case '\f':
+ return true;
+ }
+ return false;
+}
+
+static bool nrex_is_shorthand(nrex_char repr)
+{
+ switch (repr)
+ {
+ case 'W':
+ case 'w':
+ case 'D':
+ case 'd':
+ case 'S':
+ case 's':
+ return true;
+ }
+ return false;
+}
+
+struct nrex_node_shorthand : public nrex_node
+{
+ nrex_char repr;
+
+ nrex_node_shorthand(nrex_char c)
+ : nrex_node(true)
+ , repr(c)
+ {
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ if (s->end == pos)
+ {
+ return -1;
+ }
+ bool found = false;
+ bool invert = false;
+ nrex_char c = s->at(pos);
+ switch (repr)
+ {
+ case '.':
+ found = true;
+ break;
+ case 'W':
+ invert = true;
+ case 'w':
+ if (c == '_' || NREX_ISALPHANUM(c))
+ {
+ found = true;
+ }
+ break;
+ case 'D':
+ invert = true;
+ case 'd':
+ if ('0' <= c && c <= '9')
+ {
+ found = true;
+ }
+ break;
+ case 'S':
+ invert = true;
+ case 's':
+ if (nrex_is_whitespace(c))
+ {
+ found = true;
+ }
+ break;
+ }
+ if (found == invert)
+ {
+ return -1;
+ }
+ return next ? next->test(s, pos + 1) : pos + 1;
+ }
+};
+
+static bool nrex_is_quantifier(nrex_char repr)
+{
+ switch (repr)
+ {
+ case '?':
+ case '*':
+ case '+':
+ case '{':
+ return true;
+ }
+ return false;
+}
+
+struct nrex_node_quantifier : public nrex_node
+{
+ int min;
+ int max;
+ bool greedy;
+ nrex_node* child;
+
+ nrex_node_quantifier()
+ : nrex_node()
+ , min(0)
+ , max(0)
+ , greedy(true)
+ , child(NULL)
+ {
+ }
+
+ virtual ~nrex_node_quantifier()
+ {
+ if (child)
+ {
+ NREX_DELETE(child);
+ }
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ nrex_array<int> backtrack;
+ backtrack.push(pos);
+ while (backtrack.top() <= s->end)
+ {
+ if (max >= 1 && backtrack.size() > (unsigned int)max)
+ {
+ break;
+ }
+ if (!greedy && (unsigned int)min < backtrack.size())
+ {
+ int res = backtrack.top();
+ if (next)
+ {
+ res = next->test(s, res);
+ }
+ if (s->complete)
+ {
+ return res;
+ }
+ if (res >= 0 && parent->test_parent(s, res) >= 0)
+ {
+ return res;
+ }
+ }
+ int res = child->test(s, backtrack.top());
+ if (s->complete)
+ {
+ return res;
+ }
+ if (res < 0 || res == backtrack.top())
+ {
+ break;
+ }
+ backtrack.push(res);
+ }
+ while (greedy && (unsigned int) min < backtrack.size())
+ {
+ int res = backtrack.top();
+ if (next)
+ {
+ res = next->test(s, res);
+ }
+ if (res >= 0 && parent->test_parent(s, res) >= 0)
+ {
+ return res;
+ }
+ if (s->complete)
+ {
+ return res;
+ }
+ backtrack.pop();
+ }
+ return -1;
+ }
+};
+
+struct nrex_node_anchor : public nrex_node
+{
+ bool end;
+
+ nrex_node_anchor(bool end)
+ : nrex_node()
+ , end(end)
+ {
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ if (!end && pos != 0)
+ {
+ return -1;
+ }
+ else if (end && pos != s->end)
+ {
+ return -1;
+ }
+ return next ? next->test(s, pos) : pos;
+ }
+};
+
+struct nrex_node_backreference : public nrex_node
+{
+ int ref;
+
+ nrex_node_backreference(int ref)
+ : nrex_node(true)
+ , ref(ref)
+ {
+ }
+
+ int test(nrex_search* s, int pos) const
+ {
+ nrex_result& r = s->captures[ref];
+ for (int i = 0; i < r.length; ++i)
+ {
+ if (pos + i >= s->end)
+ {
+ return -1;
+ }
+ if (s->at(r.start + i) != s->at(pos + i))
+ {
+ return -1;
+ }
+ }
+ return next ? next->test(s, pos + r.length) : pos + r.length;
+ }
+};
+
+nrex::nrex()
+ : _capturing(0)
+ , _root(NULL)
+{
+}
+
+nrex::~nrex()
+{
+ if (_root)
+ {
+ NREX_DELETE(_root);
+ }
+}
+
+bool nrex::valid() const
+{
+ return (_root != NULL);
+}
+
+void nrex::reset()
+{
+ _capturing = 0;
+ if (_root)
+ {
+ NREX_DELETE(_root);
+ }
+ _root = NULL;
+}
+
+int nrex::capture_size() const
+{
+ return _capturing + 1;
+}
+
+bool nrex::compile(const nrex_char* pattern)
+{
+ reset();
+ nrex_node_group* root = NREX_NEW(nrex_node_group(_capturing));
+ nrex_array<nrex_node_group*> stack;
+ stack.push(root);
+ _root = root;
+
+ for (const nrex_char* c = pattern; c[0] != '\0'; ++c)
+ {
+ if (c[0] == '(')
+ {
+ if (c[1] == '?')
+ {
+ if (c[2] == ':')
+ {
+ c = &c[2];
+ nrex_node_group* group = NREX_NEW(nrex_node_group(-1));
+ stack.top()->add_child(group);
+ stack.push(group);
+ }
+ else
+ {
+ NREX_COMPILE_ERROR("unrecognised qualifier for parenthesis");
+ }
+ }
+ else if (_capturing < 99)
+ {
+ nrex_node_group* group = NREX_NEW(nrex_node_group(++_capturing));
+ stack.top()->add_child(group);
+ stack.push(group);
+ }
+ else
+ {
+ nrex_node_group* group = NREX_NEW(nrex_node_group(-1));
+ stack.top()->add_child(group);
+ stack.push(group);
+ }
+ }
+ else if (c[0] == ')')
+ {
+ if (stack.size() > 1)
+ {
+ stack.pop();
+ }
+ else
+ {
+ NREX_COMPILE_ERROR("unexpected ')'");
+ }
+ }
+ else if (c[0] == '[')
+ {
+ nrex_node_group* group = NREX_NEW(nrex_node_group(-1));
+ stack.top()->add_child(group);
+ if (c[1] == '^')
+ {
+ group->negate = true;
+ ++c;
+ }
+ while (true)
+ {
+ group->add_childset();
+ ++c;
+ if (c[0] == '\0')
+ {
+ NREX_COMPILE_ERROR("unclosed character class '[]'");
+ }
+ if (c[0] == ']')
+ {
+ break;
+ }
+ else if (c[0] == '\\')
+ {
+ nrex_char unescaped = nrex_unescape(c[1]);
+ if (unescaped)
+ {
+ group->add_child(NREX_NEW(nrex_node_char(unescaped)));
+ ++c;
+ }
+ else if (nrex_is_shorthand(c[1]))
+ {
+ group->add_child(NREX_NEW(nrex_node_shorthand(c[1])));
+ ++c;
+ }
+ else
+ {
+ NREX_COMPILE_ERROR("escape token not recognised");
+ }
+ }
+ else
+ {
+ if (c[1] == '-' && c[2] != '\0')
+ {
+ bool range = false;
+ if ('A' <= c[0] && c[0] <= 'Z' && 'A' <= c[2] && c[2] <= 'Z')
+ {
+ range = true;
+ }
+ if ('a' <= c[0] && c[0] <= 'z' && 'a' <= c[2] && c[2] <= 'z')
+ {
+ range = true;
+ }
+ if ('0' <= c[0] && c[0] <= '9' && '0' <= c[2] && c[2] <= '9')
+ {
+ range = true;
+ }
+ if (range)
+ {
+ group->add_child(NREX_NEW(nrex_node_range(c[0], c[2])));
+ c = &c[2];
+ continue;
+ }
+ }
+ group->add_child(NREX_NEW(nrex_node_char(c[0])));
+ }
+
+ }
+ }
+ else if (nrex_is_quantifier(c[0]))
+ {
+ nrex_node_quantifier* quant = NREX_NEW(nrex_node_quantifier);
+ quant->child = stack.top()->swap_back(quant);
+ if (quant->child == NULL || !quant->child->quantifiable)
+ {
+ NREX_COMPILE_ERROR("element not quantifiable");
+ }
+ quant->child->previous = NULL;
+ quant->child->next = NULL;
+ quant->child->parent = quant;
+ if (c[0] == '?')
+ {
+ quant->min = 0;
+ quant->max = 1;
+ }
+ else if (c[0] == '+')
+ {
+ quant->min = 1;
+ quant->max = -1;
+ }
+ else if (c[0] == '*')
+ {
+ quant->min = 0;
+ quant->max = -1;
+ }
+ else if (c[0] == '{')
+ {
+ bool max_set = false;
+ quant->min = 0;
+ quant->max = -1;
+ while (true)
+ {
+ ++c;
+ if (c[0] == '\0')
+ {
+ NREX_COMPILE_ERROR("unclosed range quantifier '{}'");
+ }
+ else if (c[0] == '}')
+ {
+ break;
+ }
+ else if (c[0] == ',')
+ {
+ max_set = true;
+ continue;
+ }
+ else if (c[0] < '0' || '9' < c[0])
+ {
+ NREX_COMPILE_ERROR("expected numeric digits, ',' or '}'");
+ }
+ if (max_set)
+ {
+ if (quant->max < 0)
+ {
+ quant->max = int(c[0] - '0');
+ }
+ else
+ {
+ quant->max = quant->max * 10 + int(c[0] - '0');
+ }
+ }
+ else
+ {
+ quant->min = quant->min * 10 + int(c[0] - '0');
+ }
+ }
+ if (!max_set)
+ {
+ quant->max = quant->min;
+ }
+ }
+ if (c[1] == '?')
+ {
+ quant->greedy = false;
+ ++c;
+ }
+ }
+ else if (c[0] == '|')
+ {
+ stack.top()->add_childset();
+ }
+ else if (c[0] == '^' || c[0] == '$')
+ {
+ stack.top()->add_child(NREX_NEW(nrex_node_anchor((c[0] == '$'))));
+ }
+ else if (c[0] == '.')
+ {
+ stack.top()->add_child(NREX_NEW(nrex_node_shorthand('.')));
+ }
+ else if (c[0] == '\\')
+ {
+ nrex_char unescaped = nrex_unescape(c[1]);
+ if (unescaped)
+ {
+ stack.top()->add_child(NREX_NEW(nrex_node_char(unescaped)));
+ ++c;
+ }
+ else if (nrex_is_shorthand(c[1]))
+ {
+ stack.top()->add_child(NREX_NEW(nrex_node_shorthand(c[1])));
+ ++c;
+ }
+ else if ('1' <= c[1] && c[1] <= '9')
+ {
+ int ref = 0;
+ if ('0' <= c[2] && c[2] <= '9')
+ {
+ ref = int(c[1] - '0') * 10 + int(c[2] - '0');
+ c = &c[2];
+ }
+ else
+ {
+ ref = int(c[1] - '0');
+ ++c;
+ }
+ if (ref > _capturing)
+ {
+ NREX_COMPILE_ERROR("backreference to non-existent capture");
+ }
+ stack.top()->add_child(NREX_NEW(nrex_node_backreference(ref)));
+ }
+ else
+ {
+ NREX_COMPILE_ERROR("escape token not recognised");
+ }
+ }
+ else
+ {
+ stack.top()->add_child(NREX_NEW(nrex_node_char(c[0])));
+ }
+ }
+ return true;
+}
+
+bool nrex::match(const nrex_char* str, nrex_result* captures, int offset, int end) const
+{
+ nrex_search s(str, captures);
+ if (end >= offset)
+ {
+ s.end = end;
+ }
+ else
+ {
+ s.end = NREX_STRLEN(str);
+ }
+ for (int i = offset; i < s.end; ++i)
+ {
+ for (int c = 0; c <= _capturing; ++c)
+ {
+ captures[c].start = 0;
+ captures[c].length = 0;
+ }
+ if (_root->test(&s, i) >= 0)
+ {
+ return true;
+ }
+ }
+ return false;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 08:58:49 +0000