packages/sql-catalog/src/Core/Text/TextGeneralization.php
1<?php
2
3declare(strict_types=1);
4
5namespace SqlCatalog\Core\Text;
6
7use SqlCatalog\Core\Type\TypeShape;
8
9/**
10 * Collapses several patterns into the one shape that covers all of them.
11 *
12 * Joining branches or iterations of a loop can produce more strings than a
13 * catalog should list. Generalization keeps the text the alternatives agree on
14 * and replaces the part they disagree on with a single gap, so the reported
15 * shape still matches every string the code can build.
16 *
17 * @visibility root
18 */
19final class TextGeneralization
20{
21 /**
22 * @param Origin $origin The origin recorded on gaps this generalization introduces
23 */
24 public function __construct(public readonly Origin $origin)
25 {
26 }
27
28 /**
29 * The narrowest pattern that covers both inputs.
30 */
31 public function merge(TextPattern $left, TextPattern $right): TextPattern
32 {
33 if ($left->equals($right)) {
34 return $left;
35 }
36
37 $resolved = $this->mergeResolved($left, $right);
38 if ($resolved !== null) {
39 return $resolved;
40 }
41
42 $leftAtoms = $this->atoms($left);
43 $rightAtoms = $this->atoms($right);
44 $prefix = $this->commonPrefixLength($leftAtoms, $rightAtoms);
45 $remaining = min(count($leftAtoms), count($rightAtoms)) - $prefix;
46 $suffix = $this->commonSuffixLength($leftAtoms, $rightAtoms, $remaining);
47
48 $segments = array_merge(
49 $this->rebuild(array_slice($leftAtoms, 0, $prefix)),
50 [new TextHole($this->origin, $this->gapType($left, $right))],
51 $this->rebuild($suffix === 0 ? [] : array_slice($leftAtoms, -$suffix)),
52 );
53
54 return TextPattern::fromSegments($segments);
55 }
56
57 /**
58 * The narrowest pattern covering two fully resolved strings, or null when either has a gap.
59 *
60 * Statements are long and are merged often, so the common case of two
61 * resolved strings is answered by comparing the strings themselves rather
62 * than by walking them character by character.
63 */
64 public function mergeResolved(TextPattern $left, TextPattern $right): ?TextPattern
65 {
66 $leftText = $left->text();
67 $rightText = $right->text();
68 if ($leftText === null || $rightText === null) {
69 return null;
70 }
71
72 $prefix = $this->sharedPrefixLength($leftText, $rightText);
73 $limit = min(strlen($leftText), strlen($rightText)) - $prefix;
74 $suffix = min($limit, $this->sharedPrefixLength(strrev($leftText), strrev($rightText)));
75
76 return TextPattern::fromSegments([
77 new LiteralText(substr($leftText, 0, $prefix)),
78 new TextHole($this->origin, TypeShape::of(['string'])),
79 new LiteralText($suffix === 0 ? '' : substr($leftText, -$suffix)),
80 ]);
81 }
82
83 /**
84 * How many leading bytes two strings share.
85 */
86 public function sharedPrefixLength(string $left, string $right): int
87 {
88 return strspn($left ^ $right, "\0");
89 }
90
91 /**
92 * The narrowest pattern that covers every input.
93 *
94 * @param list<TextPattern> $patterns
95 */
96 public function mergeAll(array $patterns): TextPattern
97 {
98 $merged = array_shift($patterns);
99 if ($merged === null) {
100 return TextPattern::empty();
101 }
102
103 foreach ($patterns as $pattern) {
104 $merged = $this->merge($merged, $pattern);
105 }
106
107 return $merged;
108 }
109
110 /**
111 * The pattern split into single characters and whole gaps, so the two sides align.
112 *
113 * @return list<string|TextHole>
114 */
115 public function atoms(TextPattern $pattern): array
116 {
117 $atoms = [];
118 foreach ($pattern->segments as $segment) {
119 if ($segment instanceof TextHole) {
120 $atoms[] = $segment;
121 continue;
122 }
123 if (!$segment instanceof LiteralText) {
124 continue;
125 }
126 $length = strlen($segment->text);
127 for ($offset = 0; $offset < $length; $offset++) {
128 $atoms[] = $segment->text[$offset];
129 }
130 }
131
132 return $atoms;
133 }
134
135 /**
136 * How many leading atoms the two sides share.
137 *
138 * @param list<string|TextHole> $left
139 * @param list<string|TextHole> $right
140 */
141 public function commonPrefixLength(array $left, array $right): int
142 {
143 $limit = min(count($left), count($right));
144 $shared = 0;
145 while ($shared < $limit && $this->sameAtom($left[$shared], $right[$shared])) {
146 $shared++;
147 }
148
149 return $shared;
150 }
151
152 /**
153 * How many trailing atoms the two sides share, without reaching into the prefix.
154 *
155 * @param list<string|TextHole> $left
156 * @param list<string|TextHole> $right
157 * @param int $limit The atoms still available after the shared prefix
158 */
159 public function commonSuffixLength(array $left, array $right, int $limit): int
160 {
161 $leftLast = count($left) - 1;
162 $rightLast = count($right) - 1;
163 $shared = 0;
164 while (
165 $shared < $limit
166 && $this->sameAtom($left[$leftLast - $shared], $right[$rightLast - $shared])
167 ) {
168 $shared++;
169 }
170
171 return $shared;
172 }
173
174 /**
175 * Whether two atoms stand for the same thing.
176 *
177 * @param string|TextHole $left
178 * @param string|TextHole $right
179 */
180 public function sameAtom(string|TextHole $left, string|TextHole $right): bool
181 {
182 if ($left instanceof TextHole || $right instanceof TextHole) {
183 return $left instanceof TextHole
184 && $right instanceof TextHole
185 && $left->origin === $right->origin;
186 }
187
188 return $left === $right;
189 }
190
191 /**
192 * Segments rebuilt from atoms.
193 *
194 * @param list<string|TextHole> $atoms
195 * @return list<TextSegment>
196 */
197 public function rebuild(array $atoms): array
198 {
199 $segments = [];
200 foreach ($atoms as $atom) {
201 $segments[] = $atom instanceof TextHole ? $atom : new LiteralText($atom);
202 }
203
204 return $segments;
205 }
206
207 /**
208 * The type recorded on the introduced gap.
209 */
210 public function gapType(TextPattern $left, TextPattern $right): TypeShape
211 {
212 return $left->isExact() && $right->isExact() ? TypeShape::of(['string']) : TypeShape::unknown();
213 }
214}
215