Support searching in the NFA using the metacharacters.

* src/paca.mjs
  (searchNFAStep): Now instead of just checking if the node has a
    transition via a character literal directly, we also check (via the
    `performTransition()` function) if a metacharacter interpretation
    allows a transition to happen.
  (intepretMetacharacter): Add function that "executes" the action
    representation in the "meta" attribute of the object, when present.
    It is somewhat ad-hoc now, doing checks that implicitly only exist
    for "." or "class" metacharacters, but OK for now, given the
    possibilities.
  (performTransition): Do the fallback to `interpretMetacharacter()`,
    giving it an empty object when the node doesn't have the "meta"
    attribute.
* tests/paca.mjs (test_{interpretMetacharacter,performTransition): Add
  routine test implementation.

2 files changed, 123 insertions, 1 deletions

diff --git a/src/paca.mjs b/src/paca.mjs
index 77a7a4b..216dc2e 100644
--- a/src/paca.mjs
+++ b/src/paca.mjs
@@ -761,10 +761,34 @@ const allDirects = (stateID, nodes) =>
 			).flat(),
 		)].toSorted();
 
+const interpretMetacharacter = ({ op, to, matches, ranges }, char) => {
+	if (!op) {
+		return null;
+	}
+
+	if (op === true) {
+		return to;
+	}
+
+	if (matches.has(char)) {
+		return op === "includes" && to;
+	}
+
+	if (inRange(ranges, char)) {
+		return op === "includes" && to;
+	}
+
+	return op === "excludes" && to;
+};
+
+const performTransition = (nodes, char) => id =>
+	nodes[id].transitions[char] ||
+	interpretMetacharacter(nodes[id].meta || {}, char);
+
 const searchNFAStep = nodes => (directStates, char) =>
 	[...new Set(
 		directStates
-			.map(id => nodes[id].transitions[char])
+			.map(performTransition(nodes, char))
 			.filter(x => !!x)
 			.map(id => allDirects(id, nodes))
 			.flat()
diff --git a/tests/paca.mjs b/tests/paca.mjs
index efee446..82640b1 100644
--- a/tests/paca.mjs
+++ b/tests/paca.mjs
@@ -39,6 +39,8 @@ import {
 	buildNFAStep,
 	buildNFA,
 	allDirects,
+	interpretMetacharacter,
+	performTransition,
 	searchNFAStep,
 	searchNFAFn,
 	searchNFA,
@@ -2675,6 +2677,100 @@ const test_allDirects = t => {
 	});
 };
 
+const test_interpretMetacharacter = t => {
+	t.start("interpretMetacharacter()");
+
+	t.testing("null on missing meta attribute", () => {
+		t.assertEq(interpretMetacharacter({}, "IGNORED"), null);
+	});
+
+	t.testing("wildcard always matches", () => {
+		const input = {
+			op: true,
+			to: "ret",
+		};
+		t.assertEq(interpretMetacharacter(input, "IGNORED"), "ret");
+	});
+
+	t.testing("matches returns depending on the op", () => {
+		const input1 = {
+			op:      "includes",
+			to:      "ret",
+			matches: new Set(["a"]),
+		};
+		const input2 = {
+			...input1,
+			op: "excludes",
+		};
+		t.assertEq(interpretMetacharacter(input1, "a"), "ret");
+		t.assertEq(interpretMetacharacter(input2, "a"), false);
+	});
+
+	t.testing("inRange returns depending on op", () => {
+		const input1 = {
+			op:      "includes",
+			to:      "ret",
+			matches: new Set([]),
+			ranges:  { 97: 122 },
+		};
+		const input2 = {
+			...input1,
+			op: "excludes",
+		};
+		t.assertEq(interpretMetacharacter(input1, "x"), "ret");
+		t.assertEq(interpretMetacharacter(input2, "x"), false);
+	});
+
+	t.testing("when nothing matches, we look at the op again", () => {
+		const input1 = {
+			op:      "includes",
+			to:      "ret",
+			matches: new Set([]),
+			ranges:  {},
+		};
+		const input2 = {
+			...input1,
+			op: "excludes",
+		};
+		t.assertEq(interpretMetacharacter(input1, "a"), false);
+		t.assertEq(interpretMetacharacter(input2, "a"), "ret");
+	});
+};
+
+const test_performTransition = t => {
+	t.start("performTransition()");
+
+	t.testing("either get the direct transition", () => {
+		const nodes = {
+			1: {
+				transitions: { a: 2 },
+			},
+			2: {
+				transitions: {},
+			},
+		};
+		t.assertEq(performTransition(nodes, "a")(1), 2);
+		t.assertEq(performTransition(nodes, "a")(2), null);
+	});
+
+	t.testing("or execute the meta attribute", () => {
+		const nodes = {
+			1: {
+				transitions: {},
+				meta: {
+					op: true,
+					to: 2,
+				},
+			},
+			2: {
+				transitions: {},
+			},
+		};
+		t.assertEq(performTransition(nodes, "a")(1), 2);
+		t.assertEq(performTransition(nodes, "a")(2), null);
+	});
+};
+
 const test_searchNFAStep = t => {
 	t.start("searchNFAStep()");
 
@@ -3459,6 +3555,8 @@ runTests([
 	test_buildNFAStep,
 	test_buildNFA,
 	test_allDirects,
+	test_interpretMetacharacter,
+	test_performTransition,
 	test_searchNFAStep,
 	test_searchNFAFn,
 	test_searchNFA,