Debian Codegraph @

Tools/cases_generator/parsing.py

raw
1 """Parser for bytecodes.inst."""
2
3 from dataclasses import dataclass, field
4 from typing import NamedTuple, Callable, TypeVar, Literal, cast, Iterator
5 from io import StringIO
6
7 import lexer as lx
8 from plexer import PLexer
9 from cwriter import CWriter
10
11
12 P = TypeVar("P", bound="Parser")
13 N = TypeVar("N", bound="Node")
14
15
16 def contextual(func: Callable[[P], N | None]) -> Callable[[P], N | None]:
17 # Decorator to wrap grammar methods.
18 # Resets position if `func` returns None.
19 def contextual_wrapper(self: P) -> N | None:
20 begin = self.getpos()
21 res = func(self)
22 if res is None:
23 self.setpos(begin)
24 return None
25 end = self.getpos()
26 res.context = Context(begin, end, self)
27 return res
28
29 return contextual_wrapper
30
31
32 class Context(NamedTuple):
33 begin: int
34 end: int
35 owner: PLexer
36
37 def __repr__(self) -> str:
38 return f"<{self.owner.filename}: {self.begin}-{self.end}>"
39
40
41 @dataclass
42 class Node:
43 context: Context | None = field(init=False, compare=False, default=None)
44
45 @property
46 def text(self) -> str:
47 return self.to_text()
48
49 def to_text(self, dedent: int = 0) -> str:
50 context = self.context
51 if not context:
52 return ""
53 return lx.to_text(self.tokens, dedent)
54
55 @property
56 def tokens(self) -> list[lx.Token]:
57 context = self.context
58 if not context:
59 return []
60 tokens = context.owner.tokens
61 begin = context.begin
62 end = context.end
63 return tokens[begin:end]
64
65 @property
66 def first_token(self) -> lx.Token:
67 context = self.context
68 assert context is not None
69 return context.owner.tokens[context.begin]
70
71 # Statements
72
73 Visitor = Callable[["Stmt"], None]
74
75 class Stmt:
76
77 def __repr__(self) -> str:
78 io = StringIO()
79 out = CWriter(io, 0, False)
80 self.print(out)
81 return io.getvalue()
82
83 def print(self, out:CWriter) -> None:
84 raise NotImplementedError
85
86 def accept(self, visitor: Visitor) -> None:
87 raise NotImplementedError
88
89 def tokens(self) -> Iterator[lx.Token]:
90 raise NotImplementedError
91
92
93 @dataclass
94 class IfStmt(Stmt):
95 if_: lx.Token
96 condition: list[lx.Token]
97 body: Stmt
98 else_: lx.Token | None
99 else_body: Stmt | None
100
101 def print(self, out:CWriter) -> None:
102 out.emit(self.if_)
103 for tkn in self.condition:
104 out.emit(tkn)
105 self.body.print(out)
106 if self.else_ is not None:
107 out.emit(self.else_)
108 self.body.print(out)
109 if self.else_body is not None:
110 self.else_body.print(out)
111
112 def accept(self, visitor: Visitor) -> None:
113 visitor(self)
114 self.body.accept(visitor)
115 if self.else_body is not None:
116 self.else_body.accept(visitor)
117
118 def tokens(self) -> Iterator[lx.Token]:
119 yield self.if_
120 yield from self.condition
121 yield from self.body.tokens()
122 if self.else_ is not None:
123 yield self.else_
124 if self.else_body is not None:
125 yield from self.else_body.tokens()
126
127
128 @dataclass
129 class ForStmt(Stmt):
130 for_: lx.Token
131 header: list[lx.Token]
132 body: Stmt
133
134 def print(self, out:CWriter) -> None:
135 out.emit(self.for_)
136 for tkn in self.header:
137 out.emit(tkn)
138 self.body.print(out)
139
140 def accept(self, visitor: Visitor) -> None:
141 visitor(self)
142 self.body.accept(visitor)
143
144 def tokens(self) -> Iterator[lx.Token]:
145 yield self.for_
146 yield from self.header
147 yield from self.body.tokens()
148
149
150 @dataclass
151 class WhileStmt(Stmt):
152 while_: lx.Token
153 condition: list[lx.Token]
154 body: Stmt
155
156 def print(self, out:CWriter) -> None:
157 out.emit(self.while_)
158 for tkn in self.condition:
159 out.emit(tkn)
160 self.body.print(out)
161
162 def accept(self, visitor: Visitor) -> None:
163 visitor(self)
164 self.body.accept(visitor)
165
166 def tokens(self) -> Iterator[lx.Token]:
167 yield self.while_
168 yield from self.condition
169 yield from self.body.tokens()
170
171
172 @dataclass
173 class MacroIfStmt(Stmt):
174 condition: lx.Token
175 body: list[Stmt]
176 else_: lx.Token | None
177 else_body: list[Stmt] | None
178 endif: lx.Token
179
180 def print(self, out:CWriter) -> None:
181 out.emit(self.condition)
182 for stmt in self.body:
183 stmt.print(out)
184 if self.else_body is not None:
185 out.emit("#else\n")
186 for stmt in self.else_body:
187 stmt.print(out)
188
189 def accept(self, visitor: Visitor) -> None:
190 visitor(self)
191 for stmt in self.body:
192 stmt.accept(visitor)
193 if self.else_body is not None:
194 for stmt in self.else_body:
195 stmt.accept(visitor)
196
197 def tokens(self) -> Iterator[lx.Token]:
198 yield self.condition
199 for stmt in self.body:
200 yield from stmt.tokens()
201 if self.else_body is not None:
202 for stmt in self.else_body:
203 yield from stmt.tokens()
204
205
206 @dataclass
207 class BlockStmt(Stmt):
208 open: lx.Token
209 body: list[Stmt]
210 close: lx.Token
211
212 def print(self, out:CWriter) -> None:
213 out.emit(self.open)
214 for stmt in self.body:
215 stmt.print(out)
216 out.start_line()
217 out.emit(self.close)
218
219 def accept(self, visitor: Visitor) -> None:
220 visitor(self)
221 for stmt in self.body:
222 stmt.accept(visitor)
223
224 def tokens(self) -> Iterator[lx.Token]:
225 yield self.open
226 for stmt in self.body:
227 yield from stmt.tokens()
228 yield self.close
229
230
231 @dataclass
232 class SimpleStmt(Stmt):
233 contents: list[lx.Token]
234
235 def print(self, out:CWriter) -> None:
236 for tkn in self.contents:
237 out.emit(tkn)
238
239 def tokens(self) -> Iterator[lx.Token]:
240 yield from self.contents
241
242 def accept(self, visitor: Visitor) -> None:
243 visitor(self)
244
245 __hash__ = object.__hash__
246
247 @dataclass
248 class StackEffect(Node):
249 name: str = field(compare=False) # __eq__ only uses type, cond, size
250 type: str = "" # Optional `:type`
251 size: str = "" # Optional `[size]`
252 # Note: size cannot be combined with type or cond
253
254 def __repr__(self) -> str:
255 items = [self.name, self.type, self.size]
256 while items and items[-1] == "":
257 del items[-1]
258 return f"StackEffect({', '.join(repr(item) for item in items)})"
259
260
261 @dataclass
262 class Expression(Node):
263 size: str
264
265
266 @dataclass
267 class CacheEffect(Node):
268 name: str
269 size: int
270
271
272 @dataclass
273 class OpName(Node):
274 name: str
275
276
277 InputEffect = StackEffect | CacheEffect
278 OutputEffect = StackEffect
279 UOp = OpName | CacheEffect
280
281
282 @dataclass
283 class InstHeader(Node):
284 annotations: list[str]
285 kind: Literal["inst", "op"]
286 name: str
287 inputs: list[InputEffect]
288 outputs: list[OutputEffect]
289
290
291 @dataclass
292 class InstDef(Node):
293 annotations: list[str]
294 kind: Literal["inst", "op"]
295 name: str
296 inputs: list[InputEffect]
297 outputs: list[OutputEffect]
298 block: BlockStmt
299
300
301 @dataclass
302 class Macro(Node):
303 name: str
304 uops: list[UOp]
305
306
307 @dataclass
308 class Family(Node):
309 name: str
310 size: str # Variable giving the cache size in code units
311 members: list[str]
312
313
314 @dataclass
315 class Pseudo(Node):
316 name: str
317 inputs: list[InputEffect]
318 outputs: list[OutputEffect]
319 flags: list[str] # instr flags to set on the pseudo instruction
320 targets: list[str] # opcodes this can be replaced by
321 as_sequence: bool
322
323 @dataclass
324 class LabelDef(Node):
325 name: str
326 spilled: bool
327 block: BlockStmt
328
329
330 AstNode = InstDef | Macro | Pseudo | Family | LabelDef
331
332
333 class Parser(PLexer):
334 @contextual
335 def definition(self) -> AstNode | None:
336 if macro := self.macro_def():
337 return macro
338 if family := self.family_def():
339 return family
340 if pseudo := self.pseudo_def():
341 return pseudo
342 if inst := self.inst_def():
343 return inst
344 if label := self.label_def():
345 return label
346 return None
347
348 @contextual
349 def label_def(self) -> LabelDef | None:
350 spilled = False
351 if self.expect(lx.SPILLED):
352 spilled = True
353 if self.expect(lx.LABEL):
354 if self.expect(lx.LPAREN):
355 if tkn := self.expect(lx.IDENTIFIER):
356 if self.expect(lx.RPAREN):
357 block = self.block()
358 return LabelDef(tkn.text, spilled, block)
359 return None
360
361 @contextual
362 def inst_def(self) -> InstDef | None:
363 if hdr := self.inst_header():
364 block = self.block()
365 return InstDef(
366 hdr.annotations,
367 hdr.kind,
368 hdr.name,
369 hdr.inputs,
370 hdr.outputs,
371 block,
372 )
373 return None
374
375 @contextual
376 def inst_header(self) -> InstHeader | None:
377 # annotation* inst(NAME, (inputs -- outputs))
378 # | annotation* op(NAME, (inputs -- outputs))
379 annotations = []
380 while anno := self.expect(lx.ANNOTATION):
381 if anno.text == "replicate":
382 self.require(lx.LPAREN)
383 times = self.require(lx.NUMBER)
384 self.require(lx.RPAREN)
385 annotations.append(f"replicate({times.text})")
386 else:
387 annotations.append(anno.text)
388 tkn = self.expect(lx.INST)
389 if not tkn:
390 tkn = self.expect(lx.OP)
391 if tkn:
392 kind = cast(Literal["inst", "op"], tkn.text)
393 if self.expect(lx.LPAREN) and (tkn := self.expect(lx.IDENTIFIER)):
394 name = tkn.text
395 if self.expect(lx.COMMA):
396 inp, outp = self.io_effect()
397 if self.expect(lx.RPAREN):
398 if (tkn := self.peek()) and tkn.kind == lx.LBRACE:
399 return InstHeader(annotations, kind, name, inp, outp)
400 return None
401
402 def io_effect(self) -> tuple[list[InputEffect], list[OutputEffect]]:
403 # '(' [inputs] '--' [outputs] ')'
404 if self.expect(lx.LPAREN):
405 inputs = self.inputs() or []
406 if self.expect(lx.MINUSMINUS):
407 outputs = self.outputs() or []
408 if self.expect(lx.RPAREN):
409 return inputs, outputs
410 raise self.make_syntax_error("Expected stack effect")
411
412 def inputs(self) -> list[InputEffect] | None:
413 # input (',' input)*
414 here = self.getpos()
415 if inp := self.input():
416 inp = cast(InputEffect, inp)
417 near = self.getpos()
418 if self.expect(lx.COMMA):
419 if rest := self.inputs():
420 return [inp] + rest
421 self.setpos(near)
422 return [inp]
423 self.setpos(here)
424 return None
425
426 @contextual
427 def input(self) -> InputEffect | None:
428 return self.cache_effect() or self.stack_effect()
429
430 def outputs(self) -> list[OutputEffect] | None:
431 # output (, output)*
432 here = self.getpos()
433 if outp := self.output():
434 near = self.getpos()
435 if self.expect(lx.COMMA):
436 if rest := self.outputs():
437 return [outp] + rest
438 self.setpos(near)
439 return [outp]
440 self.setpos(here)
441 return None
442
443 @contextual
444 def output(self) -> OutputEffect | None:
445 return self.stack_effect()
446
447 @contextual
448 def cache_effect(self) -> CacheEffect | None:
449 # IDENTIFIER '/' NUMBER
450 if tkn := self.expect(lx.IDENTIFIER):
451 if self.expect(lx.DIVIDE):
452 num = self.require(lx.NUMBER).text
453 try:
454 size = int(num)
455 except ValueError:
456 raise self.make_syntax_error(f"Expected integer, got {num!r}")
457 else:
458 return CacheEffect(tkn.text, size)
459 return None
460
461 @contextual
462 def stack_effect(self) -> StackEffect | None:
463 # IDENTIFIER [':' IDENTIFIER [TIMES]] ['if' '(' expression ')']
464 # | IDENTIFIER '[' expression ']'
465 if tkn := self.expect(lx.IDENTIFIER):
466 type_text = ""
467 if self.expect(lx.COLON):
468 type_text = self.require(lx.IDENTIFIER).text.strip()
469 if self.expect(lx.TIMES):
470 type_text += " *"
471 size_text = ""
472 if self.expect(lx.LBRACKET):
473 if type_text:
474 raise self.make_syntax_error("Unexpected [")
475 if not (size := self.expression()):
476 raise self.make_syntax_error("Expected expression")
477 self.require(lx.RBRACKET)
478 size_text = size.text.strip()
479 return StackEffect(tkn.text, type_text, size_text)
480 return None
481
482 @contextual
483 def expression(self) -> Expression | None:
484 tokens: list[lx.Token] = []
485 level = 1
486 while tkn := self.peek():
487 if tkn.kind in (lx.LBRACKET, lx.LPAREN):
488 level += 1
489 elif tkn.kind in (lx.RBRACKET, lx.RPAREN):
490 level -= 1
491 if level == 0:
492 break
493 tokens.append(tkn)
494 self.next()
495 if not tokens:
496 return None
497 return Expression(lx.to_text(tokens).strip())
498
499 # def ops(self) -> list[OpName] | None:
500 # if op := self.op():
501 # ops = [op]
502 # while self.expect(lx.PLUS):
503 # if op := self.op():
504 # ops.append(op)
505 # return ops
506
507 @contextual
508 def op(self) -> OpName | None:
509 if tkn := self.expect(lx.IDENTIFIER):
510 return OpName(tkn.text)
511 return None
512
513 @contextual
514 def macro_def(self) -> Macro | None:
515 if tkn := self.expect(lx.MACRO):
516 if self.expect(lx.LPAREN):
517 if tkn := self.expect(lx.IDENTIFIER):
518 if self.expect(lx.RPAREN):
519 if self.expect(lx.EQUALS):
520 if uops := self.uops():
521 self.require(lx.SEMI)
522 res = Macro(tkn.text, uops)
523 return res
524 return None
525
526 def uops(self) -> list[UOp] | None:
527 if uop := self.uop():
528 uop = cast(UOp, uop)
529 uops = [uop]
530 while self.expect(lx.PLUS):
531 if uop := self.uop():
532 uop = cast(UOp, uop)
533 uops.append(uop)
534 else:
535 raise self.make_syntax_error("Expected op name or cache effect")
536 return uops
537 return None
538
539 @contextual
540 def uop(self) -> UOp | None:
541 if tkn := self.expect(lx.IDENTIFIER):
542 if self.expect(lx.DIVIDE):
543 sign = 1
544 if negate := self.expect(lx.MINUS):
545 sign = -1
546 if num := self.expect(lx.NUMBER):
547 try:
548 size = sign * int(num.text)
549 except ValueError:
550 raise self.make_syntax_error(
551 f"Expected integer, got {num.text!r}"
552 )
553 else:
554 return CacheEffect(tkn.text, size)
555 raise self.make_syntax_error("Expected integer")
556 else:
557 return OpName(tkn.text)
558 return None
559
560 @contextual
561 def family_def(self) -> Family | None:
562 if (tkn := self.expect(lx.IDENTIFIER)) and tkn.text == "family":
563 size = None
564 if self.expect(lx.LPAREN):
565 if tkn := self.expect(lx.IDENTIFIER):
566 if self.expect(lx.COMMA):
567 if not (size := self.expect(lx.IDENTIFIER)):
568 if not (size := self.expect(lx.NUMBER)):
569 raise self.make_syntax_error(
570 "Expected identifier or number"
571 )
572 if self.expect(lx.RPAREN):
573 if self.expect(lx.EQUALS):
574 if not self.expect(lx.LBRACE):
575 raise self.make_syntax_error("Expected {")
576 if members := self.members():
577 if self.expect(lx.RBRACE) and self.expect(lx.SEMI):
578 return Family(
579 tkn.text, size.text if size else "", members
580 )
581 return None
582
583 def flags(self) -> list[str]:
584 here = self.getpos()
585 if self.expect(lx.LPAREN):
586 if tkn := self.expect(lx.IDENTIFIER):
587 flags = [tkn.text]
588 while self.expect(lx.COMMA):
589 if tkn := self.expect(lx.IDENTIFIER):
590 flags.append(tkn.text)
591 else:
592 break
593 if not self.expect(lx.RPAREN):
594 raise self.make_syntax_error("Expected comma or right paren")
595 return flags
596 self.setpos(here)
597 return []
598
599 @contextual
600 def pseudo_def(self) -> Pseudo | None:
601 if (tkn := self.expect(lx.IDENTIFIER)) and tkn.text == "pseudo":
602 size = None
603 if self.expect(lx.LPAREN):
604 if tkn := self.expect(lx.IDENTIFIER):
605 if self.expect(lx.COMMA):
606 inp, outp = self.io_effect()
607 if self.expect(lx.COMMA):
608 flags = self.flags()
609 else:
610 flags = []
611 if self.expect(lx.RPAREN):
612 if self.expect(lx.EQUALS):
613 if self.expect(lx.LBRACE):
614 as_sequence = False
615 closing = lx.RBRACE
616 elif self.expect(lx.LBRACKET):
617 as_sequence = True
618 closing = lx.RBRACKET
619 else:
620 raise self.make_syntax_error("Expected { or [")
621 if members := self.members(allow_sequence=True):
622 if self.expect(closing) and self.expect(lx.SEMI):
623 return Pseudo(
624 tkn.text, inp, outp, flags, members, as_sequence
625 )
626 return None
627
628 def members(self, allow_sequence : bool=False) -> list[str] | None:
629 here = self.getpos()
630 if tkn := self.expect(lx.IDENTIFIER):
631 members = [tkn.text]
632 while self.expect(lx.COMMA):
633 if tkn := self.expect(lx.IDENTIFIER):
634 members.append(tkn.text)
635 else:
636 break
637 peek = self.peek()
638 kinds = [lx.RBRACE, lx.RBRACKET] if allow_sequence else [lx.RBRACE]
639 if not peek or peek.kind not in kinds:
640 raise self.make_syntax_error(
641 f"Expected comma or right paren{'/bracket' if allow_sequence else ''}")
642 return members
643 self.setpos(here)
644 return None
645
646 def block(self) -> BlockStmt:
647 open = self.require(lx.LBRACE)
648 stmts: list[Stmt] = []
649 while not (close := self.expect(lx.RBRACE)):
650 stmts.append(self.stmt())
651 return BlockStmt(open, stmts, close)
652
653 def stmt(self) -> Stmt:
654 if tkn := self.expect(lx.IF):
655 return self.if_stmt(tkn)
656 elif self.expect(lx.LBRACE):
657 self.backup()
658 return self.block()
659 elif tkn := self.expect(lx.FOR):
660 return self.for_stmt(tkn)
661 elif tkn := self.expect(lx.WHILE):
662 return self.while_stmt(tkn)
663 elif tkn := self.expect(lx.CMACRO_IF):
664 return self.macro_if(tkn)
665 elif tkn := self.expect(lx.CMACRO_ELSE):
666 msg = "Unexpected #else"
667 raise self.make_syntax_error(msg)
668 elif tkn := self.expect(lx.CMACRO_ENDIF):
669 msg = "Unexpected #endif"
670 raise self.make_syntax_error(msg)
671 elif tkn := self.expect(lx.CMACRO_OTHER):
672 return SimpleStmt([tkn])
673 elif tkn := self.expect(lx.SWITCH):
674 msg = "switch statements are not supported due to their complex flow control. Sorry."
675 raise self.make_syntax_error(msg)
676 tokens = self.consume_to(lx.SEMI)
677 return SimpleStmt(tokens)
678
679 def if_stmt(self, if_: lx.Token) -> IfStmt:
680 lparen = self.require(lx.LPAREN)
681 condition = [lparen] + self.consume_to(lx.RPAREN)
682 body = self.block()
683 else_body: Stmt | None = None
684 else_: lx.Token | None = None
685 if else_ := self.expect(lx.ELSE):
686 if inner := self.expect(lx.IF):
687 else_body = self.if_stmt(inner)
688 else:
689 else_body = self.block()
690 return IfStmt(if_, condition, body, else_, else_body)
691
692 def macro_if(self, cond: lx.Token) -> MacroIfStmt:
693 else_ = None
694 body: list[Stmt] = []
695 else_body: list[Stmt] | None = None
696 part = body
697 while True:
698 if tkn := self.expect(lx.CMACRO_ENDIF):
699 return MacroIfStmt(cond, body, else_, else_body, tkn)
700 elif tkn := self.expect(lx.CMACRO_ELSE):
701 if part is else_body:
702 raise self.make_syntax_error("Multiple #else")
703 else_ = tkn
704 else_body = []
705 part = else_body
706 else:
707 part.append(self.stmt())
708
709 def for_stmt(self, for_: lx.Token) -> ForStmt:
710 lparen = self.require(lx.LPAREN)
711 header = [lparen] + self.consume_to(lx.RPAREN)
712 body = self.block()
713 return ForStmt(for_, header, body)
714
715 def while_stmt(self, while_: lx.Token) -> WhileStmt:
716 lparen = self.require(lx.LPAREN)
717 cond = [lparen] + self.consume_to(lx.RPAREN)
718 body = self.block()
719 return WhileStmt(while_, cond, body)
720
721
722 if __name__ == "__main__":
723 import sys
724 import pprint
725
726 if sys.argv[1:]:
727 filename = sys.argv[1]
728 if filename == "-c" and sys.argv[2:]:
729 src = sys.argv[2]
730 filename = "<string>"
731 else:
732 with open(filename, "r") as f:
733 src = f.read()
734 srclines = src.splitlines()
735 begin = srclines.index("// BEGIN BYTECODES //")
736 end = srclines.index("// END BYTECODES //")
737 src = "\n".join(srclines[begin + 1 : end])
738 else:
739 filename = "<default>"
740 src = "if (x) { x.foo; // comment\n}"
741 parser = Parser(src, filename)
742 while node := parser.definition():
743 pprint.pprint(node)