Finish pattern matcher
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4fcd8af..61c401e 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -16,3 +16,4 @@
Qt::Core
)
+add_compile_options("-fsanitize=address")
\ No newline at end of file
diff --git a/Matcher.cpp b/Matcher.cpp
index 4fc901c..b4dda6d 100644
--- a/Matcher.cpp
+++ b/Matcher.cpp
@@ -1,29 +1,97 @@
#include "Matcher.h"
+#include <QDebug>
+
MatchResult match(QList<Token> data, QList<Token> pattern, VarContext context) {
if (data.empty() && pattern.empty()) {
return MatchResult{true, context};
}
- Token patternHead = pattern.first();
+ Token ph = pattern.first();
Token dataHead = data.first();
pattern.removeFirst();
- if (patternHead.isSym() || patternHead.isIdent()) {
- if (patternHead == pattern.first()) {
+ if (ph.isSym() || ph.isIdent()) {
+ if (ph == data.first()) {
data.removeFirst();
return match(data, pattern, context);
} else {
return MatchResult{false, context};
}
- } else if (patternHead.isParen() && dataHead.isParen()) {
+ } else if (ph.isParen() && dataHead.isParen()) {
data.removeFirst();
- auto result = match(dataHead.parenContent(), patternHead.parenContent(), context);
+ auto result = match(dataHead.parenContent(), ph.parenContent(), context);
if (result.success) {
return match(data, pattern, result.context);
} else {
return MatchResult{false, result.context};
}
+ } else if (ph.isVar()) {
+ // is var bound?
+ if (context.exists(ph.name())) {
+ // TODO: handle error elegantly if types don't match up (let's just assume the user isn't stupid)
+
+ switch (ph.varType()) {
+ case 's':
+ case 't':
+ if (context.singleVar(ph.name()) == dataHead) {
+ data.removeFirst();
+ return match(data, pattern, context);
+ } else {
+ return MatchResult{false, context};
+ }
+ case 'e':
+ QList<Token> expected = context.expressionVar(ph.name());
+
+ if (listStartsWith(data, expected)) {
+ listDrop(data, expected.length());
+ return match(data, pattern, context);
+ } else {
+ return MatchResult{false, context};
+ }
+ }
+ } else {
+ bool typeIsOk = false;
+
+ switch (ph.varType()) {
+ case 't':
+ if (dataHead.isParen())
+ typeIsOk = true;
+
+ case 's':
+ if (dataHead.isSym() || dataHead.isIdent())
+ typeIsOk = true;
+
+ if (!typeIsOk) {
+ return MatchResult{false, context};
+ }
+
+ context.add(ph.varType(), ph.name(), dataHead);
+ data.removeFirst();
+
+ return match(data, pattern, context);
+
+ case 'e':
+ // Now this is tricky
+ for (int matchSyms = 1; matchSyms < data.length(); matchSyms++) {
+ QList<Token> slice = listSlice(data, 0, matchSyms);
+ VarContext newContext = context;
+ newContext.add(ph.varType(), ph.name(), slice);
+
+ MatchResult tryMatch = match(listSlice(data, matchSyms, data.length()), pattern, newContext);
+ if (tryMatch.success) {
+ return tryMatch;
+ }
+ // else matchSyms ++
+ }
+ // If this worked we would have returned already
+ return MatchResult{false, context};
+ }
+ }
}
+
+ qDebug() << "FALLING THROUGH, THIS SHOULD NOT HAPPEN";
+ // Fallthrough
+ return MatchResult{false, context};
}
diff --git a/Matcher.h b/Matcher.h
index 81f4305..84aee15 100644
--- a/Matcher.h
+++ b/Matcher.h
@@ -8,4 +8,37 @@
VarContext context;
};
+template <typename T>
+bool listStartsWith(const QList<T> &haystack, const QList<T> &needle) {
+ if (needle.length() > haystack.length())
+ return false;
+
+ for (int i = 0; i < needle.length(); i++) {
+ if (haystack[i] != needle[i])
+ return false;
+ }
+
+ return true;
+}
+
+template <typename T>
+void listDrop(QList<T> &list, int n) {
+ for (; n; n--) {
+ list.removeFirst();
+ }
+}
+
+template <typename T>
+QList<T> listSlice(QList<T> &list, int from, int to) {
+ QList<T> prime;
+
+ // I guess we'll just panic if it's too long
+ // TODO: ERROR HANDLING
+ for (int i = 0; i < to - from; i++) {
+ prime.append(list[from + i]);
+ }
+
+ return prime;
+}
+
MatchResult match(QList<Token> data, QList<Token> pattern, VarContext context);
diff --git a/Token.cpp b/Token.cpp
index 7cb50e0..4d36344 100644
--- a/Token.cpp
+++ b/Token.cpp
@@ -16,7 +16,7 @@
Token::Token(QList<Token> &&parenthesized) {
_type = PAREN;
- _listVal = new QList<Token>(parenthesized);
+ _listVal = parenthesized;
}
Token::Token(char varType, const QString &&name) {
@@ -25,11 +25,6 @@
_stringVal = name;
}
-Token::~Token() {
- // Стерать нулевые пойнтеры безопасно
- delete _listVal;
-}
-
bool Token::isSym() {
return _type == SYM;
}
@@ -49,17 +44,29 @@
Token::Token() : Token("Null") {
}
-bool Token::operator==(const Token &other) {
+bool Token::operator==(const Token &other) const {
return _type == other._type
&& _stringVal == other._stringVal
&& _charVal == other._charVal
- && (_listVal == nullptr || *_listVal == (*other._listVal));
+ && _listVal == other._listVal;
}
QList<Token> Token::parenContent() {
- if (isParen() && _listVal) {
- return *_listVal;
+ if (isParen()) {
+ return _listVal;
} else {
return {};
}
}
+
+char Token::varType() const {
+ return _charVal.toLatin1();
+}
+
+const QString &Token::name() const {
+ return _stringVal;
+}
+
+bool Token::operator!=(const Token &other) const {
+ return !(this->operator==(other));
+}
diff --git a/Token.h b/Token.h
index bb46127..a0a5eaa 100644
--- a/Token.h
+++ b/Token.h
@@ -13,9 +13,8 @@
explicit Token(QList<Token> &&parenthesized);
Token(char varType, const QString &&name);
- bool operator ==(const Token &other);
-
- ~Token();
+ bool operator ==(const Token &other) const;
+ bool operator !=(const Token &other) const;
bool isSym();
bool isIdent();
@@ -24,6 +23,9 @@
QList<Token> parenContent();
+ char varType() const;
+ const QString &name() const;
+
private:
enum Type {
SYM, IDENT, PAREN, VAR,
@@ -31,6 +33,8 @@
int _type = 0;
QString _stringVal = "";
- QList<Token> *_listVal = nullptr;
+ QList<Token> _listVal;
QChar _charVal = 0;
};
+
+using LTok = QList<Token>;
diff --git a/VarContext.cpp b/VarContext.cpp
index bde30ef..031ec42 100644
--- a/VarContext.cpp
+++ b/VarContext.cpp
@@ -1,17 +1,25 @@
#include "VarContext.h"
-void VarContext::add(char t, const QString &&name, const Token &value) {
+void VarContext::add(char t, const QString &name, const Token &value) {
_vars.insert(name, Var{t, value});
}
char VarContext::exists(const QString &name) {
- return _vars.contains(name);
+ return _vars.contains(name) ? _vars[name].t : 0;
}
-Token VarContext::operator[](const QString &name) {
+Token VarContext::singleVar(const QString &name) {
return _vars[name].value;
}
VarContext::VarContext(const VarContext &other) noexcept {
_vars = other._vars;
}
+
+void VarContext::add(char t, const QString &name, const QList<Token> &value) {
+ _vars.insert(name,Var{t,{},value});
+}
+
+QList<Token> VarContext::expressionVar(const QString &name) {
+ return _vars[name].expressionValue;
+}
diff --git a/VarContext.h b/VarContext.h
index afa1b9a..3da8b9d 100644
--- a/VarContext.h
+++ b/VarContext.h
@@ -8,9 +8,12 @@
VarContext() = default;
VarContext(VarContext const &other) noexcept;
- void add(char t, const QString &&name, const Token &value);
+ void add(char t, const QString &name, const Token &value);
+ void add(char t, const QString &name, const QList<Token> &value);
+
char exists(const QString &name);
- Token operator [](const QString &name);
+ Token singleVar(const QString &name);
+ QList<Token> expressionVar(const QString &name);
private:
struct Var {
@@ -18,6 +21,7 @@
char t = 0;
Token value;
+ QList<Token> expressionValue;
};
QMap<QString, Var> _vars;
diff --git a/main.cpp b/main.cpp
index 6c07880..a343682 100644
--- a/main.cpp
+++ b/main.cpp
@@ -1,8 +1,62 @@
#include <QCoreApplication>
#include <QDebug>
+#include "Matcher.h"
+#include "Token.h"
+
+int g_numFailed = 0;
+
+void printResult(const QString &test, bool shouldBe, const MatchResult &result) {
+ if (result.success != shouldBe) {
+ g_numFailed++;
+ qDebug() << "TEST FAILS:";
+ }
+
+ qDebug() << "MatchResult" << test << result.success;
+}
+
+int testResults() {
+ if (g_numFailed == 0) {
+ qDebug() << "ALL TESTS SUCCEEDED";
+ } else {
+ qDebug() << g_numFailed << "TESTS FAILED";
+ }
+
+ return g_numFailed;
+}
+
+void runTests() {
+ printResult("a = a", true, match({Token('a')}, {Token('a')}, VarContext()));
+
+ LTok sameTwo = {Token('s', "a"), Token('s', "a")};
+ printResult("s.a s.a = aa", true, match({Token('a'), Token('a')}, sameTwo, VarContext()));
+ printResult("s.a s.a = ab", false, match({Token('a'), Token('b')}, sameTwo, VarContext()));
+
+ LTok sameStartEnd = {
+ Token('s', "a"),
+ Token('e', "middle"),
+ Token('s', "a")
+ };
+ printResult("s.a e.middle s.a = aea", true,
+ match({
+ Token('a'), Token('e'), Token('a')
+ }, sameStartEnd, VarContext()));
+
+ printResult("s.a e.middle s.a = aef Hi a", true,
+ match({
+ Token('a'), Token('e'), Token('f'), Token("Hi"), Token('a')
+ }, sameStartEnd, VarContext()));
+
+ printResult("s.a e.middle s.a = aef Hi c", false,
+ match({
+ Token('a'), Token('e'), Token('f'), Token("Hi"), Token('c')
+ }, sameStartEnd, VarContext()));
+}
+
int main(int argc, char *argv[]) {
QCoreApplication a(argc, argv);
- qDebug() << "Hello World";
- return QCoreApplication::exec();
+
+ runTests();
+
+ return testResults();
}