Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/memo.rs

10.9 KiB, 7 runs

created by r1870400018:58621, 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 incremental content-hash memo, for a live edit-and-re-render loop (Daimond's browser view).
2//!
3//! A straight recompile re-authors and re-emits the whole document on every keystroke, which is the
4//! ~15x live-view regression that blocks swapping Austenite in for the Typst-wasm compiler. This memo
5//! caches the two costly, content-addressed stages so an edit recomputes only what actually changed:
6//!
7//! * The **block authoring memo** ([`Memo::blocks`]) keys each top-level document block on its content
8//! and the counter state it enters under (heading, footnote, figure numbers; the glossary first-use
9//! set), so an unedited block splices its previously authored nodes back rather than re-shaping and
10//! re-breaking its paragraphs. It is ledger-independent: a forward reference is a `Reserved` leaf
11//! that resolves later in the pass loop, so the authored nodes never embed a page number.
12//! * The **page emit memo** ([`Memo::pages`]) keys each page on the content of its body frame -- the
13//! placed glyph runs, rules and graphics -- so an unedited page reuses its rendered SVG body and only
14//! the furniture (the running head and folio, which differ page to page) is drawn fresh.
15//!
16//! Both keys are 64-bit FNV-1a fingerprints of the content that determines the output. A fingerprint
17//! can in principle collide; at 64 bits over a single document the probability is negligible, which is
18//! the same footing every incremental compiler (Typst.ts included) rests a content cache on.
19//!
20//! **Residency and the memo's contract.** The memo holds authored nodes and rendered SVG, so it costs
21//! roughly the memory of one document copy. A two-generation sweep ([`Memo::sweep`]) drops any entry not
22//! touched in the last two compiles, bounding that to ~2x rather than growing without limit. The memo is
23//! valid only while the document's fonts, faces, page geometry and theme are unchanged -- those are
24//! folded into a single global fingerprint the caller supplies once per compile ([`Memo::begin`]); a
25//! change to any of them belongs in a fresh [`Memo`], not this one.
26
27use crate::doc::{
28 Heading,
29 Segment,
30};
31use crate::ir::Node;
32use crate::ledger::AnchorId;
33
34use std::collections::HashMap;
35
36/// A 64-bit FNV-1a accumulator. The whole memo keys on this: it is fast, allocation-free, and stable
37/// run to run, which is all a content fingerprint needs. It is not a cryptographic hash and makes no
38/// claim to be one.
39#[derive(Clone, Copy)]
40pub struct Fnv {
41 state: u64,
42}
43
44impl Fnv {
45 const OFFSET: u64 = 0xcbf29ce484222325;
46 const PRIME: u64 = 0x00000100000001b3;
47
48 pub fn new() -> Self {
49 Self { state: Self::OFFSET }
50 }
51
52 pub fn write(&mut self, bytes: &[u8]) {
53 for b in bytes {
54 self.state ^= *b as u64;
55 self.state = self.state.wrapping_mul(Self::PRIME);
56 }
57 }
58
59 pub fn write_u8(&mut self, v: u8) { self.write(&[v]); }
60 pub fn write_u32(&mut self, v: u32) { self.write(&v.to_le_bytes()); }
61 pub fn write_u64(&mut self, v: u64) { self.write(&v.to_le_bytes()); }
62 pub fn write_i32(&mut self, v: i32) { self.write(&v.to_le_bytes()); }
63 pub fn write_usize(&mut self, v: usize) { self.write(&(v as u64).to_le_bytes()); }
64 pub fn write_bool(&mut self, v: bool) { self.write_u8(v as u8); }
65
66 /// Hashes an `f32` by its bit pattern, so a coordinate hashes exactly and reproducibly. Positions
67 /// and advances are never `NaN`, so the several bit patterns of `NaN` are not a concern here.
68 pub fn write_f32(&mut self, v: f32) { self.write(&v.to_bits().to_le_bytes()); }
69
70 /// Hashes a string length-prefixed, so "ab"+"c" and "a"+"bc" do not collide.
71 pub fn write_str(&mut self, s: &str) {
72 self.write_u64(s.len() as u64);
73 self.write(s.as_bytes());
74 }
75
76 pub fn finish(self) -> u64 { self.state }
77}
78
79impl Default for Fnv {
80 fn default() -> Self { Self::new() }
81}
82
83/// The scalar authoring counters at a block boundary: the state a block enters under (its key) and the
84/// state it leaves (its value, restored on a cache hit). These are exactly the counters a block bakes
85/// into its output -- a heading's dotted number, a footnote's mark, a figure's caption number, the
86/// anchor identity keyed off `heads_len` -- so two compiles that enter a block with the same state and
87/// the same content produce byte-identical nodes.
88#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
89pub struct BlockState {
90 pub first: bool,
91 pub prev_para: bool,
92 pub pending_banner: bool,
93 pub sec: [u32; 6],
94 pub part_no: u32,
95 pub foot_no: u32,
96 pub ref_no: u32,
97 pub margin_no: u32,
98 pub eq_no: u32,
99 pub fig_no: u32,
100 pub heads_len: u32,
101 pub index_no: u32,
102}
103
104impl BlockState {
105 /// Folds the entering state into a key hasher. `heads_len` and `index_no` are in here because a
106 /// heading's and an index marker's anchor identity is keyed off them; a block whose position among
107 /// the headings has shifted must not hit.
108 pub fn hash_into(&self, h: &mut Fnv) {
109 h.write_bool(self.first);
110 h.write_bool(self.prev_para);
111 h.write_bool(self.pending_banner);
112 for s in &self.sec { h.write_u32(*s); }
113 h.write_u32(self.part_no);
114 h.write_u32(self.foot_no);
115 h.write_u32(self.ref_no);
116 h.write_u32(self.margin_no);
117 h.write_u32(self.eq_no);
118 h.write_u32(self.fig_no);
119 h.write_u32(self.heads_len);
120 h.write_u32(self.index_no);
121 }
122}
123
124/// One cached block-authoring result: the nodes the block appended, the heading and index/claim
125/// occurrences it recorded, how many source blocks it consumed (a chapter heading swallows the first
126/// line of the paragraph it introduces, so two), and the counter state it left. The glossary terms it
127/// marked first-seen and the supplement counters it stepped are stored as deltas, applied on a hit so
128/// the shared accumulators advance exactly as a fresh authoring would advance them.
129#[derive(Clone)]
130pub struct BlockEntry {
131 pub consume: usize,
132 pub nodes: Vec<Node>,
133 pub heads: Vec<Heading>,
134 pub index_occ: Vec<(String, Option<String>, Vec<Segment>, AnchorId, bool)>,
135 pub claim_occ: Vec<(String, AnchorId)>,
136 pub seen_add: Vec<String>,
137 pub counters_set: Vec<(String, u32)>,
138 pub exit: BlockState,
139 last_gen: u64, // the generation this entry was last touched, for the two-generation sweep
140}
141
142impl BlockEntry {
143 #[allow(clippy::too_many_arguments)]
144 pub fn new(
145 consume: usize,
146 nodes: Vec<Node>,
147 heads: Vec<Heading>,
148 index_occ: Vec<(String, Option<String>, Vec<Segment>, AnchorId, bool)>,
149 claim_occ: Vec<(String, AnchorId)>,
150 seen_add: Vec<String>,
151 counters_set: Vec<(String, u32)>,
152 exit: BlockState,
153 )
154 -> Self
155 {
156 Self { consume, nodes, heads, index_occ, claim_occ, seen_add, counters_set, exit, last_gen: 0 }
157 }
158}
159
160/// One cached page-emit result: the SVG of the page's body frame, split into the visible glyph and
161/// graphic ink and the invisible selectable text layer's tspans, plus whether the body left any text
162/// behind (so the furniture's tspans take their leading interword space exactly as a single-pass render
163/// would). The furniture -- running head and folio -- is never cached, since its folio differs page to
164/// page; it is drawn fresh and concatenated onto the cached body, byte for byte as one pass produces.
165#[derive(Clone)]
166pub struct PageEntry {
167 pub body_ink: String,
168 pub body_tspans: String,
169 pub seen_text: bool,
170 last_gen: u64,
171}
172
173/// The document's incremental memo: the block-authoring and page-emit caches, the global fingerprint
174/// that scopes both to one (fonts, faces, geometry, theme) configuration, the generation counter the
175/// two-generation sweep reads, and the hit/miss tallies the gate measures.
176#[derive(Default)]
177pub struct Memo {
178 blocks: HashMap<u64, BlockEntry>,
179 pages: HashMap<u64, PageEntry>,
180 global_fp: u64, // fonts+faces+geometry+theme+refs+bib fingerprint; folded into every key
181 gen: u64,
182 pub block_hits: u64,
183 pub block_misses: u64,
184 pub page_hits: u64,
185 pub page_misses: u64,
186}
187
188impl Memo {
189 pub fn new() -> Self { Self::default() }
190
191 /// Opens a compile generation: steps the generation counter (so this compile's touches are
192 /// distinguishable from the last), resets the hit/miss tallies, and installs the configuration
193 /// fingerprint. A fingerprint that differs from the one the cached entries were built under clears
194 /// both caches, since every key was scoped to the old configuration.
195 pub fn begin(&mut self, global_fp: u64) {
196 if self.global_fp != global_fp && (!self.blocks.is_empty() || !self.pages.is_empty()) {
197 self.blocks.clear();
198 self.pages.clear();
199 }
200 self.global_fp = global_fp;
201 self.gen = self.gen.wrapping_add(1);
202 self.block_hits = 0;
203 self.block_misses = 0;
204 self.page_hits = 0;
205 self.page_misses = 0;
206 }
207
208 pub fn global_fp(&self) -> u64 { self.global_fp }
209
210 /// The number of page-emit entries currently held. The changed-only delta path renders through
211 /// [`crate::emit::svg::render_page`], which never touches this cache, so a wasm delta instance keeps
212 /// this at zero: it retains the block-authoring working set (the incremental recompile) but never the
213 /// rendered page SVG (the consumer holds that). A residency assertion reads it to prove the wasm heap
214 /// does not grow with the rendered document.
215 pub fn cached_pages(&self) -> usize { self.pages.len() }
216
217 /// The number of block-authoring entries currently held -- the working set the two-generation
218 /// [`sweep`](Self::sweep) bounds to roughly one document.
219 pub fn cached_blocks(&self) -> usize { self.blocks.len() }
220
221 /// Drops every entry not touched in the current or the immediately preceding generation, so the two
222 /// caches hold at most the working sets of the last two compiles -- roughly twice the live document,
223 /// never an unbounded accumulation of stale edits.
224 pub fn sweep(&mut self) {
225 let gen = self.gen;
226 self.blocks.retain(|_, e| gen.wrapping_sub(e.last_gen) < 2);
227 self.pages.retain(|_, e| gen.wrapping_sub(e.last_gen) < 2);
228 }
229
230 // --- block authoring cache ---------------------------------------------------------------------
231
232 /// Looks a block up, returning a clone of its cached result and marking it touched this generation.
233 /// The clone releases the borrow so the caller can splice the nodes into the authoring state; a
234 /// paragraph's node clone is far cheaper than re-shaping and re-breaking it.
235 pub fn block_lookup(&mut self, key: u64) -> Option<BlockEntry> {
236 let gen = self.gen;
237 match self.blocks.get_mut(&key) {
238 Some(e) => { e.last_gen = gen; self.block_hits += 1; Some(e.clone()) },
239 None => { self.block_misses += 1; None },
240 }
241 }
242
243 pub fn block_store(&mut self, key: u64, mut entry: BlockEntry) {
244 entry.last_gen = self.gen;
245 self.blocks.insert(key, entry);
246 }
247
248 // --- page emit cache ---------------------------------------------------------------------------
249
250 pub fn page_lookup(&mut self, key: u64) -> Option<PageEntry> {
251 let gen = self.gen;
252 match self.pages.get_mut(&key) {
253 Some(e) => { e.last_gen = gen; self.page_hits += 1; Some(e.clone()) },
254 None => { self.page_misses += 1; None },
255 }
256 }
257
258 pub fn page_store(&mut self, key: u64, body_ink: String, body_tspans: String, seen_text: bool) {
259 self.pages.insert(key, PageEntry { body_ink, body_tspans, seen_text, last_gen: self.gen });
260 }
261}