document-outline.js

Utilities for consumers holding a tree-form DocumentTree (document-schema.js 4.0.0) — the table-of-contents projection, effective-property resolution, the content-addressed property-graph projection, and the flatten-to-leaves / leaf-text / stable-hash helpers — without importing the producer that made it. The outline package for the documents.js family. Worker-isomorphic: the same code runs under Node and inside a Cloudflare Workers isolate.

Created for document-schema.js#14: none of the content shapes groups content by heading or list level — a heading paragraph sits in a flat blocks array like any other — so every consumer needing a nested tree (chunking a document for retrieval, generating a table of contents, structural diffing) had to rebuild the same nesting transform for itself. This package is that transform, once. Its core surface depends only on document-schema.js (plus zod) and never touches a codec, because it only ever operates on an already-produced package, regardless of which producer made it — the one exception is outline/pdf-regions (ExaDev/documents.js#931, see PDF regions below), which depends on pdf-codec for its LayoutPage/LayoutItem types precisely because a PDF page has no codec-independent positioned-content model to read instead.

document-schema.js#20 then made the tree the canonical form: since 4.0.0, DocumentTree is the tree — a discriminated union of { node, children } group wrappers (SectionGroupNode, SlideGroupNode, SheetGroupNode, DrawPageGroupNode, ShapeGroupNode, HeadingGroupNode, ListGroupNode, all imported from document-schema.js itself). With the tree vocabulary owned by the schema, this package's phase-1 decompose/flatten pair — the flat-to-tree transform and its bijection — moved wholesale into documents.js's package boundary (document-outline.js#2, phase 2): one implementation, one authority, no second copy of the grouping semantics here. What remains — and what this major release re-charters the package around — is the artefact-utility surface: everything a consumer holding a serialised tree-form package JSON needs to project, resolve, and hash it, with document-schema.js as the only dependency. The removal is the release note: decompose, flatten, documentEnvelope, and the local TreeNode types are gone from this package's surface outright, not @deprecated — the tree types live in document-schema.js, the lossless tree↔flat pair lives in documents.js.

Getting started

Requires Node.js >=20 and pnpm 11.6.0.

pnpm install
pnpm build          # tsdown -> dist/ (ESM + CJS + .d.ts)
pnpm typecheck      # tsc -p tsconfig.json && tsc -p tsconfig.node.json (dual tsconfig)
pnpm lint           # eslint . --fix --cache --max-warnings 0
pnpm test           # vitest run
pnpm test:watch     # vitest
pnpm test:workers   # vitest run --config vitest.workers.config.ts, inside a real Cloudflare Workers (workerd) isolate

To run a single test file, pass its path to vitest directly, e.g. pnpm exec vitest run src/outline/build.test.ts.

What it provides

