src/paca.mjs: Improve implementation of interpretMetacharactersHEADmain

1 files changed, 172 insertions, 28 deletions

diff --git a/tests/paca.mjs b/tests/paca.mjs
index 7b20e88..378fba3 100644
--- a/tests/paca.mjs
+++ b/tests/paca.mjs
@@ -3,6 +3,7 @@ import { explode, reduced, reductions, runTests } from "sjs";
 import {
 	SyntaxError,
 	ValueError,
+	InternalError,
 	ConcatStep,
 	shouldConcat,
 	isOperator,
@@ -55,6 +56,7 @@ import {
 	searchDFAStep,
 	searchDFAFn,
 	searchDFA,
+	parse,
 	compileNFA,
 	compileDFA,
 	compile,
@@ -1751,6 +1753,31 @@ const test_toPostfix = t => {
 				"c",
 				concat,
 			],
+		}, {
+			in: [
+				{ meta: "^" },
+				"a",
+				concat,
+				wildcard,
+				{ operator: "*" },
+				concat,
+				"$",
+				concat,
+				"b",
+				{ operator: "range", from: 3, to: 5 },
+			],
+			expected: [
+				{ meta: "^" },
+				"a",
+				wildcard,
+				{ operator: "*" },
+				concat,
+				"$",
+				concat,
+				"b",
+				{ operator: "range", from: 3, to: 5 },
+				concat,
+			],
 		}];
 		for (const test of table) {
 			t.assertEq(
@@ -2776,7 +2803,20 @@ const test_interpretMetacharacter = t => {
 	t.start("interpretMetacharacter()");
 
 	t.testing("null on missing meta attribute", () => {
-		t.assertEq(interpretMetacharacter({}, "IGNORED"), null);
+		t.assertEq(interpretMetacharacter({}, "IGNORED"), []);
+	});
+
+	t.testing("error on invalid op", () => {
+		try {
+			interpretMetacharacter(
+				{ op: "OP" }, null, null, null, null,
+			);
+			t.assertEq(true, false);
+		} catch (e) {
+			const message = "Unsupported op: OP";
+			t.assertEq(e.message, message);
+			t.assertEq(e instanceof InternalError, true);
+		}
 	});
 
 	t.testing("wildcard always matches", () => {
@@ -2784,7 +2824,7 @@ const test_interpretMetacharacter = t => {
 			op: true,
 			to: "ret",
 		};
-		t.assertEq(interpretMetacharacter(input, "IGNORED"), "ret");
+		t.assertEq(interpretMetacharacter(input, "IGNORED"), ["ret"]);
 	});
 
 	t.testing("matches returns depending on the op", () => {
@@ -2797,8 +2837,8 @@ const test_interpretMetacharacter = t => {
 			...input1,
 			op: "excludes",
 		};
-		t.assertEq(interpretMetacharacter(input1, "a"), "ret");
-		t.assertEq(interpretMetacharacter(input2, "a"), false);
+		t.assertEq(interpretMetacharacter(input1, "a"), ["ret"]);
+		t.assertEq(interpretMetacharacter(input2, "a"), []);
 	});
 
 	t.testing("inRange returns depending on op", () => {
@@ -2812,8 +2852,8 @@ const test_interpretMetacharacter = t => {
 			...input1,
 			op: "excludes",
 		};
-		t.assertEq(interpretMetacharacter(input1, "x"), "ret");
-		t.assertEq(interpretMetacharacter(input2, "x"), false);
+		t.assertEq(interpretMetacharacter(input1, "x"), ["ret"]);
+		t.assertEq(interpretMetacharacter(input2, "x"), []);
 	});
 
 	t.testing("when nothing matches, we look at the op again", () => {
@@ -2827,16 +2867,45 @@ const test_interpretMetacharacter = t => {
 			...input1,
 			op: "excludes",
 		};
-		t.assertEq(interpretMetacharacter(input1, "a"), false);
-		t.assertEq(interpretMetacharacter(input2, "a"), "ret");
+		t.assertEq(interpretMetacharacter(input1, "a"), []);
+		t.assertEq(interpretMetacharacter(input2, "a"), ["ret"]);
 	});
 
 	t.testing("caret only matches when at the start of the string", () => {
-		// FIXME
-	});
-
-	t.testing("dollar matches end of string", () => {
-		// FIXME
+		const input = {
+			op: "caret",
+			to: 3,
+		};
+		const nodes = {
+			3: {
+				direct:      [ 4 ],
+				transitions: {},
+			},
+			4: {
+				direct:      [ 5 ],
+				transitions: {},
+			},
+			5: {
+				direct:      [],
+				transitions: { a: 6 },
+			},
+			6: {
+				direct:      [ 7 ],
+				transitions: {},
+			},
+			7: {
+				direct:      [],
+				transitions: { x: null },
+			},
+		};
+		t.assertEq(
+			interpretMetacharacter(input, "a", 1, nodes),
+			[],
+		);
+		t.assertEq(
+			interpretMetacharacter(input, "a", 0, nodes, [ "a" ]),
+			[ 7 ],
+		);
 	});
 };
 
@@ -2852,8 +2921,8 @@ const test_performTransition = t => {
 				transitions: {},
 			},
 		};
-		t.assertEq(performTransition(nodes, "a")(1), 2);
-		t.assertEq(performTransition(nodes, "a")(2), null);
+		t.assertEq(performTransition(nodes, "a")(1), [2]);
+		t.assertEq(performTransition(nodes, "a")(2), []);
 	});
 
 	t.testing("or execute the meta attribute", () => {
@@ -2869,8 +2938,8 @@ const test_performTransition = t => {
 				transitions: {},
 			},
 		};
-		t.assertEq(performTransition(nodes, "a")(1), 2);
-		t.assertEq(performTransition(nodes, "a")(2), null);
+		t.assertEq(performTransition(nodes, "a")(1), [2]);
+		t.assertEq(performTransition(nodes, "a")(2), []);
 	});
 };
 
