1use std::collections::BTreeMap;
35
36use super::print::datum;
37use super::{sheet_prefix, Row, Sink, Source, Value, Visibility};
38use crate::form::Form;
39use crate::intrinsics::fold;
40use crate::messages::Refusal;
41use crate::printer::write_datum;
42use crate::sheet::{cell_ref, parse_a1_range};
43
44fn quoted(s: &str) -> String {
45 write_datum(&Form::string(s))
46}
47
48#[derive(Clone, Copy, Debug, PartialEq, Eq)]
50pub enum Change<'r> {
51 SheetRemoved { name: &'r str, state: Visibility },
53 SheetAdded { name: &'r str, state: Visibility },
55 SheetChanged {
57 name: &'r str,
58 old: Visibility,
59 new: Visibility,
60 },
61 Changed {
64 key: &'r str,
65 old: &'r str,
66 new: &'r str,
67 },
68}
69
70pub trait ChangeSink {
72 fn change(&mut self, change: &Change<'_>);
73}
74
75pub struct Discard;
77
78impl ChangeSink for Discard {
79 fn change(&mut self, _change: &Change<'_>) {}
80}
81
82#[derive(Default)]
84pub struct Lines {
85 pub out: String,
86}
87
88impl ChangeSink for Lines {
89 fn change(&mut self, change: &Change<'_>) {
90 self.out.push_str(&line(change));
91 self.out.push('\n');
92 }
93}
94
95pub fn line(change: &Change<'_>) -> String {
97 match change {
98 Change::SheetRemoved { name, state } => {
99 format!("(sheet-removed {} {})", quoted(name), state.word())
100 }
101 Change::SheetAdded { name, state } => {
102 format!("(sheet-added {} {})", quoted(name), state.word())
103 }
104 Change::SheetChanged { name, old, new } => format!(
105 "(sheet-changed {} {} {})",
106 quoted(name),
107 old.word(),
108 new.word()
109 ),
110 Change::Changed { key, old, new } => format!("(changed {} {} {})", quoted(key), old, new),
111 }
112}
113
114#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
116pub struct DiffStats {
117 pub sheets_removed: u64,
118 pub sheets_added: u64,
119 pub sheets_changed: u64,
120 pub names: u64,
122 pub tables: u64,
124 pub cells: u64,
126 pub compared: u64,
128}
129
130impl DiffStats {
131 pub fn line(&self) -> String {
133 format!(
134 "sheets-removed {} sheets-added {} sheets-changed {} names {} tables {} cells {} compared {}",
135 self.sheets_removed,
136 self.sheets_added,
137 self.sheets_changed,
138 self.names,
139 self.tables,
140 self.cells,
141 self.compared
142 )
143 }
144
145 pub fn differ(&self) -> bool {
147 self.sheets_removed
148 + self.sheets_added
149 + self.sheets_changed
150 + self.names
151 + self.tables
152 + self.cells
153 > 0
154 }
155}
156
157#[derive(Clone, Debug, Default, PartialEq, Eq)]
159struct CellState {
160 value: Option<Value>,
161 formula: Option<String>,
162}
163
164#[derive(Default)]
166struct SheetCells {
167 cells: BTreeMap<(u32, u32), CellState>,
168}
169
170impl Sink for SheetCells {
171 fn row(&mut self, row: &Row<'_>) {
172 match row {
173 Row::Cell { addr, value, .. } => {
174 if let Some(a) = parse_a1_range(addr) {
175 self.cells.entry((a.top, a.left)).or_default().value = Some((*value).clone());
176 }
177 }
178 Row::Formula { addr, text, .. } => {
179 if let Some(a) = parse_a1_range(addr) {
180 self.cells.entry((a.top, a.left)).or_default().formula =
181 Some((*text).to_string());
182 }
183 }
184 _ => {}
185 }
186 }
187}
188
189fn same_value(a: &Value, b: &Value) -> bool {
192 match (a, b) {
193 (Value::Number(x), Value::Number(y)) => match (x.parse::<f64>(), y.parse::<f64>()) {
194 (Ok(p), Ok(q)) => p == q,
195 _ => x == y,
196 },
197 _ => a == b,
198 }
199}
200
201fn same_cell(a: Option<&CellState>, b: Option<&CellState>) -> bool {
202 match (a, b) {
203 (None, None) => true,
204 (Some(a), Some(b)) => {
205 a.formula == b.formula
206 && match (&a.value, &b.value) {
207 (None, None) => true,
208 (Some(x), Some(y)) => same_value(x, y),
209 _ => false,
210 }
211 }
212 _ => false,
213 }
214}
215
216fn side(state: Option<&CellState>) -> String {
219 match state {
220 Some(CellState {
221 value,
222 formula: Some(text),
223 }) => match value {
224 Some(v) => format!("(formula {} {})", quoted(text), datum(v)),
225 None => format!("(formula {})", quoted(text)),
226 },
227 Some(CellState {
228 value: Some(v),
229 formula: None,
230 }) => datum(v),
231 _ => "blank".to_string(),
232 }
233}
234
235fn text_side(text: Option<&str>) -> String {
237 match text {
238 Some(t) => quoted(t),
239 None => "blank".to_string(),
240 }
241}
242
243#[derive(Default)]
245struct Sides {
246 key: String,
248 old: Option<String>,
249 new: Option<String>,
250 table: bool,
251}
252
253pub fn diff(
257 old: &dyn Source,
258 new: &dyn Source,
259 sink: &mut dyn ChangeSink,
260) -> Result<DiffStats, Refusal> {
261 let mut stats = DiffStats::default();
262 let old_sheets = old.sheets();
263 let new_sheets = new.sheets();
264 let matched: Vec<Option<usize>> = new_sheets
266 .iter()
267 .map(|s| {
268 let wanted = fold(&s.name);
269 old_sheets.iter().position(|o| fold(&o.name) == wanted)
270 })
271 .collect();
272 for (i, s) in old_sheets.iter().enumerate() {
273 if !matched.contains(&Some(i)) {
274 stats.sheets_removed += 1;
275 sink.change(&Change::SheetRemoved {
276 name: &s.name,
277 state: s.visibility,
278 });
279 }
280 }
281 for (j, s) in new_sheets.iter().enumerate() {
282 if matched[j].is_none() {
283 stats.sheets_added += 1;
284 sink.change(&Change::SheetAdded {
285 name: &s.name,
286 state: s.visibility,
287 });
288 }
289 }
290 for (j, s) in new_sheets.iter().enumerate() {
291 if let Some(i) = matched[j] {
292 if old_sheets[i].visibility != s.visibility {
293 stats.sheets_changed += 1;
294 sink.change(&Change::SheetChanged {
295 name: &s.name,
296 old: old_sheets[i].visibility,
297 new: s.visibility,
298 });
299 }
300 }
301 }
302 let mut keyed: BTreeMap<String, Sides> = BTreeMap::new();
305 for (package, is_new) in [(old, false), (new, true)] {
306 for n in package.names().iter().filter(|n| !n.placeholder) {
307 let key = package.printed_name(n);
308 let e = keyed.entry(fold(&key)).or_default();
309 e.key = key;
310 if is_new {
311 e.new = Some(n.refers_to.clone());
312 } else {
313 e.old = Some(n.refers_to.clone());
314 }
315 }
316 for t in package.tables() {
317 let place = format!(
318 "{}!{}",
319 sheet_prefix(&package.sheets()[t.sheet].name),
320 t.range
321 );
322 let e = keyed.entry(fold(&t.name)).or_default();
323 e.key = t.name.clone();
324 e.table = true;
325 if is_new {
326 e.new = Some(place);
327 } else {
328 e.old = Some(place);
329 }
330 }
331 }
332 for sides in keyed.values() {
333 if sides.old != sides.new {
334 if sides.table {
335 stats.tables += 1;
336 } else {
337 stats.names += 1;
338 }
339 sink.change(&Change::Changed {
340 key: &sides.key,
341 old: &text_side(sides.old.as_deref()),
342 new: &text_side(sides.new.as_deref()),
343 });
344 }
345 }
346 for (j, s) in new_sheets.iter().enumerate() {
348 let Some(i) = matched[j] else {
349 continue;
350 };
351 let mut before = SheetCells::default();
352 old.walk_sheet(i, &mut before)?;
353 let mut after = SheetCells::default();
354 new.walk_sheet(j, &mut after)?;
355 let prefix = sheet_prefix(&s.name);
356 let mut at: Vec<(u32, u32)> = before
357 .cells
358 .keys()
359 .chain(after.cells.keys())
360 .copied()
361 .collect();
362 at.sort_unstable();
363 at.dedup();
364 stats.compared += at.len() as u64;
365 for (row, col) in at {
366 let a = before.cells.get(&(row, col));
367 let b = after.cells.get(&(row, col));
368 if same_cell(a, b) {
369 continue;
370 }
371 stats.cells += 1;
372 let key = format!("{prefix}!{}", cell_ref(row, col));
373 sink.change(&Change::Changed {
374 key: &key,
375 old: &side(a),
376 new: &side(b),
377 });
378 }
379 }
380 Ok(stats)
381}
382
383pub fn diff_text(
387 old_bytes: &[u8],
388 old_label: &str,
389 new_bytes: &[u8],
390 new_label: &str,
391) -> Result<String, Refusal> {
392 let old = super::open(old_bytes, old_label)?;
393 let new = super::open(new_bytes, new_label)?;
394 let mut lines = Lines::default();
395 diff(old.as_ref(), new.as_ref(), &mut lines)?;
396 Ok(lines.out)
397}
398
399#[cfg(test)]
400mod tests {
401 use super::*;
402 use crate::reflect::ooxml::Package;
403 use crate::sheet::zip;
404
405 const NS: &str = "xmlns=\"http://schemas.openxmlformats.org/spreadsheetml/2006/main\" xmlns:r=\"http://schemas.openxmlformats.org/officeDocument/2006/relationships\"";
406 const REL: &str = "http://schemas.openxmlformats.org/officeDocument/2006/relationships";
407
408 fn package_bytes(sheets: &str, names: &str, model_rows: &str, table_ref: &str) -> Vec<u8> {
411 let parts: Vec<(String, Vec<u8>)> = vec![
412 (
413 "xl/workbook.xml".to_string(),
414 format!("<workbook {NS}><sheets>{sheets}</sheets><definedNames>{names}</definedNames></workbook>").into_bytes(),
415 ),
416 (
417 "xl/_rels/workbook.xml.rels".to_string(),
418 format!("<Relationships><Relationship Id=\"rId1\" Type=\"{REL}/worksheet\" Target=\"worksheets/sheet1.xml\"/><Relationship Id=\"rId2\" Type=\"{REL}/worksheet\" Target=\"worksheets/sheet2.xml\"/><Relationship Id=\"rId3\" Type=\"{REL}/worksheet\" Target=\"worksheets/sheet3.xml\"/></Relationships>").into_bytes(),
419 ),
420 (
421 "xl/worksheets/sheet1.xml".to_string(),
422 format!("<worksheet {NS}><sheetData><row r=\"1\">{model_rows}</row></sheetData><tableParts count=\"1\"><tablePart r:id=\"rId1\"/></tableParts></worksheet>").into_bytes(),
423 ),
424 (
425 "xl/worksheets/_rels/sheet1.xml.rels".to_string(),
426 format!("<Relationships><Relationship Id=\"rId1\" Type=\"{REL}/table\" Target=\"../tables/table1.xml\"/></Relationships>").into_bytes(),
427 ),
428 (
429 "xl/worksheets/sheet2.xml".to_string(),
430 format!("<worksheet {NS}><sheetData><row r=\"1\"><c r=\"A1\"><v>1</v></c></row></sheetData></worksheet>").into_bytes(),
431 ),
432 (
433 "xl/worksheets/sheet3.xml".to_string(),
434 format!("<worksheet {NS}><sheetData><row r=\"1\"><c r=\"A1\"><v>2</v></c></row></sheetData></worksheet>").into_bytes(),
435 ),
436 (
437 "xl/tables/table1.xml".to_string(),
438 format!("<table {NS} id=\"1\" name=\"T\" displayName=\"T\" ref=\"{table_ref}\"><tableColumns count=\"2\"><tableColumn id=\"1\" name=\"Item\"/><tableColumn id=\"2\" name=\"Amount\"/></tableColumns></table>").into_bytes(),
439 ),
440 ];
441 zip::write_stored(&parts).unwrap()
442 }
443
444 fn old_bytes() -> Vec<u8> {
445 package_bytes(
446 "<sheet name=\"Model\" sheetId=\"1\" r:id=\"rId1\"/><sheet name=\"Gone\" sheetId=\"2\" state=\"hidden\" r:id=\"rId2\"/><sheet name=\"Shy\" sheetId=\"3\" r:id=\"rId3\"/>",
447 "<definedName name=\"Rate\">Model!$B$2</definedName><definedName name=\"Old\">1</definedName>",
448 concat!(
449 "<c r=\"A1\"><v>1200</v></c><c r=\"B1\"><v>800</v></c>",
450 "<c r=\"C1\"><f>A1-B1</f><v>400</v></c><c r=\"D1\"><f>A1*2</f><v>2400</v></c>",
451 "<c r=\"E1\" t=\"inlineStr\"><is><t>x</t></is></c><c r=\"F1\" t=\"b\"><v>1</v></c>",
452 "<c r=\"G1\"><v>5</v></c>"
453 ),
454 "A1:B2",
455 )
456 }
457
458 fn new_bytes() -> Vec<u8> {
459 package_bytes(
460 "<sheet name=\"model\" sheetId=\"1\" r:id=\"rId1\"/><sheet name=\"Shy\" sheetId=\"2\" state=\"hidden\" r:id=\"rId2\"/><sheet name=\"Added\" sheetId=\"3\" r:id=\"rId3\"/>",
461 "<definedName name=\"RATE\">Model!$B$3</definedName><definedName name=\"New\">2</definedName>",
462 concat!(
463 "<c r=\"A1\"><v>1300</v></c><c r=\"B1\"><v>800.0</v></c>",
464 "<c r=\"C1\"><v>500</v></c><c r=\"D1\"><f>A1*2</f><v>2600</v></c>",
465 "<c r=\"E1\" t=\"inlineStr\"><is><t>y</t></is></c><c r=\"F1\" t=\"b\"><v>0</v></c>",
466 "<c r=\"H1\"><v>7</v></c>"
467 ),
468 "A1:B3",
469 )
470 }
471
472 #[test]
473 fn every_kind_of_change_is_one_row_in_the_fixed_order() {
474 let old = old_bytes();
475 let new = new_bytes();
476 let got = diff_text(&old, "old.xlsx", &new, "new.xlsx").unwrap();
477 let want = concat!(
478 "(sheet-removed \"Gone\" hidden)\n",
479 "(sheet-added \"Added\" visible)\n",
480 "(sheet-changed \"Shy\" visible hidden)\n",
481 "(changed \"New\" blank \"2\")\n",
482 "(changed \"Old\" \"1\" blank)\n",
483 "(changed \"RATE\" \"Model!$B$2\" \"Model!$B$3\")\n",
484 "(changed \"T\" \"Model!A1:B2\" \"model!A1:B3\")\n",
485 "(changed \"model!A1\" 1200 1300)\n",
486 "(changed \"model!C1\" (formula \"=A1-B1\" 400) 500)\n",
487 "(changed \"model!D1\" (formula \"=A1*2\" 2400) (formula \"=A1*2\" 2600))\n",
488 "(changed \"model!E1\" \"x\" \"y\")\n",
489 "(changed \"model!F1\" true false)\n",
490 "(changed \"model!G1\" 5 blank)\n",
491 "(changed \"model!H1\" blank 7)\n",
492 "(changed \"Shy!A1\" 2 1)\n",
495 );
496 assert_eq!(got, want);
497 let o = Package::open(&old, "old.xlsx").unwrap();
499 let n = Package::open(&new, "new.xlsx").unwrap();
500 let stats = diff(&o, &n, &mut Discard).unwrap();
501 assert_eq!(
502 stats,
503 DiffStats {
504 sheets_removed: 1,
505 sheets_added: 1,
506 sheets_changed: 1,
507 names: 3,
508 tables: 1,
509 cells: 8,
510 compared: 9,
511 }
512 );
513 assert!(stats.differ());
514 assert_eq!(
515 stats.line(),
516 "sheets-removed 1 sheets-added 1 sheets-changed 1 names 3 tables 1 cells 8 compared 9"
517 );
518 }
519
520 #[test]
521 fn a_file_against_itself_has_no_rows() {
522 let old = old_bytes();
523 assert_eq!(diff_text(&old, "a.xlsx", &old, "b.xlsx").unwrap(), "");
524 let o = Package::open(&old, "a.xlsx").unwrap();
525 let stats = diff(&o, &o, &mut Discard).unwrap();
526 assert!(!stats.differ());
527 assert_eq!(stats.compared, 9);
528 }
529
530 #[test]
531 fn numbers_compare_as_numbers_and_the_rest_by_kind_and_text() {
532 let n = |s: &str| Value::Number(s.to_string());
533 assert!(same_value(&n("800"), &n("800.0")));
534 assert!(same_value(&n("1E3"), &n("1000")));
535 assert!(!same_value(&n("0.1"), &n("0.10000000000000002")));
536 assert!(!same_value(&n("5"), &Value::Text("5".to_string())));
537 assert!(!same_value(&n("1"), &Value::Bool(true)));
538 assert!(same_value(
539 &Value::Error("#N/A".to_string()),
540 &Value::Error("#N/A".to_string())
541 ));
542 assert!(!same_value(&n("1,5"), &n("1.5")));
544 assert!(same_value(&n("1,5"), &n("1,5")));
545 }
546
547 #[test]
548 fn each_row_prints_in_the_corpus_notation() {
549 assert_eq!(
550 line(&Change::SheetRemoved {
551 name: "Q1 Data",
552 state: Visibility::VeryHidden
553 }),
554 "(sheet-removed \"Q1 Data\" very-hidden)"
555 );
556 assert_eq!(
557 line(&Change::SheetAdded {
558 name: "It's",
559 state: Visibility::Visible
560 }),
561 "(sheet-added \"It's\" visible)"
562 );
563 assert_eq!(
564 line(&Change::SheetChanged {
565 name: "Scratch",
566 old: Visibility::Hidden,
567 new: Visibility::Visible
568 }),
569 "(sheet-changed \"Scratch\" hidden visible)"
570 );
571 assert_eq!(
572 line(&Change::Changed {
573 key: "'Q1 Data'!B2",
574 old: "blank",
575 new: "(formula \"=1/0\" (error \"#DIV/0!\"))"
576 }),
577 "(changed \"'Q1 Data'!B2\" blank (formula \"=1/0\" (error \"#DIV/0!\")))"
578 );
579 let blank = CellState::default();
580 assert_eq!(side(None), "blank");
581 assert_eq!(side(Some(&blank)), "blank");
582 assert_eq!(
583 side(Some(&CellState {
584 value: Some(Value::Text("say \"hi\"".to_string())),
585 formula: None
586 })),
587 "\"say \\\"hi\\\"\""
588 );
589 assert_eq!(
590 side(Some(&CellState {
591 value: None,
592 formula: Some("=B2+B3".to_string())
593 })),
594 "(formula \"=B2+B3\")"
595 );
596 assert_eq!(text_side(Some("Data!A1:B4")), "\"Data!A1:B4\"");
597 assert_eq!(text_side(None), "blank");
598 }
599
600 #[test]
606 fn the_diff_goldens_are_reproduced() {
607 type Pair = (
609 &'static str,
610 &'static [u8],
611 &'static str,
612 &'static [u8],
613 &'static str,
614 );
615 let rows: [Pair; 5] = [
616 (
619 "scripts/reflect/opendocument.ods",
620 include_bytes!("../../../scripts/reflect/opendocument.ods"),
621 "scripts/reflect/opendocument_saved.ods",
622 include_bytes!("../../../scripts/reflect/opendocument_saved.ods"),
623 include_str!("../../../scripts/reflect/opendocument_opendocument_saved_diff.vla"),
624 ),
625 (
628 "scripts/reflect/fixture.xlsx",
629 include_bytes!("../../../scripts/reflect/fixture.xlsx"),
630 "scripts/reflect/opendocument.ods",
631 include_bytes!("../../../scripts/reflect/opendocument.ods"),
632 include_str!("../../../scripts/reflect/fixture_opendocument_diff.vla"),
633 ),
634 (
637 "scripts/build/fixture_golden.xlsx",
638 include_bytes!("../../../scripts/build/fixture_golden.xlsx"),
639 "scripts/reflect/saved.xlsx",
640 include_bytes!("../../../scripts/reflect/saved.xlsx"),
641 include_str!("../../../scripts/reflect/build_fixture_saved_diff.vla"),
642 ),
643 (
645 "scripts/build/model.xlsx",
646 include_bytes!("../../../scripts/build/model.xlsx"),
647 "scripts/build/into_golden.xlsx",
648 include_bytes!("../../../scripts/build/into_golden.xlsx"),
649 include_str!("../../../scripts/reflect/model_into_diff.vla"),
650 ),
651 (
653 "scripts/reflect/fixture.xlsx",
654 include_bytes!("../../../scripts/reflect/fixture.xlsx"),
655 "scripts/reflect/changed.xlsx",
656 include_bytes!("../../../scripts/reflect/changed.xlsx"),
657 include_str!("../../../scripts/reflect/fixture_changed_diff.vla"),
658 ),
659 ];
660 for (old_label, old, new_label, new, golden) in rows {
661 let got = diff_text(old, old_label, new, new_label).unwrap_or_else(|r| {
662 panic!("{old_label} against {new_label} did not read: {}", r.text)
663 });
664 let want = golden.replace("\r\n", "\n");
665 if got != want {
666 let line = got
667 .lines()
668 .zip(want.lines())
669 .position(|(a, b)| a != b)
670 .map(|i| i + 1)
671 .unwrap_or(got.lines().count().min(want.lines().count()) + 1);
672 panic!("{old_label} against {new_label}: the difference differs from the golden at line {line}");
673 }
674 }
675 }
676}