Precise semantics

PEP 634 explicitly includes a section on undefined behavior. Large amounts of undefined behavior may be acceptable in a language like C, but in Python it should be kept to a minimum. Pattern matching in Python can be defined more precisely without losing expressiveness or performance.

Improved control over class matching

PEP 634 delegates the decision over whether a class is a sequence or mapping to collections.abc. Not all classes that could be considered sequences are registered as subclasses of collections.abc.Sequence. This PEP allows them to match sequence patterns, without the full collections.abc.Sequence machinery.

PEP 634 privileges some builtin classes with a special form of matching, the “self” match. For example the pattern list(x) matches a list and assigns the list to x. By allowing classes to choose which kinds of pattern they match, other classes can use this form as well.

For example, using sympy, we might want to write:

# a*a == a**2
case Mul(args=[Symbol(a), Symbol(b)]) if a == b:
    return Pow(a, 2)

Which requires the sympy class Symbol to “self” match. For sympy to support this pattern with PEP 634 is possible, but a bit tricky. With this PEP it can be implemented very easily [1].

Robustness

With this PEP, access to attributes during pattern matching becomes well defined and deterministic. This makes pattern matching less error prone when matching objects with hidden side effects, such as object-relational mappers. Objects will have more control over their own deconstruction, which can help prevent unintended consequences should attribute access have side-effects.

PEP 634 relies on the collections.abc module when determining which patterns a value can match, implicitly importing it if necessary. This PEP will eliminate surprising import errors and misleading audit events from those imports.

Efficient implementation

The semantics proposed in this PEP will allow efficient implementation, partly as a result of having precise semantics and partly from using the object model.

With precise semantics, it is possible to reason about what code transformations are correct, and thus apply optimizations effectively.

Because the object model is a core part of Python, implementations already handle special attribute lookup efficiently. Looking up a special attribute is much faster than performing a subclass test on an abstract base class.

Additions to the object model

The __match_container__ and __match_class__ attributes will be added to object. __match_container__ should be overridden by classes that want to match mapping or sequence patterns. __match_class__ should be overridden by classes that want to change the default behavior when matching class patterns.

__match_container__ must be an integer and should be exactly one of these:

0
MATCH_SEQUENCE = 1
MATCH_MAPPING = 2

MATCH_SEQUENCE is used to indicate that instances of the class can match sequence patterns.

MATCH_MAPPING is used to indicate that instances of the class can match mapping patterns.

__match_class__ must be an integer and should be exactly one of these:

0
MATCH_SELF = 8

MATCH_SELF is used to indicate that for a single positional argument class pattern, the subject will be used and not deconstructed.

object will have the following values for the special attributes:

__match_container__ = 0
__match_class__= 0
__match_args__ = ()

These special attributes will be inherited as normal.

If __match_args__ is overridden, then it is required to hold a tuple of unique strings. It may be empty.

The pattern matching implementation is not required to check that any of these attributes behave as specified. If the value of __match_container__, __match_class__ or __match_args__ is not as specified, then the implementation may raise any exception, or match the wrong pattern. Of course, implementations are free to check these properties and provide meaningful error messages if they can do so efficiently.

Semantics of the matching process

In the following, all variables of the form $var are temporary variables and are not visible to the Python program. They may be visible via introspection, but that is an implementation detail and should not be relied on. The psuedo-statement FAIL is used to signify that matching failed for this pattern and that matching should move to the next pattern. If control reaches the end of the translation without reaching a FAIL, then it has matched, and following patterns are ignored.

Variables of the form $ALL_CAPS are meta-variables holding a syntactic element, they are not normal variables. So, $VARS = $items is not an assignment of $items to $VARS, but an unpacking of $items into the variables that $VARS holds. For example, with the abstract syntax case [$VARS]:, and the concrete syntax case[a, b]: then $VARS would hold the variables (a, b), not the values of those variables.

The psuedo-function QUOTE takes a variable and returns the name of that variable. For example, if the meta-variable $VAR held the variable foo then QUOTE($VAR) == "foo".

All additional code listed below that is not present in the original source will not trigger line events, conforming to PEP 626.

match expr:

$value = expr

case capture_var:

capture_var = $value

case _:

# No code -- Automatically matches

case LITERAL:

if $value != LITERAL:
    FAIL

