Skip to content

armgit / BUI

Public Imported from GitHub
0

Blender's GPU Accelerated UI, Decoupled from it's original codebase. Supports Rust, Python, JS, React, C & C++. Twice as good as GPUI

106 KB
Raw Blame
//! From an element tree to positioned boxes: cascade, box tree, taffy layout.
//!
//! * Block containers with inline content become wrapping flex lines of word
//!   boxes (so text, links and inline-blocks wrap like a browser's line
//!   boxes); inline elements own their words for painting and hit testing.
//! * Flex and grid containers get text runs as measured, wrapping leaves.
//! * Tables map onto flex rows and columns, lists paint their markers.
//!
//! Everything lives in flat arenas owned by the window and reused every
//! frame: boxes and element data in [`Frame`], computed styles in
//! [`StyleStore`] (shared between identical elements), the taffy tree, text
//! widths and images. Boxes refer to each other by index; nothing is
//! reference-counted.

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher};
use std::sync::Arc;

use taffy::prelude::*;
use taffy::style::Overflow;

use crate::css::{Decl, Prop, Rule, Stylesheet, Subject};
use crate::element::{AnyElement, Div, Listeners, PaintFn, ParentElement, SharedString};
use crate::geometry::{rect, Bounds, Units};
use crate::html::{tag_kind, ua_styled_stylesheet, ua_stylesheet, TagKind};
use crate::paint::{Image, ImageCache, ImageFile};
use crate::prof::{span, Phase};
use crate::style::ContentPart;
use crate::style::{apply, Computed, DisplayKind, Fnv, FnvMap, TextAlign, TextTransform, VAlign, WhiteSpace};
use crate::text::{self, TextCache};
use crate::widgets::WidgetSpec;

// ==========================================================================
// Keys

/// An element's identity across frames: a hash of its `.id()`, or of its
/// parent's key, tag and position.
pub(crate) type Key = u64;

fn fnv(parts: &[&[u8]]) -> u64 {
    let mut h = Fnv::default();
    for p in parts {
        h.write(p);
        h.write(&[0xff]);
    }
    h.finish()
}

/// The key of the element with `.id(id)`.
pub(crate) fn id_key(id: &str) -> Key {
    fnv(&[b"#", id.as_bytes()])
}

fn child_key(parent: Key, tag: &str, n: usize) -> Key {
    fnv(&[&parent.to_le_bytes(), tag.as_bytes(), &(n as u64).to_le_bytes()])
}

/// The key of the `<html>` element.
pub(crate) const ROOT_KEY: Key = 0x68746d6c; // "html"

/// Interaction state the cascade reads (`:hover`, `:active`, `:focus`, `details[open]`).
#[derive(Default)]
pub(crate) struct UiState {
    pub hovered: HashSet<Key>,
    pub active: HashSet<Key>,
    pub focused: Option<Key>,
    /// The focused element and its ancestors (`:focus-within`).
    pub focus_path: HashSet<Key>,
    /// The `.id()` of the focused element.
    pub focused_id: Option<String>,
    pub details_open: HashMap<Key, bool>,
    pub scroll: HashMap<Key, (f32, f32)>,
    pub checked: HashMap<Key, bool>,
}

// ==========================================================================
// Styles

/// A computed style in a [`StyleStore`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(crate) struct StyleId(u32);

/// The style everything inherits from at the root.
pub(crate) const ROOT_STYLE: StyleId = StyleId(0);

/// What a computed style depends on (style sharing).
struct StyleKey {
    parent: StyleId,
    viewport: (u32, u32),
    author: u64,
    rules: Vec<usize>,
    decls: Vec<Decl>,
    fixup: u8,
}

/// Computed styles, shared by every element with the same inputs and kept
/// across frames (browsers call this style sharing). Elements refer to them
/// by [`StyleId`].
pub(crate) struct StyleStore {
    styles: Vec<Computed>,
    cache: FnvMap<u64, Vec<(StyleKey, StyleId)>>,
    /// Custom property maps the styles point into (`Computed::vars`).
    vars: crate::vars::Vars,
    /// The author sheet whose `@property` initial values seed the root
    /// style's variables.
    seeded: u64,
}

impl Default for StyleStore {
    fn default() -> Self {
        StyleStore { styles: vec![Computed::default()], cache: Default::default(), vars: Default::default(), seeded: 0 }
    }
}

impl std::ops::Index<StyleId> for StyleStore {
    type Output = Computed;
    fn index(&self, id: StyleId) -> &Computed {
        &self.styles[id.0 as usize]
    }
}

impl StyleStore {
    /// Before building a frame: drop everything when the store has grown
    /// large (ids from the previous frame are not used after this).
    fn begin_frame(&mut self) {
        if self.styles.len() > 20_000 {
            self.styles.truncate(1);
            self.cache.clear();
            self.vars.clear();
            self.seeded = 0;
        }
    }

    /// `@property --x { initial-value: .. }`: registered properties hold
    /// their initial value until something sets them (`var(--x)` finds it
    /// without a fallback). Seeded into the root style once per sheet.
    fn seed_properties(&mut self, sheet: &Stylesheet, hash: u64) {
        if self.seeded == hash {
            return;
        }
        self.seeded = hash;
        let mut map: Vec<(Prop, Box<[crate::css::Tok]>)> = sheet.properties.iter()
            .filter(|p| p.name.starts_with("--"))
            .filter_map(|p| Some((Prop::custom(&p.name), crate::css::tokenize(p.initial.as_deref()?).into_boxed_slice())))
            .collect();
        map.sort_by_key(|e| e.0);
        map.dedup_by_key(|e| e.0);
        // styles computed against the old root variables are stale
        self.styles.truncate(1);
        self.cache.clear();
        self.vars.clear();
        self.styles[0].vars = if map.is_empty() { 0 } else { self.vars.add(map.into_boxed_slice()) };
    }

    fn add(&mut self, c: Computed) -> StyleId {
        self.styles.push(c);
        StyleId((self.styles.len() - 1) as u32)
    }
}

/// The author stylesheet (all `<style>` elements), reparsed only when its text changes.
/// Tailwind classes seen so far, compiled to CSS (like Tailwind's JIT):
/// each distinct `class` attribute is scanned once.
#[derive(Default)]
pub(crate) struct TwJit {
    on: bool,
    seen: FnvMap<u64, ()>,
    known: FnvMap<String, ()>,
    rules: Vec<((u32, u32), usize, String)>,
    css: String,
    dirty: bool,
}

/// Whether class names compile as Tailwind utilities (on by default).
pub(crate) static TAILWIND: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(true);

impl TwJit {
    fn scan(&mut self, classes: &str) {
        let h = fnv(&[classes.as_bytes()]);
        if self.seen.insert(h, ()).is_some() {
            return;
        }
        for c in classes.split_whitespace() {
            if self.known.contains_key(c) {
                continue;
            }
            self.known.insert(c.to_string(), ());
            if let Some(r) = crate::tailwind::compile(c) {
                let n = self.rules.len();
                self.rules.push((r.sort, n, r.css));
                self.dirty = true;
            }
        }
    }

    /// The utilities, in Tailwind's order.
    fn css(&mut self) -> &str {
        if self.dirty {
            self.rules.sort_by_key(|r| (r.0, r.1));
            self.css.clear();
            for r in &self.rules {
                self.css.push_str(&r.2);
                self.css.push('\n');
            }
            self.dirty = false;
        }
        &self.css
    }
}

#[derive(Default)]
pub(crate) struct AuthorSheet {
    hash: u64,
    sheet: Stylesheet,
}

// ==========================================================================
// Boxes

/// What a box holds.
pub(crate) enum Content {
    Element,
    /// A word (or pre-formatted line) inside a line container: bytes
    /// `start..end` of the text of box `src`.
    Word { src: u32, start: u32, end: u32 },
    /// A whole text run in a flex/grid container (wraps when measured).
    Text(String),
    LineBreak,
    Widget(WidgetSpec),
    Replaced(Replaced),
    /// An anonymous line container (inline content between blocks).
    Anon,
}

pub(crate) enum Replaced {
    Image(Arc<Image>),
    /// `<img src>`: decoded on the kit's workers when shown; animations
    /// play, or hold the frame of the `frame` attribute.
    File(ImageFile, Option<u32>),
    /// `<video>`: its player (yours, or the window's for `src`).
    Video(std::rc::Rc<crate::video::Video>),
    Painted(PaintFn),
    Placeholder(&'static str),
}

/// The element-level data kept from a `Div` after building (moved, not copied).
pub(crate) struct ElData {
    pub tag: &'static str,
    pub id: Option<SharedString>,
    pub attrs: Vec<(SharedString, SharedString)>,
    pub listeners: Option<Box<Listeners>>,
    /// Which of the author sheet's `:has()` hold here (bit = index).
    pub has: u64,
}

const NONE: u32 = u32::MAX;

pub(crate) struct BoxNode {
    pub parent: Option<usize>,
    /// Element and text children, linked (words / breaks / line boxes point
    /// at their parent but aren't linked into its list).
    first: u32,
    last: u32,
    next: u32,
    prev: u32,
    pub content: Content,
    /// Index into [`Frame::els`].
    el: u32,
    /// The element this box belongs to (itself, or the inline element of a word).
    pub owner: usize,
    pub style: StyleId,
    pub key: Key,
    /// What selectors can see of this element (its tag, id, attributes,
    /// position and state, chained through its parent and previous sibling):
    /// equal fingerprints match the same rules.
    fp: u64,
    pub taffy: Option<NodeId>,
    pub pos: (usize, usize),
    /// Position among siblings of the same tag, and their count.
    pub tpos: (u32, u32),
    pub marker: Option<String>,
    /// Inside a `styled` subtree: matched against the Blender UA sheet.
    pub styled: bool,
    // filled after layout
    pub bounds: Bounds<f32>,
    pub clip: Option<Bounds<f32>>,
    pub opacity: f32,
    pub visible: bool,
    pub scroll_range: (f32, f32),
    pub scroll_pos: (f32, f32),
    /// This element is one layout leaf measuring its lone text child (that box).
    pub fold: Option<usize>,
    /// This text run is laid out by its parent (`fold`), not by its own node.
    pub folded: bool,
}

/// A laid-out frame. The arenas are reused by the next frame.
#[derive(Default)]
pub(crate) struct Frame {
    pub nodes: Vec<BoxNode>,
    els: Vec<ElData>,
    pub title: Option<String>,
    by_key: std::cell::OnceCell<HashMap<Key, usize>>,
}

/// Measure contexts of taffy leaves. Compared across frames: an unchanged
/// context keeps the leaf's cached layout.
#[derive(PartialEq)]
pub(crate) enum Measure {
    /// Text of the box registered under `key` this frame (already
    /// whitespace-processed and transformed); `hash` identifies the text.
    Text { key: Key, hash: u64, size: f32, flags: i32, line: f32, nowrap: bool, brk: u8 },
}

/// The persistent taffy tree's nodes by box key (with the frame they were
/// last used in). Reconciling instead of rebuilding lets taffy's cache skip
/// every subtree whose style, content and children didn't change.
#[derive(Default)]
struct Recon {
    map: FnvMap<Key, (NodeId, u32)>,
    stamp: u32,
    /// Nodes for duplicate keys this frame: removed next frame.
    extra: Vec<NodeId>,
}

/// Everything layout keeps across frames, owned by the window.
pub(crate) struct LayoutCaches {
    pub styles: StyleStore,
    pub text: TextCache,
    pub images: ImageCache,
    pub author: AuthorSheet,
    pub(crate) taffy: crate::tree::LayoutTree<Measure>,
    /// Box index of each taffy node (by slot), rebuilt in place each frame.
    box_of: Vec<u32>,
    /// Scratch for `finish`.
    acc: Vec<Option<Bounds<f32>>>,
    /// Matched rules by element fingerprint (+ viewport): selector matching
    /// runs once per distinct element, not every frame.
    matched: MatchCache,
    recon: Recon,
    /// Measured text leaves: key -> box index, this frame.
    text_box: FnvMap<Key, usize>,
    /// Content widths of blocks with `overflow-wrap: anywhere` from the last
    /// layout: their long words are split to fit before layout.
    wrap_widths: FnvMap<Key, f32>,
    tw: TwJit,
    /// `@container`: query containers' content sizes from the last layout.
    containers: Containers,
    /// CSS animations and transitions by element key.
    pub(crate) anim: crate::anim::Animations,
}

impl LayoutCaches {
    /// After a layout: record query containers' sizes. True when the
    /// window must render again (an `@container` query may match differently).
    pub(crate) fn after_layout(&mut self, frame: &Frame) -> bool {
        let queried = self.author.sheet.has_container_queries();
        let mut again = self.containers.update(frame, &self.styles, queried);
        // overflow-wrap: blocks whose width changed lay out their words again
        for n in &frame.nodes {
            let c = &self.styles[n.style];
            if c.wrap_anywhere && n.taffy.is_some() && !c.display.is_inline_level()
                && matches!(n.content, Content::Element) {
                let w = crate::paint::content_box(c, n.bounds).size.width;
                if self.wrap_widths.get(&n.key).is_none_or(|old| (old - w).abs() > 0.5) {
                    self.wrap_widths.insert(n.key, w);
                    again = true;
                }
            }
        }
        if self.wrap_widths.len() > 4096 {
            self.wrap_widths.clear();
        }
        again
    }
}

/// Query containers by element key: content-box size, `container-type`
/// and names, from the previous layout (queries see last frame's sizes;
/// a change re-renders once more).
#[derive(Default)]
pub(crate) struct Containers {
    map: FnvMap<Key, (f32, f32, u8, Option<Box<str>>)>,
    /// Hash of `map`, part of the selector-match memo.
    generation: u64,
    /// Consecutive re-renders caused by container size changes.
    chain: u8,
}

impl Containers {
    /// After a layout: record the containers; true when a re-render is needed.
    fn update(&mut self, frame: &Frame, styles: &StyleStore, queried: bool) -> bool {
        let mut map: FnvMap<Key, (f32, f32, u8, Option<Box<str>>)> = FnvMap::default();
        for n in &frame.nodes {
            let c = &styles[n.style];
            if c.container_type != 0 && n.taffy.is_some() {
                let b = crate::paint::content_box(c, n.bounds);
                map.insert(n.key, (b.size.width, b.size.height, c.container_type, c.container_name.clone()));
            }
        }
        let mut h = Fnv::default();
        let mut keys: Vec<&Key> = map.keys().collect();
        keys.sort_unstable();
        for k in keys {
            let (w, hh, t, _) = &map[k];
            (k, w.to_bits(), hh.to_bits(), t).hash(&mut h);
        }
        let generation = h.finish();
        let changed = generation != self.generation;
        self.map = map;
        self.generation = generation;
        // a query may now match differently: render again (bounded, in case
        // the result feeds back into the container's own size)
        if changed && queried && self.chain < 3 {
            self.chain += 1;
            return true;
        }
        self.chain = 0;
        false
    }
}

/// Rule indices (`Rule::order`) in the UA and author sheets.
type RuleIds = smallvec::SmallVec<[u32; 8]>;

#[derive(Default)]
struct MatchCache {
    map: FnvMap<u64, (RuleIds, RuleIds)>,
    author: u64,
}

impl Default for LayoutCaches {
    fn default() -> Self {
        LayoutCaches {
            styles: StyleStore::default(),
            text: TextCache::default(),
            images: ImageCache::default(),
            author: AuthorSheet::default(),
            taffy: Default::default(),
            box_of: Vec::new(),
            acc: Vec::new(),
            matched: MatchCache::default(),
            recon: Recon::default(),
            text_box: FnvMap::default(),
            wrap_widths: FnvMap::default(),
            tw: TwJit::default(),
            containers: Containers::default(),
            anim: Default::default(),
        }
    }
}

struct Builder<'a> {
    nodes: Vec<BoxNode>,
    els: Vec<ElData>,
    taffy: &'a mut crate::tree::LayoutTree<Measure>,
    styles: &'a mut StyleStore,
    text: &'a mut TextCache,
    images: &'a mut ImageCache,
    matched: &'a mut MatchCache,
    recon: &'a mut Recon,
    text_box: &'a mut FnvMap<Key, usize>,
    /// Set when a node changed while building the current subtree.
    changed: bool,
    /// `tpos` for the element about to be built.
    next_tpos: (u32, u32),
    author: &'a Stylesheet,
    author_hash: u64,
    containers: &'a Containers,
    /// Media query results of the UA and author sheets this frame.
    ua_media: Vec<bool>,
    ua_styled_media: Vec<bool>,
    au_media: Vec<bool>,
    state: &'a UiState,
    viewport: (f32, f32),
    title: Option<String>,
    widgets: &'a mut dyn FnMut(Key, &WidgetSpec) -> (f32, f32),
    /// CSS counters in scope: name, value, and the box whose subtree the
    /// instance is scoped to (dropped when that box is finished).
    counters: Vec<(Box<str>, i32, usize)>,
    /// Column widths of each table (by box), computed before its cells.
    table_cols: FnvMap<usize, TableCols>,
    wrap_widths: &'a FnvMap<Key, f32>,
    anim: &'a mut crate::anim::Animations,
}

