packages/sql-parser/tests/Unit/Automaton/ParseTableBuilderTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\Automaton;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\Small;
9use PHPUnit\Framework\Attributes\UsesClass;
10use PHPUnit\Framework\TestCase;
11use SqlParser\Automaton\Bitset;
12use SqlParser\Automaton\BuildResult;
13use SqlParser\Automaton\ClosureIndex;
14use SqlParser\Automaton\ConflictResolver;
15use SqlParser\Automaton\ConflictSummary;
16use SqlParser\Automaton\Digraph;
17use SqlParser\Automaton\LookaheadSets;
18use SqlParser\Automaton\Lr0Automaton;
19use SqlParser\Automaton\Lr0Builder;
20use SqlParser\Automaton\NullableSet;
21use SqlParser\Automaton\ParseTableBuilder;
22use SqlParser\Automaton\ResolvedState;
23use SqlParser\Grammar\Associativity;
24use SqlParser\Grammar\Grammar;
25use SqlParser\Grammar\GrammarBuilder;
26use SqlParser\Grammar\Precedence;
27use SqlParser\Grammar\PrecedencePolicy;
28use SqlParser\Grammar\Rule;
29use SqlParser\Grammar\SymbolTable;
30use SqlParser\Table\ActionCode;
31use SqlParser\Table\ArrayRows;
32use SqlParser\Table\ParseTable;
33use SqlParser\Table\TableRule;
34
35#[CoversClass(ParseTableBuilder::class)]
36#[UsesClass(ActionCode::class)]
37#[UsesClass(ArrayRows::class)]
38#[UsesClass(Bitset::class)]
39#[UsesClass(BuildResult::class)]
40#[UsesClass(ClosureIndex::class)]
41#[UsesClass(ConflictResolver::class)]
42#[UsesClass(ConflictSummary::class)]
43#[UsesClass(Digraph::class)]
44#[UsesClass(LookaheadSets::class)]
45#[UsesClass(Lr0Automaton::class)]
46#[UsesClass(Lr0Builder::class)]
47#[UsesClass(NullableSet::class)]
48#[UsesClass(ParseTable::class)]
49#[UsesClass(ResolvedState::class)]
50#[UsesClass(TableRule::class)]
51#[UsesClass(Grammar::class)]
52#[UsesClass(GrammarBuilder::class)]
53#[UsesClass(Precedence::class)]
54#[UsesClass(Rule::class)]
55#[UsesClass(SymbolTable::class)]
56#[Small]
57final class ParseTableBuilderTest extends TestCase
58{
59 public function testBuildSettlesAnAmbiguousGrammarWithPrecedence(): void
60 {
61 $builder = new GrammarBuilder();
62 $builder->precedence(['+'], Associativity::Left);
63 $builder->precedence(['*'], Associativity::Left);
64 $builder->terminal('NUM');
65 $builder->rule('expr', ['expr', '+', 'expr']);
66 $builder->rule('expr', ['expr', '*', 'expr']);
67 $builder->rule('expr', ['NUM']);
68 $result = (new ParseTableBuilder())->build($builder->build());
69 $table = $result->table;
70 $symbols = $table->symbols;
71 $afterPlusExpr = $table->action($table->action($table->action(0, $symbols->id('expr') ?? -1), $symbols->id('+') ?? -1), $symbols->id('expr') ?? -1);
72
73 self::assertTrue($result->conflicts->isExpected());
74 self::assertSame(0, $result->conflicts->shiftReduce);
75 self::assertSame(ActionCode::reduce(1), $table->action($afterPlusExpr, $symbols->id('+') ?? -1));
76 self::assertTrue(ActionCode::isShift($table->action($afterPlusExpr, $symbols->id('*') ?? -1)));
77 self::assertSame(ActionCode::ACCEPT, $table->action($table->action($table->action(0, $symbols->id('expr') ?? -1), 0), 0));
78 }
79
80 public function testBuildCountsConflictsItSettlesByDefault(): void
81 {
82 $builder = new GrammarBuilder();
83 $builder->terminal('+');
84 $builder->terminal('NUM');
85 $builder->rule('expr', ['expr', '+', 'expr']);
86 $builder->rule('expr', ['NUM']);
87 $result = (new ParseTableBuilder())->build($builder->build());
88
89 self::assertSame(1, $result->conflicts->shiftReduce);
90 self::assertFalse($result->conflicts->isExpected());
91 self::assertGreaterThan(0, $result->stateCount);
92 }
93
94 public function testBuildMakesANonAssociativeOperatorAnError(): void
95 {
96 $builder = new GrammarBuilder();
97 $builder->precedence(['='], Associativity::NonAssoc);
98 $builder->terminal('NUM');
99 $builder->rule('expr', ['expr', '=', 'expr']);
100 $builder->rule('expr', ['NUM']);
101 $table = (new ParseTableBuilder())->build($builder->build())->table;
102 $symbols = $table->symbols;
103 $afterEqualsExpr = $table->action($table->action($table->action(0, $symbols->id('expr') ?? -1), $symbols->id('=') ?? -1), $symbols->id('expr') ?? -1);
104
105 self::assertSame(ActionCode::ERROR, $table->action($afterEqualsExpr, $symbols->id('=') ?? -1));
106 self::assertSame(ActionCode::reduce(1), $table->action($afterEqualsExpr, 0));
107 }
108
109 public function testBuildKeepsReductionsExplicitWhereTheWildcardActs(): void
110 {
111 $builder = new GrammarBuilder();
112 $builder->policy(PrecedencePolicy::FirstRankedTerminal);
113 $builder->wildcard('ANY');
114 $builder->terminal('LP');
115 $builder->terminal('RP');
116 $builder->rule('list', ['LP', 'any', 'RP']);
117 $builder->rule('any', []);
118 $builder->rule('any', ['any', 'ANY']);
119 $table = (new ParseTableBuilder())->build($builder->build())->table;
120 $symbols = $table->symbols;
121 $inside = $table->action($table->action(0, $symbols->id('LP') ?? -1), $symbols->id('any') ?? -1);
122
123 self::assertSame(ActionCode::ERROR, $table->defaults[$inside]);
124 self::assertTrue(ActionCode::isShift($table->action($inside, $symbols->id('RP') ?? -1)));
125 self::assertTrue(ActionCode::isShift($table->action($inside, $symbols->id('ANY') ?? -1)));
126 }
127
128 public function testBuildSpellsTokenClassesOutToTheirMembers(): void
129 {
130 $builder = new GrammarBuilder();
131 $builder->policy(PrecedencePolicy::FirstRankedTerminal);
132 $builder->tokenClass('id', ['ID', 'INDEXED']);
133 $builder->rule('nm', ['id']);
134 $table = (new ParseTableBuilder())->build($builder->build())->table;
135 $symbols = $table->symbols;
136
137 self::assertTrue(ActionCode::isShift($table->action(0, $symbols->id('INDEXED') ?? -1)));
138 self::assertSame($table->action(0, $symbols->id('ID') ?? -1), $table->action(0, $symbols->id('INDEXED') ?? -1));
139 self::assertSame(ActionCode::ERROR, $table->action(0, $symbols->id('id') ?? -1));
140 }
141
142 public function testDefaultRule(): void
143 {
144 $builder = new ParseTableBuilder();
145
146 self::assertSame(0, $builder->defaultRule(new ResolvedState([], [], 0, 0), false, true));
147 self::assertNull($builder->defaultRule(new ResolvedState([], [], 0, 0), true, false));
148 self::assertSame(4, $builder->defaultRule(new ResolvedState([], [4 => 0], 0, 0), true, false));
149 self::assertSame(2, $builder->defaultRule(new ResolvedState([], [1 => 1, 2 => 3, 3 => 3], 0, 0), false, false));
150 self::assertNull($builder->defaultRule(new ResolvedState([], [1 => 0], 0, 0), false, false));
151 }
152
153 public function testWithoutDefault(): void
154 {
155 $builder = new ParseTableBuilder();
156 $actions = [1 => ActionCode::reduce(3), 2 => ActionCode::shift(4), 3 => ActionCode::ERROR];
157
158 self::assertSame([2 => ActionCode::shift(4), 3 => ActionCode::ERROR], $builder->withoutDefault($actions, 3));
159 self::assertSame($actions, $builder->withoutDefault($actions, null));
160 }
161
162 public function testExpandShifts(): void
163 {
164 $symbols = new SymbolTable(['$end', 'ID', 'INDEXED', 'id'], ['$accept', 'nm']);
165 $grammar = new Grammar($symbols, [new Rule(0, 4, [5, 0], 0)], [], PrecedencePolicy::FirstRankedTerminal, null, [3 => [1, 2]]);
166
167 self::assertSame([1 => 7, 2 => 9], (new ParseTableBuilder())->expandShifts([1 => 7, 3 => 9], $grammar));
168 }
169
170 public function testExpandLookaheads(): void
171 {
172 $symbols = new SymbolTable(['$end', 'ID', 'INDEXED', 'id'], ['$accept', 'nm']);
173 $grammar = new Grammar($symbols, [new Rule(0, 4, [5, 0], 0)], [], PrecedencePolicy::FirstRankedTerminal, null, [3 => [1, 2]]);
174 $set = Bitset::empty(4);
175 Bitset::add($set, 3);
176 $expanded = (new ParseTableBuilder())->expandLookaheads([1 => $set], $grammar);
177
178 self::assertSame([1, 2, 3], Bitset::members($expanded[1]));
179 self::assertSame([1 => $set], (new ParseTableBuilder())->expandLookaheads([1 => $set], new Grammar($symbols, [new Rule(0, 4, [5, 0], 0)])));
180 }
181}
182