Preamble

Before any patterns are matched, the expression being matched is evaluated and its kind is determined:

match expr:

translates to:

$value = expr
$kind = type($value).__match_kind__

In addition some helper variables are initialized:

$list = None
$dict = None
$attrs = None
$items = None

Capture patterns

Capture patterns always match, so:

case capture_var if guard:

translates to:

capture_var = $value
if guard:
    DONE

Wildcard patterns

Wildcard patterns always match, so:

case _ if guard:

translates to:

if guard:
    DONE

Literal Patterns

The literal pattern:

case LITERAL if guard:

translates to:

if $value == LITERAL and guard:
    DONE

except when the literal is one of None, True or False , when it translates to:

if $value is LITERAL and guard:
    DONE

Value Patterns

The value pattern:

case value.pattern if guard:

translates to:

if $value == value.pattern and guard:
    DONE

Sequence Patterns

Before matching the first sequence pattern, but after checking that $value is a sequence, $value is converted to a list.

A pattern not including a star pattern:

case [$VARS] if guard:

translates to:

if $kind & MATCH_SEQUENCE:
    if $list is None:
        $list = list($value)
    if len($list) == len($VARS):
        $VARS = $list
        if guard:
           DONE

Example: [2]

A pattern including a star pattern:

case [$VARS] if guard

translates to:

if $kind & MATCH_SEQUENCE:
    if $list is None:
        $list = list($value)
    if len($list) >= len($VARS):
        $VARS = $list # Note that $VARS includes a star expression.
        if guard:
           DONE

Example: [3]

Mapping Patterns

Before matching the first mapping pattern, but after checking that $value is a mapping, $value is converted to a dict.

A pattern not including a double-star pattern:

case {$KEYWORD_PATTERNS} if guard:

translates to:

if $kind & MATCH_MAPPING:
    if $dict is None:
        $dict = dict($value)
    if $dict.keys() == $KEYWORD_PATTERNS.keys():
        # $KEYWORD_PATTERNS is a meta-variable mapping names to variables.
        for $KEYWORD in $KEYWORD_PATTERNS:
            $KEYWORD_PATTERNS[$KEYWORD] = $dict[QUOTE($KEYWORD)]
        if guard:
            DONE

Example: [4]

A pattern including a double-star pattern:

case {$KEYWORD_PATTERNS, **$DOUBLE_STARRED_PATTERN} if guard::

translates to:

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

Example: [5]

Class Patterns

Class pattern with no arguments:

match ClsName() if guard:

translates to:

if $kind & MATCH_CLASS:
    if isinstance($value, ClsName):
        if guard:
            DONE

Class pattern with a single positional pattern:

match ClsName($PATTERN) if guard:

translates to:

if $kind & MATCH_SELF:
    if isinstance($value, ClsName):
        x = $value
        if guard:
            DONE
else:
    As other positional-only class pattern

Positional-only class pattern:

match ClsName($VARS) if guard:

translates to:

if $kind & MATCH_CLASS:
    if isinstance($value, ClsName):
        if $items is None:
            $items = type($value).__deconstruct__($value)
        # $VARS is a meta-variable.
        if len($items) == len($VARS):
            $VARS = $items
            if guard:
                DONE

Class patterns with keyword patterns:

match ClsName($VARS, $KEYWORD_PATTERNS) if guard:

translates to:

if $kind & MATCH_CLASS:
    if isinstance($value, ClsName):
        if $attrs is None:
            $attrs = type($value).__attributes__
        if $items is None:
            $items = type($value).__deconstruct__($value)
        $right_attrs = attrs[len($VARS):]
        if set($right_attrs) >= set($KEYWORD_PATTERNS):
            $VARS = items[:len($VARS)]
            for $KEYWORD in $KEYWORD_PATTERNS:
                $index = $attrs.index(QUOTE($KEYWORD))
                $KEYWORD_PATTERNS[$KEYWORD] = $items[$index]
            if guard:
                DONE

Example: [6]

Class patterns with all keyword patterns:

match ClsName($KEYWORD_PATTERNS) if guard:

translates to:

if $kind & MATCH_CLASS:
    As above with $VARS == ()
elif $kind & MATCH_DEFAULT:
    if isinstance($value, ClsName) and hasattr($value, "__dict__"):
        if $value.__dict__.keys() >= set($KEYWORD_PATTERNS):
            for $KEYWORD in $KEYWORD_PATTERNS:
                $KEYWORD_PATTERNS[$KEYWORD] = $value.__dict__[QUOTE($KEYWORD)]
            if guard:
                DONE

Example: [7]

Non-conforming __match_kind__

All classes should ensure that the the value of __match_kind__ follows the specification. Therefore, implementations can assume, without checking, that all the following are true:

(__match_kind__ & (MATCH_SEQUENCE | MATCH_MAPPING)) != (MATCH_SEQUENCE | MATCH_MAPPING)
(__match_kind__ & (MATCH_SELF | MATCH_CLASS)) != (MATCH_SELF | MATCH_CLASS)
(__match_kind__ & (MATCH_SELF | MATCH_DEFAULT)) != (MATCH_SELF | MATCH_DEFAULT)
(__match_kind__ & (MATCH_DEFAULT | MATCH_CLASS)) != (MATCH_DEFAULT | MATCH_CLASS)

Thus, implementations can assume that __match_kind__ & MATCH_SEQUENCE implies (__match_kind__ & MATCH_MAPPING) == 0, and vice-versa. Likewise for MATCH_SELF, MATCH_CLASS and MATCH_DEFAULT.

If __match_kind__ does not follow the specification, then implementations may treat any of the expressions of the form $kind & MATCH_... above as having any value.

Splitting evaluation into lanes

Since the first step in matching each pattern is check to against the kind, it is possible to combine all the checks against kind into a single multi-way branch at the beginning of the match. The list of cases can then be duplicated into several "lanes" each corresponding to one kind. It is then trivial to remove unmatchable cases from each lane. Depending on the kind, different optimization strategies are possible for each lane. Note that the body of the match clause does not need to be duplicated, just the pattern.

Sequence patterns

This is probably the most complex to optimize and the most profitable in terms of performance. Since each pattern can only match a range of lengths, often only a single length, the sequence of tests can be rewitten in as an explicit iteration over the sequence, attempting to match only those patterns that apply to that sequence length.

For example:

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

Can be compiled roughly as:

  # 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:

Mapping patterns

The best stategy here is probably to form a decision tree based on the size of the mapping and which keys are present. There is no point repeatedly testing for the presence of a key. For example:

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

If the key "a" is not present when checking for case X, there is no need to check it again for Y.

The mapping lane can be implemented, roughly as:

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