Finish implementation of unit tests

1 files changed, 864 insertions, 17 deletions

diff --git a/tests/paca.mjs b/tests/paca.mjs
index 6390204..7c807fe 100644
--- a/tests/paca.mjs
+++ b/tests/paca.mjs
@@ -1,4 +1,4 @@
-import { explode, runTests } from "sjs";
+import { explode, reduced, runTests } from "sjs";
 
 import {
 	SyntaxError,
@@ -9,6 +9,7 @@ import {
 	tokenizeRegexFn,
 	tokenizeRegex,
 	shouldPush,
+	findLowerPrecedenceItem,
 	toPostfixStep,
 	toPostfix,
 	emptyNFA,
@@ -496,6 +497,13 @@ const test_shouldPush = t => {
 		t.assertEq(shouldPush([], null), true);
 	});
 
+	t.testing(`push when operator or stack top is "(" without ")"`, () => {
+		t.assertEq(
+			shouldPush([{ operator: "("}], { operator: ")"}),
+			false,
+		);
+	});
+
 	t.testing(`push when operator or stack top is "("`, () => {
 		t.assertEq(shouldPush([{}], { operator: "(" }), true);
 		t.assertEq(shouldPush([{ operator: "("}], {}), true);
@@ -506,6 +514,49 @@ const test_shouldPush = t => {
 	});
 };
 
+const test_findLowerPrecedenceItem = t => {
+	t.start("findLowerPrecedenceItem()");
+
+	t.testing("open parens is always stronger", () => {
+		t.assertEq(
+			findLowerPrecedenceItem([{ operator: "("}], {}),
+			0,
+		);
+		t.assertEq(
+			findLowerPrecedenceItem([
+				{ operator: "*" },
+				{ operator: "concat" },
+				{ operator: "(" },
+				{ operator: "(" },
+			], { operator: "|" }),
+			2,
+		);
+	});
+
+	t.testing("-1 if equal precedence", () => {
+		t.assertEq(
+			findLowerPrecedenceItem([
+				{ operator: "*" },
+				{ operator: "+" },
+				{ operator: "?" },
+			], { operator: "concat" }),
+			-1,
+		);
+	});
+
+	t.testing("index if lower precedence exists", () => {
+		t.assertEq(
+			findLowerPrecedenceItem([
+				{ operator: "*" },
+				{ operator: "+" },
+				{ operator: "?" },
+				{ operator: "|" },
+			], { operator: "concat" }),
+			3,
+		);
+	});
+};
+
 const test_toPostfixStep = t => {
 	t.start("toPostfixStep()");
 
@@ -529,7 +580,171 @@ const test_toPostfixStep = t => {
 		);
 	});
 
