horizon-browser

//! HTML tokenizer + arena-based DOM tree. Subset tags only (see the crate
//! README); anything unrecognized becomes `Tag::Other` so unknown elements
//! still contribute their text content and box instead of vanishing.
//!
//! Whitespace: runs of ASCII whitespace collapse to a single space at parse
//! time (except inside `<pre>`), but leading/trailing space on a text node
//! is kept rather than trimmed -- trimming here would jam adjacent inline
//! runs together (`"foo <b>bar</b>"` needs the space either side of `<b>`
//! to survive as separate text nodes). Layout trims the leading space of
//! each block's first inline run instead; a stray internal space is an
//! accepted v0.1 cosmetic gap, not a correctness bug.

use alloc::string::String;
use alloc::vec::Vec;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Tag {
    Html,
    Head,
    Body,
    Div,
    Span,
    P,
    H1,
    H2,
    H3,
    H4,
    H5,
    H6,
    A,
    B,
    I,
    Br,
    Ul,
    Ol,
    Li,
    Img,
    Canvas,
    Pre,
    Title,
    Style,
    Script,
    Text,
    Other,
}

impl Tag {
    pub fn from_name(name: &[u8]) -> Tag {
        let eq = |s: &str| name.eq_ignore_ascii_case(s.as_bytes());
        if eq("html") {
            Tag::Html
        } else if eq("head") {
            Tag::Head
        } else if eq("body") {
            Tag::Body
        } else if eq("div") || eq("section") || eq("article") || eq("nav") || eq("header") || eq("footer") || eq("main") {
            Tag::Div
        } else if eq("span") {
            Tag::Span
        } else if eq("p") {
            Tag::P
        } else if eq("h1") {
            Tag::H1
        } else if eq("h2") {
            Tag::H2
        } else if eq("h3") {
            Tag::H3
        } else if eq("h4") {
            Tag::H4
        } else if eq("h5") {
            Tag::H5
        } else if eq("h6") {
            Tag::H6
        } else if eq("a") {
            Tag::A
        } else if eq("b") || eq("strong") {
            Tag::B
        } else if eq("i") || eq("em") {
            Tag::I
        } else if eq("br") {
            Tag::Br
        } else if eq("ul") {
            Tag::Ul
        } else if eq("ol") {
            Tag::Ol
        } else if eq("li") {
            Tag::Li
        } else if eq("img") {
            Tag::Img
        } else if eq("canvas") {
            Tag::Canvas
        } else if eq("pre") {
            Tag::Pre
        } else if eq("title") {
            Tag::Title
        } else if eq("style") {
            Tag::Style
        } else if eq("script") {
            Tag::Script
        } else {
            Tag::Other
        }
    }

    pub fn is_void(self) -> bool {
        matches!(self, Tag::Br | Tag::Img)
    }
}

pub struct Attr {
    pub name: String,
    pub value: String,
}

pub struct Node {
    pub tag: Tag,
    pub attrs: Vec<Attr>,
    /// Text content, meaningful only for `Tag::Text` nodes.
    pub text: String,
    pub children: Vec<usize>,
}

impl Node {
    pub fn attr(&self, name: &str) -> Option<&str> {
        self.attrs.iter().find(|a| a.name.eq_ignore_ascii_case(name)).map(|a| a.value.as_str())
    }
}

pub struct Dom {
    pub nodes: Vec<Node>,
    pub root: usize,
}

