Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/ledger.rs

21.2 KiB, 133 runs

created by r1870400018:35667, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The anchor ledger: the one channel through which a layout fact reaches anything.
2//!
3//! Stratification (see `sec_decisions.typ`) forbids user code from observing layout directly. What
4//! it may see is here: a map from an anchor's identity to the page and position it resolved to. The
5//! ledger is filled during composition, is content-addressed by anchor identity, serialises to jdat,
6//! and -- in a later phase -- ships inside the Pearl file so the document is queryable without the
7//! engine.
8//!
9//! Content addressing is what buys incremental compilation and what turns a convergence failure into
10//! a report: two ledgers can be differenced, and the difference names the anchor that moved and the
11//! pages it moved between.
12
13use crate::ir::Sp;
14use crate::page::Region;
15use crate::vfs;
16
17use oxedyne_fe2o3_core::prelude::*;
18use oxedyne_fe2o3_jdat::prelude::*;
19
20use std::collections::BTreeMap;
21
22/// The closed vocabulary of things a reference can resolve to. A kind the engine does not know is a
23/// limit it declares, not a gap it hides.
24#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
25pub enum AnchorKind {
26 Label, // \label{...}, the general cross-reference target
27 Heading, // a section or chapter title, for running heads and the table of contents
28 IndexEntry, // an index term at the point it occurs
29 Float, // a figure or table, placed away from its anchor
30 Citation, // a bibliographic reference
31 Equation, // a numbered display equation
32 MarginNote, // a marginal claim-code annotation, drawn post-convergence in the outside margin
33}
34
35impl AnchorKind {
36 fn tag(&self) -> u8 {
37 match self {
38 AnchorKind::Label => 0,
39 AnchorKind::Heading => 1,
40 AnchorKind::IndexEntry => 2,
41 AnchorKind::Float => 3,
42 AnchorKind::Citation => 4,
43 AnchorKind::Equation => 5,
44 AnchorKind::MarginNote => 6,
45 }
46 }
47
48 fn from_tag(tag: u8) -> Outcome<Self> {
49 match tag {
50 0 => Ok(AnchorKind::Label),
51 1 => Ok(AnchorKind::Heading),
52 2 => Ok(AnchorKind::IndexEntry),
53 3 => Ok(AnchorKind::Float),
54 4 => Ok(AnchorKind::Citation),
55 5 => Ok(AnchorKind::Equation),
56 6 => Ok(AnchorKind::MarginNote),
57 _ => Err(err!(
58 "Anchor kind tag {} is not one of the seven known kinds.", tag; Input, Invalid)),
59 }
60 }
61
62 /// The kind's name, lower case -- for a diagnostic or a JSON dump where the numeric `tag` means
63 /// nothing to a reader outside the engine.
64 pub fn name(&self) -> &'static str {
65 match self {
66 AnchorKind::Label => "label",
67 AnchorKind::Heading => "heading",
68 AnchorKind::IndexEntry => "index_entry",
69 AnchorKind::Float => "float",
70 AnchorKind::Citation => "citation",
71 AnchorKind::Equation => "equation",
72 AnchorKind::MarginNote => "margin_note",
73 }
74 }
75}
76
77/// An anchor's identity, its kind and a key unique within it. Content-addressed, not positional, so
78/// a label keeps its identity when a paragraph moves it to another page.
79#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
80pub struct AnchorId {
81 pub kind: AnchorKind,
82 pub key: String,
83}
84
85impl AnchorId {
86 pub fn new<S: Into<String>>(kind: AnchorKind, key: S) -> Self {
87 Self { kind, key: key.into() }
88 }
89
90 /// A stable 64-bit FNV-1a address over kind and key, for the incremental cache. The identity
91 /// stays the map key, so a collision costs a comparison, not a wrong answer.
92 pub fn address(&self) -> u64 {
93 let mut h: u64 = 0xcbf2_9ce4_8422_2325;
94 let mix = |h: &mut u64, b: u8| {
95 *h ^= b as u64;
96 *h = h.wrapping_mul(0x0000_0100_0000_01b3);
97 };
98 mix(&mut h, self.kind.tag());
99 for b in self.key.as_bytes() {
100 mix(&mut h, *b);
101 }
102 h
103 }
104}
105
106impl ToDat for AnchorId {
107 fn to_dat(&self) -> Outcome<Dat> {
108 Ok(omapdat!{
109 "kind" => dat!(self.kind.tag()),
110 "key" => dat!(self.key.clone()),
111 })
112 }
113}
114
115impl FromDat for AnchorId {
116 fn from_dat(mut dat: Dat) -> Outcome<Self> {
117 let tag = try_extract_dat!(res!(dat.map_remove_must(&dat!("kind"))), U8);
118 let key = try_extract_dat!(res!(dat.map_remove_must(&dat!("key"))), Str);
119 Ok(Self { kind: res!(AnchorKind::from_tag(tag)), key })
120 }
121}
122
123/// Where an anchor resolved: the one-based page, and the position of its top-left on that page.
124#[derive(Clone, Copy, Debug, PartialEq, Eq)]
125pub struct Position {
126 pub page: u32,
127 pub x: Sp,
128 pub y: Sp,
129}
130
131impl Position {
132 pub fn new(page: u32, x: Sp, y: Sp) -> Self {
133 Self { page, x, y }
134 }
135}
136
137/// One resolved anchor. `reserved` is the width a forward reference held open before its value was
138/// known, `realised` what the value took; `realised` over `reserved` overflowed the reservation and
139/// owes the driver another pass.
140#[derive(Clone, Debug)]
141pub struct Anchor {
142 pub id: AnchorId,
143 pub pos: Position,
144 pub reserved: Sp,
145 pub realised: Sp,
146 pub region: Region, // the page region it sits in; decides float-relayout membership, transient (not serialised)
147}
148
149impl Anchor {
150 pub fn new(id: AnchorId, pos: Position) -> Self {
151 Self { id, pos, reserved: Sp::ZERO, realised: Sp::ZERO, region: Region::Body }
152 }
153
154 /// Did the resolved value outgrow the width held open for it?
155 pub fn overflowed(&self) -> bool {
156 self.realised > self.reserved
157 }
158}
159
160impl ToDat for Anchor {
161 fn to_dat(&self) -> Outcome<Dat> {
162 Ok(omapdat!{
163 "id" => res!(self.id.to_dat()),
164 "page" => dat!(self.pos.page),
165 "x" => res!(self.pos.x.to_dat()),
166 "y" => res!(self.pos.y.to_dat()),
167 "reserved" => res!(self.reserved.to_dat()),
168 "realised" => res!(self.realised.to_dat()),
169 })
170 }
171}
172
173impl FromDat for Anchor {
174 fn from_dat(mut dat: Dat) -> Outcome<Self> {
175 let id = res!(AnchorId::from_dat(res!(dat.map_remove_must(&dat!("id")))));
176 let page = try_extract_dat!(res!(dat.map_remove_must(&dat!("page"))), U32);
177 let x = res!(Sp::from_dat(res!(dat.map_remove_must(&dat!("x")))));
178 let y = res!(Sp::from_dat(res!(dat.map_remove_must(&dat!("y")))));
179 let reserved = res!(Sp::from_dat(res!(dat.map_remove_must(&dat!("reserved")))));
180 let realised = res!(Sp::from_dat(res!(dat.map_remove_must(&dat!("realised")))));
181 // The region is a transient layout fact, spent during composition and not serialised; a decoded
182 // anchor is never reflowed, so it defaults to the body.
183 Ok(Self { id, pos: Position::new(page, x, y), reserved, realised, region: Region::Body })
184 }
185}
186
187/// One anchor that moved between two ledgers: the identity, and the pages it left and arrived on.
188/// A non-empty diff is exactly the convergence-failure report the architecture promises.
189#[derive(Clone, Debug)]
190pub struct Delta {
191 pub id: AnchorId,
192 pub from: u32,
193 pub to: u32,
194}
195
196/// What a forward reference resolves to: a value the previous pass fixed and this pass can read.
197/// A closed vocabulary, so a kind the engine cannot resolve is a limit it declares, not a gap it
198/// hides.
199#[derive(Clone, Debug, PartialEq, Eq)]
200pub enum Ref {
201 TotalPages, // the document's own page count, the "of M" in "page N of M"
202 PageOf(AnchorId), // the physical page a named anchor resolved to, the general cross-reference
203 // The printed folio a named anchor resolved to: its physical page less the front-matter offset, so
204 // a table-of-contents entry reads the body folio (which restarts at 1 after the front matter) rather
205 // than the physical page it shares with the cover, title and contents leaves.
206 FolioOf(AnchorId),
207 // The folios a set of index-entry occurrences resolved to, deduplicated, sorted and run-compressed into
208 // the "12, 15-17, 40" list an index entry sets after its term. Each occurrence resolves as a
209 // [`FolioOf`](Ref::FolioOf), so the list reads body folios; a run of two or more consecutive folios
210 // collapses to a hyphenated range. Text-only -- it resolves to a string, not a page number -- so it is
211 // reached through [`resolve_text`](Ref::resolve_text), never [`resolve`](Ref::resolve).
212 IndexFolios(Vec<AnchorId>),
213}
214
215impl Ref {
216 /// The value this reference resolves to against `incoming`, or `None` when the previous pass has
217 /// not fixed it yet -- the empty ledger of Pass A, or an anchor not yet recorded. A composed
218 /// ledger always fixes at least one page, so a zero total is the Pass A tell.
219 pub fn resolve(&self, incoming: &Ledger) -> Option<u32> {
220 match self {
221 Ref::TotalPages => if incoming.total_pages == 0 { None } else { Some(incoming.total_pages) },
222 Ref::PageOf(id) => incoming.page_of(id),
223 // The body has not been located until a pass has recorded its first heading, so a zero
224 // `body_start_page` is the Pass A tell: reserve the slot and defer, exactly as an unresolved
225 // page reference does.
226 Ref::FolioOf(id) => if incoming.body_start_page == 0 {
227 None
228 } else {
229 incoming.page_of(id).map(|p| p.saturating_sub(incoming.body_start_page - 1))
230 },
231 // A page number is the folio-list's business, not a single value; it resolves to text alone.
232 Ref::IndexFolios(_) => None,
233 }
234 }
235
236 /// The text this reference sets, or `None` when the previous pass has not fixed it yet -- the same
237 /// deferral [`resolve`](Ref::resolve) makes, so an unresolved slot holds its reservation and shows
238 /// nothing. The page-valued arms format their number; [`IndexFolios`](Ref::IndexFolios) resolves each
239 /// occurrence's folio, deduplicates and sorts them, and joins them into the index list, a run of two or
240 /// more consecutive folios collapsing to a hyphenated range.
241 pub fn resolve_text(&self, incoming: &Ledger) -> Option<String> {
242 match self {
243 Ref::TotalPages | Ref::PageOf(_) | Ref::FolioOf(_) => self.resolve(incoming).map(|n| fmt!("{}", n)),
244 Ref::IndexFolios(ids) => {
245 let mut folios: Vec<u32> = ids.iter()
246 .filter_map(|id| Ref::FolioOf(id.clone()).resolve(incoming))
247 .collect();
248 if folios.is_empty() {
249 // Pass A (empty ledger, no body start) or no occurrence yet fixed: defer, holding the slot.
250 return None;
251 }
252 folios.sort_unstable();
253 folios.dedup();
254 Some(compress_folios(&folios))
255 },
256 }
257 }
258}
259
260/// Joins a sorted, deduplicated folio list into an index entry's page reference: a run of two or more
261/// consecutive folios collapses to `first-last`, and single folios and runs are parted by `", "`. An empty
262/// slice yields the empty string, though [`resolve_text`](Ref::resolve_text) never calls it with one.
263fn compress_folios(folios: &[u32]) -> String {
264 let mut out = String::new();
265 let mut i = 0usize;
266 while i < folios.len() {
267 let start = folios[i];
268 let mut j = i;
269 while j + 1 < folios.len() && folios[j + 1] == folios[j] + 1 {
270 j += 1;
271 }
272 if !out.is_empty() {
273 out.push_str(", ");
274 }
275 if j > i {
276 out.push_str(&fmt!("{}-{}", start, folios[j]));
277 } else {
278 out.push_str(&fmt!("{}", start));
279 }
280 i = j + 1;
281 }
282 out
283}
284
285/// The whole anchor table for one composition, plus the total page count the last page fixed.
286#[derive(Clone, Debug, Default)]
287pub struct Ledger {
288 entries: BTreeMap<AnchorId, Anchor>,
289 pub total_pages: u32,
290 // The physical page the body opens on -- the page of the first heading recorded during composition,
291 // after the cover, title, imprint and contents leaves the front matter sets. The printed folio
292 // restarts at 1 there, so a body page's folio is its physical page less `body_start_page - 1`, and a
293 // contents entry's folio is resolved through [`Ref::FolioOf`] the same way. Zero until a heading is
294 // recorded, which is the Pass A tell a folio reference reads.
295 pub body_start_page: u32,
296 // The physical page the back matter opens on -- the page carrying the bibliography marker. From there
297 // the running head is dropped and the folio centres at the foot, as the template sets its back matter.
298 // Zero when the document carries no back matter.
299 pub back_matter_start_page: u32,
300 // The region every anchor recorded from here on is stamped with, until it changes again. Body flow
301 // leaves it at the default [`Region::Body`]; laying a float's own material sets it to the float's band
302 // for that material's duration (see [`enter_region`](Self::enter_region)), so an anchor recorded through
303 // `place_line`, `place_vbox` or `place_leaf` while a float's body is laid inherits the float's band just
304 // as the float's own direct anchor does -- membership is complete, not limited to the float's top-level
305 // nodes.
306 current_region: Region,
307}
308
309impl Ledger {
310 pub fn new() -> Self {
311 Self {
312 entries: BTreeMap::new(),
313 total_pages: 0,
314 body_start_page: 0,
315 back_matter_start_page: 0,
316 current_region: Region::Body,
317 }
318 }
319
320 /// Sets the region newly recorded anchors are stamped with, returning the region it replaced so the
321 /// caller can restore it once the material that region covers has been laid. Called around a float's
322 /// body so every anchor recorded while it is laid -- direct or nested -- claims the float's band.
323 pub fn enter_region(&mut self, region: Region) -> Region {
324 std::mem::replace(&mut self.current_region, region)
325 }
326
327 /// Restores the region a matching [`enter_region`](Self::enter_region) replaced.
328 pub fn leave_region(&mut self, prev: Region) {
329 self.current_region = prev;
330 }
331
332 /// Records an anchor's placement, replacing any earlier record of the same identity within this
333 /// pass. The last placement wins because a pass overwrites a stale one as it re-lays the stream.
334 /// The anchor is stamped with the ledger's [`current_region`](Self::current_region), overriding
335 /// whatever `Anchor::new` defaulted it to, so region membership follows where the anchor was actually
336 /// recorded rather than which call site happened to record it.
337 ///
338 /// The first heading recorded fixes where the body opens, and the bibliography marker (the only
339 /// Citation-kind anchor) where the back matter does. The front matter sets only Label anchors, so the
340 /// first heading to arrive is the body's opening chapter or section -- and it is caught here, as it is
341 /// recorded, whether it reaches the driver as a top-level node (a chapter opener) or nested inside a
342 /// keep box (a `#section-banner` section's inline level-1 heading, the `DocInline` idiom). Detecting it
343 /// only among top-level nodes left the inline idiom with a zero `body_start_page`, so its front-matter
344 /// pages were mistaken for body pages and stamped with a folio and footer logo.
345 pub fn record(&mut self, mut anchor: Anchor) {
346 anchor.region = self.current_region;
347 if self.body_start_page == 0 && anchor.id.kind == AnchorKind::Heading {
348 self.body_start_page = anchor.pos.page;
349 }
350 if self.back_matter_start_page == 0 && anchor.id.kind == AnchorKind::Citation {
351 self.back_matter_start_page = anchor.pos.page;
352 }
353 self.entries.insert(anchor.id.clone(), anchor);
354 }
355
356 pub fn get(&self, id: &AnchorId) -> Option<&Anchor> {
357 self.entries.get(id)
358 }
359
360 /// Shifts every anchor on `page` belonging to `region` by `by` -- the ledger's half of a float insertion,
361 /// kept in step with [`Frame::shift_region`](crate::page::Frame::shift_region) so a reference to a body
362 /// anchor that moved for a float resolves to where the ink actually landed. An anchor in another region
363 /// is left where it sits, so membership rather than a y window decides what moves.
364 pub fn shift_region_anchors(&mut self, page: u32, by: Sp, region: Region) {
365 for anchor in self.entries.values_mut() {
366 if anchor.pos.page == page && anchor.region == region {
367 anchor.pos.y = anchor.pos.y + by;
368 }
369 }
370 }
371
372 /// As [`Ledger::shift_region_anchors`], for the anchors whose x lies in `[x0, x1)` only: the ledger's half
373 /// of a column float's insertion, which moves the material of its own column and not the columns beside
374 /// it. Columns do not overlap, so an anchor's x places it in exactly one.
375 pub fn shift_region_anchors_within(&mut self, page: u32, by: Sp, region: Region, x0: Sp, x1: Sp) {
376 for anchor in self.entries.values_mut() {
377 let p = &anchor.pos;
378 if p.page == page && anchor.region == region && p.x >= x0 && p.x < x1 {
379 anchor.pos.y = anchor.pos.y + by;
380 }
381 }
382 }
383
384 /// Every resolved anchor, in identity order -- for a caller that reports or dumps the whole table
385 /// rather than looking up one entry, such as the oracle harness's per-anchor page comparison.
386 pub fn anchors(&self) -> impl Iterator<Item = &Anchor> {
387 self.entries.values()
388 }
389
390 /// The page an anchor resolved to in this ledger, if it is known. A forward reference reads this
391 /// from the previous pass's ledger; when it is absent (the first pass) the caller reserves a
392 /// width and defers.
393 pub fn page_of(&self, id: &AnchorId) -> Option<u32> {
394 self.entries.get(id).map(|a| a.pos.page)
395 }
396
397 pub fn len(&self) -> usize {
398 self.entries.len()
399 }
400
401 pub fn is_empty(&self) -> bool {
402 self.entries.is_empty()
403 }
404
405 /// The anchors whose realised value overflowed its reservation. A non-empty result is why a third
406 /// pass is needed.
407 pub fn overflowed(&self) -> Vec<AnchorId> {
408 self.entries.values().filter(|a| a.overflowed()).map(|a| a.id.clone()).collect()
409 }
410
411 /// Every anchor that sits on a different page than it did in `prev`. Ordering by identity makes
412 /// the diff deterministic, so a report reads the same on every machine.
413 pub fn diff(&self, prev: &Ledger) -> Vec<Delta> {
414 let mut out = Vec::new();
415 for (id, anchor) in &self.entries {
416 if let Some(before) = prev.entries.get(id) {
417 if before.pos.page != anchor.pos.page {
418 out.push(Delta { id: id.clone(), from: before.pos.page, to: anchor.pos.page });
419 }
420 }
421 }
422 out
423 }
424
425 /// Has the ledger stopped moving? It is stable against `prev` when the total page count agrees
426 /// and no anchor changed page. Position within a page may still differ without forcing another
427 /// pass, because only a page change can move a forward reference's page number.
428 pub fn is_stable_against(&self, prev: &Ledger) -> bool {
429 self.total_pages == prev.total_pages
430 && self.body_start_page == prev.body_start_page
431 && self.back_matter_start_page == prev.back_matter_start_page
432 && self.diff(prev).is_empty()
433 }
434
435 /// Writes the ledger to a file as jdat text.
436 pub fn to_file<P: AsRef<std::path::Path>>(&self, path: P) -> Outcome<()> {
437 let dat = res!(self.to_dat());
438 let cfg = oxedyne_fe2o3_jdat::string::enc::EncoderConfig::<(), ()>::default();
439 let s = res!(dat.encode_string_with_config(&cfg));
440 res!(vfs::write(path.as_ref(), s.as_bytes()));
441 Ok(())
442 }
443
444 /// Reads a ledger back from a jdat file.
445 pub fn from_file<P: AsRef<std::path::Path>>(path: P) -> Outcome<Self> {
446 let s = res!(vfs::read_to_string(path.as_ref()));
447 let dat = res!(Dat::decode_string(s));
448 Self::from_dat(dat)
449 }
450}
451
452impl ToDat for Ledger {
453 fn to_dat(&self) -> Outcome<Dat> {
454 let mut anchors = Vec::with_capacity(self.entries.len());
455 for a in self.entries.values() {
456 anchors.push(res!(a.to_dat()));
457 }
458 Ok(omapdat!{
459 "total_pages" => dat!(self.total_pages),
460 "body_start_page" => dat!(self.body_start_page),
461 "back_matter_start_page" => dat!(self.back_matter_start_page),
462 "anchors" => Dat::List(anchors),
463 })
464 }
465}
466
467impl FromDat for Ledger {
468 fn from_dat(mut dat: Dat) -> Outcome<Self> {
469 if dat.kind() != Kind::OrdMap && dat.kind() != Kind::Map {
470 return Err(err!(
471 "A ledger must decode from a jdat map, found a {:?}.", dat.kind();
472 Input, Invalid, Mismatch));
473 }
474 let total_pages = try_extract_dat!(res!(dat.map_remove_must(&dat!("total_pages"))), U32);
475 // A ledger written before the front-matter offset existed carries no `body_start_page`; default it
476 // to zero so an older ledger still decodes.
477 let body_start_page = match dat.map_remove(&dat!("body_start_page")) {
478 Ok(Some(d)) => try_extract_dat!(d, U32),
479 _ => 0,
480 };
481 let back_matter_start_page = match dat.map_remove(&dat!("back_matter_start_page")) {
482 Ok(Some(d)) => try_extract_dat!(d, U32),
483 _ => 0,
484 };
485 let anchors_dat = try_extract_dat!(res!(dat.map_remove_must(&dat!("anchors"))), List);
486 let mut entries = BTreeMap::new();
487 for d in anchors_dat {
488 let a = res!(Anchor::from_dat(d));
489 entries.insert(a.id.clone(), a);
490 }
491 // A decoded ledger is never reflowed, so it needs no live region-recording state; default it as
492 // `Ledger::new` does.
493 Ok(Self { entries, total_pages, body_start_page, back_matter_start_page, current_region: Region::Body })
494 }
495}
496
497#[cfg(test)]
498mod tests {
499 use super::*;
500
501 #[test]
502 fn record_sets_body_start_on_the_first_heading() {
503 // The first heading recorded fixes the body start, whatever page it lands on and however it reached
504 // the ledger -- this is what lets a heading nested in a keep box (the inline-heading idiom) fix the
505 // body start, where detecting it only among top-level nodes left `body_start_page` zero and stamped
506 // the front-matter pages with a folio. A front-matter Label recorded first must not fix it.
507 let mut ledger = Ledger::new();
508 ledger.record(Anchor::new(
509 AnchorId::new(AnchorKind::Label, "frontmatter:contents"),
510 Position::new(3, Sp::ZERO, Sp::ZERO)));
511 assert_eq!(ledger.body_start_page, 0, "a front-matter Label does not open the body");
512
513 ledger.record(Anchor::new(
514 AnchorId::new(AnchorKind::Heading, "01-introduction"),
515 Position::new(4, Sp::ZERO, Sp::ZERO)));
516 assert_eq!(ledger.body_start_page, 4, "the first heading fixes the body start");
517
518 // A later heading does not move it: the body opens once.
519 ledger.record(Anchor::new(
520 AnchorId::new(AnchorKind::Heading, "02-server"),
521 Position::new(9, Sp::ZERO, Sp::ZERO)));
522 assert_eq!(ledger.body_start_page, 4, "a later heading leaves the body start where it was");
523 }
524
525 #[test]
526 fn record_sets_back_matter_start_on_the_citation_marker() {
527 let mut ledger = Ledger::new();
528 ledger.record(Anchor::new(
529 AnchorId::new(AnchorKind::Citation, "bibliography"),
530 Position::new(40, Sp::ZERO, Sp::ZERO)));
531 assert_eq!(ledger.back_matter_start_page, 40, "the bibliography marker opens the back matter");
532 }
533}