packages/sql-faker/tests/Unit/Generation/Derivation/DerivationTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\Generation\Derivation;
6
7use Faker\Factory;
8use Override;
9use PHPUnit\Framework\Attributes\CoversClass;
10use PHPUnit\Framework\Attributes\UsesClass;
11use PHPUnit\Framework\TestCase;
12use SqlFaker\Generation\Derivation\Derivation;
13use SqlFaker\Generation\Derivation\TerminationAnalyzer;
14use SqlFaker\Generation\Derivation\TerminationCost;
15use SqlFaker\Generation\Exception\GenerationException;
16use SqlFaker\Generation\Plan\GenerationPlan;
17use SqlFaker\Generation\Plan\ProductionPattern;
18use SqlFaker\Grammar\Model\Grammar;
19use SqlFaker\Grammar\Model\NonTerminal;
20use SqlFaker\Grammar\Model\Production;
21use SqlFaker\Grammar\Model\ProductionRule;
22use SqlFaker\Grammar\Model\Terminal;
23
24#[CoversClass(Derivation::class)]
25#[UsesClass(GenerationException::class)]
26#[UsesClass(GenerationPlan::class)]
27#[UsesClass(Grammar::class)]
28#[UsesClass(NonTerminal::class)]
29#[UsesClass(Production::class)]
30#[UsesClass(ProductionPattern::class)]
31#[UsesClass(ProductionRule::class)]
32#[UsesClass(Terminal::class)]
33#[UsesClass(TerminationAnalyzer::class)]
34#[UsesClass(TerminationCost::class)]
35#[UsesClass(\SqlFaker\Generation\Derivation\CompletionCosts::class)]
36#[UsesClass(\SqlFaker\Generation\Derivation\DerivationTrace::class)]
37#[UsesClass(\SqlFaker\Generation\Token\ProductionOccurrence::class)]
38#[UsesClass(\SqlFaker\Generation\Token\TerminalOccurrence::class)]
39#[UsesClass(\SqlFaker\Generation\Token\TerminalSequence::class)]
40#[UsesClass(\SqlFaker\Generation\Derivation\CompletionState::class)]
41#[UsesClass(\SqlFaker\Generation\Derivation\CompletionFrontier::class)]
42#[UsesClass(\SqlFaker\Generation\Derivation\ConstrainedCompletion::class)]
43#[UsesClass(\SqlFaker\Generation\Derivation\CompletionMemo::class)]
44#[UsesClass(\SqlFaker\Generation\Derivation\CompletionReduction::class)]
45#[UsesClass(\SqlFaker\Generation\Derivation\ConstraintDependencies::class)]
46#[UsesClass(\SqlFaker\Generation\Choice\BytePlanCompiler::class)]
47#[UsesClass(\SqlFaker\Generation\Derivation\Completion\PatternProductions::class)]
48#[UsesClass(\SqlFaker\Generation\Derivation\Completion\CompletionWitness::class)]
49final class DerivationTest extends TestCase
50{
51 public function testOfRewritesTheStartSymbolUntilOnlyTerminalsAreLeft(): void
52 {
53 $grammar = new Grammar('stmt', [
54 'stmt' => new ProductionRule('stmt', [new Production([new Terminal('SELECT'), new NonTerminal('nm')])]),
55 'nm' => new ProductionRule('nm', [new Production([new Terminal('IDENT')])]),
56 ]);
57 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
58 $grammar,
59 static fn (string $terminal): bool => true,
60 ));
61
62 self::assertEquals(
63 [new Terminal('SELECT'), new Terminal('IDENT')],
64 $derivation->of('stmt', GenerationPlan::all()),
65 );
66 }
67
68 public function testOfOffersTheCandidatesToTheChoicePolicy(): void
69 {
70 $grammar = new Grammar('stmt', [
71 'stmt' => new ProductionRule('stmt', [new Production([new Terminal('SELECT')]), new Production([new Terminal('DELETE')])]),
72 ]);
73 $offered = [];
74 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar), null, static function (int $count, array $candidates) use (&$offered): int {
75 $offered = $candidates;
76 return $count - 1;
77 });
78
79 self::assertEquals([new Terminal('DELETE')], $derivation->of('stmt', GenerationPlan::all()));
80 self::assertSame($grammar->ruleMap['stmt']->alternatives, $offered);
81 }
82
83 public function testOfReportsASymbolTheGrammarDeclaresNoRuleFor(): void
84 {
85 $grammar = new Grammar('stmt', [
86 'stmt' => new ProductionRule('stmt', [new Production([new NonTerminal('missing')])]),
87 ]);
88 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
89 $grammar,
90 static fn (string $terminal): bool => true,
91 ));
92
93 $this->expectException(GenerationException::class);
94
95 $derivation->of('stmt', GenerationPlan::all());
96 }
97
98 public function testOfReportsAPlanNoAlternativeCanSatisfy(): void
99 {
100 $grammar = new Grammar('stmt', [
101 'stmt' => new ProductionRule('stmt', [new Production([new Terminal('SELECT')])]),
102 ]);
103 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
104 $grammar,
105 static fn (string $terminal): bool => true,
106 ));
107
108 $this->expectException(GenerationException::class);
109
110 $derivation->of('stmt', GenerationPlan::constrained('stmt', [
111 'stmt' => [ProductionPattern::containing('DELETE')],
112 ]));
113 }
114
115 public function testFirstNonTerminalAnswersTheLeftmostPositionTheWalkActsOn(): void
116 {
117 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([])])]);
118 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
119 $grammar,
120 static fn (string $terminal): bool => true,
121 ));
122
123 self::assertSame(1, $derivation->firstNonTerminal([new Terminal('SELECT'), new NonTerminal('nm')]));
124 }
125
126 public function testFirstNonTerminalAnswersNothingWhenOnlyTerminalsAreLeft(): void
127 {
128 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([])])]);
129 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
130 $grammar,
131 static fn (string $terminal): bool => true,
132 ));
133
134 self::assertNull($derivation->firstNonTerminal([new Terminal('SELECT')]));
135 }
136
137 public function testSelectProductionTakesTheShortestAlternativeOncePastThePlanDepth(): void
138 {
139 $short = new Production([new Terminal('A')]);
140 $long = new Production([new Terminal('A'), new Terminal('B'), new Terminal('C')]);
141 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [$long, $short])]);
142 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
143 $grammar,
144 static fn (string $terminal): bool => true,
145 ));
146
147 self::assertEquals(
148 [new Terminal('A')],
149 $derivation->of('stmt', GenerationPlan::all()->withMaxDepth(1)),
150 );
151 }
152
153 public function testSelectProductionDrawsUniformlyAmongTheEligibleAlternativesBeforeTheThreshold(): void
154 {
155 $alternatives = [
156 new Production([new Terminal('A')]),
157 new Production([new Terminal('B'), new Terminal('C')]),
158 new Production([new Terminal('D'), new Terminal('E'), new Terminal('F')]),
159 ];
160 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', $alternatives)]);
161 $faker = new class () extends \Faker\Generator {
162 /** @var list<array{int, int}> */
163 public array $draws = [];
164
165 /**
166 * @param mixed $int1
167 * @param mixed $int2
168 */
169 #[Override]
170 public function numberBetween($int1 = 0, $int2 = 2147483647): int
171 {
172 $minimum = is_int($int1) ? $int1 : -1;
173 $maximum = is_int($int2) ? $int2 : -1;
174 $this->draws[] = [$minimum, $maximum];
175
176 return $maximum;
177 }
178 };
179 $derivation = new Derivation($grammar, $faker, new TerminationAnalyzer($grammar));
180
181 self::assertSame($alternatives[2], $derivation->selectProduction($alternatives, GenerationPlan::all()->withMaxDepth(2)));
182 self::assertSame([[0, 2]], $faker->draws);
183 }
184
185 public function testSelectProductionChoosesFreelyWhileThePlanStillAllowsDepth(): void
186 {
187 $grammar = new Grammar('stmt', [
188 'stmt' => new ProductionRule('stmt', [new Production([new Terminal('A')])]),
189 ]);
190 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
191 $grammar,
192 static fn (string $terminal): bool => true,
193 ));
194
195 self::assertEquals([new Terminal('A')], $derivation->of('stmt', GenerationPlan::all()));
196 }
197 public function testAffordableKeepsAnAlternativeThatStillLeavesRoomToFinish(): void
198 {
199 $short = new Production([new Terminal('A')]);
200 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [$short])]);
201 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
202 $grammar,
203 static fn (string $terminal): bool => true,
204 ));
205
206 self::assertSame([$short], $derivation->affordable([$short], new Production([])));
207 }
208
209 public function testAffordableRejectsARemainderThatExceedsTheWholeBudget(): void
210 {
211 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([new Terminal('T')])])]);
212 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
213 $this->expectException(GenerationException::class);
214
215 $derivation->affordable([new Production([])], new Production(array_fill(0, 5001, new NonTerminal('stmt'))));
216 }
217
218 public function testAffordableRejectsAnAlternativeThatCannotFitAfterTheRemainder(): void
219 {
220 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([new Terminal('T')])])]);
221 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
222 $this->expectException(GenerationException::class);
223
224 $derivation->affordable(
225 [new Production(array_fill(0, 5000, new NonTerminal('stmt')))],
226 new Production([new NonTerminal('stmt')]),
227 );
228 }
229
230 public function testAffordableAcceptsAnAlternativeThatExactlyUsesTheBudget(): void
231 {
232 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([new Terminal('T')])])]);
233 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
234 $production = new Production(array_fill(0, 4999, new NonTerminal('stmt')));
235
236 self::assertSame([$production], $derivation->affordable([$production], new Production([new NonTerminal('stmt')])));
237 }
238
239 public function testOfSelectsTerminationPolicyFromThePlan(): void
240 {
241 $grammar = new Grammar('stmt', [
242 'stmt' => new ProductionRule('stmt', [
243 new Production([new NonTerminal('short')]),
244 new Production([new Terminal('A'), new Terminal('B')]),
245 ]),
246 'short' => new ProductionRule('short', [new Production([new Terminal('T')])]),
247 ]);
248 $faker = Factory::create();
249 $analyzer = new TerminationAnalyzer($grammar);
250 $plan = GenerationPlan::all()->withMaxDepth(1);
251
252 self::assertEquals([new Terminal('T')], (new Derivation($grammar, $faker, $analyzer))->of('stmt', $plan));
253 self::assertEquals(
254 [new Terminal('A'), new Terminal('B')],
255 (new Derivation($grammar, $faker, $analyzer))->of('stmt', $plan->withStepBudget()),
256 );
257 }
258 public function testAffordableAllowsATerminalOnlyProductionWithNoExpansionBudgetLeft(): void
259 {
260 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([new Terminal('T')])])]);
261 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
262 $production = new Production([new Terminal('T')]);
263
264 self::assertSame(
265 [$production],
266 $derivation->affordable([$production], new Production(array_fill(0, 5000, new NonTerminal('stmt')))),
267 );
268 }
269
270 public function testAffordableReturnsAListAfterDiscardingAnOverBudgetAlternative(): void
271 {
272 $grammar = new Grammar('stmt', ['stmt' => new ProductionRule('stmt', [new Production([new Terminal('T')])])]);
273 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
274 $production = new Production([new Terminal('T')]);
275
276 self::assertSame([$production], $derivation->affordable([
277 new Production(array_fill(0, 5001, new NonTerminal('stmt'))),
278 $production,
279 ], new Production([])));
280 }
281
282 public function testAlternativesRespectsTheOccurrenceAndRejectsUnrealizableProductions(): void
283 {
284 $first = new Production([new Terminal('SELECT')]);
285 $second = new Production([new Terminal('DELETE')]);
286 $grammar = new Grammar('stmt', [
287 'stmt' => new ProductionRule('stmt', [$first, $second, new Production([new Terminal('UNKNOWN')])]),
288 ]);
289 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer(
290 $grammar,
291 static fn (string $terminal): bool => $terminal !== 'UNKNOWN',
292 ));
293 $plan = GenerationPlan::constrained('stmt', [
294 'stmt' => [ProductionPattern::containing('SELECT'), ProductionPattern::containing('DELETE')],
295 ]);
296
297 self::assertSame([$first], $derivation->alternatives(new NonTerminal('stmt'), $plan, 0));
298 self::assertSame([$second], $derivation->alternatives(new NonTerminal('stmt'), $plan, 1));
299 self::assertSame([$first, $second], $derivation->alternatives(new NonTerminal('stmt'), GenerationPlan::all(), 0));
300 }
301 public function testCompletableKeepsAnEmptyAlternativeWhenTheRemainingSiblingSatisfiesNonEmpty(): void
302 {
303 $empty = new Production([]);
304 $grammar = new Grammar('s', ['s' => new ProductionRule('s', [$empty])]);
305 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar, static fn (string $terminal): bool => true));
306 self::assertSame([$empty], $derivation->completable([$empty], [new NonTerminal('s'), new Terminal('X')], 0, GenerationPlan::all()->requiringNonEmpty()));
307 }
308
309
310 public function testAffordableCompletionRetainsOnlyProductionsWithAnAffordableNonEmptyContinuation(): void
311 {
312 $empty = new Production([]);
313 $output = new Production([new Terminal('T')]);
314 $grammar = new Grammar('s', ['s' => new ProductionRule('s', [$empty, $output])]);
315 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
316 self::assertSame([$output], $derivation->affordableCompletion([$empty, $output], [new NonTerminal('s')], 0, GenerationPlan::all()->requiringNonEmpty()));
317 }
318
319 public function testOfStillRejectsAnEntirelyForcedPlanWhoseDescendantCannotSatisfyNonEmpty(): void
320 {
321 $grammar = new Grammar('root', [
322 'root' => new ProductionRule('root', [new Production([new NonTerminal('child')])]),
323 'child' => new ProductionRule('child', [new Production([]), new Production([new Terminal('T')])]),
324 ]);
325 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
326 $this->expectException(GenerationException::class);
327 $derivation->of('root', GenerationPlan::constrained('root', ['child' => [ProductionPattern::at(0)]])->requiringNonEmpty());
328 }
329
330 public function testOfCountsOccurrencesAcrossSpecializedCopiesOfTheSameRule(): void
331 {
332 $choices = [new Production([new Terminal('A')], 0), new Production([new Terminal('B')], 1)];
333 $grammar = new Grammar('root', [
334 'root' => new ProductionRule('root', [new Production([new NonTerminal('left'), new NonTerminal('right'), new NonTerminal('left')])]),
335 'left' => new ProductionRule('left', $choices),
336 'right' => new ProductionRule('right', $choices),
337 ], ['left' => 'name', 'right' => 'name']);
338 $derivation = new Derivation($grammar, Factory::create(), new TerminationAnalyzer($grammar));
339 $plan = GenerationPlan::constrained('root', ['name' => [ProductionPattern::at(1), ProductionPattern::at(0), ProductionPattern::at(1)]]);
340 self::assertEquals([new Terminal('B'), new Terminal('A'), new Terminal('B')], $derivation->of('root', $plan));
341 }
342
343}
344