class Expression:
    """Base class for all expressions.

    Do not subclass this class directly but rather :class:`Symbol` or :class:`Operation`.
    Creating a direct subclass of Expression might break several (matching) algorithms.

    Attributes:
        head (Optional[Union[type, Atom]]):
            The head of the expression. For an operation, it is the type of the operation (i.e. a subclass of
            :class:`Operation`). For wildcards, it is ``None``. For symbols, it is the symbol itself.
    """

    def __init__(self, variable_name):
        super().__init__()
        self.variable_name = variable_name

    @cached_property
    def variables(self) -> MultisetOfVariables:
        """A multiset of the variables occurring in the expression."""
        variables = Multiset()
        self.collect_variables(variables)
        return variables

    def collect_variables(self, variables: MultisetOfVariables) -> None:
        """Recursively adds all variables occuring in the expression to the given multiset.

        This is used internally by `variables`. Needs to be overwritten by inheriting container expression classes.
        This method can be used when gathering the `variables` of multiple expressions, because only one multiset
        needs to be created and that is more efficient.

        Args:
            variables:
                Multiset of variables. All variables contained in the expression are recursively added to this multiset.
        """
        if self.variable_name is not None:
            variables.add(self.variable_name)

    @cached_property
    def symbols(self) -> MultisetOfStr:
        """A multiset of the symbol names occurring in the expression."""
        symbols = Multiset()
        self.collect_symbols(symbols)
        return symbols

    def collect_symbols(self, symbols: MultisetOfStr) -> None:
        """Recursively adds all symbols occuring in the expression to the given multiset.

        This is used internally by `symbols`. Needs to be overwritten by inheriting expression classes that
        can contain symbols. This method can be used when gathering the `symbols` of multiple expressions, because only
        one multiset needs to be created and that is more efficient.

        Args:
            symbols:
                Multiset of symbols. All symbols contained in the expression are recursively added to this multiset.
        """
        pass

    @cached_property
    def is_constant(self) -> bool:
        """True, iff the expression does not contain any wildcards."""
        return self._is_constant()

    @staticmethod
    def _is_constant() -> bool:
        return True

    @cached_property
    def is_syntactic(self) -> bool:
        """True, iff the expression does not contain any associative or commutative operations or sequence wildcards."""
        return self._is_syntactic()

    @staticmethod
    def _is_syntactic() -> bool:
        return True

    def with_renamed_vars(self, renaming) -> 'Expression':
        """Return a copy of the expression with renamed variables."""
        raise NotImplementedError()

    def preorder_iter(self, predicate: ExprPredicate=None) -> ExpressionsWithPos:
        """Iterates over all subexpressions that match the (optional) `predicate`.

        Args:
            predicate:
                A predicate to filter what expressions are yielded. It gets the expression and if it returns ``True``,
                the expression is yielded.

        Yields:
            Every subexpression along with a position tuple. Each item in the tuple is the position of an operation
            operand:

                - ``()`` is the position of the root element
                - ``(0, )`` that of its first operand
                - ``(0, 1)`` the position of the second operand of the root's first operand.
                - etc.

            A variable's expression always has the position ``0`` relative to the variable, i.e. if the root is a
            variable, then its expression has the position ``(0, )``.
        """
        yield from self._preorder_iter(predicate, ())

    def _preorder_iter(self, predicate: ExprPredicate, position: Tuple[int, ...]) -> ExpressionsWithPos:
        if predicate is None or predicate(self):
            yield self, position

    def __getitem__(self, position: Union[Tuple[int, ...], slice]) -> 'Expression':
        """Return the subexpression at the given position(s).

        It is also possible to use a slice notation to extract a sequence of subexpressions:

        >>> expr = f(a, b, a, c)
        >>> expr[(1, ):(2, )]
        [Symbol('b'), Symbol('a')]

        Args:
            position:
                The position as a tuple. See :meth:`preorder_iter` for its format.
                Alternatively, a range of positions can be passed using the slice notation.

        Returns:
            The subexpression at the given position(s).

        Raises:
            IndexError: If the position is invalid, i.e. it refers to a non-existing subexpression.
        """
        if isinstance(position, slice):
            if len(position.start) != len(position.stop):
                raise IndexError('Invalid slice: Start and stop must have the same length')
            if len(position.start) == 0:
                return [self]
            raise IndexError('Invalid slice: Parent expression is not an operation')
        if len(position) == 0:
            return self
        raise IndexError("Invalid position")

    def __contains__(self, expression: 'Expression') -> bool:
        return self == expression

    def __hash__(self):
        raise NotImplementedError() 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 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 SymbolWildcard(Wildcard):
    """A special `Wildcard` that matches a `Symbol`.

    Attributes:
        symbol_type:
            A subclass of `Symbol` to constrain what the wildcard matches.
            If not specified, the wildcard will match any `Symbol`.
    """

    def __init__(self, symbol_type: Type[Symbol]=Symbol, variable_name=None) -> None:
        """
        Args:
            symbol_type:
                A subclass of `Symbol` to constrain what the wildcard matches.
                If not specified, the wildcard will match any `Symbol`.

        Raises:
            TypeError: if *symbol_type* is not a subclass of `Symbol`.
        """
        super().__init__(1, True, variable_name)

        if not issubclass(symbol_type, Symbol):
            raise TypeError("The type constraint must be a subclass of Symbol")

        self.symbol_type = symbol_type

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

    def __eq__(self, other):
        return (
            isinstance(other, type(self)) and self.symbol_type == other.symbol_type and
            self.variable_name == other.variable_name
        )

    def __hash__(self):
        return hash((SymbolWildcard, self.symbol_type, self.variable_name))

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

    def __str__(self):
        if self.variable_name:
            return '{}_[{!s}]'.format(self.variable_name, self.symbol_type.__name__)
        return '_[{!s}]'.format(self.symbol_type.__name__)

    def __copy__(self) -> 'SymbolWildcard':
        return type(self)(self.symbol_type, self.variable_name) 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 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 AssociativeOperation(metaclass=ABCMeta):
    @classmethod
    def __subclasshook__(cls, C):
        if cls is AssociativeOperation:
            if issubclass(C, Operation) and hasattr(C, 'associative'):
                return C.associative
        return NotImplemented class CommutativeOperation(metaclass=ABCMeta):
    @classmethod
    def __subclasshook__(cls, C):
        if cls is CommutativeOperation:
            if issubclass(C, Operation) and hasattr(C, 'commutative'):
                return C.commutative
        return NotImplemented class Substitution(dict):
    """Special :class:`dict` for substitutions with nicer formatting.

    The key is a variable's name and the value the replacement for it.
    """

    def try_add_variable(self, variable_name: str, replacement: VariableReplacement) -> None:
        """Try to add the variable with its replacement to the substitution.

        This considers an existing replacement and will only succeed if the new replacement
        can be merged with the old replacement. Merging can occur if either the two replacements
        are equivalent. Replacements can also be merged if the old replacement for the variable_name was
        unordered (i.e. a :class:`~.Multiset`) and the new one is an equivalent ordered version of it:

        >>> subst = Substitution({'x': Multiset(['a', 'b'])})
        >>> subst.try_add_variable('x', ('a', 'b'))
        >>> print(subst)
        {x ↦ (a, b)}

        Args:
            variable:
                The name of the variable to add.
            replacement:
                The replacement for the variable.

        Raises:
            ValueError:
                if the variable cannot be merged because it conflicts with the existing
                substitution for the variable_name.
        """
        if variable_name not in self:
            self[variable_name] = replacement.copy() if isinstance(replacement, Multiset) else replacement
        else:
            existing_value = self[variable_name]

            if isinstance(existing_value, tuple):
                if isinstance(replacement, Multiset):
                    if Multiset(existing_value) != replacement:
                        raise ValueError
                elif replacement != existing_value:
                    raise ValueError
            elif isinstance(existing_value, Multiset):
                if not isinstance(replacement, (tuple, list, Multiset)):
                    raise ValueError
                compare_value = Multiset(replacement)
                if existing_value == compare_value:
                    if not isinstance(replacement, Multiset):
                        self[variable_name] = replacement
                else:
                    raise ValueError
            elif replacement != existing_value:
                raise ValueError

    def union_with_variable(self, variable: str, replacement: VariableReplacement) -> 'Substitution':
        """Try to create a new substitution with the given variable added.

        See :meth:`try_add_variable` for a version of this method that modifies the substitution
        in place.

        Args:
            variable_name:
                The name of the variable to add.
            replacement:
                The substitution for the variable.

        Returns:
            The new substitution with the variable_name added or merged.

        Raises:
            ValueError:
                if the variable cannot be merged because it conflicts with the existing
                substitution for the variable.
        """
        new_subst = Substitution(self)
        new_subst.try_add_variable(variable, replacement)
        return new_subst

    def extract_substitution(self, subject: 'expressions.Expression', pattern: 'expressions.Expression') -> bool:
        """Extract the variable substitution for the given pattern and subject.

        This assumes that subject and pattern already match when being considered as linear.
        Also, they both must be :term:`syntactic`, as sequence variables cannot be handled here.
        All that this method does is checking whether all the substitutions for the variables can be unified.
        So, in case it returns ``False``, the substitution is invalid for the match.

        ..warning::

            This method mutates the substitution and will even do so in case the extraction fails.

            Create a copy before using this method if you need to preserve the original substitution.

        Example:

            With an empty initial substitution and a linear pattern, the extraction will always succeed:

            >>> subst = Substitution()
            >>> subst.extract_substitution(f(a, b), f(x_, y_))
            True
            >>> print(subst)
            {x ↦ a, y ↦ b}

            Clashing values for existing variables will fail:

            >>> subst.extract_substitution(b, x_)
            False

            For non-linear patterns, the extraction can also fail with an empty substitution:

            >>> subst = Substitution()
            >>> subst.extract_substitution(f(a, b), f(x_, x_))
            False
            >>> print(subst)
            {x ↦ a}

            Note that the initial substitution got mutated even though the extraction failed!

        Args:
            subject:
                A :term:`syntactic` subject that matches the pattern.
            pattern:
                A :term:`syntactic` pattern that matches the subject.

        Returns:
            ``True`` iff the substitution could be extracted successfully.
        """
        if getattr(pattern, 'variable_name', False):
            try:
                self.try_add_variable(pattern.variable_name, subject)
            except ValueError:
                return False
            return True
        elif isinstance(pattern, expressions.Operation):
            assert isinstance(subject, type(pattern))
            assert op_len(subject) == op_len(pattern)
            op_expression = cast(expressions.Operation, subject)
            for subj, patt in zip(op_iter(op_expression), op_iter(pattern)):
                if not self.extract_substitution(subj, patt):
                    return False
        return True

    def union(self, *others: 'Substitution') -> 'Substitution':
        """Try to merge the substitutions.

        If a variable occurs in multiple substitutions, try to merge the replacements.
        See :meth:`union_with_variable` to see how replacements are merged.

        Does not modify any of the original substitutions.

        Example:

        >>> subst1 = Substitution({'x': Multiset(['a', 'b']), 'z': a})
        >>> subst2 = Substitution({'x': ('a', 'b'), 'y': ('c', )})
        >>> print(subst1.union(subst2))
        {x ↦ (a, b), y ↦ (c), z ↦ a}

        Args:
            others:
                The other substitutions to merge with this one.

        Returns:
            The new substitution with the other substitutions merged.

        Raises:
            ValueError:
                if a variable occurs in multiple substitutions but cannot be merged because the
                substitutions conflict.
        """
        new_subst = Substitution(self)
        for other in others:
            for variable_name, replacement in other.items():
                new_subst.try_add_variable(variable_name, replacement)
        return new_subst

    def rename(self, renaming: Dict[str, str]) -> 'Substitution':
        """Return a copy of the substitution with renamed variables.

        Example:

            Rename the variable *x* to *y*:

            >>> subst = Substitution({'x': a})
            >>> subst.rename({'x': 'y'})
            {'y': Symbol('a')}

        Args:
            renaming:
                A dictionary mapping old variable names to new ones.

        Returns:
            A copy of the substitution where variable names have been replaced according to the given renaming
            dictionary. Names that are not contained in the dictionary are left unchanged.
        """
        return Substitution((renaming.get(name, name), value) for name, value in self.items())

    @staticmethod
    def _match_value_repr_str(value: Union[List['expressions.Expression'], 'expressions.Expression']
                             ) -> str:  # pragma: no cover
        if isinstance(value, (list, tuple)):
            return '({!s})'.format(', '.join(str(x) for x in value))
        if isinstance(value, Multiset):
            return '{{{!s}}}'.format(', '.join(str(x) for x in sorted(value)))
        return str(value)

    def __str__(self):
        return '{{{}}}'.format(
            ', '.join('{!s} ↦ {!s}'.format(k, self._match_value_repr_str(v)) for k, v in sorted(self.items()))
        )

    def __repr__(self):
        return '{{{}}}'.format(', '.join('{!r}: {!r}'.format(k, v) for k, v in sorted(self.items())))

    def __copy__(self):
        return type(self)(self) def is_syntactic(expression):
    """
    Check if the given expression is syntactic, i.e. it does not contain sequence wildcards or
    associative/commutative operations.
    """
    if isinstance(expression, Wildcard):
        return expression.fixed_size
    if isinstance(expression, Expression):
        return expression.is_syntactic
    if isinstance(expression, (AssociativeOperation, CommutativeOperation)):
        return False
    if isinstance(expression, Operation):
        return all(is_syntactic(o) for o in op_iter(expression))
    return True @singledispatch
