1
// Copyright 2010 The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4

5
package html
6

7
import (
8
	"bytes"
9
	"errors"
10
	"io"
11
	"strconv"
12
	"strings"
13

14
	"golang.org/x/net/html/atom"
15
)
16

17
// A TokenType is the type of a Token.
18
type TokenType uint32
19

20
const (
21
	// ErrorToken means that an error occurred during tokenization.
22
	ErrorToken TokenType = iota
23
	// TextToken means a text node.
24
	TextToken
25
	// A StartTagToken looks like <a>.
26
	StartTagToken
27
	// An EndTagToken looks like </a>.
28
	EndTagToken
29
	// A SelfClosingTagToken tag looks like <br/>.
30
	SelfClosingTagToken
31
	// A CommentToken looks like <!--x-->.
32
	CommentToken
33
	// A DoctypeToken looks like <!DOCTYPE x>
34
	DoctypeToken
35
)
36

37
// ErrBufferExceeded means that the buffering limit was exceeded.
38
var ErrBufferExceeded = errors.New("max buffer exceeded")
39

40
// String returns a string representation of the TokenType.
41
func (t TokenType) String() string {
42
	switch t {
43
	case ErrorToken:
44
		return "Error"
45
	case TextToken:
46
		return "Text"
47
	case StartTagToken:
48
		return "StartTag"
49
	case EndTagToken:
50
		return "EndTag"
51
	case SelfClosingTagToken:
52
		return "SelfClosingTag"
53
	case CommentToken:
54
		return "Comment"
55
	case DoctypeToken:
56
		return "Doctype"
57
	}
58
	return "Invalid(" + strconv.Itoa(int(t)) + ")"
59
}
60

61
// An Attribute is an attribute namespace-key-value triple. Namespace is
62
// non-empty for foreign attributes like xlink, Key is alphabetic (and hence
63
// does not contain escapable characters like '&', '<' or '>'), and Val is
64
// unescaped (it looks like "a<b" rather than "a&lt;b").
65
//
66
// Namespace is only used by the parser, not the tokenizer.
67
type Attribute struct {
68
	Namespace, Key, Val string
69
}
70

71
// A Token consists of a TokenType and some Data (tag name for start and end
72
// tags, content for text, comments and doctypes). A tag Token may also contain
73
// a slice of Attributes. Data is unescaped for all Tokens (it looks like "a<b"
74
// rather than "a&lt;b"). For tag Tokens, DataAtom is the atom for Data, or
75
// zero if Data is not a known tag name.
76
type Token struct {
77
	Type     TokenType
78
	DataAtom atom.Atom
79
	Data     string
80
	Attr     []Attribute
81
}
82

83
// tagString returns a string representation of a tag Token's Data and Attr.
84
func (t Token) tagString() string {
85
	if len(t.Attr) == 0 {
86
		return t.Data
87
	}
88
	buf := bytes.NewBufferString(t.Data)
89
	for _, a := range t.Attr {
90
		buf.WriteByte(' ')
91
		buf.WriteString(a.Key)
92
		buf.WriteString(`="`)
93
		escape(buf, a.Val)
94
		buf.WriteByte('"')
95
	}
96
	return buf.String()
97
}
98

99
// String returns a string representation of the Token.
100
func (t Token) String() string {
101
	switch t.Type {
102
	case ErrorToken:
103
		return ""
104
	case TextToken:
105
		return EscapeString(t.Data)
106
	case StartTagToken:
107
		return "<" + t.tagString() + ">"
108
	case EndTagToken:
109
		return "</" + t.tagString() + ">"
110
	case SelfClosingTagToken:
111
		return "<" + t.tagString() + "/>"
112
	case CommentToken:
113
		return "<!--" + escapeCommentString(t.Data) + "-->"
114
	case DoctypeToken:
115
		return "<!DOCTYPE " + EscapeString(t.Data) + ">"
116
	}
117
	return "Invalid(" + strconv.Itoa(int(t.Type)) + ")"
118
}
119

120
// span is a range of bytes in a Tokenizer's buffer. The start is inclusive,
121
// the end is exclusive.
122
type span struct {
123
	start, end int
124
}
125

126
// A Tokenizer returns a stream of HTML Tokens.
127
type Tokenizer struct {
128
	// r is the source of the HTML text.
129
	r io.Reader
130
	// tt is the TokenType of the current token.
131
	tt TokenType
132
	// err is the first error encountered during tokenization. It is possible
133
	// for tt != Error && err != nil to hold: this means that Next returned a
134
	// valid token but the subsequent Next call will return an error token.
135
	// For example, if the HTML text input was just "plain", then the first
136
	// Next call would set z.err to io.EOF but return a TextToken, and all
137
	// subsequent Next calls would return an ErrorToken.
138
	// err is never reset. Once it becomes non-nil, it stays non-nil.
139
	err error
140
	// readErr is the error returned by the io.Reader r. It is separate from
141
	// err because it is valid for an io.Reader to return (n int, err1 error)
142
	// such that n > 0 && err1 != nil, and callers should always process the
143
	// n > 0 bytes before considering the error err1.
144
	readErr error
145
	// buf[raw.start:raw.end] holds the raw bytes of the current token.
146
	// buf[raw.end:] is buffered input that will yield future tokens.
147
	raw span
148
	buf []byte
149
	// maxBuf limits the data buffered in buf. A value of 0 means unlimited.
150
	maxBuf int
151
	// buf[data.start:data.end] holds the raw bytes of the current token's data:
152
	// a text token's text, a tag token's tag name, etc.
153
	data span
154
	// pendingAttr is the attribute key and value currently being tokenized.
155
	// When complete, pendingAttr is pushed onto attr. nAttrReturned is
156
	// incremented on each call to TagAttr.
157
	pendingAttr   [2]span
158
	attr          [][2]span
159
	nAttrReturned int
160
	// rawTag is the "script" in "</script>" that closes the next token. If
161
	// non-empty, the subsequent call to Next will return a raw or RCDATA text
162
	// token: one that treats "<p>" as text instead of an element.
163
	// rawTag's contents are lower-cased.
164
	rawTag string
165
	// textIsRaw is whether the current text token's data is not escaped.
166
	textIsRaw bool
167
	// convertNUL is whether NUL bytes in the current token's data should
168
	// be converted into \ufffd replacement characters.
169
	convertNUL bool
170
	// allowCDATA is whether CDATA sections are allowed in the current context.
171
	allowCDATA bool
172
}
173

