packages/sql-faker/tests/Unit/Generation/Choice/BytePlanCompilerTest.php
1<?php
2
3declare (strict_types=1);
4
5namespace Tests\Unit\SqlFaker\Generation\Choice;
6
7use Closure;
8use PHPUnit\Framework\Attributes\CoversClass;
9use PHPUnit\Framework\Attributes\DataProvider;
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\DerivationTrace;
28use SqlFaker\Generation\Derivation\TerminationAnalyzer;
29use SqlFaker\Generation\Derivation\TerminationCost;
30use SqlFaker\Generation\Derivation\TokenGenerator;
31use SqlFaker\Generation\Lexeme\Lexeme;
32use SqlFaker\Generation\Lexeme\LexemeBoundary;
33use SqlFaker\Generation\Lexeme\LexemeCandidates;
34use SqlFaker\Generation\Lexeme\LexemeInput;
35use SqlFaker\Generation\Lexeme\LexemeSequence;
36use SqlFaker\Generation\Lexeme\LexicalGrammar;
37use SqlFaker\Generation\Lexeme\OutputPart;
38use SqlFaker\Generation\Lexeme\ResolvedOutput;
39use SqlFaker\Generation\Lexeme\SpacingConstraint;
40use SqlFaker\Generation\Output\BoundaryCompletion;
41use SqlFaker\Generation\Output\CandidateResolver;
42use SqlFaker\Generation\Output\CombinedSpacingRule;
43use SqlFaker\Generation\Output\ReverseLexemeGenerator;
44use SqlFaker\Generation\Plan\GenerationPlan;
45use SqlFaker\Generation\Plan\ProductionPattern;
46use SqlFaker\Generation\Token\ProductionOccurrence;
47use SqlFaker\Generation\Token\TerminalOccurrence;
48use SqlFaker\Generation\Token\TerminalSequence;
49use SqlFaker\Generation\Value\CharacterDomain;
50use SqlFaker\Generation\Value\ValueChoices;
51use SqlFaker\Grammar\Model\Grammar;
52use SqlFaker\Grammar\Model\NonTerminal;
53use SqlFaker\Grammar\Model\Production;
54use SqlFaker\Grammar\Model\ProductionRule;
55use SqlFaker\Grammar\Model\Terminal;
56
57#[CoversClass(BytePlanCompiler::class)]
58#[UsesClass(GenerationPlan::class)]
59#[UsesClass(ProductionPattern::class)]
60#[UsesClass(PlanBuilder::class)]
61#[UsesClass(ByteChoices::class)]
62#[UsesClass(CompletionCosts::class)]
63#[UsesClass(Grammar::class)]
64#[UsesClass(NonTerminal::class)]
65#[UsesClass(Production::class)]
66#[UsesClass(ProductionRule::class)]
67#[UsesClass(Terminal::class)]
68#[UsesClass(Derivation::class)]
69#[UsesClass(DerivationTrace::class)]
70#[UsesClass(TerminationAnalyzer::class)]
71#[UsesClass(TerminationCost::class)]
72#[UsesClass(ChoiceLexemeGenerator::class)]
73#[UsesClass(Lexeme::class)]
74#[UsesClass(LexemeCandidates::class)]
75#[UsesClass(LexemeInput::class)]
76#[UsesClass(LexemeSequence::class)]
77#[UsesClass(ValueLexemeGenerator::class)]
78#[UsesClass(CandidateResolver::class)]
79#[UsesClass(OutputPart::class)]
80#[UsesClass(ResolvedOutput::class)]
81#[UsesClass(ReverseLexemeGenerator::class)]
82#[UsesClass(CombinedSpacingRule::class)]
83#[UsesClass(LexemeBoundary::class)]
84#[UsesClass(SpacingConstraint::class)]
85#[UsesClass(ProductionOccurrence::class)]
86#[UsesClass(TerminalOccurrence::class)]
87#[UsesClass(TerminalSequence::class)]
88#[UsesClass(TokenGenerator::class)]
89#[UsesClass(CompletionState::class)]
90#[UsesClass(CompletionFrontier::class)]
91#[UsesClass(ConstrainedCompletion::class)]
92#[UsesClass(ValueChoices::class)]
93#[UsesClass(BoundaryCompletion::class)]
94#[UsesClass(CompletionMemo::class)]
95#[UsesClass(CompletionReduction::class)]
96#[UsesClass(ConstraintDependencies::class)]
97#[UsesClass(PatternProductions::class)]
98#[UsesClass(CompletionWitness::class)]
99#[UsesClass(CharacterDomain::class)]
100final class BytePlanCompilerTest extends TestCase
101{
102 /**
103 * @param GenerationPlan<bool>|null $constraints
104 */
105 #[DataProvider('providerInputBudgets')]
106
107 public function testCompileMapsTheHeaderIntoTheAllowedExpansionRange(string $input, ?GenerationPlan $constraints, int $expected): void
108 {
109 $grammar = new Grammar(
110 'root',
111 [
112 'root' => new ProductionRule('root', [new Production([new NonTerminal('leaf')])]),
113 'leaf' => new ProductionRule('leaf', [new Production([new Terminal('T')])]),
114 ],
115 );
116 $lexical = $this->createMock(LexicalGrammar::class);
117 $lexical->method('isNonOutput')->willReturn(false);
118 $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
119 $lexemePipeline = new ReverseLexemeGenerator(
120 new ChoiceLexemeGenerator(
121 new ValueLexemeGenerator('T', $literalDomain, ['T'], 'fixture', 'fixture-literal'),
122 new ValueLexemeGenerator('U', $literalDomain, ['U'], 'fixture', 'fixture-literal'),
123 ),
124 new CandidateResolver(new CombinedSpacingRule()),
125 'fixture',
126 );
127 $lexical->method('resolveSequence')->willReturnCallback(
128 static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
129 );
130 $plan = (new BytePlanCompiler())->compile($input, new PlanBuilder($grammar, $lexical), $constraints);
131 self::assertSame($expected, $plan->expansionBudget());
132 self::assertSame($constraints?->startRule(), $plan->startRule());
133 }
134
135 /**
136 * @return iterable<string, array{string, GenerationPlan<bool>|null, int}>
137 */
138
139 public static function providerInputBudgets(): iterable
140 {
141 yield 'empty' => ['', null, 2];
142 yield 'short header' => ["\x01", null, 3];
143 yield 'second header byte' => ["\x00\x01", null, 258];
144 yield 'third header byte' => ["\x00\x00\x01", null, 551];
145 yield 'all header bytes' => ["\x01\x02\x03\x04", null, 4450];
146 yield 'body does not change budget' => ["\x01\x02\x03\x04\xff", null, 4450];
147 yield 'default maximum' => [pack('V', 4998), null, 5000];
148 yield 'default wraparound' => [pack('V', 4999), null, 2];
149 yield 'unsigned header' => ["\xff\xff\xff\xff", null, 1462];
150 yield 'explicit maximum' => [pack('V', 7), GenerationPlan::all()->withExpansionBudget(9), 9];
151 yield 'explicit wraparound' => [pack('V', 8), GenerationPlan::all()->withExpansionBudget(9), 2];
152 yield 'single possible budget' => ["\xff", GenerationPlan::fromRule('leaf')->withExpansionBudget(1), 1];
153 yield 'largest allowed budget' => [pack('V', 999998), GenerationPlan::all()->withExpansionBudget(1000000), 1000000];
154 }
155
156 public function testCompileSeparatesProductionChoicesFromLexemesAndCompletesAnOddInput(): void
157 {
158 $grammar = new Grammar(
159 'root',
160 [
161 'root' => new ProductionRule('root', [new Production([new NonTerminal('choice'), new NonTerminal('choice')])]),
162 'choice' => new ProductionRule('choice', [new Production([new Terminal('T')]), new Production([new Terminal('U')])]),
163 ],
164 );
165 $lexical = $this->createMock(LexicalGrammar::class);
166 $lexical->method('isNonOutput')->willReturn(false);
167 $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
168 $lexemePipeline = new ReverseLexemeGenerator(
169 new ChoiceLexemeGenerator(
170 new ValueLexemeGenerator('T', $literalDomain, ['first', 'second'], 'fixture', 'fixture-literal'),
171 new ValueLexemeGenerator('U', $literalDomain, ['first', 'second'], 'fixture', 'fixture-literal'),
172 ),
173 new CandidateResolver(new CombinedSpacingRule()),
174 'fixture',
175 );
176 $lexical->method('resolveSequence')->willReturnCallback(
177 static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
178 );
179 $builder = new PlanBuilder($grammar, $lexical);
180 $plan = (new BytePlanCompiler())->compile("\x00\x00\x00\x00\x00\x01\x01\x00\x00", $builder);
181 self::assertEquals(ProductionPattern::at(1), $plan->patternAt('choice', 0));
182 self::assertEquals(ProductionPattern::at(0), $plan->patternAt('choice', 1));
183 self::assertSame('first', $plan->lexemeAt('U', 0));
184 self::assertSame('second', $plan->lexemeAt('T', 0));
185 self::assertNotNull($plan->candidateKeyAt('U', 0));
186 }
187
188 /**
189 * @return list<array{string}>
190 */
191
192 public static function providerInputs(): array
193 {
194 return [[''], ["\x01"], ["\xff\xff\xff\xff"], ["\x00\x00\x00\x00abc"], [str_repeat("\xff", 40)]];
195 }
196 #[DataProvider('providerInputs')]
197
198 public function testCompileResolvesChoicesIntoInspectableReusableInstructions(string $input): void
199 {
200 $grammar = (new Grammar(
201 'stmt',
202 [
203 'stmt' => new ProductionRule(
204 'stmt',
205 [
206 new Production([new Terminal('SELECT'), new NonTerminal('expr'), new NonTerminal('tail')]),
207 new Production([new Terminal('DELETE'), new Terminal('FROM'), new Terminal('missing')]),
208 ],
209 ),
210 'expr' => new ProductionRule(
211 'expr',
212 [
213 new Production([new Terminal('1')]),
214 new Production([new NonTerminal('expr'), new Terminal('+'), new NonTerminal('expr')]),
215 ],
216 ),
217 'tail' => new ProductionRule('tail', [new Production([]), new Production([new Terminal('AS'), new Terminal('name')])]),
218 ],
219 ))->identified();
220 $lexical = $this->createMock(LexicalGrammar::class);
221 $lexical->method('isNonOutput')->willReturn(false);
222 $literalDomain = new CharacterDomain(array_map(chr(...), range(0, 255)), 0, 255);
223 $lexemePipeline = new ReverseLexemeGenerator(
224 new ChoiceLexemeGenerator(
225 new ValueLexemeGenerator('SELECT', $literalDomain, ['SELECT'], 'fixture', 'fixture-literal'),
226 new ValueLexemeGenerator('DELETE', $literalDomain, ['DELETE'], 'fixture', 'fixture-literal'),
227 new ValueLexemeGenerator('FROM', $literalDomain, ['FROM'], 'fixture', 'fixture-literal'),
228 new ValueLexemeGenerator('missing', $literalDomain, ['missing'], 'fixture', 'fixture-literal'),
229 new ValueLexemeGenerator('1', $literalDomain, ['1'], 'fixture', 'fixture-literal'),
230 new ValueLexemeGenerator('+', $literalDomain, ['+'], 'fixture', 'fixture-literal'),
231 new ValueLexemeGenerator('AS', $literalDomain, ['AS'], 'fixture', 'fixture-literal'),
232 new ValueLexemeGenerator('name', $literalDomain, ['name'], 'fixture', 'fixture-literal'),
233 new ValueLexemeGenerator('CHANGED', $literalDomain, ['CHANGED'], 'fixture', 'fixture-literal'),
234 ),
235 new CandidateResolver(new CombinedSpacingRule()),
236 'fixture',
237 );
238 $lexical->method('resolveSequence')->willReturnCallback(
239 static fn (TerminalSequence $sequence, ?GenerationPlan $plan, Closure $choose) => $lexemePipeline->generate($sequence, $plan, $choose),
240 );
241 $builder = new PlanBuilder($grammar, $lexical);
242 $plan = (new BytePlanCompiler())->compile($input, $builder);
243 self::assertEquals($plan, (new BytePlanCompiler())->compile($input, $builder));
244 self::assertNotNull($plan->patternAt('stmt', 0));
245 self::assertNotNull($plan->candidateKeyAt('SELECT', 0) ?? $plan->candidateKeyAt('DELETE', 0));
246 self::assertFalse($plan->requiresNonEmpty());
247 self::assertNull($plan->startRule());
248 }
249}
250