def op_iter(operation):
    return iter(operation) @singledispatch
def op_len(operation):
    return len(operation) def slot_cached_property(slot):
    """Property with caching for classes with slots.

    This is a wrapper around `cached_property` to be used with classes that have slots.
    It provides an extension of the builtin `property`, that caches the value in a slot after the first access.
    You need to specify which slot to use for the cached value.

    Example:

        First, create a class with a cached property and a slot to hold the cached value:

        >>> class MyClass:
        ...     __slots__ = ('_my_cached_property', )
        ...
        ...     @slot_cached_property('_my_cached_property')
        ...     def my_property(self):
        ...         print('my_property called')
        ...         return 42
        ...
        >>> instance = MyClass()

        Then, access the property and get the computed value:

        >>> instance.my_property
        my_property called
        42

        Now the result is cached and the original method will not be called again:

        >>> instance.my_property
        42

    Args:
        slot:
            The name of the classes slot to use for the cached value.

    Returns:
        The wrapped `cached_property`.
    """

    def _wrapper(getter):
        return cached_property(getter, slot)

    return _wrapper
import itertools
from reprlib import recursive_repr
from typing import (Any, Dict, FrozenSet, Generic, Iterator, List, Optional, Sequence, Set, Tuple, Type, TypeVar, Union)
    from graphviz import Digraph