/// A table's columns: widths in px, and whether the table sizes to them.
struct TableCols {
    widths: Vec<f32>,
    /// the table's width is auto: it shrinks to its columns
    fit: bool,
    fixed: bool,
}

/// Child box indices / layout nodes being assembled: on the stack for the usual few.
type Kids = smallvec::SmallVec<[usize; 8]>;
type NodeList = smallvec::SmallVec<[NodeId; 8]>;

/// The slot index of a layout node (dense: the tree reuses freed slots).
fn slot(id: NodeId) -> usize {
    u64::from(id) as usize
}

/// Children of box `i` in the arena `nodes`.
fn kids(nodes: &[BoxNode], i: usize) -> impl Iterator<Item = usize> + '_ {
    let mut k = nodes[i].first;
    std::iter::from_fn(move || {
        (k != NONE).then(|| {
            let cur = k as usize;
            k = nodes[cur].next;
            cur
        })
    })
}

fn el_attr<'a>(nodes: &[BoxNode], els: &'a [ElData], i: usize, name: &str) -> Option<&'a str> {
    let e = nodes[i].el;
    if e == NONE {
        return None;
    }
    els[e as usize].attrs.iter().rev().find(|(n, _)| n == name).map(|(_, v)| v.as_ref())
}

// -- selector subject -------------------------------------------------------------------

#[derive(Clone)]
struct NodeRef<'b> {
    nodes: &'b [BoxNode],
    els: &'b [ElData],
    state: &'b UiState,
    containers: &'b Containers,
    i: usize,
}

impl NodeRef<'_> {
    fn el(&self) -> Option<&ElData> {
        let e = self.nodes[self.i].el;
        (e != NONE).then(|| &self.els[e as usize])
    }
    fn own_attr(&self, name: &str) -> Option<&str> {
        el_attr(self.nodes, self.els, self.i, name)
    }
    /// A `::before` / `::after` box (invisible to sibling selectors).
    fn is_generated(&self, k: usize) -> bool {
        let e = self.nodes[k].el;
        e != NONE && self.els[e as usize].tag.starts_with("::")
    }
}

impl Subject for NodeRef<'_> {
    fn container(&self, name: Option<&str>) -> Option<(f32, f32)> {
        let mut cur = self.nodes[self.i].parent;
        while let Some(p) = cur {
            if let Some((w, h, ty, names)) = self.containers.map.get(&self.nodes[p].key) {
                let named = name.is_none_or(|n| names.as_deref().is_some_and(|s| s.split(' ').any(|x| x == n)));
                if named {
                    // an inline-size container has no queryable height
                    return Some((*w, if *ty == 2 { *h } else { f32::NAN }));
                }
            }
            cur = self.nodes[p].parent;
        }
        None
    }
    fn tag(&self) -> &str {
        self.el().map(|e| e.tag).unwrap_or("")
    }
    fn id(&self) -> Option<&str> {
        self.el()?.id.as_deref()
    }
    fn has_class(&self, class: &str) -> bool {
        self.own_attr("class").is_some_and(|c| c.split_whitespace().any(|w| w == class))
    }
    fn attr(&self, name: &str) -> Option<&str> {
        let n = &self.nodes[self.i];
        if name == "open" && self.tag() == "details" {
            return self.state.details_open.get(&n.key).copied()
                .unwrap_or(self.own_attr("open").is_some()).then_some("");
        }
        self.own_attr(name)
    }
    fn state(&self, pseudo: &str) -> bool {
        let key = self.nodes[self.i].key;
        match pseudo {
            "hover" => self.state.hovered.contains(&key),
            "active" => self.state.active.contains(&key),
            "focus" | "focus-visible" => self.state.focused == Some(key),
            "focus-within" => self.state.focus_path.contains(&key),
            "checked" => self.state.checked.get(&key).copied().unwrap_or(self.own_attr("checked").is_some()),
            "disabled" => self.own_attr("disabled").is_some(),
            "enabled" => self.own_attr("disabled").is_none(),
            "link" | "any-link" => self.tag() == "a" && self.own_attr("href").is_some(),
            "required" => self.own_attr("required").is_some(),
            "optional" => self.own_attr("required").is_none(),
            "read-only" => self.own_attr("readonly").is_some(),
            "read-write" => self.own_attr("readonly").is_none(),
            "open" => self.attr("open").is_some(),
            "placeholder-shown" => {
                self.own_attr("placeholder").is_some() && self.own_attr("value").is_none_or(str::is_empty)
            }
            _ => false,
        }
    }
    fn parent(&self) -> Option<Self> {
        self.nodes[self.i].parent.map(|p| NodeRef { i: p, ..self.clone() })
    }
    fn prev_sibling(&self) -> Option<Self> {
        let mut k = self.nodes[self.i].prev;
        while k != NONE {
            if self.nodes[k as usize].el != NONE && !self.is_generated(k as usize) {
                return Some(NodeRef { i: k as usize, ..self.clone() });
            }
            k = self.nodes[k as usize].prev;
        }
        None
    }
    fn position(&self) -> (usize, usize) {
        self.nodes[self.i].pos
    }
    fn type_position(&self) -> (usize, usize) {
        let t = self.nodes[self.i].tpos;
        (t.0 as usize, t.1 as usize)
    }
    fn is_empty(&self) -> bool {
        self.nodes[self.i].first == NONE
    }
    fn has(&self, id: u16) -> bool {
        id < 64 && self.el().is_some_and(|e| e.has & (1 << id) != 0)
    }
    fn same(&self, o: &Self) -> bool {
        self.i == o.i
    }
    fn next_sibling(&self) -> Option<Self> {
        let mut k = self.nodes[self.i].next;
        while k != NONE {
            if self.nodes[k as usize].el != NONE && !self.is_generated(k as usize) {
                return Some(NodeRef { i: k as usize, ..self.clone() });
            }
            k = self.nodes[k as usize].next;
        }
        None
    }
    fn first_child(&self) -> Option<Self> {
        let k = self.nodes[self.i].first;
        if k == NONE {
            return None;
        }
        let c = NodeRef { i: k as usize, ..self.clone() };
        if self.nodes[k as usize].el != NONE && !self.is_generated(k as usize) { Some(c) } else { c.next_sibling() }
    }
}

/// An element of a not-yet-built subtree (for `:has()`): its tag, id,
/// attributes and tree links, flattened from the declarative children.
struct Flat<'d> {
    tag: &'static str,
    id: Option<&'d str>,
    attrs: &'d [(SharedString, SharedString)],
    parent: u32,
    first: u32,
    next: u32,
    prev: u32,
    pos: (usize, usize),
    tpos: (usize, usize),
    key: Key,
}

/// (same-tag siblings before `k`, same-tag siblings in all) for `:has()`
/// subtrees (small: linear scans are fine there).
fn type_counts(els: &[&Div], k: usize) -> (usize, usize) {
    let tag = els[k].tag;
    let before = els[..k].iter().filter(|e| e.tag == tag).count();
    (before, before + els[k..].iter().filter(|e| e.tag == tag).count())
}

/// Flatten `div`'s element subtree (index 0 = `div` itself, the anchor).
fn flatten<'d>(div: &'d Div, key: Key, out: &mut Vec<Flat<'d>>) {
    out.push(Flat { tag: div.tag, id: None, attrs: &[], parent: NONE, first: NONE, next: NONE, prev: NONE,
                    pos: (1, 1), tpos: (1, 1), key });
    fn kids<'d>(div: &'d Div, me: u32, key: Key, out: &mut Vec<Flat<'d>>) {
        let els: smallvec::SmallVec<[&'d Div; 16]> = div.children.iter().filter_map(|c| match c {
            AnyElement::Element(d) => Some(d),
            _ => None,
        }).collect();
        let mut prev = NONE;
        for (k, d) in els.iter().enumerate() {
            let ck = match &d.id {
                Some(id) => id_key(id),
                None => child_key(key, d.tag, k + 1),
            };
            let (before, total) = type_counts(&els, k);
            let idx = out.len() as u32;
            out.push(Flat { tag: d.tag, id: d.id.as_deref(), attrs: &d.attrs, parent: me, first: NONE, next: NONE,
                            prev, pos: (k + 1, els.len()), tpos: (before + 1, total), key: ck });
            if prev == NONE {
                out[me as usize].first = idx;
            } else {
                out[prev as usize].next = idx;
            }
            prev = idx;
            kids(d, idx, ck, out);
        }
    }
    kids(div, 0, key, out);
}

#[derive(Clone)]
struct DivSubject<'f, 'd> {
    flat: &'f [Flat<'d>],
    state: &'f UiState,
    i: usize,
}

impl DivSubject<'_, '_> {
    fn at(&self, k: u32) -> Option<Self> {
        (k != NONE).then(|| DivSubject { i: k as usize, ..self.clone() })
    }
}

