Debian Codegraph @

Tools/cases_generator/generators_common.py

raw
1 from pathlib import Path
2
3 from analyzer import (
4 Instruction,
5 Properties,
6 StackItem,
7 analysis_error,
8 Label,
9 CodeSection,
10 )
11 from cwriter import CWriter
12 from typing import Callable, TextIO, Iterator, Iterable
13 from lexer import Token
14 from stack import Storage, StackError
15 from parser import Stmt, SimpleStmt, BlockStmt, IfStmt, ForStmt, WhileStmt, MacroIfStmt
16 from stack import PRINT_STACKS
17 DEBUG = False
18
19 class TokenIterator:
20
21 look_ahead: Token | None
22 iterator: Iterator[Token]
23
24 def __init__(self, tkns: Iterable[Token]):
25 self.iterator = iter(tkns)
26 self.look_ahead = None
27
28 def __iter__(self) -> "TokenIterator":
29 return self
30
31 def __next__(self) -> Token:
32 if self.look_ahead is None:
33 return next(self.iterator)
34 else:
35 res = self.look_ahead
36 self.look_ahead = None
37 return res
38
39 def peek(self) -> Token | None:
40 if self.look_ahead is None:
41 for tkn in self.iterator:
42 self.look_ahead = tkn
43 break
44 return self.look_ahead
45
46 ROOT = Path(__file__).parent.parent.parent.resolve()
47 DEFAULT_INPUT = (ROOT / "Python/bytecodes.c").as_posix()
48
49
50 def root_relative_path(filename: str) -> str:
51 try:
52 return Path(filename).resolve().relative_to(ROOT).as_posix()
53 except ValueError:
54 # Not relative to root, just return original path.
55 return filename
56
57
58 def type_and_null(var: StackItem) -> tuple[str, str]:
59 if var.type:
60 return var.type, "NULL"
61 elif var.is_array():
62 return "_PyStackRef *", "NULL"
63 else:
64 return "_PyStackRef", "PyStackRef_NULL"
65
66
67 def write_header(
68 generator: str, sources: list[str], outfile: TextIO, comment: str = "//"
69 ) -> None:
70 outfile.write(
71 f"""{comment} This file is generated by {root_relative_path(generator)}
72 {comment} from:
73 {comment} {", ".join(root_relative_path(src) for src in sources)}
74 {comment} Do not edit!
75 """
76 )
77
78
79 def emit_to(out: CWriter, tkn_iter: TokenIterator, end: str) -> Token:
80 parens = 0
81 for tkn in tkn_iter:
82 if tkn.kind == end and parens == 0:
83 return tkn
84 if tkn.kind == "LPAREN":
85 parens += 1
86 if tkn.kind == "RPAREN":
87 parens -= 1
88 out.emit(tkn)
89 raise analysis_error(f"Expecting {end}. Reached end of file", tkn)
90
91
92 ReplacementFunctionType = Callable[
93 [Token, TokenIterator, CodeSection, Storage, Instruction | None], bool
94 ]
95
96 def always_true(tkn: Token | None) -> bool:
97 if tkn is None:
98 return False
99 return tkn.text in {"true", "1"}
100
101 NON_ESCAPING_DEALLOCS = {
102 "_PyFloat_ExactDealloc",
103 "_PyLong_ExactDealloc",
104 "_PyUnicode_ExactDealloc",
105 }
106
107 class Emitter:
108 out: CWriter
109 labels: dict[str, Label]
110 _replacers: dict[str, ReplacementFunctionType]
111
112 def __init__(self, out: CWriter, labels: dict[str, Label]):
113 self._replacers = {
114 "EXIT_IF": self.exit_if,
115 "DEOPT_IF": self.deopt_if,
116 "ERROR_IF": self.error_if,
117 "ERROR_NO_POP": self.error_no_pop,
118 "DECREF_INPUTS": self.decref_inputs,
119 "DEAD": self.kill,
120 "INPUTS_DEAD": self.kill_inputs,
121 "SYNC_SP": self.sync_sp,
122 "SAVE_STACK": self.save_stack,
123 "RELOAD_STACK": self.reload_stack,
124 "PyStackRef_CLOSE_SPECIALIZED": self.stackref_close_specialized,
125 "PyStackRef_AsPyObjectSteal": self.stackref_steal,
126 "DISPATCH": self.dispatch,
127 "INSTRUCTION_SIZE": self.instruction_size,
128 "stack_pointer": self.stack_pointer,
129 }
130 self.out = out
131 self.labels = labels
132
133 def dispatch(
134 self,
135 tkn: Token,
136 tkn_iter: TokenIterator,
137 uop: CodeSection,
138 storage: Storage,
139 inst: Instruction | None,
140 ) -> bool:
141 if storage.spilled:
142 raise analysis_error("stack_pointer needs reloading before dispatch", tkn)
143 self.emit(tkn)
144 return False
145
146 def deopt_if(
147 self,
148 tkn: Token,
149 tkn_iter: TokenIterator,
150 uop: CodeSection,
151 storage: Storage,
152 inst: Instruction | None,
153 ) -> bool:
154 self.out.start_line()
155 self.out.emit("if (")
156 lparen = next(tkn_iter)
157 assert lparen.kind == "LPAREN"
158 first_tkn = tkn_iter.peek()
159 emit_to(self.out, tkn_iter, "RPAREN")
160 self.emit(") {\n")
161 next(tkn_iter) # Semi colon
162 assert inst is not None
163 assert inst.family is not None
164 family_name = inst.family.name
165 self.emit(f"UPDATE_MISS_STATS({family_name});\n")
166 self.emit(f"assert(_PyOpcode_Deopt[opcode] == ({family_name}));\n")
167 self.emit(f"JUMP_TO_PREDICTED({family_name});\n")
168 self.emit("}\n")
169 return not always_true(first_tkn)
170
171 exit_if = deopt_if
172
173 def goto_error(self, offset: int, storage: Storage) -> str:
174 if offset > 0:
175 return f"JUMP_TO_LABEL(pop_{offset}_error);"
176 if offset < 0:
177 storage.copy().flush(self.out)
178 return f"JUMP_TO_LABEL(error);"
179
180 def error_if(
181 self,
182 tkn: Token,
183 tkn_iter: TokenIterator,
184 uop: CodeSection,
185 storage: Storage,
186 inst: Instruction | None,
187 ) -> bool:
188 lparen = next(tkn_iter)
189 assert lparen.kind == "LPAREN"
190 first_tkn = tkn_iter.peek()
191 unconditional = always_true(first_tkn)
192 if unconditional:
193 next(tkn_iter)
194 next(tkn_iter) # RPAREN
195 self.out.start_line()
196 else:
197 self.out.emit_at("if ", tkn)
198 self.emit(lparen)
199 emit_to(self.out, tkn_iter, "RPAREN")
200 self.out.emit(") {\n")
201 next(tkn_iter) # Semi colon
202 storage.clear_inputs("at ERROR_IF")
203
204 c_offset = storage.stack.sp_offset()
205 try:
206 offset = int(c_offset)
207 except ValueError:
208 offset = -1
209 self.out.emit(self.goto_error(offset, storage))
210 self.out.emit("\n")
211 if not unconditional:
212 self.out.emit("}\n")
213 return not unconditional
214
215 def error_no_pop(
216 self,
217 tkn: Token,
218 tkn_iter: TokenIterator,
219 uop: CodeSection,
220 storage: Storage,
221 inst: Instruction | None,
222 ) -> bool:
223 next(tkn_iter) # LPAREN
224 next(tkn_iter) # RPAREN
225 next(tkn_iter) # Semi colon
226 self.out.emit_at(self.goto_error(0, storage), tkn)
227 return False
228
229 def decref_inputs(
230 self,
231 tkn: Token,
232 tkn_iter: TokenIterator,
233 uop: CodeSection,
234 storage: Storage,
235 inst: Instruction | None,
236 ) -> bool:
237 next(tkn_iter)
238 next(tkn_iter)
239 next(tkn_iter)
240 self._print_storage("DECREF_INPUTS", storage)
241 try:
242 storage.close_inputs(self.out)
243 except StackError as ex:
244 raise analysis_error(ex.args[0], tkn)
245 except Exception as ex:
246 ex.args = (ex.args[0] + str(tkn),)
247 raise
248 return True
249
250 def kill_inputs(
251 self,
252 tkn: Token,
253 tkn_iter: TokenIterator,
254 uop: CodeSection,
255 storage: Storage,
256 inst: Instruction | None,
257 ) -> bool:
258 next(tkn_iter)
259 next(tkn_iter)
260 next(tkn_iter)
261 for var in storage.inputs:
262 var.kill()
263 return True
264
265 def kill(
266 self,
267 tkn: Token,
268 tkn_iter: TokenIterator,
269 uop: CodeSection,
270 storage: Storage,
271 inst: Instruction | None,
272 ) -> bool:
273 next(tkn_iter)
274 name_tkn = next(tkn_iter)
275 name = name_tkn.text
276 next(tkn_iter)
277 next(tkn_iter)
278 for var in storage.inputs:
279 if var.name == name:
280 var.kill()
281 break
282 else:
283 raise analysis_error(
284 f"'{name}' is not a live input-only variable", name_tkn
285 )
286 return True
287
288 def stackref_kill(
289 self,
290 name: Token,
291 storage: Storage,
292 escapes: bool
293 ) -> bool:
294 live = ""
295 for var in reversed(storage.inputs):
296 if var.name == name.text:
297 if live and escapes:
298 raise analysis_error(
299 f"Cannot close '{name.text}' when "
300 f"'{live}' is still live", name)
301 var.kill()
302 break
303 if var.in_local:
304 live = var.name
305 return True
306
307 def stackref_close_specialized(
308 self,
309 tkn: Token,
310 tkn_iter: TokenIterator,
311 uop: CodeSection,
312 storage: Storage,
313 inst: Instruction | None,
314 ) -> bool:
315
316 self.out.emit(tkn)
317 tkn = next(tkn_iter)
318 assert tkn.kind == "LPAREN"
319 self.out.emit(tkn)
320 name = next(tkn_iter)
321 self.out.emit(name)
322 comma = next(tkn_iter)
323 if comma.kind != "COMMA":
324 raise analysis_error("Expected comma", comma)
325 self.out.emit(comma)
326 dealloc = next(tkn_iter)
327 if dealloc.kind != "IDENTIFIER":
328 raise analysis_error("Expected identifier", dealloc)
329 self.out.emit(dealloc)
330 if name.kind == "IDENTIFIER":
331 escapes = dealloc.text not in NON_ESCAPING_DEALLOCS
332 return self.stackref_kill(name, storage, escapes)
333 rparen = emit_to(self.out, tkn_iter, "RPAREN")
334 self.emit(rparen)
335 return True
336
337 def stackref_steal(
338 self,
339 tkn: Token,
340 tkn_iter: TokenIterator,
341 uop: CodeSection,
342 storage: Storage,
343 inst: Instruction | None,
344 ) -> bool:
345 self.out.emit(tkn)
346 tkn = next(tkn_iter)
347 assert tkn.kind == "LPAREN"
348 self.out.emit(tkn)
349 name = next(tkn_iter)
350 self.out.emit(name)
351 if name.kind == "IDENTIFIER":
352 return self.stackref_kill(name, storage, False)
353 rparen = emit_to(self.out, tkn_iter, "RPAREN")
354 self.emit(rparen)
355 return True
356
357 def sync_sp(
358 self,
359 tkn: Token,
360 tkn_iter: TokenIterator,
361 uop: CodeSection,
362 storage: Storage,
363 inst: Instruction | None,
364 ) -> bool:
365 next(tkn_iter)
366 next(tkn_iter)
367 next(tkn_iter)
368 storage.clear_inputs("when syncing stack")
369 storage.flush(self.out)
370 storage.stack.clear(self.out)
371 return True
372
373 def stack_pointer(
374 self,
375 tkn: Token,
376 tkn_iter: TokenIterator,
377 uop: CodeSection,
378 storage: Storage,
379 inst: Instruction | None,
380 ) -> bool:
381 if storage.spilled:
382 raise analysis_error("stack_pointer is invalid when stack is spilled to memory", tkn)
383 self.emit(tkn)
384 return True
385
386 def goto_label(self, goto: Token, label: Token, storage: Storage) -> None:
387 if label.text not in self.labels:
388 print(self.labels.keys())
389 raise analysis_error(f"Label '{label.text}' does not exist", label)
390 label_node = self.labels[label.text]
391 if label_node.spilled:
392 if not storage.spilled:
393 self.emit_save(storage)
394 elif storage.spilled:
395 raise analysis_error("Cannot jump from spilled label without reloading the stack pointer", goto)
396 self.out.start_line()
397 self.out.emit("JUMP_TO_LABEL(")
398 self.out.emit(label)
399 self.out.emit(")")
400
401 def emit_save(self, storage: Storage) -> None:
402 storage.flush(self.out)
403 storage.save(self.out)
404
405 def save_stack(
406 self,
407 tkn: Token,
408 tkn_iter: TokenIterator,
409 uop: CodeSection,
410 storage: Storage,
411 inst: Instruction | None,
412 ) -> bool:
413 next(tkn_iter)
414 next(tkn_iter)
415 next(tkn_iter)
416 self.emit_save(storage)
417 return True
418
419 def emit_reload(self, storage: Storage) -> None:
420 storage.reload(self.out)
421
422 def reload_stack(
423 self,
424 tkn: Token,
425 tkn_iter: TokenIterator,
426 uop: CodeSection,
427 storage: Storage,
428 inst: Instruction | None,
429 ) -> bool:
430 next(tkn_iter)
431 next(tkn_iter)
432 next(tkn_iter)
433 self.emit_reload(storage)
434 return True
435
436 def instruction_size(self,
437 tkn: Token,
438 tkn_iter: TokenIterator,
439 uop: CodeSection,
440 storage: Storage,
441 inst: Instruction | None,
442 ) -> bool:
443 """Replace the INSTRUCTION_SIZE macro with the size of the current instruction."""
444 if uop.instruction_size is None:
445 raise analysis_error("The INSTRUCTION_SIZE macro requires uop.instruction_size to be set", tkn)
446 self.out.emit(f" {uop.instruction_size}u ")
447 return True
448
449 def _print_storage(self, reason:str, storage: Storage) -> None:
450 if DEBUG:
451 self.out.start_line()
452 self.emit(f"/* {reason} */\n")
453 self.emit(storage.as_comment())
454 self.out.start_line()
455
456 def _emit_stmt(
457 self,
458 stmt: Stmt,
459 uop: CodeSection,
460 storage: Storage,
461 inst: Instruction | None,
462 ) -> tuple[bool, Token | None, Storage]:
463 method_name = "emit_" + stmt.__class__.__name__
464 method = getattr(self, method_name, None)
465 if method is None:
466 raise NotImplementedError
467 return method(stmt, uop, storage, inst) # type: ignore[no-any-return]
468
469 def emit_SimpleStmt(
470 self,
471 stmt: SimpleStmt,
472 uop: CodeSection,
473 storage: Storage,
474 inst: Instruction | None,
475 ) -> tuple[bool, Token | None, Storage]:
476 local_stores = set(uop.local_stores)
477 reachable = True
478 tkn = stmt.contents[-1]
479 try:
480 if stmt in uop.properties.escaping_calls:
481 escape = uop.properties.escaping_calls[stmt]
482 if escape.kills is not None:
483 self.stackref_kill(escape.kills, storage, True)
484 self.emit_save(storage)
485 tkn_iter = TokenIterator(stmt.contents)
486 for tkn in tkn_iter:
487 if tkn.kind == "GOTO":
488 label_tkn = next(tkn_iter)
489 self.goto_label(tkn, label_tkn, storage)
490 reachable = False
491 elif tkn.kind == "RETURN":
492 self.emit(tkn)
493 semicolon = emit_to(self.out, tkn_iter, "SEMI")
494 self.emit(semicolon)
495 reachable = False
496 elif tkn.kind == "IDENTIFIER":
497 if tkn.text in self._replacers:
498 if not self._replacers[tkn.text](tkn, tkn_iter, uop, storage, inst):
499 reachable = False
500 else:
501 if tkn in local_stores:
502 for var in storage.inputs:
503 if var.name == tkn.text:
504 var.in_local = True
505 var.memory_offset = None
506 break
507 for var in storage.outputs:
508 if var.name == tkn.text:
509 var.in_local = True
510 var.memory_offset = None
511 break
512 if tkn.text.startswith("DISPATCH"):
513 reachable = False
514 self.out.emit(tkn)
515 else:
516 self.out.emit(tkn)
517 if stmt in uop.properties.escaping_calls:
518 self.emit_reload(storage)
519 return reachable, None, storage
520 except StackError as ex:
521 raise analysis_error(ex.args[0], tkn) #from None
522
523
524 def emit_MacroIfStmt(
525 self,
526 stmt: MacroIfStmt,
527 uop: CodeSection,
528 storage: Storage,
529 inst: Instruction | None,
530 ) -> tuple[bool, Token | None, Storage]:
531 self.out.emit(stmt.condition)
532 branch = stmt.else_ is not None
533 reachable = True
534 if branch:
535 else_storage = storage.copy()
536 for s in stmt.body:
537 r, tkn, storage = self._emit_stmt(s, uop, storage, inst)
538 if tkn is not None:
539 self.out.emit(tkn)
540 if not r:
541 reachable = False
542 if branch:
543 assert stmt.else_ is not None
544 self.out.emit(stmt.else_)
545 assert stmt.else_body is not None
546 for s in stmt.else_body:
547 r, tkn, else_storage = self._emit_stmt(s, uop, else_storage, inst)
548 if tkn is not None:
549 self.out.emit(tkn)
550 if not r:
551 reachable = False
552 else_storage.merge(storage, self.out) # type: ignore[possibly-undefined]
553 storage = else_storage
554 self.out.emit(stmt.endif)
555 return reachable, None, storage
556
557
558 def emit_IfStmt(
559 self,
560 stmt: IfStmt,
561 uop: CodeSection,
562 storage: Storage,
563 inst: Instruction | None,
564 ) -> tuple[bool, Token | None, Storage]:
565 self.out.emit(stmt.if_)
566 for tkn in stmt.condition:
567 self.out.emit(tkn)
568 if_storage = storage.copy()
569 rbrace: Token | None = stmt.if_
570 try:
571 reachable, rbrace, if_storage = self._emit_stmt(stmt.body, uop, if_storage, inst)
572 if stmt.else_ is not None:
573 assert rbrace is not None
574 self.out.emit(rbrace)
575 self.out.emit(stmt.else_)
576 if stmt.else_body is not None:
577 else_reachable, rbrace, else_storage = self._emit_stmt(stmt.else_body, uop, storage, inst)
578 if not reachable:
579 reachable, storage = else_reachable, else_storage
580 elif not else_reachable:
581 # Discard the else storage
582 storage = if_storage
583 else:
584 #Both reachable
585 else_storage.merge(if_storage, self.out)
586 storage = else_storage
587 else:
588 if reachable:
589 if_storage.merge(storage, self.out)
590 storage = if_storage
591 else:
592 # Discard the if storage
593 reachable = True
594 return reachable, rbrace, storage
595 except StackError as ex:
596 assert rbrace is not None
597 raise analysis_error(ex.args[0], rbrace) from None
598
599 def emit_BlockStmt(
600 self,
601 stmt: BlockStmt,
602 uop: CodeSection,
603 storage: Storage,
604 inst: Instruction | None,
605 emit_braces: bool = True,
606 ) -> tuple[bool, Token | None, Storage]:
607 """ Returns (reachable?, closing '}', stack)."""
608 tkn: Token | None = None
609 try:
610 if emit_braces:
611 self.out.emit(stmt.open)
612 reachable = True
613 for s in stmt.body:
614 reachable, tkn, storage = self._emit_stmt(s, uop, storage, inst)
615 if tkn is not None:
616 self.out.emit(tkn)
617 if not reachable:
618 break
619 return reachable, stmt.close, storage
620 except StackError as ex:
621 if tkn is None:
622 tkn = stmt.close
623 raise analysis_error(ex.args[0], tkn) from None
624
625 def emit_ForStmt(
626 self,
627 stmt: ForStmt,
628 uop: CodeSection,
629 storage: Storage,
630 inst: Instruction | None,
631 ) -> tuple[bool, Token | None, Storage]:
632 """ Returns (reachable?, closing '}', stack)."""
633 self.out.emit(stmt.for_)
634 for tkn in stmt.header:
635 self.out.emit(tkn)
636 return self._emit_stmt(stmt.body, uop, storage, inst)
637
638 def emit_WhileStmt(
639 self,
640 stmt: WhileStmt,
641 uop: CodeSection,
642 storage: Storage,
643 inst: Instruction | None,
644 ) -> tuple[bool, Token | None, Storage]:
645 """ Returns (reachable?, closing '}', stack)."""
646 self.out.emit(stmt.while_)
647 for tkn in stmt.condition:
648 self.out.emit(tkn)
649 return self._emit_stmt(stmt.body, uop, storage, inst)
650
651
652 def emit_tokens(
653 self,
654 code: CodeSection,
655 storage: Storage,
656 inst: Instruction | None,
657 emit_braces: bool = True
658 ) -> tuple[bool, Storage]:
659 self.out.start_line()
660 reachable, tkn, storage = self.emit_BlockStmt(code.body, code, storage, inst, emit_braces)
661 assert tkn is not None
662 try:
663 if reachable:
664 storage.push_outputs()
665 if emit_braces:
666 self.out.emit(tkn)
667 except StackError as ex:
668 raise analysis_error(ex.args[0], tkn) from None
669 return reachable, storage
670
671 def emit(self, txt: str | Token) -> None:
672 self.out.emit(txt)
673
674
675 def cflags(p: Properties) -> str:
676 flags: list[str] = []
677 if p.oparg:
678 flags.append("HAS_ARG_FLAG")
679 if p.uses_co_consts:
680 flags.append("HAS_CONST_FLAG")
681 if p.uses_co_names:
682 flags.append("HAS_NAME_FLAG")
683 if p.jumps:
684 flags.append("HAS_JUMP_FLAG")
685 if p.has_free:
686 flags.append("HAS_FREE_FLAG")
687 if p.uses_locals:
688 flags.append("HAS_LOCAL_FLAG")
689 if p.eval_breaker:
690 flags.append("HAS_EVAL_BREAK_FLAG")
691 if p.deopts:
692 flags.append("HAS_DEOPT_FLAG")
693 if p.side_exit:
694 flags.append("HAS_EXIT_FLAG")
695 if not p.infallible:
696 flags.append("HAS_ERROR_FLAG")
697 if p.error_without_pop:
698 flags.append("HAS_ERROR_NO_POP_FLAG")
699 if p.escapes:
700 flags.append("HAS_ESCAPES_FLAG")
701 if p.pure:
702 flags.append("HAS_PURE_FLAG")
703 if p.no_save_ip:
704 flags.append("HAS_NO_SAVE_IP_FLAG")
705 if flags:
706 return " | ".join(flags)
707 else:
708 return "0"