Syntax-Matching.txt

======================
Matching Python Syntax
======================

The ``peak.rules.syntax`` module allows you to define pattern-matching
predicates against snippets of parameterized Python code, such that a
rule expression like::

    syntax.match(expr, type(`x`) is `y`) and isinstance(y, Const)

Will return true if ``expr`` is a PEAK-Rules AST of the form::

    Compare(Call(Const(type), (v1,)), ('is', Const(v2)))

(where v1 and v2 are arbitrary values).


.. contents:: **Table of Contents**


Bind Variables
==============

Bind variables are placeholders in a pattern that "bind" themselves to the
value found in that location in the matched data structure.  Thus, in the
example above, ```x``` and ```y``` are bind variables, and cause "y"
in the later part of the expression to refer to the right-hand side of the
``is`` operator being matched.  (The arbitrary value ``v2`` in the example
above.)

Bind variables are represented within a tree as an AST node created from the
variable name::

    >>> from peak.rules.syntax import Bind

    >>> Bind('x')
    Bind('x')


Compiling Tree-Match Predicates
===============================

The ``match_predicate(pattern, expr, binds)`` function is used to combine a
pattern AST and an expression AST to create a PEAK-Rules predicate object that
will match the specified pattern.  The `binds` argument is a dictionary mapping
from bind-variable names to lists of expression ASTs, and is modified in-place
as the predicate is assembled::

    >>> from peak.rules.syntax import match_predicate

Rules defined for this function will determine what to do based on the type of
`pattern`.  If `pattern` is a bind variable, the `binds` dictionary is updated
in-place, inserting `expr` under the bind variable's name, and ``True`` is
returned, indicating that this part of the pattern will always match::

    >>> from peak.util.assembler import Local
    >>> b = {}

    >>> match_predicate(Bind('x'), Local('y'), b)
    True

    >>> b
    {'x': [Local('y')]}

If there's already an entry for that variable in the `binds` dictionary, a more
complex predicate is returned, performing an equality comparison between the
new binding and the old binding of the variable, and the value in `binds` is
updated::

    >>> match_predicate(Bind('x'), Local('z'), b)
    Test(Truth(Compare(Local('z'), (('==', Local('y')),))), True)


This is so that patterns like "`x` is not `x`" will actually compare the two
"x"s and see if they're equal.  Of course, if you bind the same variable more
than once to equal expression ASTs, you will not get back a comparison, and
the `binds` will be unchanged::

    >>> match_predicate(Bind('x'), Local('z'), b)
    True

    >>> b
    {'x': [Local('y'), Local('z')]}

Finally, there is a special exception for bind variables named ```_```: that
is, a single underscore.  Bind variables of this name are never stored in the
`binds`, and always return ``True`` as a predicate, allowing you to use them as
"don't care" placeholders::

    >>> any = Bind('_')
    >>> match_predicate(any, Local('q'), b)
    True

    >>> b
    {'x': [Local('y'), Local('z')]}


Matching Structures and AST nodes
---------------------------------

For most node types other than ``Bind``, the predicates are a bit more complex.
By default, the predicate should be an exact (``istype``) match of the node
type, intersected with a recursive application of ``match_predicate()`` to each
of the target node's children.  For example::

    >>> b = {}
    >>> from peak.util.assembler import *
    >>> from peak.rules.codegen import *

    >>> match_predicate(Add(any, any), Local('q'), b)
    Test(IsInstance(Local('q')), istype(<class '...Add'>, True))

    >>> b
    {}

Each child is defined via a ``Getitem()`` operation on the target node, so that
any placeholders and criteria will target the right part of the tree::

    >>> match_predicate(Add(Bind('x'), Bind('y')), Local('q'), b)
    Test(IsInstance(Local('q')), istype(<class '...Add'>, True))

    >>> b
    {'y': [Getitem(Local('q'), Const(2))],
     'x': [Getitem(Local('q'), Const(1))]}

Non-node patterns are treated as equality comparisons::

    >>> b = {}
    >>> match_predicate(42, Local('q'), b)
    Test(Comparison(Local('q')), Value(42, True))

    >>> b
    {}

Except for ``None``, which produces an ``is None`` test::

    >>> match_predicate(None, Local('q'), b)
    Test(Identity(Local('q')), IsObject(None, True))

    >>> b
    {}