from ..expressions.expressions import (
    Expression, Operation, Symbol, SymbolWildcard, Wildcard, Pattern, AssociativeOperation, CommutativeOperation
)
from ..expressions.substitution import Substitution
from ..expressions.functions import is_syntactic, op_iter, op_len
from ..utils import slot_cached_property
# -*- coding: utf-8 -*-
"""This module contains various many-to-one matchers for syntactic patterns:

- There `DiscriminationNet` class that is a many-to-one matcher for syntactic patterns.
- The `SequenceMatcher` can be used to match patterns with a common surrounding operation with some fixed
  syntactic patterns.
- The `FlatTerm` representation for an expression flattens the expression's tree structure and allows faster preoder
  traversal.

Furthermore, the module contains some utility functions for working with flatterms.
"""


try:
except ImportError:
    Digraph = None


__all__ = ['FlatTerm', 'is_operation', 'is_symbol_wildcard', 'DiscriminationNet', 'SequenceMatcher']

T = TypeVar('T')

OPERATION_END = ')'
"""Constant used to represent the end of an operation in a :class:`FlatTerm` and :class:`DiscriminationNet`."""

EPSILON = 'ε'
"""Constant used to label an epsilon transition for the :class:`DiscriminationNet`."""


def is_operation(term: Any) -> bool:
    """Return True iff the given term is a subclass of :class:`.Operation`."""
    return isinstance(term, type) and issubclass(term, Operation)


