packages/sql-faker/src/Generation/Plan/Compilation/GrammarCompiler.php
1<?php
2
3declare(strict_types=1);
4
5namespace SqlFaker\Generation\Plan\Compilation;
6
7use InvalidArgumentException;
8use SqlFaker\Generation\Derivation\TerminationAnalyzer;
9use SqlFaker\Generation\Exception\GenerationException;
10use SqlFaker\Generation\Plan\LexemeConstraint;
11use SqlFaker\Generation\Plan\RulePlan;
12use SqlFaker\Grammar\Model\Grammar;
13use SqlFaker\Grammar\Model\NonTerminal;
14use SqlFaker\Grammar\Model\Production;
15use SqlFaker\Grammar\Model\ProductionRule;
16use SqlFaker\Grammar\Model\Symbol;
17
18/**
19 * Specializes grammar subtrees before making choices; every alternative retains its source production.
20 */
21final class GrammarCompiler
22{
23 /** @var array<string, string> */
24 private array $names = [];
25 /** @var array<string, string> */
26 private array $aliases = [];
27 /** @var array<string, ProductionRule> */
28 private array $rules = [];
29 /** @var array<string, array<int, array<string, LexemeConstraint>>> */
30 private array $lexemes = [];
31
32 /**
33 * Keeps the dialect grammar immutable across different plans.
34 */
35 public function __construct(private readonly Grammar $grammar)
36 {
37 }
38
39 /**
40 * @param array<string, RulePlan> $plans
41 * @throws InvalidArgumentException When a declaration names an unknown rule
42 * @throws GenerationException When no finite derivation satisfies the conditions
43 */
44 public function compile(string $root, array $plans): PreparedGrammar
45 {
46 $this->validate($plans);
47 $entry = $this->rule($root, new Scope($plans));
48 $grammar = new Grammar($entry, $this->rules, $this->aliases);
49 if ((new TerminationAnalyzer($grammar))->getMinLength($entry) === PHP_INT_MAX) {
50 throw GenerationException::noAlternativeMatchingPlan($root);
51 }
52 return new PreparedGrammar($grammar, $this->lexemes);
53 }
54
55 /**
56 * Checks all declarations, including conditionally visited branches.
57 * @param array<string, RulePlan> $plans
58 * @throws InvalidArgumentException When a planned rule is absent from this grammar
59 */
60 public function validate(array $plans): void
61 {
62 foreach ($plans as $name => $plan) {
63 if (!isset($this->grammar->ruleMap[$name])) {
64 throw new InvalidArgumentException('Unknown planned grammar rule: ' . $name);
65 }
66 $this->validate($plan->rules);
67 foreach ($plan->children as $childName => $children) {
68 foreach ($children as $child) {
69 $this->validate([$childName => $child]);
70 }
71 }
72 foreach ($plan->items ?? [] as $item) {
73 $this->validate([$name => $item]);
74 }
75 }
76 }
77
78 /**
79 * Memoizes recursive scopes before visiting their descendants.
80 * @param non-empty-list<RulePlan>|null $items Remaining items of a planned list
81 */
82 public function rule(string $name, Scope $scope, ?array $items = null): string
83 {
84 $plan = $scope->rules[$name] ?? RulePlan::any();
85 $scope = $scope->enter($plan);
86 $items ??= $plan->items;
87 $key = $name . ':' . serialize([$scope, $plan->pattern, $plan->children, $items]);
88 if (isset($this->names[$key])) {
89 return $this->names[$key];
90 }
91 $alias = '@plan' . count($this->names);
92 $this->names[$key] = $alias;
93 $this->aliases[$alias] = $name;
94 $this->rules[$alias] = new ProductionRule($alias, []);
95 $alternatives = [];
96 foreach ($this->grammar->ruleMap[$name]->alternatives ?? [] as $ordinal => $production) {
97 $symbols = array_map(static fn (Symbol $symbol): string => $symbol->value(), $production->symbols);
98 if ($plan->pattern !== null && !$plan->pattern->matches($symbols, $ordinal)) {
99 continue;
100 }
101 $item = $this->item($name, $production, $items);
102 if ($item === false || ($item?->pattern !== null && !$item->pattern->matches($symbols, $ordinal))) {
103 continue;
104 }
105 $children = $item === null ? $plan->children : $plan->merge($item)->children;
106 if (!$this->hasChildren($production, $children)) {
107 continue;
108 }
109 $inner = $item === null ? $scope : $scope->enter($item);
110 $expanded = $this->symbols($name, $production, $scope, $inner, $items, $children);
111 $this->lexemes[$alias][count($alternatives)] = $inner->lexemes;
112 $alternatives[] = new Production($expanded, $ordinal, $production->origin);
113 }
114 $this->rules[$alias] = new ProductionRule($alias, $alternatives);
115 return $alias;
116 }
117
118 /**
119 * Lists may recurse at either end; item order always means output order.
120 * @param non-empty-list<RulePlan>|null $items
121 */
122 public function item(string $name, Production $production, ?array $items): RulePlan|false|null
123 {
124 if ($items === null) {
125 return null;
126 }
127 $positions = [];
128 foreach ($production->symbols as $index => $symbol) {
129 if ($symbol instanceof NonTerminal && $symbol->value === $name) {
130 $positions[] = $index;
131 }
132 }
133 if (count($items) === 1) {
134 return $positions === [] && $production->symbols !== [] ? $items[0] : false;
135 }
136 if (count($positions) !== 1 || count($production->symbols) < 2) {
137 return false;
138 }
139 return match ($positions[0]) {
140 0 => $items[count($items) - 1],
141 count($production->symbols) - 1 => $items[0],
142 default => false,
143 };
144 }
145
146 /**
147 * Required child roles prune incompatible alternatives before generation.
148 * @param array<string, array<int, RulePlan>> $children
149 */
150 public function hasChildren(Production $production, array $children): bool
151 {
152 $counts = [];
153 foreach ($production->symbols as $symbol) {
154 if ($symbol instanceof NonTerminal) {
155 $counts[$symbol->value] = ($counts[$symbol->value] ?? 0) + 1;
156 }
157 }
158 foreach ($children as $name => $plans) {
159 foreach ($plans as $index => $plan) {
160 if ($index >= ($counts[$name] ?? 0)) {
161 return false;
162 }
163 }
164 }
165 return true;
166 }
167
168 /**
169 * Compiles list tails in the list scope and each item's fields in its own scope.
170 * @param non-empty-list<RulePlan>|null $items
171 * @param array<string, array<int, RulePlan>> $children
172 * @return list<Symbol>
173 * @throws InvalidArgumentException When a recursive list tail has no items
174 */
175 public function symbols(string $name, Production $production, Scope $scope, Scope $inner, ?array $items, array $children): array
176 {
177 $symbols = [];
178 $occurrences = [];
179 foreach ($production->symbols as $index => $symbol) {
180 if (!$symbol instanceof NonTerminal) {
181 $symbols[] = $symbol;
182 continue;
183 }
184 $occurrence = $occurrences[$symbol->value] ?? 0;
185 $occurrences[$symbol->value] = $occurrence + 1;
186 $child = $children[$symbol->value][$occurrence] ?? null;
187 if ($items !== null && $symbol->value === $name && count($items) > 1) {
188 $remaining = $index === 0 ? array_slice($items, 0, -1) : array_slice($items, 1);
189 if ($remaining === []) {
190 throw new InvalidArgumentException('A recursive list tail must retain an item.');
191 }
192 $tailScope = $child === null ? $scope : new Scope(array_replace($scope->rules, [$name => $child]), $scope->lexemes);
193 $symbols[] = new NonTerminal($this->rule($name, $tailScope, $remaining));
194 } else {
195 $childScope = $child === null ? $inner : new Scope(array_replace($inner->rules, [$symbol->value => $child]), $inner->lexemes);
196 $symbols[] = new NonTerminal($this->rule($symbol->value, $childScope));
197 }
198 }
199 return $symbols;
200 }
201}
202