packages/sql-faker/tests/Unit/Generation/Derivation/TerminationAnalyzerTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\SqlFaker\Generation\Derivation;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\UsesClass;
9use PHPUnit\Framework\TestCase;
10use SqlFaker\Generation\Derivation\TerminationAnalyzer;
11use SqlFaker\Generation\Derivation\TerminationCost;
12use SqlFaker\Grammar\Model\Grammar;
13use SqlFaker\Grammar\Model\NonTerminal;
14use SqlFaker\Grammar\Model\Production;
15use SqlFaker\Grammar\Model\ProductionRule;
16use SqlFaker\Grammar\Model\Terminal;
17
18#[CoversClass(TerminationAnalyzer::class)]
19#[UsesClass(TerminationCost::class)]
20#[CoversClass(Grammar::class)]
21#[CoversClass(NonTerminal::class)]
22#[CoversClass(Production::class)]
23#[CoversClass(ProductionRule::class)]
24#[CoversClass(Terminal::class)]
25final class TerminationAnalyzerTest extends TestCase
26{
27 public function testGetMinLengthTerminalOnly(): void
28 {
29 $grammar = new Grammar(
30 'start',
31 [
32 'start' => new ProductionRule('start', [
33 new Production([new Terminal('TOKEN')]),
34 ]),
35 ]
36 );
37
38 $analyzer = new TerminationAnalyzer($grammar);
39
40 self::assertSame(1, $analyzer->getMinLength('start'));
41 }
42
43 public function testGetMinLengthEmptyProduction(): void
44 {
45 $grammar = new Grammar(
46 'opt',
47 [
48 'opt' => new ProductionRule('opt', [
49 new Production([]),
50 ]),
51 ]
52 );
53
54 $analyzer = new TerminationAnalyzer($grammar);
55
56 self::assertSame(0, $analyzer->getMinLength('opt'));
57 }
58
59 public function testGetMinLengthChoosesShortestAlternative(): void
60 {
61 $grammar = new Grammar(
62 'expr',
63 [
64 'expr' => new ProductionRule('expr', [
65 new Production([new Terminal('A'), new Terminal('B'), new Terminal('C')]),
66 new Production([new Terminal('X')]),
67 ]),
68 ]
69 );
70
71 $analyzer = new TerminationAnalyzer($grammar);
72
73 self::assertSame(1, $analyzer->getMinLength('expr'));
74 }
75
76 public function testGetMinLengthNestedRules(): void
77 {
78 $grammar = new Grammar(
79 'a',
80 [
81 'a' => new ProductionRule('a', [
82 new Production([new NonTerminal('b')]),
83 ]),
84 'b' => new ProductionRule('b', [
85 new Production([new NonTerminal('c')]),
86 ]),
87 'c' => new ProductionRule('c', [
88 new Production([new Terminal('TOKEN')]),
89 ]),
90 ]
91 );
92
93 $analyzer = new TerminationAnalyzer($grammar);
94
95 self::assertSame(1, $analyzer->getMinLength('a'));
96 self::assertSame(1, $analyzer->getMinLength('b'));
97 self::assertSame(1, $analyzer->getMinLength('c'));
98 }
99
100 public function testEstimateProductionLengthTerminals(): void
101 {
102 $grammar = new Grammar('start', []);
103 $analyzer = new TerminationAnalyzer($grammar);
104
105 $production = new Production([new Terminal('A'), new Terminal('B')]);
106
107 self::assertSame(2, $analyzer->estimateProductionLength($production));
108 }
109
110 public function testEstimateProductionLengthNonTerminals(): void
111 {
112 $grammar = new Grammar(
113 'start',
114 [
115 'start' => new ProductionRule('start', [
116 new Production([]),
117 ]),
118 'inner' => new ProductionRule('inner', [
119 new Production([new Terminal('A'), new Terminal('B'), new Terminal('C')]),
120 ]),
121 ]
122 );
123
124 $analyzer = new TerminationAnalyzer($grammar);
125
126 $production = new Production([new NonTerminal('inner')]);
127
128 self::assertSame(3, $analyzer->estimateProductionLength($production));
129 }
130
131 public function testEstimateProductionLengthEmpty(): void
132 {
133 $grammar = new Grammar('start', []);
134 $analyzer = new TerminationAnalyzer($grammar);
135
136 $production = new Production([]);
137
138 self::assertSame(0, $analyzer->estimateProductionLength($production));
139 }
140
141 public function testEstimateProductionStepsBreaksARecursiveLengthTie(): void
142 {
143 $recursive = new Production([new NonTerminal('value')]);
144 $terminal = new Production([new Terminal('VALUE')]);
145 $grammar = new Grammar('value', [
146 'value' => new ProductionRule('value', [$recursive, $terminal]),
147 ]);
148 $analyzer = new TerminationAnalyzer($grammar);
149
150 self::assertSame(1, $analyzer->estimateProductionLength($recursive));
151 self::assertSame(1, $analyzer->estimateProductionLength($terminal));
152 self::assertSame(1, $analyzer->estimateProductionSteps($recursive));
153 self::assertSame(0, $analyzer->estimateProductionSteps($terminal));
154 }
155
156 public function testTreatsUnknownSupportedNonTerminalAsOneToken(): void
157 {
158 $analyzer = new TerminationAnalyzer(new Grammar('start', []));
159 $production = new Production([new NonTerminal('lexer_token')]);
160
161 self::assertSame(1, $analyzer->getMinLength('lexer_token'));
162 self::assertSame(1, $analyzer->estimateProductionLength($production));
163 self::assertSame(1, $analyzer->estimateProductionSteps($production));
164 }
165
166 public function testEstimateProductionStepsRejectsUnsupportedTerminal(): void
167 {
168 $analyzer = new TerminationAnalyzer(
169 new Grammar('start', []),
170 static fn (string $terminal): bool => $terminal !== 'UNSUPPORTED',
171 );
172
173 self::assertSame(
174 PHP_INT_MAX,
175 $analyzer->estimateProductionSteps(new Production([new Terminal('UNSUPPORTED')])),
176 );
177 }
178
179 public function testEstimateProductionLengthMixed(): void
180 {
181 $grammar = new Grammar(
182 'start',
183 [
184 'start' => new ProductionRule('start', [
185 new Production([]),
186 ]),
187 'expr' => new ProductionRule('expr', [
188 new Production([new Terminal('NUM')]),
189 ]),
190 ]
191 );
192
193 $analyzer = new TerminationAnalyzer($grammar);
194
195 $production = new Production([
196 new Terminal('('),
197 new NonTerminal('expr'),
198 new Terminal(')'),
199 ]);
200
201 self::assertSame(3, $analyzer->estimateProductionLength($production));
202 }
203
204 public function testComputesAViewThatExcludesUnsupportedTerminals(): void
205 {
206 $unsupported = new Production([new Terminal('UNSUPPORTED')]);
207 $supported = new Production([new Terminal('SUPPORTED')]);
208 $grammar = new Grammar('start', [
209 'start' => new ProductionRule('start', [$unsupported, $supported]),
210 ]);
211 $analyzer = new TerminationAnalyzer($grammar, static fn (string $terminal): bool => $terminal !== 'UNSUPPORTED');
212
213 self::assertFalse($analyzer->isProductionViable($unsupported));
214 self::assertTrue($analyzer->isProductionViable($supported));
215 self::assertSame(1, $analyzer->getMinLength('start'));
216 }
217
218 public function testPropagatesLexicalImpossibilityThroughNonTerminals(): void
219 {
220 $grammar = new Grammar('start', [
221 'start' => new ProductionRule('start', [new Production([new NonTerminal('nested')])]),
222 'nested' => new ProductionRule('nested', [new Production([new Terminal('UNSUPPORTED')])]),
223 ]);
224 $analyzer = new TerminationAnalyzer($grammar, static fn (string $terminal): bool => $terminal !== 'UNSUPPORTED');
225
226 self::assertSame(PHP_INT_MAX, $analyzer->getMinLength('start'));
227 }
228
229 public function testIsProductionViableAcceptsAProductionSomeDerivationFinishes(): void
230 {
231 $grammar = new Grammar('nm', ['nm' => new ProductionRule('nm', [new Production([new Terminal('IDENT')])])]);
232 $analyzer = new TerminationAnalyzer($grammar);
233
234 self::assertTrue($analyzer->isProductionViable(new Production([new NonTerminal('nm')])));
235 }
236
237 public function testIsProductionViableRejectsAProductionThatCanNeverBeFinished(): void
238 {
239 $grammar = new Grammar('loop', ['loop' => new ProductionRule('loop', [new Production([new NonTerminal('loop')])])]);
240 $analyzer = new TerminationAnalyzer($grammar);
241
242 self::assertFalse($analyzer->isProductionViable(new Production([new NonTerminal('loop')])));
243 }
244}
245