Have internal immutable AST nodes

Feature or enhancement

Proposal:

This is an idea @iritkatriel, @markshannon and @pablogsal and I were discussing at the sprints in Cambridge.

Currently the ast module exposes a set of mutable AST nodes. The process of marshaling out to Python and converting back into C is extremely expensive. There's some ideas which it also blocks, for example PEP 638 contains:

To do that efficiently, will mean making all the nodes in the _ast module immutable, so as not degrade performance by much. They will need to be immutable to guarantee that the AST remains a tree to avoid having to support cyclic GC. Making them immutable means they will not have a dict attribute, making them compact.

We could offer a higher-performance option to consumers who don't need to modify the AST and unlock potential new features if we had an immutable AST.

The proposal here is to:

1. Replace the existing Python-ast.c nodes with nodes that are immutable.
2. Add a PyObject_HEAD to the begging of the arena allocated AST nodes.
3. Make the existing mutable nodes be wrappers around the immutable nodes that lazily produce the mutable nodes.
4. Add a new flag to ast.parse that returns the immutable nodes.

The nodes in the normal compiler will continue to be allocated via the slab compiler - the parser produces redundant nodes, deals with void* objects in addition to the AST nodes, and is just generally too hard to change to have heap allocated nodes. It also would increase the cost of parsing to have the nodes actually heap allocated during a normal compilation pass.

ast.parse would be able to do a much faster copy of the data to heap allocated PyObject*'s then it can today though.

Users interacting with the immutable nodes can use copy.replace to update them and when doing so can pass in an immutable node which will then go through something similar to the existing obj2ast mechanism.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response