matchpy.matching.many_to_one module

Contains the ManyToOneMatcher which can be used for fast many-to-one matching.

You can initialize the matcher with a list of the patterns that you wish to match:

>>> pattern1 = Pattern(f(a, x_))
>>> pattern2 = Pattern(f(y_, b))
>>> matcher = ManyToOneMatcher(pattern1, pattern2)

You can also add patterns later:

>>> pattern3 = Pattern(f(a, b))
>>> matcher.add(pattern3)

A pattern can be added with a label which is yielded instead of the pattern during matching:

>>> pattern4 = Pattern(f(x_, y_))
>>> matcher.add(pattern4, "some label")

Then you can match a subject against all the patterns at once:

>>> subject = f(a, b)
>>> matches = matcher.match(subject)
>>> for matched_pattern, substitution in sorted(map(lambda m: (str(m[0]), str(m[1])), matches)):
...     print('{} matched with {}'.format(matched_pattern, substitution))
f(a, b) matched with {}
f(a, x_) matched with {x ↦ b}
f(y_, b) matched with {y ↦ a}
some label matched with {x ↦ a, y ↦ b}

Also contains the ManyToOneReplacer which can replace a set ReplacementRule at one using a ManyToOneMatcher for finding the matches.

class ManyToOneMatcher(*patterns, rename=True)

Bases: object

__init__(*patterns, rename=True) → None
Parameters:*patterns – The patterns which the matcher should match.
classmethod _collect_variable_renaming(expression: matchpy.expressions.expressions.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.

_internal_add(pattern: matchpy.expressions.expressions.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.

Parameters:pattern – The pattern to add.
Returns:The internal id for the pattern. This is mainly used by the CommutativeMatcher.
add(pattern: matchpy.expressions.expressions.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.

Parameters:
  • pattern – The pattern to add.
  • label – An optional label for the pattern. Defaults to the pattern itself.
as_graph() → None
constraint_vars
constraints
finals
is_match(subject: matchpy.expressions.expressions.Expression) → bool

Check if the subject matches any of the matcher’s patterns.

Parameters:subject – The subject to match.
Returns:True, if the subject is matched by any of the matcher’s patterns. False, otherwise.
match(subject: matchpy.expressions.expressions.Expression) → Iterator[Tuple[matchpy.expressions.expressions.Expression, matchpy.expressions.substitution.Substitution]]

Match the subject against all the matcher’s patterns.

Parameters:subject – The subject to match.
Yields:For every match, a tuple of the matching pattern and the match substitution.
pattern_vars
patterns
rename
root
states
class ManyToOneReplacer(*rules)

Bases: object

Class that contains a set of replacement rules and can apply them efficiently to an expression.

__init__(*rules)

A replacement rule consists of a pattern, that is matched against any subexpression of the expression. If a match is found, the replacement callback of the rule is called with the variables from the match substitution. Whatever the callback returns is used as a replacement for the matched subexpression. This can either be a single expression or a sequence of expressions, which is then integrated into the surrounding operation in place of the subexpression.

Note that the pattern can therefore not be a single sequence variable/wildcard, because only single expressions will be matched.

Parameters:*rules – The replacement rules.
add(rule: matchpy.functions.ReplacementRule) → None

Add a new rule to the replacer.

Parameters:rule – The rule to add.
replace(expression: matchpy.expressions.expressions.Expression, max_count: int = inf) → Union[matchpy.expressions.expressions.Expression, Sequence[matchpy.expressions.expressions.Expression]]

Replace all occurrences of the patterns according to the replacement rules.

Parameters:
  • expression – The expression to which the replacement rules are applied.
  • max_count – If given, at most max_count applications of the rules are performed. Otherwise, the rules are applied until there is no more match. If the set of replacement rules is not confluent, the replacement might not terminate without a max_count set.
Returns:

The resulting expression after the application of the replacement rules. This can also be a sequence of expressions, if the root expression is replaced with a sequence of expressions by a rule.

replace_post_order(expression: matchpy.expressions.expressions.Expression) → Union[matchpy.expressions.expressions.Expression, Sequence[matchpy.expressions.expressions.Expression]]

Replace all occurrences of the patterns according to the replacement rules.

Replaces innermost expressions first.

Parameters:
  • expression – The expression to which the replacement rules are applied.
  • max_count – If given, at most max_count applications of the rules are performed. Otherwise, the rules are applied until there is no more match. If the set of replacement rules is not confluent, the replacement might not terminate without a max_count set.
Returns:

The resulting expression after the application of the replacement rules. This can also be a sequence of expressions, if the root expression is replaced with a sequence of expressions by a rule.