174
// AllowCDATA sets whether or not the tokenizer recognizes <![CDATA[foo]]> as
175
// the text "foo". The default value is false, which means to recognize it as
176
// a bogus comment "<!-- [CDATA[foo]] -->" instead.
177
//
178
// Strictly speaking, an HTML5 compliant tokenizer should allow CDATA if and
179
// only if tokenizing foreign content, such as MathML and SVG. However,
180
// tracking foreign-contentness is difficult to do purely in the tokenizer,
181
// as opposed to the parser, due to HTML integration points: an <svg> element
182
// can contain a <foreignObject> that is foreign-to-SVG but not foreign-to-
183
// HTML. For strict compliance with the HTML5 tokenization algorithm, it is the
184
// responsibility of the user of a tokenizer to call AllowCDATA as appropriate.
185
// In practice, if using the tokenizer without caring whether MathML or SVG
186
// CDATA is text or comments, such as tokenizing HTML to find all the anchor
187
// text, it is acceptable to ignore this responsibility.
188
func (z *Tokenizer) AllowCDATA(allowCDATA bool) {
189
	z.allowCDATA = allowCDATA
190
}
191

192
// NextIsNotRawText instructs the tokenizer that the next token should not be
193
// considered as 'raw text'. Some elements, such as script and title elements,
194
// normally require the next token after the opening tag to be 'raw text' that
195
// has no child elements. For example, tokenizing "<title>a<b>c</b>d</title>"
196
// yields a start tag token for "<title>", a text token for "a<b>c</b>d", and
197
// an end tag token for "</title>". There are no distinct start tag or end tag
198
// tokens for the "<b>" and "</b>".
199
//
200
// This tokenizer implementation will generally look for raw text at the right
201
// times. Strictly speaking, an HTML5 compliant tokenizer should not look for
202
// raw text if in foreign content: <title> generally needs raw text, but a
203
// <title> inside an <svg> does not. Another example is that a <textarea>
204
// generally needs raw text, but a <textarea> is not allowed as an immediate
205
// child of a <select>; in normal parsing, a <textarea> implies </select>, but
206
// one cannot close the implicit element when parsing a <select>'s InnerHTML.
207
// Similarly to AllowCDATA, tracking the correct moment to override raw-text-
208
// ness is difficult to do purely in the tokenizer, as opposed to the parser.
209
// For strict compliance with the HTML5 tokenization algorithm, it is the
210
// responsibility of the user of a tokenizer to call NextIsNotRawText as
211
// appropriate. In practice, like AllowCDATA, it is acceptable to ignore this
212
// responsibility for basic usage.
213
//
214
// Note that this 'raw text' concept is different from the one offered by the
215
// Tokenizer.Raw method.
216
func (z *Tokenizer) NextIsNotRawText() {
217
	z.rawTag = ""
218
}
219

220
// Err returns the error associated with the most recent ErrorToken token.
221
// This is typically io.EOF, meaning the end of tokenization.
222
func (z *Tokenizer) Err() error {
223
	if z.tt != ErrorToken {
224
		return nil
225
	}
226
	return z.err
227
}
228

229
// readByte returns the next byte from the input stream, doing a buffered read
230
// from z.r into z.buf if necessary. z.buf[z.raw.start:z.raw.end] remains a contiguous byte
231
// slice that holds all the bytes read so far for the current token.
232
// It sets z.err if the underlying reader returns an error.
233
// Pre-condition: z.err == nil.
234
func (z *Tokenizer) readByte() byte {
235
	if z.raw.end >= len(z.buf) {
236
		// Our buffer is exhausted and we have to read from z.r. Check if the
237
		// previous read resulted in an error.
238
		if z.readErr != nil {
239
			z.err = z.readErr
240
			return 0
241
		}
242
		// We copy z.buf[z.raw.start:z.raw.end] to the beginning of z.buf. If the length
243
		// z.raw.end - z.raw.start is more than half the capacity of z.buf, then we
244
		// allocate a new buffer before the copy.
245
		c := cap(z.buf)
246
		d := z.raw.end - z.raw.start
247
		var buf1 []byte
248
		if 2*d > c {
249
			buf1 = make([]byte, d, 2*c)
250
		} else {
251
			buf1 = z.buf[:d]
252
		}
253
		copy(buf1, z.buf[z.raw.start:z.raw.end])
254
		if x := z.raw.start; x != 0 {
255
			// Adjust the data/attr spans to refer to the same contents after the copy.
256
			z.data.start -= x
257
			z.data.end -= x
258
			z.pendingAttr[0].start -= x
259
			z.pendingAttr[0].end -= x
260
			z.pendingAttr[1].start -= x
261
			z.pendingAttr[1].end -= x
262
			for i := range z.attr {
263
				z.attr[i][0].start -= x
264
				z.attr[i][0].end -= x
265
				z.attr[i][1].start -= x
266
				z.attr[i][1].end -= x
267
			}
268
		}
269
		z.raw.start, z.raw.end, z.buf = 0, d, buf1[:d]
270
		// Now that we have copied the live bytes to the start of the buffer,
271
		// we read from z.r into the remainder.
272
		var n int
273
		n, z.readErr = readAtLeastOneByte(z.r, buf1[d:cap(buf1)])
274
		if n == 0 {
275
			z.err = z.readErr
276
			return 0
277
		}
278
		z.buf = buf1[:d+n]
279
	}
280
	x := z.buf[z.raw.end]
281
	z.raw.end++
282
	if z.maxBuf > 0 && z.raw.end-z.raw.start >= z.maxBuf {
283
		z.err = ErrBufferExceeded
284
		return 0
285
	}
286
	return x
287
}
288