impl Subject for DivSubject<'_, '_> {
    fn tag(&self) -> &str {
        self.flat[self.i].tag
    }
    fn id(&self) -> Option<&str> {
        self.flat[self.i].id
    }
    fn has_class(&self, class: &str) -> bool {
        self.attr("class").is_some_and(|c| c.split_whitespace().any(|w| w == class))
    }
    fn attr(&self, name: &str) -> Option<&str> {
        self.flat[self.i].attrs.iter().find(|(k, _)| k.as_ref() == name).map(|(_, v)| v.as_ref())
    }
    fn state(&self, pseudo: &str) -> bool {
        let key = self.flat[self.i].key;
        match pseudo {
            "hover" => self.state.hovered.contains(&key),
            "active" => self.state.active.contains(&key),
            "focus" | "focus-visible" => self.state.focused == Some(key),
            "focus-within" => self.state.focus_path.contains(&key),
            "checked" => self.state.checked.get(&key).copied().unwrap_or(self.attr("checked").is_some()),
            "disabled" => self.attr("disabled").is_some(),
            "enabled" => self.attr("disabled").is_none(),
            "required" => self.attr("required").is_some(),
            "link" | "any-link" => self.tag() == "a" && self.attr("href").is_some(),
            _ => false,
        }
    }
    fn parent(&self) -> Option<Self> {
        self.at(self.flat[self.i].parent)
    }
    fn prev_sibling(&self) -> Option<Self> {
        self.at(self.flat[self.i].prev)
    }
    fn next_sibling(&self) -> Option<Self> {
        self.at(self.flat[self.i].next)
    }
    fn first_child(&self) -> Option<Self> {
        self.at(self.flat[self.i].first)
    }
    fn position(&self) -> (usize, usize) {
        self.flat[self.i].pos
    }
    fn type_position(&self) -> (usize, usize) {
        self.flat[self.i].tpos
    }
    fn is_empty(&self) -> bool {
        self.flat[self.i].first == NONE
    }
    fn same(&self, o: &Self) -> bool {
        self.i == o.i
    }
}

// -- building -------------------------------------------------------------------------------

fn collect_styles(el: &AnyElement, css: &mut String, title: &mut Option<String>, jit: &mut TwJit) {
    if let AnyElement::Element(d) = el {
        if jit.on {
            if let Some((_, classes)) = d.attrs.iter().find(|(k, _)| k.as_ref() == "class") {
                jit.scan(classes);
            }
        }
        let text = || d.children.iter().filter_map(|c| match c {
            AnyElement::Text(t) => Some(t.as_ref()),
            _ => None,
        }).collect::<String>();
        match d.tag {
            "style" => css.push_str(&text()),
            "title" if title.is_none() => *title = Some(text()),
            _ => {}
        }
        for c in &d.children {
            collect_styles(c, css, title, jit);
        }
    }
}