def is_symbol_wildcard(term: Any) -> bool:
    """Return True iff the given term is a subclass of :class:`.Symbol`."""
    return isinstance(term, type) and issubclass(term, Symbol)


def _get_symbol_wildcard_label(state: '_State', symbol: Symbol) -> Type[Symbol]:
    """Return the transition target for the given symbol type from the the given state or None if it does not exist."""
    return next((t for t in state.keys() if is_symbol_wildcard(t) and isinstance(symbol, t)), None)


TermAtom = Union[Symbol, Wildcard, Type[Operation], Type[Symbol], type(OPERATION_END)]
TransitionLabel = Union[Symbol, Type[Operation], Type[Symbol], Type[Wildcard], type(OPERATION_END), type(EPSILON)]


class FlatTerm(Sequence[TermAtom]):
    """A flattened representation of an :class:`.Expression`.

    This is a subclass of list. This representation is similar to the prefix notation generated by
    :meth:`.Expression.preorder_iter`, but contains some additional elements.

    Operation expressions are represented by the :func:`type` of the operation before the operands as well as
    :const:`OPERATION_END` after the last operand of the operation:

    >>> FlatTerm(f(a, b))
    [f, a, b, )]

    Variables are not included in the flatterm representation, only wildcards remain.

    >>> FlatTerm(x_)
    [_]

    Consecutive wildcards are merged, as the :class:`DiscriminationNet` cannot handle multiple consecutive sequence
    wildcards:

    >>> FlatTerm(f(_, _))
    [f, _[2], )]
    >>> FlatTerm(f(_, __, __))
    [f, _[3+], )]

    Furthermore, every :class:`SymbolWildcard` is replaced by its :attr:`~SymbolWildcard.symbol_type`:

    >>> class SpecialSymbol(Symbol):
    ...     pass
    >>> _s = Wildcard.symbol(SpecialSymbol)
    >>> FlatTerm(_s)
    [<class '__main__.SpecialSymbol'>]


    Symbol wildcards are also not merged like other wildcards, because they can never be sequence wildcards:

    >>> FlatTerm(f(_, _s))
    [f, _, <class '__main__.SpecialSymbol'>, )]
    """

    __slots__ = '_terms', '_is_syntactic'

    def __init__(self, expression: Union[Expression, Sequence[TermAtom]]) -> None:
        if isinstance(expression, Expression):
            expression = self._combined_wildcards_iter(self._flatterm_iter(expression))
        self._terms = tuple(expression)

    def __getitem__(self, index):
        return self._terms[index]

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

    def __contains__(self, term):
        return term in self._terms

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

    def __add__(self, other):
        if isinstance(other, FlatTerm):
            return FlatTerm(self._terms + other._terms)
        if isinstance(other, Sequence):
            return FlatTerm(self._terms + tuple(other))
        return NotImplemented

    def __eq__(self, other):
        if isinstance(other, FlatTerm):
            return self._terms == other._terms
        return NotImplemented

    @slot_cached_property('_is_syntactic')

    def is_syntactic(self):