bpo-41746: Add type information to asdl_seq objects (GH-22223)

* Add new capability to the PEG parser to type variable assignments. For instance:
```
       | a[asdl_stmt_seq*]=';'.small_stmt+ [';'] NEWLINE { a }
```

* Add new sequence types from the asdl definition (automatically generated)
* Make `asdl_seq` type a generic aliasing pointer type.
* Create a new `asdl_generic_seq` for the generic case using `void*`.
* The old `asdl_seq_GET`/`ast_seq_SET` macros now are typed.
* New `asdl_seq_GET_UNTYPED`/`ast_seq_SET_UNTYPED` macros for dealing with generic sequences.
* Changes all possible `asdl_seq` types to use specific versions everywhere.

4 files changed, 56 insertions, 6 deletions

diff --git a/Tools/peg_generator/pegen/c_generator.py b/Tools/peg_generator/pegen/c_generator.py
index aee668c..1a814aa 100644
--- a/Tools/peg_generator/pegen/c_generator.py
+++ b/Tools/peg_generator/pegen/c_generator.py
@@ -74,6 +74,7 @@ class FunctionCall:
     function: str
     arguments: List[Any] = field(default_factory=list)
     assigned_variable: Optional[str] = None
+    assigned_variable_type: Optional[str] = None
     return_type: Optional[str] = None
     nodetype: Optional[NodeTypes] = None
     force_true: bool = False
@@ -87,7 +88,10 @@ class FunctionCall:
         if self.force_true:
             parts.append(", 1")
         if self.assigned_variable:
-            parts = ["(", self.assigned_variable, " = ", *parts, ")"]
+            if self.assigned_variable_type:
+                parts = ["(", self.assigned_variable, " = ", '(', self.assigned_variable_type, ')', *parts, ")"]
+            else:
+                parts = ["(", self.assigned_variable, " = ", *parts, ")"]
         if self.comment:
             parts.append(f"  // {self.comment}")
         return "".join(parts)
@@ -210,6 +214,8 @@ class CCallMakerVisitor(GrammarVisitor):
         call = self.generate_call(node.item)
         if node.name:
             call.assigned_variable = node.name
+        if node.type:
+            call.assigned_variable_type = node.type
         return call
 
     def lookahead_call_helper(self, node: Lookahead, positive: int) -> FunctionCall:
@@ -568,9 +574,9 @@ class CParserGenerator(ParserGenerator, GrammarVisitor):
                     self.print("PyMem_Free(_children);")
                     self.add_return("NULL")
                 self.print("}")
-            self.print("asdl_seq *_seq = _Py_asdl_seq_new(_n, p->arena);")
+            self.print("asdl_seq *_seq = (asdl_seq*)_Py_asdl_generic_seq_new(_n, p->arena);")
             self.out_of_memory_return(f"!_seq", cleanup_code="PyMem_Free(_children);")
-            self.print("for (int i = 0; i < _n; i++) asdl_seq_SET(_seq, i, _children[i]);")
+            self.print("for (int i = 0; i < _n; i++) asdl_seq_SET_UNTYPED(_seq, i, _children[i]);")
             self.print("PyMem_Free(_children);")
             if node.name:
                 self.print(f"_PyPegen_insert_memo(p, _start_mark, {node.name}_type, _seq);")
@@ -782,4 +788,5 @@ class CParserGenerator(ParserGenerator, GrammarVisitor):
         name = node.name if node.name else call.assigned_variable
         if name is not None:
             name = self.dedupe(name)
-        return name, call.return_type
+        return_type = call.return_type if node.type is None else node.type
+        return name, return_type
diff --git a/Tools/peg_generator/pegen/grammar.py b/Tools/peg_generator/pegen/grammar.py
index 78edf41..332ee3c 100644
--- a/Tools/peg_generator/pegen/grammar.py
+++ b/Tools/peg_generator/pegen/grammar.py
@@ -259,9 +259,10 @@ class Alt:
 
 
 class NamedItem:
-    def __init__(self, name: Optional[str], item: Item):
+    def __init__(self, name: Optional[str], item: Item, type: Optional[str] = None):
         self.name = name
         self.item = item
+        self.type = type
         self.nullable = False
 
     def __str__(self) -> str:
diff --git a/Tools/peg_generator/pegen/grammar_parser.py b/Tools/peg_generator/pegen/grammar_parser.py
index c784cfd..6e3bc50 100644
--- a/Tools/peg_generator/pegen/grammar_parser.py
+++ b/Tools/peg_generator/pegen/grammar_parser.py
@@ -402,12 +402,52 @@ class GeneratedParser(Parser):
 
     @memoize
     def named_item(self) -> Optional[NamedItem]:
-        # named_item: NAME '=' ~ item | item | lookahead
+        # named_item: NAME '[' NAME '*' ']' '=' ~ item | NAME '[' NAME ']' '=' ~ item | NAME '=' ~ item | item | lookahead
         mark = self.mark()
         cut = False
         if (
             (name := self.name())
             and
+            (literal := self.expect('['))
+            and
+            (type := self.name())
+            and
+            (literal_1 := self.expect('*'))
+            and
+            (literal_2 := self.expect(']'))
+            and
+            (literal_3 := self.expect('='))
+            and
+            (cut := True)
+            and
+            (item := self.item())
+        ):
+            return NamedItem ( name . string , item , f"{type.string}*" )
+        self.reset(mark)
+        if cut: return None
+        cut = False
+        if (
+            (name := self.name())
+            and
+            (literal := self.expect('['))
+            and
+            (type := self.name())
+            and
+            (literal_1 := self.expect(']'))
+            and
+            (literal_2 := self.expect('='))
+            and
+            (cut := True)
+            and
+            (item := self.item())
+        ):
+            return NamedItem ( name . string , item , type . string )
+        self.reset(mark)
+        if cut: return None
+        cut = False
+        if (
+            (name := self.name())
+            and
             (literal := self.expect('='))
             and
             (cut := True)
diff --git a/Tools/peg_generator/pegen/metagrammar.gram b/Tools/peg_generator/pegen/metagrammar.gram
index f0c5ac3..4802f56 100644
--- a/Tools/peg_generator/pegen/metagrammar.gram
+++ b/Tools/peg_generator/pegen/metagrammar.gram
@@ -83,6 +83,8 @@ items[NamedItemList]:
     | named_item { [named_item] }
 
 named_item[NamedItem]:
+    | NAME '[' type=NAME '*' ']' '=' ~ item {NamedItem(name.string, item, f"{type.string}*")}
+    | NAME '[' type=NAME ']' '=' ~ item {NamedItem(name.string, item, type.string)}
     | NAME '=' ~ item {NamedItem(name.string, item)}
     | item {NamedItem(None, item)}
     | it=lookahead {NamedItem(None, it)}