impl<'a> Builder<'a> {
    fn subject(&self, i: usize) -> NodeRef<'_> {
        NodeRef { nodes: &self.nodes, els: &self.els, state: self.state, containers: self.containers, i }
    }

    fn st(&self, i: usize) -> &Computed {
        &self.styles[self.nodes[i].style]
    }

    /// `<video src>`'s player: muted autoplay unless `autoplay="false"` (React's
    /// `autoPlay={false}`);
    /// `loop`, `poster` (the HTML attributes).
    fn video_src(&mut self, i: usize) -> Option<std::rc::Rc<crate::video::Video>> {
        let attrs = crate::video::VideoAttrs {
            autoplay: self.attr(i, "autoplay").or_else(|| self.attr(i, "autoPlay")) != Some("false"), // React: autoPlay
            looped: self.attr(i, "loop").is_some_and(|v| v != "false"),
            poster: self.attr(i, "poster").map(str::to_owned),
        };
        let src = self.attr(i, "src")?.to_owned();
        self.images.videos.get(&src, attrs)
    }

    fn attr(&self, i: usize, name: &str) -> Option<&str> {
        el_attr(&self.nodes, &self.els, i, name)
    }

    /// The computed style of element `i`, shared with every element (this
    /// frame or earlier) that had the same parent style, matched rules and
    /// declarations. `fixup` adjusts `display` for widgets and flex/grid
    /// items before the result is shared.
    fn cascade(&mut self, i: usize, div: &Div, parent: StyleId, fixup: u8) -> StyleId {
        let _s = span(Phase::Cascade);
        let (ua, au) = self.matched_rules(i);
        let decls = self.declared(i, div, &ua, &au);
        let viewport = (self.viewport.0.to_bits(), self.viewport.1.to_bits());
        let rule_ids = || ua.iter().map(|r| *r as *const Rule as usize).chain(au.iter().map(|r| r.order));
        // probe without building a key: hash the inputs, compare in place
        let hash = {
            let mut h = Fnv::default();
            parent.hash(&mut h);
            viewport.hash(&mut h);
            self.author_hash.hash(&mut h);
            fixup.hash(&mut h);
            for r in rule_ids() {
                r.hash(&mut h);
            }
            for d in &decls {
                d.probe_hash(&mut h);
            }
            h.finish()
        };
        let same = |k: &StyleKey| {
            k.parent == parent
                && k.viewport == viewport
                && k.author == self.author_hash
                && k.fixup == fixup
                && k.rules.len() == ua.len() + au.len()
                && k.rules.iter().copied().eq(rule_ids())
                && k.decls.len() == decls.len()
                && k.decls.iter().zip(&decls).all(|(a, d)| a == *d)
        };
        if let Some(&(_, id)) = self.styles.cache.get(&hash).and_then(|b| b.iter().find(|(k, _)| same(k))) {
            return id;
        }
        let key = StyleKey {
            parent,
            viewport,
            author: self.author_hash,
            rules: rule_ids().collect(),
            decls: decls.iter().map(|d| (*d).clone()).collect(),
            fixup,
        };
        let mut c = self.compute(parent, &decls);
        match fixup {
            1 if c.display == DisplayKind::Inline => c.display = DisplayKind::InlineBlock,
            2 if c.display == DisplayKind::Inline => c.display = DisplayKind::Block,
            _ => {}
        }
        let id = self.styles.add(c);
        self.styles.cache.entry(hash).or_default().push((key, id));
        id
    }

    /// CSS animations and transitions of element `i` (`anim.rs`): a private
    /// copy of its shared style `style` with the animated values on top.
    /// Never cached, so the shared styles stay what the cascade made them.
    fn animate(&mut self, i: usize, div: &Div, parent: StyleId, style: StyleId) -> StyleId {
        let key = self.nodes[i].key;
        if !self.anim.wants(key, &self.styles[style]) {
            return style;
        }
        let important: smallvec::SmallVec<[Prop; 8]> = {
            let (ua, au) = self.matched_rules(i);
            self.declared(i, div, &ua, &au).iter().filter(|d| d.important).map(|d| d.prop).collect()
        };
        let base = &self.styles[style];
        let env = crate::anim::Env {
            parent: &self.styles[parent],
            viewport: self.viewport,
            vars: self.styles.vars.get(base.vars),
            sheet: self.author,
            media: &self.au_media,
            important: &important,
        };
        match self.anim.apply(key, base, &env) {
            Some(c) => self.styles.add(c),
            None => style,
        }
    }

    /// The UA and author rules matching element `i`: from the memo when an
    /// element with the same fingerprint was matched before.
    fn matched_rules(&mut self, i: usize) -> (crate::css::Matches<'static>, crate::css::Matches<'a>) {
        let (ua_sheet, ua_media) = self.ua_for(i);
        let author: &'a Stylesheet = self.author;
        let memo = {
            let mut h = Fnv::default();
            self.nodes[i].fp.hash(&mut h);
            self.nodes[i].styled.hash(&mut h);
            self.containers.generation.hash(&mut h);
            self.viewport.0.to_bits().hash(&mut h);
            self.viewport.1.to_bits().hash(&mut h);
            h.finish()
        };
        if let Some((u, a)) = self.matched.map.get(&memo) {
            return (u.iter().map(|&k| &ua_sheet.rules[k as usize]).collect(),
                    a.iter().map(|&k| &author.rules[k as usize]).collect());
        }
        let subj = self.subject(i);
        let ua = ua_sheet.matches(&subj, ua_media, None);
        let au = author.matches(&subj, &self.au_media, None);
        self.matched.map.insert(memo, (ua.iter().map(|r| r.order as u32).collect(),
                                       au.iter().map(|r| r.order as u32).collect()));
        (ua, au)
    }

    /// The UA sheet for box `i` (plain, or Blender's inside `styled`) and
    /// its media query results.
    fn ua_for(&self, i: usize) -> (&'static Stylesheet, &Vec<bool>) {
        if self.nodes[i].styled {
            (ua_styled_stylesheet(), &self.ua_styled_media)
        } else {
            (ua_stylesheet(), &self.ua_media)
        }
    }

    /// The fingerprint of element `i` (see [`BoxNode::fp`]).
    fn fingerprint(&self, i: usize) -> u64 {
        let n = &self.nodes[i];
        let mut h = Fnv::default();
        n.parent.map(|p| self.nodes[p].fp).unwrap_or(0).hash(&mut h);
        // the previous element sibling (text in between doesn't count)
        let mut k = n.prev;
        while k != NONE && self.nodes[k as usize].el == NONE {
            k = self.nodes[k as usize].prev;
        }
        (if k == NONE { 0 } else { self.nodes[k as usize].fp }).hash(&mut h);
        n.pos.hash(&mut h);
        n.tpos.hash(&mut h);
        if let Some(e) = (n.el != NONE).then(|| &self.els[n.el as usize]) {
            e.has.hash(&mut h);
            e.tag.hash(&mut h);
            e.id.as_deref().hash(&mut h);
            for (a, v) in &e.attrs {
                a.hash(&mut h);
                v.hash(&mut h);
            }
        }
        let st = self.state;
        let key = n.key;
        (st.hovered.contains(&key), st.active.contains(&key), st.focused == Some(key),
         st.focus_path.contains(&key), st.checked.get(&key).copied(), st.details_open.get(&key).copied())
            .hash(&mut h);
        h.finish()
    }

    /// Every declaration that applies to element `i`, in cascade order.
    fn declared<'d>(&self, i: usize, div: &'d Div, ua: &[&'d Rule], au: &[&'d Rule])
        -> smallvec::SmallVec<[&'d Decl; 24]> {
        let key = self.nodes[i].key;
        let mut decls = smallvec::SmallVec::new();
        decls.extend(ua.iter().flat_map(|r| r.decls.iter()));
        decls.extend(au.iter().flat_map(|r| r.decls.iter()));
        decls.extend(div.decls.iter());
        if let Some(st) = &div.states {
            if self.state.hovered.contains(&key) {
                decls.extend(st.hover.iter());
            }
            if self.state.active.contains(&key) {
                decls.extend(st.active.iter());
            }
            if self.state.focused == Some(key) {
                decls.extend(st.focus.iter());
            }
        }
        decls
    }

    fn compute(&mut self, parent: StyleId, decls: &[&Decl]) -> Computed {
        // custom properties first: other declarations may reference them
        let pvars = self.styles[parent].vars;
        let vars = if decls.iter().any(|d| d.prop.is_custom()) {
            let mut map: Vec<(Prop, Box<[crate::css::Tok]>)> = self.styles.vars.get(pvars).to_vec();
            for important in [false, true] {
                for d in decls.iter().filter(|d| d.important == important && d.prop.is_custom()) {
                    let v: Box<[crate::css::Tok]> = if crate::vars::uses_vars(&d.value) {
                        match crate::vars::substitute(&d.value, &map) {
                            Some(v) => v.into_boxed_slice(),
                            None => Box::new([]), // guaranteed-invalid: falls back
                        }
                    } else {
                        d.value.to_vec().into_boxed_slice()
                    };
                    match map.binary_search_by_key(&d.prop, |e| e.0) {
                        Ok(i) => map[i].1 = v,
                        Err(i) => map.insert(i, (d.prop, v)),
                    }
                }
            }
            self.styles.vars.add(map.into_boxed_slice())
        } else {
            pvars
        };
        let parent = &self.styles[parent];
        let mut c = Computed::inherit(parent);
        c.vars = vars;
        let map = self.styles.vars.get(vars);
        let subst = |d: &Decl| -> Option<Decl> {
            crate::vars::substitute(&d.value, map).map(|v| Decl {
                prop: d.prop,
                value: crate::css::Value::Owned(v.into_boxed_slice()),
                important: d.important,
            })
        };
        const FONT_SIZE: Prop = Prop::named("font-size");
        const FONT: Prop = Prop::named("font");
        let font_first = |d: &&Decl| d.prop == FONT_SIZE || d.prop == FONT;
        let units = |fs: f32| Units { font_size: fs, viewport: self.viewport };
        let run = |c: &mut Computed, u: Units, d: &Decl| {
            if crate::vars::uses_vars(&d.value) {
                if let Some(d) = subst(d) {
                    apply(c, parent, u, &d);
                }
            } else {
                apply(c, parent, u, d);
            }
        };
        for important in [false, true] {
            // font-size first: em lengths in the other properties depend on it
            for d in decls.iter().filter(|d| d.important == important && font_first(d)) {
                run(&mut c, units(parent.font_size), d);
            }
        }
        let u = units(c.font_size);
        for important in [false, true] {
            for d in decls.iter().filter(|d| d.important == important && !font_first(d)) {
                run(&mut c, u, d);
            }
        }
        c
    }

    fn units(&self, font_size: f32) -> Units {
        Units { font_size, viewport: self.viewport }
    }

    /// A new box. `link`: append it to its parent's child list (elements and
    /// text); words, breaks and line boxes only point at their parent.
    fn push(&mut self, parent: Option<usize>, content: Content, owner: Option<usize>, style: StyleId,
            key: Key, link: bool) -> usize {
        let i = self.nodes.len();
        let prev = match parent {
            Some(p) if link => self.nodes[p].last,
            _ => NONE,
        };
        self.nodes.push(BoxNode {
            parent,
            first: NONE,
            last: NONE,
            next: NONE,
            prev,
            content,
            el: NONE,
            owner: owner.unwrap_or(i),
            style,
            key,
            fp: 0,
            taffy: None,
            pos: (1, 1),
            tpos: (1, 1),
            marker: None,
            styled: false,
            bounds: rect(0.0, 0.0, 0.0, 0.0),
            clip: None,
            opacity: 1.0,
            visible: true,
            scroll_range: (0.0, 0.0),
            scroll_pos: (0.0, 0.0),
            fold: None,
            folded: false,
        });
        if let (Some(p), true) = (parent, link) {
            if prev == NONE {
                self.nodes[p].first = i as u32;
            } else {
                self.nodes[prev as usize].next = i as u32;
            }
            self.nodes[p].last = i as u32;
        }
        i
    }

    /// Remove the last box (an element that turned out not to render).
    fn pop(&mut self) {
        let n = self.nodes.pop().expect("a box to pop");
        if let Some(p) = n.parent {
            let i = self.nodes.len() as u32;
            if self.nodes[p].last == i {
                self.nodes[p].last = n.prev;
                if n.prev == NONE {
                    self.nodes[p].first = NONE;
                } else {
                    self.nodes[n.prev as usize].next = NONE;
                }
            }
        }
        if n.el != NONE && n.el as usize == self.els.len() - 1 {
            self.els.pop();
        }
    }

    /// Build an element; returns its index (None when not rendered).
    fn element(&mut self, mut div: Div, parent: Option<usize>, key: Key, pos: (usize, usize)) -> Option<usize> {
        let parent_style = parent.map(|p| self.nodes[p].style).unwrap_or(ROOT_STYLE);
        let i = self.push(parent, Content::Element, None, parent_style, key, true);
        self.nodes[i].pos = pos;
        self.nodes[i].tpos = std::mem::replace(&mut self.next_tpos, (1, 1));
        self.nodes[i].el = self.els.len() as u32;
        self.els.push(ElData {
            tag: div.tag,
            id: div.id.take(),
            attrs: std::mem::take(&mut div.attrs),
            listeners: std::mem::take(&mut div.listeners),
            has: 0,
        });
        if !self.author.has.is_empty() {
            // :has() looks at the element's subtree, which isn't built yet:
            // evaluate it on the declarative children instead
            let mut bits = 0u64;
            let mut flat = Vec::new();
            for (id, entry) in self.author.has.iter().enumerate().take(64) {
                if !entry.host_matches(&self.subject(i)) {
                    continue;
                }
                if flat.is_empty() {
                    flatten(&div, key, &mut flat);
                }
                let anchor = DivSubject { flat: &flat, state: self.state, i: 0 };
                if crate::css::has_match(&entry.rels, &anchor) {
                    bits |= 1 << id;
                }
            }
            if let Some(e) = self.els.last_mut() {
                e.has = bits;
            }
        }
        self.nodes[i].fp = self.fingerprint(i);
        // `styled` (any value but "false") turns Blender's theme on for the subtree
        self.nodes[i].styled = match self.els.last().and_then(|e| e.attrs.iter().find(|(n, _)| n == "styled")) {
            Some((_, v)) => v.as_ref() != "false",
            None => parent.is_some_and(|p| self.nodes[p].styled),
        };
        let kind = tag_kind(div.tag);
        // widgets and replaced elements are atomic inlines; flex/grid items are blockified
        let fixup = if kind == TagKind::Widget || kind == TagKind::Replaced {
            1
        } else if parent.is_some_and(|p| matches!(self.st(p).display,
                                                  DisplayKind::Flex | DisplayKind::InlineFlex
                                                  | DisplayKind::Grid | DisplayKind::InlineGrid)) {
            2
        } else {
            0
        };
        let style = self.cascade(i, &div, parent_style, fixup);
        if self.styles[style].display == DisplayKind::None || kind == TagKind::Metadata {
            self.pop();
            return None;
        }
        let style = self.animate(i, &div, parent_style, style);
        self.nodes[i].style = style;
        self.counter_ops(style, parent.unwrap_or(usize::MAX));
        // attributes moved into ElData: widgets read them back through the arena
        div.attrs = Vec::new();
        match kind {
            TagKind::Widget => {
                let spec = WidgetSpec::from_element(&div, self.els.last().map(|e| &e.attrs[..]).unwrap_or(&[]),
                                                    key, self.state);
                if let Some(mut spec) = spec {
                    // browser-look controls in plain HTML; Blender widgets inside
                    // `styled` and for the Blender components (`bui-blender`)
                    spec.html = !self.nodes[i].styled && self.attr(i, "bui-blender").is_none();
                    self.nodes[i].content = Content::Widget(spec);
                } else {
                    self.children(i, div.children);
                }
            }
            TagKind::Replaced => {
                let r = if let Some(f) = div.paint.take() {
                    Replaced::Painted(f)
                } else if let Some(img) = div.image.take() {
                    Replaced::Image(img)
                } else if let Some(v) = div.video.take() {
                    Replaced::Video(v)
                } else if div.tag == "video" && let Some(v) = self.video_src(i) {
                    Replaced::Video(v)
                } else if let Some(file) = self.attr(i, "src").map(str::to_owned).and_then(|s| self.images.load(&s)) {
                    Replaced::File(file, self.attr(i, "frame").and_then(|v| v.trim().parse().ok()))
                } else {
                    Replaced::Placeholder(div.tag)
                };
                self.nodes[i].content = Content::Replaced(r);
            }
            TagKind::Break => {
                self.nodes[i].content = Content::LineBreak;
            }
            TagKind::Box | TagKind::Metadata => {
                let mut children = div.children;
                if div.tag == "details" {
                    let open = self.subject(i).attr("open").is_some();
                    if !open {
                        children.retain(|c| matches!(c, AnyElement::Element(d) if d.tag == "summary"));
                    }
                }
                if div.tag == "q" {
                    let (open, close) = self.st(i).quotes.clone()
                        .unwrap_or_else(|| ("\u{201c}".into(), "\u{201d}".into()));
                    children.insert(0, AnyElement::Text(open.into()));
                    children.push(AnyElement::Text(close.into()));
                }
                let pseudo = self.author.uses_pseudo() || self.ua_for(i).0.uses_pseudo();
                if pseudo {
                    self.generated(i, crate::css::PseudoElement::Before);
                }
                self.children(i, children);
                if pseudo {
                    self.generated(i, crate::css::PseudoElement::After);
                }
            }
        }
        // counters this element's children created go out of scope
        while self.counters.last().is_some_and(|c| c.2 == i) {
            self.counters.pop();
        }
        Some(i)
    }

    /// Apply `counter-reset`, then `-increment`, then `-set` of style `sid`; new counters are scoped to `scope` (the parent: an element's
    /// counter is seen by its following siblings).
    fn counter_ops(&mut self, sid: StyleId, scope: usize) {
        let Some(ops) = self.styles[sid].counters.clone() else { return };
        for (name, v) in &ops.reset {
            // a sibling's reset replaces the instance a previous sibling made
            let same_scope = self.counters.iter_mut().rev().take_while(|c| c.2 == scope).find(|c| c.0 == *name);
            match same_scope {
                Some(c) => c.1 = *v,
                None => self.counters.push((name.clone(), *v, scope)),
            }
        }
        let find = |b: &mut Self, name: &str| -> usize {
            match b.counters.iter().rposition(|c| &*c.0 == name) {
                Some(k) => k,
                None => {
                    // using a counter that doesn't exist instantiates it here
                    b.counters.push((name.into(), 0, scope));
                    b.counters.len() - 1
                }
            }
        };
        for (name, v) in &ops.increment {
            let k = find(self, name);
            self.counters[k].1 = self.counters[k].1.wrapping_add(*v);
        }
        for (name, v) in &ops.set {
            let k = find(self, name);
            self.counters[k].1 = *v;
        }
    }

    /// The `::before` / `::after` box of element `i`, when a rule gives it content.
    fn generated(&mut self, i: usize, pe: crate::css::PseudoElement) {
        let (ua_sheet, ua_media) = self.ua_for(i);
        let author: &'a Stylesheet = self.author;
        let (ua, au) = {
            let subj = self.subject(i);
            (ua_sheet.matches(&subj, ua_media, Some(pe)), author.matches(&subj, &self.au_media, Some(pe)))
        };
        if ua.is_empty() && au.is_empty() {
            return;
        }
        let parent = self.nodes[i].style;
        let tag = if pe == crate::css::PseudoElement::Before { "::before" } else { "::after" };
        // shared like element styles: same parent + same rules = same style
        let hash = {
            let mut h = Fnv::default();
            (parent, tag, self.author_hash).hash(&mut h);
            for r in ua.iter().chain(au.iter()) {
                (*r as *const Rule as usize).hash(&mut h);
            }
            h.finish()
        };
        let rule_ids: Vec<usize> = ua.iter().chain(au.iter()).map(|r| *r as *const Rule as usize).collect();
        let fixup = if pe == crate::css::PseudoElement::Before { 3 } else { 4 };
        let viewport = (self.viewport.0.to_bits(), self.viewport.1.to_bits());
        let found = self.styles.cache.get(&hash).and_then(|b| b.iter().find(|(k, _)| {
            k.parent == parent && k.fixup == fixup && k.viewport == viewport && k.author == self.author_hash
                && k.rules == rule_ids
        })).map(|(_, id)| *id);
        let sid = match found {
            Some(id) => id,
            None => {
                let decls: smallvec::SmallVec<[&Decl; 24]> =
                    ua.iter().chain(au.iter()).flat_map(|r| r.decls.iter()).collect();
                let mut c = self.compute(parent, &decls);
                if matches!(self.st(i).display, DisplayKind::Flex | DisplayKind::InlineFlex
                            | DisplayKind::Grid | DisplayKind::InlineGrid) && c.display == DisplayKind::Inline {
                    c.display = DisplayKind::Block; // flex / grid items are blockified
                }
                let id = self.styles.add(c);
                let key = StyleKey { parent, viewport, author: self.author_hash, rules: rule_ids, decls: Vec::new(), fixup };
                self.styles.cache.entry(hash).or_default().push((key, id));
                id
            }
        };
        let st = &self.styles[sid];
        if st.content.is_none() || st.display == DisplayKind::None {
            return;
        }
        self.counter_ops(sid, i);
        let st = &self.styles[sid];
        let Some(parts) = st.content.as_ref() else { return };
        let quotes = st.quotes.clone().unwrap_or_else(|| ("\u{201c}".into(), "\u{201d}".into()));
        let mut text = String::new();
        for p in parts.iter() {
            match p {
                ContentPart::Text(t) => text.push_str(t),
                ContentPart::Attr(n) => text.push_str(self.attr(i, n).unwrap_or("")),
                ContentPart::OpenQuote => text.push_str(&quotes.0),
                ContentPart::CloseQuote => text.push_str(&quotes.1),
                ContentPart::Counter(name, ls) => {
                    let v = self.counters.iter().rev().find(|c| c.0 == *name).map_or(0, |c| c.1);
                    text.push_str(&ls.format(v));
                }
                ContentPart::Counters(name, sep, ls) => {
                    let all: Vec<String> = self.counters.iter().filter(|c| c.0 == *name)
                        .map(|c| ls.format(c.1)).collect();
                    text.push_str(&if all.is_empty() { ls.format(0) } else { all.join(sep) });
                }
            }
        }
        let key = child_key(self.nodes[i].key, tag, 0);
        let g = self.push(Some(i), Content::Element, None, sid, key, true);
        self.nodes[g].el = self.els.len() as u32;
        self.els.push(ElData { tag, id: None, attrs: Vec::new(), listeners: None, has: 0 });
        if !text.is_empty() {
            self.push(Some(g), Content::Text(text), Some(g), sid, child_key(key, "#text", 1), true);
        }
    }

    /// Children of element `i`: elements and text, keyed by position.
    fn children(&mut self, i: usize, mut children: Vec<AnyElement>) {
        // list markers: painted outside the box, or inline text when `inside`
        if self.st(i).display == DisplayKind::ListItem {
            let ls = self.st(i).list_style;
            let tag = self.subject(i).tag().to_owned();
            let marker = if tag == "summary" {
                let details = self.nodes[i].parent.unwrap_or(i);
                Some(if self.subject(details).attr("open").is_some() { "\u{25be}" } else { "\u{25b8}" }.into())
            } else {
                let idx = self.nodes[i].pos.0 + self.nodes[i].parent
                    .and_then(|p| self.attr(p, "start"))
                    .and_then(|s| s.parse::<usize>().ok()).map(|s| s - 1).unwrap_or(0);
                ls.marker(idx).or_else(|| self.st(i).list_image.as_ref().map(|_| String::new()))
            };
            match marker {
                Some(m) if self.st(i).marker_inside => {
                    children.insert(0, AnyElement::Text(format!("{m}\u{a0}").into()));
                }
                m => self.nodes[i].marker = m,
            }
        }
        let count = children.iter().filter(|c| matches!(c, AnyElement::Element(_))).count();
        // positions among siblings of the same tag (`:nth-of-type`, `:last-of-type`):
        // totals per tag (few distinct tags), then running counters, O(n)
        let mut tag_counts: smallvec::SmallVec<[(&'static str, u32, u32); 8]> = smallvec::SmallVec::new();
        for c in &children {
            if let AnyElement::Element(d) = c {
                match tag_counts.iter_mut().find(|t| std::ptr::eq(t.0, d.tag) || t.0 == d.tag) {
                    Some(t) => t.1 += 1,
                    None => tag_counts.push((d.tag, 1, 0)),
                }
            }
        }
        let (mut k, mut n) = (0, 0);
        let parent_key = self.nodes[i].key;
        for child in children {
            n += 1;
            match child {
                AnyElement::Element(d) => {
                    k += 1;
                    let key = match &d.id {
                        Some(id) => id_key(id),
                        None => child_key(parent_key, d.tag, k),
                    };
                    if let Some(t) = tag_counts.iter_mut().find(|t| std::ptr::eq(t.0, d.tag) || t.0 == d.tag) {
                        t.2 += 1;
                        self.next_tpos = (t.2, t.1);
                    }
                    self.element(d, Some(i), key, (k, count));
                }
                AnyElement::Text(t) => {
                    let style = self.nodes[i].style;
                    self.push(Some(i), Content::Text(t.into_owned()), Some(i), style,
                              child_key(parent_key, "#text", n), true);
                }
            }
        }
    }

    // -- taffy ------------------------------------------------------------------------------

    fn is_block_level(&self, i: usize) -> bool {
        match &self.nodes[i].content {
            Content::Element => !self.st(i).display.is_inline_level(),
            _ => false,
        }
    }

    fn base_style(&self, i: usize) -> Style {
        let c = self.st(i);
        let mut s = c.layout.clone();
        s.display = match c.display {
            DisplayKind::Flex | DisplayKind::InlineFlex => Display::Flex,
            DisplayKind::Grid | DisplayKind::InlineGrid => Display::Grid,
            DisplayKind::Table | DisplayKind::TableRowGroup => {
                s.flex_direction = FlexDirection::Column;
                let sp = if c.border_collapse { 0.0 } else { c.border_spacing.1 };
                s.gap.height = LengthPercentage::length(sp);
                if c.display == DisplayKind::Table && !c.border_collapse {
                    let pad = |v: LengthPercentage, add: f32| match v.into_raw() {
                        r if r.tag() == taffy::CompactLength::LENGTH_TAG => LengthPercentage::length(r.value() + add),
                        _ => v,
                    };
                    let (h, v) = c.border_spacing;
                    s.padding = Rect { left: pad(s.padding.left, h), right: pad(s.padding.right, h),
                                       top: pad(s.padding.top, v), bottom: pad(s.padding.bottom, v) };
                }
                Display::Flex
            }
            DisplayKind::TableRow => {
                s.flex_direction = FlexDirection::Row;
                s.gap.width = LengthPercentage::length(if c.border_collapse { 0.0 } else { c.border_spacing.0 });
                Display::Flex
            }
            _ if c.layout.display == Display::FlowRoot => Display::FlowRoot,
            _ => Display::Block,
        };
        if c.display == DisplayKind::Table {
            if let Some(tc) = self.table_cols.get(&i).filter(|t| t.fit && !t.widths.is_empty()) {
                // auto width: the table shrinks to its columns (up to its container)
                let sp = if c.border_collapse { 0.0 } else { c.border_spacing.0 };
                let w: f32 = tc.widths.iter().sum::<f32>() + sp * (tc.widths.len() + 1) as f32;
                let pad = |v: LengthPercentage| match v.into_raw() {
                    r if r.tag() == taffy::CompactLength::LENGTH_TAG => r.value(),
                    _ => 0.0,
                };
                let extra = pad(s.padding.left) + pad(s.padding.right) + pad(s.border.left) + pad(s.border.right);
                s.size.width = Dimension::length((w + extra).ceil());
                if s.max_size.width == LengthPercentageAuto::auto() {
                    s.max_size.width = LengthPercentageAuto::percent(1.0);
                }
            }
        }
        if c.display == DisplayKind::TableCell && s.size.width == Dimension::auto() {
            let span = self.attr(i, "colspan").and_then(|v| v.parse::<usize>().ok()).unwrap_or(1).max(1);
            match self.cell_columns(i, span) {
                // every cell of a column gets the column's width: rows line up
                Some((w, fit, fixed)) if w > 0.0 || fixed => {
                    s.flex_basis = Dimension::length(w);
                    s.flex_grow = if fit && !fixed { 0.0 } else { w.max(1.0) };
                    s.flex_shrink = w.max(1.0);
                    if fixed {
                        s.min_size.width = LengthPercentageAuto::length(0.0); // fixed tables don't widen for content
                    }
                }
                _ => {
                    s.flex_grow = span as f32;
                    s.flex_shrink = 1.0;
                    s.flex_basis = Dimension::percent(0.0);
                }
            }
        }
        s
    }

    /// The rows of table `t` (in row groups or directly inside).
    fn table_rows(&self, t: usize) -> Vec<usize> {
        let mut rows = Vec::new();
        for k in kids(&self.nodes, t) {
            if !matches!(self.nodes[k].content, Content::Element) {
                continue;
            }
            match self.st(k).display {
                DisplayKind::TableRow => rows.push(k),
                DisplayKind::TableRowGroup => rows.extend(kids(&self.nodes, k)
                    .filter(|&r| matches!(self.nodes[r].content, Content::Element)
                            && self.st(r).display == DisplayKind::TableRow)),
                _ => {}
            }
        }
        rows
    }

    fn row_cells(&self, r: usize) -> Vec<usize> {
        kids(&self.nodes, r).filter(|&c| matches!(self.nodes[c].content, Content::Element | Content::Widget(_))
                                     && self.st(c).display == DisplayKind::TableCell).collect()
    }

    /// The single-line width of everything in box `k` (its text, in its fonts).
    fn max_content(&mut self, k: usize) -> f32 {
        let mut w = 0.0f32;
        let list: Vec<usize> = kids(&self.nodes, k).collect();
        for c in list {
            match &self.nodes[c].content {
                Content::Text(t) => {
                    let st = &self.styles[self.nodes[c].style];
                    let (size, flags) = (st.font_size, text::flags(st));
                    let t = t.split_whitespace().collect::<Vec<_>>().join(" ");
                    w += self.text.width(&t, size, flags) + st.letter_spacing * t.chars().count() as f32;
                }
                Content::Element => {
                    let inner = self.max_content(c);
                    let st = self.st(c);
                    let u = self.units(st.font_size);
                    let px = |v: LengthPercentage| match v.into_raw() {
                        r if r.tag() == taffy::CompactLength::LENGTH_TAG => r.value(),
                        _ => 0.0,
                    };
                    let edges = px(st.layout.padding.left) + px(st.layout.padding.right)
                        + px(st.layout.border.left) + px(st.layout.border.right);
                    let explicit = match st.layout.size.width.into_raw() {
                        r if r.tag() == taffy::CompactLength::LENGTH_TAG => Some(r.value()),
                        _ => None,
                    };
                    let _ = u;
                    let own = explicit.unwrap_or(inner + edges);
                    // blocks stack; inline content continues the line
                    if st.display.is_inline_level() || st.display == DisplayKind::Inline {
                        w += own;
                    } else {
                        w = w.max(own);
                    }
                }
                _ => {}
            }
        }
        w
    }

    /// Column widths of table `t`: the widest single-line content of each
    /// column (auto layout), or the first row's cell widths (fixed).
    fn table_columns(&mut self, t: usize) {
        let fixed = self.st(t).table_fixed;
        let fit = self.st(t).layout.size.width == Dimension::auto();
        let mut widths: Vec<f32> = Vec::new();
        let rows = self.table_rows(t);
        for (ri, r) in rows.iter().enumerate() {
            if fixed && ri > 0 {
                break;
            }
            let mut col = 0usize;
            for c in self.row_cells(*r) {
                let span = self.attr(c, "colspan").and_then(|v| v.parse::<usize>().ok()).unwrap_or(1).max(1);
                let st = self.st(c);
                let px = |v: LengthPercentage| match v.into_raw() {
                    r if r.tag() == taffy::CompactLength::LENGTH_TAG => r.value(),
                    _ => 0.0,
                };
                let edges = px(st.layout.padding.left) + px(st.layout.padding.right)
                    + px(st.layout.border.left) + px(st.layout.border.right);
                let explicit = match st.layout.size.width.into_raw() {
                    r if r.tag() == taffy::CompactLength::LENGTH_TAG => Some(r.value()),
                    _ => None,
                };
                let w = if fixed { explicit.unwrap_or(0.0) } else { explicit.unwrap_or(0.0).max(self.max_content(c) + edges) };
                if widths.len() < col + span {
                    widths.resize(col + span, 0.0);
                }
                if span == 1 {
                    widths[col] = widths[col].max(w.ceil());
                }
                col += span;
            }
        }
        if fixed {
            // unspecified columns share what the specified ones leave
            let given: f32 = widths.iter().sum();
            let free = widths.iter().filter(|w| **w == 0.0).count();
            if free > 0 {
                let total = match self.st(t).layout.size.width.into_raw() {
                    r if r.tag() == taffy::CompactLength::LENGTH_TAG => r.value(),
                    _ => self.viewport.0,
                };
                let each = ((total - given) / free as f32).max(0.0);
                widths.iter_mut().filter(|w| **w == 0.0).for_each(|w| *w = each);
            }
        }
        self.table_cols.insert(t, TableCols { widths, fit, fixed });
    }

    /// The width (px) of the columns cell `c` spans, and its table's mode.
    fn cell_columns(&self, c: usize, span: usize) -> Option<(f32, bool, bool)> {
        let row = self.nodes[c].parent?;
        let mut t = self.nodes[row].parent?;
        if self.st(t).display == DisplayKind::TableRowGroup {
            t = self.nodes[t].parent?;
        }
        let tc = self.table_cols.get(&t)?;
        let mut col = 0usize;
        for k in self.row_cells(row) {
            if k == c {
                break;
            }
            col += self.attr(k, "colspan").and_then(|v| v.parse::<usize>().ok()).unwrap_or(1).max(1);
        }
        let end = (col + span).min(tc.widths.len());
        if col >= end {
            return None;
        }
        let sp = self.st(t).border_spacing.0;
        let w = tc.widths[col..end].iter().sum::<f32>() + sp * (end - col - 1) as f32;
        Some((w, tc.fit, tc.fixed))
    }

    /// Make line-container style: a wrapping flex row aligned per text-align.
    fn line_style(c: &Computed, mut s: Style) -> Style {
        s.display = Display::Flex;
        s.flex_direction = FlexDirection::Row;
        // nowrap / pre text arrives as unbreakable pieces; wrapping only
        // happens at forced breaks (<br>, newlines) and between inline boxes
        s.flex_wrap = FlexWrap::Wrap;
        s.align_items = AlignItems::FLEX_END;
        s.align_content = AlignContent::FLEX_START;
        s.justify_content = match c.text_align {
            TextAlign::Center => JustifyContent::CENTER,
            TextAlign::Right => JustifyContent::FLEX_END,
            _ => JustifyContent::FLEX_START,
        };
        s
    }

    /// The taffy node for `key` with this style, measure context and
    /// children: last frame's node, updated only where something differs
    /// (which marks it dirty), or a new one.
    fn node(&mut self, key: Key, style: Style, ctx: Option<Measure>, children: &[NodeId]) -> NodeId {
        let stamp = self.recon.stamp;
        let reuse = match self.recon.map.get_mut(&key) {
            Some((id, st)) if *st != stamp => {
                *st = stamp;
                Some(*id)
            }
            _ => None,
        };
        let t = &mut *self.taffy;
        if let Some(id) = reuse {
            if *t.style(id) != style {
                t.set_style(id, style);
                self.changed = true;
            }
            if t.children(id) != children {
                t.set_children(id, children);
                self.changed = true;
            }
            if t.context(id) != ctx.as_ref() {
                t.set_context(id, ctx);
                self.changed = true;
            }
            return id;
        }
        let id = match ctx {
            Some(m) => t.new_leaf_with_context(style, m),
            None => t.new_with_children(style, children),
        };
        self.changed = true;
        match self.recon.map.entry(key) {
            std::collections::hash_map::Entry::Occupied(_) => self.recon.extra.push(id), // duplicate key
            std::collections::hash_map::Entry::Vacant(v) => {
                v.insert((id, stamp));
            }
        }
        id
    }

    fn leaf(&mut self, i: usize, style: Style) -> NodeId {
        let id = self.node(self.nodes[i].key, style, None, &[]);
        self.nodes[i].taffy = Some(id);
        id
    }

    /// Replace the text of box `k` by its whitespace-processed, transformed form.
    fn transform_text(&mut self, k: usize, c: StyleId) {
        let (tt, ws, tab) = (self.styles[c].text_transform, self.styles[c].white_space, self.styles[c].tab_size);
        let (rtl, ovr) = (self.styles[c].layout.direction == taffy::style::Direction::Rtl, self.styles[c].bidi_override);
        if let Content::Text(t) = &self.nodes[k].content {
            let t = match transform(t, tt, ws, tab) {
                std::borrow::Cow::Owned(s) => s,
                std::borrow::Cow::Borrowed(s) => s.to_owned(),
            };
            let t = text::bidi_visual(&t, rtl, ovr).unwrap_or(t);
            self.nodes[k].content = Content::Text(t);
        }
    }

    /// The measure context for the text of box `node`, registered under `key`.
    fn text_measure(&mut self, key: Key, node: usize, c: StyleId, nowrap: bool) -> Measure {
        self.text_box.insert(key, node);
        let hash = match &self.nodes[node].content {
            Content::Text(t) => fnv(&[t.as_bytes()]),
            _ => 0,
        };
        let c = &self.styles[c];
        Measure::Text { key, hash, size: c.font_size, flags: text::flags(c), line: c.line_px(), nowrap,
                        brk: text::break_mode(c) }
    }

    /// The taffy node for box `i` (and its subtree). Marks it dirty when
    /// anything below changed (taffy's own propagation follows parent links,
    /// which reconciling can leave stale).
    fn layout_node(&mut self, i: usize) -> NodeId {
        let outer = std::mem::replace(&mut self.changed, false);
        let id = self.layout_node_inner(i);
        if self.changed {
            self.taffy.mark_dirty(id);
        }
        self.changed |= outer;
        id
    }

    fn layout_node_inner(&mut self, i: usize) -> NodeId {
        if self.st(i).display == DisplayKind::Table {
            self.table_columns(i);
        }
        let mut base = self.base_style(i);
        if i == 0 {
            // the root fills the viewport
            base.min_size = Size { width: LengthPercentageAuto::length(self.viewport.0),
                                   height: LengthPercentageAuto::length(self.viewport.1) };
        }
        let sid = self.nodes[i].style;
        match &self.nodes[i].content {
            Content::Widget(spec) => {
                let (w, h) = (self.widgets)(self.nodes[i].key, spec);
                let mut s = base;
                if s.size.width == Dimension::auto() {
                    s.size.width = Dimension::length(w);
                }
                if s.size.height == Dimension::auto() {
                    s.size.height = Dimension::length(h);
                }
                return self.leaf(i, s);
            }
            Content::Replaced(r) => {
                let (iw, ih) = match r {
                    Replaced::Image(img) => (img.width as f32, img.height as f32),
                    Replaced::File(file, _) => (file.width as f32, file.height as f32),
                    Replaced::Video(v) => v.size().map_or((300.0, 150.0), |(w, h)| (w as f32, h as f32)),
                    _ => (300.0, 150.0),
                };
                let attr = |n: &str| self.attr(i, n).and_then(|v| v.trim_end_matches("px").parse::<f32>().ok());
                let mut s = base;
                let (aw, ah) = (attr("width"), attr("height"));
                if s.size.width == Dimension::auto() {
                    s.size.width = Dimension::length(aw.unwrap_or(match ah {
                        Some(h) if ih > 0.0 => h * iw / ih,
                        _ => iw,
                    }));
                }
                if s.size.height == Dimension::auto() {
                    s.size.height = Dimension::length(ah.unwrap_or(match aw {
                        Some(w) if iw > 0.0 => w * ih / iw,
                        _ => ih,
                    }));
                }
                return self.leaf(i, s);
            }
            Content::LineBreak => {
                let s = Style { size: Size { width: Dimension::percent(1.0), height: Dimension::length(0.0) },
                                flex_shrink: 0.0, ..Default::default() };
                return self.leaf(i, s);
            }
            Content::Text(_) => {
                // a text run as a flex/grid item: measured, wrapping. The box
                // keeps the transformed text, so paint draws what was measured.
                self.transform_text(i, sid);
                let nowrap = matches!(self.styles[sid].white_space, WhiteSpace::NoWrap | WhiteSpace::Pre);
                let key = self.nodes[i].key;
                let m = self.text_measure(key, i, sid, nowrap);
                let id = self.node(key, Style::default(), Some(m), &[]);
                self.nodes[i].taffy = Some(id);
                return id;
            }
            _ => {}
        }
        if let Some(k) = self.foldable_text(i) {
            // one leaf for the box and its text: the text is measured as the
            // box's content and placed inside it after layout
            self.transform_text(k, sid);
            let nowrap = self.styles[sid].white_space == WhiteSpace::NoWrap;
            let key = self.nodes[i].key;
            let m = self.text_measure(key, k, sid, nowrap);
            let mut s = base;
            s.display = Display::Block;
            let id = self.node(key, s, Some(m), &[]);
            self.nodes[i].taffy = Some(id);
            self.nodes[i].fold = Some(k);
            self.nodes[k].folded = true;
            return id;
        }
        let c = self.styles[sid].clone_display();
        let flex_like = matches!(c.display, DisplayKind::Flex | DisplayKind::InlineFlex
                                 | DisplayKind::Grid | DisplayKind::InlineGrid
                                 | DisplayKind::Table | DisplayKind::TableRowGroup
                                 | DisplayKind::TableRow);
        let mut list: Kids = kids(&self.nodes, i).collect();
        let ordered = |b: &Builder, k: usize| {
            let st = b.st(k);
            if st.display == DisplayKind::TableCaption && st.caption_bottom { i32::MAX } else { st.order }
        };
        if list.iter().any(|&k| ordered(self, k) != 0) {
            list.sort_by_key(|&k| ordered(self, k));
        }
        let mut out: NodeList = NodeList::new();
        if flex_like {
            for k in list {
                if let Content::Text(t) = &self.nodes[k].content {
                    if t.trim().is_empty() && self.st(k).white_space == WhiteSpace::Normal {
                        continue;
                    }
                }
                self.child_nodes(k, &mut out);
            }
            let id = self.node(self.nodes[i].key, base, None, &out);
            self.nodes[i].taffy = Some(id);
            return id;
        }
        // block container: runs of inline content become line boxes
        if list.iter().all(|&k| !self.is_block_level(k)) {
            self.inline_items(&list, i, &mut out, true);
            let line = Self::line_style(&self.styles[sid], base);
            let id = self.node(self.nodes[i].key, line, None, &out);
            self.nodes[i].taffy = Some(id);
            return id;
        }
        let mut run: Kids = Kids::new();
        for k in list {
            if self.is_block_level(k) {
                self.flush_run(i, &mut run, &mut out);
                self.child_nodes(k, &mut out);
            } else {
                run.push(k);
            }
        }
        self.flush_run(i, &mut run, &mut out);
        let id = self.node(self.nodes[i].key, base, None, &out);
        self.nodes[i].taffy = Some(id);
        id
    }

    /// The lone text child of element `i`, when laying the pair out as one
    /// measured leaf gives the same result as two nodes (or a line of words).
    fn foldable_text(&self, i: usize) -> Option<usize> {
        let n = &self.nodes[i];
        if !matches!(n.content, Content::Element) || n.first == NONE || n.first != n.last {
            return None;
        }
        let k = n.first as usize;
        match &self.nodes[k].content {
            Content::Text(t) if !t.trim().is_empty() => {}
            _ => return None,
        }
        let c = self.st(i);
        let s = &c.layout;
        let display_ok = match c.display {
            DisplayKind::Block | DisplayKind::InlineBlock | DisplayKind::ListItem
            | DisplayKind::TableCell | DisplayKind::TableCaption => true,
            DisplayKind::Flex | DisplayKind::InlineFlex => {
                s.flex_wrap == FlexWrap::NoWrap
                    && matches!(s.flex_direction, FlexDirection::Row | FlexDirection::Column)
            }
            _ => false,
        };
        (display_ok
            && c.letter_spacing == 0.0
            && c.word_spacing == 0.0
            && c.text_indent == crate::geometry::Length::Px(0.0)
            && c.vertical_align == VAlign::Baseline
            && !c.small_caps
            && matches!(c.white_space, WhiteSpace::Normal | WhiteSpace::NoWrap)
            && s.overflow.x == Overflow::Visible
            && s.overflow.y == Overflow::Visible)
            .then_some(k)
    }

    fn child_nodes(&mut self, k: usize, out: &mut NodeList) {
        if self.st(k).display == DisplayKind::Contents {
            let list: Kids = kids(&self.nodes, k).collect();
            for c in list {
                self.child_nodes(c, out);
            }
            return;
        }
        out.push(self.layout_node(k));
    }

    /// An anonymous line box for inline content between blocks.
    fn flush_run(&mut self, parent: usize, run: &mut Kids, out: &mut NodeList) {
        let only_space = run.iter().all(|&k| matches!(&self.nodes[k].content,
                                                      Content::Text(t) if t.trim().is_empty()));
        if run.is_empty() || only_space {
            run.clear();
            return;
        }
        let style = self.nodes[parent].style;
        let key = child_key(self.nodes[parent].key, "#anon", out.len());
        let anon = self.push(Some(parent), Content::Anon, Some(parent), style, key, false);
        let mut line = NodeList::new();
        let items: Kids = std::mem::take(run);
        self.inline_items(&items, parent, &mut line, true);
        let ls = Self::line_style(&self.styles[style], Style::default());
        let id = self.node(key, ls, None, &line);
        if self.changed {
            self.taffy.mark_dirty(id);
        }
        self.nodes[anon].taffy = Some(id);
        out.push(id);
    }

    /// Flatten inline content into line items: words, atomic inline boxes, breaks.
    fn inline_items(&mut self, list: &[usize], owner: usize, line: &mut NodeList, first: bool) {
        let mut first_word = first;
        for &k in list {
            match &self.nodes[k].content {
                Content::Text(_) => {
                    let n = line.len();
                    self.words(k, owner, first_word, line);
                    if line.len() > n {
                        first_word = false;
                    }
                }
                Content::Element if matches!(self.st(k).display, DisplayKind::Inline | DisplayKind::Contents) => {
                    let inner: Kids = kids(&self.nodes, k).collect();
                    self.inline_items(&inner, k, line, first_word);
                    first_word = false;
                }
                _ => {
                    self.child_nodes(k, line);
                    first_word = false;
                }
            }
        }
    }

    /// Word boxes for text box `src`, with the style of its inline owner. The
    /// box keeps the processed text; words are byte ranges into it.
    fn words(&mut self, src: usize, owner: usize, first: bool, line: &mut NodeList) {
        let sid = self.nodes[owner].style;
        let c = &self.styles[sid];
        let (ws, tt, size, letter, word_sp) = (c.white_space, c.text_transform, c.font_size, c.letter_spacing, c.word_spacing);
        let (tab, break_all) = (c.tab_size, c.break_all);
        let flags = text::flags(c);
        let line_h = c.line_px();
        let indent = if first { c.text_indent.resolve(&self.units(size), 0.0) } else { 0.0 };
        // the processed text, kept in the box
        let Content::Text(raw) = std::mem::replace(&mut self.nodes[src].content, Content::Anon) else { return };
        let mut text = match transform(&raw, tt, ws, tab) {
            std::borrow::Cow::Borrowed(_) => raw,
            std::borrow::Cow::Owned(s) => s,
        };
        // bidirectional text: laid out in visual order
        let (rtl, ovr) = (c.layout.direction == taffy::style::Direction::Rtl, c.bidi_override);
        if let Some(v) = text::bidi_visual(&text, rtl, ovr) {
            text = v;
        }
        if ws == WhiteSpace::NoWrap {
            text = collapse(&text);
        }
        // pieces: byte range, trailing space, forced break after
        let mut pieces: smallvec::SmallVec<[(usize, usize, bool, bool); 16]> = smallvec::SmallVec::new();
        let base = text.as_ptr() as usize;
        let range = |w: &str| (w.as_ptr() as usize - base, w.as_ptr() as usize - base + w.len());
        match ws {
            WhiteSpace::Pre | WhiteSpace::PreWrap | WhiteSpace::PreLine => {
                let lines: Vec<&str> = text.split('\n').collect();
                for (n, l) in lines.iter().enumerate() {
                    let brk = n + 1 < lines.len();
                    if ws == WhiteSpace::Pre {
                        let (a, b) = range(l);
                        pieces.push((a, b, false, brk));
                    } else {
                        let words: Vec<&str> = l.split_whitespace().collect();
                        if words.is_empty() {
                            let (a, _) = range(l);
                            pieces.push((a, a, false, brk));
                        }
                        for (j, w) in words.iter().enumerate() {
                            let (a, b) = range(w);
                            pieces.push((a, b, j + 1 < words.len(), brk && j + 1 == words.len()));
                        }
                    }
                }
            }
            WhiteSpace::NoWrap => pieces.push((0, text.len(), false, false)),
            WhiteSpace::Normal => {
                let lead = text.starts_with(char::is_whitespace) && !first;
                let words: Vec<&str> = text.split_whitespace().collect();
                let trail = text.ends_with(char::is_whitespace);
                for (j, w) in words.iter().enumerate() {
                    let (mut a, b) = range(w);
                    if j == 0 && lead {
                        a -= 1; // one leading space, drawn with the word
                    }
                    pieces.push((a, b, j + 1 < words.len() || trail, false));
                }
            }
        }
        // overflow-wrap: a word wider than its block (as laid out last
        // frame) is cut where it has to be
        let anywhere = self.styles[sid].wrap_anywhere && !break_all
            && ws != WhiteSpace::NoWrap && ws != WhiteSpace::Pre;
        if anywhere {
            let mut blk = owner;
            while self.st(blk).display.is_inline_level() || self.st(blk).display == DisplayKind::Inline {
                match self.nodes[blk].parent {
                    Some(p) => blk = p,
                    None => break,
                }
            }
            let max = self.wrap_widths.get(&self.nodes[blk].key).copied().unwrap_or(self.viewport.0).max(1.0);
            let mut out: smallvec::SmallVec<[(usize, usize, bool, bool); 16]> = smallvec::SmallVec::new();
            for &(a, b, trailing, brk) in &pieces {
                let piece = &text[a..b];
                if self.text.width(piece, size, flags) <= max {
                    out.push((a, b, trailing, brk));
                    continue;
                }
                let mut start = a;
                let mut acc = String::new();
                for (o, ch) in piece.char_indices() {
                    acc.push(ch);
                    if self.text.width(&acc, size, flags) > max && acc.chars().count() > 1 {
                        out.push((start, a + o, false, false));
                        start = a + o;
                        acc.clear();
                        acc.push(ch);
                    }
                }
                out.push((start, b, trailing, brk));
            }
            pieces = out;
        }
        if break_all && ws != WhiteSpace::NoWrap && ws != WhiteSpace::Pre {
            let mut chars: smallvec::SmallVec<[(usize, usize, bool, bool); 16]> = smallvec::SmallVec::new();
            for &(a, b, trailing, brk) in &pieces {
                let piece = &text[a..b];
                let n = piece.char_indices().count();
                for (j, (o, ch)) in piece.char_indices().enumerate() {
                    let last = j + 1 == n;
                    chars.push((a + o, a + o + ch.len_utf8(), trailing && last, brk && last));
                }
                if n == 0 {
                    chars.push((a, b, trailing, brk));
                }
            }
            pieces = chars;
        }
        let space = self.text.width(" ", size, flags) + word_sp;
        let src_key = self.nodes[src].key;
        for (n, &(a, b, trailing, brk)) in pieces.iter().enumerate() {
            let piece = &text[a..b];
            // a leading space becomes a plain space for measuring and drawing
            let w = self.text.width(piece, size, flags)
                + letter * piece.chars().count() as f32
                + if trailing { space } else { 0.0 };
            let content = Content::Word { src: src as u32, start: a as u32, end: b as u32 };
            let node = self.push(Some(owner), content, Some(owner), sid, child_key(src_key, "#w", n), false);
            let s = Style {
                size: Size { width: Dimension::length(w.ceil()), height: Dimension::length(line_h) },
                flex_shrink: 0.0,
                margin: Rect { left: LengthPercentageAuto::length(if n == 0 { indent } else { 0.0 }),
                               ..Rect::zero() },
                ..Default::default()
            };
            line.push(self.leaf(node, s));
            if brk {
                let br = self.push(Some(owner), Content::LineBreak, Some(owner), sid,
                                   child_key(src_key, "#br", n), false);
                line.push(self.leaf(br, Style {
                    size: Size { width: Dimension::percent(1.0), height: Dimension::length(0.0) },
                    flex_shrink: 0.0,
                    ..Default::default()
                }));
            }
        }
        self.nodes[src].content = Content::Text(text);
    }
}

impl Computed {
    /// The few fields `layout_node` reads after building children (avoids
    /// holding a borrow of the style store across recursion).
    fn clone_display(&self) -> DisplayOnly {
        DisplayOnly { display: self.display }
    }
}

struct DisplayOnly {
    display: DisplayKind,
}

fn collapse(s: &str) -> String {
    let mut out = String::with_capacity(s.len());
    for w in s.split_whitespace() {
        if !out.is_empty() {
            out.push(' ');
        }
        out.push_str(w);
    }
    out
}

/// Whitespace processing and `text-transform`; borrows when nothing changes.
fn transform(s: &str, t: TextTransform, ws: WhiteSpace, tab: u8) -> std::borrow::Cow<'_, str> {
    use std::borrow::Cow;
    let collapse_ws = (ws == WhiteSpace::Normal || ws == WhiteSpace::NoWrap) && s.contains(['\n', '\t', '\r']);
    // preserved tabs advance to the next multiple of `tab-size` spaces
    let expand_tabs = matches!(ws, WhiteSpace::Pre | WhiteSpace::PreWrap) && s.contains('\t');
    if !collapse_ws && !expand_tabs && t == TextTransform::None {
        return Cow::Borrowed(s);
    }
    let s = if collapse_ws {
        s.replace(['\n', '\t', '\r'], " ")
    } else if expand_tabs {
        let mut out = String::with_capacity(s.len() + 16);
        let mut col = 0usize;
        for ch in s.chars() {
            match ch {
                '\t' if tab > 0 => {
                    let n = tab as usize - col % tab as usize;
                    out.extend(std::iter::repeat_n(' ', n));
                    col += n;
                }
                '\t' => {}
                '\n' => {
                    out.push('\n');
                    col = 0;
                }
                c => {
                    out.push(c);
                    col += 1;
                }
            }
        }
        out
    } else {
        s.to_string()
    };
    Cow::Owned(match t {
        TextTransform::None => s,
        TextTransform::Upper => s.to_uppercase(),
        TextTransform::Lower => s.to_lowercase(),
        TextTransform::Capitalize => s
            .split(' ')
            .map(|w| {
                let mut c = w.chars();
                c.next().map(|f| f.to_uppercase().chain(c).collect()).unwrap_or_default()
            })
            .collect::<Vec<String>>()
            .join(" "),
    })
}

