class CustomConstraint(Constraint):  # pylint: disable=too-few-public-methods
    """Wrapper for lambdas of functions as constraints.

    The parameter names have to be the same as the the variable names in the expression:

    >>> constraint = CustomConstraint(lambda x, y: x.name < y.name)
    >>> pattern = Pattern(f(x_, y_), constraint)
    >>> is_match(f(a, b), pattern)
    True
    >>> is_match(f(b, a), pattern)
    False

    The ordering of the parameters is not important. You only need to have the parameters needed for the constraint,
    not all variables occurring in the pattern.

    Note, that the matching happens from left left to right, so not all variables may have been assigned a value when
    constraint is called. For constraints over multiple variables you should attach the constraint to the last
    variable occurring in the pattern or a surrounding operation.
    """

    def __init__(self, constraint: Callable[..., bool]) -> None:
        """
        Args:
            constraint:
                The constraint callback.

        Raises:
            ValueError:
                If the callback has positional-only or variable parameters (\*args and \*\*kwargs).
        """
        self.constraint = constraint
        signature = inspect.signature(constraint)

        self._variables = OrderedDict()

        for param in signature.parameters.values():
            if param.kind == inspect.Parameter.POSITIONAL_OR_KEYWORD or param.kind == inspect.Parameter.KEYWORD_ONLY:
                self._variables[param.name] = param.name
            elif param.kind == inspect.Parameter.VAR_KEYWORD:
                raise ValueError("Constraint cannot have variable keyword arguments ({})".format(param.name))
            else:
                raise ValueError(
                    "Constraint cannot have positional-only or variable positional arguments ({})".format(param.name)
                )

    @property
    def variables(self):
        return frozenset(self._variables.values())

    def __call__(self, match: substitution.Substitution) -> bool:
        args = dict((name, match[var_name]) for name, var_name in self._variables.items())

        return self.constraint(**args)

    def _get_name(self):
        try:
            return get_short_lambda_source(self.constraint) or self.constraint.__name__
        except Exception:
            return 'UNKNOWN'

    def __str__(self):
        return '({!s})'.format(self._get_name())

    def __repr__(self):
        return 'CustomConstraint({!s})'.format(self._get_name())

    def __eq__(self, other):
        return (
            isinstance(other, CustomConstraint) and self.constraint == other.constraint and
            self._variables == other._variables
        )

    def __hash__(self):
        return hash(self.constraint)

    def with_renamed_vars(self, renaming):
        cc = CustomConstraint(self.constraint)
        for param_name in cc._variables.keys():
            old_name = self._variables[param_name]
            cc._variables[param_name] = renaming.get(old_name, old_name)
        return cc class Symbol(Atom):
    """An atomic constant expression term.

    It is uniquely identified by its name.

    Attributes:
        name (str):
            The symbol's name.
    """

    def __init__(self, name: str, variable_name=None) -> None:
        """
        Args:
            name:
                The name of the symbol that uniquely identifies it.
        """
        super().__init__(variable_name)
        self.name = name
        self.head = self

    def __str__(self):
        if self.variable_name:
            return '{}: {}'.format(self.name, self.variable_name)
        return self.name

    def __repr__(self):
        if self.variable_name:
            return '{!s}({!r}, variable_name={})'.format(type(self).__name__, self.name, self.variable_name)
        return '{!s}({!r})'.format(type(self).__name__, self.name)

    def collect_symbols(self, symbols):
        symbols.add(self.name)

    def with_renamed_vars(self, renaming) -> 'Symbol':
        return type(self)(self.name, variable_name=renaming.get(self.variable_name, self.variable_name))

    def __copy__(self) -> 'Symbol':
        return type(self)(self.name, variable_name=self.variable_name)

    def __lt__(self, other):
        if not isinstance(other, Expression):
            return NotImplemented
        if isinstance(other, Symbol):
            if self.name == other.name:
                return (self.variable_name or '') < (other.variable_name or '')
            return self.name < other.name
        return type(self).__name__ < type(other).__name__

    def __eq__(self, other):
        if not isinstance(other, type(self)):
            return NotImplemented
        return self.name == other.name and self.variable_name == other.variable_name

    def __hash__(self):
        return hash((Symbol, self.name, self.variable_name)) class Pattern:
    """A pattern is a term that can be matched against another subject term.

    A pattern can contain variables and can optionally have constraints attached to it.
    Those constraints a predicates which limit what the pattern can match.
    """

    def __init__(self, expression, *constraints) -> None:
        """
        Args:
            expression:
                The term that forms the pattern.
            *constraints:
                Optional constraints for the pattern.
        """
        self.expression = expression
        self.constraints = constraints

    def __str__(self):
        if not self.constraints:
            return str(self.expression)
        return '{} /; {}'.format(self.expression, ' and '.join(map(str, self.constraints)))

    def __repr__(self):
        if not self.constraints:
            return '{}({})'.format(type(self).__name__, self.expression)
        return '{}({}, constraints={})'.format(type(self).__name__, self.expression, self.constraints)

    def __eq__(self, other):
        if not isinstance(other, Pattern):
            return NotImplemented
        return self.expression == other.expression and self.constraints == other.constraints

    @property
    def is_syntactic(self):
        """True, iff the pattern is :term:`syntactic`."""
        return self.expression.is_syntactic

    @property
    def local_constraints(self):
        """The subset of the pattern constraints which are local.

        A local constraint has a defined non-empty set of dependency variables.
        These constraints can be evaluated once their dependency variables have a substitution.
        """
        return [c for c in self.constraints if c.variables]

    @property
    def global_constraints(self):
        """The subset of the pattern constraints which are global.

        A global constraint does not define dependency variables and can only be evaluated, once the
        match has been completed.
        """
        return [c for c in self.constraints if not c.variables] class Operation(Expression, metaclass=_OperationMeta):
    """Base class for all operations.

    Do not instantiate this class directly, but create a subclass for every operation in your domain.
    You can use :meth:`new` as a shortcut for doing so.
    """

    name = None  # type: str
    """str: Name or symbol for the operator.

    This needs to be overridden in the subclass.
    """

    arity = Arity.variadic  # type: Arity
    """Arity: The arity of the operator.

    Trying to construct an operation expression with a number of operands that does not fit its
    operation's arity will result in an error.
    """

    associative = False
    """bool: True if the operation is associative, i.e. `f(a, f(b, c)) = f(f(a, b), c)`.

    This attribute is used to flatten nested associative operations of the same type.
    Therefore, the `arity` of an associative operation has to have an unconstrained maximum
    number of operand.
    """

    commutative = False
    """bool: True if the operation is commutative, i.e. `f(a, b) = f(b, a)`.

    Note that commutative operations will always be converted into canonical
    form with sorted operands.
    """

    one_identity = False
    """bool: True if the operation with a single argument is equivalent to the identity function.

    This property is used to simplify expressions, e.g. for ``f`` with ``f.one_identity = True``
    the expression ``f(a)`` if simplified to ``a``.
    """

    infix = False
    """bool: True if the name of the operation should be used as an infix operator by str()."""


    unpacked_args_to_init = False
    """bool: True if the class must be instantiated with ``*operands`` instead of ``operands``."""

    def __init__(self, operands: List[Expression], variable_name=None) -> None:
        """Create an operation expression.

        Args:
            *operands
                The operands for the operation expression.

        Raises:
            ValueError:
                if the operand count does not match the operation's arity.
            ValueError:
                if the operation contains conflicting variables, i.e. variables with the same name that match
                different things. A common example would be mixing sequence and fixed variables with the same name in
                one expression.
        """
        super().__init__(variable_name)

        operand_count, variable_count = self._count_operands(operands)

        if not variable_count and operand_count < self.arity.min_count:
            raise ValueError(
                "Operation {!s} got arity {!s}, but got {:d} operands.".
                format(type(self).__name__, self.arity, operand_count)
            )

        if self.arity.fixed_size and operand_count > self.arity.min_count:
            msg = "Operation {!s} got arity {!s}, but got {:d} operands.".format(
                type(self).__name__, self.arity, operand_count
            )
            if self.associative:
                msg += " Associative operations should have a variadic/polyadic arity."
            raise ValueError(msg)

        self.operands = operands

    @staticmethod
    def _count_operands(operands):
        operand_count = 0
        variable = False
        for operand in operands:
            if isinstance(operand, Wildcard):
                operand_count += operand.min_count
                if not operand.fixed_size:
                    variable = True
            else:
                operand_count += 1
        return operand_count, variable

    def __str__(self):
        if self.infix:
            separator = ' {!s} '.format(self.name) if self.name else ''
            value = '({!s})'.format(separator.join(str(o) for o in self.operands))
        else:
            value = '{!s}({!s})'.format(self.name, ', '.join(str(o) for o in self.operands))
        if self.variable_name:
            value = '{}: {}'.format(self.variable_name, value)
        return value

    def __repr__(self):
        operand_str = ', '.join(map(repr, self.operands))
        if self.variable_name:
            return '{!s}({!s}, variable_name={})'.format(type(self).__name__, operand_str, self.variable_name)
        return '{!s}({!s})'.format(type(self).__name__, operand_str)

    @staticmethod
    def new(
            name: str,
            arity: Arity,
            class_name: str=None,
            *,
            associative: bool=False,
            commutative: bool=False,
            one_identity: bool=False,
            infix: bool=False
    ) -> Type['Operation']:
        """Utility method to create a new operation type.

        Example:

        >>> Times = Operation.new('*', Arity.polyadic, 'Times', associative=True, commutative=True, one_identity=True)
        >>> Times
        Times['*', Arity(min_count=2, fixed_size=False), associative, commutative, one_identity]
        >>> str(Times(Symbol('a'), Symbol('b')))
        '*(a, b)'

        Args:
            name:
                Name or symbol for the operator. Will be used as name for the new class if
                `class_name` is not specified.
            arity:
                The arity of the operator as explained in the documentation of `Operation`.
            class_name:
                Name for the new operation class to be used instead of name. This argument
                is required if `name` is not a valid python identifier.

        Keyword Args:
            associative:
                See :attr:`~Operation.associative`.
            commutative:
                See :attr:`~Operation.commutative`.
            one_identity:
                See :attr:`~Operation.one_identity`.
            infix:
                See :attr:`~Operation.infix`.

        Raises:
            ValueError: if the class name of the operation is not a valid class identifier.
        """
        class_name = class_name or name
        if not class_name.isidentifier() or keyword.iskeyword(class_name):
            raise ValueError("Invalid identifier for new operator class.")

        return type(
            class_name, (Operation, ), {
                'name': name,
                'arity': arity,
                'associative': associative,
                'commutative': commutative,
                'one_identity': one_identity,
                'infix': infix
            }
        )

    def __lt__(self, other):
        if not isinstance(other, Expression):
            return NotImplemented
        if not isinstance(other, type(self)) and not isinstance(self, type(other)):
            return type(self).__name__ < type(other).__name__
        if self.name != other.name:
            return self.name < other.name
        if len(self.operands) != len(other.operands):
            return len(self.operands) < len(other.operands)
        for left, right in zip(self.operands, other.operands):
            if left < right:
                return True
            elif right < left:
                return False
        return (self.variable_name or '') < (other.variable_name or '')

    def __eq__(self, other):
        if not isinstance(other, type(self)):
            return NotImplemented
        return (
            len(self.operands) == len(other.operands) and all(x == y for x, y in zip(self.operands, other.operands)) and
            self.variable_name == other.variable_name
        )

    def __iter__(self):
        return iter(self.operands)

    def __len__(self):
        return len(self.operands)

    def __getitem__(self, key: Union[Tuple[int, ...], slice]) -> Expression:
        if isinstance(key, int):
            return self.operands[key]
        if isinstance(key, slice):
            if len(key.start) != len(key.stop):
                raise IndexError('Invalid slice: Start and stop must have the same length')
            if len(key.start) == 0:
                return [self]
            if key.start > key.stop:
                raise IndexError('Invalid slice: Start must come before stop')
            if len(key.start) == 1:
                return self.operands[key.start[0]:key.stop[0] + 1]
            start, *new_start = key.start
            stop, *new_stop = key.stop
            if start != stop:
                raise IndexError('Invalid slice: Start and stop must have the same parent')
            return self.operands[start][new_start:new_stop]
        if isinstance(key, (list, tuple)):
            if len(key) == 0:
                return self
            head, *remainder = key
            return self.operands[head][remainder]
        raise TypeError('Invalid key: {}'.format(key))

    __getitem__.__doc__ = Expression.__getitem__.__doc__

    def __contains__(self, expression: 'Expression') -> bool:
        if self == expression:
            return True
        for operand in self.operands:
            if operand == expression:
                return True
            try:
                if expression in operand:
                    return True
            except TypeError:
                pass
        return False

    def _is_constant(self) -> bool:
        return all(x.is_constant for x in self.operands)

    def _is_syntactic(self) -> bool:
        if self.associative or self.commutative:
            return False
        return all(o.is_syntactic for o in self.operands)

    def collect_variables(self, variables) -> None:
        if self.variable_name:
            variables.add(self.variable_name)
        for operand in self.operands:
            operand.collect_variables(variables)

    def collect_symbols(self, symbols) -> None:
        symbols.add(self.name)
        for operand in self.operands:
            operand.collect_symbols(symbols)

    def _preorder_iter(self, predicate: ExprPredicate=None, position: Tuple[int, ...]=()) -> ExpressionsWithPos:
        if predicate is None or predicate(self):
            yield self, position
        for i, operand in enumerate(self.operands):
            yield from operand._preorder_iter(predicate, position + (i, ))  # pylint: disable=protected-access

    def __hash__(self):
        return hash((self.name, ) + tuple(self.operands))

    def with_renamed_vars(self, renaming) -> 'Operation':
        return type(self)(
            *(o.with_renamed_vars(renaming) for o in self.operands),
            variable_name=renaming.get(self.variable_name, self.variable_name)
        )

    def __copy__(self) -> 'Operation':
        return type(self)(*self.operands, variable_name=self.variable_name) class Arity(_ArityBase):
    """Arity of an operator as (`int`, `bool`) tuple.

    The first component is the minimum number of operands.
    If the second component is ``True``, the operator has fixed width arity. In that case, the first component
    describes the fixed number of operands required.
    If it is ``False``, the operator has variable width arity.
    """
    pass class Wildcard(Atom):
    """A wildcard that matches any expression.

    The wildcard will match any number of expressions between *min_count* and *fixed_size*.
    Optionally, the wildcard can also be constrained to only match expressions satisfying a predicate.

    Attributes:
        min_count (int):
            The minimum number of expressions this wildcard will match.
        fixed_size (bool):
            If ``True``, the wildcard matches exactly *min_count* expressions.
            If ``False``, the wildcard is a sequence wildcard and can match *min_count* or more expressions.
    """

    head = None

    def __init__(self, min_count: int, fixed_size: bool, variable_name=None, optional=None) -> None:
        """
        Args:
            min_count:
                The minimum number of expressions this wildcard will match. Must be a non-negative number.
            fixed_size:
                If ``True``, the wildcard matches exactly *min_count* expressions.
                If ``False``, the wildcard is a sequence wildcard and can match *min_count* or more expressions.

        Raises:
            ValueError: if *min_count* is negative or when trying to create a fixed zero-length wildcard.
        """
        if min_count < 0:
            raise ValueError("min_count cannot be negative")
        if min_count == 0 and fixed_size:
            raise ValueError("Cannot create a fixed zero length wildcard")

        super().__init__(variable_name)
        self.min_count = min_count
        self.fixed_size = fixed_size
        self.optional = optional

    def _is_constant(self) -> bool:
        return False

    def _is_syntactic(self) -> bool:
        return self.fixed_size

    def with_renamed_vars(self, renaming) -> 'Wildcard':
        return type(self)(
            self.min_count, self.fixed_size, variable_name=renaming.get(self.variable_name, self.variable_name)
        )

    @staticmethod
    def dot(name=None) -> 'Wildcard':
        """Create a `Wildcard` that matches a single argument.

        Args:
            name: An optional name for the wildcard.

        Returns:
            A dot wildcard.
        """
        return Wildcard(min_count=1, fixed_size=True, variable_name=name)

    @staticmethod
    def optional(name, default) -> 'Wildcard':
        """Create a `Wildcard` that matches a single argument with a default value.

        If the wildcard does not match, the substitution will contain the
        default value instead.

        Args:
            name:
                The name for the wildcard.
            default:
                The default value of the wildcard.

        Returns:
            A n optional wildcard.
        """
        return Wildcard(min_count=1, fixed_size=True, variable_name=name, optional=default)

    @staticmethod
    def symbol(name: str=None, symbol_type: Type[Symbol]=Symbol) -> 'SymbolWildcard':
        """Create a `SymbolWildcard` that matches a single `Symbol` argument.

        Args:
            name:
                Optional variable name for the wildcard.
            symbol_type:
                An optional subclass of `Symbol` to further limit which kind of symbols are
                matched by the wildcard.

        Returns:
            A `SymbolWildcard` that matches the *symbol_type*.
        """
        if isinstance(name, type) and issubclass(name, Symbol) and symbol_type is Symbol:
            return SymbolWildcard(name)
        return SymbolWildcard(symbol_type, variable_name=name)

    @staticmethod
    def star(name=None) -> 'Wildcard':
        """Creates a `Wildcard` that matches any number of arguments.

        Args:
            name:
                Optional variable name for the wildcard.

        Returns:
            A star wildcard.
        """
        return Wildcard(min_count=0, fixed_size=False, variable_name=name)

    @staticmethod
    def plus(name=None) -> 'Wildcard':
        """Creates a `Wildcard` that matches at least one and up to any number of arguments

        Args:
            name:
                Optional variable name for the wildcard.

        Returns:
            A plus wildcard.
        """
        return Wildcard(min_count=1, fixed_size=False, variable_name=name)

    def __str__(self):
        value = None
        if not self.fixed_size:
            if self.min_count == 0:
                value = '___'
            elif self.min_count == 1:
                value = '__'
        elif self.min_count == 1:
            value = '_'
        if value is None:
            value = '_[{:d}{!s}]'.format(self.min_count, '' if self.fixed_size else '+')
        if self.variable_name:
            value = '{}{}'.format(self.variable_name, value)
        if self.optional is not None:
            value += ': {}'.format(self.optional)
        return value

    def __repr__(self):
        if self.variable_name:
            if self.optional is not None:
                return '{!s}({!r}, {!r}, variable_name={}, optional={})'.format(
                    type(self).__name__, self.min_count, self.fixed_size, self.variable_name, self.optional
                )
            return '{!s}({!r}, {!r}, variable_name={})'.format(
                type(self).__name__, self.min_count, self.fixed_size, self.variable_name
            )
        return '{!s}({!r}, {!r})'.format(type(self).__name__, self.min_count, self.fixed_size)

    def __lt__(self, other):
        if not isinstance(other, Expression):
            return NotImplemented
        if not isinstance(other, Wildcard):
            return type(self).__name__ < type(other).__name__
        if self.min_count != other.min_count or self.fixed_size != other.fixed_size:
            return self.min_count < other.min_count or (self.fixed_size and not other.fixed_size)
        if self.variable_name != other.variable_name:
            return (self.variable_name or '') < (other.variable_name or '')
        if not isinstance(self, SymbolWildcard):
            return isinstance(other, SymbolWildcard)
        if isinstance(other, SymbolWildcard):
            return self.symbol_type.__name__ < other.symbol_type.__name__
        return False

    def __eq__(self, other):
        if not isinstance(other, type(self)):
            return NotImplemented
        return (
            other.min_count == self.min_count and other.fixed_size == self.fixed_size and
            self.variable_name == other.variable_name and
            self.optional == other.optional
        )

    def __hash__(self):
        return hash((Wildcard, self.min_count, self.fixed_size, self.variable_name))

    def __copy__(self) -> 'Wildcard':
        return type(self)(self.min_count, self.fixed_size, variable_name=self.variable_name, optional=self.optional) class ManyToOneMatcher:
    __slots__ = ('patterns', 'states', 'root', 'pattern_vars', 'constraints', 'constraint_vars', 'finals', 'rename', 'commutative_matchers')

    _state_id = 0

    def __init__(self, *patterns: Expression, rename=True) -> None:
        """
        Args:
            *patterns: The patterns which the matcher should match.
        """
        self.patterns = []
        self.states = []
        self.root = self._create_state()
        self.pattern_vars = []
        self.constraints = []
        self.constraint_vars = {}
        self.finals = set()
        self.rename = rename
        self.commutative_matchers = []

        for pattern in patterns:
            self.add(pattern)

    def clear(self):
        """Removes all cached data."""
        for commutative_matcher in self.commutative_matchers:
            commutative_matcher.clear()

    def add(self, pattern: Pattern, label=None) -> None:
        """Add a new pattern to the matcher.

        The optional label defaults to the pattern itself and is yielded during matching. The same pattern can be
        added with different labels which means that every match for the pattern will result in every associated label
        being yielded with that match individually.

        Equivalent patterns with the same label are not added again. However, patterns that are structurally equivalent,
        but have different constraints or different variable names are distinguished by the matcher.

        Args:
            pattern:
                The pattern to add.
            label:
                An optional label for the pattern. Defaults to the pattern itself.
        """
        if label is None:
            label = pattern
        for i, (p, l, _) in enumerate(self.patterns):
            if pattern == p and label == l:
                return i
        # TODO: Avoid renaming in the pattern, use variable indices instead
        renaming = self._collect_variable_renaming(pattern.expression) if self.rename else {}
        self._internal_add(pattern, label, renaming)

    def _internal_add(self, pattern: Pattern, label, renaming) -> int:
        """Add a new pattern to the matcher.

        Equivalent patterns are not added again. However, patterns that are structurally equivalent,
        but have different constraints or different variable names are distinguished by the matcher.

        Args:
            pattern: The pattern to add.

        Returns:
            The internal id for the pattern. This is mainly used by the :class:`CommutativeMatcher`.
        """
        pattern_index = len(self.patterns)
        renamed_constraints = [c.with_renamed_vars(renaming) for c in pattern.local_constraints]
        constraint_indices = [self._add_constraint(c, pattern_index) for c in renamed_constraints]
        self.patterns.append((pattern, label, constraint_indices))
        self.pattern_vars.append(renaming)
        pattern = rename_variables(pattern.expression, renaming)
        state = self.root
        patterns_stack = [deque([pattern])]

        self._process_pattern_stack(state, patterns_stack, renamed_constraints, pattern_index)

        return pattern_index

    def _process_pattern_stack(self, state, patterns_stack, renamed_constraints, pattern_index):
        while patterns_stack:
            if patterns_stack[-1]:
                subpattern = patterns_stack[-1].popleft()
                variable_name = getattr(subpattern, 'variable_name', None)
                if isinstance(subpattern, Operation):
                    if isinstance(subpattern, OneIdentityOperation):
                        non_optional, added_subst = check_one_identity(subpattern)
                        if non_optional is not None:
                            stack = [q.copy() for q in patterns_stack]
                            stack[-1].appendleft(non_optional)
                            new_state = self._create_expression_transition(state, _EPS, variable_name, pattern_index, added_subst)
                            self._process_pattern_stack(new_state, stack, renamed_constraints, pattern_index)
                    if not isinstance(subpattern, CommutativeOperation):
                        patterns_stack.append(deque(op_iter(subpattern)))
                state = self._create_expression_transition(state, subpattern, variable_name, pattern_index)
                if isinstance(subpattern, CommutativeOperation):
                    subpattern_id = state.matcher.add_pattern(subpattern, renamed_constraints)
                    state = self._create_simple_transition(state, subpattern_id, pattern_index)
            else:
                patterns_stack.pop()
                if len(patterns_stack) > 0:
                    state = self._create_simple_transition(state, OPERATION_END, pattern_index)
        self.finals.add(state.number)


    def _add_constraint(self, constraint, pattern):
        index = None
        for i, (c, patterns) in enumerate(self.constraints):
            if c == constraint:
                patterns.add(pattern)
                index = i
                break
        else:
            index = len(self.constraints)
            self.constraints.append((constraint, set([pattern])))
        for var in constraint.variables:
            self.constraint_vars.setdefault(var, set()).add(index)
        return index

    def match(self, subject: Expression) -> Iterator[Tuple[Expression, Substitution]]:
        """Match the subject against all the matcher's patterns.

        Args:
            subject: The subject to match.

        Yields:
            For every match, a tuple of the matching pattern and the match substitution.
        """
        return _MatchIter(self, subject)

    def is_match(self, subject: Expression) -> bool:
        """Check if the subject matches any of the matcher's patterns.

        Args:
            subject: The subject to match.

        Return:
            True, if the subject is matched by any of the matcher's patterns.
            False, otherwise.
        """
        return _MatchIter(self, subject).any()

    def _create_expression_transition(
            self, state: _State, expression: Expression, variable_name: Optional[str], index: int, subst=None
    ) -> _State:
        label, head = self._get_label_and_head(expression)
        transitions = state.transitions.setdefault(head, [])
        commutative = isinstance(expression, CommutativeOperation)
        matcher = None
        for transition in transitions:
            if transition.variable_name == variable_name and transition.label == label and transition.subst == subst:
                transition.patterns.add(index)
                if variable_name is not None:
                    constraints = set(
                        self.constraint_vars[variable_name] if variable_name in self.constraint_vars else []
                    )
                    for c in list(constraints):
                        patterns = self.constraints[c][1]
                        if patterns.isdisjoint(transition.patterns):
                            constraints.discard(c)
                    transition.check_constraints.update(constraints)
                state = transition.target
                break
        else:
            if commutative:
                matcher = CommutativeMatcher(type(expression) if isinstance(expression, AssociativeOperation) else None)
                self.commutative_matchers.append(matcher)
            state = self._create_state(matcher)
            if variable_name is not None:
                constraints = set(self.constraint_vars[variable_name] if variable_name in self.constraint_vars else [])
                for c in list(constraints):
                    patterns = self.constraints[c][1]
                    if index not in patterns:
                        constraints.discard(c)
            else:
                constraints = None
            transition = _Transition(label, state, variable_name, {index}, constraints, subst)
            transitions.append(transition)
        return state

    def _create_simple_transition(self, state: _State, label: LabelType, index: int, variable_name=None) -> _State:
        if label in state.transitions:
            transition = state.transitions[label][0]
            transition.patterns.add(index)
            return transition.target
        new_state = self._create_state()
        transition = _Transition(label, new_state, variable_name, {index}, None, None)
        state.transitions[label] = [transition]
        return new_state

    @staticmethod
    def _get_label_and_head(expression: Expression) -> Tuple[LabelType, HeadType]:
        if expression is _EPS:
            return _EPS, None
        if isinstance(expression, Operation):
            head = label = type(expression)
        else:
            label = expression
            if isinstance(label, SymbolWildcard):
                head = label.symbol_type
                label = SymbolWildcard(symbol_type=label.symbol_type)
            elif isinstance(label, Wildcard):
                head = None
                label = Wildcard(label.min_count, label.fixed_size, optional=label.optional)
            elif isinstance(label, Symbol):
                label_copy = copy.copy(label)
                label_copy.variable_name = None
                head = label = label_copy
            else:
                head = expression

        return label, head

    def _create_state(self, matcher: 'CommutativeMatcher'=None) -> _State:
        state = _State(ManyToOneMatcher._state_id, dict(), matcher)
        self.states.append(state)
        ManyToOneMatcher._state_id += 1
        return state

    @classmethod
    def _collect_variable_renaming(
            cls, expression: Expression, position: List[int]=None, variables: Dict[str, str]=None
    ) -> Dict[str, str]:
        """Return renaming for the variables in the expression.

        The variable names are generated according to the position of the variable in the expression. The goal is to
        rename variables in structurally identical patterns so that the automaton contains less redundant states.
        """
        if position is None:
            position = [0]
        if variables is None:
            variables = {}
        if getattr(expression, 'variable_name', False):
            if expression.variable_name not in variables:
                variables[expression.variable_name] = cls._get_name_for_position(position, variables.values())
        position[-1] += 1
        if isinstance(expression, Operation):
            if isinstance(expression, CommutativeOperation):
                for operand in op_iter(expression):
                    position.append(0)
                    cls._collect_variable_renaming(operand, position, variables)
                    position.pop()
            else:
                for operand in op_iter(expression):
                    cls._collect_variable_renaming(operand, position, variables)

        return variables

    @staticmethod
    def _get_name_for_position(position: List[int], variables: Container[str]) -> str:
        new_name = 'i{}'.format('.'.join(map(str, position)))
        if new_name in variables:
            counter = 1
            while '{}_{}'.format(new_name, counter) in variables:
                counter += 1
            new_name = '{}_{}'.format(new_name, counter)
        return new_name

    def as_graph(self) -> Digraph:  # pragma: no cover
        return self._as_graph(None)

    _PATTERN_COLORS = [
        '#2E4272',
        '#7887AB',
        '#4F628E',
        '#162955',
        '#061539',
        '#403075',
        '#887CAF',
        '#615192',
        '#261758',
        '#13073A',
        '#226666',
        '#669999',
        '#407F7F',
        '#0D4D4D',
        '#003333',
    ]

    _CONSTRAINT_COLORS = [
        '#AA3939',
        '#D46A6A',
        '#801515',
        '#550000',
        '#AA6C39',
        '#D49A6A',
        '#804515',
        '#552600',
        '#882D61',
        '#AA5585',
        '#661141',
        '#440027',
    ]

    _VARIABLE_COLORS = [
        '#8EA336',
        '#B9CC66',
        '#677B14',
        '#425200',
        '#5C9632',
        '#B5E196',
        '#85BC5E',
        '#3A7113',
        '#1F4B00',
        '#AAA139',
        '#807715',
        '#554E00',
    ]

    @classmethod
    def _colored_pattern(cls, pid):  # pragma: no cover
        color = cls._PATTERN_COLORS[pid % len(cls._PATTERN_COLORS)]
        return '<font color="{}"><b>p{}</b></font>'.format(color, pid)

    @classmethod
    def _colored_constraint(cls, cid):  # pragma: no cover
        color = cls._CONSTRAINT_COLORS[cid % len(cls._CONSTRAINT_COLORS)]
        return '<font color="{}"><b>c{}</b></font>'.format(color, cid)

    @classmethod
    def _colored_variable(cls, var):  # pragma: no cover
        color = cls._VARIABLE_COLORS[hash(var) % len(cls._VARIABLE_COLORS)]
        return '<font color="{}"><b>{}</b></font>'.format(color, var)

    @classmethod
    def _format_pattern_set(cls, patterns):  # pragma: no cover
        return '{{{}}}'.format(', '.join(map(cls._colored_pattern, patterns)))

    @classmethod
    def _format_constraint_set(cls, constraints):  # pragma: no cover
        return '{{{}}}'.format(', '.join(map(cls._colored_constraint, constraints)))

    def _as_graph(self, finals: Optional[List[str]]) -> Digraph:  # pragma: no cover
        if Digraph is None:
            raise ImportError('The graphviz package is required to draw the graph.')
        graph = Digraph()
        if finals is None:
            patterns = [
                '{}: {} with {}'.format(
                    self._colored_pattern(i), html.escape(str(p.expression)), self._format_constraint_set(c)
                ) for i, (p, l, c) in enumerate(self.patterns)
            ]
            graph.node('patterns', '<<b>Patterns:</b><br/>\n{}>'.format('<br/>\n'.join(patterns)), {'shape': 'box'})

        self._make_graph_nodes(graph, finals)
        if finals is None:
            constraints = [
                '{}: {} for {}'.format(self._colored_constraint(i), html.escape(str(c)), self._format_pattern_set(p))
                for i, (c, p) in enumerate(self.constraints)
            ]
            graph.node(
                'constraints', '<<b>Constraints:</b><br/>\n{}>'.format('<br/>\n'.join(constraints)), {'shape': 'box'}
            )
        self._make_graph_edges(graph)
        return graph

    def _make_graph_nodes(self, graph: Digraph, finals: Optional[List[str]]) -> None:  # pragma: no cover
        state_patterns = {}
        for state in self.states:
            state_patterns.setdefault(state.number, set())
            for transition in itertools.chain.from_iterable(state.transitions.values()):
                state_patterns.setdefault(transition.target.number, set()).update(transition.patterns)
        for state in self.states:
            name = 'n{!s}'.format(state.number)
            if state.matcher:
                has_states = len(state.matcher.automaton.states) > 1
                if has_states:
                    graph.node(name, 'Sub Matcher', {'shape': 'box'})
                subfinals = []
                if has_states:
                    graph.subgraph(state.matcher.automaton._as_graph(subfinals))
                submatch_label = '<<b>Sub Matcher End</b>' if has_states else '<<b>Sub Matcher</b>'
                for pattern_index, subpatterns, variables in state.matcher.patterns.values():
                    var_formatted = ', '.join(
                        '{}[{}]x{}{}{}'.format(self._colored_variable(n), m, c, 'W' if w else '', ': {}'.format(d) if d is not None else '')
                        for (n, c, m, d), w in variables
                    )
                    submatch_label += '<br/>\n{}: {} {}'.format(
                        self._colored_pattern(pattern_index), subpatterns, var_formatted
                    )
                submatch_label += '>'
                end_name = (name + '-end') if has_states else name
                graph.node(end_name, submatch_label, {'shape': 'box'})
                for f in subfinals:
                    graph.edge(f, end_name)
                if has_states:
                    graph.edge(name, 'n{}'.format(state.matcher.automaton.root.number))
            else:
                attrs = {'shape': ('doublecircle' if state.number in self.finals else 'circle')}
                if state.number in _VISITED:
                    attrs['color'] = 'red'
                graph.node(name, str(state.number), attrs)
                if state.number in self.finals:
                    sp = state_patterns[state.number]
                    if finals is not None:
                        finals.append(name + '-out')
                    variables = [
                        '{}: {}'.format(
                            self._colored_pattern(i),
                            ', '.join('{} -&gt; {}'.format(self._colored_variable(o), n) for n, o in r.items())
                        ) for i, r in enumerate(self.pattern_vars) if i in sp
                    ]
                    graph.node(
                        name + '-out', '<<b>Pattern Variables:</b><br/>\n{}>'.format('<br/>\n'.join(variables)),
                        {'shape': 'box'}
                    )
                    graph.edge(name, name + '-out')

    def _make_graph_edges(self, graph: Digraph) -> None:  # pragma: no cover
        for state in self.states:
            for _, transitions in state.transitions.items():
                for transition in transitions:
                    t_label = '<'
                    if transition.variable_name:
                        t_label += '{}: '.format(self._colored_variable(transition.variable_name))
                    t_label += '&epsilon;' if transition.label is _EPS else html.escape(str(transition.label))
                    if is_operation(transition.label):
                        t_label += '('
                    t_label += '<br/>{}'.format(self._format_pattern_set(transition.patterns))
                    if transition.check_constraints is not None:
                        t_label += '<br/>{}'.format(self._format_constraint_set(transition.check_constraints))
                    if transition.subst is not None:
                        t_label += '<br/>{}'.format(html.escape(str(transition.subst)))
                    t_label += '>'

                    start = 'n{!s}'.format(state.number)
                    if state.matcher and len(state.matcher.automaton.states) > 1:
                        start += '-end'
                    end = 'n{!s}'.format(transition.target.number)
                    graph.edge(start, end, t_label) class MockConstraint(Constraint):
    def __init__(self, return_value, *variables, renaming=None):
        self.return_value = return_value
        self.called_with = []
        self._variables = set(variables)
        self.renaming = renaming or {}

    def __call__(self, match):
        self.called_with.append(Substitution(match))
        return self.return_value

    def __eq__(self, other):
        return id(self) == id(other)

    def __hash__(self):
        return hash(id(self))

    def __repr__(self):
        if self.variables:
            return 'MockConstraint({!r}, {}, renaming={!r})'.format(
                self.return_value, ', '.join(map(repr, self.variables)), self.renaming)
        return 'MockConstraint({!r}, renaming={!r})'.format(self.return_value, self.renaming)

    def with_renamed_vars(self, renaming):
        self.renaming.update(renaming)
        return self

    @property
    def variables(self):
        return set(self.renaming.get(v, v) for v in self._variables)

    @property
    def call_count(self):
        return len(self.called_with)

    def assert_called_with(self, args):
        args = dict((self.renaming.get(n, n), v) for n, v in args.items())
        assert args in self.called_with, "Constraint was not called with {}. List of calls: {}".format(
            args, self.called_with
        ) PARAM_MATCHES = {} PARAM_PATTERNS = {}
