Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/tests/delta.rs

22.6 KiB, 9 runs

created by r1870400018:58774, 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 changed-only page delta, proved on the native compile path.
2//!
3//! The master goal is to swap Austenite in for Daimond's Typst-wasm compiler. The emit memo (see
4//! `tests/memo.rs`) buys back the CPU of a per-keystroke recompile; this layer buys back the MEMORY and the
5//! wire cost, by returning only the pages whose rendered SVG has changed since the consumer's last-known
6//! set, keyed by a stable page-content id (see [`oxedyne_fe2o3_austenite::delta`]). These tests hold that
7//! layer to the properties the consumer contract rests on: a first compile is a full reset; an unchanged
8//! recompile sends nothing; a warm edit sends only the pages that genuinely changed; an inserted page
9//! resends only itself and not every page after it (the id-vs-position claim); and the state kept between
10//! compiles is the id list alone, never the rendered SVG.
11//!
12//! The wasm return shape is a thin marshal of this same [`delta::compute`] result, so unit-testing the
13//! delta logic over real (and synthetic) pages here proves the browser behaviour without a browser. Each
14//! test passes the prior id set explicitly, exactly as the wasm surface passes the consumer's supplied
15//! `known` ids: the compiler holds no prior set of its own, so the boundary these tests exercise is the
16//! real one.
17
18use oxedyne_fe2o3_austenite::compile::{
19 author_and_run,
20 author_and_run_memo,
21 Assembled,
22};
23use oxedyne_fe2o3_austenite::delta;
24use oxedyne_fe2o3_austenite::doc::Block;
25use oxedyne_fe2o3_austenite::emit::svg;
26use oxedyne_fe2o3_austenite::fonts::{
27 self,
28 FaceResolver,
29};
30use oxedyne_fe2o3_austenite::memo::Memo;
31use oxedyne_fe2o3_austenite::ir::{
32 Dims,
33 Sp,
34};
35use oxedyne_fe2o3_austenite::page::{
36 Frame,
37 Page,
38 PageGeometry,
39 Placed,
40 PlacedKind,
41};
42use oxedyne_fe2o3_austenite::theme::Theme;
43
44use oxedyne_fe2o3_core::prelude::*;
45
46use std::collections::HashSet;
47use std::sync::Arc;
48use std::time::Instant;
49
50// ┌───────────────────────────────────────────────────────────────────────────┐
51// │ REAL COMPILE FIXTURES │
52// └───────────────────────────────────────────────────────────────────────────┘
53
54/// A deterministic body of prose paragraphs, each unique per index so no two pages coincide by accident.
55/// `edit_at` rewrites one paragraph, standing in for the one edit a keystroke makes; `None` is untouched.
56fn build_doc(n: usize, edit_at: Option<usize>) -> Vec<Block> {
57 let words = [
58 "typesetting", "streams", "a", "document", "through", "two", "passes", "of", "the", "driver",
59 "while", "the", "ledger", "resolves", "each", "anchor", "into", "the", "page", "it", "landed",
60 "on", "and", "the", "breaker", "sets", "every", "justified", "line", "to", "the", "measure",
61 "without", "a", "single", "floating", "point", "along", "the", "way", "so", "the", "build",
62 ];
63 let mut blocks = Vec::with_capacity(n);
64 for k in 0..n {
65 let edited = edit_at == Some(k);
66 let seed = if edited { k * 7 + 3 } else { k * 5 + 1 };
67 let count = 34 + (seed % 20);
68 let mut s = fmt!("Paragraph{}{}.", k, if edited { "edited" } else { "" });
69 for i in 0..count {
70 s.push(' ');
71 s.push_str(words[(seed + i * 3) % words.len()]);
72 }
73 s.push('.');
74 blocks.push(Block::paragraph(s));
75 }
76 blocks
77}
78
79/// Authors and runs a document to its resolved pages -- the same pipeline the wasm delta path drives, minus
80/// the emit (the delta renders each page itself, only when its id is new).
81fn compile_pages(blocks: Vec<Block>) -> Outcome<Vec<Page>> {
82 let fonts = Arc::new(res!(fonts::libertinus()));
83 let assembled = Assembled {
84 blocks,
85 fonts,
86 geom: PageGeometry::a4(),
87 style: Theme::default(),
88 title: String::new(),
89 faces: FaceResolver::default(),
90 front: None,
91 bib: None,
92 };
93 Ok(res!(author_and_run(assembled)).out.pages)
94}
95
96/// The first compile resets and carries every page: `reset` is true, `version` steps to one, `order` names
97/// every page, and `changed` carries the SVG of each (all page ids distinct, since each page's folio and
98/// body differ).
99#[test]
100fn first_compile_resets_and_sends_every_page() -> Outcome<()> {
101 let pages = res!(compile_pages(build_doc(24, None)));
102 assert!(pages.len() > 1, "the fixture must paginate over several pages, found {}", pages.len());
103
104 let d = res!(delta::compute(&pages, &[], 0));
105
106 assert!(d.reset, "the first compile against an empty prior set is a reset");
107 assert_eq!(d.version, 1, "the version steps from zero to one on the first compile");
108 assert_eq!(d.order.len(), pages.len(), "order names every page");
109 assert_eq!(d.changed.len(), d.order.len(),
110 "a reset carries every page's SVG, found {} changed for {} pages", d.changed.len(), d.order.len());
111 // Every id in order is carried in changed, and each changed entry's SVG is the real page SVG.
112 let carried: HashSet<u64> = d.changed.iter().map(|(id, _)| *id).collect();
113 for id in &d.order {
114 assert!(carried.contains(id), "every ordered id is carried on a reset");
115 }
116 Ok(())
117}
118
119/// Recompiling identical source sends nothing: `reset` is false, `order` is unchanged, `changed` is empty,
120/// and `version` still steps. This is the idle keystroke -- a compile that produced the same bytes.
121#[test]
122fn identical_recompile_sends_nothing() -> Outcome<()> {
123 let first = res!(compile_pages(build_doc(24, None)));
124 let d1 = res!(delta::compute(&first, &[], 0));
125
126 let second = res!(compile_pages(build_doc(24, None)));
127 let d2 = res!(delta::compute(&second, &d1.order, d1.version));
128
129 assert!(!d2.reset, "a recompile against a non-empty prior set is not a reset");
130 assert_eq!(d2.version, 2, "the version steps on every compile, idle or not");
131 assert_eq!(d2.order, d1.order, "identical source yields the identical id sequence");
132 assert!(d2.changed.is_empty(),
133 "an unchanged recompile resends nothing, found {} changed", d2.changed.len());
134 Ok(())
135}
136
137/// The audit blocker: the consumer -- not the compiler -- owns the SVG cache, and clears it on a document
138/// close or switch. A recompile after that clear must be told to resend everything (`reset`, full
139/// `changed`), NOT that nothing changed against the prior ids -- which would leave the emptied cache with no
140/// SVG for any id and a blank preview it could never recover from. Modelled by supplying an empty `known`
141/// (the consumer's now-empty cache) though the source, and so the pages and their ids, are identical to the
142/// priming compile. Were the prior set held in the compiler instead of supplied here, this would return
143/// `changed: []` and the assertion below would fail.
144#[test]
145fn a_cleared_cache_forces_a_full_resend() -> Outcome<()> {
146 let pages = res!(compile_pages(build_doc(24, None)));
147 let d1 = res!(delta::compute(&pages, &[], 0));
148 assert!(!d1.changed.is_empty(), "the priming compile sends the pages");
149
150 // The consumer closed the document: its cache is empty, so it supplies no known ids on reopen.
151 let reopened = res!(compile_pages(build_doc(24, None)));
152 let d2 = res!(delta::compute(&reopened, &[], d1.version));
153
154 assert!(d2.reset, "a recompile against an empty known set is a reset -- the recovery");
155 assert_eq!(d2.changed.len(), d2.order.len(),
156 "a cleared cache must be resent in full, not told nothing changed: {} changed of {} pages",
157 d2.changed.len(), d2.order.len());
158 assert!(d2.version > d1.version, "the version still steps monotonically across the clear");
159 Ok(())
160}
161
162/// A warm edit late in the document resends only the pages whose SVG genuinely changed: the leading pages
163/// -- unchanged in body and in folio -- keep their ids and are absent from `changed`, while the edited page
164/// and the pagination cascade below it carry new ids that appear in `changed`.
165#[test]
166fn warm_edit_sends_only_the_changed_pages() -> Outcome<()> {
167 let n = 24;
168 let edit_at = 20; // late, so many earlier pages fall outside the cascade
169
170 let orig = res!(compile_pages(build_doc(n, None)));
171 let d1 = res!(delta::compute(&orig, &[], 0));
172
173 let edited = res!(compile_pages(build_doc(n, Some(edit_at))));
174 let d2 = res!(delta::compute(&edited, &d1.order, d1.version));
175
176 assert!(!d2.reset, "the warm edit is not a reset");
177 assert_eq!(d2.version, 2, "the version steps to two");
178
179 // The edit really changes something, but not everything: some pages are resent, some are not.
180 assert!(!d2.changed.is_empty(), "the edit must resend at least the edited page");
181 assert!(d2.changed.len() < d2.order.len(),
182 "a late edit must leave earlier pages untouched: {} changed of {} pages",
183 d2.changed.len(), d2.order.len());
184
185 // changed carries exactly the ids new against the prior set -- no page the consumer already holds.
186 let prior: HashSet<u64> = d1.order.iter().copied().collect();
187 for (id, _) in &d2.changed {
188 assert!(!prior.contains(id), "a resent page's id must be new against the prior set");
189 }
190
191 // The leading pages before the edit are byte-identical (same body, same folio), so their ids survive
192 // into the new order and are NOT resent -- the changed-only property, proved non-vacuously against the
193 // real cold renders of both documents.
194 let leading_shared = d1.order.iter().zip(d2.order.iter()).take_while(|(a, b)| a == b).count();
195 assert!(leading_shared > 0, "the edit must leave at least one leading page untouched");
196 let resent: HashSet<u64> = d2.changed.iter().map(|(id, _)| *id).collect();
197 for id in d2.order.iter().take(leading_shared) {
198 assert!(!resent.contains(id), "an unchanged leading page must not be resent");
199 }
200 Ok(())
201}
202
203// ┌───────────────────────────────────────────────────────────────────────────┐
204// │ THE ID-VS-POSITION CLAIM (synthetic pages) │
205// └───────────────────────────────────────────────────────────────────────────┘
206//
207// The core correctness claim is that the delta keys on a page's CONTENT, not its ordinal position. A
208// content-free fixture isolates that claim: each page here carries one rule of a distinct width, so its id
209// and its SVG depend on its content alone and not on any folio furniture. (A real folio'd document would
210// resend a shifted page too -- correctly, since its printed folio, and so its rendered SVG, genuinely
211// changes; that is the whole-frame keying the real-compile tests above exercise. Here the furniture is
212// removed so the content-vs-position distinction stands alone.)
213
214/// A synthetic page carrying one rule whose width encodes its identity: distinct `tag` gives distinct
215/// content, so a distinct id and a distinct SVG, with no folio furniture in the frame.
216fn rule_page(number: u32, geom: PageGeometry, tag: i32) -> Page {
217 let mut frame = Frame::new();
218 let dims = Dims::new(Sp::from_pt(100.0 + tag as f64), Sp::from_pt(10.0), Sp::ZERO);
219 frame.push(Placed::new(Sp::from_pt(60.0), Sp::from_pt(80.0), dims, PlacedKind::Rule));
220 Page::new(number, geom, frame)
221}
222
223/// How many slots a POSITION-keyed cache would resend: a page at index `i` is compared with whatever the
224/// prior compile held at index `i`, so a page that merely moved to a new index counts as changed. This is
225/// the strawman the content-keyed delta must beat, computed here so the beat is a measured fact.
226fn positional_resends(prior: &[Page], now: &[Page]) -> Outcome<usize> {
227 let mut n = 0;
228 for (i, page) in now.iter().enumerate() {
229 let same = match prior.get(i) {
230 Some(p) => res!(svg::render_page(p)) == res!(svg::render_page(page)),
231 None => false, // a new slot the prior compile never held
232 };
233 if !same { n += 1; }
234 }
235 Ok(n)
236}
237
238/// Inserting a page near the front resends only the inserted page. Every later page shifts position but
239/// keeps its content, so its id is unchanged and it is not resent -- whereas a position-keyed cache would
240/// resend every page from the insertion point on. This is the load-bearing proof that the id keys on
241/// content, not position: it FAILS under positional keying, and the test measures exactly that.
242#[test]
243fn inserting_a_page_resends_only_the_inserted_page() -> Outcome<()> {
244 let geom = PageGeometry::a4();
245
246 // Four distinct pages, first compiled cold.
247 let before: Vec<Page> = (0..4).map(|k| rule_page(k as u32 + 1, geom, 10 * (k + 1))).collect();
248 let d1 = res!(delta::compute(&before, &[], 0));
249 assert!(d1.reset, "the first compile resets");
250 assert_eq!(d1.changed.len(), 4, "all four pages are sent cold");
251
252 // Insert a fresh page at the front; the four originals follow, unchanged in content, renumbered.
253 let mut after: Vec<Page> = Vec::new();
254 after.push(rule_page(1, geom, 999)); // the inserted page, a width no original uses
255 for (k, tag) in [10, 20, 30, 40].iter().enumerate() {
256 after.push(rule_page(k as u32 + 2, geom, *tag));
257 }
258
259 let d2 = res!(delta::compute(&after, &d1.order, d1.version));
260
261 assert!(!d2.reset, "the insert is a warm compile, not a reset");
262 assert_eq!(d2.order.len(), 5, "order now names five pages");
263 // The four originals' ids survive into the new order (shifted one slot right), proving id-by-content.
264 assert_eq!(&d2.order[1..], &d1.order[..],
265 "every original page keeps its content id when it shifts position");
266 // Only the inserted page is resent.
267 assert_eq!(d2.changed.len(), 1,
268 "exactly one page -- the inserted one -- is resent, found {} changed", d2.changed.len());
269 let prior: HashSet<u64> = d1.order.iter().copied().collect();
270 assert!(!prior.contains(&d2.changed[0].0), "the resent page's id is genuinely new");
271 assert_eq!(d2.changed[0].0, d2.order[0], "the resent page is the one at the front of the order");
272
273 // The non-vacuous proof: a position-keyed cache would have resent all five slots (the front slot's page
274 // changed, and every following slot now holds a page different from the one it held before). The
275 // content-keyed delta resends one. If the delta keyed on position, this test's `changed.len() == 1`
276 // above would instead be five, so the assertion is load-bearing on the id-by-content design.
277 let positional = res!(positional_resends(&before, &after));
278 assert_eq!(positional, 5, "positional keying would resend every slot, the strawman we beat");
279 assert!(d2.changed.len() < positional,
280 "content keying ({}) must resend fewer than positional keying ({})", d2.changed.len(), positional);
281 Ok(())
282}
283
284/// The state kept between compiles is the id list alone, never the rendered SVG. The retained `order` is a
285/// `Vec<u64>`: its backing store is exactly eight bytes per page (a 64-bit id), independent of how large
286/// each page's SVG is. Were it ever changed to retain the SVG (a `Vec<String>` or `Vec<(u64, String)>`),
287/// each element would be at least a `String`'s 24 bytes and this assertion would fail.
288#[test]
289fn retained_state_is_ids_only() -> Outcome<()> {
290 let pages = res!(compile_pages(build_doc(16, None)));
291 let d = res!(delta::compute(&pages, &[], 0));
292
293 assert_eq!(core::mem::size_of::<u64>(), 8, "a retained id is a bare 64-bit value");
294 assert_eq!(
295 core::mem::size_of_val(d.order.as_slice()),
296 d.order.len() * core::mem::size_of::<u64>(),
297 "the retained order holds one 8-byte id per page and no SVG");
298 // The SVG that WAS rendered lives only in `changed`, to be handed over and dropped -- it is not reachable
299 // from anything a caller would keep (`order`), which is the residency the swap depends on.
300 assert!(!d.changed.is_empty(), "the reset rendered pages into changed, to be sent and then dropped");
301 Ok(())
302}
303
304// ┌───────────────────────────────────────────────────────────────────────────┐
305// │ THE WASM DELTA PATH: PERSISTENT BLOCK MEMO + PAGE-SVG RESIDENCY │
306// └───────────────────────────────────────────────────────────────────────────┘
307//
308// The delta path the browser drives is `author_and_run_memo(Some(&mut memo))` -> `delta::compute` ->
309// `memo.sweep()`: the block-authoring memo is retained across recompiles (so an unedited block splices its
310// cached layout -- the incremental recompile), while each changed page is rendered through
311// `svg::render_page`, NOT the page-emit memo. These tests hold that path to the two properties the swap
312// rests on: a warm recompile is byte-identical to a cold compile of the edited source, and the retained
313// heap holds the block working set alone -- never a page's rendered SVG (the consumer holds those).
314
315/// Authors and runs a document to its resolved pages through the memo, exactly as the wasm delta path does:
316/// `author_and_run_memo` threads the block memo through authoring, and the pages are returned for the delta
317/// to render itself (through `svg::render_page`, not the page-emit memo). `None` is the cold, un-memoised
318/// compile -- the byte reference and the straight-swap latency baseline.
319fn author_pages(blocks: Vec<Block>, memo: Option<&mut Memo>) -> Outcome<Vec<Page>> {
320 let fonts = Arc::new(res!(fonts::libertinus()));
321 let assembled = Assembled {
322 blocks,
323 fonts,
324 geom: PageGeometry::a4(),
325 style: Theme::default(),
326 title: String::new(),
327 faces: FaceResolver::default(),
328 front: None,
329 bib: None,
330 };
331 Ok(res!(author_and_run_memo(assembled, memo)).out.pages)
332}
333
334/// The whole delta contract in one test: priming the memo on the original, then warm-recompiling a
335/// one-block edit, must (1) render byte-identical pages to a cold compile of the edited source, (2) hit the
336/// block-authoring cache on every block but the edited one, and (3) leave the page-emit cache untouched --
337/// the residency invariant that keeps the wasm heap holding the block working set, never the rendered
338/// document. The delta itself must resend only the pages the edit reached.
339#[test]
340fn the_delta_path_reuses_blocks_and_never_retains_page_svg() -> Outcome<()> {
341 let n = 40;
342 let edit_at = 34; // late, so many earlier pages fall outside the pagination cascade
343
344 // The cold reference: the edited source compiled with no memo, rendered whole (the straight swap).
345 let cold_pages = res!(author_pages(build_doc(n, Some(edit_at)), None));
346 let cold_svgs: Vec<String> = res!(cold_pages.iter().map(svg::render_page).collect());
347
348 // Prime the memo on the original document -- the first open, before the edit loop.
349 let mut memo = Memo::new();
350 let orig_pages = res!(author_pages(build_doc(n, None), Some(&mut memo)));
351 let d1 = res!(delta::compute(&orig_pages, &[], 0));
352 memo.sweep();
353 assert_eq!(memo.cached_pages(), 0, "priming through the delta path fills no page-emit entry");
354 assert_eq!(memo.page_hits + memo.page_misses, 0, "the page-emit memo is never consulted on the delta path");
355
356 // Warm recompile the edited source, the consumer's prior ids being the priming compile's order.
357 let warm_pages = res!(author_pages(build_doc(n, Some(edit_at)), Some(&mut memo)));
358 let d2 = res!(delta::compute(&warm_pages, &d1.order, d1.version));
359 memo.sweep();
360
361 // (1) Byte identity: the memo must not change one output byte of any page.
362 let warm_svgs: Vec<String> = res!(warm_pages.iter().map(svg::render_page).collect());
363 assert_eq!(warm_svgs, cold_svgs,
364 "a warm memo recompile must render byte-identical pages to a cold compile of the edited source");
365
366 // (2) The block-authoring cache: only the edited block misses (Memo::begin resets the tallies each
367 // compile, so these count the warm recompile alone).
368 assert_eq!(memo.block_misses, 1,
369 "only the one edited block should miss the authoring cache, found {}", memo.block_misses);
370 assert_eq!(memo.block_hits as usize, n - 1,
371 "every block but the edited one should hit, found {}", memo.block_hits);
372
373 // (3) Residency: the page-emit cache is STILL empty and was never consulted, so the retained heap holds
374 // blocks alone -- the bounded working set the two-generation sweep keeps -- never a page's rendered SVG.
375 assert_eq!(memo.cached_pages(), 0,
376 "the wasm delta path must never retain a page's SVG in the memo, found {} entries", memo.cached_pages());
377 assert_eq!(memo.page_hits + memo.page_misses, 0, "the page-emit memo stays unconsulted across recompiles");
378 assert!(memo.cached_blocks() <= n + 2,
379 "the block cache is bounded to roughly the document, found {} for {} blocks", memo.cached_blocks(), n);
380
381 // The delta resends only the pages the edit reached, not the whole document.
382 assert!(!d2.changed.is_empty() && d2.changed.len() < d2.order.len(),
383 "a late edit resends only its cascade: {} changed of {} pages", d2.changed.len(), d2.order.len());
384 Ok(())
385}
386
387/// The number the swap rests on: the warm live-view recompile the delta path pays per keystroke against the
388/// cold full compile a straight Typst-wasm swap would pay. Cold authors and renders the whole document; warm
389/// reuses the block cache and renders only the changed pages. Not an assertion -- machines differ -- but it
390/// prints the speedup daimond-a needs. Run with `--nocapture` to read it.
391#[test]
392fn measure_delta_cold_versus_warm_recompile() -> Outcome<()> {
393 let n = 260;
394 let edit_at = 130;
395
396 // Cold: a full compile with no memo, rendering every page -- the latency a straight swap pays each edit.
397 let t0 = Instant::now();
398 let cold = res!(author_pages(build_doc(n, Some(edit_at)), None));
399 let cold_svgs: Vec<String> = res!(cold.iter().map(svg::render_page).collect());
400 let cold_ms = t0.elapsed().as_secs_f64() * 1000.0;
401
402 // Prime the memo on the original document (the first open, not the edit loop).
403 let mut memo = Memo::new();
404 let orig = res!(author_pages(build_doc(n, None), Some(&mut memo)));
405 let d1 = res!(delta::compute(&orig, &[], 0));
406 memo.sweep();
407
408 // Warm: the edit-and-re-render a keystroke triggers -- reuse the block cache, render only changed pages.
409 let t1 = Instant::now();
410 let warm = res!(author_pages(build_doc(n, Some(edit_at)), Some(&mut memo)));
411 let d2 = res!(delta::compute(&warm, &d1.order, d1.version));
412 let warm_ms = t1.elapsed().as_secs_f64() * 1000.0;
413 memo.sweep();
414
415 // The warm pages must still be byte-identical to the cold render of the edited source.
416 let warm_svgs: Vec<String> = res!(warm.iter().map(svg::render_page).collect());
417 assert_eq!(warm_svgs, cold_svgs, "the measured warm recompile must still be byte-identical");
418 assert_eq!(memo.cached_pages(), 0, "the measurement path retains no page SVG either");
419
420 eprintln!(
421 "[delta] {} pages: cold {:.1} ms, warm {:.1} ms, speedup {:.1}x (block {}/{} hit, {} of {} pages resent)",
422 cold.len(), cold_ms, warm_ms, cold_ms / warm_ms.max(0.001),
423 memo.block_hits, n - 1, d2.changed.len(), d2.order.len());
424 Ok(())
425}