/// Build, cascade and lay out `root` in a `viewport` (logical pixels),
/// reusing the arenas of `recycle` (the previous frame) and `caches`.
pub(crate) fn layout(root: AnyElement, viewport: (f32, f32), state: &UiState, caches: &mut LayoutCaches,
                     recycle: Frame, widgets: &mut dyn FnMut(Key, &WidgetSpec) -> (f32, f32)) -> Frame {
    let mut css = String::new();
    let mut title = None;
    caches.tw.on = TAILWIND.load(std::sync::atomic::Ordering::Relaxed);
    collect_styles(&root, &mut css, &mut title, &mut caches.tw);
    if caches.tw.on && !caches.tw.rules.is_empty() {
        css.push('\n');
        css.push_str(caches.tw.css());
    }
    let css_hash = fnv(&[css.as_bytes()]);
    if css_hash != caches.author.hash {
        caches.author = AuthorSheet { hash: css_hash, sheet: Stylesheet::parse(&css) };
        load_font_faces(&caches.author.sheet);
    }
    caches.styles.begin_frame();
    caches.styles.seed_properties(&caches.author.sheet, caches.author.hash);
    // the taffy tree persists: drop last frame's duplicates, start a new stamp
    for id in caches.recon.extra.drain(..) {
        caches.taffy.remove(id);
    }
    caches.recon.stamp = caches.recon.stamp.wrapping_add(1);
    caches.text_box.clear();
    let Frame { mut nodes, mut els, .. } = recycle;
    nodes.clear();
    els.clear();
    if caches.matched.author != caches.author.hash || caches.matched.map.len() > 50_000 {
        caches.matched.map.clear();
        caches.matched.author = caches.author.hash;
    }
    let LayoutCaches { styles, text, images, author, taffy, box_of, acc, matched, recon, text_box, containers,
                       wrap_widths, anim, .. } = caches;
    let mut b = Builder {
        nodes,
        els,
        taffy,
        styles,
        text,
        images,
        matched,
        recon,
        text_box,
        containers,
        wrap_widths,
        changed: false,
        next_tpos: (1, 1),
        author: &author.sheet,
        author_hash: author.hash,
        ua_media: ua_stylesheet().media_results(&crate::css::MediaEnv::viewport(viewport)),
        ua_styled_media: ua_styled_stylesheet().media_results(&crate::css::MediaEnv::viewport(viewport)),
        au_media: author.sheet.media_results(&crate::css::MediaEnv::viewport(viewport)),
        state,
        viewport,
        title,
        widgets,
        counters: Vec::new(),
        table_cols: FnvMap::default(),
        anim,
    };
    // the document: <html><body> unless the app built them itself
    let root_div = match root {
        AnyElement::Element(d) if d.tag == "html" => d,
        AnyElement::Element(d) if d.tag == "body" => crate::html::html().child(d),
        other => {
            let mut body = crate::html::body();
            body.children.push(other);
            crate::html::html().child(body)
        }
    };
    let s = span(Phase::Build);
    let root = match b.element(root_div, None, ROOT_KEY, (1, 1)) {
        Some(r) => r,
        None => b.push(None, Content::Element, None, ROOT_STYLE, ROOT_KEY, false),
    };
    drop(s);
    let s = span(Phase::Boxes);
    let root_id = b.layout_node(root);
    drop(s);
    let s = span(Phase::Taffy);
    // nodes not used this frame
    let stamp = b.recon.stamp;
    let taffy_ref = &mut *b.taffy;
    b.recon.map.retain(|_, (id, st)| {
        if *st == stamp {
            return true;
        }
        taffy_ref.remove(*id);
        false
    });
    let avail = Size { width: AvailableSpace::Definite(viewport.0),
                       height: AvailableSpace::Definite(viewport.1) };
    let Builder { nodes, els, taffy, styles, text: tc, title, text_box, .. } = b;
    taffy.compute(root_id, avail, |known, available, ctx| {
            match ctx {
                Measure::Text { key, size, flags, line, nowrap, brk, .. } => {
                    let text = match text_box.get(key).map(|&k| &nodes[k].content) {
                        Some(Content::Text(t)) => t.as_str(),
                        _ => "",
                    };
                    if !text.contains([' ', '\n']) && *brk == 0 {
                        // one word: no wrapping to do
                        let w = tc.width(text, *size, *flags);
                        return Size { width: known.width.unwrap_or(w.ceil()),
                                      height: known.height.unwrap_or(*line) };
                    }
                    let max_w = known.width.unwrap_or(match available.width {
                        AvailableSpace::Definite(w) => w,
                        AvailableSpace::MinContent => 0.0,
                        AvailableSpace::MaxContent => f32::INFINITY,
                    });
                    let lines = tc.wrap(text, *size, *flags, if *nowrap { f32::INFINITY } else { max_w }, *brk);
                    let w = lines.iter().map(|l| tc.width(l, *size, *flags)).fold(0.0, f32::max);
                    Size { width: known.width.unwrap_or(w.ceil()),
                           height: known.height.unwrap_or(*line * lines.len().max(1) as f32) }
                }
            }
        });
    drop(s);
    let _s = span(Phase::Place);
    let mut frame = Frame { nodes, els, title, by_key: Default::default() };
    box_of.clear();
    for (i, n) in frame.nodes.iter().enumerate() {
        if let Some(t) = n.taffy {
            let s = slot(t);
            if s >= box_of.len() {
                box_of.resize(s + 1, NONE);
            }
            box_of[s] = i as u32;
        }
    }
    let mut walk = Walk { t: taffy, box_of, state, vp: viewport, styles, text: tc };
    walk.place(&mut frame.nodes, root_id, 0.0, 0.0, None, (0.0, 0.0));
    finish(&mut frame.nodes, styles, acc);
    frame
}

