Make match patterns explicit in the AST

[ncoghlan]

BPO	43892
Nosy	@ncoghlan, @markshannon, @gvanrossum, @pablogsal, @brandtbucher, @isidentical, @freundTech
PRs	WIP bpo-43892: Make match patterns explicit in AST #25521 bpo-43892: Make match patterns explicit in AST #25585 bpo-43892: Validate the first term of complex literal value patterns #25735

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/brandtbucher'
closed_at = <Date 2021-04-29.11:27:27.671>
created_at = <Date 2021-04-20.11:59:54.593>
labels = ['type-feature', '3.10']
title = 'Make match patterns explicit in the AST'
updated_at = <Date 2021-04-30.00:19:37.153>
user = 'https://github.com/ncoghlan'

bugs.python.org fields:

activity = <Date 2021-04-30.00:19:37.153>
actor = 'brandtbucher'
assignee = 'brandtbucher'
closed = True
closed_date = <Date 2021-04-29.11:27:27.671>
closer = 'ncoghlan'
components = []
creation = <Date 2021-04-20.11:59:54.593>
creator = 'ncoghlan'
dependencies = []
files = []
hgrepos = []
issue_num = 43892
keywords = ['patch']
message_count = 26.0
messages = ['391430', '391433', '391437', '391438', '391448', '391457', '391471', '391485', '391599', '391610', '391622', '391668', '391672', '391674', '391687', '391694', '391695', '391712', '391842', '391844', '391845', '391943', '391950', '392279', '392300', '392368']
nosy_count = 7.0
nosy_names = ['ncoghlan', 'Mark.Shannon', 'Guido.van.Rossum', 'pablogsal', 'brandtbucher', 'BTaskaya', 'freundTech']
pr_nums = ['25521', '25585', '25735']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue43892'
versions = ['Python 3.10']

[ncoghlan]