And sequences are matched by comparing their length::

    >>> match_predicate((), Local('q'), b)
    Test(Comparison(Call(Const(<... len>), (Local('q'),),...)), Value(0, True))

    >>> match_predicate([], Local('q'), b)
    Test(Comparison(Call(Const(<... len>), (Local('q'),),...)), Value(0, True))

    >>> b
    {}

And recursively matching their contents::

    >>> match_predicate((Bind('x'), Add(Bind('y'), any)), Local('q'), b)
    Signature([Test(Comparison(Call(Const(<... len>), (Local('q'),),...)),
                    Value(2, True)),
               Test(IsInstance(Getitem(Local('q'), Const(1))),
                    istype(<class '...Add'>, True))])

    >>> b
    {'y': [Getitem(Getitem(Local('q'), Const(1)), Const(1))],
     'x': [Getitem(Local('q'), Const(0))]}


Parsing Syntax Patterns
=======================

The ``syntax.SyntaxBuilder`` class is used to parse Python expressions into
AST patterns suitable for use with ``match_predicate``::

    >>> from peak.rules.syntax import SyntaxBuilder, match
    >>> builder = SyntaxBuilder({}, locals(), globals(), __builtins__)
    >>> pe = builder.parse

It parses backquoted identifiers into ``Bind`` nodes:

    >>> pe('type(`x`) is `y`')
    Compare(Call(Const(<type 'type'>), (Bind('x'),), (), (), (), True),
            (('is', Bind('y')),))

And rejects all other use of backquotes::

    >>> pe('`type(x)`')
    Traceback (most recent call last):
      ...
    SyntaxError: backquotes may only be used around an indentifier

In all other respects, it's essentially the same as ``codegen.ExprBuilder``.


The ``match()`` Pseudo-function
-------------------------------

This isn't really a function, but you can use it in a predicate string in order
to perform a pattern match on a PEAK-Rules AST.  It's mainly intended for use
in extending PEAK-Rules to recognize and replace various kinds of subexpression
patterns (e.g. by adding rules to ``predicates.expressionSignature()``), but it
can of course also be used in any other tools you build atop PEAK-Rules'
expression machinery.

In this example, we show it being used to define a rule that will recognize
expressions of the form ``"type(x) is y"``, where x and y are arbitrary
expressions::

    >>> from peak.rules.syntax import match

    >>> from peak.rules.predicates import CriteriaBuilder
    >>> builder = CriteriaBuilder(
    ...     {'expr':Local('expr')}, locals(), globals(), __builtins__
    ... )
    >>> pe = builder.parse

    >>> pe('match(expr, type(`x`) is `y`)')
    Signature([Test(IsInstance(Local('expr')),
                    istype(<class 'peak.util.assembler.Compare'>, True)),
               Test(IsInstance(Getitem(Local('expr'), Const(1))),
                    istype(<class 'peak.util.assembler.Call'>, True)),
               Test(Comparison(Getitem(Getitem(Local('expr'), Const(1)),
                                       Const(1))),
                    Value(Const(<type 'type'>), True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Getitem(Local('expr'),
                                             Const(1)), Const(2)),), (),
                                    (), (), True)),
                               Value(1, True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Getitem(Local('expr'), Const(1)),
                                             Const(3)),), (), (), (), True)),
                               Value(0, True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Getitem(Local('expr'), Const(1)),
                                             Const(4)),), (), (), (), True)),
                               Value(0, True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Getitem(Local('expr'), Const(1)),
                                             Const(5)),), (), (), (), True)),
                               Value(0, True)),
               Test(Comparison(Getitem(Getitem(Local('expr'), Const(1)),
                                       Const(6))),
                               Value(True, True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Local('expr'), Const(2)),), (),
                                    (), (), True)),
                               Value(1, True)),
               Test(Comparison(Call(Const(<... len>),
                                    (Getitem(Getitem(Local('expr'), Const(2)),
                                             Const(0)),), (), (), (), True)),
                               Value(2, True)),
               Test(Comparison(Getitem(Getitem(Getitem(Local('expr'),
                                                       Const(2)), Const(0)),
                                       Const(0))),
                               Value('is', True))])

    >>> builder.bindings[0]
    {'y': Getitem(Getitem(Getitem(Local('expr'), Const(2)), Const(0)), Const(1)),
     'x': Getitem(Getitem(Getitem(Local('expr'), Const(1)), Const(2)), Const(0))}