packages/sql-faker/tests/Unit/Generation/Choice/PlanBuilderTest.php

1<?php
2
3declare (strict_types=1);
4
5namespace Tests\Unit\SqlFaker\Generation\Choice;
6
7use Closure;
8use Faker\Factory;
9use PHPUnit\Framework\Attributes\CoversClass;
10use PHPUnit\Framework\Attributes\UsesClass;
11use PHPUnit\Framework\TestCase;
12use SqlFaker\Generation\Candidate\ChoiceLexemeGenerator;
13use SqlFaker\Generation\Candidate\ValueLexemeGenerator;
14use SqlFaker\Generation\Choice\ByteChoices;
15use SqlFaker\Generation\Choice\BytePlanCompiler;
16use SqlFaker\Generation\Choice\PlanBuilder;
17use SqlFaker\Generation\Derivation\Completion\CompletionWitness;
18use SqlFaker\Generation\Derivation\Completion\PatternProductions;
19use SqlFaker\Generation\Derivation\CompletionCosts;
20use SqlFaker\Generation\Derivation\CompletionFrontier;
21use SqlFaker\Generation\Derivation\CompletionMemo;
22use SqlFaker\Generation\Derivation\CompletionReduction;
23use SqlFaker\Generation\Derivation\CompletionState;
24use SqlFaker\Generation\Derivation\ConstrainedCompletion;
25use SqlFaker\Generation\Derivation\ConstraintDependencies;
26use SqlFaker\Generation\Derivation\Derivation;
27use SqlFaker\Generation\Derivation\DerivationNode;
28use SqlFaker\Generation\Derivation\DerivationTrace;
29use SqlFaker\Generation\Derivation\TerminationAnalyzer;
30use SqlFaker\Generation\Derivation\TerminationCost;
31use SqlFaker\Generation\Derivation\TokenGenerator;
32use SqlFaker\Generation\Exception\GenerationException;
33use SqlFaker\Generation\Exception\LexicalException;
34use SqlFaker\Generation\Lexeme\Lexeme;
35use SqlFaker\Generation\Lexeme\LexemeBoundary;
36use SqlFaker\Generation\Lexeme\LexemeCandidates;
37use SqlFaker\Generation\Lexeme\LexemeInput;
38use SqlFaker\Generation\Lexeme\LexemeSequence;
39use SqlFaker\Generation\Lexeme\LexicalGrammar;
40use SqlFaker\Generation\Lexeme\OutputPart;
41use SqlFaker\Generation\Lexeme\ResolvedOutput;
42use SqlFaker\Generation\Lexeme\SpacingConstraint;
43use SqlFaker\Generation\Output\BoundaryCompletion;
44use SqlFaker\Generation\Output\CandidateResolver;
45use SqlFaker\Generation\Output\CombinedSpacingRule;
46use SqlFaker\Generation\Output\ReverseLexemeGenerator;
47use SqlFaker\Generation\Output\SqlSerializer;
48use SqlFaker\Generation\Plan\GenerationPlan;
49use SqlFaker\Generation\Plan\ProductionPattern;
50use SqlFaker\Generation\SqlGenerator;
51use SqlFaker\Generation\Token\ProductionOccurrence;
52use SqlFaker\Generation\Token\TerminalMappingRule;
53use SqlFaker\Generation\Token\TerminalOccurrence;
54use SqlFaker\Generation\Token\TerminalSequence;
55use SqlFaker\Generation\Token\TokenRewriter;
56use SqlFaker\Generation\Value\CharacterDomain;
57use SqlFaker\Generation\Value\ValueChoices;
58use SqlFaker\Grammar\Model\Grammar;
59use SqlFaker\Grammar\Model\NonTerminal;
60use SqlFaker\Grammar\Model\Production;
61use SqlFaker\Grammar\Model\ProductionRule;
62use SqlFaker\Grammar\Model\Terminal;
63
64#[CoversClass(PlanBuilder::class)]
65#[UsesClass(CompletionCosts::class)]
66#[UsesClass(GenerationPlan::class)]
67#[UsesClass(ProductionPattern::class)]
68#[UsesClass(Derivation::class)]
69#[UsesClass(TerminationAnalyzer::class)]
70#[UsesClass(TerminationCost::class)]
71#[UsesClass(DerivationNode::class)]
72#[UsesClass(ByteChoices::class)]
73#[UsesClass(Grammar::class)]
74#[UsesClass(NonTerminal::class)]
75#[UsesClass(Production::class)]
76#[UsesClass(ProductionRule::class)]
77#[UsesClass(Terminal::class)]
78#[UsesClass(GenerationException::class)]
79#[UsesClass(LexicalException::class)]
80#[UsesClass(SqlGenerator::class)]
81#[UsesClass(DerivationTrace::class)]
82#[UsesClass(ChoiceLexemeGenerator::class)]
83#[UsesClass(Lexeme::class)]
84#[UsesClass(LexemeCandidates::class)]
85#[UsesClass(LexemeInput::class)]
86#[UsesClass(LexemeSequence::class)]
87#[UsesClass(ValueLexemeGenerator::class)]
88#[UsesClass(CandidateResolver::class)]
89#[UsesClass(OutputPart::class)]
90#[UsesClass(ResolvedOutput::class)]
91#[UsesClass(ReverseLexemeGenerator::class)]
92#[UsesClass(SqlSerializer::class)]
93#[UsesClass(CombinedSpacingRule::class)]
94#[UsesClass(LexemeBoundary::class)]
95#[UsesClass(SpacingConstraint::class)]
96#[UsesClass(ProductionOccurrence::class)]
97#[UsesClass(TerminalMappingRule::class)]
98#[UsesClass(TerminalOccurrence::class)]
99#[UsesClass(TerminalSequence::class)]
100#[UsesClass(TokenGenerator::class)]
101#[UsesClass(TokenRewriter::class)]
102#[UsesClass(CompletionState::class)]
103#[UsesClass(CompletionFrontier::class)]
104#[UsesClass(ConstrainedCompletion::class)]
105#[UsesClass(ValueChoices::class)]
106#[UsesClass(BoundaryCompletion::class)]
107#[UsesClass(CompletionMemo::class)]
108#[UsesClass(CompletionReduction::class)]
109#[UsesClass(ConstraintDependencies::class)]
110#[UsesClass(BytePlanCompiler::class)]
111#[UsesClass(PatternProductions::class)]
112#[UsesClass(CompletionWitness::class)]
113#[UsesClass(CharacterDomain::class)]
114final class PlanBuilderTest extends TestCase
115{
116    public function testRootResolvesOnlyAnExplicitReleaseAlias(): void
117    {
118        $builder = new PlanBuilder(
119            (new Grammar(
120                'stmt',
121                [
122                    'stmt' => new ProductionRule(
123                        'stmt',
124                        [
125                            new Production([new Terminal('SELECT'), new NonTerminal('expr'), new NonTerminal('tail')]),
126                            new Production([new Terminal('DELETE'), new Terminal('FROM'), new Terminal('missing')]),
127                        ],
128                    ),
129                    'expr' => new ProductionRule(
130                        'expr',
131                        [
132                            new Production([new Terminal('1')]),
133                            new Production([new NonTerminal('expr'), new Terminal('+'), new NonTerminal('expr')]),
134                        ],
135                    ),
136                    'tail' => new ProductionRule('tail', [new Production([]), new Production([new Terminal('AS'), new Terminal('name')])]),
137                ],
138            ))->identified(),
139            $this->createMock(LexicalGrammar::class),
140            startSymbol: static fn (?string $requested): string => 'expr',
141        );
142        self::assertSame('stmt', $builder->root(GenerationPlan::all()));
143        self::assertSame('expr', $builder->root(GenerationPlan::fromRule('alias')));
144    }
145
146    public function testMinimumExpansionsKeepsTheNonEmptyRequirementSeparateFromNullability(): void
147    {
148        $grammar = new Grammar(
149            'root',
150            [
151                'root' => new ProductionRule('root', [new Production([]), new Production([new NonTerminal('leaf')])]),
152                'leaf' => new ProductionRule('leaf', [new Production([new Terminal('T')])]),
153            ],
154        );
155        $builder = new PlanBuilder($grammar, $this->createMock(LexicalGrammar::class));
156        self::assertSame(1, $builder->minimumExpansions(GenerationPlan::all()));
157        self::assertSame(2, $builder->minimumExpansions(GenerationPlan::all()->requiringNonEmpty()));
158    }
159
160    public function testMinimumExpansionsIncludesTheSelectedRootAlternativeBeforeAllocatingInputBudget(): void
161    {
162        $grammar = new Grammar(
163            'root',
164            [
165                'root' => new ProductionRule('root', [new Production([new Terminal('T')]), new Production([new NonTerminal('leaf')])]),
166                'leaf' => new ProductionRule('leaf', [new Production([new NonTerminal('end')])]),
167                'end' => new ProductionRule('end', [new Production([new Terminal('U')])]),
168            ],
169        );
170        $lexical = $this->createMock(LexicalGrammar::class);
171        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
172        $lexemePipeline = new ReverseLexemeGenerator(
173            new ChoiceLexemeGenerator(
174                new ValueLexemeGenerator('T', $literalDomain, ['T'], 'fixture', 'fixture-literal'),
175                new ValueLexemeGenerator('U', $literalDomain, ['U'], 'fixture', 'fixture-literal'),
176            ),
177            new CandidateResolver(new CombinedSpacingRule()),
178            'fixture',
179        );
180        $lexical->method('resolveSequence')->willReturnCallback(
181            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
182        );
183        $builder = new PlanBuilder($grammar, $lexical);
184        $constraints = GenerationPlan::constrained('root', ['root' => [ProductionPattern::at(1)]])->requiringNonEmpty()->withExpansionBudget(5);
185        self::assertSame(3, $builder->minimumExpansions($constraints));
186        $plan = (new BytePlanCompiler())->compile('', $builder, $constraints);
187        self::assertSame(3, $plan->expansionBudget());
188        self::assertEquals(ProductionPattern::at(1), $plan->patternAt('root', 0));
189        self::assertSame('U', (new SqlGenerator($grammar, Factory::create(), $lexical))->generate($plan));
190    }
191
192    public function testMinimumExpansionsRetainsNonEmptyCostsAndTheUnreachableSentinelForRootPatterns(): void
193    {
194        $grammar = new Grammar('root', ['root' => new ProductionRule('root', [new Production([]), new Production([new Terminal('T')])])]);
195        $builder = new PlanBuilder($grammar, $this->createMock(LexicalGrammar::class));
196        $empty = GenerationPlan::constrained('root', ['root' => [ProductionPattern::at(0)]]);
197        self::assertSame(1, $builder->minimumExpansions($empty));
198        self::assertSame(PHP_INT_MAX, $builder->minimumExpansions($empty->requiringNonEmpty()));
199        self::assertSame(
200            PHP_INT_MAX,
201            $builder->minimumExpansions(GenerationPlan::constrained('root', ['root' => [ProductionPattern::at(5)]])),
202        );
203        self::assertSame(
204            PHP_INT_MAX,
205            $builder->minimumExpansions(GenerationPlan::constrained('missing', ['missing' => [ProductionPattern::at(0)]])),
206        );
207    }
208
209    public function testBuildUsesTheSameContextualRewriteAndPinsItsCompleteCandidate(): void
210    {
211        $grammar = new Grammar('root', ['root' => new ProductionRule('root', [new Production([new Terminal('T')])])]);
212        $lexical = $this->createMock(LexicalGrammar::class);
213        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
214        $lexemePipeline = new ReverseLexemeGenerator(
215            new ChoiceLexemeGenerator(
216                new ValueLexemeGenerator('CONTEXTUAL', $literalDomain, ['CONTEXTUAL'], 'fixture', 'fixture-literal'),
217                new ValueLexemeGenerator('U', $literalDomain, ['U'], 'fixture', 'fixture-literal'),
218            ),
219            new CandidateResolver(new CombinedSpacingRule()),
220            'fixture',
221        );
222        $lexical->method('resolveSequence')->willReturnCallback(
223            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
224        );
225        $rewriter = new TokenRewriter(new TerminalMappingRule('root', 'T', 'CONTEXTUAL', 'fixture'));
226        $constraints = GenerationPlan::all()->withLexemes(['T' => ['explicit']]);
227        $plan = (new PlanBuilder($grammar, $lexical, $rewriter))->build($constraints, 1, static fn (int $count): int => 0, static fn (int $count): int => $count - 1);
228        self::assertSame('explicit', $plan->lexemeAt('CONTEXTUAL', 0));
229        self::assertNotNull($plan->candidateKeyAt('CONTEXTUAL', 0));
230        self::assertNull($plan->startRule());
231        $generator = new SqlGenerator($grammar, Factory::create(), $lexical, $rewriter);
232        self::assertSame('explicit', $generator->generate($plan));
233        self::assertSame('explicit', $generator->generate($plan));
234    }
235
236    public function testBuildPreservesRepeatedProductionAndLexemeConstraints(): void
237    {
238        $grammar = new Grammar(
239            'root',
240            [
241                'root' => new ProductionRule('root', [new Production([new NonTerminal('leaf'), new NonTerminal('leaf'), new NonTerminal('leaf')])]),
242                'leaf' => new ProductionRule('leaf', [new Production([new Terminal('T')]), new Production([new Terminal('U')])]),
243            ],
244        );
245        $lexical = $this->createMock(LexicalGrammar::class);
246        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
247        $lexemePipeline = new ReverseLexemeGenerator(
248            new ChoiceLexemeGenerator(
249                new ValueLexemeGenerator('T', $literalDomain, ['first', 'second'], 'fixture', 'fixture-literal'),
250                new ValueLexemeGenerator('U', $literalDomain, ['first', 'second'], 'fixture', 'fixture-literal'),
251            ),
252            new CandidateResolver(new CombinedSpacingRule()),
253            'fixture',
254        );
255        $lexical->method('resolveSequence')->willReturnCallback(
256            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
257        );
258        $constraints = GenerationPlan::constrained('root', ['leaf' => [ProductionPattern::at(0), ProductionPattern::at(0), ProductionPattern::at(1)]])->withLexemes(['T' => ['first', 'second'], 'U' => ['third']]);
259        $plan = (new PlanBuilder($grammar, $lexical))->build($constraints, 4, static fn (int $count): ?int => null, static fn (int $count): ?int => null);
260        self::assertEquals(ProductionPattern::at(0), $plan->patternAt('leaf', 0));
261        self::assertEquals(ProductionPattern::at(0), $plan->patternAt('leaf', 1));
262        self::assertEquals(ProductionPattern::at(1), $plan->patternAt('leaf', 2));
263        self::assertSame('first', $plan->lexemeAt('T', 0));
264        self::assertSame('second', $plan->lexemeAt('T', 1));
265        self::assertSame('third', $plan->lexemeAt('U', 0));
266    }
267
268    public function testBuildPreservesEmptyMarkerCandidatesWithoutLosingNonEmptyCompletion(): void
269    {
270        $grammar = new Grammar(
271            'root',
272            [
273                'root' => new ProductionRule('root', [new Production([new Terminal('END'), new NonTerminal('leaf')])]),
274                'leaf' => new ProductionRule('leaf', [new Production([]), new Production([new Terminal('T')])]),
275            ],
276        );
277        $lexical = $this->createMock(LexicalGrammar::class);
278        $lexical->method('isNonOutput')->willReturnCallback(static fn (string $name): bool => $name === 'END');
279        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
280        $lexemePipeline = new ReverseLexemeGenerator(
281            new ChoiceLexemeGenerator(
282                new ValueLexemeGenerator('T', $literalDomain, ['T'], 'fixture', 'fixture-literal'),
283                new ValueLexemeGenerator('END', $literalDomain, [''], 'fixture', 'fixture-literal'),
284            ),
285            new CandidateResolver(new CombinedSpacingRule()),
286            'fixture',
287        );
288        $lexical->method('resolveSequence')->willReturnCallback(
289            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
290        );
291        $builder = new PlanBuilder($grammar, $lexical);
292        $empty = $builder->build(GenerationPlan::all(), 2, static fn (int $count): ?int => null, static fn (int $count): ?int => null);
293        $nonEmpty = $builder->build(
294            GenerationPlan::all()->requiringNonEmpty(),
295            2,
296            static fn (int $count): ?int => null,
297            static fn (int $count): ?int => null,
298        );
299        self::assertSame('', $empty->lexemeAt('END', 0));
300        self::assertNotNull($empty->candidateKeyAt('END', 0));
301        self::assertNull($empty->lexemeAt('T', 0));
302        self::assertSame('T', $nonEmpty->lexemeAt('T', 0));
303    }
304
305    public function testBuildReservesAllPendingSiblingsAndRetainsTheOriginalOrdinal(): void
306    {
307        $grammar = (new Grammar(
308            'stmt',
309            [
310                'stmt' => new ProductionRule(
311                    'stmt',
312                    [
313                        new Production([new Terminal('SELECT'), new NonTerminal('expr'), new NonTerminal('tail')]),
314                        new Production([new Terminal('DELETE'), new Terminal('FROM'), new Terminal('missing')]),
315                    ],
316                ),
317                'expr' => new ProductionRule(
318                    'expr',
319                    [
320                        new Production([new Terminal('1')]),
321                        new Production([new NonTerminal('expr'), new Terminal('+'), new NonTerminal('expr')]),
322                    ],
323                ),
324                'tail' => new ProductionRule('tail', [new Production([]), new Production([new Terminal('AS'), new Terminal('name')])]),
325            ],
326        ))->identified();
327        $lexical = $this->createMock(LexicalGrammar::class);
328        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
329        $lexemePipeline = new ReverseLexemeGenerator(
330            new ChoiceLexemeGenerator(
331                new ValueLexemeGenerator('SELECT', $literalDomain, ['SELECT'], 'fixture', 'fixture-literal'),
332                new ValueLexemeGenerator('DELETE', $literalDomain, ['DELETE'], 'fixture', 'fixture-literal'),
333                new ValueLexemeGenerator('FROM', $literalDomain, ['FROM'], 'fixture', 'fixture-literal'),
334                new ValueLexemeGenerator('missing', $literalDomain, ['missing'], 'fixture', 'fixture-literal'),
335                new ValueLexemeGenerator('1', $literalDomain, ['1'], 'fixture', 'fixture-literal'),
336                new ValueLexemeGenerator('+', $literalDomain, ['+'], 'fixture', 'fixture-literal'),
337                new ValueLexemeGenerator('AS', $literalDomain, ['AS'], 'fixture', 'fixture-literal'),
338                new ValueLexemeGenerator('name', $literalDomain, ['name'], 'fixture', 'fixture-literal'),
339                new ValueLexemeGenerator('CHANGED', $literalDomain, ['CHANGED'], 'fixture', 'fixture-literal'),
340            ),
341            new CandidateResolver(new CombinedSpacingRule()),
342            'fixture',
343        );
344        $lexical->method('resolveSequence')->willReturnCallback(
345            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
346        );
347        $constraints = GenerationPlan::constrained('stmt', ['stmt' => [ProductionPattern::at(0)]])->requiringNonEmpty();
348        $plan = (new PlanBuilder($grammar, $lexical))->build($constraints, 3, static fn (int $count): ?int => null, static fn (int $count): ?int => null);
349        self::assertEquals(ProductionPattern::at(0), $plan->patternAt('tail', 0));
350        self::assertSame('SELECT 1', (new SqlGenerator($grammar, Factory::create(), $lexical))->generate($plan));
351    }
352
353    public function testBuildPropagatesMissingCandidateFailuresWithoutRetrying(): void
354    {
355        $lexical = $this->createMock(LexicalGrammar::class);
356        $lexical->expects(self::once())->method('resolveSequence')->willThrowException(new LexicalException('missing candidate'));
357        $builder = new PlanBuilder(
358            (new Grammar(
359                'stmt',
360                [
361                    'stmt' => new ProductionRule(
362                        'stmt',
363                        [
364                            new Production([new Terminal('SELECT'), new NonTerminal('expr'), new NonTerminal('tail')]),
365                            new Production([new Terminal('DELETE'), new Terminal('FROM'), new Terminal('missing')]),
366                        ],
367                    ),
368                    'expr' => new ProductionRule(
369                        'expr',
370                        [
371                            new Production([new Terminal('1')]),
372                            new Production([new NonTerminal('expr'), new Terminal('+'), new NonTerminal('expr')]),
373                        ],
374                    ),
375                    'tail' => new ProductionRule('tail', [new Production([]), new Production([new Terminal('AS'), new Terminal('name')])]),
376                ],
377            ))->identified(),
378            $lexical,
379        );
380        $this->expectException(LexicalException::class);
381        $builder->build(GenerationPlan::all(), 5, static fn (int $count): ?int => null, static fn (int $count): ?int => null);
382    }
383
384    public function testBuildReportsAnUnknownRequestedRule(): void
385    {
386        $builder = new PlanBuilder(
387            (new Grammar(
388                'stmt',
389                [
390                    'stmt' => new ProductionRule(
391                        'stmt',
392                        [
393                            new Production([new Terminal('SELECT'), new NonTerminal('expr'), new NonTerminal('tail')]),
394                            new Production([new Terminal('DELETE'), new Terminal('FROM'), new Terminal('missing')]),
395                        ],
396                    ),
397                    'expr' => new ProductionRule(
398                        'expr',
399                        [
400                            new Production([new Terminal('1')]),
401                            new Production([new NonTerminal('expr'), new Terminal('+'), new NonTerminal('expr')]),
402                        ],
403                    ),
404                    'tail' => new ProductionRule('tail', [new Production([]), new Production([new Terminal('AS'), new Terminal('name')])]),
405                ],
406            ))->identified(),
407            $this->createMock(LexicalGrammar::class),
408        );
409        $this->expectException(GenerationException::class);
410        $builder->build(GenerationPlan::fromRule('missing'), 5, static fn (int $count): ?int => null, static fn (int $count): ?int => null);
411    }
412
413    public function testMinimumExpansionsIncludesTheConstrainedDescendantBeforeDrawingTheBudget(): void
414    {
415        $grammar = new Grammar(
416            'root',
417            [
418                'root' => new ProductionRule('root', [new Production([new NonTerminal('child')])]),
419                'child' => new ProductionRule('child', [new Production([new Terminal('T')]), new Production([new NonTerminal('leaf')])]),
420                'leaf' => new ProductionRule('leaf', [new Production([new Terminal('U')])]),
421            ],
422        );
423        $lexical = $this->createMock(LexicalGrammar::class);
424        $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
425        $lexemePipeline = new ReverseLexemeGenerator(
426            new ChoiceLexemeGenerator(
427                new ValueLexemeGenerator('T', $literalDomain, ['T'], 'fixture', 'fixture-literal'),
428                new ValueLexemeGenerator('U', $literalDomain, ['U'], 'fixture', 'fixture-literal'),
429            ),
430            new CandidateResolver(new CombinedSpacingRule()),
431            'fixture',
432        );
433        $lexical->method('resolveSequence')->willReturnCallback(
434            static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
435        );
436        $builder = new PlanBuilder($grammar, $lexical);
437        $constraints = GenerationPlan::constrained('root', ['child' => [ProductionPattern::at(1)]])->requiringNonEmpty()->withExpansionBudget(5);
438        self::assertSame(3, $builder->minimumExpansions($constraints));
439        $plan = (new BytePlanCompiler())->compile('', $builder, $constraints);
440        self::assertSame(3, $plan->expansionBudget());
441        self::assertSame('U', (new SqlGenerator($grammar, Factory::create(), $lexical))->generate($plan));
442    }
443}
444