pdf_oxide 0.3.38

//! Box tree construction (LAYOUT-1).
//!
//! Walks the DOM in document order and a cascade-output style
//! resolver, producing a [`BoxTree`] — the semantic positioning tree
//! the rest of Phase LAYOUT operates on.
//!
//! Per CSS Display L3 §2.4, every element with a non-`none` display
//! produces one **principal box** plus, for some display values
//! (e.g. `list-item`), additional boxes. v0.3.35 generates only the
//! principal box for now; marker boxes wire in as part of the lists
//! work in LAYOUT-3.
//!
//! Anonymous block boxes get inserted per CSS 2.1 §9.2.1.1 when a
//! block container has a mix of block- and inline-level children —
//! the inline-level runs are wrapped in anonymous blocks so the
//! sibling-list is uniform. This matches what every browser engine
//! does and is what LAYOUT-2's Taffy mapping expects.
//!
//! Non-element nodes:
//! - `Text` → `BoxKind::Text` (always inline-level).
//! - `Comment`/`RawText` → skipped (raw text from `<style>`/`<script>`
//!   never reaches layout).
//!
//! `display: none` elements (and their subtrees) produce no box.
//! `display: contents` elements produce no principal box but their
//! children are emitted as if they were direct children of the
//! parent.

use thiserror::Error;

use crate::html_css::css::{
    cascade, parse_property, ComputedStyles, ResolvedValue, Stylesheet, Value,
};
use crate::html_css::html::{Dom, NodeId, NodeKind};

// ─────────────────────────────────────────────────────────────────────
// Display split per CSS Display L3
// ─────────────────────────────────────────────────────────────────────

/// "Outer display type" — how the box participates in its parent's
/// formatting context.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DisplayOutside {
    /// Block-level (paragraph, div, h1, …).
    Block,
    /// Inline-level (span, em, anchor, image, inline-block, …).
    Inline,
    /// `list-item` outer display.
    ListItem,
    /// Internal table boxes (table-row, table-cell, …) plus
    /// `display: contents` and `display: none`.
    Other,
}

/// "Inner display type" — what kind of formatting context the box
/// establishes.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DisplayInside {
    /// Block-and-inline formatting (the normal flow).
    Flow,
    /// `flow-root` — establishes a new BFC (block formatting context).
    FlowRoot,
    /// Flexbox container.
    Flex,
    /// Grid container.
    Grid,
    /// Outer table or table-* internal.
    Table,
    /// `inline-block` outer with flow inner.
    InlineBlock,
    /// No box generated.
    None,
    /// Children are unwrapped into the parent.
    Contents,
}

impl DisplayInside {
    /// True if this kind generates a principal box.
    pub fn generates_box(self) -> bool {
        !matches!(self, DisplayInside::None | DisplayInside::Contents)
    }
}

// ─────────────────────────────────────────────────────────────────────
// Box tree
// ─────────────────────────────────────────────────────────────────────

/// Index into [`BoxTree::boxes`].
pub type BoxId = u32;

/// One box in the tree.
#[derive(Debug, Clone)]
pub struct BoxNode {
    /// Source DOM element this box comes from. `None` for anonymous
    /// blocks (those generated by CSS 2.1 §9.2.1.1).
    pub element: Option<NodeId>,
    /// What kind of box.
    pub kind: BoxKind,
    /// Outer display.
    pub outside: DisplayOutside,
    /// Inner display (for kinds that have a formatting context).
    pub inside: DisplayInside,
    /// Direct children in tree order.
    pub children: Vec<BoxId>,
    /// Parent id, or `None` for the root.
    pub parent: Option<BoxId>,
}

/// Box-specific data.
#[derive(Debug, Clone)]
pub enum BoxKind {
    /// Element-backed principal box. The `element` field on the host
    /// `BoxNode` carries the source NodeId.
    Element,
    /// Anonymous block wrapping a run of inline-level boxes mixed
    /// with block-level siblings.
    AnonymousBlock,
    /// Text content from a [`NodeKind::Text`] DOM node.
    Text(String),
}

/// The whole box tree.
#[derive(Debug, Clone, Default)]
pub struct BoxTree {
    /// All boxes; box 0 is the root.
    pub boxes: Vec<BoxNode>,
}

impl BoxTree {
    /// Root box id.
    pub const ROOT: BoxId = 0;

    /// Look up a box by id.
    pub fn get(&self, id: BoxId) -> &BoxNode {
        &self.boxes[id as usize]
    }

    /// Number of boxes (including the root).
    pub fn len(&self) -> usize {
        self.boxes.len()
    }

