[ENH] PEP 634 - Structural Pattern Matching

[da-woods]

PEP 634 defines a new "switch-statement-like syntax": https://www.python.org/dev/peps/pep-0634/ that will appear in Python 3.10. Being a Python language feature, Cython should aim to support this.

Additional context

• Probably not worth supporting until after the release of Python 3.10 (in principle it could change before then).
• Probably a fairly complicated feature to implement (involves both parser and code generation changes)
• If cdef dataclasses #3400 is merged by then, it'll need to generate __match_args__ (this can be implemented separately from the language support though)

• Parsing
• Basic constant cases converted to if ... elif ... statement: Implementation of basic pattern matching cases #6000
• Handle simple "guards" https://github.com/da-woods/cython/tree/guards
• A few extra types of patterns that assign targets https://github.com/da-woods/cython/tree/match-targets
• Handle sequence patterns https://github.com/da-woods/cython/tree/match-sequence
• Handle mapping patterns https://github.com/da-woods/cython/tree/match-mapping
• Handle class patterns https://github.com/da-woods/cython/tree/match-class
• (optional) A quick benchmark https://github.com/da-woods/cython/tree/match-benchmark
• Or patterns https://github.com/da-woods/cython/tree/match-or
• At the end, update the tests to match the latest Python pattern matching tests

[Jaakkonen]

Python 3.10 was released on 2021-10-04 so this is now required for upstream Python compatibility.
For SEO the current error on cython -3 main.py messages show

Error compiling Cython file:
------------------------------------------------------------
...


def my_func(t: int) -> str:
    match t:
         ^
------------------------------------------------------------

main.py:41:10: Syntax error in simple statement list

[scoder]

PRs welcome, as usual.

I would expect that at least larger parts of the C implementation in CPython can be adopted – if that's what we want to use, as opposed to a (probably simpler) Cython implementation. The parser implementation is independent, though, and I would guess that there will be Cython specific issues along the way, possibly even cases where Cython's own syntax (such as C types) interferes with pattern syntax. But we'll see about that when we run into it.

In any case, this is a fairly large feature that will take time to implement, probably in several steps. So, again, PRs welcome.

[da-woods]

at least larger parts of the C implementation in CPython can be adopted

I don't know that there's much C implementation to take. If you look at the byte-code for a function that uses pattern matching, it's mostly broken down into a set of comparisons. E.g. case (a, b) gets split into:

              8 GET_LEN
             10 LOAD_CONST               1 (2)
             12 COMPARE_OP               2 (==)
             14 POP_JUMP_IF_FALSE       18 (to 36)
             16 UNPACK_SEQUENCE          2
             18 STORE_FAST               1 (a)
             20 STORE_FAST               2 (b)

So I think it's mostly a parsing then AST manipulation issue.

It can probably be split into a parsing PR, and then successive PRs to make individual types of patterns work successfully. (I wasn't planning to do any of this myself any time soon though).

[scoder]

Ok, I was kinda expecting that this might be the case. Thanks for checking.

Then I guess it's really just about generating Cython code (or syntax nodes directly) to implement the comparisons. That merits its own transform class, best also in its own module.

[da-woods]

FWIW I can currently parse the entire CPython test_patma file (https://github.com/python/cpython/blob/main/Lib/test/test_patma.py). It then fails at AnalyseExpressions (because I haven't tried to implement that yet).

Changes are on https://github.com/da-woods/cython/tree/parse-match. I'll submit that as a PR at some point fairly soon (but it's dependent on #4813, so I'll wait until that's finalized)

• Basic constant cases converted to if ... elif ... statement: https://github.com/da-woods/cython/tree/basic_match
• Handle simple "guards" https://github.com/da-woods/cython/tree/guards
• A few extra types of patterns that assign targets https://github.com/da-woods/cython/tree/match-targets
• Handle sequence patterns https://github.com/da-woods/cython/tree/match-sequence
• Handle mapping patterns https://github.com/da-woods/cython/tree/match-mapping
• Handle class patterns https://github.com/da-woods/cython/tree/match-class
• A quick benchmark https://github.com/da-woods/cython/tree/match-benchmark
• Or patterns https://github.com/da-woods/cython/tree/match-or

[da-woods]

I have an implementation that passes the CPython test_patma.py tests (which I think is the extent of the testing in CPython). I'll submit it in chunks (with the parser changes already submitted being the first chunk) in the hope of making it a little more tractable to review.

If anyone wants to test/use it in advance then the "Or pattern" branch is the final one and covers basically everything.

[da-woods]

@scoder

As I said above, I'm going to submit this in bits (with #4813) effectively being the first.

I'd like to make it easy for people to try it and give some early feedback (we did get some useful reports from people testing dataclasses and assignment expressions for example).

What I was proposing to do was to make a pat-match branch in this repo containing the unreviewed changes, so that there's a single easy thing to check out if people want to try it.

Does that sound reasonable?

[da-woods]

Does that sound reasonable?

In the absence of comments (and because it's very easy to delete if it is a problem...) I've created a branch in the cython repository https://github.com/cython/cython/tree/patma-preview

If anyone wants to try out pattern matching before it's officially added to Cython then use that. It's obviously "at your own risk" but I'd be happy to hear of any issues there.

It'll hopefully be merged gradually in little bits...

[Riko2909]

Are there any updates on this or some possible fixes that can be applied? Seems like, the patma-preview patch is a bit to old to be used.

[da-woods]

I've bumped the patma-preview branch to be up to date with the latest master.

I should point out:

• I'm not making a big effort to keep this branch rigorously up-to-date. It's intended as something you can check and and give a try, not a patch that you actually want to apply to Cython for real-world uses.
• It's about 7000 lines of unreviewed code (although 3000 of those are tests copied from Python) - use it at your peril! My aim was to collect feedback on bugs so I really hope no-one's using it on production code.