fleuron/

content.rs

//! The content tree: semantic input.
//!
//! The markdown frontend produces this; the element vocabulary is
//! bounded by what a book needs — book/section, heading, paragraph,
//! blockquote, thematic break, image, list, table,
//! emphasis/strong/code, link, hard break.
//!
//! This module is the **input contract**: everything downstream (style,
//! box construction, layout) consumes these types, and nothing widens
//! the vocabulary without a fixture and a test. It is a Rust type, and
//! that is the seam a frontend of its own builds against: a docx or CMS
//! reader constructs a `Book` directly, with the compiler checking the
//! shape.
//!
//! # Reading a tree back
//!
//! The tree serializes, internally tagged (`{"type": "paragraph", …}`)
//! so the shape maps one-to-one onto mdast. It is mostly an output: it
//! is how to see what a frontend made of a manuscript. It reads back
//! too, which is the door a host with a structured source of its own
//! comes in through, so what the engine writes is what a host may hand
//! it again.
//!
//! # Naming a node
//!
//! Every section, block and inline carries [`Attributes`]: any number of
//! classes and at most one id, which is what a sheet reaches one
//! element by. They are empty unless something set them, and a
//! frontend is not the only thing that can: a host with a structured
//! source of its own sets them on the tree it builds.
//!
//! # Node identity
//!
//! `NodeId` is engine-assigned, never frontend-supplied: input can't
//! collide ids or forge diagnostic origins. Every node's `id` field is
//! `#[serde(skip)]`, so a serialized tree has none. The ids in a tree
//! built by hand are `NodeId::UNASSIGNED` until `Book::assign_node_ids`
//! assigns dense ids from 1 in document order (pre-order: a node before
//! its children, sections in reading order).
//!
//! # Source positions
//!
//! Every node has an optional 1-based line/column into the markdown
//! source the frontend read it from; the section's `source` names the
//! file. `origin` formats the pair for diagnostics
//! (`chapter-01.md:12:3`). A missing position never fails a run.
//!
//! Beside it every node has an optional `span`: the bytes of that
//! source the node was read from, markup included. [`Book::node_at`]
//! turns a byte of a source into the node written there and
//! [`Book::source_of`] turns a node back into the bytes it was read
//! from, which is how a host holding the manuscript maps a cursor
//! onto a page and a run under the pointer back onto the file it was
//! written in. A tree built rather than parsed has neither, and both
//! questions answer with nothing.

use std::collections::BTreeMap;
use std::ops::Range;

use serde::{Deserialize, Serialize};

mod anchor;

pub use anchor::{Anchors, LinkTarget};

/// Identity of one node in the content tree, for diagnostics and
/// incremental relayout.
///
/// Assigned in document order, starting at 1.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Serialize, Deserialize,
)]
pub struct NodeId(u32);

impl NodeId {
    /// What every node's id is before assignment.
    pub const UNASSIGNED: NodeId = NodeId(0);

    /// The raw id. Monotonic in document order within one book.
    pub fn get(self) -> u32 {
        self.0
    }

    /// The node one number names. Identity stays the engine's to
    /// hand out; this is how a host asks about an id it read off a
    /// display structure, and an id no node has answers with
    /// nothing.
    pub fn new(id: u32) -> NodeId {
        NodeId(id)
    }

    /// The id this one becomes when the section around it is
    /// renumbered by `step`. A section's nodes are dense and in
    /// document order from its own id, so one step moves all of
    /// them. Unassigned stays unassigned.
    pub(crate) fn shifted(self, step: i64) -> NodeId {
        if self == NodeId::UNASSIGNED {
            return self;
        }
        if let Some((element, which)) = self.pseudo_element() {
            return element.shifted(step).pseudo(which);
        }
        NodeId((self.0 as i64 + step).max(0) as u32)
    }

    /// The id of one pseudo-element of this element. No content node
    /// has it.
    pub(crate) fn pseudo(self, which: PseudoElement) -> NodeId {
        let kind = match which {
            PseudoElement::Before => 0,
            PseudoElement::After => 1,
            PseudoElement::FirstLetter => 2,
            PseudoElement::FirstLine => 3,
        };
        NodeId(PSEUDO | (self.0 << 2) | kind)
    }

    /// The element and the pseudo-element this id names, where it
    /// names one. Nothing for the id of a content node.
    pub fn pseudo_element(self) -> Option<(NodeId, PseudoElement)> {
        if self.0 & PSEUDO == 0 {
            return None;
        }
        let which = match self.0 & 3 {
            0 => PseudoElement::Before,
            1 => PseudoElement::After,
            2 => PseudoElement::FirstLetter,
            _ => PseudoElement::FirstLine,
        };
        Some((NodeId((self.0 & !PSEUDO) >> 2), which))
    }

    /// The element this id stands for: the element a pseudo-element
    /// belongs to, or the node itself.
    pub fn element(self) -> NodeId {
        self.pseudo_element().map_or(self, |(element, _)| element)
    }
}

/// The ids at and above this one name pseudo-elements. Content ids
/// count up from 1 and stay below 2^29, so the element and two bits
/// for the kind fit under it.
const PSEUDO: u32 = 1 << 31;

/// The pseudo-elements the engine styles.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum PseudoElement {
    /// `::before`: on a block, a box that is its first child. On an
    /// inline element, text before its own.
    Before,
    /// `::after`: on a block, a box that is its last child. On an
    /// inline element, text after its own.
    After,
    /// `::first-letter`: the initial letter a drop cap is set from.
    FirstLetter,
    /// `::first-line`: the line a paragraph opens on.
    FirstLine,
}

/// A stretch of one node's text: the node it was written in, and
/// the bytes of that node's own text the stretch covers.
///
/// The range indexes the node's text as the frontend read it, before
/// `text-transform` or a synthesized small capital changed what was
/// shaped.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct SourceRange {
    /// The node the text was written in.
    pub node: NodeId,
    /// Byte range in that node's own text.
    pub range: Range<u32>,
}

/// The bytes of one source a node was read from: its extent in the
/// file, markup included.
///
/// A source and the text of the nodes read from it are different
/// bytes, because markup is not text. The span is the node's extent
/// rather than a character-by-character map, so a byte of the source
/// lands on the node written there and not on a letter of it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct SourceSpan {
    /// First byte of the source the node was read from.
    pub start: u32,
    /// One past the last.
    pub end: u32,
}

impl SourceSpan {
    /// Whether a byte of the source falls in the span. The end is
    /// past it, so the spans of two nodes written one after the other
    /// answer for their own bytes and no others.
    pub fn covers(self, byte: u32) -> bool {
        (self.start..self.end).contains(&byte)
    }

    /// How many bytes of the source it covers.
    fn width(self) -> u32 {
        self.end.saturating_sub(self.start)
    }
}

/// What a sheet names one node by: any number of classes, at most
/// one id.
///
/// Every section, block and inline carries one, empty unless
/// something set it. The names are as they are written in CSS, without the `.` or
/// the `#`.
#[derive(Debug, Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Attributes {
    /// The id, which the sheet reaches with `#name`.
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub id: Option<String>,
    /// The classes, in the order they were written, which the sheet
    /// reaches with `.name`.
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub classes: Vec<String>,
}

impl Attributes {
    /// Whether it names nothing, which is what a node carries until
    /// something sets one.
    pub fn is_empty(&self) -> bool {
        self.id.is_none() && self.classes.is_empty()
    }
}

/// The classes and the ids some part of a book carries, each once and
/// in sorted order, as a sheet names them: without the `.` or the `#`.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Names {
    /// Every class.
    pub classes: Vec<String>,
    /// Every id.
    pub ids: Vec<String>,
}

/// A 1-based position in the frontend's source document.
///
/// Line and column are as the markdown parser reported them. This is
/// diagnostic data, never layout input.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct SourcePos {
    /// 1-based line in the source markdown.
    pub line: u32,
    /// 1-based column in the source markdown.
    pub column: u32,
}

/// Formats a file name plus a position for diagnostics:
/// `chapter-01.md:12:3`. Missing parts degrade: bare file name, bare
/// position, empty string.
pub fn origin(source: Option<&str>, position: Option<SourcePos>) -> String {
    match (source, position) {
        (Some(file), Some(pos)) => format!("{file}:{}:{}", pos.line, pos.column),
        (Some(file), None) => file.to_string(),
        (None, Some(pos)) => format!("{}:{}", pos.line, pos.column),
        (None, None) => String::new(),
    }
}

/// Book metadata: everything about the work that isn't content.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Metadata {
    /// Title, for the half-title and running heads.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub title: Option<String>,
    /// Author, for the title page.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub author: Option<String>,
    /// Frontend-defined extensions (language, ISBN, subtitle…) keyed
    /// by name. Opaque to the engine; style reads them, layout
    /// doesn't.
    ///
    /// Left out of the JSON when empty, and so it has to be
    /// optional coming back in: what the engine writes is what a
    /// host hands it again.
    #[serde(default, skip_serializing_if = "BTreeMap::is_empty")]
    pub extra: BTreeMap<String, String>,
}

impl Metadata {
    /// The BCP 47 tag under `extra["language"]`. The PDF records it
    /// and hyphenation takes its patterns from it. A blank tag counts
    /// as none declared.
    pub fn language(&self) -> Option<&str> {
        self.extra
            .get("language")
            .map(|tag| tag.trim())
            .filter(|tag| !tag.is_empty())
    }
}