/// Positions follow the taffy tree (words live in line containers, which may
/// be anonymous); translate and scroll offsets shift whole subtrees.
struct Walk<'a> {
    t: &'a crate::tree::LayoutTree<Measure>,
    box_of: &'a [u32],
    state: &'a UiState,
    vp: (f32, f32),
    styles: &'a StyleStore,
    text: &'a mut TextCache,
}

impl Walk<'_> {
    /// `cb`: the origin of the containing block of absolutely positioned
    /// descendants (taffy places those relative to it, not to their parent).
    fn place(&mut self, nodes: &mut [BoxNode], id: NodeId, ox: f32, oy: f32, clip: Option<Bounds<f32>>,
             cb: (f32, f32)) {
        let l = *self.t.layout(id);
        let (mut x, mut y) = (ox + l.location.x, oy + l.location.y);
        let (w, h) = (l.size.width, l.size.height);
        let mut child_clip = clip;
        let (mut sx, mut sy) = (0.0, 0.0);
        if let Some(i) = self.box_of.get(slot(id)).filter(|&&b| b != NONE).map(|&b| b as usize) {
            let st = &self.styles[nodes[i].style];
            let u = Units { font_size: st.font_size, viewport: self.vp };
            x += st.translate.0.resolve(&u, w);
            y += st.translate.1.resolve(&u, h);
            if matches!(nodes[i].content, Content::Word { .. }) {
                y += match st.vertical_align {
                    VAlign::Sub => st.font_size * 0.25,
                    VAlign::Super => -st.font_size * 0.35,
                    VAlign::Baseline => 0.0,
                };
            }
            nodes[i].bounds = rect(x, y, w, h);
            nodes[i].clip = clip;
            if let Some(cr) = st.clip_rect.filter(|_| matches!(st.layout.position, Position::Absolute | Position::Fixed)) {
                // edges from the border box's top-left corner; auto = that edge
                let e = |k: usize, auto: f32, basis: f32| cr[k].map_or(auto, |l| l.resolve(&u, basis));
                let (top, right, bottom, left) = (e(0, 0.0, h), e(1, w, w), e(2, h, h), e(3, 0.0, w));
                let r = rect(x + left, y + top, (right - left).max(0.0), (bottom - top).max(0.0));
                let r = match clip {
                    Some(c) => c.intersect(&r),
                    None => r,
                };
                nodes[i].clip = Some(r);
                child_clip = Some(r);
            }
            let ov = st.layout.overflow;
            if ov.x != Overflow::Visible || ov.y != Overflow::Visible {
                let b = l.border;
                let pad = rect(x + b.left, y + b.top, (w - b.left - b.right).max(0.0),
                               (h - b.top - b.bottom).max(0.0));
                child_clip = Some(match clip {
                    Some(c) => c.intersect(&pad),
                    None => pad,
                });
                if ov.x == Overflow::Scroll || ov.y == Overflow::Scroll {
                    let axis = |o: Overflow, content: f32, view: f32| {
                        if o == Overflow::Scroll { (content - view).max(0.0) } else { 0.0 }
                    };
                    let range = (axis(ov.x, l.scrollable_overflow_rect.right, pad.size.width),
                                 axis(ov.y, l.scrollable_overflow_rect.bottom, pad.size.height));
                    nodes[i].scroll_range = range;
                    let (ax, ay) = self.state.scroll.get(&nodes[i].key).copied().unwrap_or((0.0, 0.0));
                    sx = ax.clamp(0.0, range.0);
                    sy = ay.clamp(0.0, range.1);
                    nodes[i].scroll_pos = (sx, sy);
                }
            }
            if let Some(k) = nodes[i].fold {
                place_folded_text(nodes, i, k, rect(x, y, w, h), &l, self.styles, self.text);
            }
        }
        let inner = (x - sx, y - sy);
        let cb = if self.t.style(id).position == Position::Static { cb } else { inner };
        for &k in self.t.children(id) {
            let (kx, ky) = match self.t.style(k).position {
                Position::Absolute => cb,
                Position::Fixed => (0.0, 0.0),
                _ => inner,
            };
            self.place(nodes, k, kx, ky, child_clip, cb);
        }
    }
}