289
// Buffered returns a slice containing data buffered but not yet tokenized.
290
func (z *Tokenizer) Buffered() []byte {
291
	return z.buf[z.raw.end:]
292
}
293

294
// readAtLeastOneByte wraps an io.Reader so that reading cannot return (0, nil).
295
// It returns io.ErrNoProgress if the underlying r.Read method returns (0, nil)
296
// too many times in succession.
297
func readAtLeastOneByte(r io.Reader, b []byte) (int, error) {
298
	for i := 0; i < 100; i++ {
299
		if n, err := r.Read(b); n != 0 || err != nil {
300
			return n, err
301
		}
302
	}
303
	return 0, io.ErrNoProgress
304
}
305

306
// skipWhiteSpace skips past any white space.
307
func (z *Tokenizer) skipWhiteSpace() {
308
	if z.err != nil {
309
		return
310
	}
311
	for {
312
		c := z.readByte()
313
		if z.err != nil {
314
			return
315
		}
316
		switch c {
317
		case ' ', '\n', '\r', '\t', '\f':
318
			// No-op.
319
		default:
320
			z.raw.end--
321
			return
322
		}
323
	}
324
}
325

326
// readRawOrRCDATA reads until the next "</foo>", where "foo" is z.rawTag and
327
// is typically something like "script" or "textarea".
328
func (z *Tokenizer) readRawOrRCDATA() {
329
	if z.rawTag == "script" {
330
		z.readScript()
331
		z.textIsRaw = true
332
		z.rawTag = ""
333
		return
334
	}
335
loop:
336
	for {
337
		c := z.readByte()
338
		if z.err != nil {
339
			break loop
340
		}
341
		if c != '<' {
342
			continue loop
343
		}
344
		c = z.readByte()
345
		if z.err != nil {
346
			break loop
347
		}
348
		if c != '/' {
349
			z.raw.end--
350
			continue loop
351
		}
352
		if z.readRawEndTag() || z.err != nil {
353
			break loop
354
		}
355
	}
356
	z.data.end = z.raw.end
357
	// A textarea's or title's RCDATA can contain escaped entities.
358
	z.textIsRaw = z.rawTag != "textarea" && z.rawTag != "title"
359
	z.rawTag = ""
360
}
361

362
// readRawEndTag attempts to read a tag like "</foo>", where "foo" is z.rawTag.
363
// If it succeeds, it backs up the input position to reconsume the tag and
364
// returns true. Otherwise it returns false. The opening "</" has already been
365
// consumed.
366
func (z *Tokenizer) readRawEndTag() bool {
367
	for i := 0; i < len(z.rawTag); i++ {
368
		c := z.readByte()
369
		if z.err != nil {
370
			return false
371
		}
372
		if c != z.rawTag[i] && c != z.rawTag[i]-('a'-'A') {
373
			z.raw.end--
374
			return false
375
		}
376
	}
377
	c := z.readByte()
378
	if z.err != nil {
379
		return false
380
	}
381
	switch c {
382
	case ' ', '\n', '\r', '\t', '\f', '/', '>':
383
		// The 3 is 2 for the leading "</" plus 1 for the trailing character c.
384
		z.raw.end -= 3 + len(z.rawTag)
385
		return true
386
	}
387
	z.raw.end--
388
	return false
389
}
390

391
// readScript reads until the next </script> tag, following the byzantine
392
// rules for escaping/hiding the closing tag.
393
func (z *Tokenizer) readScript() {
394
	defer func() {
395
		z.data.end = z.raw.end
396
	}()
397
	var c byte
398

399
scriptData:
400
	c = z.readByte()
401
	if z.err != nil {
402
		return
403
	}
404
	if c == '<' {
405
		goto scriptDataLessThanSign
406
	}
407
	goto scriptData
408

409
scriptDataLessThanSign:
410
	c = z.readByte()
411
	if z.err != nil {
412
		return
413
	}
414
	switch c {
415
	case '/':
416
		goto scriptDataEndTagOpen
417
	case '!':
418
		goto scriptDataEscapeStart
419
	}
420
	z.raw.end--
421
	goto scriptData
422

423
scriptDataEndTagOpen:
424
	if z.readRawEndTag() || z.err != nil {
425
		return
426
	}
427
	goto scriptData
428

429
scriptDataEscapeStart:
430
	c = z.readByte()
431
	if z.err != nil {
432
		return
433
	}
434
	if c == '-' {
435
		goto scriptDataEscapeStartDash
436
	}
437
	z.raw.end--
438
	goto scriptData
439

440
scriptDataEscapeStartDash:
441
	c = z.readByte()
442
	if z.err != nil {
443
		return
444
	}
445
	if c == '-' {
446
		goto scriptDataEscapedDashDash
447
	}
448
	z.raw.end--
449
	goto scriptData
450

451
scriptDataEscaped:
452
	c = z.readByte()
453
	if z.err != nil {
454
		return
455
	}
456
	switch c {
457
	case '-':
458
		goto scriptDataEscapedDash
459
	case '<':
460
		goto scriptDataEscapedLessThanSign
461
	}
462
	goto scriptDataEscaped
463

464
scriptDataEscapedDash:
465
	c = z.readByte()
466
	if z.err != nil {
467
		return
468
	}
469
	switch c {
470
	case '-':
471
		goto scriptDataEscapedDashDash
472
	case '<':
473
		goto scriptDataEscapedLessThanSign
474
	}
475
	goto scriptDataEscaped
476

477
scriptDataEscapedDashDash:
478
	c = z.readByte()
479
	if z.err != nil {
480
		return
481
	}
482
	switch c {
483
	case '-':
484
		goto scriptDataEscapedDashDash
485
	case '<':
486
		goto scriptDataEscapedLessThanSign
487
	case '>':
488
		goto scriptData
489
	}
490
	goto scriptDataEscaped
491

492
scriptDataEscapedLessThanSign:
493
	c = z.readByte()
494
	if z.err != nil {
495
		return
496
	}
497
	if c == '/' {
498
		goto scriptDataEscapedEndTagOpen
499
	}
500
	if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' {
501
		goto scriptDataDoubleEscapeStart
502
	}
