314 

   315 def _matchtree(pattern, tree, placeholder, incompletenodes, matches):

   316     if pattern == tree:

   317         return True

   318     if not isinstance(pattern, tuple) or not isinstance(tree, tuple):

   319         return False

   320     if pattern == placeholder and tree[0] not in incompletenodes:

   321         matches.append(tree)

   322         return True

   323     if len(pattern) != len(tree):

   324         return False

   325     return all(_matchtree(p, x, placeholder, incompletenodes, matches)

   326                for p, x in zip(pattern, tree))

   327 

   328 def matchtree(pattern, tree, placeholder=None, incompletenodes=()):

   329     """If a tree matches the pattern, return a list of the tree and nodes

   330     matched with the placeholder; Otherwise None

   331 

   332     >>> def f(pattern, tree):

   333     ...     m = matchtree(pattern, tree, _, {'keyvalue', 'list'})

   334     ...     if m:

   335     ...         return m[1:]

   336 

   337     >>> _ = ('symbol', '_')

   338     >>> f(('func', ('symbol', 'ancestors'), _),

   339     ...   ('func', ('symbol', 'ancestors'), ('symbol', '1')))

   340     [('symbol', '1')]

   341     >>> f(('func', ('symbol', 'ancestors'), _),

   342     ...   ('func', ('symbol', 'ancestors'), None))

   343     >>> f(('range', ('dagrange', _, _), _),

   344     ...   ('range',

   345     ...     ('dagrange', ('symbol', '1'), ('symbol', '2')),

   346     ...     ('symbol', '3')))

   347     [('symbol', '1'), ('symbol', '2'), ('symbol', '3')]

   348 

   349     The placeholder does not match the specified incomplete nodes because

   350     an incomplete node (e.g. argument list) cannot construct an expression.

   351 

   352     >>> f(('func', ('symbol', 'ancestors'), _),

   353     ...   ('func', ('symbol', 'ancestors'),

   354     ...     ('list', ('symbol', '1'), ('symbol', '2'))))

   355 

   356     The placeholder may be omitted, but which shouldn't match a None node.

   357 

   358     >>> _ = None

   359     >>> f(('func', ('symbol', 'ancestors'), None),

   360     ...   ('func', ('symbol', 'ancestors'), ('symbol', '0')))

   361     """

   362     if placeholder is not None and not isinstance(placeholder, tuple):

   363         raise error.ProgrammingError('placeholder must be a node tuple')

   364     matches = [tree]

   365     if _matchtree(pattern, tree, placeholder, incompletenodes, matches):

   366         return matches