packages/sql-faker/tests/Unit/Generation/Plan/Compilation/GrammarCompilerTest.php
1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\Generation\Plan\Compilation;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\UsesClass;
9use PHPUnit\Framework\TestCase;
10use SqlFaker\Generation\Exception\GenerationException;
11use SqlFaker\Generation\Plan\Compilation\GrammarCompiler;
12use SqlFaker\Generation\Plan\Compilation\PreparedGrammar;
13use SqlFaker\Generation\Plan\Compilation\Scope;
14use SqlFaker\Generation\Plan\LexemeConstraint;
15use SqlFaker\Generation\Plan\ProductionPattern;
16use SqlFaker\Generation\Plan\RulePlan;
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(GrammarCompiler::class)]
24#[UsesClass(PreparedGrammar::class)]
25#[UsesClass(\SqlFaker\Generation\Derivation\TerminationCost::class)]
26#[UsesClass(\SqlFaker\Generation\Derivation\TerminationAnalyzer::class)]
27#[UsesClass(GenerationException::class)]
28#[UsesClass(Scope::class)]
29#[UsesClass(ProductionPattern::class)]
30#[UsesClass(RulePlan::class)]
31#[UsesClass(Grammar::class)]
32#[UsesClass(NonTerminal::class)]
33#[UsesClass(Production::class)]
34#[UsesClass(ProductionRule::class)]
35#[UsesClass(Terminal::class)]
36#[UsesClass(LexemeConstraint::class)]
37final class GrammarCompilerTest extends TestCase
38{
39 public function testCompileListItemsPreserveOutputOrderForBothRecursionDirections(): void
40 {
41 $grammar = new Grammar('list', [
42 'list' => new ProductionRule('list', [
43 new Production([new NonTerminal('list'), new Terminal(','), new NonTerminal('item')]),
44 new Production([new NonTerminal('item'), new Terminal(';'), new NonTerminal('list')]),
45 new Production([new NonTerminal('item')]),
46 ]),
47 'item' => new ProductionRule('item', [new Production([new Terminal('ID')]), new Production([new Terminal('INTEGER')])]),
48 ]);
49 $plan = RulePlan::any()->withItems(
50 RulePlan::any()->withRule('item', RulePlan::any()->allowing(ProductionPattern::exactly('ID'))),
51 RulePlan::any()->withRule('item', RulePlan::any()->allowing(ProductionPattern::exactly('INTEGER'))),
52 );
53 $prepared = (new GrammarCompiler($grammar))->compile('list', ['list' => $plan]);
54 $enumerate = static function (string $rule) use (&$enumerate, $prepared): array {
55 $language = [];
56 foreach ($prepared->grammar->ruleMap[$rule]->alternatives as $production) {
57 $prefixes = [''];
58 foreach ($production->symbols as $symbol) {
59 $suffixes = $symbol instanceof NonTerminal ? $enumerate($symbol->value) : [$symbol->value()];
60 $combined = [];
61 foreach ($prefixes as $prefix) {
62 foreach ($suffixes as $suffix) {
63 $combined[] = trim($prefix . ' ' . $suffix);
64 }
65 }
66 $prefixes = $combined;
67 }
68 $language = [...$language, ...$prefixes];
69 }
70 return array_values(array_unique($language));
71 };
72 $language = $enumerate($prepared->grammar->startSymbol);
73 sort($language);
74 self::assertSame(['ID , INTEGER', 'ID ; INTEGER'], $language);
75 self::assertCount(3, $grammar->ruleMap['list']->alternatives);
76 }
77
78 public function testHasChildrenConditionsPruneIncompatibleProductions(): void
79 {
80 $grammar = new Grammar('pair', [
81 'pair' => new ProductionRule('pair', [new Production([new NonTerminal('value')]), new Production([new NonTerminal('value'), new NonTerminal('value')])]),
82 'value' => new ProductionRule('value', [new Production([new Terminal('ID')]), new Production([new Terminal('INTEGER')])]),
83 ]);
84 $plan = RulePlan::any()->withChild('value', 0, RulePlan::any()->allowing(ProductionPattern::exactly('ID')))
85 ->withChild('value', 1, RulePlan::any()->allowing(ProductionPattern::exactly('INTEGER')));
86 $prepared = (new GrammarCompiler($grammar))->compile('pair', ['pair' => $plan]);
87 $choices = $prepared->grammar->ruleMap[$prepared->grammar->startSymbol]->alternatives;
88 self::assertCount(1, $choices);
89 $first = $choices[0]->symbols[0]->value();
90 $second = $choices[0]->symbols[1]->value();
91 self::assertSame('ID', $prepared->grammar->ruleMap[$first]->alternatives[0]->symbols[0]->value());
92 self::assertSame('INTEGER', $prepared->grammar->ruleMap[$second]->alternatives[0]->symbols[0]->value());
93 }
94
95 public function testCompileContradictoryProductionConditionsAreRejected(): void
96 {
97 $grammar = new Grammar('root', ['root' => new ProductionRule('root', [new Production([new Terminal('T')])])]);
98 $this->expectException(GenerationException::class);
99 (new GrammarCompiler($grammar))->compile('root', ['root' => RulePlan::any()->allowing(ProductionPattern::exactly('U'))]);
100 }
101
102
103 public function testValidateAcceptsNestedChildAndListDeclarations(): void
104 {
105 $grammar = new Grammar('root', ['root' => new ProductionRule('root', [new Production([new Terminal('T')])])]);
106 $compiler = new GrammarCompiler($grammar);
107 $compiler->validate(['root' => RulePlan::any()->withChild('root', 0, RulePlan::any())->withItems(RulePlan::any()->withRule('root', RulePlan::any()))]);
108 self::assertCount(1, $compiler->compile('root', [])->grammar->ruleMap);
109 }
110
111 public function testRuleMemoizesRecursiveScopesBeforeWalkingTheirChildren(): void
112 {
113 $grammar = new Grammar('root', ['root' => new ProductionRule('root', [new Production([new NonTerminal('root')]), new Production([new Terminal('T')])])]);
114 $compiler = new GrammarCompiler($grammar);
115 $scope = new Scope();
116 self::assertSame($compiler->rule('root', $scope), $compiler->rule('root', $scope));
117 $prepared = $compiler->compile('root', []);
118 self::assertCount(1, $prepared->grammar->ruleMap);
119 self::assertCount(2, $prepared->grammar->ruleMap[$prepared->grammar->startSymbol]->alternatives);
120 }
121
122 public function testItemRejectsNullableAndBranchingRecursionForOrderedLists(): void
123 {
124 $compiler = new GrammarCompiler(new Grammar('list', []));
125 $item = RulePlan::any();
126 self::assertFalse($compiler->item('list', new Production([]), [$item]));
127 self::assertFalse($compiler->item('list', new Production([new NonTerminal('list'), new NonTerminal('list')]), [$item, $item]));
128 self::assertNull($compiler->item('list', new Production([]), null));
129 }
130
131 public function testSymbolsKeepInfeasibleBranchesFromInvalidatingOtherAlternatives(): void
132 {
133 $grammar = new Grammar('root', [
134 'root' => new ProductionRule('root', [new Production([new NonTerminal('blocked')]), new Production([new Terminal('OK')])]),
135 'blocked' => new ProductionRule('blocked', [new Production([new Terminal('T')])]),
136 ]);
137 $prepared = (new GrammarCompiler($grammar))->compile('root', ['blocked' => RulePlan::any()->allowing(ProductionPattern::exactly('U'))]);
138 $costs = new \SqlFaker\Generation\Derivation\TerminationCost($prepared->grammar, static fn (string $terminal): bool => true, 0, 1);
139 self::assertSame(1, $costs->of($prepared->grammar->startSymbol));
140 self::assertSame('OK', $prepared->grammar->ruleMap[$prepared->grammar->startSymbol]->alternatives[1]->symbols[0]->value());
141 }
142
143
144 public function testSymbolsApplyChildConditionsToARecursiveListTail(): void
145 {
146 $grammar = new Grammar('list', [
147 'list' => new ProductionRule('list', [
148 new Production([new NonTerminal('list'), new Terminal(','), new Terminal('ID')]),
149 new Production([new Terminal('ID')]),
150 new Production([new Terminal('INTEGER')]),
151 ]),
152 ]);
153 $plan = RulePlan::any()->withItems(RulePlan::any(), RulePlan::any())
154 ->withChild('list', 0, RulePlan::any()->allowing(ProductionPattern::exactly('INTEGER')));
155 $prepared = (new GrammarCompiler($grammar))->compile('list', ['list' => $plan]);
156 $root = $prepared->grammar->ruleMap[$prepared->grammar->startSymbol]->alternatives;
157 self::assertCount(1, $root);
158 $tail = $prepared->grammar->ruleMap[$root[0]->symbols[0]->value()]->alternatives;
159 self::assertCount(1, $tail);
160 self::assertSame('INTEGER', $tail[0]->symbols[0]->value());
161 }
162
163
164 public function testCompileAppliesProductionConditionsToEachListItem(): void
165 {
166 $grammar = new Grammar('list', ['list' => new ProductionRule('list', [new Production([new Terminal('ID')]), new Production([new Terminal('INTEGER')])])]);
167 $plan = RulePlan::any()->withItems(RulePlan::any()->allowing(ProductionPattern::exactly('INTEGER')));
168 $prepared = (new GrammarCompiler($grammar))->compile('list', ['list' => $plan]);
169 $alternatives = $prepared->grammar->ruleMap[$prepared->grammar->startSymbol]->alternatives;
170 self::assertCount(1, $alternatives);
171 self::assertSame('INTEGER', $alternatives[0]->symbols[0]->value());
172 }
173
174 public function testItemSupportsUnseparatedListsButRejectsRecursionBetweenFields(): void
175 {
176 $compiler = new GrammarCompiler(new Grammar('list', []));
177 $first = RulePlan::any()->allowing(ProductionPattern::containing('ID'));
178 $second = RulePlan::any()->allowing(ProductionPattern::containing('INTEGER'));
179 self::assertSame($second, $compiler->item('list', new Production([new NonTerminal('list'), new Terminal('INTEGER')]), [$first, $second]));
180 self::assertSame($first, $compiler->item('list', new Production([new Terminal('ID'), new NonTerminal('list')]), [$first, $second]));
181 self::assertFalse($compiler->item('list', new Production([new Terminal('LP'), new NonTerminal('list'), new Terminal('RP')]), [$first, $second]));
182 }
183
184 public function testHasChildrenRejectsARequiredRoleAbsentFromTheProduction(): void
185 {
186 $compiler = new GrammarCompiler(new Grammar('root', []));
187 self::assertFalse($compiler->hasChildren(new Production([new Terminal('ID')]), ['name' => [RulePlan::any()]]));
188 self::assertTrue($compiler->hasChildren(new Production([new NonTerminal('name')]), ['name' => [RulePlan::any()]]));
189 }
190
191 public function testRuleDoesNotShareACompiledSubtreeBetweenDifferentLexicalScopes(): void
192 {
193 $grammar = new Grammar('name', ['name' => new ProductionRule('name', [new Production([new Terminal('ID')])])]);
194 $compiler = new GrammarCompiler($grammar);
195 $users = new Scope([], ['ID' => LexemeConstraint::oneOf('users')]);
196 $orders = new Scope([], ['ID' => LexemeConstraint::oneOf('orders')]);
197 self::assertNotSame($compiler->rule('name', $users), $compiler->rule('name', $orders));
198 self::assertSame($compiler->rule('name', $users), $compiler->rule('name', $users));
199 }
200
201 public function testSymbolsPreserveInheritedRulesWhenSelectingAnOperand(): void
202 {
203 $grammar = new Grammar('expr', [
204 'expr' => new ProductionRule('expr', [new Production([new NonTerminal('term')])]),
205 'term' => new ProductionRule('term', [new Production([new Terminal('INTEGER')]), new Production([new Terminal('STRING')])]),
206 ]);
207 $compiler = new GrammarCompiler($grammar);
208 $scope = new Scope(['term' => RulePlan::any()->allowing(ProductionPattern::exactly('INTEGER'))]);
209 $symbols = $compiler->symbols('pair', new Production([new NonTerminal('expr')]), $scope, $scope, null, ['expr' => [RulePlan::any()]]);
210 $prepared = $compiler->compile('expr', $scope->rules);
211 $expression = $prepared->grammar->ruleMap[$symbols[0]->value()]->alternatives[0];
212 $terms = $prepared->grammar->ruleMap[$expression->symbols[0]->value()]->alternatives;
213 self::assertCount(1, $terms);
214 self::assertSame('INTEGER', $terms[0]->symbols[0]->value());
215 }
216
217}
218