503
	z.raw.end--
504
	goto scriptData
505

506
scriptDataEscapedEndTagOpen:
507
	if z.readRawEndTag() || z.err != nil {
508
		return
509
	}
510
	goto scriptDataEscaped
511

512
scriptDataDoubleEscapeStart:
513
	z.raw.end--
514
	for i := 0; i < len("script"); i++ {
515
		c = z.readByte()
516
		if z.err != nil {
517
			return
518
		}
519
		if c != "script"[i] && c != "SCRIPT"[i] {
520
			z.raw.end--
521
			goto scriptDataEscaped
522
		}
523
	}
524
	c = z.readByte()
525
	if z.err != nil {
526
		return
527
	}
528
	switch c {
529
	case ' ', '\n', '\r', '\t', '\f', '/', '>':
530
		goto scriptDataDoubleEscaped
531
	}
532
	z.raw.end--
533
	goto scriptDataEscaped
534

535
scriptDataDoubleEscaped:
536
	c = z.readByte()
537
	if z.err != nil {
538
		return
539
	}
540
	switch c {
541
	case '-':
542
		goto scriptDataDoubleEscapedDash
543
	case '<':
544
		goto scriptDataDoubleEscapedLessThanSign
545
	}
546
	goto scriptDataDoubleEscaped
547

548
scriptDataDoubleEscapedDash:
549
	c = z.readByte()
550
	if z.err != nil {
551
		return
552
	}
553
	switch c {
554
	case '-':
555
		goto scriptDataDoubleEscapedDashDash
556
	case '<':
557
		goto scriptDataDoubleEscapedLessThanSign
558
	}
559
	goto scriptDataDoubleEscaped
560

561
scriptDataDoubleEscapedDashDash:
562
	c = z.readByte()
563
	if z.err != nil {
564
		return
565
	}
566
	switch c {
567
	case '-':
568
		goto scriptDataDoubleEscapedDashDash
569
	case '<':
570
		goto scriptDataDoubleEscapedLessThanSign
571
	case '>':
572
		goto scriptData
573
	}
574
	goto scriptDataDoubleEscaped
575

576
scriptDataDoubleEscapedLessThanSign:
577
	c = z.readByte()
578
	if z.err != nil {
579
		return
580
	}
581
	if c == '/' {
582
		goto scriptDataDoubleEscapeEnd
583
	}
584
	z.raw.end--
585
	goto scriptDataDoubleEscaped
586

587
scriptDataDoubleEscapeEnd:
588
	if z.readRawEndTag() {
589
		z.raw.end += len("</script>")
590
		goto scriptDataEscaped
591
	}
592
	if z.err != nil {
593
		return
594
	}
595
	goto scriptDataDoubleEscaped
596
}
597

598
// readComment reads the next comment token starting with "<!--". The opening
599
// "<!--" has already been consumed.
600
func (z *Tokenizer) readComment() {
601
	// When modifying this function, consider manually increasing the
602
	// maxSuffixLen constant in func TestComments, from 6 to e.g. 9 or more.
603
	// That increase should only be temporary, not committed, as it
604
	// exponentially affects the test running time.
605

606
	z.data.start = z.raw.end
607
	defer func() {
608
		if z.data.end < z.data.start {
609
			// It's a comment with no data, like <!-->.
610
			z.data.end = z.data.start
611
		}
612
	}()
613

614
	var dashCount int
615
	beginning := true
616
	for {
617
		c := z.readByte()
618
		if z.err != nil {
619
			z.data.end = z.calculateAbruptCommentDataEnd()
620
			return
621
		}
622
		switch c {
623
		case '-':
624
			dashCount++
625
			continue
626
		case '>':
627
			if dashCount >= 2 || beginning {
628
				z.data.end = z.raw.end - len("-->")
629
				return
630
			}
631
		case '!':
632
			if dashCount >= 2 {
633
				c = z.readByte()
634
				if z.err != nil {
635
					z.data.end = z.calculateAbruptCommentDataEnd()
636
					return
637
				} else if c == '>' {
638
					z.data.end = z.raw.end - len("--!>")
639
					return
640
				} else if c == '-' {
641
					dashCount = 1
642
					beginning = false
643
					continue
644
				}
645
			}
646
		}
647
		dashCount = 0
648
		beginning = false
649
	}
650
}
651