In the SC submission ticket for PEP-642 (python/steering-council#43 ), Guido indicated he was in favour of the more explicit pattern matching AST changes suggested in that PEP.

This ticket covers adapting the pattern matching implementation to explicitly separate pattern nodes from expr nodes in the AST, so the code generator doesn't need to be context dependent.

[pablogsal]

Given that the AST is a public interface, I would advise to implement this before beta freeze of 3.10 to avoid making this a breaking change in the future for linters and the like

[ncoghlan]

Agreed. I had wanted the AST to be part of the PEPs specifically *because* it's a public API, but didn't check until today whether or not the original PEP-634 implementation had been merged as-is, or with a cleaned up AST definition.

https://github.com/ncoghlan/cpython/pull/8/files is the initial implementation with the AST and Grammar file updated.

I'll only create the CPython PR once the tests are passing, but I'll try to give Brandt at least a week to review it (I'll also ping him directly via email).

[ncoghlan]

It's specifically the definition of "match_case" in the AST that is affected:

match_case = (pattern pattern, expr? guard, stmt* body)

    pattern = MatchAlways
         | MatchValue(expr value)
         | MatchConstant(constant value)
         | MatchSequence(pattern* patterns)
         | MatchMapping(expr* keys, pattern* patterns)
         | MatchClass(expr cls, pattern* patterns, identifier* extra_attrs, pattern* extra_patterns)

     | MatchRestOfSequence(identifier? target)
     -- A NULL entry in the MatchMapping key list handles capturing extra mapping keys

     | MatchAs(pattern? pattern, identifier target)
     | MatchOr(pattern* patterns)
      attributes (int lineno, int col_offset, int? end_lineno, int? end_col_offset)

Relative to the PEP-642 AST, the notion of a "matchop" is gone - MatchValue always compares by equality, and there's a MatchConstant node for the identity comparisons against None, True, and False.

The grammar, code generator, AST validator, and unparser are then updated to produce or consume the new AST nodes.

[brandtbucher]

Hm, for some reason I was thinking that this was safe to do after the feature freeze. Let's get to it then!

Batuhan, perhaps we should change the linked issue for your AST validator PR to this one. That way we can close the old catch-all PEP-634 implementation issue and keep the discussion focused here.

Nick, you might find the discussion on this mypy PR (python/mypy#10191) helpful. In particular, Adrian raises some points about ways we could make type inference in the AST a bit neater. For example: not all patterns can be used for mapping keys. Perhaps there is a way to organize parts of the AST hierarchy that makes this a bit more concrete (though we should be careful to not limit reasonable syntax extensions in the future by doing so).

A few notes, just from skimming the outline here:

MatchValue(expr value)

MatchValue technically contains an expression node, although the actual expressions it can contain are quite limited (dotted names and negative/complex numbers, if I understand correctly). Can we gain anything by splitting this up into nodes for each of these (MatchValue(identifier* parts), etc...) instead?

MatchClass(expr cls, pattern* patterns, identifier* extra_attrs, pattern* extra_patterns)

If I remember correctly (this part was implemented a while ago), collecting the different positional and keyword arguments in the parser is sort of simple since we can pass around sequences of keyword nodes easily. I *think* that the new proposed design would require hacks like creating dummy MatchClass nodes with *only* the keyword parts and later combining them with the positional arguments and a class name, since it keeps the keyword names separate from their arguments. Maybe some of the parser folks on this thread can chime in on that.

Also, continuing the theme above, I think we can be more specific with "expr cls" here (maybe "identifier* cls").

MatchRestOfSequence(identifier? target)

In the interest of brevity, maybe "MatchStar" or something?

A NULL entry in the MatchMapping key list handles capturing extra mapping keys

I think we could just give MatchMapping a "identifier? rest" member, right? That way it becomes a bit easier to use, and we don't need to worry if it's last or not. It also keeps us from having to handle empty entries in the keys.

Oh, also, the ast unparser will need to be updated as well.

[pablogsal]

Also, I would like some more extensive argument or why not having context dependent nodes justifies the extra maintainance cost (I'm not against that of course, and I am sympathetic, but I think this needs some more extensive coverage or why we are doing this). Notice that we already have context dependent nodes and attributes, as well as implicit meaning of some values like None.

[isidentical]

Batuhan, perhaps we should change the linked issue for your AST validator PR to this one. That way we can close the old catch-all PEP-634 implementation issue and keep the discussion focused here.

I think it might be better as a separate issue that has a dependency on this one. I've created bpo-43897 for this.

[ncoghlan]

https://www.python.org/dev/peps/pep-0642/#representing-patterns-explicitly-in-the-abstract-syntax-tree covers the rationale for why it is potentially problematic to reuse expression nodes for match patterns: it doesn't semantically align with the fact that patterns are *not* expressions, so the AST ends up being closer to a concrete syntax tree than we would like.

For the specifics of the AST nodes:

• restricting sub expressions directly in the AST itself is tricky without side effects on the AST for non-pattern-matching code, so I'm intending to add any such restrictions that we want to enforce to the validator (other statements and expressions like yield, await, return, break, and continue already have separately enforced restrictions like that)
• cls needs to be an expression node to allow for attribute lookups
• the linked draft PR already updates the grammar to emit the new AST. MatchClass is able to collect the keyword args and their corresponding patterns in roughly the same way that MatchMapping collects its key:pattern pairs

[ncoghlan]

The draft PR moved because I messed up the previous branch name: https://github.com/ncoghlan/cpython/pull/9/files

It's to the point where everything except symtable.c compiles.

I put an initial skeleton of a validator in, but only enough to check that the parallel sequence lengths in the class and mapping pattern nodes are consistent - there's still plenty to be done in Batuhan's PR (e.g. because the AST constant folding now just delegates to the expression folding functions for MatchValue values and MatchMapping keys, this iteration only enforces the restrictions on permitted subexpressions in the surface syntax).

In addition to Brandt's MatchStar suggestion, I've also tweaked the MatchClassparameter names to better match PEP-634 (the old names were based on PEP-642's attribute pattern concept, so "extra_" made sense, but "kwd_" makes more sense for PEP-634):

    pattern = MatchAlways
         | MatchValue(expr value)
         | MatchConstant(constant value)
         | MatchSequence(pattern* patterns)
         | MatchMapping(expr* keys, pattern* patterns)
         | MatchClass(expr cls, pattern* patterns, identifier* kwd_attrs, pattern* kwd_patterns)

     | MatchStar(identifier? target)
     -- A NULL entry in the MatchMapping key list handles capturing extra mapping keys

     | MatchAs(pattern? pattern, identifier target)
     | MatchOr(pattern* patterns)
      attributes (int lineno, int col_offset, int? end_lineno, int? end_col_offset)

I think the idea of making the MatchMapping node signature "MatchMapping(expr* keys, pattern* patterns, identifier? rest)" has merit, but I'd like to get this initial iteration reviewed first to minimise the diff in the compiler_pattern_mapping implementation (right now it is fairly clear that the code generation for mapping patterns hasn't changed, but that will become significantly less obvious if/when the "**rest" handling changes away from working the same way _PyAST_Dict works)