import pytest
from matchpy.expressions.constraints import CustomConstraint
from matchpy.expressions.expressions import Symbol, Pattern, Operation, Arity, Wildcard
from matchpy.matching.many_to_one import ManyToOneMatcher
from .common import *
from .utils import MockConstraint
from .test_matching import PARAM_MATCHES, PARAM_PATTERNS
# -*- coding: utf-8 -*-



def test_add_duplicate_pattern():
    pattern = Pattern(f(a))
    matcher = ManyToOneMatcher()

    matcher.add(pattern)
    matcher.add(pattern)

    assert len(matcher.patterns) == 1


def test_add_duplicate_pattern_with_different_constraint():
    pattern1 = Pattern(f(a))
    pattern2 = Pattern(f(a), MockConstraint(False))
    matcher = ManyToOneMatcher()

    matcher.add(pattern1)
    matcher.add(pattern2)

    assert len(matcher.patterns) == 2


def test_different_constraints():
    c1 = CustomConstraint(lambda x: len(str(x)) > 1)
    c2 = CustomConstraint(lambda x: len(str(x)) == 1)
    pattern1 = Pattern(f(x_), c1)
    pattern2 = Pattern(f(x_), c2)
    pattern3 = Pattern(f(x_, b), c1)
    pattern4 = Pattern(f(x_, b), c2)
    matcher = ManyToOneMatcher(pattern1, pattern2, pattern3, pattern4)

    subject = f(a)
    results = list(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern2
    assert results[0][1] == {'x': a}

    subject = f(Symbol('longer'), b)
    results = sorted(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern3
    assert results[0][1] == {'x': Symbol('longer')}


def test_different_constraints_with_match_on_operation():
    c1 = CustomConstraint(lambda x: len(str(x)) > 1)
    c2 = CustomConstraint(lambda x: len(str(x)) == 1)
    pattern1 = Pattern(f(x_), c1)
    pattern2 = Pattern(f(x_), c2)
    pattern3 = Pattern(f(x_, b), c1)
    pattern4 = Pattern(f(x_, b), c2)
    matcher = ManyToOneMatcher(pattern1, pattern2, pattern3, pattern4)

    subject = f(a)
    results = list(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern2
    assert results[0][1] == {'x': a}

    subject = f(Symbol('longer'), b)
    results = sorted(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern3
    assert results[0][1] == {'x': Symbol('longer')}


def test_different_constraints_no_match_on_operation():
    c1 = CustomConstraint(lambda x: x == a)
    c2 = CustomConstraint(lambda x: x == b)
    pattern1 = Pattern(f(x_), c1)
    pattern2 = Pattern(f(x_), c2)
    matcher = ManyToOneMatcher(pattern1, pattern2)

    subject = f(c)
    results = list(matcher.match(subject))
    assert len(results) == 0


def test_different_constraints_on_commutative_operation():
    c1 = CustomConstraint(lambda x: len(str(x)) > 1)
    c2 = CustomConstraint(lambda x: len(str(x)) == 1)
    pattern1 = Pattern(f_c(x_), c1)
    pattern2 = Pattern(f_c(x_), c2)
    pattern3 = Pattern(f_c(x_, b), c1)
    pattern4 = Pattern(f_c(x_, b), c2)
    matcher = ManyToOneMatcher(pattern1, pattern2, pattern3, pattern4)

    subject = f_c(a)
    results = list(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern2
    assert results[0][1] == {'x': a}

    subject = f_c(Symbol('longer'), b)
    results = sorted(matcher.match(subject))
    assert len(results) == 1
    assert results[0][0] == pattern3

    assert results[0][1] == {'x': Symbol('longer')}