Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 1 | # |
| 2 | # ElementTree |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 3 | # $Id: ElementPath.py 3375 2008-02-13 08:05:08Z fredrik $ |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 4 | # |
| 5 | # limited xpath support for element trees |
| 6 | # |
| 7 | # history: |
| 8 | # 2003-05-23 fl created |
| 9 | # 2003-05-28 fl added support for // etc |
| 10 | # 2003-08-27 fl fixed parsing of periods in element names |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 11 | # 2007-09-10 fl new selection engine |
| 12 | # 2007-09-12 fl fixed parent selector |
| 13 | # 2007-09-13 fl added iterfind; changed findall to return a list |
| 14 | # 2007-11-30 fl added namespaces support |
| 15 | # 2009-10-30 fl added child element value filter |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 16 | # |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 17 | # Copyright (c) 2003-2009 by Fredrik Lundh. All rights reserved. |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 18 | # |
| 19 | # fredrik@pythonware.com |
| 20 | # http://www.pythonware.com |
| 21 | # |
| 22 | # -------------------------------------------------------------------- |
| 23 | # The ElementTree toolkit is |
| 24 | # |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 25 | # Copyright (c) 1999-2009 by Fredrik Lundh |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 26 | # |
| 27 | # By obtaining, using, and/or copying this software and/or its |
| 28 | # associated documentation, you agree that you have read, understood, |
| 29 | # and will comply with the following terms and conditions: |
| 30 | # |
| 31 | # Permission to use, copy, modify, and distribute this software and |
| 32 | # its associated documentation for any purpose and without fee is |
| 33 | # hereby granted, provided that the above copyright notice appears in |
| 34 | # all copies, and that both that copyright notice and this permission |
| 35 | # notice appear in supporting documentation, and that the name of |
| 36 | # Secret Labs AB or the author not be used in advertising or publicity |
| 37 | # pertaining to distribution of the software without specific, written |
| 38 | # prior permission. |
| 39 | # |
| 40 | # SECRET LABS AB AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD |
| 41 | # TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANT- |
| 42 | # ABILITY AND FITNESS. IN NO EVENT SHALL SECRET LABS AB OR THE AUTHOR |
| 43 | # BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY |
| 44 | # DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
| 45 | # WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS |
| 46 | # ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE |
| 47 | # OF THIS SOFTWARE. |
| 48 | # -------------------------------------------------------------------- |
| 49 | |
Fredrik Lundh | 63168a5 | 2005-12-14 22:29:34 +0000 | [diff] [blame] | 50 | # Licensed to PSF under a Contributor Agreement. |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 51 | # See http://www.python.org/psf/license for licensing details. |
Fredrik Lundh | 63168a5 | 2005-12-14 22:29:34 +0000 | [diff] [blame] | 52 | |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 53 | ## |
| 54 | # Implementation module for XPath support. There's usually no reason |
| 55 | # to import this module directly; the <b>ElementTree</b> does this for |
| 56 | # you, if needed. |
| 57 | ## |
| 58 | |
| 59 | import re |
| 60 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 61 | xpath_tokenizer_re = re.compile( |
R David Murray | 44b548d | 2016-09-08 13:59:53 -0400 | [diff] [blame] | 62 | r"(" |
| 63 | r"'[^']*'|\"[^\"]*\"|" |
| 64 | r"::|" |
| 65 | r"//?|" |
| 66 | r"\.\.|" |
| 67 | r"\(\)|" |
| 68 | r"[/.*:\[\]\(\)@=])|" |
| 69 | r"((?:\{[^}]+\})?[^/\[\]\(\)@=\s]+)|" |
| 70 | r"\s+" |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 71 | ) |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 72 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 73 | def xpath_tokenizer(pattern, namespaces=None): |
Stefan Behnel | e8113f5 | 2019-04-18 19:05:03 +0200 | [diff] [blame^] | 74 | default_namespace = namespaces.get('') if namespaces else None |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 75 | for token in xpath_tokenizer_re.findall(pattern): |
| 76 | tag = token[1] |
Stefan Behnel | e9927e1 | 2019-04-14 10:09:09 +0200 | [diff] [blame] | 77 | if tag and tag[0] != "{": |
| 78 | if ":" in tag: |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 79 | prefix, uri = tag.split(":", 1) |
Stefan Behnel | e9927e1 | 2019-04-14 10:09:09 +0200 | [diff] [blame] | 80 | try: |
| 81 | if not namespaces: |
| 82 | raise KeyError |
| 83 | yield token[0], "{%s}%s" % (namespaces[prefix], uri) |
| 84 | except KeyError: |
| 85 | raise SyntaxError("prefix %r not found in prefix map" % prefix) from None |
| 86 | elif default_namespace: |
| 87 | yield token[0], "{%s}%s" % (default_namespace, tag) |
| 88 | else: |
| 89 | yield token |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 90 | else: |
| 91 | yield token |
| 92 | |
| 93 | def get_parent_map(context): |
| 94 | parent_map = context.parent_map |
| 95 | if parent_map is None: |
| 96 | context.parent_map = parent_map = {} |
| 97 | for p in context.root.iter(): |
| 98 | for e in p: |
| 99 | parent_map[e] = p |
| 100 | return parent_map |
| 101 | |
| 102 | def prepare_child(next, token): |
| 103 | tag = token[1] |
| 104 | def select(context, result): |
| 105 | for elem in result: |
| 106 | for e in elem: |
| 107 | if e.tag == tag: |
| 108 | yield e |
| 109 | return select |
| 110 | |
| 111 | def prepare_star(next, token): |
| 112 | def select(context, result): |
| 113 | for elem in result: |
Philip Jenvey | fd0d3e5 | 2012-10-01 15:34:31 -0700 | [diff] [blame] | 114 | yield from elem |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 115 | return select |
| 116 | |
| 117 | def prepare_self(next, token): |
| 118 | def select(context, result): |
Philip Jenvey | fd0d3e5 | 2012-10-01 15:34:31 -0700 | [diff] [blame] | 119 | yield from result |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 120 | return select |
| 121 | |
| 122 | def prepare_descendant(next, token): |
Raymond Hettinger | 828d932 | 2014-11-22 21:56:23 -0800 | [diff] [blame] | 123 | try: |
| 124 | token = next() |
| 125 | except StopIteration: |
| 126 | return |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 127 | if token[0] == "*": |
| 128 | tag = "*" |
| 129 | elif not token[0]: |
| 130 | tag = token[1] |
| 131 | else: |
| 132 | raise SyntaxError("invalid descendant") |
| 133 | def select(context, result): |
| 134 | for elem in result: |
| 135 | for e in elem.iter(tag): |
| 136 | if e is not elem: |
| 137 | yield e |
| 138 | return select |
| 139 | |
| 140 | def prepare_parent(next, token): |
| 141 | def select(context, result): |
| 142 | # FIXME: raise error if .. is applied at toplevel? |
| 143 | parent_map = get_parent_map(context) |
| 144 | result_map = {} |
| 145 | for elem in result: |
| 146 | if elem in parent_map: |
| 147 | parent = parent_map[elem] |
| 148 | if parent not in result_map: |
| 149 | result_map[parent] = None |
| 150 | yield parent |
| 151 | return select |
| 152 | |
| 153 | def prepare_predicate(next, token): |
| 154 | # FIXME: replace with real parser!!! refs: |
| 155 | # http://effbot.org/zone/simple-iterator-parser.htm |
| 156 | # http://javascript.crockford.com/tdop/tdop.html |
| 157 | signature = [] |
| 158 | predicate = [] |
| 159 | while 1: |
Raymond Hettinger | 828d932 | 2014-11-22 21:56:23 -0800 | [diff] [blame] | 160 | try: |
| 161 | token = next() |
| 162 | except StopIteration: |
| 163 | return |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 164 | if token[0] == "]": |
| 165 | break |
scoder | 101a5e8 | 2017-09-30 15:35:21 +0200 | [diff] [blame] | 166 | if token == ('', ''): |
| 167 | # ignore whitespace |
| 168 | continue |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 169 | if token[0] and token[0][:1] in "'\"": |
| 170 | token = "'", token[0][1:-1] |
| 171 | signature.append(token[0] or "-") |
| 172 | predicate.append(token[1]) |
| 173 | signature = "".join(signature) |
| 174 | # use signature to determine predicate type |
| 175 | if signature == "@-": |
| 176 | # [@attribute] predicate |
| 177 | key = predicate[1] |
| 178 | def select(context, result): |
| 179 | for elem in result: |
| 180 | if elem.get(key) is not None: |
| 181 | yield elem |
| 182 | return select |
| 183 | if signature == "@-='": |
| 184 | # [@attribute='value'] |
| 185 | key = predicate[1] |
| 186 | value = predicate[-1] |
| 187 | def select(context, result): |
| 188 | for elem in result: |
| 189 | if elem.get(key) == value: |
| 190 | yield elem |
| 191 | return select |
R David Murray | 44b548d | 2016-09-08 13:59:53 -0400 | [diff] [blame] | 192 | if signature == "-" and not re.match(r"\-?\d+$", predicate[0]): |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 193 | # [tag] |
| 194 | tag = predicate[0] |
| 195 | def select(context, result): |
| 196 | for elem in result: |
| 197 | if elem.find(tag) is not None: |
| 198 | yield elem |
| 199 | return select |
scoder | 101a5e8 | 2017-09-30 15:35:21 +0200 | [diff] [blame] | 200 | if signature == ".='" or (signature == "-='" and not re.match(r"\-?\d+$", predicate[0])): |
| 201 | # [.='value'] or [tag='value'] |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 202 | tag = predicate[0] |
| 203 | value = predicate[-1] |
scoder | 101a5e8 | 2017-09-30 15:35:21 +0200 | [diff] [blame] | 204 | if tag: |
| 205 | def select(context, result): |
| 206 | for elem in result: |
| 207 | for e in elem.findall(tag): |
| 208 | if "".join(e.itertext()) == value: |
| 209 | yield elem |
| 210 | break |
| 211 | else: |
| 212 | def select(context, result): |
| 213 | for elem in result: |
| 214 | if "".join(elem.itertext()) == value: |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 215 | yield elem |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 216 | return select |
| 217 | if signature == "-" or signature == "-()" or signature == "-()-": |
| 218 | # [index] or [last()] or [last()-index] |
| 219 | if signature == "-": |
Eli Bendersky | 5c6198b | 2013-01-24 06:29:26 -0800 | [diff] [blame] | 220 | # [index] |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 221 | index = int(predicate[0]) - 1 |
Eli Bendersky | 5c6198b | 2013-01-24 06:29:26 -0800 | [diff] [blame] | 222 | if index < 0: |
| 223 | raise SyntaxError("XPath position >= 1 expected") |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 224 | else: |
| 225 | if predicate[0] != "last": |
| 226 | raise SyntaxError("unsupported function") |
| 227 | if signature == "-()-": |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 228 | try: |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 229 | index = int(predicate[2]) - 1 |
| 230 | except ValueError: |
| 231 | raise SyntaxError("unsupported expression") |
Eli Bendersky | 5c6198b | 2013-01-24 06:29:26 -0800 | [diff] [blame] | 232 | if index > -2: |
| 233 | raise SyntaxError("XPath offset from last() must be negative") |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 234 | else: |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 235 | index = -1 |
| 236 | def select(context, result): |
| 237 | parent_map = get_parent_map(context) |
| 238 | for elem in result: |
| 239 | try: |
| 240 | parent = parent_map[elem] |
| 241 | # FIXME: what if the selector is "*" ? |
| 242 | elems = list(parent.findall(elem.tag)) |
| 243 | if elems[index] is elem: |
| 244 | yield elem |
| 245 | except (IndexError, KeyError): |
| 246 | pass |
| 247 | return select |
| 248 | raise SyntaxError("invalid predicate") |
| 249 | |
| 250 | ops = { |
| 251 | "": prepare_child, |
| 252 | "*": prepare_star, |
| 253 | ".": prepare_self, |
| 254 | "..": prepare_parent, |
| 255 | "//": prepare_descendant, |
| 256 | "[": prepare_predicate, |
| 257 | } |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 258 | |
| 259 | _cache = {} |
| 260 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 261 | class _SelectorContext: |
| 262 | parent_map = None |
| 263 | def __init__(self, root): |
| 264 | self.root = root |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 265 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 266 | # -------------------------------------------------------------------- |
| 267 | |
| 268 | ## |
| 269 | # Generate all matching objects. |
| 270 | |
| 271 | def iterfind(elem, path, namespaces=None): |
| 272 | # compile selector pattern |
| 273 | if path[-1:] == "/": |
| 274 | path = path + "*" # implicit all (FIXME: keep this?) |
Stefan Behnel | e9927e1 | 2019-04-14 10:09:09 +0200 | [diff] [blame] | 275 | |
| 276 | cache_key = (path,) |
| 277 | if namespaces: |
Stefan Behnel | e8113f5 | 2019-04-18 19:05:03 +0200 | [diff] [blame^] | 278 | cache_key += tuple(sorted(namespaces.items())) |
Stefan Behnel | e9927e1 | 2019-04-14 10:09:09 +0200 | [diff] [blame] | 279 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 280 | try: |
Eli Bendersky | 2acc525 | 2013-08-03 17:47:47 -0700 | [diff] [blame] | 281 | selector = _cache[cache_key] |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 282 | except KeyError: |
| 283 | if len(_cache) > 100: |
| 284 | _cache.clear() |
| 285 | if path[:1] == "/": |
| 286 | raise SyntaxError("cannot use absolute path on element") |
| 287 | next = iter(xpath_tokenizer(path, namespaces)).__next__ |
Raymond Hettinger | 828d932 | 2014-11-22 21:56:23 -0800 | [diff] [blame] | 288 | try: |
| 289 | token = next() |
| 290 | except StopIteration: |
| 291 | return |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 292 | selector = [] |
| 293 | while 1: |
| 294 | try: |
| 295 | selector.append(ops[token[0]](next, token)) |
| 296 | except StopIteration: |
Pablo Galindo | 0df1905 | 2017-10-16 09:24:22 +0100 | [diff] [blame] | 297 | raise SyntaxError("invalid path") from None |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 298 | try: |
| 299 | token = next() |
| 300 | if token[0] == "/": |
| 301 | token = next() |
| 302 | except StopIteration: |
| 303 | break |
Eli Bendersky | 2acc525 | 2013-08-03 17:47:47 -0700 | [diff] [blame] | 304 | _cache[cache_key] = selector |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 305 | # execute selector pattern |
| 306 | result = [elem] |
| 307 | context = _SelectorContext(elem) |
| 308 | for select in selector: |
| 309 | result = select(context, result) |
| 310 | return result |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 311 | |
| 312 | ## |
| 313 | # Find first matching object. |
| 314 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 315 | def find(elem, path, namespaces=None): |
Raymond Hettinger | 0badfd5 | 2014-11-28 14:52:14 -0800 | [diff] [blame] | 316 | return next(iterfind(elem, path, namespaces), None) |
Armin Rigo | 9ed7306 | 2005-12-14 18:10:45 +0000 | [diff] [blame] | 317 | |
| 318 | ## |
| 319 | # Find all matching objects. |
| 320 | |
Florent Xicluna | f15351d | 2010-03-13 23:24:31 +0000 | [diff] [blame] | 321 | def findall(elem, path, namespaces=None): |
| 322 | return list(iterfind(elem, path, namespaces)) |
| 323 | |
| 324 | ## |
| 325 | # Find text for first matching object. |
| 326 | |
| 327 | def findtext(elem, path, default=None, namespaces=None): |
| 328 | try: |
| 329 | elem = next(iterfind(elem, path, namespaces)) |
| 330 | return elem.text or "" |
| 331 | except StopIteration: |
| 332 | return default |