bpo-42128: Structural Pattern Matching (PEP 634) (GH-22917)

Co-authored-by: Guido van Rossum <guido@python.org>
Co-authored-by: Talin <viridia@gmail.com>
Co-authored-by: Pablo Galindo <pablogsal@gmail.com>

6 files changed, 76 insertions, 6 deletions

diff --git a/Include/Python-ast.h b/Include/Python-ast.h
index fc9f65c..bd127ca 100644
--- a/Include/Python-ast.h
+++ b/Include/Python-ast.h
@@ -44,6 +44,8 @@ typedef struct _alias *alias_ty;
 
 typedef struct _withitem *withitem_ty;
 
+typedef struct _match_case *match_case_ty;
+
 typedef struct _type_ignore *type_ignore_ty;
 
 
@@ -121,6 +123,14 @@ asdl_withitem_seq *_Py_asdl_withitem_seq_new(Py_ssize_t size, PyArena *arena);
 
 typedef struct {
     _ASDL_SEQ_HEAD
+    match_case_ty typed_elements[1];
+} asdl_match_case_seq;
+
+asdl_match_case_seq *_Py_asdl_match_case_seq_new(Py_ssize_t size, PyArena
+                                                 *arena);
+
+typedef struct {
+    _ASDL_SEQ_HEAD
     type_ignore_ty typed_elements[1];
 } asdl_type_ignore_seq;
 