652
func (z *Tokenizer) calculateAbruptCommentDataEnd() int {
653
	raw := z.Raw()
654
	const prefixLen = len("<!--")
655
	if len(raw) >= prefixLen {
656
		raw = raw[prefixLen:]
657
		if hasSuffix(raw, "--!") {
658
			return z.raw.end - 3
659
		} else if hasSuffix(raw, "--") {
660
			return z.raw.end - 2
661
		} else if hasSuffix(raw, "-") {
662
			return z.raw.end - 1
663
		}
664
	}
665
	return z.raw.end
666
}
667

668
func hasSuffix(b []byte, suffix string) bool {
669
	if len(b) < len(suffix) {
670
		return false
671
	}
672
	b = b[len(b)-len(suffix):]
673
	for i := range b {
674
		if b[i] != suffix[i] {
675
			return false
676
		}
677
	}
678
	return true
679
}
680

681
// readUntilCloseAngle reads until the next ">".
682
func (z *Tokenizer) readUntilCloseAngle() {
683
	z.data.start = z.raw.end
684
	for {
685
		c := z.readByte()
686
		if z.err != nil {
687
			z.data.end = z.raw.end
688
			return
689
		}
690
		if c == '>' {
691
			z.data.end = z.raw.end - len(">")
692
			return
693
		}
694
	}
695
}
696

697
// readMarkupDeclaration reads the next token starting with "<!". It might be
698
// a "<!--comment-->", a "<!DOCTYPE foo>", a "<![CDATA[section]]>" or
699
// "<!a bogus comment". The opening "<!" has already been consumed.
700
func (z *Tokenizer) readMarkupDeclaration() TokenType {
701
	z.data.start = z.raw.end
702
	var c [2]byte
703
	for i := 0; i < 2; i++ {
704
		c[i] = z.readByte()
705
		if z.err != nil {
706
			z.data.end = z.raw.end
707
			return CommentToken
708
		}
709
	}
710
	if c[0] == '-' && c[1] == '-' {
711
		z.readComment()
712
		return CommentToken
713
	}
714
	z.raw.end -= 2
715
	if z.readDoctype() {
716
		return DoctypeToken
717
	}
718
	if z.allowCDATA && z.readCDATA() {
719
		z.convertNUL = true
720
		return TextToken
721
	}
722
	// It's a bogus comment.
723
	z.readUntilCloseAngle()
724
	return CommentToken
725
}
726

727
// readDoctype attempts to read a doctype declaration and returns true if
728
// successful. The opening "<!" has already been consumed.
729
func (z *Tokenizer) readDoctype() bool {
730
	const s = "DOCTYPE"
731
	for i := 0; i < len(s); i++ {
732
		c := z.readByte()
733
		if z.err != nil {
734
			z.data.end = z.raw.end
735
			return false
736
		}
737
		if c != s[i] && c != s[i]+('a'-'A') {
738
			// Back up to read the fragment of "DOCTYPE" again.
739
			z.raw.end = z.data.start
740
			return false
741
		}
742
	}
743
	if z.skipWhiteSpace(); z.err != nil {
744
		z.data.start = z.raw.end
745
		z.data.end = z.raw.end
746
		return true
747
	}
748
	z.readUntilCloseAngle()
749
	return true
750
}
751

752
// readCDATA attempts to read a CDATA section and returns true if
753
// successful. The opening "<!" has already been consumed.
754
func (z *Tokenizer) readCDATA() bool {
755
	const s = "[CDATA["
756
	for i := 0; i < len(s); i++ {
757
		c := z.readByte()
758
		if z.err != nil {
759
			z.data.end = z.raw.end
760
			return false
761
		}
762
		if c != s[i] {
763
			// Back up to read the fragment of "[CDATA[" again.
764
			z.raw.end = z.data.start
765
			return false
766
		}
767
	}
768
	z.data.start = z.raw.end
769
	brackets := 0
770
	for {
771
		c := z.readByte()
772
		if z.err != nil {
773
			z.data.end = z.raw.end
774
			return true
775
		}
776
		switch c {
777
		case ']':
778
			brackets++
779
		case '>':
780
			if brackets >= 2 {
781
				z.data.end = z.raw.end - len("]]>")
782
				return true
783
			}
784
			brackets = 0
785
		default:
786
			brackets = 0
787
		}
788
	}
789
}
790

791
// startTagIn returns whether the start tag in z.buf[z.data.start:z.data.end]
792
// case-insensitively matches any element of ss.
793
func (z *Tokenizer) startTagIn(ss ...string) bool {
794
loop:
795
	for _, s := range ss {
796
		if z.data.end-z.data.start != len(s) {
797
			continue loop
798
		}
799
		for i := 0; i < len(s); i++ {
800
			c := z.buf[z.data.start+i]
801
			if 'A' <= c && c <= 'Z' {
802
				c += 'a' - 'A'
803
			}
804
			if c != s[i] {
805
				continue loop
806
			}
807
		}
808
		return true
809
	}
810
	return false
811
}
812

