fleuron/style/

element.rs

//! The content tree as something selectors can match against.
//!
//! `selectors` walks a DOM through parent and sibling links the
//! content tree does not have, so compilation flattens the tree once
//! into an arena that does. Element names are the markdown vocabulary
//! spelled the way an author writes them in CSS: `book`, `section`,
//! `h1`…`h6`, `p`, `blockquote`, `pre`, `hr`, `img`, `ul`, `ol`,
//! `li`, `table`, `thead`, `tbody`, `tr`, `th`, `td`, `em`, `strong`,
//! `code`, `a`.
//!
//! A code block is a `pre` element. It holds text rather than
//! inlines, so there is no `code` element inside it; `code` is an
//! inline code span.
//!
//! An element carries the classes and the id the content tree gave
//! it alongside the name.
//!
//! A table's header rows sit in a `thead` and its body rows in a
//! `tbody`, as HTML puts them, so a row counts among the rows of its
//! own group. The two groups are elements with no content node behind
//! them: they pass on what they inherit, and nothing else of theirs
//! reaches layout.
//!
//! An item of a tight list holds its text directly, as HTML writes
//! `<li>text</li>`. The paragraph that text is in has no element of
//! its own: its inlines are children of the `li`, and it takes the
//! style of an anonymous box inside it. So `li > p` reaches only the
//! paragraphs of a loose list.
//!
//! Text runs are not elements, the same as in CSS: they have no style
//! of their own and never count towards `:first-child`.

use std::borrow::Borrow;
use std::fmt;

use cssparser::{ToCss, serialize_identifier};
use precomputed_hash::PrecomputedHash;
use selectors::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
use selectors::bloom::{BLOOM_HASH_MASK, BloomFilter};
use selectors::matching::{ElementSelectorFlags, MatchingContext};
use selectors::parser::{NonTSPseudoClass, PseudoElement as PseudoElementTrait, SelectorImpl};
use selectors::{Element, OpaqueElement};

use crate::content::{Alignment, Attributes, Block, Book, Inline, ListItem, NodeId, Row};

/// An interned CSS identifier: element name, class, id, namespace.
///
/// One type serves every slot `SelectorImpl` asks for; the novel
/// subset has no namespaces and no attribute selectors, so the
/// distinctions the trait draws between them do not pay for separate
/// types.
#[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
pub struct Atom(pub String);

impl From<&str> for Atom {
    fn from(value: &str) -> Self {
        Atom(value.to_string())
    }
}

impl From<String> for Atom {
    fn from(value: String) -> Self {
        Atom(value)
    }
}

impl Borrow<str> for Atom {
    fn borrow(&self) -> &str {
        &self.0
    }
}

impl ToCss for Atom {
    fn to_css<W: fmt::Write>(&self, dest: &mut W) -> fmt::Result {
        serialize_identifier(&self.0, dest)
    }
}

impl PrecomputedHash for Atom {
    fn precomputed_hash(&self) -> u32 {
        fnv(&self.0)
    }
}

/// FNV-1a: the bloom filter needs a hash of the name itself, not of
/// where the string is stored.
fn fnv(name: &str) -> u32 {
    let mut hash = 0x811c_9dc5u32;
    for byte in name.as_bytes() {
        hash ^= *byte as u32;
        hash = hash.wrapping_mul(0x0100_0193);
    }
    hash
}

/// The novel subset has no non-tree-structural pseudo-classes:
/// `:hover` and its relatives describe a document being interacted
/// with, and a book is not one.
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum PseudoClass {}

impl ToCss for PseudoClass {
    fn to_css<W: fmt::Write>(&self, _dest: &mut W) -> fmt::Result {
        match *self {}
    }
}

impl NonTSPseudoClass for PseudoClass {
    type Impl = Fleuron;

    fn is_active_or_hover(&self) -> bool {
        match *self {}
    }

    fn is_user_action_state(&self) -> bool {
        match *self {}
    }
}

pub use crate::content::PseudoElement;

impl ToCss for PseudoElement {
    fn to_css<W: fmt::Write>(&self, dest: &mut W) -> fmt::Result {
        match self {
            PseudoElement::FirstLetter => dest.write_str("::first-letter"),
            PseudoElement::FirstLine => dest.write_str("::first-line"),
            PseudoElement::Before => dest.write_str("::before"),
            PseudoElement::After => dest.write_str("::after"),
        }
    }
}

