Repository: quora/pyanalyze
Pull request #376 (2021-12-29 07:16:15)

Add support for pattern matching


Patch:
diff --git a/docs/changelog.md b/docs/changelog.md
index 5922dfa..b69b181 100644
--- a/docs/changelog.md
+++ b/docs/changelog.md
@@ -2,6 +2,7 @@
 
 ## Unreleased
 
+- Support the Python 3.10 `match` statement (#376)
 - Support the walrus (`:=`) operator (#375)
 - Initial support for proposed new "type evaluation"
   mechanism (#374)
diff --git a/pyanalyze/__init__.py b/pyanalyze/__init__.py
index a70c77d..f9a0d78 100644
--- a/pyanalyze/__init__.py
+++ b/pyanalyze/__init__.py
@@ -24,6 +24,7 @@ from . import implementation
 from . import method_return_type
 from . import node_visitor
 from . import options
+from . import patma
 from . import reexport
 from . import safe
 from . import shared_options
@@ -49,6 +50,7 @@ used(extensions.evaluated)
 used(extensions.is_set)
 used(value.UNRESOLVED_VALUE)  # keeping it around for now just in case
 used(reexport)
+used(patma)
 used(checker)
 used(suggested_type)
 used(options)
diff --git a/pyanalyze/error_code.py b/pyanalyze/error_code.py
index 1351e67..2b22a75 100644
--- a/pyanalyze/error_code.py
+++ b/pyanalyze/error_code.py
@@ -88,6 +88,8 @@ class ErrorCode(enum.Enum):
     suggested_return_type = 71
     suggested_parameter_type = 72
     incompatible_override = 73
+    impossible_pattern = 74
+    bad_match = 75
 
 
 # Allow testing unannotated functions without too much fuss
@@ -202,6 +204,8 @@ ERROR_DESCRIPTION = {
     ErrorCode.suggested_return_type: "Suggested return type",
     ErrorCode.suggested_parameter_type: "Suggested parameter type",
     ErrorCode.incompatible_override: "Class attribute incompatible with base class",
+    ErrorCode.impossible_pattern: "Pattern can never match",
+    ErrorCode.bad_match: "Invalid type in match statement",
 }
 
 
diff --git a/pyanalyze/name_check_visitor.py b/pyanalyze/name_check_visitor.py
index 8e691a7..8d66443 100644
--- a/pyanalyze/name_check_visitor.py
+++ b/pyanalyze/name_check_visitor.py
@@ -78,6 +78,7 @@ from .options import (
     StringSequenceOption,
     add_arguments,
 )
+from .patma import PatmaVisitor
 from .shared_options import Paths, ImportPaths, EnforceNoUnused
 from .reexport import ImplicitReexportTracker
 from .safe import safe_getattr, is_hashable, all_of_type
@@ -170,7 +171,6 @@ from .value import (
     GenericValue,
     Value,
     TypeVarValue,
-    CanAssignContext,
     concrete_values_from_iterable,
     unpack_values,
 )
@@ -180,6 +180,12 @@ try:
 except ImportError:
     NamedExpr = Any  # 3.7 and lower
 
+try:
+    from ast import Match
+except ImportError:
+    # 3.9 and lower
+    Match = Any
+
 T = TypeVar("T")
 AwaitableValue = GenericValue(collections.abc.Awaitable, [TypeVarValue(T)])
 KnownNone = KnownValue(None)
@@ -868,7 +874,7 @@ class CallSiteCollector:
             pass
 
 
-class NameCheckVisitor(node_visitor.ReplacingNodeVisitor, CanAssignContext):
+class NameCheckVisitor(node_visitor.ReplacingNodeVisitor):
     """Visitor class that infers the type and value of Python objects and detects errors."""
 
     error_code_enum = ErrorCode
@@ -921,6 +927,8 @@ class NameCheckVisitor(node_visitor.ReplacingNodeVisitor, CanAssignContext):
         self.state = VisitorState.collect_names
         # value currently being assigned
         self.being_assigned = AnyValue(AnySource.inference)
+        # current match target
+        self.match_subject = Composite(AnyValue(AnySource.inference))
         # current class (for inferring the type of cls and self arguments)
         self.current_class = None
         self.current_function_name = None
@@ -4401,6 +4409,41 @@ class NameCheckVisitor(node_visitor.ReplacingNodeVisitor, CanAssignContext):
         else:
             return None
 
+    # Match statements
+
+    def visit_Match(self, node: Match) -> None:
+        subject = self.composite_from_node(node.subject)
+        patma_visitor = PatmaVisitor(self)
+        with qcore.override(self, "match_subject", subject):
+            constraints_to_apply = []
+            subscopes = []
+            for case in node.cases:
+                with self.scopes.subscope() as case_scope:
+                    for constraint in constraints_to_apply:
+                        self.add_constraint(case, constraint)
+
+                    pattern_constraint = patma_visitor.visit(case.pattern)
+                    constraints = [pattern_constraint]
+                    self.add_constraint(case.pattern, pattern_constraint)
+                    if case.guard is not None:
+                        _, guard_constraint = self.constraint_from_condition(case.guard)
+                        self.add_constraint(case.guard, guard_constraint)
+                        constraints.append(guard_constraint)
+
+                    constraints_to_apply.append(
+                        AndConstraint.make(constraints).invert()
+                    )
+                    self._generic_visit_list(case.body)
+                    subscopes.append(case_scope)
+
+                self.yield_checker.reset_yield_checks()
+
+            with self.scopes.subscope() as else_scope:
+                for constraint in constraints_to_apply:
+                    self.add_constraint(node, constraint)
+                subscopes.append(else_scope)
+            self.scopes.combine_subscopes(subscopes)
+
     # Attribute checking
 
     def _record_class_examined(self, cls: type) -> None:
diff --git a/pyanalyze/patma.py b/pyanalyze/patma.py
new file mode 100644
index 0000000..cafbd9a
--- /dev/null
+++ b/pyanalyze/patma.py
@@ -0,0 +1,531 @@
+"""
+
+Visitor for pattern matching.
+
+"""
+
+import ast
+import collections.abc
+from dataclasses import dataclass, replace
+import enum
+import itertools
+
+import qcore
+import pyanalyze
+from typing import (
+    Any,
+    Callable,
+    Container,
+    Optional,
+    Sequence,
+    Set,
+    Tuple,
+    TypeVar,
+    Union,
+)
+
+from pyanalyze.implementation import len_of_value
+from pyanalyze.signature import MappingValue
+
+from .annotations import type_from_value
+from .extensions import CustomCheck
+from .error_code import ErrorCode
+from .stacked_scopes import (
+    NULL_CONSTRAINT,
+    AbstractConstraint,
+    AndConstraint,
+    Composite,
+    Constraint,
+    ConstraintType,
+    OrConstraint,
+    constrain_value,
+)
+from .value import (
+    AnnotatedValue,
+    AnySource,
+    AnyValue,
+    CanAssign,
+    CanAssignContext,
+    CanAssignError,
+    CustomCheckExtension,
+    DictIncompleteValue,
+    KVPair,
+    SequenceIncompleteValue,
+    SubclassValue,
+    TypedValue,
+    Value,
+    KnownValue,
+    flatten_values,
+    kv_pairs_from_mapping,
+    replace_known_sequence_value,
+    unannotate,
+    unite_values,
+    unpack_values,
+    UNINITIALIZED_VALUE,
+)
+
+try:
+    from ast import (
+        MatchAs,
+        MatchClass,
+        MatchMapping,
+        MatchOr,
+        MatchSequence,
+        MatchSingleton,
+        MatchStar,
+        MatchValue,
+    )
+except ImportError:
+    # 3.9 and lower
+    MatchAs = MatchClass = MatchMapping = Any
+    MatchOr = MatchSequence = MatchSingleton = MatchStar = MatchValue = Any
+
+
+# For these types, a single class subpattern matches the whole thing
+_SPECIAL_CLASS_PATTERN_TYPES = {
+    bool,
+    bytearray,
+    bytes,
+    dict,
+    float,
+    frozenset,
+    int,
+    list,
+    set,
+    str,
+    tuple,
+}
+SpecialClassPatternValue = unite_values(
+    *[SubclassValue(TypedValue(typ)) for typ in _SPECIAL_CLASS_PATTERN_TYPES]
+)
+
+
+class SpecialPositionalMatch(enum.Enum):
+    self = 1  # match against self (special behavior for builtins)
+    error = 2  # couldn't figure out the attr, match against Any
+
+
+@dataclass(frozen=True)
+class Exclude(CustomCheck):
+    """A CustomCheck that excludes certain types."""
+
+    excluded: Value
+
+    def can_assign(self, value: Value, ctx: CanAssignContext) -> CanAssign:
+        for subval in flatten_values(value, unwrap_annotated=True):
+            if isinstance(subval, AnyValue):
+                continue
+            can_assign = self.excluded.can_assign(subval, ctx)
+            if not isinstance(can_assign, CanAssignError):
+                return CanAssignError(
+                    f"{subval} is compatible with excluded type {self.excluded}"
+                )
+        return {}
+
+    def __str__(self) -> str:
+        return f"Exclude[{self.excluded}]"
+
+
+T = TypeVar("T")
+MatchableSequence = AnnotatedValue(
+    TypedValue(collections.abc.Sequence),
+    [
+        CustomCheckExtension(
+            Exclude(TypedValue(str) | TypedValue(bytes) | TypedValue(bytearray))
+        )
+    ],
+)
+
+
+@dataclass
+class IsAssignablePredicate:
+    pattern_value: Value
+    ctx: CanAssignContext
+    positive_only: bool
+
+    def __call__(self, value: Value, positive: bool) -> Optional[Value]:
+        compatible = is_overlapping(self.pattern_value, value, self.ctx)
+        if positive:
+            if not compatible:
+                return None
+            if value.is_assignable(self.pattern_value, self.ctx):
+                return self.pattern_value
+        elif not self.positive_only:
+            if compatible:
+                return None
+        return value
+
+
+@dataclass
+class LenPredicate:
+    expected_length: int
+    has_star: bool
+    ctx: CanAssignContext
+
+    def __call__(self, value: Value, positive: bool) -> Optional[Value]:
+        value_len = len_of_value(value)
+        if isinstance(value_len, KnownValue) and isinstance(value_len.val, int):
+            if self.has_star:
+                match = value_len.val >= self.expected_length
+            else:
+                match = value_len.val == self.expected_length
+            if not positive:
+                match = not match
+            if match:
+                return value
+            else:
+                return None
+
+        cleaned = unannotate(value)
+        if (
+            not self.has_star
+            and isinstance(cleaned, TypedValue)
+            and cleaned.typ is tuple
+        ):
+            # Narrow Tuple[...] to a known length
+            arg = cleaned.get_generic_arg_for_type(tuple, self.ctx, 0)
+            return SequenceIncompleteValue(
+                tuple, [arg for _ in range(self.expected_length)]
+            )
+        return value
+
+
+@dataclass
+class PatmaVisitor(ast.NodeVisitor):
+    visitor: "pyanalyze.name_check_visitor.NameCheckVisitor"
+
+    def visit_MatchSingleton(self, node: MatchSingleton) -> AbstractConstraint:
+        self.check_impossible_pattern(node, KnownValue(node.value))
+        return self.make_constraint(ConstraintType.is_value, node.value)
+
+    def visit_MatchValue(self, node: MatchValue) -> AbstractConstraint:
+        pattern_val = self.visitor.visit(node.value)
+        self.check_impossible_pattern(node, pattern_val)
+        if not isinstance(pattern_val, KnownValue):
+            self.visitor.show_error(
+                node,
+                f"Match value is not a literal: {pattern_val}",
+                ErrorCode.internal_error,
+            )
+            return NULL_CONSTRAINT
+
+        def predicate_func(value: Value, positive: bool) -> Optional[Value]:
+            if isinstance(value, KnownValue):
+                try:
+                    if positive:
+                        result = value.val == pattern_val.val
+                    else:
+                        result = value.val != pattern_val.val
+                except Exception:
+                    pass
+                else:
+                    if not result:
+                        return None
+            elif positive:
+                if value.is_assignable(pattern_val, self.visitor):
+                    return pattern_val
+                else:
+                    return None
+            return value
+
+        return self.make_constraint(ConstraintType.predicate, predicate_func)
+
+    def visit_MatchSequence(self, node: MatchSequence) -> AbstractConstraint:
+        self.check_impossible_pattern(node, MatchableSequence)
+        starred_index = index_of(node.patterns, lambda pat: isinstance(pat, MatchStar))
+        if starred_index is None:
+            target_length = len(node.patterns)
+            post_starred_length = None
+        else:
+            target_length = starred_index
+            post_starred_length = len(node.patterns) - 1 - target_length
+        constraints = [
+            self.make_constraint(
+                ConstraintType.predicate,
+                IsAssignablePredicate(
+                    MatchableSequence,
+                    self.visitor,
+                    positive_only=len(node.patterns) > 1 or starred_index is None,
+                ),
+            ),
+            self.make_constraint(
+                ConstraintType.predicate,
+                LenPredicate(
+                    len(node.patterns) - int(starred_index is not None),
+                    starred_index is not None,
+                    self.visitor,
+                ),
+            ),
+        ]
+        unpacked = unpack_values(
+            constrain_value(
+                self.visitor.match_subject.value, AndConstraint.make(constraints)
+            ),
+            self.visitor,
+            target_length,
+            post_starred_length,
+        )
+        if isinstance(unpacked, CanAssignError):
+            unpacked = itertools.repeat(AnyValue(AnySource.generic_argument))
+        for pat, subject in zip(node.patterns, unpacked):
+            with qcore.override(self.visitor, "match_subject", Composite(subject)):
+                constraints.append(self.visit(pat))
+        return AndConstraint.make(constraints)
+
+    def visit_MatchMapping(self, node: MatchMapping) -> AbstractConstraint:
+        self.check_impossible_pattern(node, MappingValue)
+        constraint = self.make_constraint(
+            ConstraintType.predicate,
+            IsAssignablePredicate(
+                MappingValue, self.visitor, positive_only=len(node.keys) > 0
+            ),
+        )
+        constraints = [constraint]
+        subject = constrain_value(self.visitor.match_subject.value, constraint)
+        kv_pairs = kv_pairs_from_mapping(subject, self.visitor)
+        if isinstance(kv_pairs, CanAssignError):
+            kv_pairs = [
+                KVPair(
+                    AnyValue(AnySource.generic_argument),
+                    AnyValue(AnySource.generic_argument),
+                )
+            ]
+        kv_pairs = list(reversed(kv_pairs))
+        optional_pairs = set()
+        removed_pairs = set()
+        for key, pattern in zip(node.keys, node.patterns):
+            key_val = self.visitor.visit(key)
+            value, new_optional_pairs, new_removed_pairs = get_value_from_kv_pairs(
+                kv_pairs, key_val, self.visitor, optional_pairs, removed_pairs
+            )
+            optional_pairs |= new_optional_pairs
+            removed_pairs |= new_removed_pairs
+            if value is UNINITIALIZED_VALUE:
+                self.visitor.show_error(
+                    node,
+                    f"Impossible pattern: {self.visitor.match_subject.value} has no key"
+                    f" {key_val}",
+                    ErrorCode.impossible_pattern,
+                )
+                value = AnyValue(AnySource.error)
+            with qcore.override(self.visitor, "match_subject", Composite(value)):
+                constraints.append(self.visit(pattern))
+        if node.rest is not None:
+            new_kv_pairs = []
+            for kv_pair in kv_pairs:
+                if kv_pair in removed_pairs:
+                    continue
+                if kv_pair in optional_pairs:
+                    kv_pair = replace(kv_pair, is_required=False)
+                new_kv_pairs.append(kv_pair)
+            val = DictIncompleteValue(dict, list(reversed(new_kv_pairs)))
+            self.visitor._set_name_in_scope(node.rest, node, val)
+        return AndConstraint.make(constraints)
+
+    def visit_MatchClass(self, node: MatchClass) -> AbstractConstraint:
+        cls = self.visitor.visit(node.cls)
+        can_assign = TypedValue(type).can_assign(cls, self.visitor)
+        if isinstance(can_assign, CanAssignError):
+            self.visitor.show_error(
+                node.cls,
+                "Class pattern must be a type",
+                ErrorCode.bad_match,
+                detail=str(can_assign),
+            )
+        matched_type = type_from_value(cls, visitor=self.visitor, node=node.cls)
+        self.check_impossible_pattern(node, matched_type)
+        constraint = self.make_constraint(
+            ConstraintType.predicate,
+            # TODO figure out when to turn off positive_only
+            IsAssignablePredicate(
+                matched_type,
+                self.visitor,
+                positive_only=not node.patterns and not node.kwd_patterns,
+            ),
+        )
+        subject = constrain_value(self.visitor.match_subject.value, constraint)
+        subject_composite = self.visitor.match_subject._replace(value=subject)
+        patterns = [
+            (attr, pattern) for attr, pattern in zip(node.kwd_attrs, node.kwd_patterns)
+        ]
+        if node.patterns:
+            match_args = get_match_args(cls, self.visitor)
+            if isinstance(match_args, CanAssignError):
+                self.visitor.show_error(
+                    node.cls,
+                    "Invalid class pattern",
+                    ErrorCode.bad_match,
+                    detail=str(match_args),
+                )
+                match_args = [SpecialPositionalMatch.error for _ in node.patterns]
+            if len(node.patterns) > len(match_args):
+                self.visitor.show_error(
+                    node.cls,
+                    f"{cls} takes at most {len(match_args)} positional subpatterns, but"
+                    f" {len(match_args)} were provided",
+                    ErrorCode.bad_match,
+                    detail=str(match_args),
+                )
+                match_args = [SpecialPositionalMatch.error for _ in node.patterns]
+            patterns = [*zip(match_args, node.patterns), *patterns]
+
+        seen_names = set()
+        for name, _ in patterns:
+            if isinstance(name, str):
+                if name in seen_names:
+                    self.visitor.show_error(
+                        node, f"Duplicate keyword pattern {name}", ErrorCode.bad_match
+                    )
+                seen_names.add(name)
+
+        constraints = [constraint]
+        for name, subpattern in patterns:
+            if name is SpecialPositionalMatch.self:
+                subsubject = subject_composite
+            elif name is SpecialPositionalMatch.error:
+                subsubject = Composite(AnyValue(AnySource.error))
+            else:
+                assert isinstance(name, str)
+                attr = self.visitor.get_attribute(subject_composite, name)
+                if attr is UNINITIALIZED_VALUE:
+                    # It may exist on a child class, so we don't error here.
+                    # This matches pyright's behavior.
+                    subsubject = Composite(AnyValue(AnySource.unreachable))
+                else:
+                    new_varname = self.visitor._extend_composite(
+                        subject_composite, name, subpattern
+                    )
+                    subsubject = Composite(attr, new_varname)
+            with qcore.override(self.visitor, "match_subject", subsubject):
+                constraints.append(self.visit(subpattern))
+
+        return AndConstraint.make(constraints)
+
+    def visit_MatchStar(self, node: MatchStar) -> AbstractConstraint:
+        if node.name is not None:
+            self.visitor._set_name_in_scope(
+                node.name, node, self.visitor.match_subject.value
+            )
+        return NULL_CONSTRAINT
+
+    def visit_MatchAs(self, node: MatchAs) -> AbstractConstraint:
+        val = self.visitor.match_subject.value
+        if node.pattern is None:
+            constraint = NULL_CONSTRAINT
+        else:
+            constraint = self.visit(node.pattern)
+
+        if node.name is not None:
+            val = constrain_value(val, constraint)
+            self.visitor._set_name_in_scope(node.name, node, val)
+
+        return constraint
+
+    def visit_MatchOr(self, node: MatchOr) -> AbstractConstraint:
+        subscopes = []
+        constraints = []
+        for pattern in node.patterns:
+            with self.visitor.scopes.subscope() as subscope:
+                constraints.append(self.visit(pattern))
+                subscopes.append(subscope)
+        self.visitor.scopes.combine_subscopes(subscopes)
+        return OrConstraint.make(constraints)
+
+    def generic_visit(self, node: ast.AST) -> AbstractConstraint:
+        return NULL_CONSTRAINT
+
+    def make_constraint(self, typ: ConstraintType, value: object) -> AbstractConstraint:
+        varname = self.visitor.match_subject.varname
+        if varname is None:
+            return NULL_CONSTRAINT
+        return Constraint(varname, typ, True, value)
+
+    def check_impossible_pattern(self, node: ast.AST, value: Value) -> None:
+        if not is_overlapping(self.visitor.match_subject.value, value, self.visitor):
+            self.visitor.show_error(
+                node,
+                f"Impossible pattern: {self.visitor.match_subject.value} can never be"
+                f" {value}",
+                ErrorCode.impossible_pattern,
+            )
+
+
+def is_overlapping(left: Value, right: Value, ctx: CanAssignContext) -> bool:
+    return left.is_assignable(right, ctx) or right.is_assignable(left, ctx)
+
+
+def index_of(elts: Sequence[T], pred: Callable[[T], bool]) -> Optional[int]:
+    for i, elt in enumerate(elts):
+        if pred(elt):
+            return i
+    return None
+
+
+def get_value_from_kv_pairs(
+    kv_pairs: Sequence[KVPair],
+    key: Value,
+    ctx: CanAssignContext,
+    optional_pairs: Container[KVPair],
+    removed_pairs: Container[KVPair],
+) -> Tuple[Value, Set[KVPair], Set[KVPair]]:
+    """Return the :class:`Value` for a specific key."""
+    possible_values = []
+    covered_keys: Set[Value] = set()
+    new_optional_pairs: Set[KVPair] = set()
+    for pair in kv_pairs:
+        if pair in removed_pairs:
+            continue
+        if not pair.is_many:
+            if isinstance(pair.key, AnnotatedValue):
+                my_key = pair.key.value
+            else:
+                my_key = pair.key
+            if isinstance(my_key, KnownValue):
+                is_required = pair.is_required and pair not in optional_pairs
+                if my_key == key and is_required:
+                    if possible_values:
+                        new_optional_pairs.add(pair)
+                        new_removed_pairs = set()
+                    else:
+                        new_removed_pairs = {pair}
+                    return (
+                        unite_values(*possible_values, pair.value),
+                        new_optional_pairs,
+                        new_removed_pairs,
+                    )
+                elif my_key in covered_keys:
+                    continue
+                elif is_required:
+                    covered_keys.add(my_key)
+        if is_overlapping(key, pair.key, ctx):
+            possible_values.append(pair.value)
+            new_optional_pairs.add(pair)
+    if not possible_values:
+        return UNINITIALIZED_VALUE, set(), set()
+    return unite_values(*possible_values), new_optional_pairs, set()
+
+
+def get_match_args(
+    cls: Value, visitor: "pyanalyze.name_check_visitor.NameCheckVisitor"
+) -> Union[CanAssignError, Sequence[Union[str, SpecialPositionalMatch]]]:
+    if SpecialClassPatternValue.is_assignable(cls, visitor):
+        return [SpecialPositionalMatch.self]
+    match_args_value = visitor.get_attribute(Composite(cls), "__match_args__")
+    if match_args_value is UNINITIALIZED_VALUE:
+        return CanAssignError(f"{cls} has no attribute __match_args__")
+    match_args_value = replace_known_sequence_value(match_args_value)
+    if (
+        not isinstance(match_args_value, SequenceIncompleteValue)
+        or match_args_value.typ is not tuple
+    ):
+        return CanAssignError(
+            f"__match_args__ must be a literal tuple, not {match_args_value}"
+        )
+    match_args = []
+    for i, arg in enumerate(match_args_value.members):
+        if not isinstance(arg, KnownValue) or not isinstance(arg.val, str):
+            return CanAssignError(
+                f"__match_args__ element {i} is {arg}, not a string literal"
+            )
+        match_args.append(arg.val)
+    return match_args


Test patch:
diff --git a/pyanalyze/test_patma.py b/pyanalyze/test_patma.py
new file mode 100644
index 0000000..19b675b
--- /dev/null
+++ b/pyanalyze/test_patma.py
@@ -0,0 +1,160 @@
+# static analysis: ignore
+from .test_node_visitor import skip_before
+from .test_name_check_visitor import TestNameCheckVisitorBase
+
+
+class TestPatma(TestNameCheckVisitorBase):
+    @skip_before((3, 10))
+    def test_singletons(self):
+        self.assert_passes(
+            """
+            from typing import Literal
+            def capybara(x: Literal[True, False, None]):
+                match x:
+                    case True:
+                        assert_is_value(x, KnownValue(True))
+                    case _:
+                        assert_is_value(x, KnownValue(False) | KnownValue(None))
+            """
+        )
+
+    @skip_before((3, 10))
+    def test_value(self):
+        self.assert_passes(
+            """
+            from typing import Literal
+
+            def capybara(x: int):
+                match x:
+                    case None:  # E: impossible_pattern
+                        assert_is_value(x, AnyValue(AnySource.unreachable))
+                    case "x":  # E: impossible_pattern
+                        assert_is_value(x, AnyValue(AnySource.unreachable))
+                    case 3:
+                        assert_is_value(x, KnownValue(3))
+                    case _ if x == 4:
+                        assert_is_value(x, KnownValue(4))
+                    case _:
+                        assert_is_value(x, TypedValue(int))
+            """
+        )
+
+    @skip_before((3, 10))
+    def test_sequence(self):
+        self.assert_passes(
+            """
+            import collections.abc
+            from typing import Tuple
+
+            def capybara(seq: Tuple[int, ...], obj: object):
+                match seq:
+                    case [1, 2, 3]:
+                        assert_is_value(
+                            seq,
+                            SequenceIncompleteValue(
+                                tuple,
+                                [TypedValue(int), TypedValue(int), TypedValue(int)]
+                            )
+                        )
+                    case [1, *x]:
+                        assert_is_value(x, GenericValue(list, [TypedValue(int)]))
+
+                match obj:
+                    case [*x]:
+                        assert_is_value(
+                            obj,
+                            TypedValue(collections.abc.Sequence),
+                            skip_annotated=True
+                        )
+                        assert_is_value(
+                            x,
+                            GenericValue(list, [AnyValue(AnySource.generic_argument)])
+                        )
+
+                assert_is_value(seq[0], TypedValue(int))
+                match seq[0]:
+                    case [1, 2, 3]:  # E: impossible_pattern
+                        pass
+            """
+        )
+
+    @skip_before((3, 10))
+    def test_or(self):
+        self.assert_passes(
+            """
+            import collections.abc
+            from typing import Tuple
+
+            def capybara(obj: object):
+                match obj:
+                    case 1 | 2:
+                        assert_is_value(obj, KnownValue(1) | KnownValue(2))
+                    case (3 as x) | (4 as x):
+                        assert_is_value(x, KnownValue(3) | KnownValue(4))
+            """
+        )
+
+    @skip_before((3, 10))
+    def test_mapping(self):
+        self.assert_passes(
+            """
+            import collections.abc
+            from typing import Tuple
+
+            def capybara(obj: object):
+                match {1: 2, 3: 4, 5: 6}:
+                    case {1: x}:
+                        assert_is_value(x, KnownValue(2))
+                    case {3: 4, **x}:
+                        assert_is_value(x, DictIncompleteValue(
+                            dict, [
+                                KVPair(KnownValue(1), KnownValue(2)),
+                                KVPair(KnownValue(5), KnownValue(6)),
+                            ]
+                        ))
+            """
+        )
+
+    @skip_before((3, 10))
+    def test_class_pattern(self):
+        self.assert_passes(
+            """
+            import collections.abc
+            from typing import Tuple
+
+            class NotMatchable:
+                x: str
+
+            class MatchArgs:
+                __match_args__ = ("x", "y")
+                x: str
+                y: int
+
+            def capybara(obj: object):
+                match obj:
+                    case int(1, 2):  # E: bad_match
+                        pass
+                    case int(2):
+                        assert_is_value(obj, KnownValue(2))
+                    case int("x"):  # E: impossible_pattern
+                        pass
+                    case int():
+                        assert_is_value(obj, TypedValue(int))
+                    case NotMatchable(x="x"):
+                        pass
+                    case NotMatchable("x"):  # E: bad_match
+                        pass
+                    case NotMatchable():
+                        pass
+                    case MatchArgs("x", 1 as y):
+                        assert_is_value(y, KnownValue(1))
+                    case MatchArgs(x) if x == "x":
+                        assert_is_value(x, KnownValue("x"))
+                    case MatchArgs(x):
+                        assert_is_value(x, TypedValue(str))
+                    case MatchArgs("x", x="x"): # E: bad_match
+                        pass
+                    case MatchArgs(1, 2, 3):  # E: bad_match
+                        pass
+            """
+        )