-	// FIXME: more tests
+	t.testing("error when parens are mismatched", () => {
+		try {
+			toPostfixStep(
+				{ stack: ["a"] },
+				{ operator: ")" },
+				null,
+				"TOKENS",
+			);
+			t.assertEq(true, false);
+		} catch (e) {
+			const msg = "close parens without opening: TOKENS";
+			t.assertEq(e.message, msg);
+			t.assertEq(e instanceof SyntaxError, true);
+		}
+	});
+
+	t.testing("the matched parens splits the stack", () => {
+		t.assertEq(
+			toPostfixStep(
+				{
+					out:   ["0"],
+					stack: ["a", { operator: "(" }, "b"],
+				},
+				{ operator: ")" },
+			),
+			{
+				out:   ["0", "a"],
+				stack: ["b"],
+			},
+		);
+		t.assertEq(
+			toPostfixStep(
+				{
+					out:   ["0"],
+					stack: ["a", { operator: "(" }],
+				},
+				{ operator: ")" },
+			),
+			{
+				out:   ["0", "a"],
+				stack: [],
+			},
+		);
+		t.assertEq(
+			toPostfixStep(
+				{
+					out:   ["0"],
+					stack: [{ operator: "(" }, "b"],
+				},
+				{ operator: ")" },
+			),
+			{
+				out:   ["0"],
+				stack: ["b"],
+			},
+		);
+	});
+
+	t.testing("flush stack if nothing of lower precedence", () => {
+		t.assertEq(
+			toPostfixStep(
+				{
+					out: ["0"],
+					stack: [
+						{ operator: "*" },
+						{ operator: "+" },
+						{ operator: "?" },
+						{ operator: "concat" },
+					],
+				},
+				{ operator: "|" },
+			),
+			{
+				out:   [
+					"0",
+					{ operator: "*" },
+					{ operator: "+" },
+					{ operator: "?" },
+					{ operator: "concat" },
+				],
+				stack: [{operator: "|"}],
+			},
+		);
+	});
+
+	t.testing("split the stack if lower precedence exists", () => {
+		t.assertEq(
+			toPostfixStep(
+				{
+					out: ["0"],
+					stack: [
+						{ operator: "*" },
+						{ operator: "+" },
+						{ operator: "?" },
+						{ operator: "|" },
+					],
+				},
+				{ operator: "concat" },
+			),
+			{
+				out:   [
+					"0",
+					{ operator: "*" },
+					{ operator: "+" },
+					{ operator: "?" },
+				],
+				stack: [
+					{ operator: "concat" },
+					{ operator: "|" },
+				],
+			},
+		);
+		t.assertEq(
+			toPostfixStep(
+				{
+					out: ["0"],
+					stack: [
+						{ operator: "|" },
+						{ operator: "*" },
+						{ operator: "+" },
+						{ operator: "?" },
+					],
+				},
+				{ operator: "concat" },
+			),
+			{
+				out:   [
+					"0",
+				],
+				stack: [
+					{ operator: "concat" },
+					{ operator: "|" },
+					{ operator: "*" },
+					{ operator: "+" },
+					{ operator: "?" },
+				],
+			},
+		);
+		t.assertEq(
+			toPostfixStep(
+				{
+					out: ["0"],
+					stack: [
+						{ operator: "*" },
+						{ operator: "+" },
+						{ operator: "|" },
+						{ operator: "?" },
+					],
+				},
+				{ operator: "concat" },
+			),
+			{
+				out:   [
+					"0",
+					{ operator: "*" },
+					{ operator: "+" },
+				],
+				stack: [
+					{ operator: "concat" },
+					{ operator: "|" },
+					{ operator: "?" },
+				],
+			},
+		);
+	});
 };
 
 const test_toPostfix = t => {
@@ -594,6 +809,13 @@ const test_toPostfix = t => {
 				"c",
 				concat,
 			],
+		}, {
+			in: [
+				{ operator: "(" },
+				{ operator: ")" },
+			],
+			expected: [
+			],
 		}];
 		for (const test of table) {
 			t.assertEq(
@@ -823,7 +1045,7 @@ const test_zeroOrMore = t => {
 					transitions: { a: 2 },
 				},
 				2: {
-					direct:      [ 1, 4 ],
+					direct:      [ 3 ],
 					transitions: {},
 				},
 				3: {
@@ -1107,7 +1329,7 @@ const test_buildNFA = t => {
 					transitions: {},
 				},
 				6: {
-					direct:      [ 5, 8 ],
+					direct:      [ 7 ],
 					transitions: {},
 				},
 				7: {
@@ -1155,28 +1377,135 @@ const test_allDirects = t => {
 	t.start("allDirects()");
 
 	t.testing("empty directs", () => {
+		const input = {
+			1: {},
+			2: {},
+			3: { direct: [] },
+			4: {},
+			5: {},
+		};
+		t.assertEq(allDirects(3, input), [3]);
 	});
 
 	t.testing("single level", () => {
+		const input = {
+			1: { direct: [3] },
+			2: { direct: [4] },
+			3: { direct: []  },
+			4: { direct: []  },
+		};
+		t.assertEq(allDirects(1, input), [3]);
 	});
 
 	t.testing("deep recursion", () => {
+		const input = {
+			1: { direct: [2] },
+			2: { direct: [3] },
+			3: { direct: [4] },
+			4: { direct: [5] },
+			5: { direct: []  },
+		};
+		t.assertEq(allDirects(1, input), [5]);
+		t.assertEq(allDirects(2, input), [5]);
+		t.assertEq(allDirects(3, input), [5]);
+		t.assertEq(allDirects(4, input), [5]);
+		t.assertEq(allDirects(5, input), [5]);
 	});
 
 	t.testing("plenty of duplicates", () => {
+		const input = {
+			1: { direct: [2, 3, 4] },
+			2: { direct: [3, 4, 5] },
+			3: { direct: [4, 5, 6] },
+			4: { direct: [5, 6] },
+			5: { direct: [] },
+			6: { direct: [] },
+		};
+		t.assertEq(allDirects(1, input), [5, 6]);
 	});
 };
 
 const test_searchNFAStep = t => {
 	t.start("searchNFAStep()");
 
-	t.testing("FIXME", () => {});
+	t.testing("empty on empty input", () => {
+		t.assertEq(searchNFAStep({})([], null), []);
+	});
+
+	t.testing("empty on empty transitions", () => {
+		const nodes = {
+			1: { transitions: {} },
+			2: { transitions: {} },
+			3: { transitions: {} },
+		};
+		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a"), []);
+	});
+
+	t.testing("empty on non-matching transitions", () => {
+		const nodes = {
+			1: { transitions: { b: 2 } },
+			2: { transitions: { c: 3 } },
+			3: { transitions: { d: 1 } },
+		};
+		t.assertEq(searchNFAStep(nodes)([1, 2, 3], "a"), []);
+	});
+
+	t.testing("leaves given by allDirects() otherwise", () => {
+		const nodes = {
+			1: {
+				direct:      [],
+				transitions: { a: 5 },
+			},
+			2: {
+				direct:      [],
+				transitions: { b: 5 },
+			},
+			3: {
+				direct:      [],
+				transitions: { a: 4 },
+			},
+			4: {
+				direct:      [6, 7, 8],
+				transitions: {},
+			},
+			5: {
+				direct:      [],
+				transitions: { a: 2 },
+			},
+			6: {
+				direct:      [],
+				transitions: { b: 7 },
+			},
+			7: {
+				direct:      [],
+				transitions: { c: 8 },
+			},
+			8: {
+				direct     : [],
+				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 test_searchNFAFn = t => {
 	t.start("searchNFAFn()");
 
-	t.testing("FIXME", () => {});
+	t.testing("on composed sample regex", () => {
+		const regex = "(a|b)*c";
+		const nfa = buildNFA(toPostfix(tokenizeRegex(explode(regex))));
+		t.assertEq(searchNFAFn(nfa, "c"), [10]);
+		t.assertEq(searchNFAFn(nfa, "cc"), []);
+		t.assertEq(searchNFAFn(nfa, "aaabbbc"), [10]);
+		t.assertEq(searchNFAFn(nfa, "a"), [1, 3, 9]);
+	});
 };
 
 const test_searchNFA = t => {
@@ -1188,6 +1517,9 @@ const test_searchNFA = t => {
 		t.assertEq(searchNFA(nfa, "c"), true);
 		t.assertEq(searchNFA(nfa, "cc"), false);
 		t.assertEq(searchNFA(nfa, "aaabbbc"), true);
+		t.assertEq(searchNFA(nfa, "ababac"), true);
+		t.assertEq(searchNFA(nfa, "babac"), true);
+		t.assertEq(searchNFA(nfa, "babaca"), false);
 	});
 };
 
@@ -1226,43 +1558,368 @@ const test_unNodeID = t => {
 const test_collectTransitions = t => {
 	t.start("collectTransitions()");
 
-	t.testing("FIXME", () => {});
+	t.testing("empty values", () => {
+		t.assertEq(collectTransitions({}, []), {});
+		t.assertEq(collectTransitions({ a: 1 }, []), {});
+	});
+
+	t.testing("no transitions in states", () => {
+		t.assertEq(
+			collectTransitions(
+				{
+					1: { transitions: {} },
+					2: { transitions: {} },
+					3: { transitions: {} },
+				},
+				[1, 3],
+			),
+			{},
+		);
+	});
+
+	t.testing("error on transitions have more than one possibility", () => {
+		try {
+			collectTransitions(
+				{ 1: { transitions: { b: 2, c: 3 }}},
+				[1],
+			);
+			t.assertEq(true, false);
+		} catch (e) {
+			const msg =
+				"unexpected transitions with more than 1 key";
+			t.assertEq(e.message, msg);
+		}
+	});
+
+	t.testing("many values grouped under a single transition key", () => {
+		const nodes = {
+			1: {
+				direct:      [],
+				transitions: { a: 2 },
+			},
+			2: {
+				direct:      [],
+				transitions: { a: 3 },
+			},
+			3: {
+				direct:      [],
+				transitions: { a: 4 },
+			},
+			4: {
+				direct:      [],
+				transitions: {},
+			},
+		};
+		t.assertEq(collectTransitions(nodes, []), {});
+		t.assertEq(collectTransitions(nodes, [1]), { a: [2]});
+		t.assertEq(collectTransitions(nodes, [1, 2]), { a: [2, 3]});
+		t.assertEq(
+			collectTransitions(nodes, [1, 2, 3]),
+			{ a: [2, 3, 4]},
+		);
+		t.assertEq(
+			collectTransitions(nodes, [1, 2, 3, 4]),
+			{ a: [2, 3, 4]},
+		);
+	});
+
+	t.testing("transition with multiple direct values", () => {
+		const nodes = {
+			1: {
+				direct:      [],
+				transitions: { a: 2 },
+			},
+			2: {
+				direct:      [ 3 ],
+				transitions: {},
+			},
+			3: {
+				direct:      [ 4 ],
+				transitions: {},
+			},
+			4: {
+				direct:      [],
+				transitions: { a: 2 },
+			},
+		};
+		t.assertEq(collectTransitions(nodes, [1]), { a: [4]});
+		t.assertEq(collectTransitions(nodes, [1, 2, 3, 4]), { a: [4]});
+	});
 };
 
 const test_computePending = t => {
 	t.start("computePending()");
 
-	t.testing("FIXME", () => {});
+	t.testing("empty values", () => {
+		t.assertEq(computePending([], []), [])
+		t.assertEq(computePending([["IGNORED"]], []), [])
+	});
+
+	t.testing("deduped states", () => {
+		t.assertEq(
+			computePending(
+				[null, [1, 2], [2, 3], [1, 3], [1, 2]],
+				[],
+			),
+			[[1, 2], [1, 3], [2, 3]],
+		);
+		t.assertEq(
+			computePending(
+				[null, [1, 2], [1, 3]],
+				[[2, 3], [1, 2], [1, 3]],
+			),
+			[[1, 2], [1, 3], [2, 3]],
+		);
+	});
 };
 
 const test_buildDFANodes = t => {
 	t.start("buildDFANodes()");
 
-	t.testing("FIXME", () => {});
+	t.testing("empty values", () => {
+		t.assertEq(buildDFANodes(null, null, [], "RET"), "RET");
+	});
+
+	t.testing("ignore states that were already built", () => {
+		const nodes = {
+			"1-2-3": true,
+		};
+		const states = [[1, 2, 3], [3, 2, 1]];
+		t.assertEq(buildDFANodes(null, null, states, nodes), nodes);
+	});
+
+	t.testing("recursively build the DFA", () => {
+		const end = 4;
+		const nfaNodes = {
+			1: {
+				direct:      [],
+				transitions: { a: 2 },
+			},
+			2: {
+				direct:      [ 1, 3 ],
+				transitions: {},
+			},
+			3: {
+				direct:      [],
+				transitions: { b: 4 },
+			},
+			4: {
+				direct:      [],
+				transitions: {},
+			},
+		};
+		const pending = [[1], [1, 2], [1, 3, 4], [4], [1, 2]];
+		const dfaNodes = {};
+		const expected = {
+			"1": {
+				end:         false,
+				transitions: { a: "1-3" },
+			},
+			"1-2": {
+				end:         false,
+				transitions: { a: "1-3" },
+			},
+			"1-3": {
+				end:         false,
+				transitions: { a: "1-3", b: "4" }
+			},
+			"1-3-4": {
+				end:         true,
+				transitions: { a: "1-3", b: "4" },
+			},
+			"4": {
+				end:         true,
+				transitions: {},
+			},
+		};
+		t.assertEq(
+			buildDFANodes(end, nfaNodes, pending, dfaNodes),
+			expected,
+		);
+	});
 };
 
 const test_buildDFA = t => {
 	t.start("buildDFA()");
 
-	t.testing("FIXME", () => {});
+	t.testing("minimal NFA", () => {
+		const nfa = {
+			start:  1,
+			end:    2,
+			nextID: 3,
+			nodes:  {
+				1: {
+					direct:      [ 2 ],
+					transitions: {},
+				},
+				2: {
+					direct:      [],
+					transitions: {},
+				},
+			},
+		};
+		const expected = {
+			start: "2",
+			nodes: {
+				"2": {
+					end:         true,
+					transitions: {},
+				},
+			},
+		};
+		t.assertEq(buildDFA(nfa), expected);
+	});
+
+	t.testing("sample regex NFA", () => {
+		const nfa = {
+			start:  7,
+			end:    10,
+			nextID: 11,
+			nodes:  {
+				1: {
+					direct:      [],
+					transitions: { a: 2 },
+				},
+				2: {
+					direct:      [ 6 ],
+					transitions: {},
+				},
+				3: {
+					direct:      [],
+					transitions: { b: 4 },
+				},
+				4: {
+					direct:      [ 6 ],
+					transitions: {},
+				},
+				5: {
+					direct:      [ 1, 3 ],
+					transitions: {},
+				},
+				6: {
+					direct:      [ 7 ],
+					transitions: {},
+				},
+				7: {
+					direct:      [ 5, 8 ],
+					transitions: {},
+				},
+				8: {
+					direct:      [ 9 ],
+					transitions: {},
+				},
+				9: {
+					direct:      [],
+					transitions: { c: 10 },
+				},
+				10: {
+					direct:      [],
+					transitions: {},
+				},
+			},
+		};
+		const expected = {
+			start: "1-3-9",
+			nodes: {
+				"1-3-9": {
+					end:         false,
+					transitions: {
+						a: "1-3-9",
+						b: "1-3-9",
+						c: "10",
+					},
+				},
+				"10": {
+					end:         true,
+					transitions: {},
+				},
+			},
+		};
+		t.assertEq(nfa, compileNFA("(a|b)*c"));
+		t.assertEq(buildDFA(nfa), expected);
+	});
 };
 
 const test_searchDFAStep = t => {
 	t.start("searchDFAStep()");
 
-	t.testing("FIXME", () => {});
+	t.testing("transition must exist", () => {
+		const nodes = {
+			"1": {
+				transitions: {
+					a: "1",
+					b: "1-2",
+					c: "1-3-9",
+				},
+			},
+			"1-2": {
+				transitions: {
+					x: "1-3-9",
+				},
+			},
+			"1-3-9": {
+				transitions: {},
+			},
+		};
+		const fn = searchDFAStep(nodes);
+		t.assertEq(fn("1", "a"), "1");
+		t.assertEq(fn("1", "b"), "1-2");
+		t.assertEq(fn("1", "c"), "1-3-9");
+		t.assertEq(fn("1", "d"), reduced(false));
+		t.assertEq(fn("1-2", "x"), "1-3-9");
+		t.assertEq(fn("1-2", "y"), reduced(false));
+		t.assertEq(fn("1-3-9", "a"), reduced(false));
+	});
+
+	t.testing("error on non-existent state", () => {
+		try {
+			searchDFAStep({})("non-existent", null);
+			t.assertEq(true, false);
+		} catch (e) {
+			const msg =
+				"Cannot read properties of undefined " +
+				"(reading 'transitions')";
+			t.assertEq(e.message, msg);
+		}
+	});
 };
 
 const test_searchDFAFn = t => {
 	t.start("searchDFAFn()");
 
-	t.testing("FIXME", () => {});
+	t.testing("on composed sample regex", () => {
+		const regex = "(a|b)*c";
+		const dfa = buildDFA(
+			buildNFA(toPostfix(tokenizeRegex(explode(regex)))),
+		);
+		t.assertEq(searchDFAFn(dfa, "a"), "1-3-9");
+		t.assertEq(searchDFAFn(dfa, "b"), "1-3-9");
+		t.assertEq(searchDFAFn(dfa, "c"), "10");
+		t.assertEq(searchDFAFn(dfa, "cc"), false);
+		t.assertEq(searchDFAFn(dfa, "aaabbbc"), "10");
+		t.assertEq(searchDFAFn(dfa, "ababac"), "10");
+		t.assertEq(searchDFAFn(dfa, "babac"), "10");
+		t.assertEq(searchDFAFn(dfa, "babaca"), false);
+	});
 };
 
 const test_searchDFA = t => {
 	t.start("searchDFA()");
 
-	t.testing("FIXME", () => {});
+	t.testing("on composed sample regex", () => {
+		const regex = "(a|b)*c";
+		const dfa = buildDFA(
+			buildNFA(toPostfix(tokenizeRegex(explode(regex)))),
+		);
+		t.assertEq(searchDFA(dfa, "a"), false);
+		t.assertEq(searchDFA(dfa, "b"), false);
+		t.assertEq(searchDFA(dfa, "c"), true);
+		t.assertEq(searchDFA(dfa, "cc"), false);
+		t.assertEq(searchDFA(dfa, "aaabbbc"), true);
+		t.assertEq(searchDFA(dfa, "ababac"), true);
+		t.assertEq(searchDFA(dfa, "babac"), true);
+		t.assertEq(searchDFA(dfa, "babaca"), false);
+	});
 };
 
 const test_compileNFA = t => {
@@ -1286,6 +1943,138 @@ const test_compileNFA = t => {
 		};
 		t.assertEq(compileNFA(""), expected);
 	});
+	t.testing("compiled sample regex", () => {
+		const nfa1 = compileNFA("(a|b)*c");
+		const expected1 = {
+			start:  7,
+			end:    10,
+			nextID: 11,
+			nodes: {
+				1: {
+					direct:      [],
+					transitions: { a: 2 },
+				},
+				2: {
+					direct:      [ 6 ],
+					transitions: {},
+				},
+				3: {
+					direct:      [],
+					transitions: { b: 4 },
+				},
+				4: {
+					direct:      [ 6 ],
+					transitions: {},
+				},
+				5: {
+					direct:      [ 1, 3 ],
+					transitions: {},
+				},
+				6: {
+					direct:      [ 7 ],
+					transitions: {},
+				},
+				7: {
+					direct:      [ 5, 8 ],
+					transitions: {},
+				},
+				8: {
+					direct:      [ 9 ],
+					transitions: {},
+				},
+				9: {
+					direct:      [],
+					transitions: { c: 10 },
+				},
+				10: {
+					direct:      [],
+					transitions: {},
+				},
+			},
+		};
+		const nfa2 = compileNFA("((a+b)?c|d)*e");
+		const expected2 = {
+			start:  15,
+			end:    18,
+			nextID: 19,
+			nodes: {
+				1: {
+					direct:      [],
+					transitions: { a: 2 },
+				},
+				2: {
+					direct:      [ 3 ],
+					transitions: {},
+				},
+				3: {
+					direct:      [ 1, 4 ],
+					transitions: {},
+				},
+				4: {
+					direct:      [ 5 ],
+					transitions: {},
+				},
+				5: {
+					direct:      [],
+					transitions: { b: 6 },
+				},
+				6: {
+					direct:      [ 8 ],
+					transitions: {},
+				},
+				7: {
+					direct:      [ 1, 8 ],
+					transitions: {},
+				},
+				8: {
+					direct:      [ 9 ],
+					transitions: {},
+				},
+				9: {
+					direct:      [],
+					transitions: { c: 10 },
+				},
+				10: {
+					direct:      [ 14 ],
+					transitions: {},
+				},
+				11: {
+					direct:      [],
+					transitions: { d: 12 },
+				},
+				12: {
+					direct:      [ 14 ],
+					transitions: {},
+				},
+				13: {
+					direct:      [ 7, 11 ],
+					transitions: {},
+				},
+				14: {
+					direct:      [ 15 ],
+					transitions: {},
+				},
+				15: {
+					direct:      [ 13, 16 ],
+					transitions: {},
+				},
+				16: {
+					direct:      [ 17 ],
+					transitions: {},
+				},
+				17: {
+					direct:      [],
+					transitions: { e: 18 },
+				},
+				18: {
+					direct:      [],
+					transitions: {},
+				},
+			},
+		};
+		t.assertEq(nfa1, expected1);
+		t.assertEq(nfa2, expected2);
+	});
 
 	t.testing("composed sample regex", () => {
 		const nfa = compileNFA("(a|b)*c");
@@ -1298,16 +2087,73 @@ const test_compileNFA = t => {
 const test_compileDFA = t => {
 	t.start("compileDFA()");
 
-	t.testing("FIXME", () => {});
+	t.testing("compiled sample regex", () => {
+		const dfa1 = compileDFA("(a|b)*c");
+		const dfa2 = compileDFA("((a+b)?c|d)*e");
+		const expected1 = {
+			start: "1-3-9",
+			nodes: {
+				"1-3-9": {
+					end:         false,
+					transitions: {
+						a: "1-3-9",
+						b: "1-3-9",
+						c: "10",
+					},
+				},
+				"10": {
+					end:         true,
+					transitions: {},
+				},
+			},
+		};
+		const expected2 = {
+			start: "1-9-11-17",
+			nodes: {
+				"1-5": {
+					end:         false,
+					transitions: {
+						a: "1-5",
+						b: "9",
+					},
+				},
+				"1-9-11-17": {
+					end:         false,
+					transitions: {
+						a: "1-5",
+						d: "1-9-11-17",
+						e: "18",
+						c: "1-9-11-17",
+					},
+				},
+				"9": {
+					end:         false,
+					transitions: {
+						c: "1-9-11-17",
+					},
+				},
+				"18": {
+					end:         true,
+					transitions: {},
+				},
+			},
+		};
+		t.assertEq(dfa1, expected1);
+		t.assertEq(dfa2, expected2);
+	});
 };
 
 const test_compile = t => {
 	t.start("compile()");
 
 	t.testing("composed sample regex", () => {
-		const matcher = compile("(a|b)*c");
-		t.assertEq(matcher("ababac"),  true);
-		t.assertEq(matcher("ababaca"), false);
+		const matcher1 = compile("(a|b)*c");
+		t.assertEq(matcher1("ababac"),  true);
+		t.assertEq(matcher1("ababaca"), false);
+
+		const matcher2 = compile("((a+)b)*c");
+		t.assertEq(matcher2("aaababc"), true);
+		t.assertEq(matcher2("aaabbc"), false);
 	});
 };
 
@@ -1320,6 +2166,7 @@ runTests([
 	test_tokenizeRegexFn,
 	test_tokenizeRegex,
 	test_shouldPush,
+	test_findLowerPrecedenceItem,
 	test_toPostfixStep,
 	test_toPostfix,
 	test_emptyNFA,