/// The elements that sit inside a line of text rather than making
/// one. `::before` and `::after` generate text inside the line on
/// these.
pub const INLINE_ELEMENTS: [&str; 6] = ["code", "em", "strong", "a", "s", "span"];

/// The blocks that `::before` and `::after` generate a box inside.
pub const BLOCK_ELEMENTS: [&str; 16] = [
    "section",
    "h1",
    "h2",
    "h3",
    "h4",
    "h5",
    "h6",
    "p",
    "blockquote",
    "pre",
    "hr",
    "img",
    "ul",
    "ol",
    "li",
    "table",
];

impl PseudoElementTrait for PseudoElement {
    type Impl = Fleuron;
}

/// The engine's selector flavour.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Fleuron;

impl SelectorImpl for Fleuron {
    type ExtraMatchingData<'a> = std::marker::PhantomData<&'a ()>;
    type AttrValue = Atom;
    type Identifier = Atom;
    type LocalName = Atom;
    type NamespaceUrl = Atom;
    type NamespacePrefix = Atom;
    type BorrowedLocalName = Atom;
    type BorrowedNamespaceUrl = Atom;
    type NonTSPseudoClass = PseudoClass;
    type PseudoElement = PseudoElement;
}

/// Every element name the tree can hold, in the order the content
/// tree introduces them. A selector names one of these or matches
/// nothing.
pub const ELEMENTS: [&str; 30] = [
    "book",
    "section",
    "notes",
    "note",
    "h1",
    "h2",
    "h3",
    "h4",
    "h5",
    "h6",
    "p",
    "blockquote",
    "pre",
    "hr",
    "img",
    "ul",
    "ol",
    "li",
    "table",
    "thead",
    "tbody",
    "tr",
    "th",
    "td",
    "code",
    "em",
    "strong",
    "a",
    "s",
    "span",
];

/// The id past the last one the book assigned. Text runs hold ids
/// and are no elements, so the elements alone do not say where the
/// book's ids end.
fn past_last_id(book: &Book) -> u32 {
    book.sections
        .last()
        .and_then(|section| book.subtree(section.id))
        .map(|held| held.end)
        .unwrap_or(1)
}

/// One element: a name, an identity in the content tree, and the
/// links a selector walks.
#[derive(Debug)]
pub struct ElementNode {
    /// The element name as CSS spells it.
    pub name: &'static str,
    /// The content node this element stands for.
    pub id: NodeId,
    /// The classes and id the sheet names it by.
    pub attributes: Attributes,
    pub parent: Option<usize>,
    pub previous: Option<usize>,
    pub next: Option<usize>,
    pub first_child: Option<usize>,
    /// True for elements with text of their own.
    pub has_text: bool,
    /// The alignment the source wrote on a table cell's column, which
    /// the cascade applies below every rule of the author's.
    pub align: Option<Alignment>,
}

/// The content tree flattened into an arena, in document order. Index
/// 0 is the book.
#[derive(Debug, Default)]
pub struct ElementTree {
    nodes: Vec<ElementNode>,
    /// The paragraphs that have no element of their own, each with the
    /// `li` whose anonymous box holds it.
    anonymous: Vec<(NodeId, usize)>,
    /// The footnote area, which stands for the foot of every page
    /// rather than for anything the manuscript wrote.
    notes: NodeId,
}

impl ElementTree {
    /// Flattens one book. Elements come out in document order, so
    /// index order is reading order.
    pub fn build(book: &Book) -> ElementTree {
        let mut tree = ElementTree::default();
        let root = tree.push(
            "book",
            NodeId::UNASSIGNED,
            &Attributes::default(),
            None,
            false,
        );
        let sections: Vec<usize> = book
            .sections
            .iter()
            .map(|section| {
                let index = tree.push(
                    "section",
                    section.id,
                    &section.attributes,
                    Some(root),
                    false,
                );
                let children = tree.blocks(&section.blocks, index);
                tree.link(index, &children);
                index
            })
            .collect();
        tree.link(root, &sections);
        tree.notes = tree.area(root, past_last_id(book));
        tree
    }