813
// readStartTag reads the next start tag token. The opening "<a" has already
814
// been consumed, where 'a' means anything in [A-Za-z].
815
func (z *Tokenizer) readStartTag() TokenType {
816
	z.readTag(true)
817
	if z.err != nil {
818
		return ErrorToken
819
	}
820
	// Several tags flag the tokenizer's next token as raw.
821
	c, raw := z.buf[z.data.start], false
822
	if 'A' <= c && c <= 'Z' {
823
		c += 'a' - 'A'
824
	}
825
	switch c {
826
	case 'i':
827
		raw = z.startTagIn("iframe")
828
	case 'n':
829
		raw = z.startTagIn("noembed", "noframes", "noscript")
830
	case 'p':
831
		raw = z.startTagIn("plaintext")
832
	case 's':
833
		raw = z.startTagIn("script", "style")
834
	case 't':
835
		raw = z.startTagIn("textarea", "title")
836
	case 'x':
837
		raw = z.startTagIn("xmp")
838
	}
839
	if raw {
840
		z.rawTag = strings.ToLower(string(z.buf[z.data.start:z.data.end]))
841
	}
842
	// Look for a self-closing token (e.g. <br/>).
843
	//
844
	// Originally, we did this by just checking that the last character of the
845
	// tag (ignoring the closing bracket) was a solidus (/) character, but this
846
	// is not always accurate.
847
	//
848
	// We need to be careful that we don't misinterpret a non-self-closing tag
849
	// as self-closing, as can happen if the tag contains unquoted attribute
850
	// values (i.e. <p a=/>).
851
	//
852
	// To avoid this, we check that the last non-bracket character of the tag
853
	// (z.raw.end-2) isn't the same character as the last non-quote character of
854
	// the last attribute of the tag (z.pendingAttr[1].end-1), if the tag has
855
	// attributes.
856
	nAttrs := len(z.attr)
857
	if z.err == nil && z.buf[z.raw.end-2] == '/' && (nAttrs == 0 || z.raw.end-2 != z.attr[nAttrs-1][1].end-1) {
858
		return SelfClosingTagToken
859
	}
860
	return StartTagToken
861
}
862

863
// readTag reads the next tag token and its attributes. If saveAttr, those
864
// attributes are saved in z.attr, otherwise z.attr is set to an empty slice.
865
// The opening "<a" or "</a" has already been consumed, where 'a' means anything
866
// in [A-Za-z].
867
func (z *Tokenizer) readTag(saveAttr bool) {
868
	z.attr = z.attr[:0]
869
	z.nAttrReturned = 0
870
	// Read the tag name and attribute key/value pairs.
871
	z.readTagName()
872
	if z.skipWhiteSpace(); z.err != nil {
873
		return
874
	}
875
	for {
876
		c := z.readByte()
877
		if z.err != nil || c == '>' {
878
			break
879
		}
880
		z.raw.end--
881
		z.readTagAttrKey()
882
		z.readTagAttrVal()
883
		// Save pendingAttr if saveAttr and that attribute has a non-empty key.
884
		if saveAttr && z.pendingAttr[0].start != z.pendingAttr[0].end {
885
			z.attr = append(z.attr, z.pendingAttr)
886
		}
887
		if z.skipWhiteSpace(); z.err != nil {
888
			break
889
		}
890
	}
891
}
892

893
// readTagName sets z.data to the "div" in "<div k=v>". The reader (z.raw.end)
894
// is positioned such that the first byte of the tag name (the "d" in "<div")
895
// has already been consumed.
896
func (z *Tokenizer) readTagName() {
897
	z.data.start = z.raw.end - 1
898
	for {
899
		c := z.readByte()
900
		if z.err != nil {
901
			z.data.end = z.raw.end
902
			return
903
		}
904
		switch c {
905
		case ' ', '\n', '\r', '\t', '\f':
906
			z.data.end = z.raw.end - 1
907
			return
908
		case '/', '>':
909
			z.raw.end--
910
			z.data.end = z.raw.end
911
			return
912
		}
913
	}
914
}
915

916
// readTagAttrKey sets z.pendingAttr[0] to the "k" in "<div k=v>".
917
// Precondition: z.err == nil.
918
func (z *Tokenizer) readTagAttrKey() {
919
	z.pendingAttr[0].start = z.raw.end
920
	for {
921
		c := z.readByte()
922
		if z.err != nil {
923
			z.pendingAttr[0].end = z.raw.end
924
			return
925
		}
926
		switch c {
927
		case '=':
928
			if z.pendingAttr[0].start+1 == z.raw.end {
929
				// WHATWG 13.2.5.32, if we see an equals sign before the attribute name
930
				// begins, we treat it as a character in the attribute name and continue.
931
				continue
932
			}
933
			fallthrough
934
		case ' ', '\n', '\r', '\t', '\f', '/', '>':
935
			// WHATWG 13.2.5.33 Attribute name state
936
			// We need to reconsume the char in the after attribute name state to support the / character
937
			z.raw.end--
938
			z.pendingAttr[0].end = z.raw.end
939
			return
940
		}
941
	}
942
}
943

944
// readTagAttrVal sets z.pendingAttr[1] to the "v" in "<div k=v>".
945
func (z *Tokenizer) readTagAttrVal() {
946
	z.pendingAttr[1].start = z.raw.end
947
	z.pendingAttr[1].end = z.raw.end
948
	if z.skipWhiteSpace(); z.err != nil {
949
		return
950
	}
951
	c := z.readByte()
952
	if z.err != nil {
953
		return
954
	}
955
	if c == '/' {
956
		// WHATWG 13.2.5.34 After attribute name state
957
		// U+002F SOLIDUS (/) - Switch to the self-closing start tag state.
958
		return
959
	}
960
	if c != '=' {
961
		z.raw.end--
962
		return
963
	}
964
	if z.skipWhiteSpace(); z.err != nil {
965
		return
966
	}
967
	quote := z.readByte()
968
	if z.err != nil {
969
		return
970
	}
971
	switch quote {
972
	case '>':
973
		z.raw.end--
974
		return
975

976
	case '\'', '"':
977
		z.pendingAttr[1].start = z.raw.end
978
		for {
979
			c := z.readByte()
980
			if z.err != nil {
981
				z.pendingAttr[1].end = z.raw.end
982
				return
983
			}
984
			if c == quote {
985
				z.pendingAttr[1].end = z.raw.end - 1
986
				return
987
			}
988
		}
989

990
	default:
991
		z.pendingAttr[1].start = z.raw.end - 1
992
		for {
993
			c := z.readByte()
994
			if z.err != nil {
995
				z.pendingAttr[1].end = z.raw.end
996
				return
997
			}
998
			switch c {
999
			case ' ', '\n', '\r', '\t', '\f':
1000
				z.pendingAttr[1].end = z.raw.end - 1
1001
				return
1002
			case '>':
1003
				z.raw.end--
1004
				z.pendingAttr[1].end = z.raw.end
1005
				return
1006
			}
1007
		}
1008
	}
1009
}
1010