pub fn parse(html: &[u8]) -> Dom {
    let mut nodes: Vec<Node> = Vec::new();
    nodes.push(Node { tag: Tag::Html, attrs: Vec::new(), text: String::new(), children: Vec::new() });
    let root = 0usize;
    let mut stack: Vec<usize> = Vec::new();
    stack.push(root);
    let mut text_buf = String::new();
    let n = html.len();
    let mut i = 0usize;

    while i < n {
        if html[i] == b'<' {
            flush_text(&mut nodes, *stack.last().unwrap(), &mut text_buf);

            if i + 1 < n && html[i + 1] == b'!' {
                if html[i..].starts_with(b"<!--") {
                    i = match find(&html[i + 4..], b"-->") {
                        Some(end) => i + 4 + end + 3,
                        None => n,
                    };
                } else {
                    i = match html[i..].iter().position(|&c| c == b'>') {
                        Some(end) => i + end + 1,
                        None => n,
                    };
                }
                continue;
            }

            if i + 1 < n && html[i + 1] == b'/' {
                let Some(gt) = html[i..].iter().position(|&c| c == b'>') else { break };
                let name = trim_bytes(&html[i + 2..i + gt]);
                i += gt + 1;
                let target = Tag::from_name(name);
                if let Some(pos) = stack.iter().rposition(|&idx| nodes[idx].tag == target) {
                    stack.truncate(pos);
                    if stack.is_empty() {
                        stack.push(root);
                    }
                }
                continue;
            }

            // Opening tag.
            let Some(gt) = html[i..].iter().position(|&c| c == b'>') else { break };
            let raw_inner = &html[i + 1..i + gt];
            let self_close = raw_inner.ends_with(b"/");
            let inner = if self_close { &raw_inner[..raw_inner.len() - 1] } else { raw_inner };
            i += gt + 1;
            let (name, attrs) = parse_tag(inner);
            let tag = Tag::from_name(name);

            if tag == Tag::Html {
                // The synthetic root (index 0) already represents <html>;
                // fold this explicit tag's attributes into it instead of
                // creating a duplicate nested node.
                nodes[root].attrs.extend(attrs);
                continue;
            }

            let parent = *stack.last().unwrap();
            let idx = nodes.len();
            nodes.push(Node { tag, attrs, text: String::new(), children: Vec::new() });
            nodes[parent].children.push(idx);

            if tag == Tag::Style || tag == Tag::Script {
                let close: &[u8] = if tag == Tag::Style { b"</style" } else { b"</script" };
                match find_ci(&html[i..], close) {
                    Some(rel) => {
                        let raw = &html[i..i + rel];
                        if tag == Tag::Style {
                            nodes[idx].text = String::from_utf8_lossy(raw).into_owned();
                        }
                        i = match html[i + rel..].iter().position(|&c| c == b'>') {
                            Some(p) => i + rel + p + 1,
                            None => n,
                        };
                    },
                    None => i = n,
                }
                continue;
            }

            if self_close || tag.is_void() {
                continue;
            }
            stack.push(idx);
            continue;
        }

        match html[i..].iter().position(|&c| c == b'<') {
            Some(rel) => {
                text_buf.push_str(&decode_entities(&html[i..i + rel]));
                i += rel;
            },
            None => {
                text_buf.push_str(&decode_entities(&html[i..]));
                i = n;
            },
        }
    }
    flush_text(&mut nodes, *stack.last().unwrap(), &mut text_buf);
    Dom { nodes, root }
}

fn flush_text(nodes: &mut Vec<Node>, parent: usize, text_buf: &mut String) {
    if text_buf.is_empty() {
        return;
    }
    let is_pre = nodes[parent].tag == Tag::Pre;
    let raw = core::mem::take(text_buf);
    let content = if is_pre { raw } else { collapse_ws(&raw) };
    if content.is_empty() {
        return;
    }
    let idx = nodes.len();
    nodes.push(Node { tag: Tag::Text, attrs: Vec::new(), text: content, children: Vec::new() });
    nodes[parent].children.push(idx);
}

fn collapse_ws(s: &str) -> String {
    let mut out = String::with_capacity(s.len());
    let mut last_ws = false;
    for ch in s.chars() {
        if ch.is_ascii_whitespace() {
            if !last_ws {
                out.push(' ');
            }
            last_ws = true;
        } else {
            out.push(ch);
            last_ws = false;
        }
    }
    out
}

fn parse_tag(inner: &[u8]) -> (&[u8], Vec<Attr>) {
    let mut i = 0usize;
    let n = inner.len();
    while i < n && !inner[i].is_ascii_whitespace() {
        i += 1;
    }
    let name = &inner[..i];
    let mut attrs = Vec::new();
    loop {
        while i < n && inner[i].is_ascii_whitespace() {
            i += 1;
        }
        if i >= n {
            break;
        }
        let start = i;
        while i < n && inner[i] != b'=' && !inner[i].is_ascii_whitespace() {
            i += 1;
        }
        let aname = &inner[start..i];
        if aname.is_empty() {
            break;
        }
        while i < n && inner[i].is_ascii_whitespace() {
            i += 1;
        }
        let mut value = String::new();
        if i < n && inner[i] == b'=' {
            i += 1;
            while i < n && inner[i].is_ascii_whitespace() {
                i += 1;
            }
            if i < n && (inner[i] == b'"' || inner[i] == b'\'') {
                let q = inner[i];
                i += 1;
                let vstart = i;
                while i < n && inner[i] != q {
                    i += 1;
                }
                value = decode_entities(&inner[vstart..i]);
                if i < n {
                    i += 1;
                }
            } else {
                let vstart = i;
                while i < n && !inner[i].is_ascii_whitespace() {
                    i += 1;
                }
                value = decode_entities(&inner[vstart..i]);
            }
        }
        attrs.push(Attr { name: String::from_utf8_lossy(aname).into_owned(), value });
    }
    (name, attrs)
}

