Debian Codegraph @

src/css_selectors/select.py

raw
1 #!/usr/bin/env python
2 # vim:fileencoding=utf-8
3
4
5 __license__ = 'GPL v3'
6 __copyright__ = '2015, Kovid Goyal <kovid at kovidgoyal.net>'
7
8 import itertools
9 import re
10 from collections import OrderedDict, defaultdict
11 from functools import wraps
12 from itertools import chain
13
14 from lxml import etree
15
16 from css_selectors.errors import ExpressionError
17 from css_selectors.ordered_set import OrderedSet
18 from css_selectors.parser import Element, FunctionalPseudoElement, ascii_lower, parse
19 from polyglot.builtins import iteritems, itervalues
20
21 PARSE_CACHE_SIZE = 200
22 parse_cache = OrderedDict()
23 XPATH_CACHE_SIZE = 30
24 xpath_cache = OrderedDict()
25
26 # Test that the string is not empty and does not contain whitespace
27 is_non_whitespace = re.compile(r'^[^ \t\r\n\f]+$').match
28
29
30 def get_parsed_selector(raw):
31 try:
32 return parse_cache[raw]
33 except KeyError:
34 parse_cache[raw] = ans = parse(raw)
35 if len(parse_cache) > PARSE_CACHE_SIZE:
36 parse_cache.pop(next(iter(parse_cache)))
37 return ans
38
39
40 def get_compiled_xpath(expr):
41 try:
42 return xpath_cache[expr]
43 except KeyError:
44 xpath_cache[expr] = ans = etree.XPath(expr)
45 if len(xpath_cache) > XPATH_CACHE_SIZE:
46 xpath_cache.pop(next(iter(xpath_cache)))
47 return ans
48
49
50 class AlwaysIn:
51
52 def __contains__(self, x):
53 return True
54
55
56 always_in = AlwaysIn()
57
58
59 def trace_wrapper(func):
60 @wraps(func)
61 def trace(*args, **kwargs):
62 targs = args[1:] if args and isinstance(args[0], Select) else args
63 print('Called:', func.__name__, 'with args:', targs, kwargs or '')
64 return func(*args, **kwargs)
65 return trace
66
67
68 def normalize_language_tag(tag):
69 """Return a list of normalized combinations for a `BCP 47` language tag.
70
71 Example:
72
73 >>> normalize_language_tag('de_AT-1901')
74 ['de-at-1901', 'de-at', 'de-1901', 'de']
75 """
76 # normalize:
77 tag = ascii_lower(tag).replace('_','-')
78 # split (except singletons, which mark the following tag as non-standard):
79 tag = re.sub(r'-([a-zA-Z0-9])-', r'-\1_', tag)
80 subtags = [subtag.replace('_', '-') for subtag in tag.split('-')]
81 base_tag = (subtags.pop(0),)
82 taglist = {base_tag[0]}
83 # find all combinations of subtags
84 for n in range(len(subtags), 0, -1):
85 for tags in itertools.combinations(subtags, n):
86 taglist.add('-'.join(base_tag + tags))
87 return taglist
88
89
90 INAPPROPRIATE_PSEUDO_CLASSES = frozenset((
91 'active', 'after', 'disabled', 'visited', 'link', 'before', 'focus', 'first-letter', 'enabled', 'first-line', 'hover', 'checked', 'target'))
92
93
94 class Select:
95
96 '''
97
98 This class implements CSS Level 3 selectors
99 (http://www.w3.org/TR/css3-selectors) on an lxml tree, with caching for
100 performance. To use:
101
102 >>> from css_selectors import Select
103 >>> select = Select(root) # Where root is an lxml document
104 >>> print(tuple(select('p.myclass')))
105
106 Tags are returned in document order. Note that attribute and tag names are
107 matched case-insensitively. Class and id values are also matched
108 case-insensitively. Also namespaces are ignored (this is for performance of
109 the common case). The UI related selectors are not implemented, such as
110 :enabled, :disabled, :checked, :hover, etc. Similarly, the non-element
111 related selectors such as ::first-line, ::first-letter, ::before, etc. are
112 not implemented.
113
114 WARNING: This class uses internal caches. You *must not* make any changes
115 to the lxml tree. If you do make some changes, either create a new Select
116 object or call :meth:`invalidate_caches`.
117
118 This class can be easily sub-classed to work with tree implementations
119 other than lxml. Simply override the methods in the ``Tree Integration``
120 block below.
121
122 The caching works by maintaining internal maps from classes/ids/tag
123 names/etc. to node sets. These caches are populated as needed, and used
124 for all subsequent selections. Thus, for best performance you should use
125 the same selector object for finding the matching nodes for multiple
126 queries. Of course, remember not to change the tree in between queries.
127
128 '''
129
130 combinator_mapping = {
131 ' ': 'descendant',
132 '>': 'child',
133 '+': 'direct_adjacent',
134 '~': 'indirect_adjacent',
135 }
136
137 attribute_operator_mapping = {
138 'exists': 'exists',
139 '=': 'equals',
140 '~=': 'includes',
141 '|=': 'dashmatch',
142 '^=': 'prefixmatch',
143 '$=': 'suffixmatch',
144 '*=': 'substringmatch',
145 }
146
147 def __init__(self, root, default_lang=None, ignore_inappropriate_pseudo_classes=False, dispatch_map=None, trace=False):
148 if hasattr(root, 'getroot'):
149 root = root.getroot()
150 self.root = root
151 self.dispatch_map = dispatch_map or default_dispatch_map
152 self.invalidate_caches()
153 self.default_lang = default_lang
154 if trace:
155 self.dispatch_map = {k:trace_wrapper(v) for k, v in iteritems(self.dispatch_map)}
156 if ignore_inappropriate_pseudo_classes:
157 self.ignore_inappropriate_pseudo_classes = INAPPROPRIATE_PSEUDO_CLASSES
158 else:
159 self.ignore_inappropriate_pseudo_classes = frozenset()
160
161 # External API {{{
162 def invalidate_caches(self):
163 'Invalidate all caches. You must call this before using this object if you have made changes to the HTML tree'
164 self._element_map = None
165 self._id_map = None
166 self._class_map = None
167 self._attrib_map = None
168 self._attrib_space_map = None
169 self._lang_map = None
170 self.map_tag_name = ascii_lower
171 if '{' in self.root.tag:
172 def map_tag_name(x):
173 return ascii_lower(x.rpartition('}')[2])
174 self.map_tag_name = map_tag_name
175
176 def __call__(self, selector, root=None):
177 ''' Return an iterator over all matching tags, in document order.
178 Normally, all matching tags in the document are returned, is you
179 specify root, then only tags that are root or descendants of root are
180 returned. Note that this can be very expensive if root has a lot of
181 descendants. '''
182 seen = set()
183 if root is not None:
184 root = frozenset(self.itertag(root))
185 for parsed_selector in get_parsed_selector(selector):
186 for item in self.iterparsedselector(parsed_selector):
187 if item not in seen and (root is None or item in root):
188 yield item
189 seen.add(item)
190
191 def has_matches(self, selector, root=None):
192 'Return True iff selector matches at least one item in the tree'
193 for elem in self(selector, root=root):
194 return True
195 return False
196 # }}}
197
198 def iterparsedselector(self, parsed_selector):
199 type_name = type(parsed_selector).__name__
200 try:
201 func = self.dispatch_map[ascii_lower(type_name)]
202 except KeyError:
203 raise ExpressionError('%s is not supported' % type_name)
204 for item in func(self, parsed_selector):
205 yield item
206
207 @property
208 def element_map(self):
209 if self._element_map is None:
210 self._element_map = em = defaultdict(OrderedSet)
211 for tag in self.itertag():
212 em[self.map_tag_name(tag.tag)].add(tag)
213 return self._element_map
214
215 @property
216 def id_map(self):
217 if self._id_map is None:
218 self._id_map = im = defaultdict(OrderedSet)
219 lower = ascii_lower
220 for elem in self.iteridtags():
221 im[lower(elem.get('id'))].add(elem)
222 return self._id_map
223
224 @property
225 def class_map(self):
226 if self._class_map is None:
227 self._class_map = cm = defaultdict(OrderedSet)
228 lower = ascii_lower
229 for elem in self.iterclasstags():
230 for cls in elem.get('class').split():
231 cm[lower(cls)].add(elem)
232 return self._class_map
233
234 @property
235 def attrib_map(self):
236 if self._attrib_map is None:
237 self._attrib_map = am = defaultdict(lambda : defaultdict(OrderedSet))
238 map_attrib_name = ascii_lower
239 if '{' in self.root.tag:
240 def map_attrib_name(x):
241 return ascii_lower(x.rpartition('}')[2])
242 for tag in self.itertag():
243 for attr, val in iteritems(tag.attrib):
244 am[map_attrib_name(attr)][val].add(tag)
245 return self._attrib_map
246
247 @property
248 def attrib_space_map(self):
249 if self._attrib_space_map is None:
250 self._attrib_space_map = am = defaultdict(lambda : defaultdict(OrderedSet))
251 map_attrib_name = ascii_lower
252 if '{' in self.root.tag:
253 def map_attrib_name(x):
254 return ascii_lower(x.rpartition('}')[2])
255 for tag in self.itertag():
256 for attr, val in iteritems(tag.attrib):
257 for v in val.split():
258 am[map_attrib_name(attr)][v].add(tag)
259 return self._attrib_space_map
260
261 @property
262 def lang_map(self):
263 if self._lang_map is None:
264 self._lang_map = lm = defaultdict(OrderedSet)
265 dl = normalize_language_tag(self.default_lang) if self.default_lang else None
266 lmap = {tag:dl for tag in self.itertag()} if dl else {}
267 for tag in self.itertag():
268 lang = None
269 for attr in ('{http://www.w3.org/XML/1998/namespace}lang', 'lang'):
270 lang = tag.get(attr)
271 if lang:
272 lang = normalize_language_tag(lang)
273 for dtag in self.itertag(tag):
274 lmap[dtag] = lang
275 for tag, langs in iteritems(lmap):
276 for lang in langs:
277 lm[lang].add(tag)
278 return self._lang_map
279
280 # Tree Integration {{{
281 def itertag(self, tag=None):
282 return (self.root if tag is None else tag).iter('*')
283
284 def iterdescendants(self, tag=None):
285 return (self.root if tag is None else tag).iterdescendants('*')
286
287 def iterchildren(self, tag=None):
288 return (self.root if tag is None else tag).iterchildren('*')
289
290 def itersiblings(self, tag=None, preceding=False):
291 return (self.root if tag is None else tag).itersiblings('*', preceding=preceding)
292
293 def iteridtags(self):
294 return get_compiled_xpath('//*[@id]')(self.root)
295
296 def iterclasstags(self):
297 return get_compiled_xpath('//*[@class]')(self.root)
298
299 def sibling_count(self, child, before=True, same_type=False):
300 ' Return the number of siblings before or after child or raise ValueError if child has no parent. '
301 parent = child.getparent()
302 if parent is None:
303 raise ValueError('Child has no parent')
304 if same_type:
305 siblings = OrderedSet(child.itersiblings(preceding=before))
306 return len(self.element_map[self.map_tag_name(child.tag)] & siblings)
307 else:
308 if before:
309 return parent.index(child)
310 return len(parent) - parent.index(child) - 1
311
312 def all_sibling_count(self, child, same_type=False):
313 ' Return the number of siblings of child or raise ValueError if child has no parent '
314 parent = child.getparent()
315 if parent is None:
316 raise ValueError('Child has no parent')
317 if same_type:
318 siblings = OrderedSet(chain(child.itersiblings(preceding=False), child.itersiblings(preceding=True)))
319 return len(self.element_map[self.map_tag_name(child.tag)] & siblings)
320 else:
321 return len(parent) - 1
322
323 def is_empty(self, elem):
324 ' Return True iff elem has no child tags and no text content '
325 for child in elem:
326 # Check for comment/PI nodes with tail text
327 if child.tail:
328 return False
329 return len(tuple(elem.iterchildren('*'))) == 0 and not elem.text
330
331 # }}}
332
333 # Combinators {{{
334
335
336 def select_combinedselector(cache, combined):
337 """Translate a combined selector."""
338 combinator = cache.combinator_mapping[combined.combinator]
339 # Fast path for when the sub-selector is all elements
340 right = None if isinstance(combined.subselector, Element) and (
341 combined.subselector.element or '*') == '*' else cache.iterparsedselector(combined.subselector)
342 for item in cache.dispatch_map[combinator](cache, cache.iterparsedselector(combined.selector), right):
343 yield item
344
345
346 def select_descendant(cache, left, right):
347 """right is a child, grand-child or further descendant of left"""
348 right = always_in if right is None else frozenset(right)
349 for ancestor in left:
350 for descendant in cache.iterdescendants(ancestor):
351 if descendant in right:
352 yield descendant
353
354
355 def select_child(cache, left, right):
356 """right is an immediate child of left"""
357 right = always_in if right is None else frozenset(right)
358 for parent in left:
359 for child in cache.iterchildren(parent):
360 if child in right:
361 yield child
362
363
364 def select_direct_adjacent(cache, left, right):
365 """right is a sibling immediately after left"""
366 right = always_in if right is None else frozenset(right)
367 for parent in left:
368 for sibling in cache.itersiblings(parent):
369 if sibling in right:
370 yield sibling
371 break
372
373
374 def select_indirect_adjacent(cache, left, right):
375 """right is a sibling after left, immediately or not"""
376 right = always_in if right is None else frozenset(right)
377 for parent in left:
378 for sibling in cache.itersiblings(parent):
379 if sibling in right:
380 yield sibling
381 # }}}
382
383
384 def select_element(cache, selector):
385 """A type or universal selector."""
386 element = selector.element
387 if not element or element == '*':
388 for elem in cache.itertag():
389 yield elem
390 else:
391 for elem in cache.element_map[ascii_lower(element)]:
392 yield elem
393
394
395 def select_hash(cache, selector):
396 'An id selector'
397 items = cache.id_map[ascii_lower(selector.id)]
398 if len(items) > 0:
399 for elem in cache.iterparsedselector(selector.selector):
400 if elem in items:
401 yield elem
402
403
404 def select_class(cache, selector):
405 'A class selector'
406 items = cache.class_map[ascii_lower(selector.class_name)]
407 if items:
408 for elem in cache.iterparsedselector(selector.selector):
409 if elem in items:
410 yield elem
411
412
413 def select_negation(cache, selector):
414 'Implement :not()'
415 exclude = frozenset(cache.iterparsedselector(selector.subselector))
416 for item in cache.iterparsedselector(selector.selector):
417 if item not in exclude:
418 yield item
419
420 # Attribute selectors {{{
421
422
423 def select_attrib(cache, selector):
424 operator = cache.attribute_operator_mapping[selector.operator]
425 items = frozenset(cache.dispatch_map[operator](cache, ascii_lower(selector.attrib), selector.value))
426 for item in cache.iterparsedselector(selector.selector):
427 if item in items:
428 yield item
429
430
431 def select_exists(cache, attrib, value=None):
432 for elem_set in itervalues(cache.attrib_map[attrib]):
433 for elem in elem_set:
434 yield elem
435
436
437 def select_equals(cache, attrib, value):
438 for elem in cache.attrib_map[attrib][value]:
439 yield elem
440
441
442 def select_includes(cache, attrib, value):
443 if is_non_whitespace(value):
444 for elem in cache.attrib_space_map[attrib][value]:
445 yield elem
446
447
448 def select_dashmatch(cache, attrib, value):
449 if value:
450 for val, elem_set in iteritems(cache.attrib_map[attrib]):
451 if val == value or val.startswith(value + '-'):
452 for elem in elem_set:
453 yield elem
454
455
456 def select_prefixmatch(cache, attrib, value):
457 if value:
458 for val, elem_set in iteritems(cache.attrib_map[attrib]):
459 if val.startswith(value):
460 for elem in elem_set:
461 yield elem
462
463
464 def select_suffixmatch(cache, attrib, value):
465 if value:
466 for val, elem_set in iteritems(cache.attrib_map[attrib]):
467 if val.endswith(value):
468 for elem in elem_set:
469 yield elem
470
471
472 def select_substringmatch(cache, attrib, value):
473 if value:
474 for val, elem_set in iteritems(cache.attrib_map[attrib]):
475 if value in val:
476 for elem in elem_set:
477 yield elem
478
479 # }}}
480
481 # Function selectors {{{
482
483
484 def select_function(cache, function):
485 """Select with a functional pseudo-class."""
486 fname = function.name.replace('-', '_')
487 try:
488 func = cache.dispatch_map[fname]
489 except KeyError:
490 raise ExpressionError(
491 "The pseudo-class :%s() is unknown" % function.name)
492 if fname == 'lang':
493 items = frozenset(func(cache, function))
494 for item in cache.iterparsedselector(function.selector):
495 if item in items:
496 yield item
497 else:
498 for item in cache.iterparsedselector(function.selector):
499 if func(cache, function, item):
500 yield item
501
502
503 def select_lang(cache, function):
504 ' Implement :lang() '
505 if function.argument_types() not in (['STRING'], ['IDENT']):
506 raise ExpressionError("Expected a single string or ident for :lang(), got %r" % function.arguments)
507 lang = function.arguments[0].value
508 if lang:
509 lang = ascii_lower(lang)
510 lp = lang + '-'
511 for tlang, elem_set in iteritems(cache.lang_map):
512 if tlang == lang or (tlang is not None and tlang.startswith(lp)):
513 for elem in elem_set:
514 yield elem
515
516
517 def select_nth_child(cache, function, elem):
518 ' Implement :nth-child() '
519 a, b = function.parsed_arguments
520 try:
521 num = cache.sibling_count(elem) + 1
522 except ValueError:
523 return False
524 if a == 0:
525 return num == b
526 n = (num - b) / a
527 return n.is_integer() and n > -1
528
529
530 def select_nth_last_child(cache, function, elem):
531 ' Implement :nth-last-child() '
532 a, b = function.parsed_arguments
533 try:
534 num = cache.sibling_count(elem, before=False) + 1
535 except ValueError:
536 return False
537 if a == 0:
538 return num == b
539 n = (num - b) / a
540 return n.is_integer() and n > -1
541
542
543 def select_nth_of_type(cache, function, elem):
544 ' Implement :nth-of-type() '
545 a, b = function.parsed_arguments
546 try:
547 num = cache.sibling_count(elem, same_type=True) + 1
548 except ValueError:
549 return False
550 if a == 0:
551 return num == b
552 n = (num - b) / a
553 return n.is_integer() and n > -1
554
555
556 def select_nth_last_of_type(cache, function, elem):
557 ' Implement :nth-last-of-type() '
558 a, b = function.parsed_arguments
559 try:
560 num = cache.sibling_count(elem, before=False, same_type=True) + 1
561 except ValueError:
562 return False
563 if a == 0:
564 return num == b
565 n = (num - b) / a
566 return n.is_integer() and n > -1
567
568 # }}}
569
570 # Pseudo elements {{{
571
572
573 def pseudo_func(f):
574 f.is_pseudo = True
575 return f
576
577
578 @pseudo_func
579 def allow_all(cache, item):
580 return True
581
582
583 def get_func_for_pseudo(cache, ident):
584 try:
585 func = cache.dispatch_map[ident.replace('-', '_')]
586 except KeyError:
587 if ident in cache.ignore_inappropriate_pseudo_classes:
588 func = allow_all
589 else:
590 raise ExpressionError(
591 "The pseudo-class :%s is not supported" % ident)
592
593 try:
594 func.is_pseudo
595 except AttributeError:
596 raise ExpressionError(
597 "The pseudo-class :%s is invalid" % ident)
598 return func
599
600
601 def select_selector(cache, selector):
602 if selector.pseudo_element is None:
603 for item in cache.iterparsedselector(selector.parsed_tree):
604 yield item
605 return
606 if isinstance(selector.pseudo_element, FunctionalPseudoElement):
607 raise ExpressionError(
608 "The pseudo-element ::%s is not supported" % selector.pseudo_element.name)
609 func = get_func_for_pseudo(cache, selector.pseudo_element)
610 for item in cache.iterparsedselector(selector.parsed_tree):
611 if func(cache, item):
612 yield item
613
614
615 def select_pseudo(cache, pseudo):
616 func = get_func_for_pseudo(cache, pseudo.ident)
617 if func is select_root:
618 yield cache.root
619 return
620
621 for item in cache.iterparsedselector(pseudo.selector):
622 if func(cache, item):
623 yield item
624
625
626 @pseudo_func
627 def select_root(cache, elem):
628 return elem is cache.root
629
630
631 @pseudo_func
632 def select_first_child(cache, elem):
633 try:
634 return cache.sibling_count(elem) == 0
635 except ValueError:
636 return False
637
638
639 @pseudo_func
640 def select_last_child(cache, elem):
641 try:
642 return cache.sibling_count(elem, before=False) == 0
643 except ValueError:
644 return False
645
646
647 @pseudo_func
648 def select_only_child(cache, elem):
649 try:
650 return cache.all_sibling_count(elem) == 0
651 except ValueError:
652 return False
653
654
655 @pseudo_func
656 def select_first_of_type(cache, elem):
657 try:
658 return cache.sibling_count(elem, same_type=True) == 0
659 except ValueError:
660 return False
661
662
663 @pseudo_func
664 def select_last_of_type(cache, elem):
665 try:
666 return cache.sibling_count(elem, before=False, same_type=True) == 0
667 except ValueError:
668 return False
669
670
671 @pseudo_func
672 def select_only_of_type(cache, elem):
673 try:
674 return cache.all_sibling_count(elem, same_type=True) == 0
675 except ValueError:
676 return False
677
678
679 @pseudo_func
680 def select_empty(cache, elem):
681 return cache.is_empty(elem)
682
683
684 # }}}
685
686 default_dispatch_map = {name.partition('_')[2]:obj for name, obj in globals().items() if name.startswith('select_') and callable(obj)}
687
688 if __name__ == '__main__':
689 from pprint import pprint
690 root = etree.fromstring(
691 '<body xmlns="xxx" xml:lang="en"><p id="p" class="one two" lang="fr"><a id="a"/><b/><c/><d/></p></body>',
692 parser=etree.XMLParser(recover=True, no_network=True, resolve_entities=False))
693 select = Select(root, ignore_inappropriate_pseudo_classes=True, trace=True)
694 pprint(list(select('p:disabled')))