    /// True if the tree only has the root.
    pub fn is_empty(&self) -> bool {
        self.boxes.len() <= 1
    }

    /// Iterate every BoxId in document order (depth-first pre-order).
    pub fn iter_ids(&self) -> Vec<BoxId> {
        let mut out = Vec::with_capacity(self.boxes.len());
        let mut stack: Vec<BoxId> = vec![Self::ROOT];
        while let Some(id) = stack.pop() {
            out.push(id);
            for &c in self.boxes[id as usize].children.iter().rev() {
                stack.push(c);
            }
        }
        out
    }
}

// ─────────────────────────────────────────────────────────────────────
// Errors
// ─────────────────────────────────────────────────────────────────────

/// Errors that can come out of box-tree construction.
#[derive(Debug, Clone, Error, PartialEq)]
pub enum BoxTreeError {
    /// Style resolver returned an unparseable display value.
    #[error("invalid display value on element {0}")]
    InvalidDisplay(NodeId),
}

// ─────────────────────────────────────────────────────────────────────
// Construction
// ─────────────────────────────────────────────────────────────────────

/// Build a box tree from a DOM and an effective stylesheet.
///
/// `stylesheet` is what the cascade walks; the caller is expected to
/// have already resolved `@media`/`@page` via
/// [`crate::html_css::css::resolve_stylesheet`] and passed only the
/// matching rules in. Inline-style attributes (HTML-3) are *not*
/// applied here — wire them in at the API layer per element.
///
/// The returned tree always has a single root box anchored at the
/// `<html>` element (or, if absent, at whichever element is the DOM's
/// first child).
pub fn build_box_tree(dom: &Dom, stylesheet: &Stylesheet<'_>) -> Result<BoxTree, BoxTreeError> {
    let mut tree = BoxTree::default();
    // Root box: anonymous block representing the initial containing
    // block. Per spec the root element (<html>) is its own box; we
    // wrap everything in an outer anonymous block so the iterator
    // surfaces a single root.
    tree.boxes.push(BoxNode {
        element: None,
        kind: BoxKind::AnonymousBlock,
        outside: DisplayOutside::Block,
        inside: DisplayInside::FlowRoot,
        children: Vec::new(),
        parent: None,
    });

    // Walk the DOM children of the synthetic Document root.
    let doc_node = dom.node(Dom::ROOT);

    for &child_id in &doc_node.children {
        build_subtree(dom, child_id, BoxTree::ROOT, stylesheet, None, &mut tree)?;
    }

    // Insert anonymous-block wrappers per CSS 2.1 §9.2.1.1: in any
    // block container, if some children are block-level and others are
    // inline-level, wrap each inline-only run in an anonymous block.
    insert_anonymous_blocks(&mut tree);

    Ok(tree)
}

fn build_subtree<'i>(
    dom: &Dom,
    node_id: NodeId,
    parent_box: BoxId,
    stylesheet: &'i Stylesheet<'i>,
    parent_styles: Option<&ComputedStyles<'i>>,
    tree: &mut BoxTree,
) -> Result<(), BoxTreeError> {
    match &dom.node(node_id).kind {
        NodeKind::Element { .. } => {
            let element = dom
                .element(node_id)
                .expect("NodeKind::Element guarantees DomElement");
            let styles = cascade(stylesheet, element, parent_styles);
            let tag_for_default = match &dom.node(node_id).kind {
                NodeKind::Element { tag, .. } => Some(tag.as_str()),
                _ => None,
            };
            let (outside, inside) = resolve_display_for(&styles, tag_for_default);
            if matches!(inside, DisplayInside::None) {
                return Ok(()); // skip the whole subtree
            }
            if matches!(inside, DisplayInside::Contents) {
                // Children are emitted as if they were direct children
                // of `parent_box`; this element produces no box.
                for &child in &dom.node(node_id).children {
                    build_subtree(dom, child, parent_box, stylesheet, Some(&styles), tree)?;
                }
                return Ok(());
            }
            let box_id = push_box(
                tree,
                BoxNode {
                    element: Some(node_id),
                    kind: BoxKind::Element,
                    outside,
                    inside,
                    children: Vec::new(),
                    parent: Some(parent_box),
                },
            );
            for &child in &dom.node(node_id).children {
                build_subtree(dom, child, box_id, stylesheet, Some(&styles), tree)?;
            }
        },
        NodeKind::Text(s) => {
            // Text is always inline-level. CSS 2.1 §9.2.2.1 requires
            // we strip whitespace-only text that sits between block
            // siblings — we defer that to the inline-formatter
            // (LAYOUT-3); for v0.3.35's box tree we keep all text and
            // let the consumer decide.
            push_box(
                tree,
                BoxNode {
                    element: None,
                    kind: BoxKind::Text(s.clone()),
                    outside: DisplayOutside::Inline,
                    inside: DisplayInside::Flow,
                    children: Vec::new(),
                    parent: Some(parent_box),
                },
            );
        },
        NodeKind::Comment(_) | NodeKind::RawText { .. } | NodeKind::Document => {
            // No layout footprint.
        },
    }
    Ok(())
}

