Cython/Compiler/TreePath.py

   1 """
   2 A simple XPath-like language for tree traversal.
   3
   4 This works by creating a filter chain of generator functions.  Each
   5 function selects a part of the expression, e.g. a child node, a
   6 specific descendant or a node that holds an attribute.
   7 """
   8
   9 import re
  10 import sys
  11
  12 path_tokenizer = re.compile(
  13     "("
  14     "'[^']*'|\"[^\"]*\"|"
  15     "//?|"
  16     "\(\)|"
  17     "==?|"
  18     "[/.*\[\]\(\)@])|"
  19     "([^/\[\]\(\)@=\s]+)|"
  20     "\s+"
  21     ).findall
  22
  23 def iterchildren(node, attr_name):
  24     # returns an iterable of all child nodes of that name
  25     child = getattr(node, attr_name)
  26     if child is not None:
  27         if type(child) is list:
  28             return child
  29         else:
  30             return [child]
  31     else:
  32         return ()
  33
  34 def _get_first_or_none(it):
  35     try:
  36         try:
  37             _next = it.next
  38         except AttributeError:
  39             return next(it)
  40         else:
  41             return _next()
  42     except StopIteration:
  43         return None
  44
  45 def type_name(node):
  46     return node.__class__.__name__.split('.')[-1]
  47
  48 def parse_func(next, token):
  49     name = token[1]
  50     token = next()
  51     if token[0] != '(':
  52         raise ValueError("Expected '(' after function name '%s'" % name)
  53     predicate = handle_predicate(next, token)
  54     return name, predicate
  55
  56 def handle_func_not(next, token):
  57     """
  58     not(...)
  59     """
  60     name, predicate = parse_func(next, token)
  61
  62     def select(result):
  63         for node in result:
  64             if _get_first_or_none(predicate([node])) is None:
  65                 yield node
  66     return select
  67
  68 def handle_name(next, token):
  69     """
  70     /NodeName/
  71     or
  72     func(...)
  73     """
  74     name = token[1]
  75     if name in functions:
  76         return functions[name](next, token)
  77     def select(result):
  78         for node in result:
  79             for attr_name in node.child_attrs:
  80                 for child in iterchildren(node, attr_name):
  81                     if type_name(child) == name:
  82                         yield child
  83     return select
  84
  85 def handle_star(next, token):
  86     """
  87     /*/
  88     """
  89     def select(result):
  90         for node in result:
  91             for name in node.child_attrs:
  92                 for child in iterchildren(node, name):
  93                     yield child
  94     return select
  95
  96 def handle_dot(next, token):
  97     """
  98     /./
  99     """
 100     def select(result):
 101         return result
 102     return select
 103
 104 def handle_descendants(next, token):
 105     """
 106     //...
 107     """
 108     token = next()
 109     if token[0] == "*":
 110         def iter_recursive(node):
 111             for name in node.child_attrs:
 112                 for child in iterchildren(node, name):
 113                     yield child
 114                     for c in iter_recursive(child):
 115                         yield c
 116     elif not token[0]:
 117         node_name = token[1]
 118         def iter_recursive(node):
 119             for name in node.child_attrs:
 120                 for child in iterchildren(node, name):
 121                     if type_name(child) == node_name:
 122                         yield child
 123                     for c in iter_recursive(child):
 124                         yield c
 125     else:
 126         raise ValueError("Expected node name after '//'")
 127
 128     def select(result):
 129         for node in result:
 130             for child in iter_recursive(node):
 131                 yield child
 132
 133     return select
 134
 135 def handle_attribute(next, token):
 136     token = next()
 137     if token[0]:
 138         raise ValueError("Expected attribute name")
 139     name = token[1]
 140     value = None
 141     try:
 142         token = next()
 143     except StopIteration:
 144         pass
 145     else:
 146         if token[0] == '=':
 147             value = parse_path_value(next)
 148     if sys.version_info >= (2,6) or (sys.version_info >= (2,4) and '.' not in name):
 149         import operator
 150         readattr = operator.attrgetter(name)
 151     else:
 152         name_path = name.split('.')
 153         def readattr(node):
 154             attr_value = node
 155             for attr in name_path:
 156                 attr_value = getattr(attr_value, attr)
 157             return attr_value
 158     if value is None:
 159         def select(result):
 160             for node in result:
 161                 try:
 162                     attr_value = readattr(node)
 163                 except AttributeError:
 164                     continue
 165                 if attr_value is not None:
 166                     yield attr_value
 167     else:
 168         def select(result):
 169             for node in result:
 170                 try:
 171                     attr_value = readattr(node)
 172                 except AttributeError:
 173                     continue
 174                 if attr_value == value:
 175                     yield attr_value
 176     return select
 177
 178 def parse_path_value(next):
 179     token = next()
 180     value = token[0]
 181     if value:
 182         if value[:1] == "'" or value[:1] == '"':
 183             return value[1:-1]
 184         try:
 185             return int(value)
 186         except ValueError:
 187             pass
 188     else:
 189         name = token[1].lower()
 190         if name == 'true':
 191             return True
 192         elif name == 'false':
 193             return False
 194     raise ValueError("Invalid attribute predicate: '%s'" % value)
 195
 196 def handle_predicate(next, token):
 197     token = next()
 198     selector = []
 199     while token[0] != ']':
 200         selector.append( operations[token[0]](next, token) )
 201         try:
 202             token = next()
 203         except StopIteration:
 204             break
 205         else:
 206             if token[0] == "/":
 207                 token = next()
 208
 209         if not token[0] and token[1] == 'and':
 210             return logical_and(selector, handle_predicate(next, token))
 211
 212     def select(result):
 213         for node in result:
 214             subresult = iter((node,))
 215             for select in selector:
 216                 subresult = select(subresult)
 217             predicate_result = _get_first_or_none(subresult)
 218             if predicate_result is not None:
 219                 yield node
 220     return select
 221
 222 def logical_and(lhs_selects, rhs_select):
 223     def select(result):
 224         for node in result:
 225             subresult = iter((node,))
 226             for select in lhs_selects:
 227                 subresult = select(subresult)
 228             predicate_result = _get_first_or_none(subresult)
 229             subresult = iter((node,))
 230             if predicate_result is not None:
 231                 for result_node in rhs_select(subresult):
 232                     yield node
 233     return select
 234
 235
 236 operations = {
 237     "@":  handle_attribute,
 238     "":   handle_name,
 239     "*":  handle_star,
 240     ".":  handle_dot,
 241     "//": handle_descendants,
 242     "[":  handle_predicate,
 243     }
 244
 245 functions = {
 246     'not' : handle_func_not
 247     }
 248
 249 def _build_path_iterator(path):
 250     # parse pattern
 251     stream = iter([ (special,text)
 252                     for (special,text) in path_tokenizer(path)
 253                     if special or text ])
 254     try:
 255         _next = stream.next
 256     except AttributeError:
 257         # Python 3
 258         def _next():
 259             return next(stream)
 260     token = _next()
 261     selector = []
 262     while 1:
 263         try:
 264             selector.append(operations[token[0]](_next, token))
 265         except StopIteration:
 266             raise ValueError("invalid path")
 267         try:
 268             token = _next()
 269             if token[0] == "/":
 270                 token = _next()
 271         except StopIteration:
 272             break
 273     return selector
 274
 275 # main module API
 276
 277 def iterfind(node, path):
 278     selector_chain = _build_path_iterator(path)
 279     result = iter((node,))
 280     for select in selector_chain:
 281         result = select(result)
 282     return result
 283
 284 def find_first(node, path):
 285     return _get_first_or_none(iterfind(node, path))
 286
 287 def find_all(node, path):
 288     return list(iterfind(node, path))