1011
// Next scans the next token and returns its type.
1012
func (z *Tokenizer) Next() TokenType {
1013
	z.raw.start = z.raw.end
1014
	z.data.start = z.raw.end
1015
	z.data.end = z.raw.end
1016
	if z.err != nil {
1017
		z.tt = ErrorToken
1018
		return z.tt
1019
	}
1020
	if z.rawTag != "" {
1021
		if z.rawTag == "plaintext" {
1022
			// Read everything up to EOF.
1023
			for z.err == nil {
1024
				z.readByte()
1025
			}
1026
			z.data.end = z.raw.end
1027
			z.textIsRaw = true
1028
		} else {
1029
			z.readRawOrRCDATA()
1030
		}
1031
		if z.data.end > z.data.start {
1032
			z.tt = TextToken
1033
			z.convertNUL = true
1034
			return z.tt
1035
		}
1036
	}
1037
	z.textIsRaw = false
1038
	z.convertNUL = false
1039

1040
loop:
1041
	for {
1042
		c := z.readByte()
1043
		if z.err != nil {
1044
			break loop
1045
		}
1046
		if c != '<' {
1047
			continue loop
1048
		}
1049

1050
		// Check if the '<' we have just read is part of a tag, comment
1051
		// or doctype. If not, it's part of the accumulated text token.
1052
		c = z.readByte()
1053
		if z.err != nil {
1054
			break loop
1055
		}
1056
		var tokenType TokenType
1057
		switch {
1058
		case 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z':
1059
			tokenType = StartTagToken
1060
		case c == '/':
1061
			tokenType = EndTagToken
1062
		case c == '!' || c == '?':
1063
			// We use CommentToken to mean any of "<!--actual comments-->",
1064
			// "<!DOCTYPE declarations>" and "<?xml processing instructions?>".
1065
			tokenType = CommentToken
1066
		default:
1067
			// Reconsume the current character.
1068
			z.raw.end--
1069
			continue
1070
		}
1071

1072
		// We have a non-text token, but we might have accumulated some text
1073
		// before that. If so, we return the text first, and return the non-
1074
		// text token on the subsequent call to Next.
1075
		if x := z.raw.end - len("<a"); z.raw.start < x {
1076
			z.raw.end = x
1077
			z.data.end = x
1078
			z.tt = TextToken
1079
			return z.tt
1080
		}
1081
		switch tokenType {
1082
		case StartTagToken:
1083
			z.tt = z.readStartTag()
1084
			return z.tt
1085
		case EndTagToken:
1086
			c = z.readByte()
1087
			if z.err != nil {
1088
				break loop
1089
			}
1090
			if c == '>' {
1091
				// "</>" does not generate a token at all. Generate an empty comment
1092
				// to allow passthrough clients to pick up the data using Raw.
1093
				// Reset the tokenizer state and start again.
1094
				z.tt = CommentToken
1095
				return z.tt
1096
			}
1097
			if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' {
1098
				z.readTag(false)
1099
				if z.err != nil {
1100
					z.tt = ErrorToken
1101
				} else {
1102
					z.tt = EndTagToken
1103
				}
1104
				return z.tt
1105
			}
1106
			z.raw.end--
1107
			z.readUntilCloseAngle()
1108
			z.tt = CommentToken
1109
			return z.tt
1110
		case CommentToken:
1111
			if c == '!' {
1112
				z.tt = z.readMarkupDeclaration()
1113
				return z.tt
1114
			}
1115
			z.raw.end--
1116
			z.readUntilCloseAngle()
1117
			z.tt = CommentToken
1118
			return z.tt
1119
		}
1120
	}
1121
	if z.raw.start < z.raw.end {
1122
		z.data.end = z.raw.end
1123
		z.tt = TextToken
1124
		return z.tt
1125
	}
1126
	z.tt = ErrorToken
1127
	return z.tt
1128
}
1129

1130
// Raw returns the unmodified text of the current token. Calling Next, Token,
1131
// Text, TagName or TagAttr may change the contents of the returned slice.
1132
//
1133
// The token stream's raw bytes partition the byte stream (up until an
1134
// ErrorToken). There are no overlaps or gaps between two consecutive token's
1135
// raw bytes. One implication is that the byte offset of the current token is
1136
// the sum of the lengths of all previous tokens' raw bytes.
1137
func (z *Tokenizer) Raw() []byte {
1138
	return z.buf[z.raw.start:z.raw.end]
1139
}
1140