if $value is not LITERAL:
    FAIL

case value.pattern:

if $value != value.pattern:
    FAIL

case [$VARS]:

$kind = type($value).__match_container__
if $kind != MATCH_SEQUENCE:
    FAIL
if len($value) != len($VARS):
    FAIL
$VARS = $value

case [$VARS]

$kind = type($value).__match_container__
if $kind != MATCH_SEQUENCE:
    FAIL
if len($value) < len($VARS):
    FAIL
$VARS = $value # Note that $VARS includes a star expression.

case {$KEYWORD_PATTERNS}:

$sentinel = object()
$kind = type($value).__match_container__
if $kind != MATCH_MAPPING:
    FAIL
# $KEYWORD_PATTERNS is a meta-variable mapping names to variables.
for $KEYWORD in $KEYWORD_PATTERNS:
    $tmp = $value.get(QUOTE($KEYWORD), $sentinel)
    if $tmp is $sentinel:
        FAIL
    $KEYWORD_PATTERNS[$KEYWORD] = $tmp

case {$KEYWORD_PATTERNS, **$DOUBLE_STARRED_PATTERN}:

$kind = type($value).__match_container__
if $kind != MATCH_MAPPING:
    FAIL
# $KEYWORD_PATTERNS is a meta-variable mapping names to variables.
$tmp = dict($value)
if not $tmp.keys() >= $KEYWORD_PATTERNS.keys():
    FAIL:
for $KEYWORD in $KEYWORD_PATTERNS:
    $KEYWORD_PATTERNS[$KEYWORD] = $tmp.pop(QUOTE($KEYWORD))
$DOUBLE_STARRED_PATTERN = $tmp

case ClsName():

if not isinstance($value, ClsName):
    FAIL

case ClsName($VAR):

$kind = type($value).__match_class__
if $kind == MATCH_SELF:
    if not isinstance($value, ClsName):
        FAIL
    $VAR = $value
else:
    As other positional-only class pattern

case ClsName($VARS):

if not isinstance($value, ClsName):
    FAIL
$attrs = ClsName.__match_args__
if len($attr) < len($VARS):
    raise TypeError(...)
try:
    for i, $VAR in enumerate($VARS):
        $VAR = getattr($value, $attrs[i])
except AttributeError:
    FAIL

case ClsName($KEYWORD_PATTERNS):

if not isinstance($value, ClsName):
    FAIL
try:
    for $KEYWORD in $KEYWORD_PATTERNS:
        $tmp = getattr($value, QUOTE($KEYWORD))
        $KEYWORD_PATTERNS[$KEYWORD] = $tmp
except AttributeError:
    FAIL

case ClsName($VARS, $KEYWORD_PATTERNS):

if not isinstance($value, ClsName):
    FAIL
$attrs = ClsName.__match_args__
if len($attr) < len($VARS):
    raise TypeError(...)
$pos_attrs = $attrs[:len($VARS)]
try:
    for i, $VAR in enumerate($VARS):
        $VAR = getattr($value, $attrs[i])
    for $KEYWORD in $KEYWORD_PATTERNS:
        $name = QUOTE($KEYWORD)
        if $name in pos_attrs:
            raise TypeError(...)
        $KEYWORD_PATTERNS[$KEYWORD] = getattr($value, $name)
except AttributeError:
    FAIL

case [int(), str()]:

$kind = type($value).__match_class__
if $kind != MATCH_SEQUENCE:
    FAIL
if len($value) != 2:
    FAIL
$value_0, $value_1 = $value
#Now match on temporary values
if not isinstance($value_0, int):
    FAIL
if not isinstance($value_1, str):
    FAIL

case pattern if guard:

[translation for pattern]
if not guard:
    FAIL

__match_container__ == 0 or __match_container__ == MATCH_SEQUENCE or __match_container__ == MATCH_MAPPING
__match_class__ == 0 or __match_class__ == MATCH_SELF

Values of the special attributes for classes in the standard library

For the core builtin container classes __match_container__ will be:

• list: MATCH_SEQUENCE
• tuple: MATCH_SEQUENCE
• dict: MATCH_MAPPING
• bytearray: 0
• bytes: 0
• str: 0

Named tuples will have __match_container__ set to MATCH_SEQUENCE.

