packages/bison-parser/spec/Context/TreeDumper.php
1<?php
2
3declare(strict_types=1);
4
5namespace Spec\Context;
6
7use function array_map;
8
9use BisonParser\Ast\Declaration\Code;
10use BisonParser\Ast\Declaration\CodeProps;
11use BisonParser\Ast\Declaration\Declaration;
12use BisonParser\Ast\Declaration\Define;
13use BisonParser\Ast\Declaration\DefineForm;
14use BisonParser\Ast\Declaration\Expect;
15use BisonParser\Ast\Declaration\Flag;
16use BisonParser\Ast\Declaration\InitialAction;
17use BisonParser\Ast\Declaration\Option;
18use BisonParser\Ast\Declaration\Param;
19use BisonParser\Ast\Declaration\Prologue;
20use BisonParser\Ast\Declaration\Start;
21use BisonParser\Ast\Declaration\Symbols\Alias;
22use BisonParser\Ast\Declaration\Symbols\PrecedenceDeclaration;
23use BisonParser\Ast\Declaration\Symbols\SymbolDeclaration;
24use BisonParser\Ast\Declaration\Symbols\SymbolEntry;
25use BisonParser\Ast\Declaration\UnionDeclaration;
26use BisonParser\Ast\GrammarFile;
27use BisonParser\Ast\Line;
28use BisonParser\Ast\Rule\Action;
29use BisonParser\Ast\Rule\DprecItem;
30use BisonParser\Ast\Rule\EmptyItem;
31use BisonParser\Ast\Rule\ExpectItem;
32use BisonParser\Ast\Rule\MergeItem;
33use BisonParser\Ast\Rule\PrecItem;
34use BisonParser\Ast\Rule\Predicate;
35use BisonParser\Ast\Rule\RhsItem;
36use BisonParser\Ast\Rule\Rule;
37use BisonParser\Ast\Rule\SymbolItem;
38use BisonParser\Ast\Symbol;
39use BisonParser\Ast\SymbolKind;
40use BisonParser\Ast\Tag;
41
42use function implode;
43
44use LogicException;
45
46use function ord;
47use function sprintf;
48use function str_repeat;
49use function str_split;
50
51/**
52 * Writes a syntax tree as one line per node, so that a scenario can state the
53 * whole result of a parse in a docstring.
54 *
55 * Each line names the node class and its fields; children are indented by two
56 * spaces. The two grammar-file sections are separated by a `%%` line, and the
57 * epilogue follows a second one. Literal symbols and aliases are written in
58 * their canonical spelling followed by `spelled <source>` when the source
59 * spelled them differently. Positions are not shown.
60 */
61final class TreeDumper
62{
63 /**
64 * Renders a whole tree.
65 *
66 * @param GrammarFile $file The tree
67 *
68 * @return string One line per node, without a final newline
69 */
70 public function dump(GrammarFile $file): string
71 {
72 $lines = [];
73 foreach ($file->declarations as $declaration) {
74 $this->declaration($declaration, $lines);
75 }
76 $lines[] = '%%';
77 foreach ($file->grammar as $item) {
78 if ($item instanceof Rule) {
79 $this->rule($item, $lines);
80 } else {
81 $this->declaration($item, $lines);
82 }
83 }
84 if ($file->epilogue !== null) {
85 $lines[] = '%%';
86 $lines[] = 'Epilogue ' . $this->code($file->epilogue->code);
87 }
88
89 return implode("\n", $lines);
90 }
91
92 /**
93 * Appends the lines of a declaration and of its symbol entries.
94 *
95 * @param Declaration $declaration The declaration
96 * @param list<string> $lines The lines written so far
97 */
98 public function declaration(Declaration $declaration, array &$lines): void
99 {
100 $lines[] = $this->declarationLine($declaration);
101 if ($declaration instanceof SymbolDeclaration || $declaration instanceof PrecedenceDeclaration) {
102 foreach ($declaration->entries as $entry) {
103 $lines[] = $this->indent(1) . $this->entry($entry);
104 }
105 }
106 }
107
108 /**
109 * The line of a declaration: its class and its fields.
110 *
111 * @param Declaration $declaration The declaration
112 *
113 * @return string The line
114 *
115 * @throws LogicException When the declaration is of a class this dumper does not know
116 */
117 public function declarationLine(Declaration $declaration): string
118 {
119 if ($declaration instanceof Prologue) {
120 return 'Prologue ' . $this->code($declaration->code);
121 }
122 if ($declaration instanceof Code) {
123 return 'Code ' . ($declaration->qualifier === null ? '' : $declaration->qualifier . ' ') . $this->code($declaration->code);
124 }
125 if ($declaration instanceof Define) {
126 return $this->define($declaration);
127 }
128 if ($declaration instanceof Flag) {
129 return 'Flag ' . $declaration->name . $this->spelled('%' . $declaration->name, $declaration->raw);
130 }
131 if ($declaration instanceof Option) {
132 return 'Option ' . $declaration->name
133 . ($declaration->value === null ? '' : ' ' . $this->string($declaration->value))
134 . $this->spelled('%' . $declaration->name, $declaration->raw);
135 }
136 if ($declaration instanceof Expect) {
137 return 'Expect ' . ($declaration->reduceReduce ? 'reduce/reduce ' : '') . $declaration->count;
138 }
139 if ($declaration instanceof InitialAction) {
140 return 'InitialAction ' . $this->code($declaration->code);
141 }
142 if ($declaration instanceof Param) {
143 return 'Param ' . $declaration->kind->value . ' ' . implode(' ', array_map($this->code(...), $declaration->codes));
144 }
145 if ($declaration instanceof UnionDeclaration) {
146 return 'UnionDeclaration ' . ($declaration->name === null ? '' : $declaration->name . ' ') . $this->code($declaration->code);
147 }
148 if ($declaration instanceof Start) {
149 return 'Start ' . implode(' ', array_map($this->symbol(...), $declaration->symbols));
150 }
151 if ($declaration instanceof CodeProps) {
152 return 'CodeProps ' . ($declaration->printer ? 'printer' : 'destructor') . ' ' . $this->code($declaration->code)
153 . ' ' . implode(' ', array_map($this->target(...), $declaration->targets));
154 }
155 if ($declaration instanceof SymbolDeclaration) {
156 return 'SymbolDeclaration ' . $declaration->class->value;
157 }
158 if ($declaration instanceof PrecedenceDeclaration) {
159 return 'PrecedenceDeclaration ' . $declaration->associativity->value;
160 }
161 if ($declaration instanceof Line) {
162 return $this->line($declaration);
163 }
164
165 throw new LogicException('No rendering for ' . $declaration::class);
166 }
167
168 /**
169 * The line of a `%define`, quoting the value the way its form does.
170 *
171 * @param Define $define The declaration
172 *
173 * @return string The line
174 */
175 public function define(Define $define): string
176 {
177 if ($define->form === null) {
178 return 'Define ' . $define->variable;
179 }
180 $value = (string) $define->value;
181
182 return 'Define ' . $define->variable . ' = ' . match ($define->form) {
183 DefineForm::Keyword => $value,
184 DefineForm::String => $this->string($value),
185 DefineForm::Code => $this->code($value),
186 };
187 }
188
189 /**
190 * The line of a symbol entry: tag, symbol, number and alias.
191 *
192 * @param SymbolEntry $entry The entry
193 *
194 * @return string The line
195 */
196 public function entry(SymbolEntry $entry): string
197 {
198 $text = 'SymbolEntry';
199 if ($entry->tag !== null) {
200 $text .= ' <' . $entry->tag . '>';
201 }
202 $text .= ' ' . $this->symbol($entry->symbol);
203 if ($entry->number !== null) {
204 $text .= ' ' . $entry->number;
205 }
206 if ($entry->alias !== null) {
207 $text .= ' ' . $this->alias($entry->alias);
208 }
209
210 return $text;
211 }
212
213 /**
214 * A string alias, translatable or not, with its spelling when that differs.
215 *
216 * @param Alias $alias The alias
217 *
218 * @return string The rendering
219 */
220 public function alias(Alias $alias): string
221 {
222 $canonical = $alias->translatable ? '_(' . $this->string($alias->text) . ')' : $this->string($alias->text);
223
224 return $canonical . $this->spelled($canonical, $alias->spelling ?? $canonical);
225 }
226
227 /**
228 * Appends the lines of a rule, its alternatives and their items.
229 *
230 * @param Rule $rule The rule
231 * @param list<string> $lines The lines written so far
232 */
233 public function rule(Rule $rule, array &$lines): void
234 {
235 $lines[] = 'Rule ' . $this->symbol($rule->name) . $this->reference($rule->namedReference);
236 foreach ($rule->alternatives as $alternative) {
237 $lines[] = $this->indent(1) . 'Alternative';
238 foreach ($alternative->items as $item) {
239 $lines[] = $this->indent(2) . $this->item($item);
240 }
241 }
242 }
243
244 /**
245 * The line of a right-hand side item.
246 *
247 * @param RhsItem $item The item
248 *
249 * @return string The line
250 *
251 * @throws LogicException When the item is of a class this dumper does not know
252 */
253 public function item(RhsItem $item): string
254 {
255 if ($item instanceof SymbolItem) {
256 return 'SymbolItem ' . $this->symbol($item->symbol) . $this->reference($item->namedReference);
257 }
258 if ($item instanceof Action) {
259 return 'Action ' . ($item->tag === null ? '' : '<' . $item->tag . '> ') . $this->code($item->code) . $this->reference($item->namedReference);
260 }
261 if ($item instanceof Predicate) {
262 return 'Predicate ' . $this->code($item->code);
263 }
264 if ($item instanceof EmptyItem) {
265 return 'EmptyItem';
266 }
267 if ($item instanceof PrecItem) {
268 return 'PrecItem ' . $this->symbol($item->symbol);
269 }
270 if ($item instanceof DprecItem) {
271 return 'DprecItem ' . $item->value;
272 }
273 if ($item instanceof MergeItem) {
274 return 'MergeItem <' . $item->tag . '>';
275 }
276 if ($item instanceof ExpectItem) {
277 return 'ExpectItem ' . ($item->reduceReduce ? 'reduce/reduce ' : '') . $item->count;
278 }
279 if ($item instanceof Line) {
280 return $this->line($item);
281 }
282
283 throw new LogicException('No rendering for ' . $item::class);
284 }
285
286 /**
287 * The line of a `#line` directive.
288 *
289 * @param Line $line The directive
290 *
291 * @return string The line
292 */
293 public function line(Line $line): string
294 {
295 return 'Line ' . $line->line . ($line->file === null ? '' : ' ' . $this->string($line->file));
296 }
297
298 /**
299 * A symbol in its canonical spelling, with the source spelling when that differs.
300 *
301 * @param Symbol $symbol The symbol
302 *
303 * @return string The rendering
304 */
305 public function symbol(Symbol $symbol): string
306 {
307 $canonical = match ($symbol->kind) {
308 SymbolKind::Identifier => $symbol->value,
309 SymbolKind::CharLiteral => "'" . $this->escape($symbol->value, "'") . "'",
310 SymbolKind::String => $this->string($symbol->value),
311 };
312
313 return $canonical . $this->spelled($canonical, $symbol->spelling ?? $canonical);
314 }
315
316 /**
317 * A target of `%destructor` or `%printer`: a symbol or a tag.
318 *
319 * @param Symbol|Tag $target The target
320 *
321 * @return string The rendering
322 */
323 public function target(Symbol|Tag $target): string
324 {
325 return $target instanceof Tag ? '<' . $target->name . '>' : $this->symbol($target);
326 }
327
328 /**
329 * A bracketed named reference, or nothing.
330 *
331 * @param string|null $name The name, if any
332 *
333 * @return string The rendering, starting with a space when present
334 */
335 public function reference(?string $name): string
336 {
337 return $name === null ? '' : ' [' . $name . ']';
338 }
339
340 /**
341 * The `spelled` suffix, when the source spelling differs from the canonical one.
342 *
343 * @param string $canonical The canonical spelling
344 * @param string $spelling The spelling in the source
345 *
346 * @return string The suffix, or nothing
347 */
348 public function spelled(string $canonical, string $spelling): string
349 {
350 return $spelling === $canonical ? '' : ' spelled ' . $spelling;
351 }
352
353 /**
354 * A string in double quotes, escaped.
355 *
356 * @param string $text The bytes
357 *
358 * @return string The rendering
359 */
360 public function string(string $text): string
361 {
362 return '"' . $this->escape($text, '"') . '"';
363 }
364
365 /**
366 * Code in braces, escaped so that it stays on one line.
367 *
368 * @param string $code The code
369 *
370 * @return string The rendering
371 */
372 public function code(string $code): string
373 {
374 return '{' . $this->escape($code, '') . '}';
375 }
376
377 /**
378 * Escapes backslashes, the quote, and control characters.
379 *
380 * @param string $bytes The bytes
381 * @param string $quote The quote to escape, or an empty string for none
382 *
383 * @return string The escaped bytes
384 */
385 public function escape(string $bytes, string $quote): string
386 {
387 if ($bytes === '') {
388 return '';
389 }
390 $escaped = '';
391 foreach (str_split($bytes) as $byte) {
392 $escaped .= match (true) {
393 $byte === '\\' => '\\\\',
394 $byte === "\n" => '\\n',
395 $byte === "\r" => '\\r',
396 $byte === "\t" => '\\t',
397 $byte === $quote => '\\' . $quote,
398 ord($byte) < 0x20 || ord($byte) === 0x7F => sprintf('\\x%02x', ord($byte)),
399 default => $byte,
400 };
401 }
402
403 return $escaped;
404 }
405
406 /**
407 * The indentation of a depth.
408 *
409 * @param int $depth Two spaces per level
410 *
411 * @return string The spaces
412 */
413 public function indent(int $depth): string
414 {
415 return str_repeat(' ', $depth);
416 }
417}
418