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