• All other standard library classes for which issubclass(cls, collections.abc.Mapping) is true will have __match_container__ set to MATCH_MAPPING.
• All other standard library classes for which issubclass(cls, collections.abc.Sequence) is true will have __match_container__ set to MATCH_SEQUENCE.

For the following builtin classes __match_class__ will be set to MATCH_SELF:

• bool
• bytearray
• bytes
• float
• frozenset
• int
• set
• str
• list
• tuple
• dict

Legal optimizations

The above semantics implies a lot of redundant effort and copying in the implementation. However, it is possible to implement the above semantics efficiently by employing semantic preserving transformations on the naive implementation.

When performing matching, implementations are allowed to treat the following functions and methods as pure:

For any class supporting MATCH_SEQUENCE:

* ``cls.__len__()``
* ``cls.__getitem__()``

For any class supporting MATCH_MAPPING:

* ``cls.get()`` (Two argument form only)

Implementations are allowed to make the following assumptions:

• isinstance(obj, cls) can be freely replaced with issubclass(type(obj), cls) and vice-versa.
• isinstance(obj, cls) will always return the same result for any (obj, cls) pair and repeated calls can thus be elided.
• Reading any of __match_container__, __match_class__ or __match_args__ is a pure operation, and may be cached.
• Sequences, that is any class for which __match_container__ == MATCH_SEQUENCE is not zero, are not modified by iteration, subscripting or calls to len(). Consequently, those operations can be freely substituted for each other where they would be equivalent when applied to an immutable sequence.
• Mappings, that is any class for which __match_container__ == MATCH_MAPPING is not zero, will not capture the second argument of the get() method. So, the $sentinel value may be freely re-used.

In fact, implementations are encouraged to make these assumptions, as it is likely to result in significantly better performance.

Possible optimizations

The following is not part of the specification, but guidelines to help developers create an efficient implementation.

case []:
    A
case [x]:
    B
case [x, y]:
    C
case other:
    D

  # Choose lane
  $i = iter($value)
  for $0 in $i:
      break
  else:
      A
      goto done
  for $1 in $i:
      break
  else:
      x = $0
      B
      goto done
  for $2 in $i:
      del $0, $1, $2
      break
  else:
      x = $0
      y = $1
      C
      goto done
  other = $value
  D
done:

match obj:
    case {a:x, b:y}:
        W
    case {a:x, c:y}:
        X
    case {a:x, b:_, c:y}:
        Y
    case other:
        Z

# Choose lane
if len($value) == 2:
    if "a" in $value:
        if "b" in $value:
            x = $value["a"]
            y = $value["b"]
            goto W
        if "c" in $value:
            x = $value["a"]
            y = $value["c"]
            goto X
elif len($value) == 3:
    if "a" in $value and "b" in $value:
        x = $value["a"]
        y = $value["c"]
        goto Y
other = $value
goto Z

Using attributes from the instance’s dictionary

An earlier version of this PEP only used attributes from the instance’s dictionary when matching a class pattern with __match_class__ was the default value. The intent was to avoid capturing bound-methods and other synthetic attributes. However, this also mean that properties were ignored.

For the class:

class C:
    def __init__(self):
        self.a = "a"
    @property
    def p(self):
        ...
    def m(self):
        ...

Ideally we would match the attributes “a” and “p”, but not “m”. However, there is no general way to do that, so this PEP now follows the semantics of PEP 634.

Lookup of __match_args__ on the subject not the pattern

An earlier version of this PEP looked up __match_args__ on the class of the subject and not the class specified in the pattern. This has been rejected for a few reasons:

* Using the class specified in the pattern is more amenable to optimization and can offer better performance.
* Using the class specified in the pattern has the potential to provide better error reporting is some cases.
* Neither approach is perfect, both have odd corner cases. Keeping the status quo minimizes disruption.

Combining __match_class__ and __match_container__ into a single value

An earlier version of this PEP combined __match_class__ and __match_container__ into a single value, __match_kind__. Using a single value has a small advantage in terms of performance, but is likely to result in unintended changes to container matching when overriding class matching behavior, and vice versa.

Having a separate value to reject all class matches

In an earlier version of this PEP, there was a distinct value for __match_class__ that allowed classes to not match any class pattern that would have required deconstruction. However, this would become redundant once MATCH_POSITIONAL is introduced, and complicates the specification for an extremely rare case.