OILS / lazylex / html.py View on Github | oilshell.org

481 lines, 213 significant
1#!/usr/bin/env python2
2"""
3lazylex/html.py - Low-Level HTML Processing.
4
5See lazylex/README.md for details.
6
7TODO: This should be an Oils library eventually. It's a "lazily-parsed data
8structure" like TSV8
9"""
10from __future__ import print_function
11
12import cStringIO
13import re
14import sys
15
16from typing import List, Tuple
17
18
19def log(msg, *args):
20 msg = msg % args
21 print(msg, file=sys.stderr)
22
23
24class LexError(Exception):
25 """For bad lexical elements like <> or &&"""
26
27 def __init__(self, s, pos):
28 self.s = s
29 self.pos = pos
30
31 def __str__(self):
32 return '(LexError %r)' % (self.s[self.pos:self.pos + 20])
33
34
35class ParseError(Exception):
36 """For errors in the tag structure."""
37
38 def __init__(self, msg, *args):
39 self.msg = msg
40 self.args = args
41
42 def __str__(self):
43 return '(ParseError %s)' % (self.msg % self.args)
44
45
46class Output(object):
47 """Takes an underlying input buffer and an output file. Maintains a
48 position in the input buffer.
49
50 Print FROM the input or print new text to the output.
51 """
52
53 def __init__(self, s, f, left_pos=0, right_pos=-1):
54 self.s = s
55 self.f = f
56 self.pos = left_pos
57 self.right_pos = len(s) if right_pos == -1 else right_pos
58
59 def SkipTo(self, pos):
60 """Skip to a position."""
61 self.pos = pos
62
63 def PrintUntil(self, pos):
64 """Print until a position."""
65 piece = self.s[self.pos:pos]
66 self.f.write(piece)
67 self.pos = pos
68
69 def PrintTheRest(self):
70 """Print until the end of the string."""
71 self.PrintUntil(self.right_pos)
72
73 def Print(self, s):
74 """Print text to the underlying buffer."""
75 self.f.write(s)
76
77
78# HTML Tokens
79TOKENS = 'Decl Comment Processing StartTag StartEndTag EndTag DecChar HexChar CharEntity RawData Invalid EndOfStream'.split(
80)
81
82
83class Tok(object):
84 """
85 Avoid lint errors by using these aliases
86 """
87 pass
88
89
90assert len(TOKENS) == 12, TOKENS
91
92TOKEN_NAMES = [None] * len(TOKENS) # type: List[str]
93
94this_module = sys.modules[__name__]
95for i, tok_str in enumerate(TOKENS):
96 setattr(this_module, tok_str, i)
97 setattr(Tok, tok_str, i)
98 TOKEN_NAMES[i] = tok_str
99
100
101def TokenName(tok_id):
102 return TOKEN_NAMES[tok_id]
103
104
105def MakeLexer(rules):
106 return [
107 # DOTALL is for the comment
108 (re.compile(pat, re.VERBOSE | re.DOTALL), i) for (pat, i) in rules
109 ]
110
111
112#
113# Eggex
114#
115# Tag = / ~['>']+ /
116
117# Is this valid? A single character?
118# Tag = / ~'>'* /
119
120# Maybe better: / [NOT '>']+/
121# capital letters not allowed there?
122#
123# But then this is confusing:
124# / [NOT ~digit]+/
125#
126# / [NOT digit] / is [^\d]
127# / ~digit / is \D
128#
129# Or maybe:
130#
131# / [~ digit]+ /
132# / [~ '>']+ /
133# / [NOT '>']+ /
134
135# End = / '</' Tag '>' /
136# StartEnd = / '<' Tag '/>' /
137# Start = / '<' Tag '>' /
138#
139# EntityRef = / '&' dot{* N} ';' /
140
141LEXER = [
142 # TODO: instead of nongreedy matches, the loop can just do .find('-->') and
143 # .find('?>')
144
145 # Actually non-greedy matches are regular and can be matched in linear time
146 # with RE2.
147 #
148 # https://news.ycombinator.com/item?id=27099798
149 #
150 # Maybe try combining all of these for speed.
151 (r'<!-- .*? -->', Tok.Comment),
152 (r'<\? .*? \?>', Tok.Processing),
153
154 # NOTE: < is allowed in these.
155 (r'<! [^>]+ >', Tok.Decl), # <!DOCTYPE html>
156 (r'</ [^>]+ >', Tok.EndTag), # self-closing <br/> comes FIRST
157 (r'< [^>]+ />', Tok.StartEndTag), # end </a>
158 (r'< [^>]+ >', Tok.StartTag), # start <a>
159 (r'&\# [0-9]+ ;', Tok.DecChar),
160 (r'&\# x[0-9a-fA-F]+ ;', Tok.HexChar),
161 (r'& [a-zA-Z]+ ;', Tok.CharEntity),
162
163 # Note: > is allowed in raw data.
164 # https://stackoverflow.com/questions/10462348/right-angle-bracket-in-html
165 (r'[^&<]+', Tok.RawData),
166 (r'.', Tok.Invalid), # error!
167]
168
169LEXER = MakeLexer(LEXER)
170
171
172class Lexer(object):
173 def __init__(self, s, left_pos=0, right_pos=-1):
174 self.s = s
175 self.pos = left_pos
176 self.right_pos = len(s) if right_pos == -1 else right_pos
177
178 def Next(self):
179 # type: () -> Tuple[int, int]
180
181 # TODO: hook up lexing rules
182 pass
183
184
185def _Tokens(s, left_pos, right_pos):
186 """
187 Args:
188 s: string to parse
189 left_pos, right_pos: Optional span boundaries.
190 """
191 pos = left_pos
192 right_pos = len(s) if right_pos == -1 else right_pos
193
194 while pos < right_pos:
195 # Find the FIRST pattern that matches.
196 for pat, tok_id in LEXER:
197 m = pat.match(s, pos)
198 if m:
199 end_pos = m.end()
200 yield tok_id, end_pos
201 pos = end_pos
202 break
203
204 # Zero length sentinel
205 yield Tok.EndOfStream, pos
206
207
208def ValidTokens(s, left_pos=0, right_pos=-1):
209 """Wrapper around _Tokens to prevent callers from having to handle Invalid.
210
211 I'm not combining the two functions because I might want to do a
212 'yield' transformation on Tokens()? Exceptions might complicate the
213 issue?
214 """
215 pos = left_pos
216 for tok_id, end_pos in _Tokens(s, left_pos, right_pos):
217 if tok_id == Tok.Invalid:
218 raise LexError(s, pos)
219 yield tok_id, end_pos
220 pos = end_pos
221
222
223# Tag names:
224# Match <a or </a
225# Match <h2, but not <2h
226#
227# HTML 5 doesn't restrict tag names at all
228# https://html.spec.whatwg.org/#toc-syntax
229#
230# XML allows : - .
231# https://www.w3.org/TR/xml/#NT-NameChar
232
233# Namespaces for MathML, SVG
234# XLink, XML, XMLNS
235#
236# https://infra.spec.whatwg.org/#namespaces
237#
238# Allow - for td-attrs
239
240_TAG_RE = re.compile(r'/? \s* ([a-zA-Z][a-zA-Z0-9-]*)', re.VERBOSE)
241
242# To match href="foo"
243
244_ATTR_RE = re.compile(
245 r'''
246\s+ # Leading whitespace is required
247([a-z]+) # Attribute name
248(?: # Optional attribute value
249 \s* = \s*
250 (?:
251 " ([^>"]*) " # double quoted value
252 | ([a-zA-Z0-9_\-]+) # Just allow unquoted "identifiers"
253 # TODO: relax this? for href=$foo
254 )
255)?
256''', re.VERBOSE)
257
258TagName, AttrName, UnquotedValue, QuotedValue = range(4)
259
260
261class TagLexer(object):
262 """
263 Given a tag like <a href="..."> or <link type="..." />, the TagLexer
264 provides a few operations:
265
266 - What is the tag?
267 - Iterate through the attributes, giving (name, value_start_pos, value_end_pos)
268 """
269
270 def __init__(self, s):
271 self.s = s
272 self.start_pos = -1 # Invalid
273 self.end_pos = -1
274
275 def Reset(self, start_pos, end_pos):
276 """Reuse instances of this object."""
277 self.start_pos = start_pos
278 self.end_pos = end_pos
279
280 def TagString(self):
281 return self.s[self.start_pos:self.end_pos]
282
283 def TagName(self):
284 # First event
285 tok_id, start, end = next(self.Tokens())
286 return self.s[start:end]
287
288 def GetSpanForAttrValue(self, attr_name):
289 # Algorithm: search for QuotedValue or UnquotedValue after AttrName
290 # TODO: Could also cache these
291
292 events = self.Tokens()
293 val = (-1, -1)
294 try:
295 while True:
296 tok_id, start, end = next(events)
297 if tok_id == AttrName:
298 name = self.s[start:end]
299 if name == attr_name:
300 # The value should come next
301 tok_id, start, end = next(events)
302 if tok_id in (QuotedValue, UnquotedValue):
303 # Note: quoted values may have &amp;
304 # We would need ANOTHER lexer to unescape them.
305 # Right now help_gen.py and oils_doc.py
306 val = start, end
307 break
308
309 except StopIteration:
310 pass
311 return val
312
313 def GetAttrRaw(self, attr_name):
314 """
315 Return the value, which may be UNESCAPED.
316 """
317 # Algorithm: search for QuotedValue or UnquotedValue after AttrName
318 # TODO: Could also cache these
319 start, end = self.GetSpanForAttrValue(attr_name)
320 if start == -1:
321 return None
322 return self.s[start:end]
323
324 def AllAttrsRaw(self):
325 """
326 Get a list of pairs [('class', 'foo'), ('href', '?foo=1&amp;bar=2')]
327
328 The quoted values may be escaped. We would need another lexer to
329 unescape them.
330 """
331 pairs = []
332 events = self.Tokens()
333 try:
334 while True:
335 tok_id, start, end = next(events)
336 if tok_id == AttrName:
337 name = self.s[start:end]
338
339 # The value should come next
340 tok_id, start, end = next(events)
341 if tok_id in (QuotedValue, UnquotedValue):
342 # Note: quoted values may have &amp;
343 # We would need ANOTHER lexer to unescape them, but we
344 # don't need that for ul-table
345
346 val = self.s[start:end]
347 pairs.append((name, val))
348 except StopIteration:
349 pass
350 return pairs
351
352 def Tokens(self):
353 """
354 Yields a sequence of tokens: Tag (AttrName AttrValue?)*
355
356 Where each Token is (Type, start_pos, end_pos)
357
358 Note that start and end are NOT redundant! We skip over some unwanted
359 characters.
360 """
361 m = _TAG_RE.match(self.s, self.start_pos + 1)
362 if not m:
363 raise RuntimeError("Couldn't find HTML tag in %r" %
364 self.TagString())
365 yield TagName, m.start(1), m.end(1)
366
367 pos = m.end(0)
368
369 while True:
370 # don't search past the end
371 m = _ATTR_RE.match(self.s, pos, self.end_pos)
372 if not m:
373 # A validating parser would check that > or /> is next -- there's no junk
374 break
375
376 yield AttrName, m.start(1), m.end(1)
377
378 # Quoted is group 2, unquoted is group 3.
379 if m.group(2) is not None:
380 yield QuotedValue, m.start(2), m.end(2)
381 elif m.group(3) is not None:
382 yield UnquotedValue, m.start(3), m.end(3)
383
384 # Skip past the "
385 pos = m.end(0)
386
387
388def ReadUntilStartTag(it, tag_lexer, tag_name):
389 """Find the next <foo>, returning its (start, end) positions
390
391 Raise ParseError if it's not found.
392
393 tag_lexer is RESET.
394 """
395 pos = 0
396 while True:
397 try:
398 tok_id, end_pos = next(it)
399 except StopIteration:
400 break
401 tag_lexer.Reset(pos, end_pos)
402 if tok_id == Tok.StartTag and tag_lexer.TagName() == tag_name:
403 return pos, end_pos
404
405 pos = end_pos
406
407 raise ParseError('No start tag %r', tag_name)
408
409
410def ReadUntilEndTag(it, tag_lexer, tag_name):
411 """Find the next </foo>, returning its (start, end) position
412
413 Raise ParseError if it's not found.
414
415 tag_lexer is RESET.
416 """
417 pos = 0
418 while True:
419 try:
420 tok_id, end_pos = next(it)
421 except StopIteration:
422 break
423 tag_lexer.Reset(pos, end_pos)
424 if tok_id == Tok.EndTag and tag_lexer.TagName() == tag_name:
425 return pos, end_pos
426
427 pos = end_pos
428
429 raise ParseError('No end tag %r', tag_name)
430
431
432CHAR_ENTITY = {
433 'amp': '&',
434 'lt': '<',
435 'gt': '>',
436 'quot': '"',
437}
438
439
440def ToText(s, left_pos=0, right_pos=-1):
441 """Given HTML, return text by unquoting &gt; and &lt; etc.
442
443 Used by:
444 doctools/oils_doc.py: PygmentsPlugin
445 doctool/make_help.py: HelpIndexCards
446
447 In the latter case, we cold process some tags, like:
448
449 - Blue Link (not clickable, but still useful)
450 - Red X
451
452 That should be html.ToAnsi.
453 """
454 f = cStringIO.StringIO()
455 out = Output(s, f, left_pos, right_pos)
456
457 pos = left_pos
458 for tok_id, end_pos in ValidTokens(s, left_pos, right_pos):
459 if tok_id == Tok.RawData:
460 out.SkipTo(pos)
461 out.PrintUntil(end_pos)
462
463 elif tok_id == Tok.CharEntity: # &amp;
464
465 entity = s[pos + 1:end_pos - 1]
466
467 out.SkipTo(pos)
468 out.Print(CHAR_ENTITY[entity])
469 out.SkipTo(end_pos)
470
471 # Not handling these yet
472 elif tok_id == Tok.HexChar:
473 raise AssertionError('Hex Char %r' % s[pos:pos + 20])
474
475 elif tok_id == Tok.DecChar:
476 raise AssertionError('Dec Char %r' % s[pos:pos + 20])
477
478 pos = end_pos
479
480 out.PrintTheRest()
481 return f.getvalue()