fn push_box(tree: &mut BoxTree, mut node: BoxNode) -> BoxId {
    let id = tree.boxes.len() as BoxId;
    let parent = node.parent.expect("non-root boxes always have a parent");
    tree.boxes.push(node.clone());
    tree.boxes[parent as usize].children.push(id);
    let _ = &mut node;
    id
}

/// Resolve `display` (and the associated `position`/box-affecting
/// keywords) into outer + inner display types.
#[allow(dead_code)] // Convenience wrapper retained for future call sites
fn resolve_display(styles: &ComputedStyles<'_>) -> (DisplayOutside, DisplayInside) {
    resolve_display_for(styles, None)
}

fn resolve_display_for(
    styles: &ComputedStyles<'_>,
    tag: Option<&str>,
) -> (DisplayOutside, DisplayInside) {
    let display = styles
        .get("display")
        .and_then(|rv| typed_keyword(rv))
        .unwrap_or_else(|| ua_default_display(tag).to_string());
    match display.as_str() {
        "none" => (DisplayOutside::Block, DisplayInside::None),
        "contents" => (DisplayOutside::Inline, DisplayInside::Contents),
        "block" => (DisplayOutside::Block, DisplayInside::Flow),
        "flow-root" => (DisplayOutside::Block, DisplayInside::FlowRoot),
        "inline" => (DisplayOutside::Inline, DisplayInside::Flow),
        "inline-block" => (DisplayOutside::Inline, DisplayInside::InlineBlock),
        "flex" => (DisplayOutside::Block, DisplayInside::Flex),
        "inline-flex" => (DisplayOutside::Inline, DisplayInside::Flex),
        "grid" => (DisplayOutside::Block, DisplayInside::Grid),
        "inline-grid" => (DisplayOutside::Inline, DisplayInside::Grid),
        "list-item" => (DisplayOutside::ListItem, DisplayInside::Flow),
        "table" => (DisplayOutside::Block, DisplayInside::Table),
        "inline-table" => (DisplayOutside::Inline, DisplayInside::Table),
        // Internal table parts default to participating in their
        // containing table's formatting context — we return Other +
        // Flow as a placeholder; LAYOUT-7 (table layout) reads the raw
        // display keyword off the original computed style instead.
        "table-row" | "table-row-group" | "table-header-group" | "table-footer-group"
        | "table-cell" | "table-caption" | "table-column" | "table-column-group" => {
            (DisplayOutside::Other, DisplayInside::Flow)
        },
        _ => (DisplayOutside::Block, DisplayInside::Flow),
    }
}

/// Built-in user-agent default for `display` keyed by HTML tag name.
/// Returned only when the cascade did not supply a `display` rule.
/// Covers the v0.3.35 supported element set; everything else defaults
/// to CSS's spec initial value of `inline`.
///
/// A real UA stylesheet (CSS-9b — out of v0.3.35 first-cut) replaces
/// this hard-coded table with a parsed source.
fn ua_default_display(tag: Option<&str>) -> &'static str {
    let Some(tag) = tag else {
        return "inline";
    };
    match tag {
        "html" | "body" | "div" | "p" | "h1" | "h2" | "h3" | "h4" | "h5" | "h6" | "header"
        | "footer" | "main" | "section" | "article" | "aside" | "nav" | "address"
        | "blockquote" | "figure" | "figcaption" | "form" | "fieldset" | "hr" | "pre"
        | "dialog" => "block",
        "ul" | "ol" | "menu" | "dl" => "block",
        "li" | "dt" | "dd" => "list-item",
        "table" => "table",
        "thead" => "table-header-group",
        "tbody" => "table-row-group",
        "tfoot" => "table-footer-group",
        "tr" => "table-row",
        "td" | "th" => "table-cell",
        "caption" => "table-caption",
        "col" => "table-column",
        "colgroup" => "table-column-group",
        "head" | "title" | "meta" | "link" | "style" | "script" => "none",
        _ => "inline",
    }
}

fn typed_keyword(rv: &ResolvedValue<'_>) -> Option<String> {
    match parse_property("display", &rv.value) {
        Ok(Value::Keyword(s)) => Some(s),
        _ => None,
    }
}