/// The root of the content tree: one book.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Book {
    /// The work's title, author and frontend extensions.
    pub metadata: Metadata,
    /// The chapters/files, in reading order.
    pub sections: Vec<Section>,
}

/// A chapter or file: the unit of markdown input and of source
/// attribution for diagnostics.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Section {
    /// Engine-assigned identity, for diagnostics; never serialized.
    #[serde(skip)]
    pub id: NodeId,
    /// File the frontend read (e.g. `chapter-01.md`).
    #[serde(skip_serializing_if = "Option::is_none")]
    pub source: Option<String>,
    /// Section title supplied outside the body (frontmatter
    /// `title:`); implies heading level 1.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub title: Option<String>,
    /// The classes and id a sheet names the section by: from a chapter
    /// file's frontmatter, or set by a host beside the source, where no
    /// byte of the source moves.
    #[serde(default, skip_serializing_if = "Attributes::is_empty")]
    pub attributes: Attributes,
    /// The section's blocks, in reading order.
    pub blocks: Vec<Block>,
    /// Where the frontend read this from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub position: Option<SourcePos>,
    /// The bytes of that source it was read from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub span: Option<SourceSpan>,
}

/// A block-level element: the unit of fragmentation input.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(tag = "type", rename_all = "snake_case")]
pub enum Block {
    /// `#` through `######`; levels outside 1–6 are rejected at parse.
    Heading {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// `#` count, 1-6.
        level: HeadingLevel,
        /// The heading's text, in reading order.
        inlines: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A run of prose: the unit line layout breaks.
    Paragraph {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The paragraph's text, in reading order.
        inlines: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A quotation set off by `>`; contents are blocks, not inlines —
    /// blockquotes nest.
    Blockquote {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The quoted blocks, in reading order.
        blocks: Vec<Block>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A code block: preformatted text, set as it was written.
    ///
    /// It holds text rather than inlines, because a code block has no
    /// markup inside it. The text keeps the newlines and the spaces
    /// the author wrote, and those are what its lines break at.
    CodeBlock {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The word after the opening fence, where one was written.
        /// It is carried for a painter that reads it, and the engine
        /// makes nothing of it.
        #[serde(default, skip_serializing_if = "Option::is_none")]
        info: Option<String>,
        /// The block's text, newlines and indentation intact.
        text: String,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `---`: a scene break, rendered as space or an ornament (❦).
    ThematicBreak {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `\pagebreak`: what follows it starts a new page. It holds no
    /// text and takes no height.
    PageBreak {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `\columnbreak`: what follows it starts the next column. It
    /// holds no text and takes no height.
    ColumnBreak {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A block-level image.
    Image {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// Where the image lives; the host resolves it, not the engine.
        url: String,
        /// Alt text: not laid out, but part of the accessibility
        /// contract.
        alt: String,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A list of items, numbered or not. An item holds blocks, as a
    /// blockquote does, so a list nests inside an item of another.
    List {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// Whether the items are numbered.
        #[serde(default)]
        ordered: bool,
        /// The number of the first item of a numbered list.
        #[serde(default = "first_number", skip_serializing_if = "is_first_number")]
        start: u32,
        /// Whether the source wrote the items without blank lines
        /// between them: a list of phrases rather than a list of
        /// paragraphs.
        #[serde(default)]
        tight: bool,
        /// The items, in reading order.
        #[serde(default)]
        items: Vec<ListItem>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A grid of cells. A cell holds blocks, as a blockquote does.
    Table {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The header rows, which name the columns, in reading order.
        #[serde(default)]
        head: Vec<Row>,
        /// The body rows, in reading order.
        #[serde(default)]
        body: Vec<Row>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
}

/// A heading level: 1 to 6, the range markdown defines.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(into = "u8", try_from = "u8")]
pub enum HeadingLevel {
    /// `#`
    H1,
    /// `##`
    H2,
    /// `###`
    H3,
    /// `####`
    H4,
    /// `#####`
    H5,
    /// `######`
    H6,
}

impl From<HeadingLevel> for u8 {
    fn from(level: HeadingLevel) -> u8 {
        match level {
            HeadingLevel::H1 => 1,
            HeadingLevel::H2 => 2,
            HeadingLevel::H3 => 3,
            HeadingLevel::H4 => 4,
            HeadingLevel::H5 => 5,
            HeadingLevel::H6 => 6,
        }
    }
}

impl TryFrom<u8> for HeadingLevel {
    type Error = InvalidHeadingLevel;

    fn try_from(value: u8) -> Result<Self, Self::Error> {
        match value {
            1 => Ok(HeadingLevel::H1),
            2 => Ok(HeadingLevel::H2),
            3 => Ok(HeadingLevel::H3),
            4 => Ok(HeadingLevel::H4),
            5 => Ok(HeadingLevel::H5),
            6 => Ok(HeadingLevel::H6),
            _ => Err(InvalidHeadingLevel(value)),
        }
    }
}

/// A heading level outside 1–6, with the offending value.
#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
#[error("heading level must be 1-6, got {0}")]
pub struct InvalidHeadingLevel(pub u8);

/// What a numbered list counts from when the source names no start.
fn first_number() -> u32 {
    1
}

fn is_first_number(start: &u32) -> bool {
    *start == 1
}

/// One item of a list.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct ListItem {
    /// Engine-assigned identity, for diagnostics; never serialized.
    #[serde(skip)]
    pub id: NodeId,
    /// The item's content, in reading order. An empty item has none.
    #[serde(default)]
    pub blocks: Vec<Block>,
    /// What a sheet names it by.
    #[serde(default, skip_serializing_if = "Attributes::is_empty")]
    pub attributes: Attributes,
    /// Where the frontend read this from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub position: Option<SourcePos>,
    /// The bytes of that source it was read from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub span: Option<SourceSpan>,
}

/// The blocks of every item of a list, in reading order.
pub fn item_blocks(items: &[ListItem]) -> impl Iterator<Item = &[Block]> {
    items.iter().map(|item| item.blocks.as_slice())
}

/// One row of a table.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Row {
    /// Engine-assigned identity, for diagnostics; never serialized.
    #[serde(skip)]
    pub id: NodeId,
    /// The row's cells, from the leading edge. A row with fewer cells
    /// than the table has columns leaves the rest of them empty.
    #[serde(default)]
    pub cells: Vec<Cell>,
    /// What a sheet names it by.
    #[serde(default, skip_serializing_if = "Attributes::is_empty")]
    pub attributes: Attributes,
    /// Where the frontend read this from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub position: Option<SourcePos>,
    /// The bytes of that source it was read from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub span: Option<SourceSpan>,
}

/// One cell of a table row.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Cell {
    /// Engine-assigned identity, for diagnostics; never serialized.
    #[serde(skip)]
    pub id: NodeId,
    /// The cell's content, in reading order. An empty cell has none.
    #[serde(default)]
    pub blocks: Vec<Block>,
    /// The alignment the source wrote on the cell's column, if it
    /// wrote one.
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub align: Option<Alignment>,
    /// What a sheet names it by.
    #[serde(default, skip_serializing_if = "Attributes::is_empty")]
    pub attributes: Attributes,
    /// Where the frontend read this from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub position: Option<SourcePos>,
    /// The bytes of that source it was read from.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub span: Option<SourceSpan>,
}

/// The alignment a table's delimiter row writes on a column.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Alignment {
    /// `:---`
    Left,
    /// `:---:`
    Center,
    /// `---:`
    Right,
}

/// Every row of a table, the header rows first.
pub fn rows<'a>(head: &'a [Row], body: &'a [Row]) -> impl Iterator<Item = &'a Row> {
    head.iter().chain(body)
}

/// The blocks of every cell of a table, row by row, the header rows
/// first.
pub fn cell_blocks<'a>(head: &'a [Row], body: &'a [Row]) -> impl Iterator<Item = &'a [Block]> {
    rows(head, body).flat_map(|row| row.cells.iter().map(|cell| cell.blocks.as_slice()))
}

/// An inline element: participates in line layout.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(tag = "type", rename_all = "snake_case")]
pub enum Inline {
    /// A run of text. The frontend has already decoded entities; the
    /// engine sees plain Unicode.
    Text {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The characters themselves, entities already decoded.
        value: String,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A hard line break: the line ends here, and what follows stays
    /// in the same block. It holds no text.
    Break {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `*emphasis*`: italic, in the default sheet.
    Emphasis {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The emphasised inlines.
        children: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `**strong**`: bold, in the default sheet.
    Strong {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The strengthened inlines.
        children: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `` `code` ``: monospace, and never hyphenated.
    Code {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The literal code text; no markup inside.
        value: String,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A hyperlink. The text lays out; the url is for painters that can
    /// express one.
    Link {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The link target.
        url: String,
        /// The linked inlines.
        children: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A footnote. Its reference sits in the line where it was
    /// written, and its blocks are set at the foot of the page that
    /// reference lands on.
    ///
    /// The blocks are the note itself, so a note holds paragraphs,
    /// lists and everything else a blockquote holds. The engine sets
    /// the reference and the number beside the note from the
    /// cascade, so neither is in the tree.
    Note {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The note itself, in reading order.
        blocks: Vec<Block>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// `~~struck~~`: a line through it, in the default sheet.
    Strikethrough {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The struck inlines.
        children: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
    /// A run the sheet names, and nothing else. It carries no meaning
    /// of its own, so the built-in sheet styles it like the text
    /// around it and a class on it is what reaches it.
    Span {
        /// Engine-assigned identity, for diagnostics; never serialized.
        #[serde(skip)]
        id: NodeId,
        /// The inlines inside the run.
        children: Vec<Inline>,
        /// What a sheet names it by.
        #[serde(default, skip_serializing_if = "Attributes::is_empty")]
        attributes: Attributes,
        /// Where the frontend read this from.
        #[serde(skip_serializing_if = "Option::is_none")]
        position: Option<SourcePos>,
        /// The bytes of that source it was read from.
        #[serde(skip_serializing_if = "Option::is_none")]
        span: Option<SourceSpan>,
    },
}

/// The text of an inline tree, markup discarded: every inline run
/// together and a hard break as a newline, as `content()` reads an
/// element and as a frontend reads alt text.
pub fn text(inlines: &[Inline]) -> String {
    let mut out = String::new();
    push_text(inlines, &mut out);
    out
}

fn push_text(inlines: &[Inline], out: &mut String) {
    for inline in inlines {
        match inline {
            Inline::Text { value, .. } | Inline::Code { value, .. } => out.push_str(value),
            Inline::Break { .. } => out.push('\n'),
            // A note is set at the foot of the page, so its prose is
            // no part of the text the line it was written in holds.
            Inline::Note { .. } => {}
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => push_text(children, out),
        }
    }
}

impl Book {
    /// Assign ids to every node, in document order (pre-order: a node
    /// before its children, sections in reading order), starting at 1.
    /// Runs once, after deserialization; running it again renumbers.
    pub fn assign_node_ids(&mut self) {
        let mut next = 1u32;
        for section in &mut self.sections {
            section.id = next_id(&mut next);
            for block in &mut section.blocks {
                assign_block(block, &mut next);
            }
        }
    }

    /// The node one byte of one source was read into: the innermost,
    /// so a byte of prose answers with the run it was typed into and
    /// a byte of markup answers with the construct it opens.
    ///
    /// Only sections read from that source are looked at, so one
    /// file's cursor is answered by one file's nodes. Nothing for a
    /// byte no node was read from, such as a blank line between
    /// chapters or a source's frontmatter, and nothing for a tree
    /// built rather than parsed.
    pub fn node_at(&self, source: &str, byte: u32) -> Option<NodeId> {
        self.sections
            .iter()
            .filter(|section| section.source.as_deref() == Some(source))
            .find_map(|section| {
                let span = section.span.filter(|span| span.covers(byte))?;
                let inner = node_in_blocks(&section.blocks, byte);
                let inner = match node_in_notes(&section.blocks, byte) {
                    Some(note) => Some(narrowest(note, inner)),
                    None => inner,
                };
                Some(narrowest((section.id, span), inner))
            })
            .map(|(node, _)| node)
    }

    /// The source a node was read from, and the bytes of it the node
    /// covers.
    ///
    /// Nothing for a node the engine synthesized, or one from a tree
    /// built rather than parsed: neither was read from anything.
    pub fn source_of(&self, node: NodeId) -> Option<(&str, SourceSpan)> {
        if node == NodeId::UNASSIGNED {
            return None;
        }
        // A section's nodes are dense and in document order from the
        // section's own id, so the section holding a node is the last
        // one numbered at or before it.
        let at = self
            .sections
            .partition_point(|section| section.id.get() <= node.get())
            .checked_sub(1)?;
        let section = &self.sections[at];
        let source = section.source.as_deref()?;
        let span = if section.id == node {
            section.span?
        } else {
            span_in_blocks(&section.blocks, node)?
        };
        Some((source, span))
    }

    /// The classes and the ids the blocks and inlines of one source
    /// carry, or of every source when `source` is `None`. A list
    /// item, a table row or cell, and a note count as blocks and
    /// inlines here.
    ///
    /// A section's own names are not in the answer. A host sets them
    /// beside the source, or frontmatter writes them.
    pub fn names(&self, source: Option<&str>) -> Names {
        let mut classes = std::collections::BTreeSet::new();
        let mut ids = std::collections::BTreeSet::new();
        let mut add = |attributes: &Attributes| {
            classes.extend(attributes.classes.iter().cloned());
            ids.extend(attributes.id.iter().cloned());
        };
        for section in &self.sections {
            if source.is_none_or(|source| section.source.as_deref() == Some(source)) {
                names_in_blocks(&section.blocks, &mut add);
            }
        }
        Names {
            classes: classes.into_iter().collect(),
            ids: ids.into_iter().collect(),
        }
    }

    /// The ids one node and its descendants hold.
    ///
    /// Ids are assigned in document order, a node before its
    /// children, so what a node covers is a run of consecutive
    /// numbers. Asking what a node was set from is asking about
    /// every id in this range.
    ///
    /// Nothing for a node the book does not hold.
    pub fn subtree(&self, node: NodeId) -> Option<Range<u32>> {
        if node == NodeId::UNASSIGNED {
            return None;
        }
        let at = self
            .sections
            .partition_point(|section| section.id.get() <= node.get())
            .checked_sub(1)?;
        let section = &self.sections[at];
        let first = section.id.get();
        let count = 1 + section.blocks.iter().map(block_nodes).sum::<u32>();
        if section.id == node {
            return Some(first..first + count);
        }
        if !(first..first + count).contains(&node.get()) {
            return None;
        }
        subtree_in_blocks(&section.blocks, node)
    }
}

/// Hands the names of every block and inline under these blocks to
/// `add`.
fn names_in_blocks(blocks: &[Block], add: &mut impl FnMut(&Attributes)) {
    for block in blocks {
        add(block_attributes(block));
        match block {
            Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
                names_in_inlines(inlines, add)
            }
            Block::Blockquote { blocks, .. } => names_in_blocks(blocks, add),
            Block::List { items, .. } => {
                for item in items {
                    add(&item.attributes);
                    names_in_blocks(&item.blocks, add);
                }
            }
            Block::Table { head, body, .. } => {
                for row in rows(head, body) {
                    add(&row.attributes);
                    for cell in &row.cells {
                        add(&cell.attributes);
                        names_in_blocks(&cell.blocks, add);
                    }
                }
            }
            Block::CodeBlock { .. }
            | Block::ThematicBreak { .. }
            | Block::PageBreak { .. }
            | Block::ColumnBreak { .. }
            | Block::Image { .. } => {}
        }
    }
}

/// The same, over inlines.
fn names_in_inlines(inlines: &[Inline], add: &mut impl FnMut(&Attributes)) {
    for inline in inlines {
        add(inline_attributes(inline));
        match inline {
            Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => {}
            Inline::Note { blocks, .. } => names_in_blocks(blocks, add),
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => names_in_inlines(children, add),
        }
    }
}

/// The ids one node of these blocks holds, by id. Ids are dense, so
/// the block holding a node is the one whose own run of numbers
/// covers it.
fn subtree_in_blocks(blocks: &[Block], node: NodeId) -> Option<Range<u32>> {
    for block in blocks {
        let first = block_id(block).get();
        let held = first..first + block_nodes(block);
        if !held.contains(&node.get()) {
            continue;
        }
        if block_id(block) == node {
            return Some(held);
        }
        return match block {
            Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
                subtree_in_inlines(inlines, node)
            }
            Block::Blockquote { blocks, .. } => subtree_in_blocks(blocks, node),
            Block::List { items, .. } => subtree_in_items(items, node),
            Block::Table { head, body, .. } => subtree_in_rows(rows(head, body), node),
            Block::CodeBlock { .. }
            | Block::ThematicBreak { .. }
            | Block::PageBreak { .. }
            | Block::ColumnBreak { .. }
            | Block::Image { .. } => None,
        };
    }
    None
}

/// The same, over the items of one list.
fn subtree_in_items(items: &[ListItem], node: NodeId) -> Option<Range<u32>> {
    let item = items
        .iter()
        .find(|item| (item.id.get()..item.id.get() + item_nodes(item)).contains(&node.get()))?;
    if item.id == node {
        return Some(item.id.get()..item.id.get() + item_nodes(item));
    }
    subtree_in_blocks(&item.blocks, node)
}

/// How many ids one list item holds, itself included.
fn item_nodes(item: &ListItem) -> u32 {
    1 + item.blocks.iter().map(block_nodes).sum::<u32>()
}

/// The same, over the inlines of one block.
fn subtree_in_inlines(inlines: &[Inline], node: NodeId) -> Option<Range<u32>> {
    for inline in inlines {
        let first = inline_id(inline).get();
        let held = first..first + inline_nodes(inline);
        if !held.contains(&node.get()) {
            continue;
        }
        if inline_id(inline) == node {
            return Some(held);
        }
        return match inline {
            Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => None,
            Inline::Note { blocks, .. } => subtree_in_blocks(blocks, node),
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => subtree_in_inlines(children, node),
        };
    }
    None
}

/// How many ids one block holds, itself included.
fn block_nodes(block: &Block) -> u32 {
    1 + match block {
        Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
            inlines.iter().map(inline_nodes).sum()
        }
        Block::Blockquote { blocks, .. } => blocks.iter().map(block_nodes).sum(),
        Block::List { items, .. } => items.iter().map(item_nodes).sum(),
        Block::Table { head, body, .. } => rows(head, body).map(row_nodes).sum(),
        Block::CodeBlock { .. }
        | Block::ThematicBreak { .. }
        | Block::PageBreak { .. }
        | Block::ColumnBreak { .. }
        | Block::Image { .. } => 0,
    }
}

/// The same, for one row of a table.
fn row_nodes(row: &Row) -> u32 {
    1 + row.cells.iter().map(cell_nodes).sum::<u32>()
}

/// The same, for one cell.
fn cell_nodes(cell: &Cell) -> u32 {
    1 + cell.blocks.iter().map(block_nodes).sum::<u32>()
}

/// The ids one node of a table's rows holds, by id.
fn subtree_in_rows<'a>(rows: impl Iterator<Item = &'a Row>, node: NodeId) -> Option<Range<u32>> {
    for row in rows {
        let held = row.id.get()..row.id.get() + row_nodes(row);
        if !held.contains(&node.get()) {
            continue;
        }
        if row.id == node {
            return Some(held);
        }
        for cell in &row.cells {
            let held = cell.id.get()..cell.id.get() + cell_nodes(cell);
            if !held.contains(&node.get()) {
                continue;
            }
            if cell.id == node {
                return Some(held);
            }
            return subtree_in_blocks(&cell.blocks, node);
        }
        return None;
    }
    None
}

/// The same, for one inline.
pub(crate) fn inline_nodes(inline: &Inline) -> u32 {
    1 + match inline {
        Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => 0,
        Inline::Note { blocks, .. } => blocks.iter().map(block_nodes).sum(),
        Inline::Emphasis { children, .. }
        | Inline::Strong { children, .. }
        | Inline::Link { children, .. }
        | Inline::Strikethrough { children, .. }
        | Inline::Span { children, .. } => children.iter().map(inline_nodes).sum(),
    }
}

/// The narrower of a node and whichever of its descendants was read
/// from the same byte.
fn narrowest(
    node: (NodeId, SourceSpan),
    inner: Option<(NodeId, SourceSpan)>,
) -> (NodeId, SourceSpan) {
    match inner {
        Some(inner) if inner.1.width() <= node.1.width() => inner,
        _ => node,
    }
}

/// The innermost block or inline of these blocks a byte was read
/// into. Blocks are in source order, so a block starting past the
/// byte ends the search; an image written among prose is the one that
/// starts inside the paragraph it was moved out of, which is why the
/// narrowest span wins rather than the first.
fn node_in_blocks(blocks: &[Block], byte: u32) -> Option<(NodeId, SourceSpan)> {
    let mut found: Option<(NodeId, SourceSpan)> = None;
    for block in blocks {
        let Some(span) = block_span(block) else {
            continue;
        };
        if span.start > byte {
            break;
        }
        if !span.covers(byte) {
            continue;
        }
        let inner = match block {
            Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
                node_in_inlines(inlines, byte)
            }
            Block::Blockquote { blocks, .. } => node_in_blocks(blocks, byte),
            Block::List { items, .. } => node_in_items(items, byte),
            Block::Table { head, body, .. } => node_in_rows(rows(head, body), byte),
            Block::CodeBlock { .. }
            | Block::ThematicBreak { .. }
            | Block::PageBreak { .. }
            | Block::ColumnBreak { .. }
            | Block::Image { .. } => None,
        };
        let hit = narrowest((block_id(block), span), inner);
        if found.is_none_or(|found| hit.1.width() < found.1.width()) {
            found = Some(hit);
        }
    }
    found
}

/// The same, over the inlines of one block.
fn node_in_inlines(inlines: &[Inline], byte: u32) -> Option<(NodeId, SourceSpan)> {
    for inline in inlines {
        let Some(span) = inline_span(inline) else {
            continue;
        };
        if span.start > byte {
            break;
        }
        if !span.covers(byte) {
            continue;
        }
        let inner = match inline {
            // A note was written where its definition was, which is
            // not the stretch its reference covers. `node_in_notes`
            // answers for those bytes.
            Inline::Text { .. }
            | Inline::Code { .. }
            | Inline::Break { .. }
            | Inline::Note { .. } => None,
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => node_in_inlines(children, byte),
        };
        return Some(narrowest((inline_id(inline), span), inner));
    }
    None
}

/// Every note written among these blocks, in reading order. A note
/// written inside another note comes after it.
pub fn notes_in_blocks(blocks: &[Block]) -> Vec<&Inline> {
    let mut out = Vec::new();
    gather_notes_in_blocks(blocks, &mut out);
    out
}

/// The notes written directly among these inlines, in reading order.
/// A note written inside another note is that note's own.
pub fn notes_in_inlines(inlines: &[Inline]) -> Vec<&Inline> {
    let mut out = Vec::new();
    shallow_notes_in_inlines(inlines, &mut out);
    out
}

fn shallow_notes_in_inlines<'b>(inlines: &'b [Inline], out: &mut Vec<&'b Inline>) {
    for inline in inlines {
        match inline {
            Inline::Note { .. } => out.push(inline),
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => shallow_notes_in_inlines(children, out),
            Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => {}
        }
    }
}

fn gather_notes_in_blocks<'b>(blocks: &'b [Block], out: &mut Vec<&'b Inline>) {
    for block in blocks {
        match block {
            Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
                gather_notes_in_inlines(inlines, out)
            }
            Block::Blockquote { blocks, .. } => gather_notes_in_blocks(blocks, out),
            Block::List { items, .. } => {
                for item in items {
                    gather_notes_in_blocks(&item.blocks, out);
                }
            }
            Block::Table { head, body, .. } => {
                for blocks in cell_blocks(head, body) {
                    gather_notes_in_blocks(blocks, out);
                }
            }
            Block::CodeBlock { .. }
            | Block::ThematicBreak { .. }
            | Block::PageBreak { .. }
            | Block::ColumnBreak { .. }
            | Block::Image { .. } => {}
        }
    }
}

fn gather_notes_in_inlines<'b>(inlines: &'b [Inline], out: &mut Vec<&'b Inline>) {
    for inline in inlines {
        match inline {
            Inline::Note { blocks, .. } => {
                out.push(inline);
                gather_notes_in_blocks(blocks, out);
            }
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => gather_notes_in_inlines(children, out),
            Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => {}
        }
    }
}

/// The innermost node of the notes written among these blocks a
/// byte was read into.
///
/// A note sits in the line its reference was written on, and its own
/// blocks were read from wherever the note was written. So the bytes
/// of a note are outside the span of every node that holds it, and
/// the search for them starts again here.
fn node_in_notes(blocks: &[Block], byte: u32) -> Option<(NodeId, SourceSpan)> {
    let mut found: Option<(NodeId, SourceSpan)> = None;
    for note in notes_in_blocks(blocks) {
        let Inline::Note { id, blocks, .. } = note else {
            continue;
        };
        let Some(hit) = node_in_blocks(blocks, byte) else {
            continue;
        };
        let hit = match inline_span(note) {
            Some(span) if span.covers(byte) => narrowest((*id, span), Some(hit)),
            _ => hit,
        };
        if found.is_none_or(|found| hit.1.width() < found.1.width()) {
            found = Some(hit);
        }
    }
    found
}

/// The span of one node of these blocks, by id.
fn span_in_blocks(blocks: &[Block], node: NodeId) -> Option<SourceSpan> {
    for block in blocks {
        if block_id(block) == node {
            return block_span(block);
        }
        let found = match block {
            Block::Heading { inlines, .. } | Block::Paragraph { inlines, .. } => {
                span_in_inlines(inlines, node)
            }
            Block::Blockquote { blocks, .. } => span_in_blocks(blocks, node),
            Block::List { items, .. } => span_in_items(items, node),
            Block::Table { head, body, .. } => span_in_rows(rows(head, body), node),
            Block::CodeBlock { .. }
            | Block::ThematicBreak { .. }
            | Block::PageBreak { .. }
            | Block::ColumnBreak { .. }
            | Block::Image { .. } => None,
        };
        if found.is_some() {
            return found;
        }
    }
    None
}

/// The innermost item, block or inline of a list a byte was read
/// into.
fn node_in_items(items: &[ListItem], byte: u32) -> Option<(NodeId, SourceSpan)> {
    items.iter().find_map(|item| {
        let span = item.span.filter(|span| span.covers(byte))?;
        Some(narrowest(
            (item.id, span),
            node_in_blocks(&item.blocks, byte),
        ))
    })
}

/// The span of one node of a list's items, by id.
fn span_in_items(items: &[ListItem], node: NodeId) -> Option<SourceSpan> {
    items.iter().find_map(|item| {
        if item.id == node {
            item.span
        } else {
            span_in_blocks(&item.blocks, node)
        }
    })
}

/// The same, over the inlines of one block.
fn span_in_inlines(inlines: &[Inline], node: NodeId) -> Option<SourceSpan> {
    for inline in inlines {
        if inline_id(inline) == node {
            return inline_span(inline);
        }
        let found = match inline {
            Inline::Text { .. } | Inline::Code { .. } | Inline::Break { .. } => None,
            Inline::Note { blocks, .. } => span_in_blocks(blocks, node),
            Inline::Emphasis { children, .. }
            | Inline::Strong { children, .. }
            | Inline::Link { children, .. }
            | Inline::Strikethrough { children, .. }
            | Inline::Span { children, .. } => span_in_inlines(children, node),
        };
        if found.is_some() {
            return found;
        }
    }
    None
}

/// The innermost row, cell, block or inline of a table's rows a byte
/// was read into.
fn node_in_rows<'a>(
    rows: impl Iterator<Item = &'a Row>,
    byte: u32,
) -> Option<(NodeId, SourceSpan)> {
    for row in rows {
        let Some(span) = row.span.filter(|span| span.covers(byte)) else {
            continue;
        };
        let inner = row.cells.iter().find_map(|cell| {
            let span = cell.span.filter(|span| span.covers(byte))?;
            Some(narrowest(
                (cell.id, span),
                node_in_blocks(&cell.blocks, byte),
            ))
        });
        return Some(narrowest((row.id, span), inner));
    }
    None
}

/// The span of one node of a table's rows, by id.
fn span_in_rows<'a>(rows: impl Iterator<Item = &'a Row>, node: NodeId) -> Option<SourceSpan> {
    for row in rows {
        if row.id == node {
            return row.span;
        }
        for cell in &row.cells {
            if cell.id == node {
                return cell.span;
            }
            let found = span_in_blocks(&cell.blocks, node);
            if found.is_some() {
                return found;
            }
        }
    }
    None
}

/// What a sheet names one block by.
pub fn block_attributes(block: &Block) -> &Attributes {
    match block {
        Block::Heading { attributes, .. }
        | Block::Paragraph { attributes, .. }
        | Block::Blockquote { attributes, .. }
        | Block::ThematicBreak { attributes, .. }
        | Block::PageBreak { attributes, .. }
        | Block::ColumnBreak { attributes, .. }
        | Block::Image { attributes, .. }
        | Block::List { attributes, .. }
        | Block::CodeBlock { attributes, .. }
        | Block::Table { attributes, .. } => attributes,
    }
}

/// The same, for one inline.
pub fn inline_attributes(inline: &Inline) -> &Attributes {
    match inline {
        Inline::Text { attributes, .. }
        | Inline::Code { attributes, .. }
        | Inline::Break { attributes, .. }
        | Inline::Emphasis { attributes, .. }
        | Inline::Strong { attributes, .. }
        | Inline::Link { attributes, .. }
        | Inline::Note { attributes, .. }
        | Inline::Strikethrough { attributes, .. }
        | Inline::Span { attributes, .. } => attributes,
    }
}

/// Where in its source one block was read from.
pub fn block_position(block: &Block) -> Option<SourcePos> {
    match block {
        Block::Heading { position, .. }
        | Block::Paragraph { position, .. }
        | Block::Blockquote { position, .. }
        | Block::ThematicBreak { position, .. }
        | Block::PageBreak { position, .. }
        | Block::ColumnBreak { position, .. }
        | Block::Image { position, .. }
        | Block::List { position, .. }
        | Block::CodeBlock { position, .. }
        | Block::Table { position, .. } => *position,
    }
}

/// The same, for one inline.
pub fn inline_position(inline: &Inline) -> Option<SourcePos> {
    match inline {
        Inline::Text { position, .. }
        | Inline::Code { position, .. }
        | Inline::Break { position, .. }
        | Inline::Emphasis { position, .. }
        | Inline::Strong { position, .. }
        | Inline::Link { position, .. }
        | Inline::Note { position, .. }
        | Inline::Strikethrough { position, .. }
        | Inline::Span { position, .. } => *position,
    }
}

/// One block's identity.
pub fn block_id(block: &Block) -> NodeId {
    match block {
        Block::Heading { id, .. }
        | Block::Paragraph { id, .. }
        | Block::Blockquote { id, .. }
        | Block::ThematicBreak { id, .. }
        | Block::PageBreak { id, .. }
        | Block::ColumnBreak { id, .. }
        | Block::Image { id, .. }
        | Block::List { id, .. }
        | Block::CodeBlock { id, .. }
        | Block::Table { id, .. } => *id,
    }
}

/// The bytes of its source one block was read from.
pub fn block_span(block: &Block) -> Option<SourceSpan> {
    match block {
        Block::Heading { span, .. }
        | Block::Paragraph { span, .. }
        | Block::Blockquote { span, .. }
        | Block::ThematicBreak { span, .. }
        | Block::PageBreak { span, .. }
        | Block::ColumnBreak { span, .. }
        | Block::Image { span, .. }
        | Block::List { span, .. }
        | Block::CodeBlock { span, .. }
        | Block::Table { span, .. } => *span,
    }
}

/// One inline's identity.
pub fn inline_id(inline: &Inline) -> NodeId {
    match inline {
        Inline::Text { id, .. }
        | Inline::Code { id, .. }
        | Inline::Break { id, .. }
        | Inline::Emphasis { id, .. }
        | Inline::Strong { id, .. }
        | Inline::Link { id, .. }
        | Inline::Note { id, .. }
        | Inline::Strikethrough { id, .. }
        | Inline::Span { id, .. } => *id,
    }
}

/// The bytes of its source one inline was read from.
pub fn inline_span(inline: &Inline) -> Option<SourceSpan> {
    match inline {
        Inline::Text { span, .. }
        | Inline::Code { span, .. }
        | Inline::Break { span, .. }
        | Inline::Emphasis { span, .. }
        | Inline::Strong { span, .. }
        | Inline::Link { span, .. }
        | Inline::Note { span, .. }
        | Inline::Strikethrough { span, .. }
        | Inline::Span { span, .. } => *span,
    }
}

fn next_id(next: &mut u32) -> NodeId {
    let id = NodeId(*next);
    *next += 1;
    id
}

fn assign_block(block: &mut Block, next: &mut u32) {
    match block {
        Block::Heading { id, inlines, .. } | Block::Paragraph { id, inlines, .. } => {
            *id = next_id(next);
            for inline in inlines {
                assign_inline(inline, next);
            }
        }
        Block::Blockquote { id, blocks, .. } => {
            *id = next_id(next);
            for nested in blocks {
                assign_block(nested, next);
            }
        }
        Block::CodeBlock { id, .. }
        | Block::ThematicBreak { id, .. }
        | Block::PageBreak { id, .. }
        | Block::ColumnBreak { id, .. }
        | Block::Image { id, .. } => {
            *id = next_id(next);
        }
        Block::List { id, items, .. } => {
            *id = next_id(next);
            for item in items {
                item.id = next_id(next);
                for nested in &mut item.blocks {
                    assign_block(nested, next);
                }
            }
        }
        Block::Table { id, head, body, .. } => {
            *id = next_id(next);
            for row in head.iter_mut().chain(body.iter_mut()) {
                row.id = next_id(next);
                for cell in &mut row.cells {
                    cell.id = next_id(next);
                    for nested in &mut cell.blocks {
                        assign_block(nested, next);
                    }
                }
            }
        }
    }
}

fn assign_inline(inline: &mut Inline, next: &mut u32) {
    match inline {
        Inline::Text { id, .. } | Inline::Code { id, .. } | Inline::Break { id, .. } => {
            *id = next_id(next);
        }
        Inline::Note { id, blocks, .. } => {
            *id = next_id(next);
            for block in blocks {
                assign_block(block, next);
            }
        }
        Inline::Emphasis { id, children, .. }
        | Inline::Strong { id, children, .. }
        | Inline::Link { id, children, .. }
        | Inline::Strikethrough { id, children, .. }
        | Inline::Span { id, children, .. } => {
            *id = next_id(next);
            for child in children {
                assign_inline(child, next);
            }
        }
    }
}

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

    /// Part: `NodeId::element` still maps a pseudo-element id to its
    /// element. A renumbered section moves the id with its element,
    /// and the id stays one no content node has.
    #[test]
    fn a_pseudo_element_maps_to_its_element_and_moves_with_it() {
        let element = NodeId::new(40);
        let kinds = [
            PseudoElement::Before,
            PseudoElement::After,
            PseudoElement::FirstLetter,
            PseudoElement::FirstLine,
        ];
        let ids: Vec<NodeId> = kinds.iter().map(|which| element.pseudo(*which)).collect();
        for (id, which) in ids.iter().zip(kinds) {
            assert_eq!(id.pseudo_element(), Some((element, which)));
            assert_eq!(id.element(), element);
            assert!(id.get() >= 1 << 31, "{id:?} is in the range of content ids");
            assert_eq!(
                id.shifted(-3).pseudo_element(),
                Some((NodeId::new(37), which))
            );
            assert_eq!(ids.iter().filter(|other| *other == id).count(), 1);
        }
        assert_eq!(element.pseudo_element(), None);
        assert_eq!(element.element(), element);
        assert_eq!(element.shifted(-3).pseudo_element(), None);
    }

    /// The markdown the sample tree was read from, so that its spans
    /// are the bytes of something rather than numbers made up.
    const SOURCE: &str = "\
# Chapter One

It was the kind of morning that made you suspicious — too *clean*, too quiet.

> \"Nobody's early here.\"

---

![The drawer of knives](images/drawer.png)

1. A watch
2. A purse

| Pocket | Found |
|:---|---:|
| Right | A handkerchief |
";

    /// The bytes of the sample source one stretch of it covers.
    fn span(of: &str) -> Option<SourceSpan> {
        let start = SOURCE.find(of).expect("the sample source has it");
        Some(SourceSpan {
            start: start as u32,
            end: (start + of.len()) as u32,
        })
    }

    /// Test-local shorthand: an unassigned text run, spanning the
    /// bytes of the source it reads as.
    fn text(value: &str) -> Inline {
        Inline::Text {
            id: NodeId::UNASSIGNED,
            value: value.into(),
            attributes: Attributes::default(),
            position: None,
            span: span(value),
        }
    }

    /// An item of the sample list: one paragraph of one run, the item
    /// spanning the line it was written on.
    fn item(line: &str, value: &str) -> ListItem {
        ListItem {
            blocks: vec![Block::Paragraph {
                id: NodeId::UNASSIGNED,
                inlines: vec![text(value)],
                attributes: Attributes::default(),
                position: None,
                span: span(value),
            }],
            span: span(line),
            ..ListItem::default()
        }
    }

    /// A list serializes as its items and each item as its blocks. A
    /// list that counts from one leaves `start` out.
    #[test]
    fn a_list_serializes_as_items_of_blocks() {
        let list = sample_book().sections[0].blocks[5].clone();
        let json = serde_json::to_value(&list).unwrap();
        assert_eq!(json["type"], "list");
        assert_eq!(json["ordered"], true);
        assert_eq!(json["tight"], true);
        assert!(json.get("start").is_none(), "{json}");
        assert_eq!(
            json["items"][1]["blocks"][0]["inlines"][0]["value"],
            "A purse"
        );

        let Block::List {
            ordered,
            tight,
            items,
            attributes,
            position,
            span,
            ..
        } = list
        else {
            panic!("the sixth block is a list");
        };
        let seventh = Block::List {
            id: NodeId::UNASSIGNED,
            ordered,
            start: 7,
            tight,
            items,
            attributes,
            position,
            span,
        };
        let json = serde_json::to_value(&seventh).unwrap();
        assert_eq!(json["start"], 7);
        let read: Block = serde_json::from_value(json).unwrap();
        assert_eq!(read, seventh);
    }

    /// A list is numbered like every other node: the list before its
    /// items, an item before what it holds. A byte of an item answers
    /// with the run typed into it, and a byte of its marker with the
    /// item.
    #[test]
    fn a_list_numbers_its_items_and_a_byte_of_one_answers_with_its_run() {
        let mut book = sample_book();
        book.assign_node_ids();
        let Block::List { id, items, .. } = &book.sections[0].blocks[5] else {
            panic!("the sixth block is a list");
        };
        assert!(*id < items[0].id);
        assert!(items[0].id < block_id(&items[0].blocks[0]));
        assert!(block_id(&items[0].blocks[0]) < items[1].id);
        let held = book.subtree(*id).expect("the book holds the list");
        assert!(held.contains(&block_id(&items[1].blocks[0]).get()));

        let Block::Paragraph { inlines, .. } = &items[1].blocks[0] else {
            panic!("the item holds a paragraph");
        };
        let byte = SOURCE.find("purse").unwrap() as u32;
        assert_eq!(
            book.node_at("chapter-01.md", byte),
            Some(inline_id(&inlines[0]))
        );
        let marker = SOURCE.find("2. A purse").unwrap() as u32;
        assert_eq!(book.node_at("chapter-01.md", marker), Some(items[1].id));
    }

    /// A row of the sample table, spanning the line it was written on.
    fn row(line: &str, cells: Vec<Cell>) -> Row {
        Row {
            cells,
            span: span(line),
            ..Row::default()
        }
    }

    /// A cell of the sample table: one paragraph of one run, under the
    /// alignment its column was written with.
    fn cell(value: &str, align: Alignment) -> Cell {
        Cell {
            blocks: vec![Block::Paragraph {
                id: NodeId::UNASSIGNED,
                inlines: vec![text(value)],
                attributes: Attributes::default(),
                position: None,
                span: span(value),
            }],
            align: Some(align),
            span: span(value),
            ..Cell::default()
        }
    }

    /// The sample book's table.
    fn table(book: &Book) -> (&[Row], &[Row]) {
        let Some(Block::Table { head, body, .. }) = book.sections[0].blocks.last() else {
            panic!("the sample book ends with a table");
        };
        (head, body)
    }

    /// A table serializes as its rows, each row as its cells, and each
    /// cell as its blocks and the alignment its column was written
    /// with.
    #[test]
    fn a_table_serializes_as_rows_of_cells() {
        let json = serde_json::to_value(sample_book().sections[0].blocks.last()).unwrap();
        assert_eq!(json["type"], "table");
        assert_eq!(json["head"][0]["cells"][1]["align"], "right");
        assert_eq!(
            json["body"][0]["cells"][1]["blocks"][0],
            serde_json::json!({
                "type": "paragraph",
                "inlines": [{"type": "text", "value": "A handkerchief", "span": {
                    "start": SOURCE.find("A handkerchief").unwrap(),
                    "end": SOURCE.find("A handkerchief").unwrap() + "A handkerchief".len(),
                }}],
                "span": {
                    "start": SOURCE.find("A handkerchief").unwrap(),
                    "end": SOURCE.find("A handkerchief").unwrap() + "A handkerchief".len(),
                },
            }),
        );
    }

    /// A table is numbered like every other node: the table before its
    /// rows, a row before its cells, a cell before what it holds, and
    /// the header rows before the body rows.
    #[test]
    fn a_table_numbers_its_rows_and_cells_in_reading_order() {
        let mut book = sample_book();
        book.assign_node_ids();
        let table_id = block_id(book.sections[0].blocks.last().unwrap());
        let (head, body) = table(&book);
        let header = &head[0];
        let first = &body[0];
        assert!(table_id < header.id);
        assert!(header.id < header.cells[0].id);
        assert!(header.cells[0].id < block_id(&header.cells[0].blocks[0]));
        assert!(block_id(&header.cells[1].blocks[0]) < first.id);
        assert!(first.id < first.cells[1].id);

        // A row covers its cells, and a cell what is in it.
        let held = book.subtree(first.id).expect("the book holds the row");
        assert_eq!(held.start, first.id.get());
        assert!(held.contains(&block_id(&first.cells[1].blocks[0]).get()));
        assert_eq!(
            book.subtree(table_id).map(|held| held.end),
            book.subtree(book.sections[0].id).map(|held| held.end),
            "the table is the last node of the book",
        );
    }

    /// A byte of a cell answers with the run typed into it, and a
    /// byte of the pipes between two cells answers with the row.
    #[test]
    fn a_byte_of_a_cell_answers_with_the_run_written_there() {
        let mut book = sample_book();
        book.assign_node_ids();
        let (_, body) = table(&book);
        let Block::Paragraph { inlines, .. } = &body[0].cells[1].blocks[0] else {
            panic!("the cell holds a paragraph");
        };
        let byte = SOURCE.find("handkerchief").unwrap() as u32;
        assert_eq!(
            book.node_at("chapter-01.md", byte),
            Some(inline_id(&inlines[0]))
        );
        let pipe = SOURCE.find("| Right").unwrap() as u32;
        assert_eq!(book.node_at("chapter-01.md", pipe), Some(body[0].id));
    }

    /// What the engine writes, a host may hand back. The fields
    /// left out of the JSON when they are empty are the ones this
    /// catches: a book with no extras serializes without the map it
    /// then has to be readable without.
    #[test]
    fn a_tree_the_engine_wrote_reads_back() {
        for book in [sample_book(), Book::default()] {
            let json = serde_json::to_string(&book).unwrap();
            let read: Book = serde_json::from_str(&json).unwrap();
            assert_eq!(read, book, "{json}");
        }
    }

    fn sample_book() -> Book {
        Book {
            metadata: Metadata {
                title: Some("The Fixture Book".into()),
                author: Some("A. Author".into()),
                extra: [("language".to_string(), "en".to_string())]
                    .into_iter()
                    .collect(),
            },
            sections: vec![Section {
                attributes: Default::default(),
                id: NodeId::UNASSIGNED,
                source: Some("chapter-01.md".into()),
                title: Some("Chapter One".into()),
                blocks: vec![
                    Block::Heading {
                        id: NodeId::UNASSIGNED,
                        level: HeadingLevel::H1,
                        inlines: vec![text("Chapter One")],
                        attributes: Attributes::default(),
                        position: Some(SourcePos { line: 1, column: 1 }),
                        span: span("# Chapter One\n"),
                    },
                    Block::Paragraph {
                        id: NodeId::UNASSIGNED,
                        inlines: vec![
                            text("It was the kind of morning that made you suspicious — too "),
                            Inline::Emphasis {
                                id: NodeId::UNASSIGNED,
                                children: vec![text("clean")],
                                attributes: Attributes::default(),
                                position: None,
                                span: span("*clean*"),
                            },
                            text(", too quiet."),
                        ],
                        attributes: Attributes::default(),
                        position: Some(SourcePos { line: 3, column: 1 }),
                        span: span(
                            "It was the kind of morning that made you suspicious — too *clean*, too quiet.\n",
                        ),
                    },
                    Block::Blockquote {
                        id: NodeId::UNASSIGNED,
                        blocks: vec![Block::Paragraph {
                            id: NodeId::UNASSIGNED,
                            inlines: vec![text("\"Nobody's early here.\"")],
                            attributes: Attributes::default(),
                            position: None,
                            span: span("\"Nobody's early here.\"\n"),
                        }],
                        attributes: Attributes::default(),
                        position: Some(SourcePos { line: 5, column: 1 }),
                        span: span("> \"Nobody's early here.\"\n"),
                    },
                    Block::ThematicBreak {
                        id: NodeId::UNASSIGNED,
                        attributes: Attributes::default(),
                        position: Some(SourcePos { line: 7, column: 1 }),
                        span: span("---\n"),
                    },
                    Block::Image {
                        id: NodeId::UNASSIGNED,
                        url: "images/drawer.png".into(),
                        alt: "The drawer of knives".into(),
                        attributes: Attributes::default(),
                        position: Some(SourcePos { line: 9, column: 1 }),
                        span: span("![The drawer of knives](images/drawer.png)"),
                    },
                    Block::List {
                        id: NodeId::UNASSIGNED,
                        ordered: true,
                        start: 1,
                        tight: true,
                        items: vec![
                            item("1. A watch\n", "A watch"),
                            item("2. A purse\n", "A purse"),
                        ],
                        attributes: Attributes::default(),
                        position: Some(SourcePos {
                            line: 11,
                            column: 1,
                        }),
                        span: span("1. A watch\n2. A purse\n"),
                    },
                    Block::Table {
                        id: NodeId::UNASSIGNED,
                        head: vec![row(
                            "| Pocket | Found |\n",
                            vec![
                                cell("Pocket", Alignment::Left),
                                cell("Found", Alignment::Right),
                            ],
                        )],
                        body: vec![row(
                            "| Right | A handkerchief |\n",
                            vec![
                                cell("Right", Alignment::Left),
                                cell("A handkerchief", Alignment::Right),
                            ],
                        )],
                        attributes: Attributes::default(),
                        position: Some(SourcePos {
                            line: 14,
                            column: 1,
                        }),
                        span: span("| Pocket | Found |\n|:---|---:|\n| Right | A handkerchief |\n"),
                    },
                ],
                position: Some(SourcePos { line: 1, column: 1 }),
                span: Some(SourceSpan {
                    start: 0,
                    end: SOURCE.len() as u32,
                }),
            }],
        }
    }

    /// Every id in the tree, in walk order — the order assignment uses.
    fn collect_ids(book: &Book) -> Vec<NodeId> {
        fn walk_block(ids: &mut Vec<NodeId>, block: &Block) {
            match block {
                Block::Heading { id, inlines, .. } | Block::Paragraph { id, inlines, .. } => {
                    ids.push(*id);
                    ids.extend(inlines.iter().flat_map(walk_inline_ids));
                }
                Block::Blockquote { id, blocks, .. } => {
                    ids.push(*id);
                    for nested in blocks {
                        walk_block(ids, nested);
                    }
                }
                Block::CodeBlock { id, .. }
                | Block::ThematicBreak { id, .. }
                | Block::PageBreak { id, .. }
                | Block::ColumnBreak { id, .. }
                | Block::Image { id, .. } => ids.push(*id),
                Block::List { id, items, .. } => {
                    ids.push(*id);
                    for item in items {
                        ids.push(item.id);
                        for nested in &item.blocks {
                            walk_block(ids, nested);
                        }
                    }
                }
                Block::Table { id, head, body, .. } => {
                    ids.push(*id);
                    for row in rows(head, body) {
                        ids.push(row.id);
                        for cell in &row.cells {
                            ids.push(cell.id);
                            for nested in &cell.blocks {
                                walk_block(ids, nested);
                            }
                        }
                    }
                }
            }
        }

        fn walk_inline_ids(inline: &Inline) -> Vec<NodeId> {
            match inline {
                Inline::Text { id, .. } | Inline::Code { id, .. } | Inline::Break { id, .. } => {
                    vec![*id]
                }
                Inline::Note { id, blocks, .. } => {
                    let mut ids = vec![*id];
                    for block in blocks {
                        walk_block(&mut ids, block);
                    }
                    ids
                }
                Inline::Emphasis { id, children, .. }
                | Inline::Strong { id, children, .. }
                | Inline::Link { id, children, .. }
                | Inline::Strikethrough { id, children, .. }
                | Inline::Span { id, children, .. } => {
                    let mut ids = vec![*id];
                    ids.extend(children.iter().flat_map(walk_inline_ids));
                    ids
                }
            }
        }

        let mut ids = Vec::new();
        for section in &book.sections {
            ids.push(section.id);
            for block in &section.blocks {
                walk_block(&mut ids, block);
            }
        }
        ids
    }

    /// Two serializations of one tree are the same bytes: a dump is
    /// something to diff.
    #[test]
    fn serialization_is_stable() {
        let mut book = sample_book();
        book.assign_node_ids();
        let once = serde_json::to_string_pretty(&book).unwrap();
        assert_eq!(once, serde_json::to_string_pretty(&book).unwrap());
    }

    /// A serialized tree has no ids: the tree is authoritative,
    /// and identity is the engine's to hand out.
    #[test]
    fn ids_are_never_serialized() {
        let mut book = sample_book();
        book.assign_node_ids();
        let json = serde_json::to_string(&book).unwrap();
        assert!(!json.contains("\"id\""));
    }

    /// Tags are `type`, text runs are plain strings, and the shape
    /// maps onto mdast.
    #[test]
    fn a_serialized_tree_is_internally_tagged() {
        let block = Block::Paragraph {
            id: NodeId::UNASSIGNED,
            inlines: vec![
                Inline::Text {
                    id: NodeId::UNASSIGNED,
                    value: "plain ".into(),
                    attributes: Attributes::default(),
                    position: None,
                    span: None,
                },
                Inline::Strong {
                    id: NodeId::UNASSIGNED,
                    children: vec![Inline::Text {
                        id: NodeId::UNASSIGNED,
                        value: "bold".into(),
                        attributes: Attributes::default(),
                        position: None,
                        span: None,
                    }],
                    attributes: Attributes::default(),
                    position: None,
                    span: None,
                },
            ],
            attributes: Attributes::default(),
            position: Some(SourcePos { line: 4, column: 1 }),
            span: Some(SourceSpan { start: 40, end: 58 }),
        };
        assert_eq!(
            serde_json::to_value(&block).unwrap(),
            serde_json::json!({
                "type": "paragraph",
                "inlines": [
                    {"type": "text", "value": "plain "},
                    {"type": "strong", "children": [{"type": "text", "value": "bold"}]},
                ],
                "position": {"line": 4, "column": 1},
                "span": {"start": 40, "end": 58},
            }),
        );
    }

    /// A hard break is a node of its own, with no text in it. It
    /// serializes as its tag, reads back, and is a newline in the
    /// text of the inlines around it.
    #[test]
    fn a_hard_break_is_an_inline_of_its_own() {
        let words = |value: &str| Inline::Text {
            id: NodeId::UNASSIGNED,
            value: value.into(),
            attributes: Attributes::default(),
            position: None,
            span: None,
        };
        let inlines = vec![
            words("Chapter One"),
            Inline::Break {
                id: NodeId::UNASSIGNED,
                attributes: Attributes::default(),
                position: None,
                span: None,
            },
            words("The Voyage to Lilliput"),
        ];
        let json = serde_json::to_value(&inlines).unwrap();
        assert_eq!(json[1], serde_json::json!({"type": "break"}));
        let read: Vec<Inline> = serde_json::from_value(json).unwrap();
        assert_eq!(read, inlines);
        assert_eq!(super::text(&inlines), "Chapter One\nThe Voyage to Lilliput");
    }

    /// A heading level is 1-6, and a level outside that is rejected
    /// rather than clamped.
    #[test]
    fn heading_levels_run_one_to_six() {
        for level in 1..=6u8 {
            let heading = HeadingLevel::try_from(level).expect("1-6 is a heading level");
            assert_eq!(u8::from(heading), level);
        }
        for outside in [0u8, 7, 255] {
            assert_eq!(
                HeadingLevel::try_from(outside),
                Err(InvalidHeadingLevel(outside)),
            );
        }
    }

    /// Ids are dense (exactly `1..=n`), assigned pre-order, and the
    /// same on every assignment.
    #[test]
    fn node_ids_are_dense_pre_order_and_deterministic() {
        let mut book = sample_book();
        book.assign_node_ids();
        let ids = collect_ids(&book);

        // Dense from 1: same length, same set, no gaps.
        let mut sorted = ids.clone();
        sorted.sort_by_key(|id| id.get());
        sorted.dedup();
        assert_eq!(sorted.len(), ids.len());
        assert_eq!(sorted.first().unwrap().get(), 1);
        assert_eq!(sorted.last().unwrap().get(), ids.len() as u32);

        // Pre-order: the section precedes its first block, a block
        // precedes its first inline, an inline precedes its children.
        let section = book.sections[0].id;
        let Block::Heading { id: heading, .. } = &book.sections[0].blocks[0] else {
            panic!("fixture starts with a heading");
        };
        let Block::Paragraph {
            id: paragraph,
            inlines,
            ..
        } = &book.sections[0].blocks[1]
        else {
            panic!("second block is a paragraph");
        };
        assert!(section.get() < heading.get());
        assert!(heading.get() < paragraph.get());
        let Inline::Emphasis {
            id: emphasis,
            children,
            ..
        } = &inlines[1]
        else {
            panic!("second inline is emphasis");
        };
        let Inline::Text { id: child, .. } = &children[0] else {
            panic!("emphasis child is text");
        };
        assert!(paragraph.get() < emphasis.get());
        assert!(emphasis.get() < child.get());

        // Deterministic: a fresh assignment over the same tree is
        // byte-identical.
        let first = collect_ids(&book);
        book.assign_node_ids();
        assert_eq!(first, collect_ids(&book));
    }

    /// A byte of the source answers with the node written there, and
    /// the innermost one: the run inside the emphasis rather than the
    /// emphasis, the emphasis rather than the paragraph.
    #[test]
    fn a_byte_answers_with_the_innermost_node_written_there() {
        let mut book = sample_book();
        book.assign_node_ids();

        let letter = SOURCE.find("clean").unwrap() as u32;
        let Some(Inline::Emphasis {
            id: emphasis,
            children,
            ..
        }) = paragraph(&book).get(1)
        else {
            panic!("the sample paragraph holds an emphasis");
        };
        assert_eq!(
            book.node_at("chapter-01.md", letter),
            Some(inline_id(&children[0]))
        );
        // The asterisk is markup, which no run was shaped from, so it
        // answers with the construct it opens.
        assert_eq!(book.node_at("chapter-01.md", letter - 1), Some(*emphasis));
        // A byte between two blocks belongs to no node under the
        // section, and the section is what covers it.
        let blank = SOURCE.find("\n\n").unwrap() as u32 + 1;
        assert_eq!(
            book.node_at("chapter-01.md", blank),
            Some(book.sections[0].id)
        );
        assert_eq!(book.node_at("chapter-01.md", SOURCE.len() as u32), None);
    }

    /// A question about one source is answered by that source's
    /// nodes: the same byte of two files is two different nodes, and
    /// a file the book has never read answers with nothing.
    #[test]
    fn a_question_is_answered_from_one_source() {
        let mut book = sample_book();
        let mut second = book.sections[0].clone();
        second.source = Some("chapter-02.md".into());
        book.sections.push(second);
        book.assign_node_ids();

        let letter = SOURCE.find("clean").unwrap() as u32;
        let first = book
            .node_at("chapter-01.md", letter)
            .expect("the first chapter");
        let second = book.node_at("chapter-02.md", letter).expect("the second");
        assert_ne!(first, second);
        assert_eq!(
            book.source_of(first).map(|(name, _)| name),
            Some("chapter-01.md")
        );
        assert_eq!(
            book.source_of(second).map(|(name, _)| name),
            Some("chapter-02.md")
        );
        assert_eq!(book.node_at("chapter-03.md", letter), None);
    }

    /// Every node of a parsed tree says where it was read from, and
    /// the byte it starts at answers with that node again.
    #[test]
    fn a_node_taken_to_its_source_and_back_is_the_same_node() {
        let mut book = sample_book();
        book.assign_node_ids();

        for id in collect_ids(&book) {
            let (source, span) = book
                .source_of(id)
                .expect("a parsed node was read from a file");
            assert_eq!(source, "chapter-01.md");
            assert!(
                span.end as usize <= SOURCE.len(),
                "node {} covers {span:?}, which is past the source",
                id.get(),
            );
            let there = book
                .node_at(source, span.start)
                .expect("a node was read there");
            let (_, back) = book.source_of(there).expect("and it says so");
            assert_eq!(back.start, span.start, "node {} starts elsewhere", id.get());
        }
    }

    /// A tree built rather than parsed was read from nothing, and
    /// both questions say so rather than guessing.
    #[test]
    fn a_tree_built_rather_than_parsed_answers_with_nothing() {
        let mut book = Book {
            metadata: Metadata::default(),
            sections: vec![Section {
                attributes: Default::default(),
                source: Some("chapter-01.md".into()),
                blocks: vec![Block::Paragraph {
                    id: NodeId::UNASSIGNED,
                    inlines: vec![Inline::Text {
                        id: NodeId::UNASSIGNED,
                        value: "Built by hand.".into(),
                        attributes: Attributes::default(),
                        position: None,
                        span: None,
                    }],
                    attributes: Attributes::default(),
                    position: None,
                    span: None,
                }],
                ..Section::default()
            }],
        };
        book.assign_node_ids();

        assert_eq!(book.node_at("chapter-01.md", 0), None);
        for id in collect_ids(&book) {
            assert_eq!(
                book.source_of(id),
                None,
                "node {} was read from nothing",
                id.get()
            );
        }
        assert_eq!(book.source_of(NodeId::UNASSIGNED), None);
    }

    /// A node covers itself and everything under it, as one run of
    /// numbers: the section covers the book, the blockquote covers
    /// the paragraph quoted in it, and a text run covers only
    /// itself.
    #[test]
    fn a_subtree_is_a_run_of_ids() {
        let mut book = sample_book();
        book.assign_node_ids();
        let ids = collect_ids(&book);
        let last = ids.last().expect("the sample book has nodes").get();

        let section = book.sections[0].id;
        assert_eq!(book.subtree(section), Some(section.get()..last + 1));

        let quote = book.sections[0].blocks[2].clone();
        let Block::Blockquote { id, blocks, .. } = &quote else {
            panic!("the third block is a blockquote");
        };
        let quoted = block_id(&blocks[0]);
        assert_eq!(book.subtree(*id), Some(id.get()..quoted.get() + 2));

        for id in ids {
            let held = book.subtree(id).expect("the book holds it");
            assert_eq!(held.start, id.get(), "a node opens its own run");
            assert!(held.end <= last + 1, "a run stops inside the book");
        }
    }

    /// An id the book has no node for is covered by nothing rather
    /// than by whatever was numbered near it.
    #[test]
    fn an_id_the_book_does_not_hold_covers_nothing() {
        let mut book = sample_book();
        book.assign_node_ids();
        let past = collect_ids(&book).last().expect("nodes").get() + 1;

        assert_eq!(book.subtree(NodeId::UNASSIGNED), None);
        assert_eq!(book.subtree(NodeId::new(past)), None);
        assert_eq!(Book::default().subtree(NodeId::new(1)), None);
    }

    /// The sample book's one paragraph of prose.
    fn paragraph(book: &Book) -> &[Inline] {
        let Block::Paragraph { inlines, .. } = &book.sections[0].blocks[1] else {
            panic!("the second block is a paragraph");
        };
        inlines
    }

    /// Acceptance: a page break and a column break serialize under
    /// tags of their own.
    #[test]
    fn a_break_serializes_under_its_own_tag() {
        let page = Block::PageBreak {
            id: NodeId::UNASSIGNED,
            attributes: Attributes::default(),
            position: None,
            span: None,
        };
        let column = Block::ColumnBreak {
            id: NodeId::UNASSIGNED,
            attributes: Attributes::default(),
            position: None,
            span: None,
        };
        assert_eq!(
            serde_json::to_value(&page).expect("a break serializes"),
            serde_json::json!({ "type": "page_break" })
        );
        assert_eq!(
            serde_json::to_value(&column).expect("a break serializes"),
            serde_json::json!({ "type": "column_break" })
        );
    }

    /// File + position in all four presence combinations.
    #[test]
    fn origin_formats_file_line_column() {
        let pos = SourcePos {
            line: 12,
            column: 3,
        };
        assert_eq!(
            origin(Some("chapter-01.md"), Some(pos)),
            "chapter-01.md:12:3"
        );
        assert_eq!(origin(Some("chapter-01.md"), None), "chapter-01.md");
        assert_eq!(origin(None, Some(pos)), "12:3");
        assert_eq!(origin(None, None), "");
    }

    /// The names a book reports are the ones its blocks and inlines
    /// carry, down to a list item, a table cell and a note, each once
    /// and sorted. A section's own names are left out, and a source
    /// answers for its own sections alone.
    #[test]
    fn a_source_reports_the_names_its_blocks_and_inlines_carry() {
        let text = |value: &str| serde_json::json!({"type": "text", "value": value});
        let book: Book = serde_json::from_value(serde_json::json!({
            "metadata": {},
            "sections": [
                {
                    "source": "one.md",
                    "attributes": {"id": "front", "classes": ["chapter"]},
                    "blocks": [
                        {"type": "heading", "level": 1, "inlines": [text("One")],
                         "attributes": {"id": "ch1", "classes": ["opening"]}},
                        {"type": "paragraph", "inlines": [
                            {"type": "span", "children": [text("aside")],
                             "attributes": {"classes": ["smallcaps"]}},
                            {"type": "note", "blocks": [
                                {"type": "paragraph", "inlines": [text("n")],
                                 "attributes": {"classes": ["gloss"]}}
                            ]}
                        ]},
                        {"type": "list", "items": [
                            {"blocks": [], "attributes": {"id": "first-item", "classes": ["opening"]}}
                        ]},
                        {"type": "table", "body": [
                            {"cells": [{"blocks": [], "attributes": {"classes": ["total"]}}],
                             "attributes": {"classes": ["sum"]}}
                        ]}
                    ]
                },
                {
                    "source": "two.md",
                    "blocks": [
                        {"type": "blockquote", "blocks": [], "attributes": {"classes": ["epigraph"]}}
                    ]
                }
            ]
        }))
        .unwrap();

        let one = book.names(Some("one.md"));
        assert_eq!(
            one.classes,
            ["gloss", "opening", "smallcaps", "sum", "total"]
        );
        assert_eq!(one.ids, ["ch1", "first-item"]);
        assert_eq!(book.names(Some("two.md")).classes, ["epigraph"]);
        assert_eq!(book.names(Some("three.md")), Names::default());
        let all = book.names(None);
        assert_eq!(
            all.classes,
            ["epigraph", "gloss", "opening", "smallcaps", "sum", "total"]
        );
        assert_eq!(all.ids, ["ch1", "first-item"]);
    }
}