/// Put a folded text run where its own flex item / line box would have gone:
/// inside the content box, aligned like a lone flex item (or by `text-align`
/// in a block, which paint applies across the full width).
fn place_folded_text(nodes: &mut [BoxNode], i: usize, k: usize, b: Bounds<f32>, l: &taffy::Layout,
                     styles: &StyleStore, tc: &mut TextCache) {
    let c = &styles[nodes[i].style];
    let cb = rect(b.origin.x + l.border.left + l.padding.left, b.origin.y + l.border.top + l.padding.top,
                  (b.size.width - l.border.left - l.border.right - l.padding.left - l.padding.right).max(0.0),
                  (b.size.height - l.border.top - l.border.bottom - l.padding.top - l.padding.bottom).max(0.0));
    let Content::Text(t) = &nodes[k].content else { return };
    let flags = text::flags(c);
    let line = c.line_px();
    let brk = text::break_mode(c);
    let (tw, th) = if !t.contains([' ', '\n']) && brk == 0 {
        (tc.width(t, c.font_size, flags).ceil(), line)
    } else {
        let max = if c.white_space == WhiteSpace::NoWrap { f32::INFINITY } else { cb.size.width + 0.5 };
        let lines = tc.wrap(t, c.font_size, flags, max, brk);
        let w = lines.iter().map(|s| tc.width(s, c.font_size, flags)).fold(0.0, f32::max);
        (w.ceil(), line * lines.len().max(1) as f32)
    };
    let tw = if c.white_space == WhiteSpace::NoWrap { tw } else { tw.min(cb.size.width) };
    let s = &c.layout;
    // offset of a box of `size` in `room` for a start / center / end choice
    let at = |room: f32, size: f32, pos: u8| match pos {
        1 => (room - size) / 2.0,
        2 => room - size,
        _ => 0.0,
    };
    use taffy::style::{AlignContentKeyword as Ac, AlignItemsKeyword as Ai};
    let justify = match s.justify_content.keyword() {
        Ac::Center | Ac::SpaceAround | Ac::SpaceEvenly => 1,
        Ac::End | Ac::FlexEnd => 2,
        _ => 0,
    };
    let align = match s.align_items.keyword() {
        Ai::Center => 1,
        Ai::End | Ai::FlexEnd => 2,
        _ => 0,
    };
    let stretch = matches!(s.align_items.keyword(), Ai::Normal | Ai::Stretch);
    let tb = match c.display {
        DisplayKind::Flex | DisplayKind::InlineFlex if s.flex_direction == FlexDirection::Row => {
            rect(cb.origin.x + at(cb.size.width, tw, justify), cb.origin.y + at(cb.size.height, th, align), tw, th)
        }
        DisplayKind::Flex | DisplayKind::InlineFlex => {
            let w = if stretch { cb.size.width } else { tw };
            rect(cb.origin.x + at(cb.size.width, w, align), cb.origin.y + at(cb.size.height, th, justify), w, th)
        }
        _ => rect(cb.origin.x, cb.origin.y, cb.size.width, th), // block: text-align at paint
    };
    nodes[k].bounds = tb;
}