@@ -2878,7 +2947,7 @@ const test_searchNFAStep = t => {
 	t.start("searchNFAStep()");
 
 	t.testing("empty on empty input", () => {
-		t.assertEq(searchNFAStep({})([], null), []);
+		t.assertEq(searchNFAStep({})([], null, null, []), []);
 	});
 
 	t.testing("empty on empty transitions", () => {
@@ -2887,7 +2956,7 @@ const test_searchNFAStep = t => {
 			2: { transitions: {} },
 			3: { transitions: {} },
 		};
-		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a"), []);
+		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a", null, []), []);
 	});
 
 	t.testing("empty on non-matching transitions", () => {
@@ -2896,7 +2965,7 @@ const test_searchNFAStep = t => {
 			2: { transitions: { c: 3 } },
 			3: { transitions: { d: 1 } },
 		};
-		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a"), []);
+		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a", null, []), []);
 	});
 
 	t.testing("leaves given by allDirects() otherwise", () => {
@@ -2934,13 +3003,33 @@ const test_searchNFAStep = t => {
 				transitions: {},
 			},
 		};
-		t.assertEq(searchNFAStep(nodes)([1], "a"), [5]);
-		t.assertEq(searchNFAStep(nodes)([1], "b"), []);
-		t.assertEq(searchNFAStep(nodes)([3, 2, 1], "a"), [5, 6, 7, 8]);
-		t.assertEq(searchNFAStep(nodes)([5, 6, 7, 8], "a"), [2]);
-		t.assertEq(searchNFAStep(nodes)([5, 6, 7, 8], "b"), [7]);
-		t.assertEq(searchNFAStep(nodes)([5, 6, 7, 8], "c"), [8]);
-		t.assertEq(searchNFAStep(nodes)([5, 6, 7, 8], "d"), []);
+		const fn = searchNFAStep(nodes);
+		t.assertEq(fn([1], "a", null, []), [5]);
+		t.assertEq(fn([1], "b", null, []), []);
+		t.assertEq(fn([3, 2, 1], "a", null, []), [5, 6, 7, 8]);
+		t.assertEq(fn([5, 6, 7, 8], "a", null, []), [2]);
+		t.assertEq(fn([5, 6, 7, 8], "b", null, []), [7]);
+		t.assertEq(fn([5, 6, 7, 8], "c", null, []), [8]);
+		t.assertEq(fn([5, 6, 7, 8], "d", null, []), []);
+	});
+
+	t.testing("recursive call to self via interpretMetacharacter", () => {
+		const regex = "^[behilos]*$";
+		const nfa = buildNFA(toPostfix(tokenizeRegex(explode(regex))));
+		const str = "sebo";
+		const fn = searchNFAStep(nfa.nodes, str.length);
+		t.assertEq(fn([1], str[0], 0), [3, 7]);
+		t.assertEq(fn([1], str[0], 1), []);
+		t.assertEq(fn([1], " ", 0), []);
+		t.assertEq(fn([3], str[0], 1), [3, 7]);
+		t.assertEq(fn([3], " ",    1), []);
+		t.assertEq(fn([3, 7], str[3], 4), [3, 7]);
+		t.assertEq(fn([3, 7], " ", 3), []);
+
+		t.assertEq(fn([1],    str[0], 0), [3, 7]);
+		t.assertEq(fn([3, 7], str[1], 1), [3, 7]);
+		t.assertEq(fn([3, 7], str[2], 2), [3, 7]);
+		t.assertEq(fn([3, 7], str[3], 3), [3, 7]);
 	});
 };
 
