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