    /// The footnote area: the box the notes of a page are set in.
    ///
    /// No content node stands behind it, so it takes an id past the
    /// ones the book assigned. It is not among the children of the
    /// book, because the sections are the children a sheet counts,
    /// and it is the book that it inherits from.
    fn area(&mut self, root: usize, past: u32) -> NodeId {
        let id = NodeId::new(past);
        self.push("notes", id, &Attributes::default(), Some(root), false);
        id
    }

    /// The id of the footnote area.
    pub fn notes(&self) -> NodeId {
        self.notes
    }

    /// Every element, in document order.
    pub fn nodes(&self) -> &[ElementNode] {
        &self.nodes
    }

    /// The paragraphs of tight list items, each with the index of the
    /// item that holds it.
    pub fn anonymous(&self) -> &[(NodeId, usize)] {
        &self.anonymous
    }

    /// A handle onto one element, for matching.
    pub fn at(&self, index: usize) -> ElementRef<'_> {
        ElementRef { tree: self, index }
    }

    fn blocks(&mut self, blocks: &[Block], parent: usize) -> Vec<usize> {
        blocks
            .iter()
            .map(|block| match block {
                Block::Heading {
                    id,
                    level,
                    inlines,
                    attributes,
                    ..
                } => {
                    let name = match u8::from(*level) {
                        1 => "h1",
                        2 => "h2",
                        3 => "h3",
                        4 => "h4",
                        5 => "h5",
                        _ => "h6",
                    };
                    let index = self.push(name, *id, attributes, Some(parent), false);
                    let (children, has_text) = self.inlines(inlines, index);
                    self.link(index, &children);
                    self.nodes[index].has_text = has_text;
                    index
                }
                Block::Paragraph {
                    id,
                    inlines,
                    attributes,
                    ..
                } => {
                    let index = self.push("p", *id, attributes, Some(parent), false);
                    let (children, has_text) = self.inlines(inlines, index);
                    self.link(index, &children);
                    self.nodes[index].has_text = has_text;
                    index
                }
                Block::Blockquote {
                    id,
                    blocks,
                    attributes,
                    ..
                } => {
                    let index = self.push("blockquote", *id, attributes, Some(parent), false);
                    let children = self.blocks(blocks, index);
                    self.link(index, &children);
                    index
                }
                Block::CodeBlock {
                    id,
                    text,
                    attributes,
                    ..
                } => self.push("pre", *id, attributes, Some(parent), !text.is_empty()),
                Block::ThematicBreak { id, attributes, .. } => {
                    self.push("hr", *id, attributes, Some(parent), false)
                }
                Block::PageBreak { id, attributes, .. } => {
                    self.push("pagebreak", *id, attributes, Some(parent), false)
                }
                Block::ColumnBreak { id, attributes, .. } => {
                    self.push("columnbreak", *id, attributes, Some(parent), false)
                }
                Block::Image { id, attributes, .. } => {
                    self.push("img", *id, attributes, Some(parent), false)
                }
                Block::List {
                    id,
                    ordered,
                    tight,
                    items,
                    attributes,
                    ..
                } => {
                    let name = if *ordered { "ol" } else { "ul" };
                    let index = self.push(name, *id, attributes, Some(parent), false);
                    let children = self.items(items, *tight, index);
                    self.link(index, &children);
                    index
                }
                Block::Table {
                    id,
                    head,
                    body,
                    attributes,
                    ..
                } => {
                    let index = self.push("table", *id, attributes, Some(parent), false);
                    let mut groups = Vec::new();
                    for (group, rows, cell) in [("thead", head, "th"), ("tbody", body, "td")] {
                        if rows.is_empty() {
                            continue;
                        }
                        let at = self.push(
                            group,
                            NodeId::UNASSIGNED,
                            &Attributes::default(),
                            Some(index),
                            false,
                        );
                        let children = self.rows(rows, cell, at);
                        self.link(at, &children);
                        groups.push(at);
                    }
                    self.link(index, &groups);
                    index
                }
            })
            .collect()
    }

    /// The `li` elements of one list. In a tight list, a paragraph an
    /// item holds with no names of its own is not an element.
    fn items(&mut self, items: &[ListItem], tight: bool, parent: usize) -> Vec<usize> {
        let mut indices = Vec::with_capacity(items.len());
        for item in items {
            let index = self.push("li", item.id, &item.attributes, Some(parent), false);
            let mut children = Vec::new();
            for block in &item.blocks {
                match block {
                    Block::Paragraph {
                        id,
                        inlines,
                        attributes,
                        ..
                    } if tight && attributes.is_empty() => {
                        let (inline, has_text) = self.inlines(inlines, index);
                        children.extend(inline);
                        self.nodes[index].has_text |= has_text;
                        self.anonymous.push((*id, index));
                    }
                    _ => children.extend(self.blocks(std::slice::from_ref(block), index)),
                }
            }
            self.link(index, &children);
            indices.push(index);
        }
        indices
    }

    /// The rows of one group of a table, each with its cells, which
    /// are `cell` elements.
    fn rows(&mut self, rows: &[Row], cell: &'static str, parent: usize) -> Vec<usize> {
        let mut indices = Vec::with_capacity(rows.len());
        for row in rows {
            let index = self.push("tr", row.id, &row.attributes, Some(parent), false);
            let mut cells = Vec::with_capacity(row.cells.len());
            for content in &row.cells {
                let at = self.push(cell, content.id, &content.attributes, Some(index), false);
                self.nodes[at].align = content.align;
                let children = self.blocks(&content.blocks, at);
                self.link(at, &children);
                cells.push(at);
            }
            self.link(index, &cells);
            indices.push(index);
        }
        indices
    }

    /// The element children of an inline sequence, plus whether any
    /// text run sits directly inside it — which is what `:empty` asks.
    fn inlines(&mut self, inlines: &[Inline], parent: usize) -> (Vec<usize>, bool) {
        let mut children = Vec::new();
        let mut text = false;
        for inline in inlines {
            let (name, id, attributes, nested): (_, _, _, Option<&[Inline]>) = match inline {
                Inline::Text { value, .. } => {
                    text |= !value.is_empty();
                    continue;
                }
                Inline::Break { .. } => continue,
                Inline::Code {
                    id,
                    value,
                    attributes,
                    ..
                } => {
                    let index = self.push("code", *id, attributes, Some(parent), !value.is_empty());
                    children.push(index);
                    continue;
                }
                Inline::Emphasis {
                    id,
                    children,
                    attributes,
                    ..
                } => ("em", *id, attributes, Some(children)),
                Inline::Strong {
                    id,
                    children,
                    attributes,
                    ..
                } => ("strong", *id, attributes, Some(children)),
                Inline::Link {
                    id,
                    children,
                    attributes,
                    ..
                } => ("a", *id, attributes, Some(children)),
                Inline::Strikethrough {
                    id,
                    children,
                    attributes,
                    ..
                } => ("s", *id, attributes, Some(children)),
                Inline::Span {
                    id,
                    children,
                    attributes,
                    ..
                } => ("span", *id, attributes, Some(children)),
                // A note holds blocks, so its children are blocks of
                // its own rather than the inlines around it.
                Inline::Note {
                    id,
                    blocks,
                    attributes,
                    ..
                } => {
                    let index = self.push("note", *id, attributes, Some(parent), false);
                    let kids = self.blocks(blocks, index);
                    self.link(index, &kids);
                    children.push(index);
                    continue;
                }
            };
            let index = self.push(name, id, attributes, Some(parent), false);
            if let Some(nested) = nested {
                let (kids, has_text) = self.inlines(nested, index);
                self.link(index, &kids);
                self.nodes[index].has_text = has_text;
            }
            children.push(index);
        }
        (children, text)
    }

    fn push(
        &mut self,
        name: &'static str,
        id: NodeId,
        attributes: &Attributes,
        parent: Option<usize>,
        has_text: bool,
    ) -> usize {
        self.nodes.push(ElementNode {
            name,
            id,
            attributes: attributes.clone(),
            parent,
            previous: None,
            next: None,
            first_child: None,
            has_text,
            align: None,
        });
        self.nodes.len() - 1
    }

    /// Chains a parent's children: first child, and each one's
    /// siblings.
    fn link(&mut self, parent: usize, children: &[usize]) {
        self.nodes[parent].first_child = children.first().copied();
        for (position, index) in children.iter().enumerate() {
            self.nodes[*index].previous = position.checked_sub(1).map(|p| children[p]);
            self.nodes[*index].next = children.get(position + 1).copied();
        }
    }
}