@@ -158,10 +168,10 @@ enum _stmt_kind {FunctionDef_kind=1, AsyncFunctionDef_kind=2, ClassDef_kind=3,
                   Return_kind=4, Delete_kind=5, Assign_kind=6,
                   AugAssign_kind=7, AnnAssign_kind=8, For_kind=9,
                   AsyncFor_kind=10, While_kind=11, If_kind=12, With_kind=13,
-                  AsyncWith_kind=14, Raise_kind=15, Try_kind=16,
-                  Assert_kind=17, Import_kind=18, ImportFrom_kind=19,
-                  Global_kind=20, Nonlocal_kind=21, Expr_kind=22, Pass_kind=23,
-                  Break_kind=24, Continue_kind=25};
+                  AsyncWith_kind=14, Match_kind=15, Raise_kind=16, Try_kind=17,
+                  Assert_kind=18, Import_kind=19, ImportFrom_kind=20,
+                  Global_kind=21, Nonlocal_kind=22, Expr_kind=23, Pass_kind=24,
+                  Break_kind=25, Continue_kind=26};
 struct _stmt {
     enum _stmt_kind kind;
     union {
@@ -259,6 +269,11 @@ struct _stmt {
         } AsyncWith;
 
         struct {
+            expr_ty subject;
+            asdl_match_case_seq *cases;
+        } Match;
+
+        struct {
             expr_ty exc;
             expr_ty cause;
         } Raise;
@@ -311,7 +326,8 @@ enum _expr_kind {BoolOp_kind=1, NamedExpr_kind=2, BinOp_kind=3, UnaryOp_kind=4,
                   YieldFrom_kind=15, Compare_kind=16, Call_kind=17,
                   FormattedValue_kind=18, JoinedStr_kind=19, Constant_kind=20,
                   Attribute_kind=21, Subscript_kind=22, Starred_kind=23,
-                  Name_kind=24, List_kind=25, Tuple_kind=26, Slice_kind=27};
+                  Name_kind=24, List_kind=25, Tuple_kind=26, Slice_kind=27,
+                  MatchAs_kind=28, MatchOr_kind=29};
 struct _expr {
     enum _expr_kind kind;
     union {
@@ -454,6 +470,15 @@ struct _expr {
             expr_ty step;
         } Slice;
 
+        struct {
+            expr_ty pattern;
+            identifier name;
+        } MatchAs;
+
+        struct {
+            asdl_expr_seq *patterns;
+        } MatchOr;
+
     } v;
     int lineno;
     int col_offset;
@@ -524,6 +549,12 @@ struct _withitem {
     expr_ty optional_vars;
 };
 
+struct _match_case {
+    expr_ty pattern;
+    expr_ty guard;
+    asdl_stmt_seq *body;
+};
+
 enum _type_ignore_kind {TypeIgnore_kind=1};
 struct _type_ignore {
     enum _type_ignore_kind kind;
@@ -607,6 +638,10 @@ stmt_ty _Py_With(asdl_withitem_seq * items, asdl_stmt_seq * body, string
 stmt_ty _Py_AsyncWith(asdl_withitem_seq * items, asdl_stmt_seq * body, string
                       type_comment, int lineno, int col_offset, int end_lineno,
                       int end_col_offset, PyArena *arena);
+#define Match(a0, a1, a2, a3, a4, a5, a6) _Py_Match(a0, a1, a2, a3, a4, a5, a6)
+stmt_ty _Py_Match(expr_ty subject, asdl_match_case_seq * cases, int lineno, int
+                  col_offset, int end_lineno, int end_col_offset, PyArena
+                  *arena);
 #define Raise(a0, a1, a2, a3, a4, a5, a6) _Py_Raise(a0, a1, a2, a3, a4, a5, a6)
 stmt_ty _Py_Raise(expr_ty exc, expr_ty cause, int lineno, int col_offset, int
                   end_lineno, int end_col_offset, PyArena *arena);
@@ -743,6 +778,13 @@ expr_ty _Py_Tuple(asdl_expr_seq * elts, expr_context_ty ctx, int lineno, int
 expr_ty _Py_Slice(expr_ty lower, expr_ty upper, expr_ty step, int lineno, int
                   col_offset, int end_lineno, int end_col_offset, PyArena
                   *arena);
+#define MatchAs(a0, a1, a2, a3, a4, a5, a6) _Py_MatchAs(a0, a1, a2, a3, a4, a5, a6)
+expr_ty _Py_MatchAs(expr_ty pattern, identifier name, int lineno, int
+                    col_offset, int end_lineno, int end_col_offset, PyArena
+                    *arena);
+#define MatchOr(a0, a1, a2, a3, a4, a5) _Py_MatchOr(a0, a1, a2, a3, a4, a5)
+expr_ty _Py_MatchOr(asdl_expr_seq * patterns, int lineno, int col_offset, int
+                    end_lineno, int end_col_offset, PyArena *arena);
 #define comprehension(a0, a1, a2, a3, a4) _Py_comprehension(a0, a1, a2, a3, a4)
 comprehension_ty _Py_comprehension(expr_ty target, expr_ty iter, asdl_expr_seq
                                    * ifs, int is_async, PyArena *arena);
@@ -769,6 +811,9 @@ alias_ty _Py_alias(identifier name, identifier asname, PyArena *arena);
 #define withitem(a0, a1, a2) _Py_withitem(a0, a1, a2)
 withitem_ty _Py_withitem(expr_ty context_expr, expr_ty optional_vars, PyArena
                          *arena);
+#define match_case(a0, a1, a2, a3) _Py_match_case(a0, a1, a2, a3)
+match_case_ty _Py_match_case(expr_ty pattern, expr_ty guard, asdl_stmt_seq *
+                             body, PyArena *arena);
 #define TypeIgnore(a0, a1, a2) _Py_TypeIgnore(a0, a1, a2)
 type_ignore_ty _Py_TypeIgnore(int lineno, string tag, PyArena *arena);
 
diff --git a/Include/internal/pycore_ast.h b/Include/internal/pycore_ast.h
index 058fbc0..2d0c5fb 100644
--- a/Include/internal/pycore_ast.h
+++ b/Include/internal/pycore_ast.h
@@ -91,6 +91,9 @@ struct ast_state {
     PyObject *Lt_type;
     PyObject *MatMult_singleton;
     PyObject *MatMult_type;
+    PyObject *MatchAs_type;
+    PyObject *MatchOr_type;
+    PyObject *Match_type;
     PyObject *Mod_singleton;
     PyObject *Mod_type;
     PyObject *Module_type;
@@ -137,6 +140,7 @@ struct ast_state {
     PyObject *Yield_type;
     PyObject *__dict__;
     PyObject *__doc__;
+    PyObject *__match_args__;
     PyObject *__module__;
     PyObject *_attributes;
     PyObject *_fields;
@@ -153,6 +157,7 @@ struct ast_state {
     PyObject *bases;
     PyObject *body;
     PyObject *boolop_type;
+    PyObject *cases;
     PyObject *cause;
     PyObject *cmpop_type;
     PyObject *col_offset;
@@ -175,6 +180,7 @@ struct ast_state {
     PyObject *format_spec;
     PyObject *func;
     PyObject *generators;
+    PyObject *guard;
     PyObject *handlers;
     PyObject *id;
     PyObject *ifs;
@@ -193,6 +199,7 @@ struct ast_state {
     PyObject *level;
     PyObject *lineno;
     PyObject *lower;
+    PyObject *match_case_type;
     PyObject *mod_type;
     PyObject *module;
     PyObject *msg;
@@ -204,6 +211,8 @@ struct ast_state {
     PyObject *ops;
     PyObject *optional_vars;
     PyObject *orelse;
+    PyObject *pattern;
+    PyObject *patterns;
     PyObject *posonlyargs;
     PyObject *returns;
     PyObject *right;
@@ -211,6 +220,7 @@ struct ast_state {
     PyObject *slice;
     PyObject *step;
     PyObject *stmt_type;
+    PyObject *subject;
     PyObject *tag;
     PyObject *target;
     PyObject *targets;
diff --git a/Include/internal/pycore_interp.h b/Include/internal/pycore_interp.h
index 58b1126..477cbf0 100644
--- a/Include/internal/pycore_interp.h
+++ b/Include/internal/pycore_interp.h
@@ -253,6 +253,10 @@ struct _is {
     // importlib module
     PyObject *importlib;
 
+    // Kept handy for pattern matching:
+    PyObject *map_abc;  // _collections_abc.Mapping
+    PyObject *seq_abc;  // _collections_abc.Sequence
+
     /* Used in Modules/_threadmodule.c. */
     long num_threads;
     /* Support for runtime thread stack size tuning.
@@ -347,4 +351,3 @@ PyAPI_FUNC(void) _PyInterpreterState_IDDecref(struct _is *);
 }
 #endif
 #endif /* !Py_INTERNAL_INTERP_H */
-
diff --git a/Include/object.h b/Include/object.h
index 0870e4c..1454583 100644
--- a/Include/object.h
+++ b/Include/object.h
@@ -359,6 +359,11 @@ given type object has a specified feature.
 #define Py_TPFLAGS_HAVE_AM_SEND (1UL << 21)
 #endif
 
+// This undocumented flag gives certain built-ins their unique pattern-matching
+// behavior, which allows a single positional subpattern to match against the
+// subject itself (rather than a mapped attribute on it):
+#define _Py_TPFLAGS_MATCH_SELF (1UL << 22)
+
 /* These flags are used to determine if a type is a subclass. */
 #define Py_TPFLAGS_LONG_SUBCLASS        (1UL << 24)
 #define Py_TPFLAGS_LIST_SUBCLASS        (1UL << 25)
diff --git a/Include/opcode.h b/Include/opcode.h
index 998a5ce..ea484c5 100644
--- a/Include/opcode.h
+++ b/Include/opcode.h
@@ -30,6 +30,11 @@ extern "C" {
 #define BINARY_TRUE_DIVIDE       27
 #define INPLACE_FLOOR_DIVIDE     28
 #define INPLACE_TRUE_DIVIDE      29
+#define GET_LEN                  30
+#define MATCH_MAPPING            31
+#define MATCH_SEQUENCE           32
+#define MATCH_KEYS               33
+#define COPY_DICT_WITHOUT_KEYS   34
 #define WITH_EXCEPT_START        49
 #define GET_AITER                50
 #define GET_ANEXT                51
@@ -117,6 +122,7 @@ extern "C" {
 #define SET_ADD                 146
 #define MAP_ADD                 147
 #define LOAD_CLASSDEREF         148
+#define MATCH_CLASS             152
 #define SETUP_ASYNC_WITH        154
 #define FORMAT_VALUE            155
 #define BUILD_CONST_KEY_MAP     156
diff --git a/Include/symtable.h b/Include/symtable.h
index abd19a7..6f0b7cb 100644
--- a/Include/symtable.h
+++ b/Include/symtable.h
@@ -33,6 +33,7 @@ struct symtable {
                                        the symbol table */
     int recursion_depth;            /* current recursion depth */
     int recursion_limit;            /* recursion limit */
+    int in_pattern;                 /* whether we are currently in a pattern */
 };
 
 typedef struct _symtable_entry {