@@ -2972,9 +3061,10 @@ const test_searchNFA = t => {
 	});
 
 	t.testing("regex with metacharacters", () => {
-		const regex = "^[behilos]*";
+		const regex = "^[behilos]*$";
 		const nfa = buildNFA(toPostfix(tokenizeRegex(explode(regex))));
 		t.assertEq(searchNFA(nfa, "helios"),  true);
+		t.assertEq(searchNFA(nfa, " helios"), false);
 		t.assertEq(searchNFA(nfa, "helios "), false);
 		t.assertEq(searchNFA(nfa, "abc"), false);
 	});
@@ -3377,6 +3467,59 @@ const test_searchDFA = t => {
 	});
 };
 
+const test_parse = t => {
+	t.start("parse()");
+
+	t.testing("regex table", () => {
+		const table = [{
+			in: "",
+			expected: [],
+		}, {
+			in: "a",
+			expected: ["a"],
+		}, {
+			in: "a|b",
+			expected: ["a", "b", { operator: "|" }],
+		}, {
+			in: "(a|b)*a?(a|b)+",
+			expected: [
+				"a",
+				"b",
+				{ operator: "|" },
+				{ operator: "*" },
+				"a",
+				{ operator: "?" },
+				{ operator: "concat" },
+				"a",
+				"b",
+				{ operator: "|" },
+				{ operator: "+" },
+				{ operator: "concat" },
+			],
+		}, {
+			in: "^[behilos]*$",
+			expected: [
+				{ meta: "^" },
+				{
+					meta: "class",
+					set:  [
+						"b", "e", "h", "i",
+						"l", "o", "s",
+					],
+					caret: false,
+				},
+				{ operator: "*" },
+				{ operator: "concat" },  // FIXME
+				{ meta: "$" },
+				{ operator: "concat" },  // FIXME
+			],
+		}];
+		for (const tcase of table) {
+			t.assertEq(parse(tcase.in), tcase.expected);
+		}
+	});
+};
+
 const test_compileNFA = t => {
 	t.start("compileNFA()");
 
@@ -3677,6 +3820,7 @@ runTests([
 	test_searchDFAStep,
 	test_searchDFAFn,
 	test_searchDFA,
+	test_parse,
 	test_compileNFA,
 	test_compileDFA,
 	test_compile,