1141
// convertNewlines converts "\r" and "\r\n" in s to "\n".
1142
// The conversion happens in place, but the resulting slice may be shorter.
1143
func convertNewlines(s []byte) []byte {
1144
	for i, c := range s {
1145
		if c != '\r' {
1146
			continue
1147
		}
1148

1149
		src := i + 1
1150
		if src >= len(s) || s[src] != '\n' {
1151
			s[i] = '\n'
1152
			continue
1153
		}
1154

1155
		dst := i
1156
		for src < len(s) {
1157
			if s[src] == '\r' {
1158
				if src+1 < len(s) && s[src+1] == '\n' {
1159
					src++
1160
				}
1161
				s[dst] = '\n'
1162
			} else {
1163
				s[dst] = s[src]
1164
			}
1165
			src++
1166
			dst++
1167
		}
1168
		return s[:dst]
1169
	}
1170
	return s
1171
}
1172

1173
var (
1174
	nul         = []byte("\x00")
1175
	replacement = []byte("\ufffd")
1176
)
1177

1178
// Text returns the unescaped text of a text, comment or doctype token. The
1179
// contents of the returned slice may change on the next call to Next.
1180
func (z *Tokenizer) Text() []byte {
1181
	switch z.tt {
1182
	case TextToken, CommentToken, DoctypeToken:
1183
		s := z.buf[z.data.start:z.data.end]
1184
		z.data.start = z.raw.end
1185
		z.data.end = z.raw.end
1186
		s = convertNewlines(s)
1187
		if (z.convertNUL || z.tt == CommentToken) && bytes.Contains(s, nul) {
1188
			s = bytes.Replace(s, nul, replacement, -1)
1189
		}
1190
		if !z.textIsRaw {
1191
			s = unescape(s, false)
1192
		}
1193
		return s
1194
	}
1195
	return nil
1196
}
1197

1198
// TagName returns the lower-cased name of a tag token (the `img` out of
1199
// `<IMG SRC="foo">`) and whether the tag has attributes.
1200
// The contents of the returned slice may change on the next call to Next.
1201
func (z *Tokenizer) TagName() (name []byte, hasAttr bool) {
1202
	if z.data.start < z.data.end {
1203
		switch z.tt {
1204
		case StartTagToken, EndTagToken, SelfClosingTagToken:
1205
			s := z.buf[z.data.start:z.data.end]
1206
			z.data.start = z.raw.end
1207
			z.data.end = z.raw.end
1208
			return lower(s), z.nAttrReturned < len(z.attr)
1209
		}
1210
	}
1211
	return nil, false
1212
}
1213

1214
// TagAttr returns the lower-cased key and unescaped value of the next unparsed
1215
// attribute for the current tag token and whether there are more attributes.
1216
// The contents of the returned slices may change on the next call to Next.
1217
func (z *Tokenizer) TagAttr() (key, val []byte, moreAttr bool) {
1218
	if z.nAttrReturned < len(z.attr) {
1219
		switch z.tt {
1220
		case StartTagToken, SelfClosingTagToken:
1221
			x := z.attr[z.nAttrReturned]
1222
			z.nAttrReturned++
1223
			key = z.buf[x[0].start:x[0].end]
1224
			val = z.buf[x[1].start:x[1].end]
1225
			return lower(key), unescape(convertNewlines(val), true), z.nAttrReturned < len(z.attr)
1226
		}
1227
	}
1228
	return nil, nil, false
1229
}
1230

1231
// Token returns the current Token. The result's Data and Attr values remain
1232
// valid after subsequent Next calls.
1233
func (z *Tokenizer) Token() Token {
1234
	t := Token{Type: z.tt}
1235
	switch z.tt {
1236
	case TextToken, CommentToken, DoctypeToken:
1237
		t.Data = string(z.Text())
1238
	case StartTagToken, SelfClosingTagToken, EndTagToken:
1239
		name, moreAttr := z.TagName()
1240
		for moreAttr {
1241
			var key, val []byte
1242
			key, val, moreAttr = z.TagAttr()
1243
			t.Attr = append(t.Attr, Attribute{"", atom.String(key), string(val)})
1244
		}
1245
		if a := atom.Lookup(name); a != 0 {
1246
			t.DataAtom, t.Data = a, a.String()
1247
		} else {
1248
			t.DataAtom, t.Data = 0, string(name)
1249
		}
1250
	}
1251
	return t
1252
}
1253

1254
// SetMaxBuf sets a limit on the amount of data buffered during tokenization.
1255
// A value of 0 means unlimited.
1256
func (z *Tokenizer) SetMaxBuf(n int) {
1257
	z.maxBuf = n
1258
}
1259

1260
// NewTokenizer returns a new HTML Tokenizer for the given Reader.
1261
// The input is assumed to be UTF-8 encoded.
1262
func NewTokenizer(r io.Reader) *Tokenizer {
1263
	return NewTokenizerFragment(r, "")
1264
}
1265

1266
// NewTokenizerFragment returns a new HTML Tokenizer for the given Reader, for
1267
// tokenizing an existing element's InnerHTML fragment. contextTag is that
1268
// element's tag, such as "div" or "iframe".
1269
//
1270
// For example, how the InnerHTML "a<b" is tokenized depends on whether it is
1271
// for a <p> tag or a <script> tag.
1272
//
1273
// The input is assumed to be UTF-8 encoded.
1274
func NewTokenizerFragment(r io.Reader, contextTag string) *Tokenizer {
1275
	z := &Tokenizer{
1276
		r:   r,
1277
		buf: make([]byte, 0, 4096),
1278
	}
1279
	if contextTag != "" {
1280
		switch s := strings.ToLower(contextTag); s {
1281
		case "iframe", "noembed", "noframes", "noscript", "plaintext", "script", "style", "title", "textarea", "xmp":
1282
			z.rawTag = s
1283
		}
1284
	}
1285
	return z
1286
}
1287

1288