rama_http/protocols/html/tokenizer/
name.rs

1//! Compact, allocation-free hashing of element/tag names.
2//!
3//! HTML tag names are ASCII case-insensitive, so a name is hashed over its
4//! ASCII-lowercased bytes. The hash lets the tokenizer and (later) the
5//! tree-builder simulator dispatch on known tags (`script`, `style`, …)
6//! with a single integer comparison instead of repeated byte matching.
7
8/// A 64-bit hash of an ASCII-lowercased tag name.
9///
10/// `0` is reserved to mean "no / empty name". The hash is FNV-1a over the
11/// lowercased bytes; the known-tag constants below are verified to be
12/// collision-free by a test, which is all the dispatch paths rely on.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
14pub struct LocalNameHash(u64);
15
16const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
17const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
18
19impl LocalNameHash {
20    /// The reserved "no name" hash.
21    pub const NONE: Self = Self(0);
22
23    /// Hashes a tag name (ASCII-lowercasing as it goes). Returns
24    /// [`Self::NONE`] for an empty name.
25    #[must_use]
26    pub fn of(name: &[u8]) -> Self {
27        if name.is_empty() {
28            return Self::NONE;
29        }
30        let mut hash = FNV_OFFSET;
31        for &byte in name {
32            hash ^= u64::from(byte.to_ascii_lowercase());
33            hash = hash.wrapping_mul(FNV_PRIME);
34        }
35        Self(hash)
36    }
37
38    /// `const` constructor for known-tag constants from a static lowercase
39    /// byte string.
40    #[must_use]
41    pub const fn from_static(name: &'static [u8]) -> Self {
42        let mut hash = FNV_OFFSET;
43        let mut i = 0;
44        while i < name.len() {
45            // The static must already be lowercase: `of` lowercases, this does
46            // not, so an uppercase byte here would hash to a different value.
47            debug_assert!(!name[i].is_ascii_uppercase());
48            hash ^= name[i] as u64;
49            hash = hash.wrapping_mul(FNV_PRIME);
50            i += 1;
51        }
52        Self(hash)
53    }
54
55    /// Whether this is the reserved "no name" hash.
56    #[must_use]
57    pub const fn is_none(self) -> bool {
58        self.0 == 0
59    }
60
61    /// The raw hash value, for matching against known-tag constants (a `u64`
62    /// `match` lowers to a switch / binary search, unlike a struct compare).
63    pub(crate) const fn as_u64(self) -> u64 {
64        self.0
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use ahash::HashMap;
71
72    use super::LocalNameHash;
73
74    #[test]
75    fn case_insensitive_and_const_agreement() {
76        assert_eq!(LocalNameHash::of(b"DIV"), LocalNameHash::of(b"div"));
77        assert_eq!(LocalNameHash::of(b"ScRiPt"), LocalNameHash::of(b"script"));
78        assert_eq!(
79            LocalNameHash::of(b"script"),
80            LocalNameHash::from_static(b"script")
81        );
82        assert!(LocalNameHash::of(b"").is_none());
83        assert!(!LocalNameHash::of(b"div").is_none());
84    }
85
86    /// Hashing every distinct (lowercased) name across the full 1-3 ASCII-
87    /// letter space plus longer real tags must be collision-free: dispatch and
88    /// the rewriter's open-element matching compare names by hash alone.
89    #[test]
90    fn names_are_collision_free() {
91        let mut seen: HashMap<u64, Vec<u8>> = HashMap::default();
92        let mut check = |name: &[u8]| {
93            let hash = LocalNameHash::of(name);
94            if let Some(prev) = seen.insert(hash.0, name.to_vec())
95                && !prev.eq_ignore_ascii_case(name)
96            {
97                panic!("collision: {prev:?} vs {name:?}");
98            }
99        };
100
101        for a in b'a'..=b'z' {
102            check(&[a]);
103            for b in b'a'..=b'z' {
104                check(&[a, b]);
105                for c in b'a'..=b'z' {
106                    check(&[a, b, c]);
107                }
108            }
109        }
110        for tag in [
111            b"blockquote".as_slice(),
112            b"figcaption",
113            b"foreignobject",
114            b"plaintext",
115            b"textarea",
116            b"template",
117            b"noscript",
118            b"optgroup",
119        ] {
120            check(tag);
121        }
122    }
123}
rama_http/protocols/html/tokenizer/name.rs

rama_http/protocols/html/tokenizer/
name.rs
