//! What saving a document with many content controls costs (#13). //! //! A form-shaped document: a control per paragraph, inline, or a control around two paragraphs. //! The writer used to look for each paragraph's markers in the whole set of markers, once per //! paragraph, and to compare every control with every other one, so the save was quadratic in the //! number of controls. use std::time::Instant; use craft_docx::write; use craft_wordmodel::control::{ContentControl, ControlKind}; use craft_wordmodel::para::InlineObject; use craft_wordmodel::props::CharProps; use craft_wordmodel::{Document, Paragraph, para_block}; /// One paragraph per control, the control inline in it. fn inline_controls(n: usize) -> Document { let mut doc = Document::new(); doc.body.clear(); let props = CharProps::default(); for _ in 0..n { let mut p = Paragraph::with_text("value: ", props.clone()); let off = p.len(); p.insert_object(off, InlineObject::ControlStart { control: Box::new(ContentControl::new(ControlKind::RichText)) }, &props) .expect("insert the start marker"); let off = p.len(); p.insert_object(off, InlineObject::ControlEnd, &props).expect("insert the end marker"); doc.body.push(para_block(p)); } doc } /// Two paragraphs per control, the control written around both of them. fn block_controls(n: usize) -> Document { let mut doc = Document::new(); doc.body.clear(); let props = CharProps::default(); for _ in 0..n { let mut open = Paragraph::new(); let off = open.len(); open.insert_object(off, InlineObject::ControlStart { control: Box::new(ContentControl::new(ControlKind::RichText)) }, &props) .expect("insert the start marker"); doc.body.push(para_block(open)); let mut close = Paragraph::with_text("value", props.clone()); let off = close.len(); close.insert_object(off, InlineObject::ControlEnd, &props).expect("insert the end marker"); doc.body.push(para_block(close)); } doc } /// How much more saving the bigger document costs than the smaller one, for the bigger one /// `scale` times the size of the smaller one's: ~`scale` when linear, ~`scale`² when quadratic. /// Each is the cheapest of several runs after a warm-up, the runs alternating so a busy spell /// slows both sizes alike; the smaller document is saved `scale` times over per run, so both /// timings are long against the clock's resolution. fn cost_ratio(scale: usize, mut small: impl FnMut(), mut big: impl FnMut()) -> (f64, f64, f64) { small(); big(); let mut small_scaled = || (0..scale).for_each(|_| small()); let (mut t1, mut tk) = (f64::INFINITY, f64::INFINITY); for _ in 0..5 { let a = Instant::now(); small_scaled(); t1 = t1.min(a.elapsed().as_secs_f64() / scale as f64); let b = Instant::now(); big(); tk = tk.min(b.elapsed().as_secs_f64()); } (t1, tk, tk / t1.max(1e-9)) } /// A document with many inline content controls saves in the time the controls take: the writer /// looked for each paragraph's markers in the whole set of markers, once per paragraph, so a /// document with 32,000 controls took four seconds to save where it takes a tenth of one now. #[test] fn a_document_with_many_inline_content_controls_saves_in_linear_time() { let scale = 4; let small = inline_controls(8_000); let big = inline_controls(8_000 * scale); let (t1, tk, ratio) = cost_ratio( scale, || { write(&small).expect("write"); }, || { write(&big).expect("write"); }, ); eprintln!("t(n) {t1:.4} s, t(4n) {tk:.4} s, ratio {ratio:.1}"); assert!(ratio < 8.0, "four times the controls took {ratio:.1}x the time ({t1:.4} s → {tk:.4} s): not linear"); } /// The same for the controls written around whole paragraphs: the writer compared every control /// with every other one to find the ones that clash, so the save was quadratic in their number. #[test] fn a_document_with_many_block_content_controls_saves_in_linear_time() { let scale = 4; let small = block_controls(8_000); let big = block_controls(8_000 * scale); let (t1, tk, ratio) = cost_ratio( scale, || { write(&small).expect("write"); }, || { write(&big).expect("write"); }, ); eprintln!("t(n) {t1:.4} s, t(4n) {tk:.4} s, ratio {ratio:.1}"); assert!(ratio < 8.0, "four times the controls took {ratio:.1}x the time ({t1:.4} s → {tk:.4} s): not linear"); } /// The controls are written where they were: the plan that decides whether a control is written /// inline or around whole paragraphs gives the same answer as it did before it was made faster. #[test] fn the_controls_are_written_where_they_were() { // Inline controls: both markers in the same paragraph, so the control is written in it. let bytes = write(&inline_controls(50)).expect("write"); let back = craft_docx::read(&bytes).expect("read back"); let ranges = back.control_ranges(craft_wordmodel::StoryRef::Body); assert_eq!(ranges.len(), 50, "every control survives the round trip"); for r in &ranges { assert_eq!(r.start.path, r.end.path, "the control is written inline: {:?}", r.start.path); } // Block controls: the markers in different paragraphs, so the control is written around them. let bytes = write(&block_controls(50)).expect("write"); let back = craft_docx::read(&bytes).expect("read back"); let ranges = back.control_ranges(craft_wordmodel::StoryRef::Body); assert_eq!(ranges.len(), 50, "every control survives the round trip"); for r in &ranges { assert_ne!(r.start.path, r.end.path, "the control is written around the paragraphs"); } } /// The names of the parts of a package, in the order they are in it. fn part_names(bytes: &[u8]) -> Vec { let z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).expect("zip"); z.file_names().map(|n| n.unwrap().to_string()).collect() } /// The body of the document part of a package. fn document_body(bytes: &[u8]) -> String { let mut z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).expect("zip"); let mut xml = String::new(); { use std::io::Read; z.by_name("word/document.xml").expect("the document part").read_to_string(&mut xml).expect("read"); } let rest = xml.split_once("").expect("the body").1; let body = rest.split_once("").expect("the end of the body").0; format!("{body}") } /// A document whose controls are written in an order and a place worth pinning: two inline /// controls in one paragraph, and a control around a whole paragraph. fn pinned_doc() -> Document { let props = CharProps::default(); let mut doc = Document::new(); doc.body.clear(); // "before [a] between [b] after", the two controls inline in one paragraph. let mut p = Paragraph::with_text("before ", props.clone()); let mut at = p.len(); p.insert_object(at, InlineObject::ControlStart { control: Box::new(ContentControl::new(ControlKind::Text { multi_line: false })) }, &props) .expect("the first marker"); at = p.len(); p.insert_text(at, "inside a", &props).expect("text"); at = p.len(); p.insert_object(at, InlineObject::ControlEnd, &props).expect("the first end marker"); at = p.len(); p.insert_text(at, " between ", &props).expect("text"); at = p.len(); p.insert_object(at, InlineObject::ControlStart { control: Box::new(ContentControl::new(ControlKind::RichText)) }, &props) .expect("the second marker"); at = p.len(); p.insert_text(at, "inside b", &props).expect("text"); at = p.len(); p.insert_object(at, InlineObject::ControlEnd, &props).expect("the second end marker"); at = p.len(); p.insert_text(at, " after", &props).expect("text"); doc.body.push(para_block(p)); // A control around a whole paragraph. let mut open = Paragraph::new(); let at = open.len(); open.insert_object(at, InlineObject::ControlStart { control: Box::new(ContentControl::new(ControlKind::RichText)) }, &props) .expect("the block marker"); doc.body.push(para_block(open)); let mut inside = Paragraph::with_text("in the block", props.clone()); let at = inside.len(); inside.insert_object(at, InlineObject::ControlEnd, &props).expect("the block end marker"); doc.body.push(para_block(inside)); doc } /// The body of the document part the writer writes for [`pinned_doc`], byte for byte: what the /// writer wrote before it was made faster. The counts and the paragraphs in the test above say /// that the controls are where they belong; this says that the rest is where it was too, down to /// the order and the place of the markers inside a paragraph. /// /// The body is what the plan decides: which controls are written inline and which around whole /// paragraphs, and where. Nothing outside it can change with the plan, so it is what is pinned. /// /// Regenerate it when the writer's output changes on purpose: write [`pinned_doc`] and take the /// body of the document part. #[test] fn the_document_body_is_written_as_it_was() { let bytes = write(&pinned_doc()).expect("write"); assert_eq!(document_body(&bytes), PINNED_BODY); // The parts are the same ones, so nothing is added to the package and nothing is lost. assert_eq!(part_names(&bytes), PINNED_PARTS); } /// The body of the document part of [`pinned_doc`], as the writer wrote it before it was made /// faster. const PINNED_PARTS: &[&str] = &[ "[Content_Types].xml", "_rels/.rels", "word/document.xml", "word/_rels/document.xml.rels", "word/styles.xml", "word/settings.xml", "word/theme/theme1.xml", "docProps/core.xml", "docProps/app.xml", ]; const PINNED_BODY: &str = r#"before inside a between inside b afterin the block"#;