From 6b626f2e0408e52f771e0895648b4b75060ec082 Mon Sep 17 00:00:00 2001 From: EuAndreh Date: Tue, 1 Jul 2025 13:45:29 -0300 Subject: Implement v0 version of NFA and DFA; WIP tests --- tests/paca.mjs | 1351 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1351 insertions(+) create mode 100644 tests/paca.mjs (limited to 'tests/paca.mjs') diff --git a/tests/paca.mjs b/tests/paca.mjs new file mode 100644 index 0000000..6390204 --- /dev/null +++ b/tests/paca.mjs @@ -0,0 +1,1351 @@ +import { explode, runTests } from "sjs"; + +import { + SyntaxError, + ConcatStep, + shouldConcat, + isOperator, + tokenizeRegexStep, + tokenizeRegexFn, + tokenizeRegex, + shouldPush, + toPostfixStep, + toPostfix, + emptyNFA, + baseNFA, + concat, + union, + zeroOrMore, + oneOrMore, + zeroOrOne, + OPERATORS_FNS, + buildNFAStep, + buildNFA, + allDirects, + searchNFAStep, + searchNFAFn, + searchNFA, + nodeID, + unNodeID, + collectTransitions, + computePending, + buildDFANodes, + buildDFA, + searchDFAStep, + searchDFAFn, + searchDFA, + compileNFA, + compileDFA, + compile, +} from "../src/paca.exported.mjs"; + + + +const test_shouldConcat = t => { + t.start("shouldConcat()"); + + t.testing("do concat literal chars", () => { + t.assertEq(shouldConcat("a", "b"), true); + }); + + t.testing("but not when they're the last one", () => { + t.assertEq(shouldConcat("a", undefined), false); + t.assertEq(shouldConcat("b", undefined), false); + }); + + t.testing("do not concat when starting a parens group", () => { + t.assertEq(shouldConcat("(", "a"), false); + t.assertEq(shouldConcat("(", "b"), false); + }); + + t.testing("do not concat when starting a union", () => { + t.assertEq(shouldConcat("|", "a"), false); + t.assertEq(shouldConcat("|", "b"), false); + }); + + t.testing("do not concat when next is special", () => { + t.assertEq(shouldConcat("a", "*"), false); + t.assertEq(shouldConcat("a", "|"), false); + t.assertEq(shouldConcat("a", ")"), false); + }); +}; + +const test_isOperator = t => { + t.start("isOperator()"); + + t.testing("operators and open parens are true", () => { + t.assertEq(isOperator("*"), true); + t.assertEq(isOperator("|"), true); + t.assertEq(isOperator("+"), true); + t.assertEq(isOperator("?"), true); + t.assertEq(isOperator("("), true); + t.assertEq(isOperator(")"), true); + }); + + t.testing("false for everyday non-meta chars", () => { + t.assertEq(isOperator("a"), false); + t.assertEq(isOperator("_"), false); + }); +}; + +const test_tokenizeRegexStep = t => { + t.start("tokenizeRegexStep()"); + + t.testing("when escaping we get whatever the char is", () => { + const stepFn = tokenizeRegexStep("ab|(cd)*"); + const steps = [{ + char: "a", + index: 0, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["a", { operator: "concat" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "b", + index: 1, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["b"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "|", + index: 2, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["|"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "(", + index: 3, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["("], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "c", + index: 4, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["c", {operator: "concat"}], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "d", + index: 5, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["d"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: ")", + index: 6, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: [")"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "*", + index: 7, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["*"], + state: ConcatStep.ACCEPTING, + }, + }]; + for (const step of steps) { + t.assertEq( + stepFn(step.in, step.char, step.index), + step.out, + ); + } + }); + + t.testing("trailing escape errors", () => { + try { + t.assertEq(tokenizeRegexStep("\\")({ + out: [], + index: 0, + state: ConcatStep.ACCEPTING, + }, "\\"), null); + t.assertEq(true, false); + } catch (e) { + const message = "bad trailing escape character: "; + t.assertEq( + e.message.substring(0, message.length), + message, + ); + t.assertEq(e instanceof SyntaxError, true); + } + }); + + t.testing("escape makes it enter escaping mode", () => { + const stepFn = tokenizeRegexStep("\\a\\*"); + const steps = [{ + char: "\\", + index: 0, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [], + state: ConcatStep.ESCAPING, + }, + }, { + char: "a", + index: 1, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["a", { operator: "concat" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "\\", + index: 2, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [], + state: ConcatStep.ESCAPING, + }, + }, { + char: "*", + index: 3, + in: { + out: [], + state: ConcatStep.ESCAPING, + }, + out: { + out: ["*"], + state: ConcatStep.ACCEPTING, + }, + }]; + for (const step of steps) { + t.assertEq( + stepFn(step.in, step.char, step.index), + step.out, + ); + } + }); + + t.testing("operators get detected as such", () => { + const stepFn = tokenizeRegexStep("ab|(cd)*"); + const steps = [{ + char: "a", + index: 0, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: ["a", { operator: "concat" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "b", + index: 1, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: ["b"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "|", + index: 2, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [{ operator: "|" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "(", + index: 3, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [{ operator: "(" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "c", + index: 4, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: ["c", { operator: "concat" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "d", + index: 5, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: ["d"], + state: ConcatStep.ACCEPTING, + }, + }, { + char: ")", + index: 6, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [{ operator: ")" }], + state: ConcatStep.ACCEPTING, + }, + }, { + char: "*", + index: 7, + in: { + out: [], + state: ConcatStep.ACCEPTING, + }, + out: { + out: [{ operator: "*" }], + state: ConcatStep.ACCEPTING, + }, + }]; + for (const step of steps) { + t.assertEq( + stepFn(step.in, step.char, step.index), + step.out, + ); + } + }); +}; + +const test_tokenizeRegexFn = t => { + t.start("tokenizeRegexFn"); + + t.testing("regex table", () => { + const concat = { operator: "concat" }; + const star = { operator: "*" }; + const table = [{ + in: "", + expected: { + out: [], + state: ConcatStep.ACCEPTING, + }, + }, { + in: "a", + expected: { + out: ["a"], + state: ConcatStep.ACCEPTING, + }, + }, { + in: "a*", + expected: { + out: ["a", star], + state: ConcatStep.ACCEPTING, + }, + }, { + in: "a*b", + expected: { + out: ["a", star, concat, "b"], + state: ConcatStep.ACCEPTING, + }, + }]; + for (const test of table) { + t.assertEq( + tokenizeRegexFn(explode(test.in)), + test.expected, + ); + } + }); +}; + +const test_tokenizeRegex = t => { + t.start("tokenizeRegex()"); + + t.testing("regex table", () => { + const concat = { operator: "concat" }; + const star = { operator: "*" }; + const table = [{ + in: "", + expected: [] + }, { + in: "a", + expected: [ "a" ], + }, { + in: "ab", + expected: [ "a", concat, "b" ], + }, { + in: "abc", + expected: [ "a", concat, "b", concat, "c" ], + }, { + in: "a*", + expected: [ "a", star], + }, { + in: "ab*", + expected: [ "a", concat, "b", star], + }, { + in: "a*b*", + expected: [ "a", star, concat, "b", star], + }, { + in: "a|b", + expected: [ "a", { operator: "|" }, "b" ], + }, { + in: "a(bc(d))ef", + expected: [ + "a", + concat, + { operator: "(" }, + "b", + concat, + "c", + concat, + { operator: "(" }, + "d", + { operator: ")" }, + { operator: ")" }, + concat, + "e", + concat, + "f", + ], + }, { + in: "ab|(cd)*", + expected: [ + "a", + concat, + "b", + { operator: "|" }, + { operator: "(" }, + "c", + concat, + "d", + { operator: ")" }, + star, + ], + }, { + in: "(a|b)*c", + expected: [ + { operator: "(" }, + "a", + { operator: "|" }, + "b", + { operator: ")" }, + star, + concat, + "c", + ], + }]; + for (const test of table) { + t.assertEq( + tokenizeRegex(explode(test.in)), + test.expected, + ); + } + }); +}; + +const test_shouldPush = t => { + t.start("shouldPush()"); + + t.testing("always push on empty stack", () => { + t.assertEq(shouldPush([], "a"), true); + t.assertEq(shouldPush([], null), true); + }); + + t.testing(`push when operator or stack top is "("`, () => { + t.assertEq(shouldPush([{}], { operator: "(" }), true); + t.assertEq(shouldPush([{ operator: "("}], {}), true); + }); + + t.testing("don't push otherwise", () => { + t.assertEq(shouldPush([{}], {}), false); + }); +}; + +const test_toPostfixStep = t => { + t.start("toPostfixStep()"); + + t.testing("string literals go directly to out", () => { + t.assertEq( + toPostfixStep({ out: ["a"], stack: "stack" }, "t"), + { out: ["a", "t"], stack: "stack" }, + ); + }); + + t.testing("parens put things on the stack", () => { + t.assertEq( + toPostfixStep({ + out: "out", + stack: [{ operator: "(" }], + }, { operator: "X" }), + { out: "out", stack: [ + { operator: "X" }, + { operator: "(" }, + ]}, + ); + }); + + // FIXME: more tests +}; + +const test_toPostfix = t => { + t.start("toPostfix()"); + + t.testing("regex table", () => { + const concat = { operator: "concat" }; + const table = [{ + in: [], + expected: [] + }, { + in: [ "a" ], + expected: [ "a" ], + }, { + in: [ "a", concat, "b", concat, "c" ], + expected: [ "a", "b", concat, "c", concat ], + }, { + in: [ "a", { operator: "*" }], + expected: [ "a", { operator: "*" }], + }, { + in: [ "a", { operator: "|" }, "b" ], + expected: [ "a", "b", { operator: "|" } ], + }, { + in: [ + "a", + concat, + "b", + { operator: "|" }, + { operator: "(" }, + "c", + concat, + "d", + { operator: ")" }, + { operator: "*" }, + ], + expected: [ + "a", + "b", + concat, + "c", + "d", + concat, + { operator: "*" }, + { operator: "|" }, + ], + }, { + in: [ + { operator: "(" }, + "a", + { operator: "|" }, + "b", + { operator: ")" }, + { operator: "*" }, + concat, + "c", + ], + expected: [ + "a", + "b", + { operator: "|" }, + { operator: "*" }, + "c", + concat, + ], + }]; + for (const test of table) { + t.assertEq( + toPostfix(test.in), + test.expected, + ); + } + }); +}; + +const test_emptyNFA = t => { + t.start("emptyNFA()"); + + t.testing("we deterministically build out of the ID", () => { + const expected = { + start: 1, + end: 2, + nextID: 3, + nodes: { + 1: { + direct: [ 2 ], + transitions: {}, + }, + 2: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(emptyNFA(), expected); + }); +}; + +const test_baseNFA = t => { + t.start("baseNFA()"); + + t.testing("the given edge connects the nodes", () => { + const expected = { + start: 123, + end: 124, + nextID: 125, + nodes: { + 123: { + direct: [], + transitions: { X: 124 }, + }, + 124: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(baseNFA("X", 123), expected); + }); +}; + +const test_concat = t => { + t.start("concat()"); + + t.testing("on baseNFA() and on more complex NFAs", () => { + const a = baseNFA("a", 1); + const b = baseNFA("b", a.nextID); + const a_ = baseNFA("a", b.nextID); + const expected1 = { + start: 1, + end: 4, + nextID: 5, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 3 ], + transitions: {}, + }, + 3: { + direct: [], + transitions: { b: 4 }, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(concat(a, b), expected1); + + const expected2 = { + start: 1, + end: 6, + nextID: 7, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 3 ], + transitions: {}, + }, + 3: { + direct: [], + transitions: { b: 4 }, + }, + 4: { + direct: [ 5 ], + transitions: {}, + }, + 5: { + direct: [], + transitions: { a: 6 }, + }, + 6: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(concat(concat(a, b), a_), expected2); + }); +}; + +const test_union = t => { + t.start("union()"); + + t.testing("on baseNFA() and on more complex NFAs", () => { + const a = baseNFA("a", 1); + const b = baseNFA("b", a.nextID); + const expected1 = { + start: 5, + end: 6, + nextID: 7, + 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: [], + transitions: {}, + }, + }, + }; + t.assertEq(union(a, b), expected1); + + const c = baseNFA("c", expected1.nextID); + const expected2 = { + start: 9, + 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: [ 10 ], + transitions: {}, + }, + 7: { + direct: [], + transitions: { c: 8 }, + }, + 8: { + direct: [ 10 ], + transitions: {}, + }, + 9: { + direct: [ 5, 7 ], + transitions: {}, + }, + 10: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(union(union(a, b), c), expected2); + }); +}; + +const test_zeroOrMore = t => { + t.start("zeroOrMore()"); + + t.testing("on baseNFA()", () => { + const a = baseNFA("a", 1); + const expected = { + start: 3, + end: 4, + nextID: 5, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 1, 4 ], + transitions: {}, + }, + 3: { + direct: [ 1, 4 ], + transitions: {}, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(zeroOrMore(a), expected); + }); +}; + +const test_oneOrMore = t => { + t.start("oneOrMore()"); + + t.testing("on baseNFA()", () => { + const a = baseNFA("a", 1); + const expected = { + start: 1, + end: 4, + nextID: 5, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 3 ], + transitions: {}, + }, + 3: { + direct: [ 1, 4 ], + transitions: {}, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(oneOrMore(a), expected); + }); +}; + +const test_zeroOrOne = t => { + t.start("zeroOrOne()"); + + t.testing("on baseNFA()", () => { + const a = baseNFA("a", 1); + const expected = { + start: 3, + end: 4, + nextID: 5, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 4 ], + transitions: {}, + }, + 3: { + direct: [ 1, 4 ], + transitions: {}, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(zeroOrOne(a), expected); + }); +}; + +const test_OPERATORS_FNS = t => { + t.start("OPERATORS_FNS"); + + const arr = []; + const fn = ret => (...args) => { + arr.push({ + args, + ret, + }); + return ret; + }; + const input = [1, 2, 3]; + + + t.testing("star", () => { + arr.splice(0); + t.assertEq( + OPERATORS_FNS({ zeroOrMoreFn: fn(111) })["*"](input), + [1, 2, 111], + ); + t.assertEq(arr, [{ args: [3], ret: 111 }]); + }); + + t.testing("plus", () => { + arr.splice(0); + t.assertEq( + OPERATORS_FNS({ oneOrMoreFn: fn(222) })["+"](input), + [1, 2, 222], + ); + t.assertEq(arr, [{ args: [3], ret: 222 }]); + }); + + t.testing("question mark", () => { + arr.splice(0); + t.assertEq( + OPERATORS_FNS({ zeroOrOneFn: fn(333) })["?"](input), + [1, 2, 333], + ); + t.assertEq(arr, [{ args: [3], ret: 333 }]); + }); + + t.testing("pipe", () => { + arr.splice(0); + t.assertEq( + OPERATORS_FNS({ unionFn: fn(444) })["|"](input), + [1, 444], + ); + t.assertEq(arr, [{ args: [2, 3], ret: 444 }]); + }); + + t.testing("concat", () => { + arr.splice(0); + t.assertEq( + OPERATORS_FNS({ concatFn: fn(555) })["concat"](input), + [1, 555], + ); + t.assertEq(arr, [{ args: [2, 3], ret: 555 }]); + }); +}; + +const test_buildNFAStep = t => { + t.start("buildNFAStep()"); + + t.testing("literal char without existing nextID", () => { + const expected = [{ + start: 1, + end: 2, + nextID: 3, + nodes: { + 1: { + direct: [], + transitions: { t: 2 }, + }, + 2: { + direct: [], + transitions: {}, + }, + + }, + }]; + t.assertEq(buildNFAStep([], "t"), expected); + }); + + t.testing("literal char with existing nextID", () => { + const input = baseNFA("a", 1); + const expected = [{ + start: 1, + end: 2, + nextID: 3, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [], + transitions: {}, + }, + }, + }, { + start: 3, + end: 4, + nextID: 5, + nodes: { + 3: { + direct: [], + transitions: { b: 4 }, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }]; + t.assertEq(buildNFAStep([input], "b"), expected); + t.assertEq( + buildNFAStep([input], "b"), + [ baseNFA("a", 1), baseNFA("b", 3) ] + ); + }); + + t.testing("operator", () => { + const input = [ baseNFA("a", 1), baseNFA("b", 3) ]; + const expected = [{ + start: 1, + end: 4, + nextID: 5, + nodes: { + 1: { + direct: [], + transitions: { a: 2 }, + }, + 2: { + direct: [ 3 ], + transitions: {}, + }, + 3: { + direct: [], + transitions: { b: 4 }, + }, + 4: { + direct: [], + transitions: {}, + }, + }, + }]; + t.assertEq( + buildNFAStep(input, { operator: "concat" }), + expected, + ); + }); +}; + +const test_buildNFA = t => { + t.start("buildNFA()"); + + t.testing("empty regex pattern", () => { + const expected = { + start: 1, + end: 2, + nextID: 3, + nodes: { + 1: { + direct: [ 2 ], + transitions: {}, + }, + 2: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(buildNFA([]), expected); + }); + + t.testing("sample composed regex", () => { + const regex = "(a|b)*cde"; + const expected = { + start: 7, + end: 14, + nextID: 15, + 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: [ 5, 8 ], + transitions: {}, + }, + 7: { + direct: [ 5, 8 ], + transitions: {}, + }, + 8: { + direct: [ 9 ], + transitions: {}, + }, + 9: { + direct: [], + transitions: { c: 10 }, + }, + 10: { + direct: [ 11 ], + transitions: {}, + }, + 11: { + direct: [], + transitions: { d: 12 }, + }, + 12: { + direct: [ 13 ], + transitions: {}, + }, + 13: { + direct: [], + transitions: { e: 14 }, + }, + 14: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq( + buildNFA(toPostfix(tokenizeRegex(explode(regex)))), + expected, + ); + }); +}; + +const test_allDirects = t => { + t.start("allDirects()"); + + t.testing("empty directs", () => { + }); + + t.testing("single level", () => { + }); + + t.testing("deep recursion", () => { + }); + + t.testing("plenty of duplicates", () => { + }); +}; + +const test_searchNFAStep = t => { + t.start("searchNFAStep()"); + + t.testing("FIXME", () => {}); +}; + +const test_searchNFAFn = t => { + t.start("searchNFAFn()"); + + t.testing("FIXME", () => {}); +}; + +const test_searchNFA = t => { + t.start("searchNFA()"); + + t.testing("on composed sample regex", () => { + const regex = "(a|b)*c"; + const nfa = buildNFA(toPostfix(tokenizeRegex(explode(regex)))); + t.assertEq(searchNFA(nfa, "c"), true); + t.assertEq(searchNFA(nfa, "cc"), false); + t.assertEq(searchNFA(nfa, "aaabbbc"), true); + }); +}; + +const test_nodeID = t => { + t.start("nodeID()"); + + t.testing("single number", () => { + t.assertEq(nodeID([1]), "1"); + }); + + t.testing("plenty of duplicates", () => { + t.assertEq(nodeID([1, 1, 1, 1, 1, 1]), "1"); + }); + + t.testing("unsorted input", () => { + t.assertEq( + nodeID([5, 5, 11, 11, 11, 3, 4, 5, 123]), + "3-4-5-11-123", + ); + }); +}; + +const test_unNodeID = t => { + t.start("unNodeID()"); + + t.testing("no hyphes", () => { + t.assertEq(unNodeID("123"), [123]); + }); + + t.testing("with hyphens", () => { + t.assertEq(unNodeID("1-2"), [1, 2]); + t.assertEq(unNodeID("11-3-0"), [11, 3, 0]); + }); +}; + +const test_collectTransitions = t => { + t.start("collectTransitions()"); + + t.testing("FIXME", () => {}); +}; + +const test_computePending = t => { + t.start("computePending()"); + + t.testing("FIXME", () => {}); +}; + +const test_buildDFANodes = t => { + t.start("buildDFANodes()"); + + t.testing("FIXME", () => {}); +}; + +const test_buildDFA = t => { + t.start("buildDFA()"); + + t.testing("FIXME", () => {}); +}; + +const test_searchDFAStep = t => { + t.start("searchDFAStep()"); + + t.testing("FIXME", () => {}); +}; + +const test_searchDFAFn = t => { + t.start("searchDFAFn()"); + + t.testing("FIXME", () => {}); +}; + +const test_searchDFA = t => { + t.start("searchDFA()"); + + t.testing("FIXME", () => {}); +}; + +const test_compileNFA = t => { + t.start("compileNFA()"); + + t.testing("empty regex", () => { + const expected = { + start: 1, + end: 2, + nextID: 3, + nodes: { + 1: { + direct: [ 2 ], + transitions: {}, + }, + 2: { + direct: [], + transitions: {}, + }, + }, + }; + t.assertEq(compileNFA(""), expected); + }); + + t.testing("composed sample regex", () => { + const nfa = compileNFA("(a|b)*c"); + t.assertEq(searchNFA(nfa, "ababac"), true); + t.assertEq(searchNFA(nfa, "babac"), true); + t.assertEq(searchNFA(nfa, "babaca"), false); + }); +}; + +const test_compileDFA = t => { + t.start("compileDFA()"); + + t.testing("FIXME", () => {}); +}; + +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); + }); +}; + + + +runTests([ + test_shouldConcat, + test_isOperator, + test_tokenizeRegexStep, + test_tokenizeRegexFn, + test_tokenizeRegex, + test_shouldPush, + test_toPostfixStep, + test_toPostfix, + test_emptyNFA, + test_baseNFA, + test_concat, + test_union, + test_zeroOrMore, + test_oneOrMore, + test_zeroOrOne, + test_OPERATORS_FNS, + test_buildNFAStep, + test_buildNFA, + test_allDirects, + test_searchNFAStep, + test_searchNFAFn, + test_searchNFA, + test_nodeID, + test_unNodeID, + test_collectTransitions, + test_computePending, + test_buildDFANodes, + test_buildDFA, + test_searchDFAStep, + test_searchDFAFn, + test_searchDFA, + test_compileNFA, + test_compileDFA, + test_compile, +]); -- cgit v1.2.3