fn decode_entities(bytes: &[u8]) -> String {
    let s = String::from_utf8_lossy(bytes);
    if !s.as_bytes().contains(&b'&') {
        return s.into_owned();
    }
    let mut out = String::with_capacity(s.len());
    let sb = s.as_bytes();
    let n = sb.len();
    let mut i = 0usize;
    while i < n {
        if sb[i] == b'&' {
            if let Some(end) = sb[i..].iter().position(|&c| c == b';').map(|p| i + p) {
                let ent = &s[i + 1..end];
                let rep = match ent {
                    "amp" => Some('&'),
                    "lt" => Some('<'),
                    "gt" => Some('>'),
                    "quot" => Some('"'),
                    "#39" | "apos" => Some('\''),
                    "nbsp" => Some('\u{a0}'),
                    _ => None,
                };
                if let Some(c) = rep {
                    out.push(c);
                    i = end + 1;
                    continue;
                }
            }
        }
        let ch_len = s[i..].chars().next().map(|c| c.len_utf8()).unwrap_or(1);
        out.push_str(&s[i..i + ch_len]);
        i += ch_len;
    }
    out
}

fn trim_bytes(b: &[u8]) -> &[u8] {
    let mut a = 0;
    let mut z = b.len();
    while a < z && b[a].is_ascii_whitespace() {
        a += 1;
    }
    while z > a && b[z - 1].is_ascii_whitespace() {
        z -= 1;
    }
    &b[a..z]
}

fn find(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    if needle.is_empty() || haystack.len() < needle.len() {
        return None;
    }
    (0..=haystack.len() - needle.len()).find(|&i| &haystack[i..i + needle.len()] == needle)
}

fn find_ci(haystack: &[u8], needle_lower: &[u8]) -> Option<usize> {
    if needle_lower.is_empty() || haystack.len() < needle_lower.len() {
        return None;
    }
    (0..=haystack.len() - needle_lower.len()).find(|&i| haystack[i..i + needle_lower.len()].eq_ignore_ascii_case(needle_lower))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn parses_basic_tree() {
        let dom = parse(b"<html><body><h1>Hi</h1><p>Hello <b>world</b>!</p></body></html>");
        let body = dom.nodes[dom.root].children[0];
        assert_eq!(dom.nodes[body].tag, Tag::Body);
        assert_eq!(dom.nodes[body].children.len(), 2);
    }

    #[test]
    fn keeps_space_around_inline_elements() {
        let dom = parse(b"<p>foo <b>bar</b> baz</p>");
        // Walk to <p>'s children and reconstitute the text to check no words fused.
        let p = dom.nodes[dom.root].children[0];
        let mut out = String::new();
        for &c in &dom.nodes[p].children {
            collect_text(&dom, c, &mut out);
        }
        assert_eq!(out, "foo bar baz");
    }

    fn collect_text(dom: &Dom, idx: usize, out: &mut String) {
        let node = &dom.nodes[idx];
        if node.tag == Tag::Text {
            out.push_str(&node.text);
        }
        for &c in &node.children {
            collect_text(dom, c, out);
        }
    }

    #[test]
    fn self_closing_img_does_not_swallow_siblings() {
        let dom = parse(b"<div><img src=\"a.png\"/><p>after</p></div>");
        let div = dom.nodes[dom.root].children[0];
        assert_eq!(dom.nodes[div].children.len(), 2);
        assert_eq!(dom.nodes[dom.nodes[div].children[0]].tag, Tag::Img);
        assert_eq!(dom.nodes[dom.nodes[div].children[1]].tag, Tag::P);
    }

    #[test]
    fn style_and_script_contents_are_not_parsed_as_tags() {
        let dom = parse(b"<style>p { color: red; }</style><script>if (1<2) {}</script><p>x</p>");
        let html_children = &dom.nodes[dom.root].children;
        // style, script, p -- three siblings, none of the '<' inside script spawned bogus nodes.
        assert_eq!(html_children.len(), 3);
        assert_eq!(dom.nodes[html_children[2]].tag, Tag::P);
    }

    #[test]
    fn entities_decode() {
        let dom = parse(b"<p>Tom &amp; Jerry &lt;3&gt;</p>");
        let p = dom.nodes[dom.root].children[0];
        let t = dom.nodes[p].children[0];
        assert_eq!(dom.nodes[t].text, "Tom & Jerry <3>");
    }
}