qalgebra.pattern_matching module¶

QNET’s pattern matching engine.

Patterns may be constructed by either instantiating a Pattern instance directly, or (preferred) by calling the pattern(), pattern_head(), or wc() helper routines.

The pattern may then be matched against an expression using match_pattern(). The result of a match is a MatchDict object, which evaluates to True or False in a boolean context to indicate the success or failure of the match (or alternatively, through the success attribute). The MatchDict object also maps any wildcard names to the expression that the corresponding wildcard Pattern matches.

Summary¶

Classes:

`MatchDict`	Result of a `Pattern.match()`.
`Pattern`	Pattern for matching an expression.
`ProtoExpr`	Object representing an un-instantiated `Expression`.

Functions:

`match_pattern`	Recursively match expr with the given expr_or_pattern.
`pattern`	‘Flat’ constructor for `Pattern`.
`pattern_head`	Constructor for a `Pattern` matching a `ProtoExpr`.
`wc`	Constructor for a wildcard-`Pattern`.

__all__: MatchDict, Pattern, match_pattern, pattern, pattern_head, wc

Reference¶

class qalgebra.pattern_matching.MatchDict(*args)[source]¶

Bases: collections.OrderedDict

Result of a Pattern.match().

Dictionary of wildcard names to expressions. Once the value for a key is set, attempting to set it again with a different value raises a KeyError. The attribute merge_lists may be set to modify this behavior for values that are lists: If it is set to a value different from zero, two lists that are set via the same key are merged. If merge_lists is negative, the new values are appended to the existing values; if it is positive, the new values are prepended.

In a boolean context, a MatchDict always evaluates as True (even if empty, unlike a normal dictionary), unless the success attribute is explicitly set to False (which a failed Pattern.match() should do)

Attributes

success (bool) – Value of the MatchDict object in a boolean context: bool(match) == match.success
reason (str) – If success is False, string explaining why the match failed
merge_lists (int) – Code that indicates how to combine multiple values that are lists

update(*others)[source]¶

Update dict with entries from other

If other has an attribute success=False and reason, those attributes are copied as well

class qalgebra.pattern_matching.Pattern(head=None, args=None, kwargs=None, *, mode=1, wc_name=None, conditions=None)[source]¶

Bases: object

Pattern for matching an expression.

Parameters

head (type or None) – The type (or tuple of types) of the expression that can be matched. If None, any type of Expression matches
args (list or None) – List or tuple of positional arguments of the matched Expression (cf. Expression.args). Each element is an expression (to be matched exactly) or another Pattern instance (matched recursively). If None, no arguments are checked
kwargs (dict or None) – Dictionary of keyword arguments of the expression (cf. Expression.kwargs). As for args, each value is an expression or Pattern instance.
mode (int) – If the pattern is used to match the arguments of an expression, code to indicate how many arguments the Pattern can consume: Pattern.single, Pattern.one_or_more, Pattern.zero_or_more
wc_name (str or None) – If pattern matches an expression, key in the resulting MatchDict for the expression. If None, the match will not be recorded in the result
conditions (List[callable], or None) – If not None, a list of callables that take expr and return a boolean value. If the return value is False, the pattern is determined not to match expr.

Note

For (sub-)patterns that occur nested in the args attribute of another pattern, only the first or last sub-pattern may have a mode other than Pattern.single. This also implies that only one of the args may have a mode other than Pattern.single. This restrictions ensures that patterns can be matched without backtracking, thus guaranteeing numerical efficiency.

single = 1¶

one_or_more = 2¶

zero_or_more = 3¶

extended_arg_patterns()[source]¶

Iterator over patterns for positional arguments to be matched.

This yields the elements of args, extended by their mode value.

match(expr)[source]¶

Match the given expression (recursively).

Returns a MatchDict instance that maps any wildcard names to the expressions that the corresponding wildcard pattern matches. For (sub-)pattern that have a mode attribute other than Pattern.single, the wildcard name is mapped to a list of all matched expression.

If the match is successful, the resulting MatchDict instance will evaluate to True in a boolean context. If the match is not successful, it will evaluate as False, and the reason for failure is available in the reason attribute of the MatchDict object.

Return type: MatchDict

findall(expr)[source]¶: list of all matching (sub-)expressions in expr

See also

finditer() yields the matches (MatchDict instances) for the matched expressions.

finditer(expr)[source]¶

Return an iterator over all matches in expr

Iterate over all MatchDict results of matches for any matching (sub-)expressions in expr. The order of the matches conforms to the equivalent matched expressions returned by findall().

property wc_names¶: Set of all wildcard names occurring in the pattern.

qalgebra.pattern_matching.match_pattern(expr_or_pattern, expr)[source]¶

Recursively match expr with the given expr_or_pattern.

Parameters

expr_or_pattern (object) – either a direct expression (equal to expr for a successful match), or an instance of Pattern.
expr (object) – the expression to be matched

Return type

MatchDict

qalgebra.pattern_matching.pattern(head, *args, mode=1, wc_name=None, conditions=None, **kwargs)[source]¶

‘Flat’ constructor for Pattern.

Positional and keyword arguments are mapped into args and kwargs, respectively. Useful for defining rules that match an instantiated Expression with specific arguments

Return type: Pattern

qalgebra.pattern_matching.pattern_head(*args, conditions=None, wc_name=None, **kwargs)[source]¶

Constructor for a Pattern matching a ProtoExpr.

The patterns associated with _rules and _binary_rules` of an Expression subclass, or those passed to Expression.add_rule(), must be instantiated through this routine. The function does not allow to set a wildcard name (wc_name must not be given / be None)

Return type: Pattern

qalgebra.pattern_matching.wc(name_mode='_', head=None, args=None, kwargs=None, *, conditions=None)[source]¶

Constructor for a wildcard-Pattern.

Helper function to create a Pattern object with an emphasis on wildcard patterns, if we don’t care about the arguments of the matched expressions (otherwise, use pattern())

Parameters

name_mode (str) – Combined wc_name and mode for Pattern constructor argument. See below for syntax
head (type, or None) – See Pattern
args (list or None) – See Pattern
kwargs (dict or None) – See Pattern
conditions (list or None) – See Pattern

The name_mode argument uses trailing underscored to indicate the mode:

A -> Pattern(wc_name="A", mode=Pattern.single, ...)

A_ -> Pattern(wc_name="A", mode=Pattern.single, ...)

B__ -> Pattern(wc_name="B", mode=Pattern.one_or_more, ...)

B___ -> Pattern(wc_name="C", mode=Pattern.zero_or_more, ...)

Return type: Pattern

class qalgebra.pattern_matching.ProtoExpr(args, kwargs, cls=None)[source]¶

Bases: collections.abc.Sequence

Object representing an un-instantiated Expression.

A ProtoExpr may be matched by a Pattern created via pattern_head(). This is used in Expression.create(): before an expression is instantiated, a ProtoExpr is constructed with the positional and keyword arguments passed to create(). Then, this ProtoExpr is matched against all the automatic rules create() knows about.

Parameters

args (list) – positional arguments that would be used in the instantiation of the Expression
kwargs (dict) – keyword arguments. Will we converted to an OrderedDict
cls – The class of the Expression that will ultimately be instantiated, or None if the class is unknown.

The combined values of args and kwargs are accessible as a (mutable) sequence.

instantiate(cls=None)[source]¶

Return an instantiated Expression.

Equivalent to cls.create(*self.args, **self.kwargs).

Parameters: cls – The class of the instantiated expression. If not given, self.cls will be used.

classmethod from_expr(expr)[source]¶: Instantiate proto-expression from the given Expression.