// ─────────────────────────────────────────────────────────────────────
// Anonymous-block insertion (CSS 2.1 §9.2.1.1)
// ─────────────────────────────────────────────────────────────────────

fn insert_anonymous_blocks(tree: &mut BoxTree) {
    // Walk every box; if it's block-level and has a mix of block- and
    // inline-level children, wrap each maximal inline run in an
    // anonymous block.
    let mut i = 0u32;
    while (i as usize) < tree.boxes.len() {
        let host = &tree.boxes[i as usize];
        if matches!(host.outside, DisplayOutside::Block | DisplayOutside::ListItem)
            && matches!(host.inside, DisplayInside::Flow | DisplayInside::FlowRoot)
        {
            let kids: Vec<BoxId> = host.children.clone();
            // Find any block children — if none, no wrapping needed
            // (the block holds only inlines and acts as a single line
            // box host).
            let has_block = kids.iter().any(|&c| {
                matches!(
                    tree.boxes[c as usize].outside,
                    DisplayOutside::Block | DisplayOutside::ListItem
                )
            });
            if has_block {
                let new_kids = wrap_inline_runs(tree, i, &kids);
                tree.boxes[i as usize].children = new_kids;
            }
        }
        i += 1;
    }
}

fn wrap_inline_runs(tree: &mut BoxTree, parent: BoxId, kids: &[BoxId]) -> Vec<BoxId> {
    let mut out = Vec::with_capacity(kids.len());
    let mut current_run: Vec<BoxId> = Vec::new();
    let flush = |tree: &mut BoxTree, parent: BoxId, run: &mut Vec<BoxId>, out: &mut Vec<BoxId>| {
        if !run.is_empty() {
            // Whitespace-only text at the top/bottom of a wrapped run
            // would normally collapse — defer to LAYOUT-3 (inline
            // formatter) which already does this work properly.
            let anon_id = tree.boxes.len() as BoxId;
            tree.boxes.push(BoxNode {
                element: None,
                kind: BoxKind::AnonymousBlock,
                outside: DisplayOutside::Block,
                inside: DisplayInside::Flow,
                children: std::mem::take(run),
                parent: Some(parent),
            });
            // Re-parent the moved children.
            let moved = tree.boxes[anon_id as usize].children.clone();
            for c in moved {
                tree.boxes[c as usize].parent = Some(anon_id);
            }
            out.push(anon_id);
        }
    };
    for &k in kids {
        let kind = tree.boxes[k as usize].outside;
        match kind {
            DisplayOutside::Inline => current_run.push(k),
            _ => {
                flush(tree, parent, &mut current_run, &mut out);
                out.push(k);
            },
        }
    }
    flush(tree, parent, &mut current_run, &mut out);
    out
}