| Module | Exports | | --------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | outline/build | buildOutline (per-kind TOC projection over a DocumentTree) | | outline/effective | effectivePackage (effective-property resolution) | | outline/graph | projectDocumentGraph (content-addressed property-graph projection over one or several DocumentTrees), insertNode/insertEdge (the projection's write side — minting a new content-addressed node and attaching it into a graph), removeEdge/replaceEdge (the write side's detach/repoint primitives — dropping an existing edge, or atomically repointing one onto a new target in the same position), defaultExtractionPolicy, contentHashV1 (the projection's named, versioned node-identity contract), orderKeys (the fractional/lexicographic sibling-order-key operations — orderKeyForIndex/orderKeyBetween/orderKeyBefore/orderKeyAfter/renumberedOrderKeys) and OrderKeyBudgetExhaustedError (the named error every order-key exhaustion throws), UnknownSiblingError (the named error insertEdge throws for a before/after position naming a sibling id the parent does not carry), AmbiguousSiblingError (thrown when such a position names a sibling id matching more than one qualifying edge), ContainsCycleError (thrown by insertEdge, or by insertNode's own fresh-mint children-wiring, when attaching a CONTAINS edge would close a cycle), NodeKindMismatchError (thrown when insertNode's dedup hits an id already minted under a different kind), UnknownEdgeError/AmbiguousEdgeError (thrown by removeEdge/replaceEdge when the requested (from, to, kind[, path]) names zero, or more than one, existing edge), walkPropertyGraph (the shared cycle-guarded traversal), and the PropertyGraph/GraphNode/GraphEdge/GraphDocument/ExtractionPolicy/GraphEdgeLike/GraphLike/WalkedNode/WalkPropertyGraphOptions/InsertNodeContent/InsertNodeResult/InsertPosition/InsertEdgeOptions/RemoveEdgeOptions/ReplaceEdgeOptions types | | outline/node | OutlineNode, OutlineChild, OutlineLeaf, OutlineNodeSchema, isOutlineNode, isOutlineChild, isOutlineLeaf | | outline/helpers | flattenOutline, outlineLeafText, leafContentHash | | outline/regions | segmentSheetRegions (connected-component region segmentation over a sheet's populated cells, each classified with a confidence), and the SheetRegion/RegionClassification types | | outline/labels | deriveNeighbourLabels (nearest-text-neighbour label derivation per cell), and the CellLabel/CellNeighbourReference types | | outline/pdf-regions | segmentPdfRegions (recursive X-Y cut region segmentation over a PDF page's own positioned items, each classified with a confidence), and the PdfRegion/PdfRegionBounds types |

Every module in the table is re-exported from the package root, so its exports import from 'document-outline.js' directly. outline/hash (the stableContentHash/canonicalise/sha256 primitives behind leafContentHash's published recipe) is deliberately not on the root entry — it stays reachable via the document-outline.js/outline/hash subpath, keeping the root surface small.

buildOutline(pkg) dispatches on pkg.kind and projects pkg.children into the root scope's children — OutlineChild[], an ordered mix of this package's own OutlineNode groups and the schema's leaf payloads. The root is deliberately not itself a node (no synthetic "document" group), so a wordprocessing package's pre-heading content — or a package with no grouping signal at all — appears as leaves directly in the returned array.

This is the TOC projection, not a decomposition, and the difference is the charter: it deliberately re-groups across container boundaries — a wordprocessing package's sections flow into one tree, a slide's paragraphs are taken across its shapes in shape order — which is exactly the lossiness a table of contents wants, and exactly why the lossless container-boundary-respecting pair lives in documents.js's package boundary instead.

An OutlineNode carries text (the group's own label), level (its source level signal, verbatim), and children (nested groups and leaf payloads in document order). level is the source signal, not tree depth: heading groups carry their anchor's headingLevel (1-based), list-item groups carry list.level (0-based), and the synthetic slide/sheet/page/formula groups are level 1. Render indentation from the nesting, never from level — a slide group (level 1) legitimately contains list items at levels 0, 1, 2… on the other scale.

Per-kind hierarchy

| Kind | Groups | Nesting | Leaves | | -------------- | ---------------------------------------- | -------------------------------------------------------- | ----------------------------------------------------- | | wordprocessing | one per heading group, by headingLevel | stack semantics; list groups nest inside by list.level | non-list blocks, at the current depth | | presentation | one per slide group, Slide N | slide paragraphs nest by list.level, across its shapes | non-paragraph blocks, at the current depth | | spreadsheet | one per sheet group, the sheet's name | — | the sheet's images, then its embedded objects | | drawing | one per page group, Page N | — | the page's shape contents flattened, then its vectors | | formula | a single node | — | the ContentFormula itself |

Both nesting scales follow the same stack semantics, modelled on how Word's navigation pane and PowerPoint's outline view present structure: each new group nests under the deepest open group with a strictly shallower level and pops equal-or-deeper groups closed, so an H4 following an H2 becomes its direct child (no synthetic intermediates) and an H1 after an H3 pops to the root; list groups behave identically on list.level's 0-based scale (a jump from level 0 to level 2 nests directly under the 0). Within a group the two compose: heading groups open scopes, list groups nest inside them, and non-paragraph blocks (tables, images, page breaks, embedded objects) attach as leaves at the current depth without changing it. A paragraph at a leaf position carries neither grouping signal in a well-formed tree, sits flat at its scope, and closes the list nesting — which is what keeps the flattened leaf order identical to document order. headingLevel is the only heading signal read — a Heading styleId without headingLevel does not group — and in presentations it is not read at all: slides have no heading hierarchy of their own, so list.level is the only depth signal they carry.

Slide and page labels (Slide 1, Page 1, …) are 1-based, matching the Markdown renderer's own per-slide/per-page heading convention; spreadsheet groups are labelled with the sheet's own name (cells are addressable data, not outline content, and never appear); drawing vectors stay in the tree as textless leaves so structural diffing still sees them.

Effective properties

A tree group may carry a style ref into the package's styles table (document-schema.js#21). effectivePackage(pkg) resolves those refs away using document-schema.js's own overlay helpers (resolveStyleChain, applyParagraphStyleProperties, applyRunStyleProperties — the mechanics are the schema's to own, the same single-authority rule that moved the tree vocabulary there) and returns the package with every ref consumed and the styles table dropped:

import { effectivePackage } from "document-outline.js";

const resolved = effectivePackage(pkg); // same tree, properties inlined, no styles table

The semantics: a group's ref, plus every ancestor group's ref, overlays onto each paragraph in that group's subtree — group anchors (heading and list groups carry full ContentParagraph anchors) and bare paragraph leaves alike — with the chain ordered outermost-first so the nearest group's entry wins over further-out ones, and the paragraph's own direct properties win over everything (the schema's apply helpers fill gaps, never overwrite). The run half of a resolved entry applies to every run of each paragraph it resolved for. The walk's boundary is the block flow: a table leaf's cell paragraphs and an embedded document's own content are leaf-local payload this walk does not rewrite — an embedded document is its own whole document context.

Two guarantees worth depending on. First, effectivePackage(factored) deep-equals effectivePackage(unfactored): a serialisation that factored properties into style refs and one that inlined them everywhere resolve to the same effective tree, so consumers comparing or hashing content never see the producer's compression choices. To get that property for hashes, resolve first — leafContentHash over the leaves of buildOutline(effectivePackage(pkg)) names the document, not the factoring. Second, resolution runs loudly: a ref the styles table does not carry is malformed, and resolveStyleChain throws rather than silently skipping. A styles-free package is returned as the same object — nothing anywhere needs rewriting.

Graph projection

projectDocumentGraph (ExaDev/documents.js#659) exports one or several tree-form packages into a single property graph — nodes plus typed edges — with content-based deduplication and no DocumentTree schema change:

import { projectDocumentGraph } from "document-outline.js";

const graph = projectDocumentGraph([
  { id: "report-1", package: reportPkg }, // id: your stable, external document id
  { id: "memo-1", package: memoPkg },
]);
// graph.nodes: { id, kind, ...own properties }
// graph.edges: { from, to, kind, orderKey, path? } — kind is CONTAINS | STYLED_BY | DEFINED_BY | PROPERTY

Node identity is computed, not stored, and never caller-supplied. Every content node's id is contentHashV1 of its own projected content — this projection's own named, versioned node-identity contract (pinned independently of leafContentHash's own contract, even though the two happen to share an implementation today), applied bottom-up as a Merkle DAG: a leaf's hash covers its own content, a group's hash covers its own properties plus its children's hashes. A node may therefore have any number of parents — the git/IPFS object model, not a strict Merkle tree — which is what makes cross-document sharing possible at all. No mint site ever reads an id-shaped field out of a node's own content; a content field named id or kind is always shadowed by the real computed value. The document root is the one exception: content hashing it would change its id on every interior edit, so the root carries the caller-assigned stable id (a git ref pointing at a moving commit hash) with metadata/symbolTable/pages/source inline as per-document identity facts.

Refs are dereferenced before hashing. A style: 's1' ref (or an anchor's definition: 'n1') is a document-local label with no cross-document meaning — every assembled package mints its own s1, s2, … keys — so the referenced entry's content hash enters the referencing node's hash input and the bare key never does. The ref itself becomes an edge: (group)-[:STYLED_BY {orderKey}]->(styleEntry) and (anchor node)-[:DEFINED_BY {orderKey}]->(definitionEntry). Two structurally identical paragraphs whose documents name an identical style entry differently therefore dedupe to one node.

STYLED_BY carries the whole resolution chain, not just the direct ref. A heading or list anchor, and a bare paragraph leaf sitting inside a styled ancestor's scope, each emit one STYLED_BY edge per entry in their resolved ancestor style chain — outermost first — rather than only their own direct ref, so a consumer can walk the full resolution chain (effective.ts's own overlay order) from edges alone with no separate lookup. This widens edge counts for a plain paragraph nested inside any styled heading or section: it now carries its own inherited-chain edges in addition to whatever it carried before. Every other group kind is not an effectivePackage resolution target either, so its own STYLED_BY behaviour is unchanged — at most its own single ref, never an inherited chain.

Factoring is visible to node ids. The projection hashes each node's own projected content, never style-resolved content, so a factored and an unfactored spelling of one document give the nodes the style rides different ids — the factored hash folds in the dereferenced entry's hash, the unfactored hashes the properties inline — while everything the style does not touch projects to the same shared nodes. The route to factoring-invariant ids is the same as leafContentHash's: run effectivePackage(pkg) first, and the two spellings project to the identical graph.

Containment is an edge. (parent)-[:CONTAINS {orderKey}]->(child), orderKey being a fractional/lexicographic string derived from the child's index in document order, because a shared node has no single tree position and document order is semantically load-bearing. A dense integer would force a renumber of every later sibling on every insertion; a lexicographically sortable string lets a later single insertion (an editor building on this projection) mint one new key strictly between its neighbours — orderKeys.orderKeyBetween — without touching any edge that did not move, rebalancing via orderKeys.renumberedOrderKeys only once that interval is exhausted — and that exhaustion throws OrderKeyBudgetExhaustedError, a named class exported beside the namespace so the consumer branches on instanceof rather than parsing a message. The two ends a between-insert cannot reach have operations of their own: orderKeys.orderKeyBefore mints the shortest key below a drifted minimum (an all-zero key is the floor of the scheme — the honest rebalance signal), and orderKeys.orderKeyAfter appends above a drifted maximum, each stepping the first digit with room by half the remaining headroom so later mints on the same side keep finding space. The projection itself only ever mints via orderKeys.orderKeyForIndex; the other four operations exist for exactly this downstream consumer. Edits otherwise fall out of the identity scheme rather than being implemented: modifying a node mints a new node while the old one persists beside it — free version history if orphans are never pruned.

Extraction is a policy, not a rulebook. One pluggable (path, value) => 'extract' | 'inline' decision is consulted uniformly at every level — root envelope fields, table entries, tree-node properties, individual scalars — with paths relative to the owning node. The default (defaultExtractionPolicy) extracts the definitions-table facility's entries (styles, definitions, layers, attachments, destinations — the reused content the tables exist to hold) and leaves everything else inline; a custom policy can promote any value at any path to a kind: 'value' node joined by a PROPERTY edge carrying the property path. An assembled package's recurring property tuples are already factored into its tables by minting's own recurrence rule, so the default needs no frequency survey of its own: sharing happens at the node level, exactly as the projection's worked example pins (recurring text stays inline on each paragraph node; the paragraphs themselves are shared).

Dedup itself needs no merge logic: identical content yields an identical hash yields an identical id, so the projection keeps one node per id and one edge per (from, to, kind, orderKey, path) tuple — exactly what a graph store's native upsert (Neo4j MERGE, an RDF store keyed by the hash) would do with this output. An identical whole subtree collapses to one shared subtree with only the seam edges from each document's own ancestors being document-specific; table entries nothing references are still emitted as nodes, reachable by kind queries.

Walking the graph

walkPropertyGraph(graph, startId, options?) is a shared pre-order depth-first traversal over any { nodes, edges } value shaped like a PropertyGraph, so every consumer — an outline renderer walking CONTAINS, a style-chain reader walking STYLED_BY, a generic graph browser walking everything — shares one traversal and one cycle policy instead of each hand-rolling its own:

import { walkPropertyGraph } from "document-outline.js";

const contains = walkPropertyGraph(graph, "report-1", { kinds: ["CONTAINS"] });
// readonly { node: GraphNode, edge: GraphEdgeLike | undefined }[], in document order

At each node, outgoing edges are restricted to options.kinds when given (else every kind present) and visited sorted ascending by orderKey — which is what makes a CONTAINS walk reproduce document order and a STYLED_BY walk reproduce the resolution chain in order. The cycle guard is derived from the kinds being traversed, never separately configured: a CONTAINS-only walk skips allocating one as a pure optimisation, safe because every CONTAINS edge that could ever enter a graph built through this module's own functions is guaranteed acyclic before it is ever appended — projectDocumentGraph's own tree walk mints one by folding a child's hash into its parent's, and insertEdge/insertNode (see "Writing to the graph" below) both run a shared reachability check before attaching one of their own, refusing anything that would close a cycle. Traversing any other kind — including the default "every kind present," since STYLED_BY/DEFINED_BY/PROPERTY edges carry no acyclicity guarantee of their own — tracks the current path and skips descending into an already-on-path neighbour, suppressing a true cycle while still visiting a node reached by two different, non-nested paths once per path (the same multi-parent sharing a CONTAINS walk already relies on).

Writing to the graph

ExaDev/documents.js#935: projectDocumentGraph only ever reads a whole DocumentTree, so a caller building an interactive editor on top of its output had no path to mint a new content node or attach one into an existing graph. insertNode mints; insertEdge attaches:

import { insertEdge, insertNode } from "document-outline.js";

const paragraph = insertNode(
  { nodes: [], edges: [] }, // or an existing PropertyGraph
  {
    kind: "paragraph",
    properties: { kind: "paragraph", runs: [{ text: "New paragraph." }] },
  },
);
// paragraph: { graph: PropertyGraph, id: string } -- id is contentHashV1 of exactly the content given

const withParagraph = insertEdge(
  paragraph.graph,
  existingSectionId,
  paragraph.id,
);
// appends a CONTAINS edge from existingSectionId to the new paragraph, at the end of its existing children

insertNode mints with the identical discipline every read-side mint site already follows. id is contentHashV1 of the content handed in — folding in children (an ordered list of already-minted node ids) exactly as a group node folds its own children's ids into its hash — computed and spread into the node face after the content, so a properties field named id or kind is shadowed unconditionally. InsertNodeContent carries no id field at all, which is what makes the no-caller-supplied-id property hold structurally rather than by validation: there is no parameter through which a caller could supply one, even by mistake. kind is deliberately excluded from the hash input itself, for the same reason mintValueNode's own kind: 'value' is never folded into its hash either: it is the graph vocabulary's word for what a node IS, not a fact about its content. When children is given for an id nothing has pointed a CONTAINS edge onto yet (the common case), insertNode mints one CONTAINS edge per child at orderKeys.orderKeyForIndex(index) — the same wide, evenly spaced keys a fresh projection mints — but each one is checked for a CONTAINS cycle exactly as insertEdge's own attachment is (see below), and throws ContainsCycleError when a child already reaches this node's own about-to-be-minted id: folding a child's hash into a fresh node's own hash rules out that node being its own pre-existing descendant, but not an edge some earlier insertEdge call already pointed at this id before it existed, which is exactly the shape a fresh mint cannot skip checking for. When graph already carries one or more CONTAINS edges from this id — that exact dangling-edge shape — minting every child at its own bare orderKeyForIndex(index) regardless of what is already there risks an order-key tie against an edge already sitting at that key, or a byte-identical duplicate of an edge already attached to that exact child, so this case routes through the identical reconciliation described below instead of the bare index-keyed mint. Content identical to a node already in the graph dedupes to the existing node rather than minting a duplicate, the same upsert-once rule projectDocumentGraph itself follows — but that dedup is checked against the existing node's own kind first: two calls whose properties/children happen to hash identically while asking for different kinds is a genuine cross-kind collision, refused loudly as NodeKindMismatchError rather than silently handing back whichever kind minted first. A dedup hit's requested children are reconciled against the existing node's own CONTAINS edges rather than assumed to already match, since two differently spelled calls (children named explicitly vs. an equal-valued field folded directly into properties) can hash identically while only one of them declared children at all — and reconciliation is by multiplicity, not set membership: children can legitimately repeat an id (two identical CONTAINS children under one section), so an existing edge is never dropped just because some other occurrence of the same id already satisfied the request. Classification and anchoring both resolve to a SPECIFIC existing edge, never a bare id value, and the classification pass itself is a longest-common-subsequence match between the existing edges' own target sequence and the full requested children list — considering every id's existing edges relative to every OTHER id's, not each id's own count in isolation, which is what a merely per-id front-to-back matcher gets wrong: requested [A, B, A] against existing edges wired [B, A] is a genuine, order-consistent pre-wiring (dropping the request's own first A from [A, B, A] yields exactly [B, A]), yet counting each id's occurrences independently pairs request position 0's A with the wrong existing edge, an assignment no reading of the two sequences together would produce. A missing occurrence anchors to the specific existing edge at the nearest later already-matched position (immediately before it), or at the end when nothing later matched — anchoring by a specific edge rather than by id is what lets [A, X, A] insert X between two already-wired As correctly even though the id A alone would otherwise resolve ambiguously to whichever A sorts first. An existing edge the LCS match cannot place without breaking that global order (existing containment wired in a relative order the request cannot embed at all, e.g. requested [A, B] against existing edges wired [B, A]) is paired against a remaining unmatched requested occurrence of the identical id by a second, per-id pass instead, so a genuine ordering conflict caps that id's final multiplicity at max(existingCount, requestedCount) rather than minting a needless extra edge. Only a position classified as missing is ever placed this way; an already-matched occurrence is never moved. Walking CONTAINS edges from id after reconciliation reproduces the exact requested children list, in order and multiplicity both, whenever the existing edges' own target sequence is a genuine subsequence of children — covering any order-consistent interleaving across ids, not only a prefix of each id's own occurrences; when it is not even a subsequence, reconciliation still terminates safely and never inflates any id's multiplicity beyond max(existingCount, requestedCount), but the resulting order is not guaranteed to equal children, since existing containment is never reordered to fit a new request. Re-inserting an identical children list stays the no-op past-the-first-call behaviour this has always promised, because every position is then classified as already matched and none are inserted.

Mutating a node is not a separate operation. Content-addressing already means "mutate" is "mint a new version": call insertNode again with the changed content, get back a new id, then attach that new id wherever the old one was referenced. The old node and its edges are left exactly as they were — neither insertNode nor insertEdge ever removes or rewrites existing graph state, which is the free version history projectDocumentGraph itself exhibits when projecting two versions of one document side by side. A true in-place replacement — the new version REPLACING the old one at the same position, not sitting beside it — is replaceEdge's own job (ExaDev/documents.js#1004): calling insertEdge a second time would only add a second edge from the same parent alongside the old one, since neither function ever removes or repoints an existing edge.

import { insertNode, replaceEdge } from "document-outline.js";

const revised = insertNode(graph, {
  kind: "paragraph",
  properties: { runs: [{ text: "Revised." }] },
});
const updated = replaceEdge(revised.graph, parentId, oldChildId, revised.id);

replaceEdge(graph, from, oldTo, newTo, options?) resolves the existing edge via (from, oldTo, kind, path?) — kind defaults to CONTAINS, matching insertEdge's own default — and repoints it onto newTo while reusing that edge's own orderKey (and path) unchanged, rather than routing through insertEdge's bisection/rebalance machinery to mint a fresh position: the position slot is reused, not renumbered, so the new version lands in exactly the slot the old one held. This is deliberately one atomic call rather than a caller composing removeEdge then insertEdge by hand, which would leave a window for some other mutation to land in between and invalidate the position being preserved. A CONTAINS replacement is checked for a cycle exactly as insertEdge's own attachment is, but against the edge set with the edge being replaced already excluded, so a genuine no-op replacement (newTo identical to oldTo) is never refused as a self-cycle. removeEdge(graph, from, to, options?) is the standalone detach primitive replaceEdge builds on, for callers who want to drop an edge without attaching a replacement.

Both removeEdge and replaceEdge resolve the edge they act on via (from, to, kind, path?), not the full edgeKey tuple — a caller detaching or repointing an edge is not expected to already know its current orderKey. path is optional disambiguation, needed only when (from, to, kind) alone matches more than one edge (two PROPERTY/DEFINED_BY edges from one owner extracting to the identical shared value node, say). No match at all is refused as UnknownEdgeError; more than one match — whether path was omitted where it was needed, or the matches are identical in every field these functions can compare — is refused as AmbiguousEdgeError, in the same "resolves to exactly one thing or not at all" tradition UnknownSiblingError/AmbiguousSiblingError already established for insertEdge's own sibling lookups. Neither function ever touches graph.nodes: an edge's own to node, quite possibly unreferenced once its last edge is gone, is exactly the orphan this module's own free-version-history behaviour already treats as intentional — pruning it is deliberately out of scope, the same as for every other node that ends up unreferenced by any other means.

insertEdge attaches an already-minted node at a sibling position, defaulting to a CONTAINS edge appended after the target's existing children:

insertEdge(graph, parentId, childId); // append, CONTAINS
insertEdge(graph, parentId, childId, { position: { at: "start" } });
insertEdge(graph, parentId, childId, { position: { at: "before", siblingId } });
insertEdge(graph, parentId, childId, {
  position: { at: "after", siblingId },
  kind: "PROPERTY",
  path: ["metadata", "keywords"],
});

Attaching a CONTAINS edge is checked for a cycle first: if to already reaches from via existing CONTAINS edges (most directly, re-parenting a node underneath its own descendant in one call), attaching from -> to would make from its own transitive ancestor, so insertEdge refuses it as ContainsCycleError rather than handing back a graph a CONTAINS-only walk could no longer traverse without looping forever. This check is deliberately edge-only — it searches graph.edges directly and never consults graph.nodes — because insertEdge allows attaching an edge onto a to that names no node yet (a dangling forward edge to an id a caller has computed but not yet minted), and a later insertNode call minting that exact id needs the identical check to catch a cycle closing across the two calls; insertNode's own fresh-mint children-wiring runs this same check (see above), so no CONTAINS edge this module ever attaches onto an already-existing graph can skip it.

A named siblingId not found among the parent's existing edges of the requested kind is refused loudly, as UnknownSiblingError (carrying from/kind/siblingId as structured fields rather than only a message) — there is no position to compute otherwise. A named siblingId matching more than one such edge (a parent can carry more than one edge of the same kind to the same target, e.g. two identical CONTAINS children under one section, or two PROPERTY edges to one shared value node at different paths) resolves to the earliest such match in orderKey order — siblings are already sorted before position resolution runs, so "the earliest match" is a deterministic, reproducible boundary, not a guess dependent on insertion order — UNLESS the matches genuinely tie on orderKey, which projectDocumentGraph's own emitWalkEdges produces for every PROPERTY/DEFINED_BY sibling group (they carry no real document-order sequence, so they all mint at the identical floor key): a real tie has no principled "earliest," so that shape alone is refused as AmbiguousSiblingError. When bisection between two neighbours has no room left, insertEdge catches the resulting OrderKeyBudgetExhaustedError itself and rebalances: every one of that sibling group's edges is re-minted with a fresh, evenly spaced renumberedOrderKeys set that includes the new edge in the requested position, so the caller never has to handle the exhaustion by hand. This covers two distinct no-room shapes, both routed through the identical rebalance: the common case is start against a first child, which — like every first child projectDocumentGraph itself ever mints — already sits at the order-key scheme's own floor; the other is two adjacent siblings that already share one orderKey (the same genuine tie the ambiguity check above watches for) — inserting between such a tied pair is recognised as no-room before ever attempting to bisect between two identical keys, and rebalances the same way.

Neither function recomputes an ancestor's id when a new child is attached beneath it. A compound node's id was folded from whatever children list it was minted with; attaching one more CONTAINS edge to an already-minted node does not retroactively change that node's own id, exactly as adding a blob to a git tree does not change a tree object already written to the object store — git mints a new tree object instead, and a ref is what moves to point at it. A caller wanting an ancestor's id to reflect a new descendant re-mints that ancestor with insertNode (its own unchanged properties plus the updated children list) and re-wires whichever of its own referrers should see the new version, one level at a time, up to (never including) the document root — whose id is caller-assigned and content-independent for exactly this reason, so a root-level insertion needs no cascade at all.

Sheet regions and neighbour labels

ExaDev/documents.js#823: a real sheet is a canvas, not a table — a table in one corner, a column of unrelated prose commentary elsewhere, a sheet that is entirely narrative, label/value pairs scattered in margins. segmentSheetRegions and deriveNeighbourLabels are two independent, purely advisory inferences over a sheet's populated cells (ContentSheetCell[], read straight off a ContentSheet, a tree-form SheetDescriptor, or a SheetGroupNode.node — whichever a consumer already holds): neither mutates its input, neither is wired into buildOutline or any other existing entry point, and a consumer who never calls either still has every cell exactly as the lossless cell model already carries it. Classification and labelling add information; they never gate what is emitted, because the failure mode of a structure-gated reader is silently dropping what it did not recognise, and a consumer cannot tell "the sheet does not say that" from "the reader did not understand that part."

import {
  deriveNeighbourLabels,
  segmentSheetRegions,
} from "document-outline.js";

const regions = segmentSheetRegions(sheet.cells);
// [{ range: { startRow, startColumn, endRow, endColumn }, cells: [...], classification: 'table', confidence: 0.94 }, ...]

const labels = deriveNeighbourLabels(sheet.cells);
// one entry per populated cell: { cell: { row, column }, above?: { ref, text, distance, confidence }, left?: {...} }

Regions are connected components of populated cells, tolerating a single blank row or column inside a block: two cells connect when they share a column and are at most 2 rows apart, or share a row and are at most 2 columns apart — never both axes loosened at once, so a diagonal-only jump across both a blank row and a blank column does not connect two otherwise-unrelated blocks, while an ordinary dense table still chains together through its own same-row/same-column neighbours. Each region is classified table / prose / model / mixed / unknown from plain, cheap signals over its own cells — row-count regularity and a header-row signal (the topmost row is predominantly text where at least one other row is predominantly numeric/formula) for table; text fraction weighted by average string length for prose; formula fraction weighted above plain numeric fraction for model (a plain numeric table full of literal values is still a table, not a model) — with mixed when two candidates score comparably and unknown when nothing clears the signal bar (including any region of a single cell, which carries no structural signal at all). confidence is a 0 (no signal) to 1 (unambiguous) scale this package introduces for exactly this purpose, since nothing in this workspace already had a numeric confidence convention to match.

Labels are derived from neighbours, not from detecting a header row as a precondition: for every populated cell, deriveNeighbourLabels finds the nearest text-valued cell (value.kind === 'string') strictly above it in the same column and strictly to its left in the same row, each independently optional and absent — never a fabricated placeholder — when nothing is found. That single rule covers a table (the header row is simply the nearest text above, repeated down every column), a scattered label/value pair, and a margin annotation, without requiring the sheet to be tidy. The search is bounded to the target cell's own region (segmentSheetRegions' own partition): a candidate in a different, disconnected region is never reported as a label, since segmentation has already judged those two cells unrelated. confidence follows the same 0..1 scale as regions, mapped from distance as 1 / distance — an immediately adjacent label (distance 1) is maximal confidence, decaying smoothly the further away the nearest match is found.

RegionClassification (a region's kind + confidence) was always deliberately not spreadsheet-scoped in its own name: the issue that introduced it was explicit that "regions with confidence" is a document-model concept — a PDF's columns/tables/figures/captions share the identical shape — so it was named as the vocabulary a future PDF region pass would reuse rather than re-mint. ExaDev/documents.js#931 is that PDF pass — see PDF regions below.

PDF regions

ExaDev/documents.js#931: pdf-codec's LayoutPage is deliberately just positioned items — text/image/rect/line/ellipse/path/link, in PDF user space — with no notion of columns, tables, figures, or captions (pdf-codec's own README explains why: semantic reconstruction from geometry is expensive, lossy, and deliberately kept out of the codec). segmentPdfRegions is the PDF-specific sibling of segmentSheetRegions above: a purely additional, opt-in inference over a page's own items, reusing RegionClassification rather than mutating or gating anything.

import { segmentPdfRegions } from "document-outline.js";

const regions = segmentPdfRegions(layoutDocument.pages[0]);
// [{ bounds: { xPt, yPt, widthPt, heightPt }, items: [...], classification: 'column', confidence: 0.87 }, ...]

The technique is the recursive X-Y cut (Nagy, G., & Seth, S., "Hierarchical representation of optically scanned documents", Proc. 7th ICPR, 1984, pp. 347-349 — also see Meunier, J-L., "Optimized XY-cut for determining a page reading order", 2005, for the gap-threshold variant this package adapts), the standard top-down page-segmentation algorithm: recursively split a page's content along whichever axis has the widest whitespace gap between item clusters, until no gap wide enough to be structural remains. This was chosen over a literal port of segmentSheetRegions' own connected-component/gap-tolerance approach because a sheet's cells already sit on a discrete row/column grid, whereas a PDF page has only continuous coordinates — "how wide a gap, relative to the content around it" is the only signal available, and recursive X-Y cut is the established technique for exactly that case. Each gap's own threshold is derived locally from the smaller of its two neighbouring clusters' own content scale (a small font size, or a graphic's own thickness) rather than a single page-wide figure, since a page mixes fine content (body text) with coarse content (a large photo) and a caption's own small scale — not the much larger figure beside it — is what should decide whether a modest caption gap counts as a break. A candidate vertical cut is rejected outright when its bands turn out to share the same row rhythm (most of one band's text lines recur, within a small tolerance, in every other band): that is a table's own columns, not independent multi-column body text, and rejecting the cut lets the whole grid survive as one leaf so it can be recognised as a table instead of fragmenting into one falsely-prose-like leaf per column.

Each leaf is then classified table / column / figure / caption / mixed / unknown from plain, cheap signals over its own items, the same "no external corpus, no learned weights" philosophy segmentSheetRegions uses for sheets: a leaf whose text lines each split into several consistently-spaced horizontal clusters is a table (the geometric signature of a grid, whether or not it is also ruled); a leaf of text lines with a consistent left edge and no internal splits is a column; a leaf dominated by non-text painted content (images, vector art) is a figure, with a raster image's presence weighted as stronger evidence than vector decoration alone. caption is the one classification that is a relationship rather than a standalone geometric signature: a short text leaf sitting close beside (and horizontally overlapping) a figure leaf is reclassified as its caption in a second pass, after every leaf already has its own first-pass classification — confidence there reflects how close the gap is to the maximum qualifying distance. A single item too small to carry a signal is unknown, with one exception: a single painted graphic (an image, or a standalone vector shape) is unambiguously a figure on its own, unlike a lone table cell or a lone word.

Helpers

import {
  buildOutline,
  effectivePackage,
  flattenOutline,
  leafContentHash,
  outlineLeafText,
} from "document-outline.js";

const outline = buildOutline(pkg); // OutlineChild[] — the TOC projection
const resolved = effectivePackage(pkg); // style refs consumed, table dropped
flattenOutline(outline); // every leaf payload, in document order
outlineLeafText(aLeaf); // the leaf's own text (paragraph runs, table cells,
// image altText, formula LaTeX; '' for textless leaves)
leafContentHash(aLeaf); // stable content hash — see the recipe below

Heading and list paragraphs are represented by their group nodes and are not duplicated as leaves, so a tree of groups flattens to the non-paragraph content plus every unlevelled paragraph; a group's own text is always its text field. leafContentHash hashes the leaf as given and deliberately does not fold style resolution in — a leaf alone does not know its ancestor group refs, so effective-property resolution can only happen with the whole package in hand. The resolve-then-hash route is effectivePackage(pkg) first, then hash the resolved leaves; hash the raw leaf only when you truly mean the literal object.

The hash recipe

leafContentHash (via stableContentHash) is a published contract — changing any step changes every hash ever issued:

1. Strip $schema keys recursively from the value (arrays mapped, plain objects rebuilt without the key). Serialised dumps carry a release-pinned $schema CDN URI stamped by document-schema.js's serialisation helper; the label is transport metadata about which schema version produced the JSON, not content, and no content field is named $schema — so a dump and its parsed-then-rehashed original agree.
2. Canonicalise the result: rebuild every plain object with its own keys sorted ascending by UTF-16 code unit (arrays keep their order, primitives pass through) — so independently constructed, structurally identical content is byte-identical from here on regardless of field-construction order.
3. JSON.stringify the canonicalised value (no spacing; undefined-valued optional fields drop out, so "absent" and "explicitly undefined" hash the same).
4. UTF-8 encode with TextEncoder.
5. SHA-256, hand-rolled over Uint8Array (Worker-isomorphic; no node:crypto, no async SubtleCrypto) and pinned against the FIPS 180-4 example vectors in hash.test.ts.
6. Hex-encode the digest, lowercase.

The result is deterministic across processes and platforms, equal exactly when the leaf's content is equal, and different for different content up to SHA-256 collision resistance.

Where decompose and flatten went

The phase-1 decompose/flatten pair and its property-tested bijection — the lossless tree↔flat transform this package once carried as the vehicle for the DocumentTree promotion — now live in documents.js's package boundary. Schema 4.0.0 made DocumentTree itself tree-form, so the grouping semantics have one home next to the codecs that produce and consume packages, and the tree types (TreeNode, TreeGroup, SectionGroupNode, …) import from document-schema.js. If you hold a flat ContentDocument and need the tree, or need the exact container-boundary-preserving inverse of the TOC projection above, that is documents.js's surface now.

Conventions

• Worker-isomorphic (see the family-wide convention): runtime src/ must not import node:*, a bare Node builtin, or use the Buffer global — enforced by a no-restricted-imports/no-restricted-globals ESLint rule and exercised in CI by running a test suite inside an actual workerd isolate (pnpm test:workers).
• Only src/index.ts may be named index.* — a custom ESLint rule (local/no-non-barrel-index) rejects any other module using an index basename, since that would be a hidden entry point the exports map in package.json doesn't advertise.
• OutlineNodeSchema follows document-schema.js's z.custom hand-written-guard pattern (ContentBlock is the precedent): z.lazy() collapses recursive schemas' static type to unknown in the pinned zod 4, so the recursion lives in a plain function guard instead.
• Release, CI, and commit-message conventions are all workspace-wide, not package-local — see the monorepo root README for the mechanism (topological per-package semantic-release via @exadev/semantic-release-workspace, OIDC trusted npm publishing) and its post-release republishing and attestation note on the restored GitHub Packages mirrors, npm aliases, and SBOM/provenance signing.

Install

pnpm a