From 9434d30805576a7dbf4e2c8a5fb7da72089e6260 Mon Sep 17 00:00:00 2001 From: EuAndreh Date: Thu, 17 Jul 2025 07:31:12 -0300 Subject: Do away with the "nextID" attribute Instead of being an increment over "end" that is carried along on NFA transformation, now the id is computed directly as an increment on "end". During this refactor, I even saw that "end" and "nextID" of `concat()` are computed differently, despite arriving at the same result: "end" is rhs.end, while "nextID" is the max of the nextID from lhs and rhs. --- src/paca.mjs | 27 ++++++--------------------- tests/paca.mjs | 36 ++++-------------------------------- 2 files changed, 10 insertions(+), 53 deletions(-) diff --git a/src/paca.mjs b/src/paca.mjs index 216dc2e..12eb4b9 100644 --- a/src/paca.mjs +++ b/src/paca.mjs @@ -480,11 +480,9 @@ const toPostfix = tokens => { const emptyNFA = () => { const startID = 1; const endID = 2; - const nextID = 3; return { start: startID, end: endID, - nextID, nodes: { [startID]: { direct: [ endID ], @@ -501,11 +499,9 @@ const emptyNFA = () => { const literal = (edge, id) => { const startID = id + 0; const endID = id + 1; - const nextID = id + 2; return { start: startID, end: endID, - nextID, nodes: { [startID]: { direct: [], @@ -524,7 +520,6 @@ const literal = (edge, id) => { const concat = (lhs, rhs) => ({ start: lhs.start, end: rhs.end, - nextID: max(lhs.nextID, rhs.nextID), nodes: { ...lhs.nodes, ...rhs.nodes, @@ -536,13 +531,11 @@ const concat = (lhs, rhs) => ({ }); const union = (lhs, rhs) => { - const startID = max(lhs.nextID, rhs.nextID); + const startID = max(lhs.end, rhs.end) + 1; const endID = startID + 1; - const nextID = startID + 2; return { start: startID, end: endID, - nextID, nodes: { ...lhs.nodes, ...rhs.nodes, @@ -567,13 +560,11 @@ const union = (lhs, rhs) => { }; const zeroOrMore = nfa => { - const startID = nfa.nextID; - const endID = startID + 1; - const nextID = startID + 2; + const startID = nfa.end + 1; + const endID = nfa.end + 2; return { start: startID, end: endID, - nextID, nodes: { ...nfa.nodes, [nfa.end]: { @@ -598,13 +589,11 @@ const oneOrMore = nfa => concat(nfa, zeroOrMore(nfa)); const zeroOrOne = nfa => { - const startID = nfa.nextID; - const endID = startID + 1; - const nextID = startID + 2; + const startID = nfa.end + 1; + const endID = nfa.end + 2; return { start: startID, end: endID, - nextID, nodes: { ...nfa.nodes, [nfa.end]: { @@ -650,7 +639,6 @@ const inRange = (ranges, char) => { const characterClass = ({ set, caret }, id) => { const start = id + 0; const end = id + 1; - const nextID = id + 2; const { string, object } = Object.groupBy(set, x => typeof x); const ranges = Object.fromEntries( compressCharacterRanges((object || []).map( @@ -665,7 +653,6 @@ const characterClass = ({ set, caret }, id) => { return { start, end, - nextID, nodes: { [start]: { direct: [], @@ -688,11 +675,9 @@ const characterClass = ({ set, caret }, id) => { const wildcard = (_edge, id) => { const start = id + 0; const end = id + 1; - const nextID = id + 2; return { start, end, - nextID, nodes: { [start]: { direct: [], @@ -744,7 +729,7 @@ const baseNFA = (token, id) => ( const buildNFAStep = (stack, token) => !token.operator - ? stack.concat(baseNFA(token, last(stack)?.nextID || 1)) + ? stack.concat(baseNFA(token, (last(stack)?.end || 0) + 1)) : OPERATORS[token.operator](stack); const buildNFA = tokens => diff --git a/tests/paca.mjs b/tests/paca.mjs index 82640b1..36ab2a7 100644 --- a/tests/paca.mjs +++ b/tests/paca.mjs @@ -1765,7 +1765,6 @@ const test_emptyNFA = t => { const expected = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [ 2 ], @@ -1788,7 +1787,6 @@ const test_literal = t => { const expected = { start: 123, end: 124, - nextID: 125, nodes: { 123: { direct: [], @@ -1809,12 +1807,11 @@ const test_concat = t => { t.testing("on literal() and on more complex NFAs", () => { const a = literal("a", 1); - const b = literal("b", a.nextID); - const a_ = literal("a", b.nextID); + const b = literal("b", a.end + 1); + const a_ = literal("a", b.end + 1); const expected1 = { start: 1, end: 4, - nextID: 5, nodes: { 1: { direct: [], @@ -1839,7 +1836,6 @@ const test_concat = t => { const expected2 = { start: 1, end: 6, - nextID: 7, nodes: { 1: { direct: [], @@ -1876,11 +1872,10 @@ const test_union = t => { t.testing("on literal() and on more complex NFAs", () => { const a = literal("a", 1); - const b = literal("b", a.nextID); + const b = literal("b", a.end + 1); const expected1 = { start: 5, end: 6, - nextID: 7, nodes: { 1: { direct: [], @@ -1910,11 +1905,10 @@ const test_union = t => { }; t.assertEq(union(a, b), expected1); - const c = literal("c", expected1.nextID); + const c = literal("c", expected1.end + 1); const expected2 = { start: 9, end: 10, - nextID: 11, nodes: { 1: { direct: [], @@ -1970,7 +1964,6 @@ const test_zeroOrMore = t => { const expected = { start: 3, end: 4, - nextID: 5, nodes: { 1: { direct: [], @@ -2002,7 +1995,6 @@ const test_oneOrMore = t => { const expected = { start: 1, end: 4, - nextID: 5, nodes: { 1: { direct: [], @@ -2034,7 +2026,6 @@ const test_zeroOrOne = t => { const expected = { start: 3, end: 4, - nextID: 5, nodes: { 1: { direct: [], @@ -2161,7 +2152,6 @@ const test_characterClass = t => { const expected = { start: 3, end: 4, - nextID: 5, nodes: { 3: { direct: [], @@ -2198,7 +2188,6 @@ const test_characterClass = t => { const expected = { start: 7, end: 8, - nextID: 9, nodes: { 7: { direct: [], @@ -2233,7 +2222,6 @@ const test_characterClass = t => { const expected = { start: 3, end: 4, - nextID: 5, nodes: { 3: { direct: [], @@ -2274,7 +2262,6 @@ const test_wildcard = t => { const expected = { start: 5, end: 6, - nextID: 7, nodes: { 5: { direct: [], @@ -2361,7 +2348,6 @@ const test_baseNFA = t => { const expected1 = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [], @@ -2376,7 +2362,6 @@ const test_baseNFA = t => { const expected2 = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [], @@ -2404,7 +2389,6 @@ const test_buildNFAStep = t => { const expected = [{ start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [], @@ -2425,7 +2409,6 @@ const test_buildNFAStep = t => { const expected = [{ start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [], @@ -2439,7 +2422,6 @@ const test_buildNFAStep = t => { }, { start: 3, end: 4, - nextID: 5, nodes: { 3: { direct: [], @@ -2463,7 +2445,6 @@ const test_buildNFAStep = t => { const expected = [{ start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [], @@ -2477,7 +2458,6 @@ const test_buildNFAStep = t => { }, { start: 3, end: 4, - nextID: 5, nodes: { 3: { direct: [], @@ -2504,7 +2484,6 @@ const test_buildNFAStep = t => { const expected = [{ start: 1, end: 4, - nextID: 5, nodes: { 1: { direct: [], @@ -2538,7 +2517,6 @@ const test_buildNFA = t => { const expected = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [ 2 ], @@ -2558,7 +2536,6 @@ const test_buildNFA = t => { const expected = { start: 7, end: 14, - nextID: 15, nodes: { 1: { direct: [], @@ -3092,7 +3069,6 @@ const test_buildDFA = t => { const nfa = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [ 2 ], @@ -3120,7 +3096,6 @@ const test_buildDFA = t => { const nfa = { start: 7, end: 10, - nextID: 11, nodes: { 1: { direct: [], @@ -3275,7 +3250,6 @@ const test_compileNFA = t => { const expected = { start: 1, end: 2, - nextID: 3, nodes: { 1: { direct: [ 2 ], @@ -3295,7 +3269,6 @@ const test_compileNFA = t => { const expected1 = { start: 7, end: 10, - nextID: 11, nodes: { 1: { direct: [], @@ -3343,7 +3316,6 @@ const test_compileNFA = t => { const expected2 = { start: 15, end: 18, - nextID: 19, nodes: { 1: { direct: [], -- cgit v1.2.3