// ─────────────────────────────────────────────────────────────────────
// Tests
// ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;
    use crate::html_css::css::parse_stylesheet;
    use crate::html_css::html::parse_document;

    fn build(html: &str, css: &'static str) -> BoxTree {
        let dom = parse_document(html);
        let ss = parse_stylesheet(css).unwrap();
        // The cascade machinery wants a 'static lifetime through the
        // Stylesheet — leak both for test simplicity.
        let ss: &'static _ = Box::leak(Box::new(ss));
        // Convert dom outputs through the cascade — we need the
        // stylesheet to outlive the function. Use a static-lifetime
        // workaround by parsing into a leaked string.
        let _ = ss;
        let ss = Box::leak(Box::new(parse_stylesheet(css).unwrap()));
        // Drop dom owned and rebuild to make lifetimes work for the
        // test — caller owns nothing after this returns.
        let dom: &'static _ = Box::leak(Box::new(parse_document(html)));
        build_box_tree(dom, ss).unwrap()
    }

    fn count_kind(tree: &BoxTree, pred: impl Fn(&BoxNode) -> bool) -> usize {
        tree.iter_ids()
            .into_iter()
            .filter(|&id| pred(tree.get(id)))
            .count()
    }

    #[test]
    fn empty_html_produces_just_root() {
        let tree = build("", "");
        assert_eq!(tree.len(), 1);
    }

    #[test]
    fn single_paragraph_produces_one_element_box() {
        let tree = build("<p>hi</p>", "");
        // Root + p + text
        assert_eq!(tree.len(), 3);
        let element_boxes = count_kind(&tree, |b| matches!(b.kind, BoxKind::Element));
        assert_eq!(element_boxes, 1);
        let text_boxes = count_kind(&tree, |b| matches!(b.kind, BoxKind::Text(_)));
        assert_eq!(text_boxes, 1);
    }

    #[test]
    fn display_none_skips_subtree() {
        let tree = build("<p>visible</p><p class=hide>x</p>", ".hide { display: none; }");
        // Only the visible p plus its text plus the root.
        let element_boxes = count_kind(&tree, |b| matches!(b.kind, BoxKind::Element));
        assert_eq!(element_boxes, 1);
    }

    #[test]
    fn display_contents_unwraps() {
        let tree = build("<div><span>x</span></div>", "div { display: contents; }");
        // div produces no box; span sits directly under root.
        let element_boxes = count_kind(&tree, |b| matches!(b.kind, BoxKind::Element));
        assert_eq!(element_boxes, 1); // only the span
    }

    #[test]
    fn block_outside_for_default_div() {
        let tree = build("<div>x</div>", "");
        let div_box = tree
            .iter_ids()
            .into_iter()
            .find(|&id| matches!(tree.get(id).kind, BoxKind::Element))
            .unwrap();
        assert_eq!(tree.get(div_box).outside, DisplayOutside::Block);
        assert_eq!(tree.get(div_box).inside, DisplayInside::Flow);
    }

    #[test]
    fn flex_inside_for_display_flex() {
        let tree = build("<div>x</div>", "div { display: flex; }");
        let div_box = tree
            .iter_ids()
            .into_iter()
            .find(|&id| matches!(tree.get(id).kind, BoxKind::Element))
            .unwrap();
        assert_eq!(tree.get(div_box).outside, DisplayOutside::Block);
        assert_eq!(tree.get(div_box).inside, DisplayInside::Flex);
    }

    #[test]
    fn inline_outside_for_display_inline() {
        let tree = build("<div><a>x</a></div>", "a { display: inline; }");
        // <a> ends up wrapped in an anonymous block under <div> if div
        // had block children mixed in; here it's the only child so no
        // wrap needed.
        let a_box = tree.iter_ids().into_iter().find(|&id| {
            matches!(tree.get(id).kind, BoxKind::Element)
                && tree.get(id).outside == DisplayOutside::Inline
        });
        assert!(a_box.is_some());
    }

    #[test]
    fn anonymous_block_wraps_inline_run_amid_blocks() {
        // <div> mixing inline text with a block <p>:
        //   "before"      → inline
        //   <p>middle</p> → block
        //   "after"       → inline
        // Expected: [anon-block(text="before"), <p>, anon-block(text="after")]
        // — three children of <div>, two of which are anonymous.
        let tree = build("<div>before<p>middle</p>after</div>", "");
        let div_box = tree.iter_ids().into_iter().find(|&id| {
            matches!(tree.get(id).kind, BoxKind::Element)
                && tree.get(id).element
                    == Some(
                        tree.iter_ids()
                            .into_iter()
                            .find(|&id2| matches!(tree.get(id2).kind, BoxKind::Element))
                            .unwrap_or(0),
                    )
        });
        // Just count anonymous blocks somewhere in the tree.
        let anon = count_kind(&tree, |b| matches!(b.kind, BoxKind::AnonymousBlock));
        // Root (1) + 2 wrappers around the text runs.
        assert_eq!(anon, 3);
        let _ = div_box;
    }

    #[test]
    fn no_anonymous_wrap_when_all_inline() {
        // <p> with only inline children → no wrap (the block already
        // hosts an inline formatting context directly).
        let tree = build("<p>just <em>inline</em> text</p>", "");
        let anon = count_kind(&tree, |b| matches!(b.kind, BoxKind::AnonymousBlock));
        // Only the synthetic root.
        assert_eq!(anon, 1);
    }

    #[test]
    fn list_item_keeps_outside_class() {
        let tree = build("<li>x</li>", "li { display: list-item; }");
        let li = tree
            .iter_ids()
            .into_iter()
            .find(|&id| matches!(tree.get(id).kind, BoxKind::Element))
            .unwrap();
        assert_eq!(tree.get(li).outside, DisplayOutside::ListItem);
    }

    #[test]
    fn document_order_preserved() {
        let tree = build("<p>1</p><p>2</p><p>3</p>", "");
        let ps: Vec<&BoxNode> = tree
            .iter_ids()
            .into_iter()
            .map(|id| tree.get(id))
            .filter(|b| matches!(b.kind, BoxKind::Element))
            .collect();
        assert_eq!(ps.len(), 3);
        // Their text children must be "1", "2", "3" in order.
        let texts: Vec<&str> = tree
            .iter_ids()
            .into_iter()
            .filter_map(|id| match &tree.get(id).kind {
                BoxKind::Text(s) => Some(s.as_str()),
                _ => None,
            })
            .collect();
        assert_eq!(texts, vec!["1", "2", "3"]);
    }
}