/// Inherited opacity / visibility (parents precede children in the arena),
/// and bounds of boxes without a layout node (inline elements): the union of
/// their pieces (children follow parents, so a reverse pass sees them first).
fn finish(nodes: &mut [BoxNode], styles: &StyleStore, acc: &mut Vec<Option<Bounds<f32>>>) {
    for i in 0..nodes.len() {
        let (po, pv, pc) = match nodes[i].parent {
            Some(p) => (nodes[p].opacity, nodes[p].visible, nodes[p].clip),
            None => (1.0, true, None),
        };
        let st = &styles[nodes[i].style];
        let own = matches!(nodes[i].content, Content::Element | Content::Widget(_) | Content::Replaced(_));
        nodes[i].opacity = if own { po * st.opacity } else { po };
        nodes[i].visible = pv && st.visible;
        if nodes[i].taffy.is_none() {
            nodes[i].clip = pc;
        }
    }
    acc.clear();
    acc.resize(nodes.len(), None);
    for i in (0..nodes.len()).rev() {
        if nodes[i].taffy.is_none() {
            if let Some(a) = acc[i] {
                nodes[i].bounds = a;
            }
        }
        let Some(p) = nodes[i].parent else { continue };
        if nodes[p].taffy.is_some() {
            continue;
        }
        let cb = nodes[i].bounds;
        if cb.size.width <= 0.0 && cb.size.height <= 0.0 {
            continue;
        }
        acc[p] = Some(match acc[p] {
            None => cb,
            Some(a) => {
                let x0 = a.origin.x.min(cb.origin.x);
                let y0 = a.origin.y.min(cb.origin.y);
                let x1 = (a.origin.x + a.size.width).max(cb.origin.x + cb.size.width);
                let y1 = (a.origin.y + a.size.height).max(cb.origin.y + cb.size.height);
                rect(x0, y0, x1 - x0, y1 - y0)
            }
        });
    }
}

impl Frame {
    /// Element boxes by key, built on first use (events and tests need it,
    /// rendering doesn't).
    pub(crate) fn by_key(&self) -> &HashMap<Key, usize> {
        self.by_key.get_or_init(|| {
            self.nodes.iter().enumerate().filter(|(_, n)| n.el != NONE).map(|(i, n)| (n.key, i)).collect()
        })
    }

    /// The element data of box `i`.
    pub(crate) fn el(&self, i: usize) -> Option<&ElData> {
        let e = self.nodes[i].el;
        (e != NONE).then(|| &self.els[e as usize])
    }

    pub(crate) fn attr(&self, i: usize, name: &str) -> Option<&str> {
        el_attr(&self.nodes, &self.els, i, name)
    }

    /// Element children of box `i`.
    pub(crate) fn children_of(&self, i: usize) -> impl Iterator<Item = usize> + '_ {
        kids(&self.nodes, i).filter(|&k| matches!(self.nodes[k].content, Content::Element | Content::Widget(_)
                                                  | Content::Replaced(_)))
    }

    /// Box `i` has no content (only collapsible whitespace): `empty-cells`.
    pub(crate) fn is_empty(&self, i: usize) -> bool {
        kids(&self.nodes, i).all(|k| match &self.nodes[k].content {
            Content::Text(t) => t.trim().is_empty(),
            Content::Anon => kids(&self.nodes, k).next().is_none(),
            _ => false,
        })
    }

    /// The text a box draws: a text run's text, or a word's slice of it.
    pub(crate) fn text(&self, i: usize) -> &str {
        match &self.nodes[i].content {
            Content::Text(t) => t,
            Content::Word { src, start, end } => match &self.nodes[*src as usize].content {
                Content::Text(t) => &t[*start as usize..*end as usize],
                _ => "",
            },
            _ => "",
        }
    }

    /// Element boxes from the root down to the topmost box under (x, y).
    pub(crate) fn hit_path(&self, x: f32, y: f32, styles: &StyleStore) -> Vec<usize> {
        let mut best: Option<(i32, usize)> = None;
        for (i, n) in self.nodes.iter().enumerate() {
            if !n.visible || n.taffy.is_none() || !styles[n.style].pointer_events {
                continue;
            }
            if n.clip.is_some_and(|c| !c.contains(x, y)) || !n.bounds.contains(x, y) {
                continue;
            }
            // later boxes paint over earlier ones; z-index lifts a subtree
            let z = self.z_of(i, styles);
            if best.is_none_or(|(bz, _)| z >= bz) {
                best = Some((z, i));
            }
        }
        let mut path = Vec::new();
        let mut cur = best.map(|(_, b)| self.nodes[b].owner);
        while let Some(i) = cur {
            if self.nodes[i].el != NONE {
                path.push(i);
            }
            cur = self.nodes[i].parent;
        }
        path.reverse();
        path
    }

    /// The effective stacking level of a box (its nearest z-index).
    pub(crate) fn z_of(&self, mut i: usize, styles: &StyleStore) -> i32 {
        loop {
            if let Some(z) = styles[self.nodes[i].style].z_index {
                return z;
            }
            match self.nodes[i].parent {
                Some(p) => i = p,
                None => return 0,
            }
        }
    }
}

/// `@font-face`: registers each face's first `url()` that loads (paths are
/// relative to the working directory), once per process. Styles computed
/// before a face loaded are recomputed because the sheet changed.
fn load_font_faces(sheet: &Stylesheet) {
    static LOADED: std::sync::Mutex<Vec<(String, bool, bool)>> = std::sync::Mutex::new(Vec::new());
    for face in &sheet.font_faces {
        let key = (face.family.to_ascii_lowercase(), face.bold, face.italic);
        if LOADED.lock().unwrap_or_else(|e| e.into_inner()).contains(&key) {
            continue;
        }
        let loaded = face.src.iter().any(|path| {
            std::fs::read(path).is_ok_and(|bytes| crate::add_font(&face.family, face.bold, face.italic, &bytes))
        });
        if loaded {
            LOADED.lock().unwrap_or_else(|e| e.into_inner()).push(key);
        }
    }
}