/// One element of the arena, as `selectors` sees it.
#[derive(Clone, Copy)]
pub struct ElementRef<'a> {
    tree: &'a ElementTree,
    /// Index into the arena, which is also document order.
    pub index: usize,
}

impl ElementRef<'_> {
    fn node(&self) -> &ElementNode {
        &self.tree.nodes[self.index]
    }

    fn sibling(&self, which: fn(&ElementNode) -> Option<usize>) -> Option<Self> {
        which(self.node()).map(|index| ElementRef {
            tree: self.tree,
            index,
        })
    }
}

impl fmt::Debug for ElementRef<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<{}>", self.node().name)
    }
}

impl Element for ElementRef<'_> {
    type Impl = Fleuron;

    fn opaque(&self) -> OpaqueElement {
        OpaqueElement::new(self.node())
    }

    fn parent_element(&self) -> Option<Self> {
        self.sibling(|node| node.parent)
    }

    fn parent_node_is_shadow_root(&self) -> bool {
        false
    }

    fn containing_shadow_host(&self) -> Option<Self> {
        None
    }

    fn is_pseudo_element(&self) -> bool {
        false
    }

    fn prev_sibling_element(&self) -> Option<Self> {
        self.sibling(|node| node.previous)
    }

    fn next_sibling_element(&self) -> Option<Self> {
        self.sibling(|node| node.next)
    }

    fn first_element_child(&self) -> Option<Self> {
        self.sibling(|node| node.first_child)
    }

    fn is_html_element_in_html_document(&self) -> bool {
        false
    }

    fn has_local_name(&self, name: &Atom) -> bool {
        self.node().name == name.0
    }

    fn has_namespace(&self, ns: &Atom) -> bool {
        ns.0.is_empty()
    }

    fn is_same_type(&self, other: &Self) -> bool {
        self.node().name == other.node().name
    }

    fn attr_matches(
        &self,
        _ns: &NamespaceConstraint<&Atom>,
        _local_name: &Atom,
        _operation: &AttrSelectorOperation<&Atom>,
    ) -> bool {
        false
    }

    fn match_non_ts_pseudo_class(
        &self,
        pc: &PseudoClass,
        _context: &mut MatchingContext<Fleuron>,
    ) -> bool {
        match *pc {}
    }

    /// Nothing in the content tree *is* a pseudo-element: a rule that
    /// names one is matched against its originating element instead,
    /// in `MatchingMode::ForStatelessPseudoElement`.
    fn match_pseudo_element(
        &self,
        _pe: &PseudoElement,
        _context: &mut MatchingContext<Fleuron>,
    ) -> bool {
        false
    }

    fn apply_selector_flags(&self, _flags: ElementSelectorFlags) {}

    fn is_link(&self) -> bool {
        self.node().name == "a"
    }

    fn is_html_slot_element(&self) -> bool {
        false
    }

    fn has_id(&self, id: &Atom, case_sensitivity: CaseSensitivity) -> bool {
        self.node()
            .attributes
            .id
            .as_ref()
            .is_some_and(|mine| case_sensitivity.eq(mine.as_bytes(), id.0.as_bytes()))
    }

    fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool {
        self.node()
            .attributes
            .classes
            .iter()
            .any(|mine| case_sensitivity.eq(mine.as_bytes(), name.0.as_bytes()))
    }

    fn has_custom_state(&self, _name: &Atom) -> bool {
        false
    }

    fn imported_part(&self, _name: &Atom) -> Option<Atom> {
        None
    }

    fn is_part(&self, _name: &Atom) -> bool {
        false
    }

    fn is_empty(&self) -> bool {
        self.node().first_child.is_none() && !self.node().has_text
    }

    fn is_root(&self) -> bool {
        self.node().parent.is_none()
    }

    /// The hashes a `:has()` filter tests an ancestor by: the name a
    /// selector reaches this element under, and the names a sheet
    /// gives it.
    fn add_element_unique_hashes(&self, filter: &mut BloomFilter) -> bool {
        let node = self.node();
        let mut insert = |name: &str| filter.insert_hash(fnv(name) & BLOOM_HASH_MASK);
        insert(node.name);
        if let Some(id) = &node.attributes.id {
            insert(id);
        }
        for class in &node.attributes.classes {
            insert(class);
        }
        true
    }
}