Skip to main content

parsec/
tokenizer.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! The tokenizer, as section 13.2.5 of the HTML Standard describes it.
5//!
6//! It reads the input in place rather than a character at a time, so it
7//! looks ahead instead of keeping the spec's temporary buffer, and it
8//! hands text to the sink in runs, borrowed from the input wherever
9//! nothing in the run had to change. Given the input as it arrives, it
10//! stops wherever what's still to come could change what it reads. Parse
11//! errors are recovered from as the spec says, and reported to the sink
12//! by name once [`Tokenizer::report_errors`] asks.
13
14use std::borrow::Cow;
15
16use memchr::{memchr, memchr2, memchr3};
17
18use crate::entities::ENTITIES;
19
20/// What the tree builder can ask the tokenizer to read next, after a start
21/// tag such as `<title>` or `<script>`.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum TextMode {
24    Rcdata,
25    Rawtext,
26    ScriptData,
27    Plaintext,
28    /// Only for starting a tokenizer in this state, as the tokenizer tests
29    /// do; the tree builder reaches it through `cdata_allowed`.
30    Cdata,
31}
32
33/// Where the tokens go.
34pub trait Sink {
35    fn doctype(&mut self, doctype: &Doctype<'_>);
36    /// A start tag. The answer switches the tokenizer into one of the text
37    /// modes, as the tree builder does after `<textarea>` or `<style>`.
38    fn start_tag(&mut self, tag: &Tag<'_>) -> Option<TextMode>;
39    fn end_tag(&mut self, tag: &Tag<'_>);
40    fn comment(&mut self, text: &str);
41    /// `<?target data?>`, or `<?target data>`.
42    fn processing_instruction(&mut self, target: &str, data: &str);
43    /// A run of characters. Runs are split wherever the input needed a
44    /// change, so a sink that needs whole text joins adjacent runs.
45    fn text(&mut self, text: &str);
46    fn eof(&mut self);
47    /// Whether `<![CDATA[` starts a CDATA section here: true when the
48    /// adjusted current node is in a foreign namespace.
49    fn cdata_allowed(&self) -> bool {
50        false
51    }
52    /// Where the token the next call hands over was written: a byte range
53    /// of the tokenizer's (preprocessed) input, from a tag's `<` to past
54    /// its `>`, or the characters a text run was read from (a character
55    /// reference's whole `&...;` for what it stands for, and all of a run
56    /// of text and references gathered up, unless
57    /// [`Tokenizer::keep_positions`] keeps them apart). Called just
58    /// before every token, text runs included; a sink that doesn't need
59    /// positions leaves it as this, which costs nothing.
60    fn position(&mut self, start: usize, end: usize) {
61        let _ = (start, end);
62    }
63    /// A parse error, by the HTML Standard's name for it (such as
64    /// `unexpected-null-character`), at a byte offset into the input: the
65    /// character the tokenizer was looking at when it found the error, or
66    /// the input's length at its end. Only called after
67    /// [`Tokenizer::report_errors`], and not in order of offset: errors in
68    /// the input stream itself (a control character, a noncharacter) all
69    /// come first.
70    fn error(&mut self, code: &'static str, at: usize) {
71        let _ = (code, at);
72    }
73}
74
75#[derive(Debug)]
76pub struct Doctype<'a> {
77    pub name: Option<&'a str>,
78    pub public_id: Option<&'a str>,
79    pub system_id: Option<&'a str>,
80    pub force_quirks: bool,
81}
82
83#[derive(Debug)]
84pub struct Tag<'a> {
85    /// Lowercased, as the spec stores tag names.
86    pub name: &'a str,
87    pub self_closing: bool,
88    input: &'a str,
89    buf: &'a str,
90    attrs: &'a [Attr],
91}
92
93impl<'a> Tag<'a> {
94    /// The attributes in source order, names lowercased, duplicates
95    /// dropped (the first one wins). Each is a slice of the input when
96    /// nothing in it had to change.
97    pub fn attrs(&self) -> Attrs<'a> {
98        Attrs {
99            input: self.input,
100            buf: self.buf,
101            attrs: self.attrs.iter(),
102        }
103    }
104
105    /// Where the `i`th attribute [`Tag::attrs`] gives was written, as a
106    /// range of the input from its name's first byte to the end of its
107    /// value (past a closing quote), or of its name when it has none.
108    pub fn attr_span(&self, i: usize) -> Option<std::ops::Range<usize>> {
109        self.attrs
110            .get(i)
111            .map(|a| a.at[0] as usize..a.at[1] as usize)
112    }
113}
114
115/// A string the tokenizer read: a range of the input, or of its buffer.
116#[derive(Debug, Clone, Copy)]
117struct Text {
118    start: u32,
119    end: u32,
120    input: bool,
121}
122
123impl Text {
124    fn get<'a>(self, input: &'a str, buf: &'a str) -> &'a str {
125        let from = if self.input { input } else { buf };
126        &from[self.start as usize..self.end as usize]
127    }
128}
129
130#[derive(Debug, Clone)]
131struct Attr {
132    name: Text,
133    value: Text,
134    /// Where in the input it was written, for [`Tag::attr_span`].
135    at: [u32; 2],
136}
137
138pub struct Attrs<'a> {
139    input: &'a str,
140    buf: &'a str,
141    attrs: std::slice::Iter<'a, Attr>,
142}
143
144impl<'a> Iterator for Attrs<'a> {
145    type Item = (&'a str, &'a str);
146
147    fn next(&mut self) -> Option<Self::Item> {
148        let a = self.attrs.next()?;
149        Some((
150            a.name.get(self.input, self.buf),
151            a.value.get(self.input, self.buf),
152        ))
153    }
154
155    fn size_hint(&self) -> (usize, Option<usize>) {
156        self.attrs.size_hint()
157    }
158}
159
160impl ExactSizeIterator for Attrs<'_> {}
161
162/// The spec's input stream preprocessing: CRLF and lone CR become LF. Most
163/// pages have no CR at all, and those are borrowed as they are.
164pub fn preprocess(input: &str) -> Cow<'_, str> {
165    if memchr(b'\r', input.as_bytes()).is_none() {
166        return Cow::Borrowed(input);
167    }
168    let mut out = String::with_capacity(input.len());
169    let mut rest = input;
170    while let Some(i) = memchr(b'\r', rest.as_bytes()) {
171        out.push_str(&rest[..i]);
172        out.push('\n');
173        rest = &rest[i + 1..];
174        if rest.as_bytes().first() == Some(&b'\n') {
175            rest = &rest[1..];
176        }
177    }
178    out.push_str(rest);
179    Cow::Owned(out)
180}
181
182#[derive(Debug, Clone, Copy, PartialEq, Eq)]
183enum State {
184    Data,
185    Rcdata,
186    Rawtext,
187    ScriptData,
188    Plaintext,
189    TagOpen,
190    EndTagOpen,
191    TagName,
192    ScriptDataEscapeStart,
193    ScriptDataEscapeStartDash,
194    ScriptDataEscaped,
195    ScriptDataEscapedDash,
196    ScriptDataEscapedDashDash,
197    ScriptDataEscapedLessThan,
198    ScriptDataDoubleEscapeStart,
199    ScriptDataDoubleEscaped,
200    ScriptDataDoubleEscapedDash,
201    ScriptDataDoubleEscapedDashDash,
202    ScriptDataDoubleEscapedLessThan,
203    ScriptDataDoubleEscapeEnd,
204    BeforeAttributeName,
205    AttributeName,
206    AfterAttributeName,
207    BeforeAttributeValue,
208    AttributeValueDoubleQuoted,
209    AttributeValueSingleQuoted,
210    AttributeValueUnquoted,
211    AfterAttributeValueQuoted,
212    SelfClosingStartTag,
213    BogusComment,
214    ProcessingInstructionOpen,
215    ProcessingInstructionTarget,
216    AfterProcessingInstructionTarget,
217    ProcessingInstructionData,
218    ProcessingInstructionQuestionable,
219    MarkupDeclarationOpen,
220    CommentStart,
221    CommentStartDash,
222    Comment,
223    CommentLessThan,
224    CommentLessThanBang,
225    CommentLessThanBangDash,
226    CommentLessThanBangDashDash,
227    CommentEndDash,
228    CommentEnd,
229    CommentEndBang,
230    Doctype,
231    BeforeDoctypeName,
232    DoctypeName,
233    AfterDoctypeName,
234    AfterDoctypePublicKeyword,
235    BeforeDoctypePublicIdentifier,
236    DoctypePublicIdentifierDoubleQuoted,
237    DoctypePublicIdentifierSingleQuoted,
238    AfterDoctypePublicIdentifier,
239    BetweenDoctypePublicAndSystemIdentifiers,
240    AfterDoctypeSystemKeyword,
241    BeforeDoctypeSystemIdentifier,
242    DoctypeSystemIdentifierDoubleQuoted,
243    DoctypeSystemIdentifierSingleQuoted,
244    AfterDoctypeSystemIdentifier,
245    BogusDoctype,
246    CdataSection,
247}
248
249/// The attribute being read: where its name and value start in
250/// `attr_buf`, and whether an earlier one had the same name.
251#[derive(Clone, Copy)]
252struct Current {
253    /// Where it was written, so far.
254    at: [u32; 2],
255    name_start: usize,
256    name: Option<Text>,
257    value_start: usize,
258    value: Option<Text>,
259    duplicate: bool,
260}
261
262pub struct Tokenizer<'a> {
263    input: &'a str,
264    pos: usize,
265    state: State,
266    last_start_tag: String,
267
268    tag_name: String,
269    /// The tag name as a slice of the input, while nothing in it needed
270    /// changing.
271    name_input: Option<(usize, usize)>,
272    end_tag: bool,
273    self_closing: bool,
274    attr_buf: String,
275    attrs: Vec<Attr>,
276    current: Option<Current>,
277    attr_name_input: Option<(usize, usize)>,
278    /// Where the attribute value being read starts in the input, while it
279    /// is still an unchanged slice of it.
280    value_from: Option<usize>,
281
282    comment: String,
283
284    pi_target: String,
285    pi_data: String,
286    /// Where the target ended: the suite places an end of file inside a
287    /// processing instruction there.
288    pi_target_end: usize,
289
290    doctype_name: Option<String>,
291    public_id: Option<String>,
292    system_id: Option<String>,
293    force_quirks: bool,
294
295    /// Whether plain tags take [`Tokenizer::fast_tag`]; off only in the
296    /// test that checks it against the state machine.
297    fast: bool,
298    /// Whether to tell the sink about parse errors, and those the fast
299    /// path found in the tag it's reading: they're reported only if it
300    /// reads the whole tag, since the state machine finds them again when
301    /// it gives up.
302    errors: bool,
303    fast_errors: Vec<(&'static str, usize)>,
304
305    /// Where the token being read started (its `<`), and the character
306    /// reference being read (its `&`), for [`Sink::position`].
307    token_start: usize,
308    ref_start: usize,
309    /// How far [`Tokenizer::ref_ready`] has looked.
310    ref_scan: usize,
311    /// Text in the data state with character references in it, decoded
312    /// and gathered into one run from `text_from` of the input, so a page
313    /// of them is a handful of runs for the sink rather than three per
314    /// reference. Off with [`Tokenizer::keep_positions`].
315    gather: bool,
316    text: String,
317    text_from: Option<usize>,
318    /// How much of the input has been checked for errors in the stream.
319    stream_checked: usize,
320
321    /// When to give up, checked every few thousand steps.
322    deadline: Option<std::time::Instant>,
323    timed_out: bool,
324}
325
326const fn is_space(b: u8) -> bool {
327    matches!(b, b'\t' | b'\n' | b'\x0C' | b' ')
328}
329
330const REPLACEMENT: &str = "\u{FFFD}";
331
332impl<'a> Tokenizer<'a> {
333    /// A tokenizer over `input`, which should already have been through
334    /// [`preprocess`].
335    pub fn new(input: &'a str) -> Tokenizer<'a> {
336        Tokenizer {
337            input,
338            pos: 0,
339            state: State::Data,
340            last_start_tag: String::new(),
341            tag_name: String::new(),
342            name_input: None,
343            end_tag: false,
344            self_closing: false,
345            attr_buf: String::new(),
346            gather: true,
347            text: String::new(),
348            text_from: None,
349            attrs: Vec::new(),
350            current: None,
351            attr_name_input: None,
352            value_from: None,
353            comment: String::new(),
354            pi_target: String::new(),
355            pi_data: String::new(),
356            pi_target_end: 0,
357            doctype_name: None,
358            public_id: None,
359            system_id: None,
360            force_quirks: false,
361            fast: true,
362            errors: false,
363            fast_errors: Vec::new(),
364            token_start: 0,
365            ref_start: 0,
366            ref_scan: 0,
367            stream_checked: 0,
368            deadline: None,
369            timed_out: false,
370        }
371    }
372
373    /// Stops `run` once `deadline` has passed; [`Tokenizer::timed_out`]
374    /// says whether it did.
375    pub fn set_deadline(&mut self, deadline: std::time::Instant) {
376        self.deadline = Some(deadline);
377    }
378
379    pub fn timed_out(&self) -> bool {
380        self.timed_out
381    }
382
383    /// How far into the input it got.
384    pub fn position(&self) -> usize {
385        self.pos
386    }
387
388    /// Reports each parse error to the sink's [`Sink::error`]. It costs a
389    /// pass over the input, for the errors in it as a stream.
390    pub fn report_errors(&mut self) {
391        self.errors = true;
392    }
393
394    /// Hands the sink each character reference as a run of its own, at
395    /// the place it was written, rather than gathered up with the text
396    /// around it: for a sink that keeps where each character came from.
397    pub fn keep_positions(&mut self) {
398        self.gather = false;
399    }
400
401    #[inline]
402    fn error<S: Sink>(&self, sink: &mut S, code: &'static str, at: usize) {
403        if self.errors {
404            report(sink, code, at);
405        }
406    }
407
408    /// The errors in the input as a stream: control characters other than
409    /// whitespace and NUL, and noncharacters. (A surrogate can't be in a
410    /// `str`.)
411    fn stream_errors<S: Sink>(&self, sink: &mut S, from: usize) {
412        let bytes = self.input.as_bytes();
413        for (i, &b) in bytes.iter().enumerate().skip(from) {
414            // Only these bytes start such a character: C0 controls and
415            // DEL, C1 controls (C2 80 to C2 9F), and the three- and
416            // four-byte forms noncharacters take; the rest are skipped
417            // without decoding.
418            if !(b < 0x20 || b == 0x7F || b == 0xC2 || b == 0xEF || b >= 0xF0) {
419                continue;
420            }
421            let Some(c) = self.input.get(i..).and_then(|s| s.chars().next()) else {
422                continue;
423            };
424            let n = c as u32;
425            let code = if matches!(n, 0x01..=0x08 | 0x0B | 0x0E..=0x1F | 0x7F..=0x9F) {
426                "control-character-in-input-stream"
427            } else if noncharacter(n) {
428                "noncharacter-in-input-stream"
429            } else {
430                continue;
431            };
432            sink.error(code, i);
433        }
434    }
435
436    pub fn set_text_mode(&mut self, mode: TextMode) {
437        self.state = match mode {
438            TextMode::Rcdata => State::Rcdata,
439            TextMode::Rawtext => State::Rawtext,
440            TextMode::ScriptData => State::ScriptData,
441            TextMode::Plaintext => State::Plaintext,
442            TextMode::Cdata => State::CdataSection,
443        };
444    }
445
446    /// The tag an end tag must match to close RCDATA, RAWTEXT or script
447    /// data, as when tokenizing a fragment.
448    pub fn set_last_start_tag(&mut self, name: &str) {
449        self.last_start_tag.clear();
450        self.last_start_tag.push_str(name);
451    }
452
453    fn byte(&self) -> Option<u8> {
454        self.input.as_bytes().get(self.pos).copied()
455    }
456
457    fn rest(&self) -> &'a str {
458        &self.input[self.pos..]
459    }
460
461    fn new_tag(&mut self, end: bool) {
462        self.tag_name.clear();
463        self.name_input = None;
464        self.end_tag = end;
465        self.self_closing = false;
466        self.attr_buf.clear();
467        self.attrs.clear();
468        self.current = None;
469    }
470
471    /// Appends a run of the tag name: kept as a slice of the input when
472    /// it's the whole name so far and already lowercase.
473    fn push_tag_name(&mut self, start: usize, end: usize) {
474        let run = &self.input[start..end];
475        if self.tag_name.is_empty()
476            && self.name_input.is_none()
477            && !run.bytes().any(|b| b.is_ascii_uppercase())
478        {
479            self.name_input = Some((start, end));
480        } else {
481            self.flush_tag_name();
482            push_lower(&mut self.tag_name, run);
483        }
484    }
485
486    fn flush_tag_name(&mut self) {
487        if let Some((s, e)) = self.name_input.take() {
488            self.tag_name.push_str(&self.input[s..e]);
489        }
490    }
491
492    /// An attribute whose name starts at `from` in the input.
493    fn start_attr(&mut self, from: usize) {
494        self.finish_attr();
495        let at = self.attr_buf.len();
496        self.current = Some(Current {
497            at: [from as u32; 2],
498            name_start: at,
499            name: None,
500            value_start: at,
501            value: None,
502            duplicate: false,
503        });
504        self.attr_name_input = None;
505        self.value_from = None;
506    }
507
508    fn push_attr_name(&mut self, start: usize, end: usize) {
509        let run = &self.input[start..end];
510        let empty = self
511            .current
512            .is_some_and(|c| c.name_start == self.attr_buf.len())
513            && self.attr_name_input.is_none();
514        if empty && !run.bytes().any(|b| b.is_ascii_uppercase()) {
515            self.attr_name_input = Some((start, end));
516        } else {
517            self.flush_attr_name();
518            push_lower(&mut self.attr_buf, run);
519        }
520    }
521
522    fn flush_attr_name(&mut self) {
523        if let Some((s, e)) = self.attr_name_input.take() {
524            self.attr_buf.push_str(&self.input[s..e]);
525        }
526    }
527
528    /// On leaving the attribute name state, the name ending at `end` in
529    /// the input: the spec drops an attribute whose name the tag already
530    /// has.
531    fn end_attr_name<S: Sink>(&mut self, sink: &mut S, end: usize) {
532        let Some(mut c) = self.current else { return };
533        c.at[1] = end as u32;
534        let name = match self.attr_name_input.take() {
535            Some((s, e)) => Text {
536                start: s as u32,
537                end: e as u32,
538                input: true,
539            },
540            None => Text {
541                start: c.name_start as u32,
542                end: self.attr_buf.len() as u32,
543                input: false,
544            },
545        };
546        c.name = Some(name);
547        c.value_start = self.attr_buf.len();
548        let this = name.get(self.input, &self.attr_buf);
549        c.duplicate = self
550            .attrs
551            .iter()
552            .any(|a| a.name.get(self.input, &self.attr_buf) == this);
553        if c.duplicate {
554            self.error(sink, "duplicate-attribute", end);
555        }
556        self.current = Some(c);
557    }
558
559    /// Reports each of `chars` in `start..end` of the input, a run of an
560    /// attribute's name or unquoted value that may not hold them.
561    #[cold]
562    fn misplaced<S: Sink>(
563        &self,
564        sink: &mut S,
565        start: usize,
566        end: usize,
567        chars: &[u8],
568        place: &str,
569    ) {
570        let code = if place == "attribute-name" {
571            "unexpected-character-in-attribute-name"
572        } else {
573            "unexpected-character-in-unquoted-attribute-value"
574        };
575        for (i, b) in self.input.as_bytes()[start..end].iter().enumerate() {
576            if chars.contains(b) {
577                sink.error(code, start + i);
578            }
579        }
580    }
581
582    /// The value so far, from the input, into the buffer: something in
583    /// it is about to change.
584    fn flush_value(&mut self, upto: usize) {
585        if let Some(s) = self.value_from.take() {
586            self.attr_buf.push_str(&self.input[s..upto]);
587        }
588    }
589
590    /// The value ends at `end`; if it never changed, it's that slice.
591    /// As written it ends at `written`, past any closing quote.
592    fn end_value(&mut self, end: usize, written: usize) {
593        if let Some(c) = self.current.as_mut() {
594            c.at[1] = written as u32;
595        }
596        if let Some(s) = self.value_from.take()
597            && let Some(c) = self.current.as_mut()
598        {
599            c.value = Some(Text {
600                start: s as u32,
601                end: end as u32,
602                input: true,
603            });
604        }
605    }
606
607    fn finish_attr(&mut self) {
608        let Some(c) = self.current.take() else { return };
609        if c.duplicate {
610            self.attr_buf.truncate(c.name_start);
611            return;
612        }
613        let name = c.name.unwrap_or(Text {
614            start: c.name_start as u32,
615            end: c.name_start as u32,
616            input: false,
617        });
618        let value = c.value.unwrap_or(Text {
619            start: c.value_start as u32,
620            end: self.attr_buf.len() as u32,
621            input: false,
622        });
623        self.attrs.push(Attr {
624            name,
625            value,
626            at: c.at,
627        });
628    }
629
630    fn emit_tag<S: Sink>(&mut self, sink: &mut S) {
631        self.finish_attr();
632        let input = self.input;
633        let name = match self.name_input {
634            Some((s, e)) => &input[s..e],
635            None => self.tag_name.as_str(),
636        };
637        let tag = Tag {
638            name,
639            self_closing: self.self_closing,
640            input,
641            buf: &self.attr_buf,
642            attrs: &self.attrs,
643        };
644        sink.position(self.token_start, self.pos);
645        if self.end_tag {
646            // `pos` is past the `>`.
647            if self.errors {
648                if !tag.attrs.is_empty() {
649                    report(sink, "end-tag-with-attributes", self.pos - 1);
650                }
651                if tag.self_closing {
652                    report(sink, "end-tag-with-trailing-solidus", self.pos - 1);
653                }
654            }
655            sink.end_tag(&tag);
656            self.state = State::Data;
657        } else {
658            let mode = sink.start_tag(&tag);
659            self.state = State::Data;
660            // Only a tag that switches to a text mode is ever matched by
661            // an end tag there, so only that one is kept.
662            if let Some(mode) = mode {
663                let name = match self.name_input {
664                    Some((s, e)) => &input[s..e],
665                    None => self.tag_name.as_str(),
666                };
667                self.last_start_tag.clear();
668                self.last_start_tag.push_str(name);
669                self.set_text_mode(mode);
670            }
671        }
672    }
673
674    /// Reads a plain tag in one pass, from its name to its `>`: lowercase
675    /// names, and values with no character reference or NUL, which is
676    /// most tags on most pages. Anything else, it leaves for the state
677    /// machine, from the same place, and returns false. It takes the
678    /// same steps the states would, so a tag reads the same either way.
679    fn fast_tag<S: Sink>(&mut self, sink: &mut S) -> bool {
680        // A copy for each, so a parse that isn't collecting errors doesn't
681        // ask whether it is at every attribute.
682        match (self.fast, self.errors) {
683            (false, _) => false,
684            (true, false) => self.fast_tag_as::<S, false>(sink),
685            (true, true) => self.fast_tag_as::<S, true>(sink),
686        }
687    }
688
689    fn fast_tag_as<S: Sink, const ERRORS: bool>(&mut self, sink: &mut S) -> bool {
690        let bytes = self.input.as_bytes();
691        let len = bytes.len();
692        let mut p = self.pos;
693        let name_start = p;
694        while p < len && !TAG_NAME_END[bytes[p] as usize] {
695            if bytes[p].is_ascii_uppercase() {
696                return false;
697            }
698            p += 1;
699        }
700        let name = (name_start, p);
701        let mut self_closing = false;
702        if ERRORS {
703            self.fast_errors.clear();
704        }
705        loop {
706            while p < len && is_space(bytes[p]) {
707                p += 1;
708            }
709            match bytes.get(p) {
710                None => return self.bail(),
711                Some(b'>') => {
712                    p += 1;
713                    break;
714                }
715                Some(b'/') if bytes.get(p + 1) == Some(&b'>') => {
716                    self_closing = true;
717                    p += 2;
718                    break;
719                }
720                Some(b'/') => return self.bail(),
721                _ => {}
722            }
723            let a = p;
724            while p < len && !ATTR_NAME_END[bytes[p] as usize] {
725                let c = bytes[p];
726                if c.is_ascii_uppercase() || matches!(c, b'"' | b'\'' | b'<') {
727                    return self.bail();
728                }
729                p += 1;
730            }
731            if p == a || p >= len {
732                return self.bail();
733            }
734            let attr_name = (a, p);
735            let mut written = p;
736            let value = match bytes[p] {
737                b'=' => {
738                    p += 1;
739                    match bytes.get(p) {
740                        Some(&q @ (b'"' | b'\'')) => {
741                            p += 1;
742                            match memchr3(q, b'&', 0, &bytes[p..]) {
743                                Some(i) if bytes[p + i] == q => {
744                                    let v = (p, p + i);
745                                    p += i + 1;
746                                    written = p;
747                                    if ERRORS
748                                        && bytes.get(p).is_some_and(|&b| {
749                                            !is_space(b) && b != b'>' && b != b'/'
750                                        })
751                                    {
752                                        self.fast_errors
753                                            .push(("missing-whitespace-between-attributes", p));
754                                    }
755                                    v
756                                }
757                                _ => return self.bail(),
758                            }
759                        }
760                        Some(_) => {
761                            let v = p;
762                            while p < len && !UNQUOTED_END[bytes[p] as usize] {
763                                if matches!(bytes[p], b'"' | b'\'' | b'<' | b'=' | b'`') {
764                                    return self.bail();
765                                }
766                                p += 1;
767                            }
768                            if p >= len || matches!(bytes[p], b'&' | 0) || p == v {
769                                return self.bail();
770                            }
771                            written = p;
772                            (v, p)
773                        }
774                        None => return self.bail(),
775                    }
776                }
777                b if is_space(b) || b == b'>' || b == b'/' => (p, p),
778                _ => return self.bail(),
779            };
780            let this = &self.input[attr_name.0..attr_name.1];
781            let input = self.input;
782            if !self
783                .attrs
784                .iter()
785                .any(|x| x.name.get(input, &self.attr_buf) == this)
786            {
787                self.attrs.push(Attr {
788                    name: Text {
789                        start: attr_name.0 as u32,
790                        end: attr_name.1 as u32,
791                        input: true,
792                    },
793                    value: Text {
794                        start: value.0 as u32,
795                        end: value.1 as u32,
796                        input: true,
797                    },
798                    at: [a as u32, written as u32],
799                });
800            } else if ERRORS {
801                self.fast_errors.push(("duplicate-attribute", attr_name.1));
802            }
803        }
804        if ERRORS {
805            for &(code, at) in &self.fast_errors {
806                report(sink, code, at);
807            }
808        }
809        self.name_input = Some(name);
810        self.self_closing = self_closing;
811        self.pos = p;
812        self.emit_tag(sink);
813        true
814    }
815
816    fn bail(&mut self) -> bool {
817        self.attrs.clear();
818        false
819    }
820
821    fn emit_comment<S: Sink>(&mut self, sink: &mut S) {
822        sink.position(self.token_start, self.pos);
823        sink.comment(&self.comment);
824        self.state = State::Data;
825    }
826
827    /// A processing instruction with a target the spec won't take is a
828    /// bogus comment instead, starting with the `?`.
829    fn pi_to_comment(&mut self) {
830        self.comment.clear();
831        self.comment.push('?');
832        self.comment.push_str(&self.pi_target);
833        self.state = State::BogusComment;
834    }
835
836    fn new_doctype(&mut self) {
837        self.doctype_name = None;
838        self.public_id = None;
839        self.system_id = None;
840        self.force_quirks = false;
841    }
842
843    fn emit_pi<S: Sink>(&mut self, sink: &mut S) {
844        sink.position(self.token_start, self.pos);
845        sink.processing_instruction(&self.pi_target, &self.pi_data);
846        self.state = State::Data;
847    }
848
849    fn emit_doctype<S: Sink>(&mut self, sink: &mut S) {
850        sink.position(self.token_start, self.pos);
851        sink.doctype(&Doctype {
852            name: self.doctype_name.as_deref(),
853            public_id: self.public_id.as_deref(),
854            system_id: self.system_id.as_deref(),
855            force_quirks: self.force_quirks,
856        });
857        self.state = State::Data;
858    }
859
860    fn quirky_doctype_eof<S: Sink>(&mut self, sink: &mut S) {
861        self.error(sink, "eof-in-doctype", self.input.len());
862        self.force_quirks = true;
863        self.emit_doctype(sink);
864        sink.eof();
865    }
866
867    /// Text in RCDATA, RAWTEXT or script data after `</`: an end tag if
868    /// it names the last start tag and ends there, else text.
869    /// False, having read nothing, when more input is needed to know
870    /// (only when `PARTIAL`): `pos` is back at the `<`, in `text`.
871    fn end_tag_or_text<S: Sink, const PARTIAL: bool>(&mut self, sink: &mut S, text: State) -> bool {
872        let rest = self.rest().as_bytes();
873        let run = rest.iter().take_while(|b| b.is_ascii_alphabetic()).count();
874        // A name no longer than the one it must match, up to the end of
875        // what's here: what follows decides.
876        if PARTIAL && run == rest.len() && run <= self.last_start_tag.len() {
877            self.pos -= 2;
878            self.state = text;
879            return false;
880        }
881        let ends = rest
882            .get(run)
883            .is_some_and(|&b| is_space(b) || b == b'/' || b == b'>');
884        if run > 0
885            && ends
886            && !self.last_start_tag.is_empty()
887            && rest[..run].eq_ignore_ascii_case(self.last_start_tag.as_bytes())
888        {
889            // `pos` is just past the `</`.
890            self.token_start = self.pos - 2;
891            self.new_tag(true);
892            self.tag_name.push_str(&self.last_start_tag);
893            self.pos += run;
894            match rest[run] {
895                b'/' => {
896                    self.pos += 1;
897                    self.state = State::SelfClosingStartTag;
898                }
899                b'>' => {
900                    self.pos += 1;
901                    self.emit_tag(sink);
902                }
903                _ => self.state = State::BeforeAttributeName,
904            }
905            return true;
906        }
907        let input = self.input;
908        emit_text(sink, "</", self.pos - 2, self.pos);
909        emit_text(
910            sink,
911            &input[self.pos..self.pos + run],
912            self.pos,
913            self.pos + run,
914        );
915        self.pos += run;
916        self.state = text;
917        true
918    }
919
920    /// Whether the character reference just past `pos` can be read with
921    /// what's here, when more may follow: true once a byte that can't be
922    /// part of one does. How far it looked is kept, so a long run of
923    /// letters or digits arriving in pieces is looked at once.
924    fn ref_ready(&mut self) -> bool {
925        let bytes = self.input.as_bytes();
926        let from = self.ref_scan.max(self.pos);
927        let ready = bytes[from..]
928            .iter()
929            .any(|&b| !(b.is_ascii_alphanumeric() || b == b'#'));
930        self.ref_scan = if ready { 0 } else { bytes.len() };
931        ready
932    }
933
934    fn out<S: Sink>(&mut self, sink: &mut S, in_attr: bool, s: &str) {
935        if in_attr {
936            self.attr_buf.push_str(s);
937        } else if self.text_from.is_some() {
938            self.text.push_str(s);
939        } else {
940            emit_text(sink, s, self.ref_start, self.pos);
941        }
942    }
943
944    /// The data state's text from `pos` to `end`: on the run being
945    /// gathered, if there is one, else straight to the sink as a slice of
946    /// the input.
947    fn data_text<S: Sink>(&mut self, sink: &mut S, end: usize) {
948        if self.text_from.is_some() {
949            self.text.push_str(&self.input[self.pos..end]);
950        } else {
951            emit_text(sink, &self.input[self.pos..end], self.pos, end);
952        }
953    }
954
955    /// Hands the sink the run gathered by [`Tokenizer::data_text`] and
956    /// character references, read from `text_from` to `end`.
957    fn flush_text<S: Sink>(&mut self, sink: &mut S, end: usize) {
958        // Nothing gathered is no run: an empty one would still take the
959        // place of the newline a <pre> drops.
960        if let Some(from) = self.text_from.take()
961            && !self.text.is_empty()
962        {
963            emit_text(sink, &self.text, from, end);
964            self.text.clear();
965        }
966    }
967
968    /// A character reference, with `pos` just past the `&`.
969    fn char_ref<S: Sink>(&mut self, sink: &mut S, in_attr: bool) {
970        self.ref_start = self.pos - 1;
971        let rest = self.rest();
972        match rest.as_bytes().first() {
973            Some(b) if b.is_ascii_alphanumeric() => self.named_ref(sink, in_attr, rest),
974            Some(b'#') => self.numeric_ref(sink, in_attr, rest),
975            _ => self.out(sink, in_attr, "&"),
976        }
977    }
978
979    fn named_ref<S: Sink>(&mut self, sink: &mut S, in_attr: bool, rest: &'a str) {
980        let bytes = rest.as_bytes();
981        let run = alnum_run(bytes);
982        if bytes.get(run) == Some(&b';')
983            && let Some(value) = lookup(bytes, run + 1)
984        {
985            self.pos += run + 1;
986            self.out(sink, in_attr, value);
987            return;
988        }
989        // Without a semicolon, only the legacy names match, and the
990        // longest one wins.
991        for len in (1..=run.min(LONGEST_LEGACY)).rev() {
992            let Some(value) = lookup(bytes, len) else {
993                continue;
994            };
995            let next = bytes.get(len).copied();
996            self.pos += len;
997            if in_attr && next.is_some_and(|b| b == b'=' || b.is_ascii_alphanumeric()) {
998                self.out(sink, true, "&");
999                self.out(sink, true, &rest[..len]);
1000            } else {
1001                self.error(
1002                    sink,
1003                    "missing-semicolon-after-character-reference",
1004                    self.pos,
1005                );
1006                self.out(sink, in_attr, value);
1007            }
1008            return;
1009        }
1010        self.pos += run;
1011        if bytes.get(run) == Some(&b';') {
1012            self.error(sink, "unknown-named-character-reference", self.pos);
1013        }
1014        self.out(sink, in_attr, "&");
1015        self.out(sink, in_attr, &rest[..run]);
1016    }
1017
1018    fn numeric_ref<S: Sink>(&mut self, sink: &mut S, in_attr: bool, rest: &'a str) {
1019        let bytes = rest.as_bytes();
1020        let hex = matches!(bytes.get(1), Some(b'x' | b'X'));
1021        let start = if hex { 2 } else { 1 };
1022        let radix = if hex { 16 } else { 10 };
1023        // The digits and their value in one pass, held at 0x110000, past
1024        // the last code point, however many there are.
1025        let mut code: u32 = 0;
1026        let mut digits = 0;
1027        for &b in &bytes[start..] {
1028            let d = match b {
1029                b'0'..=b'9' => b - b'0',
1030                b'a'..=b'f' if hex => b - b'a' + 10,
1031                b'A'..=b'F' if hex => b - b'A' + 10,
1032                _ => break,
1033            };
1034            code = (code * radix + d as u32).min(0x11_0000);
1035            digits += 1;
1036        }
1037        if digits == 0 {
1038            self.pos += start;
1039            self.error(
1040                sink,
1041                "absence-of-digits-in-numeric-character-reference",
1042                self.pos,
1043            );
1044            self.out(sink, in_attr, "&");
1045            self.out(sink, in_attr, &rest[..start]);
1046            return;
1047        }
1048        self.pos += start + digits;
1049        if bytes.get(start + digits) == Some(&b';') {
1050            self.pos += 1;
1051        } else {
1052            self.error(
1053                sink,
1054                "missing-semicolon-after-character-reference",
1055                self.pos,
1056            );
1057        }
1058        if self.errors {
1059            reference_error(sink, code, self.pos);
1060        }
1061        let c = match code {
1062            0 | 0xD800..=0xDFFF | 0x11_0000.. => '\u{FFFD}',
1063            0x80..=0x9F => c1(code),
1064            _ => char::from_u32(code).unwrap_or('\u{FFFD}'),
1065        };
1066        if !in_attr && self.text_from.is_some() {
1067            self.text.push(c);
1068        } else {
1069            let mut buf = [0; 4];
1070            self.out(sink, in_attr, c.encode_utf8(&mut buf));
1071        }
1072    }
1073
1074    /// Tokenizes the input to the end, handing each token to `sink`.
1075    pub fn run<S: Sink>(&mut self, sink: &mut S) {
1076        self.run_as::<S, false>(sink);
1077    }
1078
1079    /// Tokenizes as far as the input allows when more of it is to come:
1080    /// it stops where what follows could change what it reads, keeping
1081    /// its place, and goes on from there when [`Tokenizer::extend`] has
1082    /// given it more. Everything it hands the sink is what [`run`] over
1083    /// the whole input would have; the end of the input is `run`'s.
1084    ///
1085    /// [`run`]: Tokenizer::run
1086    pub(crate) fn run_partial<S: Sink>(&mut self, sink: &mut S) {
1087        self.run_as::<S, true>(sink);
1088    }
1089
1090    /// The input, grown: `input` must start with all the tokenizer has
1091    /// read, since it keeps its place as offsets into it.
1092    pub(crate) fn extend(&mut self, input: &'a str) {
1093        debug_assert!(input.len() >= self.pos && input.is_char_boundary(self.pos));
1094        debug_assert!(self.stream_checked <= input.len() && self.ref_scan <= input.len());
1095        // Every place it keeps in the token it's reading is in what it has
1096        // read.
1097        debug_assert!(
1098            [self.token_start, self.ref_start]
1099                .into_iter()
1100                .chain(self.value_from)
1101                .chain(self.name_input.map(|(_, e)| e))
1102                .chain(self.attr_name_input.map(|(_, e)| e))
1103                .all(|at| at <= self.pos),
1104            "a place past the tokenizer's position, {}",
1105            self.pos
1106        );
1107        self.input = input;
1108    }
1109
1110    /// Lets go of the input between [`Tokenizer::run_partial`]s, while it
1111    /// grows and moves; [`Tokenizer::extend`] gives it back.
1112    pub(crate) fn detach(&mut self) {
1113        self.input = "";
1114    }
1115
1116    fn run_as<S: Sink, const PARTIAL: bool>(&mut self, sink: &mut S) {
1117        let input = self.input;
1118        let bytes = input.as_bytes();
1119        let mut steps: u32 = 0;
1120        if self.errors && self.stream_checked < bytes.len() {
1121            self.stream_errors(sink, self.stream_checked);
1122            self.stream_checked = bytes.len();
1123        }
1124        loop {
1125            if let Some(deadline) = self.deadline {
1126                steps = steps.wrapping_add(1);
1127                if steps.is_multiple_of(4096) && std::time::Instant::now() > deadline {
1128                    self.timed_out = true;
1129                    self.flush_text(sink, self.pos);
1130                    return;
1131                }
1132            }
1133            // With more to come, no state can tell from nothing what the
1134            // next character is; each picks up from here when it comes.
1135            if PARTIAL && self.pos >= bytes.len() {
1136                self.flush_text(sink, self.pos);
1137                return;
1138            }
1139            match self.state {
1140                State::Data => {
1141                    let rest = &bytes[self.pos..];
1142                    let Some(i) = memchr3(b'<', b'&', 0, rest) else {
1143                        if !rest.is_empty() {
1144                            self.data_text(sink, bytes.len());
1145                        }
1146                        self.flush_text(sink, bytes.len());
1147                        self.pos = bytes.len();
1148                        if PARTIAL {
1149                            return;
1150                        }
1151                        sink.eof();
1152                        return;
1153                    };
1154                    if rest[i] == b'&' && self.gather {
1155                        // The text before it and what it stands for go on
1156                        // the run being gathered.
1157                        let at = self.pos + i;
1158                        if self.text_from.is_none() {
1159                            self.text_from = Some(self.pos);
1160                        }
1161                        if i > 0 {
1162                            self.text.push_str(&input[self.pos..at]);
1163                        }
1164                        self.pos = at + 1;
1165                        if PARTIAL && !self.ref_ready() {
1166                            // A reference not all here yet.
1167                            self.pos = at;
1168                            self.flush_text(sink, at);
1169                            return;
1170                        }
1171                        self.char_ref(sink, false);
1172                        // A run's handed over now and then, so a long one
1173                        // isn't held twice, here and in the sink.
1174                        if self.text.len() >= 1 << 16 {
1175                            self.flush_text(sink, self.pos);
1176                        }
1177                        continue;
1178                    }
1179                    if i > 0 {
1180                        self.data_text(sink, self.pos + i);
1181                    }
1182                    self.flush_text(sink, self.pos + i);
1183                    self.pos += i + 1;
1184                    match rest[i] {
1185                        b'<' => {
1186                            self.token_start = self.pos - 1;
1187                            self.state = State::TagOpen;
1188                        }
1189                        b'&' => {
1190                            if PARTIAL && !self.ref_ready() {
1191                                self.pos -= 1;
1192                                return;
1193                            }
1194                            self.char_ref(sink, false);
1195                        }
1196                        _ => {
1197                            self.error(sink, "unexpected-null-character", self.pos - 1);
1198                            emit_text(sink, "\0", self.pos - 1, self.pos);
1199                        }
1200                    }
1201                }
1202                State::Rcdata | State::Rawtext | State::ScriptData | State::Plaintext => {
1203                    let state = self.state;
1204                    let rest = &bytes[self.pos..];
1205                    let found = match state {
1206                        State::Rcdata => memchr3(b'<', b'&', 0, rest),
1207                        State::Plaintext => memchr(0, rest),
1208                        _ => memchr2(b'<', 0, rest),
1209                    };
1210                    let Some(i) = found else {
1211                        if !rest.is_empty() {
1212                            emit_text(sink, &input[self.pos..], self.pos, bytes.len());
1213                        }
1214                        self.pos = bytes.len();
1215                        if PARTIAL {
1216                            return;
1217                        }
1218                        sink.eof();
1219                        return;
1220                    };
1221                    if i > 0 {
1222                        emit_text(sink, &input[self.pos..self.pos + i], self.pos, self.pos + i);
1223                    }
1224                    self.pos += i + 1;
1225                    match rest[i] {
1226                        b'&' => {
1227                            if PARTIAL && !self.ref_ready() {
1228                                self.pos -= 1;
1229                                return;
1230                            }
1231                            self.char_ref(sink, false);
1232                        }
1233                        0 => {
1234                            self.error(sink, "unexpected-null-character", self.pos - 1);
1235                            emit_text(sink, REPLACEMENT, self.pos - 1, self.pos);
1236                        }
1237                        _ => match self.byte() {
1238                            // What follows the `<` decides.
1239                            None if PARTIAL => {
1240                                self.pos -= 1;
1241                                return;
1242                            }
1243                            Some(b'/') => {
1244                                self.pos += 1;
1245                                if !self.end_tag_or_text::<S, PARTIAL>(sink, state) {
1246                                    return;
1247                                }
1248                            }
1249                            Some(b'!') if state == State::ScriptData => {
1250                                self.pos += 1;
1251                                emit_text(sink, "<!", self.pos - 2, self.pos);
1252                                self.state = State::ScriptDataEscapeStart;
1253                            }
1254                            _ => emit_text(sink, "<", self.pos - 1, self.pos),
1255                        },
1256                    }
1257                }
1258                State::TagOpen => match self.byte() {
1259                    Some(b'!') => {
1260                        self.pos += 1;
1261                        self.state = State::MarkupDeclarationOpen;
1262                    }
1263                    Some(b'/') => {
1264                        self.pos += 1;
1265                        self.state = State::EndTagOpen;
1266                    }
1267                    Some(b) if b.is_ascii_alphabetic() => {
1268                        self.new_tag(false);
1269                        if !self.fast_tag(sink) {
1270                            self.state = State::TagName;
1271                        }
1272                    }
1273                    Some(b'?') => {
1274                        self.pos += 1;
1275                        self.pi_target.clear();
1276                        self.state = State::ProcessingInstructionOpen;
1277                    }
1278                    None => {
1279                        self.error(sink, "eof-before-tag-name", self.pos);
1280                        emit_text(sink, "<", self.pos - 1, self.pos);
1281                        sink.eof();
1282                        return;
1283                    }
1284                    Some(_) => {
1285                        self.error(sink, "invalid-first-character-of-tag-name", self.pos);
1286                        emit_text(sink, "<", self.pos - 1, self.pos);
1287                        self.state = State::Data;
1288                    }
1289                },
1290                State::EndTagOpen => match self.byte() {
1291                    Some(b) if b.is_ascii_alphabetic() => {
1292                        self.new_tag(true);
1293                        if !self.fast_tag(sink) {
1294                            self.state = State::TagName;
1295                        }
1296                    }
1297                    Some(b'>') => {
1298                        self.error(sink, "missing-end-tag-name", self.pos);
1299                        self.pos += 1;
1300                        self.state = State::Data;
1301                    }
1302                    None => {
1303                        self.error(sink, "eof-before-tag-name", self.pos);
1304                        emit_text(sink, "</", self.pos - 2, self.pos);
1305                        sink.eof();
1306                        return;
1307                    }
1308                    Some(_) => {
1309                        self.error(sink, "invalid-first-character-of-tag-name", self.pos);
1310                        self.comment.clear();
1311                        self.state = State::BogusComment;
1312                    }
1313                },
1314                State::TagName => match self.byte() {
1315                    None => {
1316                        self.error(sink, "eof-in-tag", self.pos);
1317                        sink.eof();
1318                        return;
1319                    }
1320                    Some(b) if is_space(b) => {
1321                        self.pos += 1;
1322                        self.state = State::BeforeAttributeName;
1323                    }
1324                    Some(b'/') => {
1325                        self.pos += 1;
1326                        self.state = State::SelfClosingStartTag;
1327                    }
1328                    Some(b'>') => {
1329                        self.pos += 1;
1330                        self.emit_tag(sink);
1331                    }
1332                    Some(0) => {
1333                        self.error(sink, "unexpected-null-character", self.pos);
1334                        self.pos += 1;
1335                        self.flush_tag_name();
1336                        self.tag_name.push_str(REPLACEMENT);
1337                    }
1338                    Some(_) => {
1339                        let start = self.pos;
1340                        let end = scan(bytes, start, |b| {
1341                            is_space(b) || matches!(b, b'/' | b'>' | 0)
1342                        });
1343                        self.push_tag_name(start, end);
1344                        self.pos = end;
1345                    }
1346                },
1347                State::ScriptDataEscapeStart | State::ScriptDataEscapeStartDash => {
1348                    if self.byte() == Some(b'-') {
1349                        self.pos += 1;
1350                        emit_text(sink, "-", self.pos - 1, self.pos);
1351                        self.state = if self.state == State::ScriptDataEscapeStart {
1352                            State::ScriptDataEscapeStartDash
1353                        } else {
1354                            State::ScriptDataEscapedDashDash
1355                        };
1356                    } else {
1357                        self.state = State::ScriptData;
1358                    }
1359                }
1360                State::ScriptDataEscaped | State::ScriptDataDoubleEscaped => {
1361                    let double = self.state == State::ScriptDataDoubleEscaped;
1362                    let rest = &bytes[self.pos..];
1363                    let Some(i) = memchr3(b'-', b'<', 0, rest) else {
1364                        if !rest.is_empty() {
1365                            emit_text(sink, &input[self.pos..], self.pos, bytes.len());
1366                        }
1367                        self.pos = bytes.len();
1368                        if PARTIAL {
1369                            return;
1370                        }
1371                        self.error(sink, "eof-in-script-html-comment-like-text", self.pos);
1372                        sink.eof();
1373                        return;
1374                    };
1375                    if i > 0 {
1376                        emit_text(sink, &input[self.pos..self.pos + i], self.pos, self.pos + i);
1377                    }
1378                    self.pos += i + 1;
1379                    match rest[i] {
1380                        b'-' => {
1381                            emit_text(sink, "-", self.pos - 1, self.pos);
1382                            self.state = if double {
1383                                State::ScriptDataDoubleEscapedDash
1384                            } else {
1385                                State::ScriptDataEscapedDash
1386                            };
1387                        }
1388                        b'<' if double => {
1389                            emit_text(sink, "<", self.pos - 1, self.pos);
1390                            self.state = State::ScriptDataDoubleEscapedLessThan;
1391                        }
1392                        b'<' => self.state = State::ScriptDataEscapedLessThan,
1393                        _ => {
1394                            self.error(sink, "unexpected-null-character", self.pos - 1);
1395                            emit_text(sink, REPLACEMENT, self.pos - 1, self.pos);
1396                        }
1397                    }
1398                }
1399                State::ScriptDataEscapedDash
1400                | State::ScriptDataEscapedDashDash
1401                | State::ScriptDataDoubleEscapedDash
1402                | State::ScriptDataDoubleEscapedDashDash => {
1403                    let double = matches!(
1404                        self.state,
1405                        State::ScriptDataDoubleEscapedDash | State::ScriptDataDoubleEscapedDashDash
1406                    );
1407                    let dash_dash = matches!(
1408                        self.state,
1409                        State::ScriptDataEscapedDashDash | State::ScriptDataDoubleEscapedDashDash
1410                    );
1411                    let (body, dash2, less) = if double {
1412                        (
1413                            State::ScriptDataDoubleEscaped,
1414                            State::ScriptDataDoubleEscapedDashDash,
1415                            State::ScriptDataDoubleEscapedLessThan,
1416                        )
1417                    } else {
1418                        (
1419                            State::ScriptDataEscaped,
1420                            State::ScriptDataEscapedDashDash,
1421                            State::ScriptDataEscapedLessThan,
1422                        )
1423                    };
1424                    match self.byte() {
1425                        None => {
1426                            self.error(sink, "eof-in-script-html-comment-like-text", self.pos);
1427                            sink.eof();
1428                            return;
1429                        }
1430                        Some(b'-') => {
1431                            self.pos += 1;
1432                            emit_text(sink, "-", self.pos - 1, self.pos);
1433                            self.state = dash2;
1434                        }
1435                        Some(b'<') => {
1436                            self.pos += 1;
1437                            if double {
1438                                emit_text(sink, "<", self.pos - 1, self.pos);
1439                            }
1440                            self.state = less;
1441                        }
1442                        Some(b'>') if dash_dash => {
1443                            self.pos += 1;
1444                            emit_text(sink, ">", self.pos - 1, self.pos);
1445                            self.state = State::ScriptData;
1446                        }
1447                        Some(0) => {
1448                            self.error(sink, "unexpected-null-character", self.pos);
1449                            self.pos += 1;
1450                            emit_text(sink, REPLACEMENT, self.pos - 1, self.pos);
1451                            self.state = body;
1452                        }
1453                        Some(_) => self.state = body,
1454                    }
1455                }
1456                State::ScriptDataEscapedLessThan => match self.byte() {
1457                    Some(b'/') => {
1458                        self.pos += 1;
1459                        // Back to the `<`, which that state took.
1460                        if !self.end_tag_or_text::<S, PARTIAL>(sink, State::ScriptDataEscaped) {
1461                            return;
1462                        }
1463                    }
1464                    Some(b) if b.is_ascii_alphabetic() => {
1465                        emit_text(sink, "<", self.pos - 1, self.pos);
1466                        self.state = State::ScriptDataDoubleEscapeStart;
1467                    }
1468                    _ => {
1469                        emit_text(sink, "<", self.pos - 1, self.pos);
1470                        self.state = State::ScriptDataEscaped;
1471                    }
1472                },
1473                State::ScriptDataDoubleEscapeStart | State::ScriptDataDoubleEscapeEnd => {
1474                    let start = self.state == State::ScriptDataDoubleEscapeStart;
1475                    let rest = &bytes[self.pos..];
1476                    let run = rest.iter().take_while(|b| b.is_ascii_alphabetic()).count();
1477                    // Up to six letters might still be `script`, and what
1478                    // follows them decides; past that, nothing does.
1479                    if PARTIAL && run == rest.len() && run <= 6 {
1480                        return;
1481                    }
1482                    if run > 0 {
1483                        emit_text(
1484                            sink,
1485                            &input[self.pos..self.pos + run],
1486                            self.pos,
1487                            self.pos + run,
1488                        );
1489                    }
1490                    let script = rest[..run].eq_ignore_ascii_case(b"script");
1491                    self.pos += run;
1492                    match rest.get(run) {
1493                        Some(&b) if is_space(b) || b == b'/' || b == b'>' => {
1494                            self.pos += 1;
1495                            emit_text(sink, &input[self.pos - 1..self.pos], self.pos - 1, self.pos);
1496                            self.state = match (start, script) {
1497                                (true, true) | (false, false) => State::ScriptDataDoubleEscaped,
1498                                _ => State::ScriptDataEscaped,
1499                            };
1500                        }
1501                        _ => {
1502                            self.state = if start {
1503                                State::ScriptDataEscaped
1504                            } else {
1505                                State::ScriptDataDoubleEscaped
1506                            };
1507                        }
1508                    }
1509                }
1510                State::ScriptDataDoubleEscapedLessThan => {
1511                    if self.byte() == Some(b'/') {
1512                        self.pos += 1;
1513                        emit_text(sink, "/", self.pos - 1, self.pos);
1514                        self.state = State::ScriptDataDoubleEscapeEnd;
1515                    } else {
1516                        self.state = State::ScriptDataDoubleEscaped;
1517                    }
1518                }
1519                State::BeforeAttributeName => match self.byte() {
1520                    Some(b) if is_space(b) => self.pos += 1,
1521                    None | Some(b'/' | b'>') => self.state = State::AfterAttributeName,
1522                    Some(b'=') => {
1523                        self.error(
1524                            sink,
1525                            "unexpected-equals-sign-before-attribute-name",
1526                            self.pos,
1527                        );
1528                        self.pos += 1;
1529                        self.start_attr(self.pos - 1);
1530                        self.attr_buf.push('=');
1531                        self.state = State::AttributeName;
1532                    }
1533                    Some(_) => {
1534                        self.start_attr(self.pos);
1535                        self.state = State::AttributeName;
1536                    }
1537                },
1538                State::AttributeName => match self.byte() {
1539                    None => {
1540                        self.end_attr_name(sink, self.pos);
1541                        self.state = State::AfterAttributeName;
1542                    }
1543                    Some(b) if is_space(b) || b == b'/' || b == b'>' => {
1544                        self.end_attr_name(sink, self.pos);
1545                        self.state = State::AfterAttributeName;
1546                    }
1547                    Some(b'=') => {
1548                        self.pos += 1;
1549                        self.end_attr_name(sink, self.pos - 1);
1550                        self.state = State::BeforeAttributeValue;
1551                    }
1552                    Some(0) => {
1553                        self.error(sink, "unexpected-null-character", self.pos);
1554                        self.pos += 1;
1555                        self.flush_attr_name();
1556                        self.attr_buf.push_str(REPLACEMENT);
1557                    }
1558                    Some(_) => {
1559                        let start = self.pos;
1560                        let end = scan(bytes, start, |b| {
1561                            is_space(b) || matches!(b, b'/' | b'>' | b'=' | 0)
1562                        });
1563                        if self.errors {
1564                            self.misplaced(sink, start, end, b"\"'<", "attribute-name");
1565                        }
1566                        self.push_attr_name(start, end);
1567                        self.pos = end;
1568                    }
1569                },
1570                State::AfterAttributeName => match self.byte() {
1571                    Some(b) if is_space(b) => self.pos += 1,
1572                    Some(b'/') => {
1573                        self.pos += 1;
1574                        self.state = State::SelfClosingStartTag;
1575                    }
1576                    Some(b'=') => {
1577                        self.pos += 1;
1578                        self.state = State::BeforeAttributeValue;
1579                    }
1580                    Some(b'>') => {
1581                        self.pos += 1;
1582                        self.emit_tag(sink);
1583                    }
1584                    None => {
1585                        self.error(sink, "eof-in-tag", self.pos);
1586                        sink.eof();
1587                        return;
1588                    }
1589                    Some(_) => {
1590                        self.start_attr(self.pos);
1591                        self.state = State::AttributeName;
1592                    }
1593                },
1594                State::BeforeAttributeValue => match self.byte() {
1595                    Some(b) if is_space(b) => self.pos += 1,
1596                    Some(b'"') => {
1597                        self.pos += 1;
1598                        self.value_from = Some(self.pos);
1599                        self.state = State::AttributeValueDoubleQuoted;
1600                    }
1601                    Some(b'\'') => {
1602                        self.pos += 1;
1603                        self.value_from = Some(self.pos);
1604                        self.state = State::AttributeValueSingleQuoted;
1605                    }
1606                    Some(b'>') => {
1607                        self.error(sink, "missing-attribute-value", self.pos);
1608                        self.pos += 1;
1609                        self.emit_tag(sink);
1610                    }
1611                    _ => {
1612                        self.value_from = Some(self.pos);
1613                        self.state = State::AttributeValueUnquoted;
1614                    }
1615                },
1616                State::AttributeValueDoubleQuoted | State::AttributeValueSingleQuoted => {
1617                    let quote = if self.state == State::AttributeValueDoubleQuoted {
1618                        b'"'
1619                    } else {
1620                        b'\''
1621                    };
1622                    let rest = &bytes[self.pos..];
1623                    let Some(i) = memchr3(quote, b'&', 0, rest) else {
1624                        if PARTIAL {
1625                            // The value goes on: still a slice of the
1626                            // input, or in the buffer.
1627                            if self.value_from.is_none() {
1628                                self.attr_buf.push_str(&input[self.pos..]);
1629                            }
1630                            self.pos = bytes.len();
1631                            return;
1632                        }
1633                        self.error(sink, "eof-in-tag", bytes.len());
1634                        sink.eof();
1635                        return;
1636                    };
1637                    let at = self.pos + i;
1638                    if rest[i] == quote {
1639                        if self.value_from.is_none() {
1640                            self.attr_buf.push_str(&input[self.pos..at]);
1641                        }
1642                        self.end_value(at, at + 1);
1643                        self.pos = at + 1;
1644                        self.state = State::AfterAttributeValueQuoted;
1645                    } else {
1646                        if PARTIAL && rest[i] == b'&' {
1647                            let from = self.pos;
1648                            self.pos = at + 1;
1649                            if !self.ref_ready() {
1650                                // Back to the `&`, the value so far kept.
1651                                if self.value_from.is_none() {
1652                                    self.attr_buf.push_str(&input[from..at]);
1653                                }
1654                                self.pos = at;
1655                                return;
1656                            }
1657                            self.pos = from;
1658                        }
1659                        if self.value_from.is_some() {
1660                            self.flush_value(at);
1661                        } else {
1662                            self.attr_buf.push_str(&input[self.pos..at]);
1663                        }
1664                        self.pos = at + 1;
1665                        if rest[i] == b'&' {
1666                            self.char_ref(sink, true);
1667                        } else {
1668                            self.error(sink, "unexpected-null-character", at);
1669                            self.attr_buf.push_str(REPLACEMENT);
1670                        }
1671                    }
1672                }
1673                State::AttributeValueUnquoted => match self.byte() {
1674                    None => {
1675                        self.error(sink, "eof-in-tag", self.pos);
1676                        sink.eof();
1677                        return;
1678                    }
1679                    Some(b) if is_space(b) => {
1680                        self.end_value(self.pos, self.pos);
1681                        self.pos += 1;
1682                        self.state = State::BeforeAttributeName;
1683                    }
1684                    Some(b'&') => {
1685                        if PARTIAL {
1686                            self.pos += 1;
1687                            let ready = self.ref_ready();
1688                            self.pos -= 1;
1689                            if !ready {
1690                                return;
1691                            }
1692                        }
1693                        self.flush_value(self.pos);
1694                        self.pos += 1;
1695                        self.char_ref(sink, true);
1696                    }
1697                    Some(b'>') => {
1698                        self.end_value(self.pos, self.pos);
1699                        self.pos += 1;
1700                        self.emit_tag(sink);
1701                    }
1702                    Some(0) => {
1703                        self.error(sink, "unexpected-null-character", self.pos);
1704                        self.flush_value(self.pos);
1705                        self.pos += 1;
1706                        self.attr_buf.push_str(REPLACEMENT);
1707                    }
1708                    Some(_) => {
1709                        let start = self.pos;
1710                        let end = scan(bytes, start, |b| {
1711                            is_space(b) || matches!(b, b'&' | b'>' | 0)
1712                        });
1713                        if self.errors {
1714                            self.misplaced(sink, start, end, b"\"'<=`", "unquoted-attribute-value");
1715                        }
1716                        if self.value_from.is_none() {
1717                            self.attr_buf.push_str(&input[start..end]);
1718                        }
1719                        self.pos = end;
1720                    }
1721                },
1722                State::AfterAttributeValueQuoted => match self.byte() {
1723                    Some(b) if is_space(b) => {
1724                        self.pos += 1;
1725                        self.state = State::BeforeAttributeName;
1726                    }
1727                    Some(b'/') => {
1728                        self.pos += 1;
1729                        self.state = State::SelfClosingStartTag;
1730                    }
1731                    Some(b'>') => {
1732                        self.pos += 1;
1733                        self.emit_tag(sink);
1734                    }
1735                    None => {
1736                        self.error(sink, "eof-in-tag", self.pos);
1737                        sink.eof();
1738                        return;
1739                    }
1740                    Some(_) => {
1741                        self.error(sink, "missing-whitespace-between-attributes", self.pos);
1742                        self.state = State::BeforeAttributeName;
1743                    }
1744                },
1745                State::SelfClosingStartTag => match self.byte() {
1746                    Some(b'>') => {
1747                        self.pos += 1;
1748                        self.self_closing = true;
1749                        self.emit_tag(sink);
1750                    }
1751                    None => {
1752                        self.error(sink, "eof-in-tag", self.pos);
1753                        sink.eof();
1754                        return;
1755                    }
1756                    Some(_) => {
1757                        self.error(sink, "unexpected-solidus-in-tag", self.pos);
1758                        self.state = State::BeforeAttributeName;
1759                    }
1760                },
1761                State::BogusComment => {
1762                    let rest = &bytes[self.pos..];
1763                    match memchr2(b'>', 0, rest) {
1764                        None => {
1765                            self.comment.push_str(&input[self.pos..]);
1766                            self.pos = bytes.len();
1767                            if PARTIAL {
1768                                return;
1769                            }
1770                            self.emit_comment(sink);
1771                            sink.eof();
1772                            return;
1773                        }
1774                        Some(i) => {
1775                            self.comment.push_str(&input[self.pos..self.pos + i]);
1776                            self.pos += i + 1;
1777                            if rest[i] == 0 {
1778                                self.error(sink, "unexpected-null-character", self.pos - 1);
1779                                self.comment.push_str(REPLACEMENT);
1780                            } else {
1781                                self.emit_comment(sink);
1782                            }
1783                        }
1784                    }
1785                }
1786                State::ProcessingInstructionOpen => match self.byte() {
1787                    Some(b) if b.is_ascii_alphabetic() || b == b'_' => {
1788                        self.state = State::ProcessingInstructionTarget;
1789                    }
1790                    None => {
1791                        self.error(sink, "eof-in-processing-instruction", self.pos);
1792                        sink.eof();
1793                        return;
1794                    }
1795                    Some(_) => {
1796                        self.error(
1797                            sink,
1798                            "invalid-first-character-of-processing-instruction-target",
1799                            self.pos,
1800                        );
1801                        self.pi_to_comment();
1802                    }
1803                },
1804                State::ProcessingInstructionTarget => {
1805                    let start = self.pos;
1806                    let end = scan(bytes, start, |b| {
1807                        !(b.is_ascii_alphanumeric() || b == b'-' || b == b'_')
1808                    });
1809                    self.pi_target.push_str(&input[start..end]);
1810                    self.pos = end;
1811                    if PARTIAL && end == bytes.len() {
1812                        return;
1813                    }
1814                    match self.byte() {
1815                        None => {
1816                            self.error(sink, "eof-in-processing-instruction", self.pos);
1817                            sink.eof();
1818                            return;
1819                        }
1820                        Some(b) if is_space(b) || b == b'?' || b == b'>' => {
1821                            let t = self.pi_target.as_bytes();
1822                            if t.eq_ignore_ascii_case(b"xml")
1823                                || t.eq_ignore_ascii_case(b"xml-stylesheet")
1824                            {
1825                                self.error(
1826                                    sink,
1827                                    "disallowed-processing-instruction-target",
1828                                    self.pos,
1829                                );
1830                                self.pi_to_comment();
1831                            } else {
1832                                self.pi_data.clear();
1833                                self.pi_target_end = self.pos;
1834                                self.state = State::AfterProcessingInstructionTarget;
1835                            }
1836                        }
1837                        Some(_) => self.pi_to_comment(),
1838                    }
1839                }
1840                State::AfterProcessingInstructionTarget => match self.byte() {
1841                    Some(b) if is_space(b) => self.pos += 1,
1842                    _ => self.state = State::ProcessingInstructionData,
1843                },
1844                State::ProcessingInstructionData => {
1845                    let rest = &bytes[self.pos..];
1846                    let Some(i) = memchr2(b'?', b'>', rest) else {
1847                        if PARTIAL {
1848                            self.pi_data.push_str(&input[self.pos..]);
1849                            self.pos = bytes.len();
1850                            return;
1851                        }
1852                        self.pos = bytes.len();
1853                        self.error(sink, "eof-in-processing-instruction", self.pi_target_end);
1854                        sink.eof();
1855                        return;
1856                    };
1857                    self.pi_data.push_str(&input[self.pos..self.pos + i]);
1858                    self.pos += i + 1;
1859                    if rest[i] == b'?' {
1860                        self.state = State::ProcessingInstructionQuestionable;
1861                    } else {
1862                        self.emit_pi(sink);
1863                    }
1864                }
1865                State::ProcessingInstructionQuestionable => match self.byte() {
1866                    Some(b'>') => {
1867                        self.pos += 1;
1868                        self.emit_pi(sink);
1869                    }
1870                    None => {
1871                        self.error(sink, "eof-in-processing-instruction", self.pi_target_end);
1872                        sink.eof();
1873                        return;
1874                    }
1875                    Some(_) => {
1876                        self.pi_data.push('?');
1877                        self.state = State::ProcessingInstructionData;
1878                    }
1879                },
1880                State::MarkupDeclarationOpen => {
1881                    let rest = self.rest().as_bytes();
1882                    self.comment.clear();
1883                    if rest.starts_with(b"--") {
1884                        self.pos += 2;
1885                        self.state = State::CommentStart;
1886                    } else if PARTIAL
1887                        && rest.len() < 7
1888                        && (rest == b"-"
1889                            || rest.eq_ignore_ascii_case(&b"doctype"[..rest.len()])
1890                            || b"[CDATA[".starts_with(rest))
1891                    {
1892                        // Too little to tell which it is.
1893                        return;
1894                    } else if rest.len() >= 7 && rest[..7].eq_ignore_ascii_case(b"doctype") {
1895                        self.pos += 7;
1896                        self.state = State::Doctype;
1897                    } else if rest.starts_with(b"[CDATA[") {
1898                        self.pos += 7;
1899                        if sink.cdata_allowed() {
1900                            self.state = State::CdataSection;
1901                        } else {
1902                            self.error(sink, "cdata-in-html-content", self.pos - 1);
1903                            self.comment.push_str("[CDATA[");
1904                            self.state = State::BogusComment;
1905                        }
1906                    } else {
1907                        self.error(sink, "incorrectly-opened-comment", self.pos);
1908                        self.state = State::BogusComment;
1909                    }
1910                }
1911                State::CommentStart => match self.byte() {
1912                    Some(b'-') => {
1913                        self.pos += 1;
1914                        self.state = State::CommentStartDash;
1915                    }
1916                    Some(b'>') => {
1917                        self.error(sink, "abrupt-closing-of-empty-comment", self.pos);
1918                        self.pos += 1;
1919                        self.emit_comment(sink);
1920                    }
1921                    _ => self.state = State::Comment,
1922                },
1923                State::CommentStartDash => match self.byte() {
1924                    Some(b'-') => {
1925                        self.pos += 1;
1926                        self.state = State::CommentEnd;
1927                    }
1928                    Some(b'>') => {
1929                        self.error(sink, "abrupt-closing-of-empty-comment", self.pos);
1930                        self.pos += 1;
1931                        self.emit_comment(sink);
1932                    }
1933                    None => {
1934                        self.error(sink, "eof-in-comment", self.pos);
1935                        self.emit_comment(sink);
1936                        sink.eof();
1937                        return;
1938                    }
1939                    Some(_) => {
1940                        self.comment.push('-');
1941                        self.state = State::Comment;
1942                    }
1943                },
1944                State::Comment => {
1945                    let rest = &bytes[self.pos..];
1946                    let Some(i) = memchr3(b'<', b'-', 0, rest) else {
1947                        self.comment.push_str(&input[self.pos..]);
1948                        self.pos = bytes.len();
1949                        if PARTIAL {
1950                            return;
1951                        }
1952                        self.error(sink, "eof-in-comment", self.pos);
1953                        self.emit_comment(sink);
1954                        sink.eof();
1955                        return;
1956                    };
1957                    self.comment.push_str(&input[self.pos..self.pos + i]);
1958                    self.pos += i + 1;
1959                    match rest[i] {
1960                        b'<' => {
1961                            self.comment.push('<');
1962                            self.state = State::CommentLessThan;
1963                        }
1964                        b'-' => self.state = State::CommentEndDash,
1965                        _ => {
1966                            self.error(sink, "unexpected-null-character", self.pos - 1);
1967                            self.comment.push_str(REPLACEMENT);
1968                        }
1969                    }
1970                }
1971                State::CommentLessThan => match self.byte() {
1972                    Some(b'!') => {
1973                        self.pos += 1;
1974                        self.comment.push('!');
1975                        self.state = State::CommentLessThanBang;
1976                    }
1977                    Some(b'<') => {
1978                        self.pos += 1;
1979                        self.comment.push('<');
1980                    }
1981                    _ => self.state = State::Comment,
1982                },
1983                State::CommentLessThanBang => {
1984                    if self.byte() == Some(b'-') {
1985                        self.pos += 1;
1986                        self.state = State::CommentLessThanBangDash;
1987                    } else {
1988                        self.state = State::Comment;
1989                    }
1990                }
1991                State::CommentLessThanBangDash => {
1992                    if self.byte() == Some(b'-') {
1993                        self.pos += 1;
1994                        self.state = State::CommentLessThanBangDashDash;
1995                    } else {
1996                        self.state = State::CommentEndDash;
1997                    }
1998                }
1999                State::CommentLessThanBangDashDash => {
2000                    if !matches!(self.byte(), None | Some(b'>')) {
2001                        self.error(sink, "nested-comment", self.pos);
2002                    }
2003                    self.state = State::CommentEnd;
2004                }
2005                State::CommentEndDash => match self.byte() {
2006                    Some(b'-') => {
2007                        self.pos += 1;
2008                        self.state = State::CommentEnd;
2009                    }
2010                    None => {
2011                        self.error(sink, "eof-in-comment", self.pos);
2012                        self.emit_comment(sink);
2013                        sink.eof();
2014                        return;
2015                    }
2016                    Some(_) => {
2017                        self.comment.push('-');
2018                        self.state = State::Comment;
2019                    }
2020                },
2021                State::CommentEnd => match self.byte() {
2022                    Some(b'>') => {
2023                        self.pos += 1;
2024                        self.emit_comment(sink);
2025                    }
2026                    Some(b'!') => {
2027                        self.pos += 1;
2028                        self.state = State::CommentEndBang;
2029                    }
2030                    Some(b'-') => {
2031                        self.pos += 1;
2032                        self.comment.push('-');
2033                    }
2034                    None => {
2035                        self.error(sink, "eof-in-comment", self.pos);
2036                        self.emit_comment(sink);
2037                        sink.eof();
2038                        return;
2039                    }
2040                    Some(_) => {
2041                        self.comment.push_str("--");
2042                        self.state = State::Comment;
2043                    }
2044                },
2045                State::CommentEndBang => match self.byte() {
2046                    Some(b'-') => {
2047                        self.pos += 1;
2048                        self.comment.push_str("--!");
2049                        self.state = State::CommentEndDash;
2050                    }
2051                    Some(b'>') => {
2052                        self.error(sink, "incorrectly-closed-comment", self.pos);
2053                        self.pos += 1;
2054                        self.emit_comment(sink);
2055                    }
2056                    None => {
2057                        self.error(sink, "eof-in-comment", self.pos);
2058                        self.emit_comment(sink);
2059                        sink.eof();
2060                        return;
2061                    }
2062                    Some(_) => {
2063                        self.comment.push_str("--!");
2064                        self.state = State::Comment;
2065                    }
2066                },
2067                State::Doctype => match self.byte() {
2068                    Some(b) if is_space(b) => {
2069                        self.pos += 1;
2070                        self.state = State::BeforeDoctypeName;
2071                    }
2072                    None => {
2073                        self.new_doctype();
2074                        self.quirky_doctype_eof(sink);
2075                        return;
2076                    }
2077                    Some(b) => {
2078                        if b != b'>' {
2079                            self.error(sink, "missing-whitespace-before-doctype-name", self.pos);
2080                        }
2081                        self.state = State::BeforeDoctypeName;
2082                    }
2083                },
2084                State::BeforeDoctypeName => match self.byte() {
2085                    Some(b) if is_space(b) => self.pos += 1,
2086                    Some(b'>') => {
2087                        self.error(sink, "missing-doctype-name", self.pos);
2088                        self.pos += 1;
2089                        self.new_doctype();
2090                        self.force_quirks = true;
2091                        self.emit_doctype(sink);
2092                    }
2093                    None => {
2094                        self.new_doctype();
2095                        self.quirky_doctype_eof(sink);
2096                        return;
2097                    }
2098                    Some(_) => {
2099                        self.new_doctype();
2100                        self.doctype_name = Some(String::new());
2101                        self.state = State::DoctypeName;
2102                    }
2103                },
2104                State::DoctypeName => match self.byte() {
2105                    Some(b) if is_space(b) => {
2106                        self.pos += 1;
2107                        self.state = State::AfterDoctypeName;
2108                    }
2109                    Some(b'>') => {
2110                        self.pos += 1;
2111                        self.emit_doctype(sink);
2112                    }
2113                    None => {
2114                        self.quirky_doctype_eof(sink);
2115                        return;
2116                    }
2117                    Some(0) => {
2118                        self.error(sink, "unexpected-null-character", self.pos);
2119                        self.pos += 1;
2120                        self.doctype_name.as_mut().unwrap().push_str(REPLACEMENT);
2121                    }
2122                    Some(_) => {
2123                        let start = self.pos;
2124                        let end = scan(bytes, start, |b| is_space(b) || matches!(b, b'>' | 0));
2125                        push_lower(self.doctype_name.as_mut().unwrap(), &input[start..end]);
2126                        self.pos = end;
2127                    }
2128                },
2129                State::AfterDoctypeName => match self.byte() {
2130                    Some(b) if is_space(b) => self.pos += 1,
2131                    Some(b'>') => {
2132                        self.pos += 1;
2133                        self.emit_doctype(sink);
2134                    }
2135                    None => {
2136                        self.quirky_doctype_eof(sink);
2137                        return;
2138                    }
2139                    Some(_) => {
2140                        let rest = self.rest().as_bytes();
2141                        let prefix = |w: &[u8]| {
2142                            rest.len() < 6 && rest.eq_ignore_ascii_case(&w[..rest.len()])
2143                        };
2144                        if PARTIAL && (prefix(b"public") || prefix(b"system")) {
2145                            return;
2146                        }
2147                        let word = |w: &[u8]| rest.len() >= 6 && rest[..6].eq_ignore_ascii_case(w);
2148                        if word(b"public") {
2149                            self.pos += 6;
2150                            self.state = State::AfterDoctypePublicKeyword;
2151                        } else if word(b"system") {
2152                            self.pos += 6;
2153                            self.state = State::AfterDoctypeSystemKeyword;
2154                        } else {
2155                            self.error(
2156                                sink,
2157                                "invalid-character-sequence-after-doctype-name",
2158                                self.pos,
2159                            );
2160                            self.force_quirks = true;
2161                            self.state = State::BogusDoctype;
2162                        }
2163                    }
2164                },
2165                State::AfterDoctypePublicKeyword
2166                | State::BeforeDoctypePublicIdentifier
2167                | State::AfterDoctypeSystemKeyword
2168                | State::BeforeDoctypeSystemIdentifier
2169                | State::AfterDoctypePublicIdentifier
2170                | State::BetweenDoctypePublicAndSystemIdentifiers => {
2171                    let state = self.state;
2172                    match self.byte() {
2173                        Some(b) if is_space(b) => {
2174                            self.pos += 1;
2175                            self.state = match state {
2176                                State::AfterDoctypePublicKeyword => {
2177                                    State::BeforeDoctypePublicIdentifier
2178                                }
2179                                State::AfterDoctypeSystemKeyword => {
2180                                    State::BeforeDoctypeSystemIdentifier
2181                                }
2182                                State::AfterDoctypePublicIdentifier => {
2183                                    State::BetweenDoctypePublicAndSystemIdentifiers
2184                                }
2185                                _ => state,
2186                            };
2187                        }
2188                        Some(q @ (b'"' | b'\'')) => {
2189                            let missing = match state {
2190                                State::AfterDoctypePublicKeyword => {
2191                                    Some("missing-whitespace-after-doctype-public-keyword")
2192                                }
2193                                State::AfterDoctypeSystemKeyword => {
2194                                    Some("missing-whitespace-after-doctype-system-keyword")
2195                                }
2196                                State::AfterDoctypePublicIdentifier => Some(
2197                                    "missing-whitespace-between-doctype-public-and-system-identifiers",
2198                                ),
2199                                _ => None,
2200                            };
2201                            if let Some(code) = missing {
2202                                self.error(sink, code, self.pos);
2203                            }
2204                            self.pos += 1;
2205                            let public = matches!(
2206                                state,
2207                                State::AfterDoctypePublicKeyword
2208                                    | State::BeforeDoctypePublicIdentifier
2209                            );
2210                            let double = q == b'"';
2211                            if public {
2212                                self.public_id = Some(String::new());
2213                                self.state = if double {
2214                                    State::DoctypePublicIdentifierDoubleQuoted
2215                                } else {
2216                                    State::DoctypePublicIdentifierSingleQuoted
2217                                };
2218                            } else {
2219                                self.system_id = Some(String::new());
2220                                self.state = if double {
2221                                    State::DoctypeSystemIdentifierDoubleQuoted
2222                                } else {
2223                                    State::DoctypeSystemIdentifierSingleQuoted
2224                                };
2225                            }
2226                        }
2227                        Some(b'>') => {
2228                            match state {
2229                                State::AfterDoctypePublicKeyword
2230                                | State::BeforeDoctypePublicIdentifier => {
2231                                    self.error(sink, "missing-doctype-public-identifier", self.pos);
2232                                }
2233                                State::AfterDoctypeSystemKeyword
2234                                | State::BeforeDoctypeSystemIdentifier => {
2235                                    self.error(sink, "missing-doctype-system-identifier", self.pos);
2236                                }
2237                                _ => {}
2238                            }
2239                            self.pos += 1;
2240                            if !matches!(
2241                                state,
2242                                State::AfterDoctypePublicIdentifier
2243                                    | State::BetweenDoctypePublicAndSystemIdentifiers
2244                            ) {
2245                                self.force_quirks = true;
2246                            }
2247                            self.emit_doctype(sink);
2248                        }
2249                        None => {
2250                            self.quirky_doctype_eof(sink);
2251                            return;
2252                        }
2253                        Some(_) => {
2254                            let code = match state {
2255                                State::AfterDoctypePublicKeyword
2256                                | State::BeforeDoctypePublicIdentifier => {
2257                                    "missing-quote-before-doctype-public-identifier"
2258                                }
2259                                _ => "missing-quote-before-doctype-system-identifier",
2260                            };
2261                            self.error(sink, code, self.pos);
2262                            self.force_quirks = true;
2263                            self.state = State::BogusDoctype;
2264                        }
2265                    }
2266                }
2267                State::DoctypePublicIdentifierDoubleQuoted
2268                | State::DoctypePublicIdentifierSingleQuoted
2269                | State::DoctypeSystemIdentifierDoubleQuoted
2270                | State::DoctypeSystemIdentifierSingleQuoted => {
2271                    let state = self.state;
2272                    let public = matches!(
2273                        state,
2274                        State::DoctypePublicIdentifierDoubleQuoted
2275                            | State::DoctypePublicIdentifierSingleQuoted
2276                    );
2277                    let quote = if matches!(
2278                        state,
2279                        State::DoctypePublicIdentifierDoubleQuoted
2280                            | State::DoctypeSystemIdentifierDoubleQuoted
2281                    ) {
2282                        b'"'
2283                    } else {
2284                        b'\''
2285                    };
2286                    let rest = &bytes[self.pos..];
2287                    let id = if public {
2288                        self.public_id.as_mut().unwrap()
2289                    } else {
2290                        self.system_id.as_mut().unwrap()
2291                    };
2292                    let Some(i) = memchr3(quote, b'>', 0, rest) else {
2293                        id.push_str(&input[self.pos..]);
2294                        self.pos = bytes.len();
2295                        if PARTIAL {
2296                            return;
2297                        }
2298                        self.quirky_doctype_eof(sink);
2299                        return;
2300                    };
2301                    id.push_str(&input[self.pos..self.pos + i]);
2302                    self.pos += i + 1;
2303                    match rest[i] {
2304                        0 => {
2305                            id.push_str(REPLACEMENT);
2306                            self.error(sink, "unexpected-null-character", self.pos - 1);
2307                        }
2308                        b'>' => {
2309                            let code = if public {
2310                                "abrupt-doctype-public-identifier"
2311                            } else {
2312                                "abrupt-doctype-system-identifier"
2313                            };
2314                            self.error(sink, code, self.pos - 1);
2315                            self.force_quirks = true;
2316                            self.emit_doctype(sink);
2317                        }
2318                        _ => {
2319                            self.state = if public {
2320                                State::AfterDoctypePublicIdentifier
2321                            } else {
2322                                State::AfterDoctypeSystemIdentifier
2323                            };
2324                        }
2325                    }
2326                }
2327                State::AfterDoctypeSystemIdentifier => match self.byte() {
2328                    Some(b) if is_space(b) => self.pos += 1,
2329                    Some(b'>') => {
2330                        self.pos += 1;
2331                        self.emit_doctype(sink);
2332                    }
2333                    None => {
2334                        self.quirky_doctype_eof(sink);
2335                        return;
2336                    }
2337                    Some(_) => {
2338                        self.error(
2339                            sink,
2340                            "unexpected-character-after-doctype-system-identifier",
2341                            self.pos,
2342                        );
2343                        self.state = State::BogusDoctype;
2344                    }
2345                },
2346                State::BogusDoctype => {
2347                    let skipped = match memchr(b'>', &bytes[self.pos..]) {
2348                        None => bytes.len(),
2349                        Some(i) => self.pos + i,
2350                    };
2351                    if self.errors {
2352                        for i in memchr::memchr_iter(0, &bytes[self.pos..skipped]) {
2353                            sink.error("unexpected-null-character", self.pos + i);
2354                        }
2355                    }
2356                    if skipped == bytes.len() {
2357                        self.pos = bytes.len();
2358                        if PARTIAL {
2359                            return;
2360                        }
2361                        self.emit_doctype(sink);
2362                        sink.eof();
2363                        return;
2364                    }
2365                    self.pos = skipped + 1;
2366                    self.emit_doctype(sink);
2367                }
2368                State::CdataSection => {
2369                    let rest = &bytes[self.pos..];
2370                    match memchr::memmem::find(rest, b"]]>") {
2371                        None if PARTIAL => {
2372                            // The last `]` or `]]` may start the `]]>`.
2373                            let keep = rest
2374                                .iter()
2375                                .rev()
2376                                .take(2)
2377                                .take_while(|&&b| b == b']')
2378                                .count();
2379                            let cut = bytes.len() - keep;
2380                            if cut > self.pos {
2381                                emit_text(sink, &input[self.pos..cut], self.pos, cut);
2382                                self.pos = cut;
2383                            }
2384                            return;
2385                        }
2386                        None => {
2387                            if !rest.is_empty() {
2388                                emit_text(sink, &input[self.pos..], self.pos, bytes.len());
2389                            }
2390                            self.pos = bytes.len();
2391                            self.error(sink, "eof-in-cdata", self.pos);
2392                            sink.eof();
2393                            return;
2394                        }
2395                        Some(i) => {
2396                            if i > 0 {
2397                                emit_text(
2398                                    sink,
2399                                    &input[self.pos..self.pos + i],
2400                                    self.pos,
2401                                    self.pos + i,
2402                                );
2403                            }
2404                            self.pos += i + 3;
2405                            self.state = State::Data;
2406                        }
2407                    }
2408                }
2409            }
2410        }
2411    }
2412}
2413
2414/// Hands `sink` an error. Out of line, so the checks for errors cost the
2415/// state machine as little as they can when they're off.
2416#[cold]
2417#[inline(never)]
2418fn report<S: Sink>(sink: &mut S, code: &'static str, at: usize) {
2419    sink.error(code, at);
2420}
2421
2422/// The error a numeric character reference to `code` is, if any.
2423#[cold]
2424#[inline(never)]
2425fn reference_error<S: Sink>(sink: &mut S, code: u32, at: usize) {
2426    let problem = match code {
2427        0 => "null-character-reference",
2428        0x11_0000.. => "character-reference-outside-unicode-range",
2429        0xD800..=0xDFFF => "surrogate-character-reference",
2430        _ if noncharacter(code) => "noncharacter-character-reference",
2431        0x0D | 0x01..=0x08 | 0x0B | 0x0E..=0x1F | 0x7F..=0x9F => "control-character-reference",
2432        _ => return,
2433    };
2434    sink.error(problem, at);
2435}
2436
2437/// Whether `n` is one of Unicode's noncharacters: U+FDD0 to U+FDEF, and
2438/// the last two code points of every plane.
2439fn noncharacter(n: u32) -> bool {
2440    matches!(n, 0xFDD0..=0xFDEF) || (n & 0xFFFE == 0xFFFE && n <= 0x10_FFFF)
2441}
2442
2443/// Hands `sink` a run of text read from `start..end` of the input.
2444fn emit_text<S: Sink>(sink: &mut S, text: &str, start: usize, end: usize) {
2445    sink.position(start, end);
2446    sink.text(text);
2447}
2448
2449/// A table of the bytes that end a run: whitespace and `extra`.
2450const fn stops(extra: &[u8]) -> [bool; 256] {
2451    let mut t = [false; 256];
2452    t[b'\t' as usize] = true;
2453    t[b'\n' as usize] = true;
2454    t[0x0C] = true;
2455    t[b' ' as usize] = true;
2456    let mut i = 0;
2457    while i < extra.len() {
2458        t[extra[i] as usize] = true;
2459        i += 1;
2460    }
2461    t
2462}
2463
2464static TAG_NAME_END: [bool; 256] = stops(b"/>\0");
2465static ATTR_NAME_END: [bool; 256] = stops(b"/>=\0");
2466static UNQUOTED_END: [bool; 256] = stops(b"&>\0");
2467
2468/// The first index from `start` whose byte `stop` accepts, or the end.
2469fn scan(bytes: &[u8], start: usize, stop: impl Fn(u8) -> bool) -> usize {
2470    bytes[start..]
2471        .iter()
2472        .position(|&b| stop(b))
2473        .map_or(bytes.len(), |i| start + i)
2474}
2475
2476fn push_lower(to: &mut String, s: &str) {
2477    let at = to.len();
2478    to.push_str(s);
2479    to[at..].make_ascii_lowercase();
2480}
2481
2482/// The longest name without a semicolon, in bytes.
2483const LONGEST_LEGACY: usize = 6;
2484
2485/// Eight bytes of `s` from `at`, little-endian: the first `n` of them,
2486/// all 8 when `n` is 8 or more, and zeros after. The tables below are
2487/// made with it, at compile time.
2488const fn word(s: &[u8], at: usize, n: usize) -> u64 {
2489    let mut v = 0;
2490    let mut i = 0;
2491    while i < 8 && i < n {
2492        v |= (s[at + i] as u64) << (8 * i);
2493        i += 1;
2494    }
2495    v
2496}
2497
2498const HASH_BITS: u32 = 13;
2499
2500/// The slot in [`BY_HASH`] to look for a name from: its length, and its
2501/// first and last 8 bytes as [`word`] has them (or all of it, twice).
2502const fn name_slot(first: u64, last: u64, n: usize) -> usize {
2503    let mixed = (first ^ last.rotate_left(23) ^ n as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
2504    (mixed >> (64 - HASH_BITS)) as usize
2505}
2506
2507/// Every name's first 8 bytes, as [`word`] has them, so most names are
2508/// told apart from the one looked for without comparing their bytes.
2509static FIRST_WORDS: [u64; ENTITIES.len()] = {
2510    let mut t = [0; ENTITIES.len()];
2511    let mut i = 0;
2512    while i < t.len() {
2513        let name = ENTITIES[i].0.as_bytes();
2514        t[i] = word(name, 0, name.len());
2515        i += 1;
2516    }
2517    t
2518};
2519
2520/// [`ENTITIES`] as a hash table, by [`name_slot`] with linear probing:
2521/// one more than a name's index in it, or 0 for an empty slot.
2522static BY_HASH: [u16; 1 << HASH_BITS] = {
2523    let mut t = [0; 1 << HASH_BITS];
2524    let mut i = 0;
2525    while i < ENTITIES.len() {
2526        let name = ENTITIES[i].0.as_bytes();
2527        let n = name.len();
2528        let last = if n >= 8 {
2529            word(name, n - 8, 8)
2530        } else {
2531            FIRST_WORDS[i]
2532        };
2533        let mut slot = name_slot(FIRST_WORDS[i], last, n);
2534        while t[slot] != 0 {
2535            slot = (slot + 1) & (t.len() - 1);
2536        }
2537        t[slot] = i as u16 + 1;
2538        i += 1;
2539    }
2540    t
2541};
2542
2543/// The value of the named character reference that is the first `n`
2544/// bytes of `bytes`, without its `&`.
2545fn lookup(bytes: &[u8], n: usize) -> Option<&'static str> {
2546    debug_assert!(0 < n && n <= bytes.len());
2547    let (first, last) = if bytes.len() >= 8 {
2548        // Whole words, the bytes past the name masked off: no loop over
2549        // its length.
2550        let at = |i: usize| u64::from_le_bytes(bytes[i..i + 8].try_into().unwrap());
2551        let keep = u64::MAX >> (64 - 8 * n.min(8));
2552        (at(0) & keep, at(n.saturating_sub(8)) & keep)
2553    } else {
2554        let first = word(bytes, 0, n);
2555        (first, first)
2556    };
2557    let mut slot = name_slot(first, last, n);
2558    loop {
2559        let i = BY_HASH[slot].checked_sub(1)? as usize;
2560        let name = ENTITIES[i].0.as_bytes();
2561        if FIRST_WORDS[i] == first && name.len() == n && (n <= 8 || name[8..] == bytes[8..n]) {
2562            return Some(ENTITIES[i].1);
2563        }
2564        slot = (slot + 1) & (BY_HASH.len() - 1);
2565    }
2566}
2567
2568/// How many ASCII letters and digits `bytes` starts with, looked at 8
2569/// bytes at a time.
2570fn alnum_run(bytes: &[u8]) -> usize {
2571    const ONES: u64 = 0x0101_0101_0101_0101;
2572    const HIGH: u64 = ONES * 0x80;
2573    // The high bit of each byte of `x` from `lo` to `hi`, for bytes
2574    // below 0x80: neither subtraction borrows across bytes.
2575    let within = |x: u64, lo: u8, hi: u8| {
2576        ((x | HIGH) - ONES * lo as u64) & (ONES * (0x80 + hi as u64) - (x & !HIGH)) & !x & HIGH
2577    };
2578    let mut n = 0;
2579    while let Some(w) = bytes.get(n..n + 8) {
2580        let x = u64::from_le_bytes(w.try_into().unwrap());
2581        // Setting 0x20 makes the capitals small and no other byte a letter.
2582        let alnum = within(x, b'0', b'9') | within(x | (ONES * 0x20), b'a', b'z');
2583        let other = !alnum & HIGH;
2584        if other != 0 {
2585            return n + other.trailing_zeros() as usize / 8;
2586        }
2587        n += 8;
2588    }
2589    n + bytes[n..]
2590        .iter()
2591        .take_while(|b| b.is_ascii_alphanumeric())
2592        .count()
2593}
2594
2595/// The spec's replacements for numeric references to C1 controls, which
2596/// pages mean as Windows-1252.
2597fn c1(code: u32) -> char {
2598    let c = match code {
2599        0x80 => 0x20AC,
2600        0x82 => 0x201A,
2601        0x83 => 0x0192,
2602        0x84 => 0x201E,
2603        0x85 => 0x2026,
2604        0x86 => 0x2020,
2605        0x87 => 0x2021,
2606        0x88 => 0x02C6,
2607        0x89 => 0x2030,
2608        0x8A => 0x0160,
2609        0x8B => 0x2039,
2610        0x8C => 0x0152,
2611        0x8E => 0x017D,
2612        0x91 => 0x2018,
2613        0x92 => 0x2019,
2614        0x93 => 0x201C,
2615        0x94 => 0x201D,
2616        0x95 => 0x2022,
2617        0x96 => 0x2013,
2618        0x97 => 0x2014,
2619        0x98 => 0x02DC,
2620        0x99 => 0x2122,
2621        0x9A => 0x0161,
2622        0x9B => 0x203A,
2623        0x9C => 0x0153,
2624        0x9E => 0x017E,
2625        0x9F => 0x0178,
2626        other => other,
2627    };
2628    char::from_u32(c).unwrap()
2629}
2630
2631#[cfg(test)]
2632mod tests {
2633    use super::*;
2634
2635    #[test]
2636    fn every_name_is_found_by_its_hash() {
2637        for (name, value) in ENTITIES {
2638            // Alone, and with more after it, as in a page.
2639            assert_eq!(lookup(name.as_bytes(), name.len()), Some(value), "{name}");
2640            let more = format!("{name}abcdefgh;");
2641            assert_eq!(lookup(more.as_bytes(), name.len()), Some(value), "{name}");
2642            assert!(name.ends_with(';') || name.len() <= LONGEST_LEGACY);
2643        }
2644        assert_eq!(lookup(b"notit;", 6), None);
2645        assert_eq!(lookup(b"quot;", 3), None);
2646        assert_eq!(lookup(b"CounterClockwiseContourIntegral", 31), None);
2647    }
2648
2649    #[test]
2650    fn alnum_run_counts_letters_and_digits() {
2651        for s in [
2652            "",
2653            "a",
2654            "amp;",
2655            "AZaz09@[`{/:",
2656            "CounterClockwiseContourIntegral;",
2657            "abcdefgh",
2658            "abcdefghi&",
2659            "x\u{e9}y",
2660            "0123456789abcdefXYZ\u{80}",
2661        ] {
2662            let slow = s.bytes().take_while(u8::is_ascii_alphanumeric).count();
2663            assert_eq!(alnum_run(s.as_bytes()), slow, "{s:?}");
2664        }
2665        // Every byte, at each place in a word.
2666        for b in 0..=255u8 {
2667            for at in 0..8 {
2668                let mut v = b"abcdefgh".to_vec();
2669                v[at] = b;
2670                let want = if b.is_ascii_alphanumeric() { 8 } else { at };
2671                assert_eq!(alnum_run(&v), want, "{b:#x} at {at}");
2672            }
2673        }
2674    }
2675
2676    /// Every token, as text, for comparing two runs.
2677    #[derive(Default)]
2678    struct Record(Vec<String>);
2679
2680    impl Sink for Record {
2681        fn doctype(&mut self, d: &Doctype<'_>) {
2682            self.0.push(format!("{d:?}"));
2683        }
2684        fn start_tag(&mut self, t: &Tag<'_>) -> Option<TextMode> {
2685            let attrs: Vec<_> = t.attrs().collect();
2686            self.0
2687                .push(format!("<{} {attrs:?} {}>", t.name, t.self_closing));
2688            None
2689        }
2690        fn end_tag(&mut self, t: &Tag<'_>) {
2691            self.0.push(format!("</{}>", t.name));
2692        }
2693        fn comment(&mut self, text: &str) {
2694            self.0.push(format!("<!--{text}-->"));
2695        }
2696        fn processing_instruction(&mut self, target: &str, data: &str) {
2697            self.0.push(format!("<?{target} {data}>"));
2698        }
2699        fn text(&mut self, text: &str) {
2700            match self.0.last_mut() {
2701                Some(last) if last.starts_with('"') => last.push_str(text),
2702                _ => self.0.push(format!("\"{text}")),
2703            }
2704        }
2705        fn eof(&mut self) {
2706            self.0.push("EOF".into());
2707        }
2708        fn error(&mut self, code: &'static str, at: usize) {
2709            self.0.push(format!("!{code}@{at}"));
2710        }
2711    }
2712
2713    fn tokens(input: &str, fast: bool) -> Vec<String> {
2714        let mut t = Tokenizer::new(input);
2715        t.report_errors();
2716        t.fast = fast;
2717        let mut r = Record::default();
2718        t.run(&mut r);
2719        r.0
2720    }
2721
2722    /// Random tag soup, built from the pieces the fast path decides on,
2723    /// tokenizes the same with and without it, with the same errors.
2724    #[test]
2725    fn the_fast_path_reads_tags_as_the_states_do() {
2726        const PIECES: &[&str] = &[
2727            "<", ">", "/", "/>", "</", "a", "B", "div", " ", "\t", "\n", "=", "\"", "'", "&",
2728            "&amp;", "&#65;", "x", "-", "\0", "`", "<p", "<a ", "href", "id", "=x", "=\"v\"",
2729            "='v'", "é", "!", "?", ">text<",
2730        ];
2731        let mut seed: u64 = 0x2545_F491_4F6C_DD1D;
2732        let mut next = || {
2733            seed ^= seed << 13;
2734            seed ^= seed >> 7;
2735            seed ^= seed << 17;
2736            seed
2737        };
2738        for _ in 0..20_000 {
2739            let n = (next() % 24) as usize;
2740            let input: String = (0..n)
2741                .map(|_| PIECES[(next() % PIECES.len() as u64) as usize])
2742                .collect();
2743            assert_eq!(tokens(&input, true), tokens(&input, false), "{input:?}");
2744        }
2745    }
2746
2747    #[test]
2748    fn crlf_and_cr_become_lf() {
2749        assert_eq!(preprocess("a\r\nb\rc\n\r"), "a\nb\nc\n\n");
2750        assert!(matches!(preprocess("no returns"), Cow::Borrowed(_)));
2751    }
2752}