1use std::collections::{BTreeMap, HashSet};
30
31use super::print::datum;
32use super::{sheet_prefix, Row, Sink, Source, Value, Visibility};
33use crate::form::Form;
34use crate::intrinsics::fold;
35use crate::messages::Refusal;
36use crate::printer::write_datum;
37use crate::refers::{self, Kind, Shape};
38use crate::sheet::{cell_ref, parse_a1_range};
39
40fn quoted(s: &str) -> String {
41 write_datum(&Form::string(s))
42}
43
44#[derive(Clone, Copy, Debug, PartialEq, Eq)]
46pub enum Finding<'r> {
47 TypedOver {
50 cell: &'r str,
51 value: &'r str,
52 expected: &'r str,
53 },
54 Inconsistent {
57 cell: &'r str,
58 formula: &'r str,
59 expected: &'r str,
60 },
61 UnusedName { name: &'r str, refers_to: &'r str },
64 EmptyReference { cell: &'r str, target: &'r str },
67 HiddenSheet { name: &'r str, state: Visibility },
69 ExternalLink { cell: &'r str, target: &'r str },
71}
72
73pub trait FindingSink {
75 fn finding(&mut self, finding: &Finding<'_>);
76}
77
78pub struct Discard;
80
81impl FindingSink for Discard {
82 fn finding(&mut self, _finding: &Finding<'_>) {}
83}
84
85#[derive(Default)]
87pub struct Lines {
88 pub out: String,
89}
90
91impl FindingSink for Lines {
92 fn finding(&mut self, finding: &Finding<'_>) {
93 self.out.push_str(&line(finding));
94 self.out.push('\n');
95 }
96}
97
98pub fn line(finding: &Finding<'_>) -> String {
100 match finding {
101 Finding::TypedOver {
102 cell,
103 value,
104 expected,
105 } => format!(
106 "(typed-over {} {} {})",
107 quoted(cell),
108 value,
109 quoted(expected)
110 ),
111 Finding::Inconsistent {
112 cell,
113 formula,
114 expected,
115 } => format!(
116 "(inconsistent {} {} {})",
117 quoted(cell),
118 quoted(formula),
119 quoted(expected)
120 ),
121 Finding::UnusedName { name, refers_to } => {
122 format!("(unused-name {} {})", quoted(name), quoted(refers_to))
123 }
124 Finding::EmptyReference { cell, target } => {
125 format!("(empty-reference {} {})", quoted(cell), quoted(target))
126 }
127 Finding::HiddenSheet { name, state } => {
128 format!("(hidden-sheet {} {})", quoted(name), state.word())
129 }
130 Finding::ExternalLink { cell, target } => {
131 format!("(external-link {} {})", quoted(cell), quoted(target))
132 }
133 }
134}
135
136#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
138pub struct AuditStats {
139 pub typed_over: u64,
140 pub inconsistent: u64,
141 pub unused_names: u64,
142 pub empty_references: u64,
143 pub hidden_sheets: u64,
144 pub external_links: u64,
145}
146
147impl AuditStats {
148 pub fn line(&self) -> String {
150 format!(
151 "typed-over {} inconsistent {} unused-names {} empty-references {} hidden-sheets {} external-links {}",
152 self.typed_over,
153 self.inconsistent,
154 self.unused_names,
155 self.empty_references,
156 self.hidden_sheets,
157 self.external_links
158 )
159 }
160
161 pub fn any(&self) -> bool {
163 self.typed_over
164 + self.inconsistent
165 + self.unused_names
166 + self.empty_references
167 + self.hidden_sheets
168 + self.external_links
169 > 0
170 }
171}
172
173#[derive(Clone, Debug, Default, PartialEq, Eq)]
175struct Held {
176 formula: Option<String>,
177 value: Option<Value>,
178}
179
180#[derive(Debug, Default)]
183pub struct AuditIndex {
184 sheets: Vec<String>,
186 cells: Vec<BTreeMap<(u32, u32), Held>>,
187}
188
189impl AuditIndex {
190 pub fn new(package: &dyn Source) -> AuditIndex {
193 let n = package.sheets().len();
194 AuditIndex {
195 sheets: package.sheets().iter().map(|s| fold(&s.name)).collect(),
196 cells: (0..n).map(|_| BTreeMap::new()).collect(),
197 }
198 }
199
200 fn sheet_index(&self, name: &str) -> Option<usize> {
201 let f = fold(name);
202 self.sheets.iter().position(|s| *s == f)
203 }
204
205 fn holds(&self, sheet: usize, row: u32, col: u32) -> bool {
206 self.cells[sheet].contains_key(&(col, row))
207 }
208}
209
210impl Sink for AuditIndex {
211 fn row(&mut self, row: &Row<'_>) {
212 match row {
213 Row::Cell {
214 sheet, addr, value, ..
215 } => {
216 if let (Some(i), Some(a)) = (self.sheet_index(sheet), parse_a1_range(addr)) {
217 self.cells[i].entry((a.left, a.top)).or_default().value =
218 Some((*value).clone());
219 }
220 }
221 Row::Formula {
222 sheet, addr, text, ..
223 } => {
224 if let (Some(i), Some(a)) = (self.sheet_index(sheet), parse_a1_range(addr)) {
225 self.cells[i].entry((a.left, a.top)).or_default().formula =
226 Some((*text).to_string());
227 }
228 }
229 _ => {}
230 }
231 }
232}
233
234fn agreeing_neighbours(
238 cells: &BTreeMap<(u32, u32), Held>,
239 row: u32,
240 col: u32,
241) -> Option<(u32, &str)> {
242 let (&(_, above_row), above) = cells.range((col, 0)..(col, row)).next_back()?;
243 let (&(_, below_row), below) = cells.range((col, row + 1)..(col + 1, 0)).next()?;
244 let (a, b) = (above.formula.as_deref()?, below.formula.as_deref()?);
245 if refers::r1c1(a, above_row, col) != refers::r1c1(b, below_row, col) {
246 return None;
247 }
248 Some((above_row, a))
249}
250
251fn is_mark(name: &str) -> bool {
257 name.starts_with("_xlnm.") || name.starts_with("frazaro.") || name.starts_with("vlat_")
258}
259
260fn note_names(used: &mut HashSet<String>, text: &str) {
263 for r in refers::scan(text) {
264 match r.kind {
265 Kind::Name => {
266 used.insert(fold(&r.part));
267 }
268 Kind::Spill if r.shape != Shape::Cell => {
269 used.insert(fold(r.part.trim_end_matches('#')));
270 }
271 _ => {}
272 }
273 }
274}
275
276pub fn audit(index: &AuditIndex, package: &dyn Source, sink: &mut dyn FindingSink) -> AuditStats {
279 let mut stats = AuditStats::default();
280 let sheets = package.sheets();
281 let mut typed: Vec<(String, String, String)> = Vec::new();
284 let mut inconsistent: Vec<(String, String, String)> = Vec::new();
285 for (s, info) in sheets.iter().enumerate() {
286 let prefix = sheet_prefix(&info.name);
287 let cells = &index.cells[s];
288 let mut at: Vec<(u32, u32)> = cells.keys().map(|&(c, r)| (r, c)).collect();
289 at.sort_unstable();
290 for (row, col) in at {
291 let held = &cells[&(col, row)];
292 let Some((above_row, above)) = agreeing_neighbours(cells, row, col) else {
293 continue;
294 };
295 let expected = refers::shift_a1_references(above, i64::from(row - above_row), 0);
296 let cell = format!("{prefix}!{}", cell_ref(row, col));
297 match (&held.formula, &held.value) {
298 (Some(f), _) => {
299 if refers::r1c1(f, row, col) != refers::r1c1(above, above_row, col) {
300 inconsistent.push((cell, f.clone(), expected));
301 }
302 }
303 (None, Some(v)) => typed.push((cell, datum(v), expected)),
304 (None, None) => {}
305 }
306 }
307 }
308 let mut used: HashSet<String> = HashSet::new();
310 for cells in &index.cells {
311 for held in cells.values() {
312 if let Some(f) = &held.formula {
313 note_names(&mut used, f);
314 }
315 }
316 }
317 for n in package.names().iter().filter(|n| !n.placeholder) {
318 note_names(&mut used, &n.refers_to);
319 }
320 let mut unused: Vec<(String, String)> = package
321 .names()
322 .iter()
323 .filter(|n| {
324 let f = fold(&n.name);
325 !n.placeholder && !is_mark(&f) && !used.contains(&f)
326 })
327 .map(|n| (package.printed_name(n), n.refers_to.clone()))
328 .collect();
329 unused.sort_by(|a, b| fold(&a.0).cmp(&fold(&b.0)).then_with(|| a.0.cmp(&b.0)));
330 let mut empty: Vec<(String, String)> = Vec::new();
332 let mut links: Vec<(String, String)> = Vec::new();
333 for (s, info) in sheets.iter().enumerate() {
334 let prefix = sheet_prefix(&info.name);
335 let cells = &index.cells[s];
336 let mut at: Vec<(u32, u32)> = cells
337 .iter()
338 .filter(|(_, h)| h.formula.is_some())
339 .map(|(&(c, r), _)| (r, c))
340 .collect();
341 at.sort_unstable();
342 for (row, col) in at {
343 let Some(text) = cells[&(col, row)].formula.as_deref() else {
344 continue;
345 };
346 let cell = format!("{prefix}!{}", cell_ref(row, col));
347 let mut empties: Vec<String> = Vec::new();
348 let mut externals: Vec<String> = Vec::new();
349 for r in refers::scan(text) {
350 match r.kind {
351 Kind::Cell if r.shape == Shape::Cell => {
352 let target = if r.sheet_name.is_empty() {
353 Some(s)
354 } else {
355 index.sheet_index(&r.sheet_name)
356 };
357 if let Some(t) = target {
358 if !index.holds(t, r.row1, r.col1) {
359 empties.push(refers::spell(&r, &info.name));
360 }
361 }
362 }
363 Kind::External => externals.push(refers::spell(&r, &info.name)),
364 _ => {}
365 }
366 }
367 for list in [&mut empties, &mut externals] {
368 list.sort_by_key(|t| quoted(t));
369 list.dedup();
370 }
371 for t in empties {
372 empty.push((cell.clone(), t));
373 }
374 for t in externals {
375 links.push((cell.clone(), t));
376 }
377 }
378 }
379 for (cell, value, expected) in &typed {
380 stats.typed_over += 1;
381 sink.finding(&Finding::TypedOver {
382 cell,
383 value,
384 expected,
385 });
386 }
387 for (cell, formula, expected) in &inconsistent {
388 stats.inconsistent += 1;
389 sink.finding(&Finding::Inconsistent {
390 cell,
391 formula,
392 expected,
393 });
394 }
395 for (name, refers_to) in &unused {
396 stats.unused_names += 1;
397 sink.finding(&Finding::UnusedName { name, refers_to });
398 }
399 for (cell, target) in &empty {
400 stats.empty_references += 1;
401 sink.finding(&Finding::EmptyReference { cell, target });
402 }
403 for info in sheets
404 .iter()
405 .filter(|i| i.visibility != Visibility::Visible)
406 {
407 stats.hidden_sheets += 1;
408 sink.finding(&Finding::HiddenSheet {
409 name: &info.name,
410 state: info.visibility,
411 });
412 }
413 for (cell, target) in &links {
414 stats.external_links += 1;
415 sink.finding(&Finding::ExternalLink { cell, target });
416 }
417 stats
418}
419
420pub fn audit_text(bytes: &[u8], label: &str) -> Result<String, Refusal> {
424 let package = super::open(bytes, label)?;
425 let mut index = AuditIndex::new(package.as_ref());
426 for i in 0..package.sheets().len() {
427 package.walk_sheet(i, &mut index)?;
428 }
429 let mut lines = Lines::default();
430 audit(&index, package.as_ref(), &mut lines);
431 Ok(lines.out)
432}
433
434#[cfg(test)]
435mod tests {
436 use super::*;
437 use crate::reflect::ooxml::Package;
438 use crate::sheet::zip;
439
440 const NS: &str = "xmlns=\"http://schemas.openxmlformats.org/spreadsheetml/2006/main\" xmlns:r=\"http://schemas.openxmlformats.org/officeDocument/2006/relationships\"";
441 const REL: &str = "http://schemas.openxmlformats.org/officeDocument/2006/relationships";
442
443 fn package_bytes() -> Vec<u8> {
446 let model = concat!(
447 "<row r=\"1\"><c r=\"A1\"><v>1</v></c><c r=\"B1\"><f>A1*2</f><v>2</v></c><c r=\"C1\"><f>A1+1</f><v>2</v></c>",
454 "<c r=\"D1\"><f>Z9</f><v>0</v></c><c r=\"E1\"><f>Used</f><v>1</v></c><c r=\"F1\"><f>[1]Sheet1!A1+[1]Sheet1!A1</f><v>2</v></c>",
455 "<c r=\"H1\"><f>A1</f><v>1</v></c></row>",
456 "<row r=\"2\"><c r=\"A2\"><v>2</v></c><c r=\"B2\"><f>A2*2</f><v>4</v></c><c r=\"C2\"><f>A2+1</f><v>3</v></c>",
457 "<c r=\"D2\"><f>Other!A1</f><v>1</v></c></row>",
458 "<row r=\"3\"><c r=\"A3\"><v>3</v></c><c r=\"B3\"><v>61</v></c><c r=\"C3\"><f>A3+2</f><v>5</v></c>",
459 "<c r=\"D3\"><f>Missing!A1</f><v>0</v></c><c r=\"H3\"><f>A3</f><v>3</v></c></row>",
460 "<row r=\"4\"><c r=\"A4\"><v>4</v></c><c r=\"B4\"><f>A4*2</f><v>8</v></c><c r=\"C4\"><f>A4+1</f><v>5</v></c>",
461 "<c r=\"D4\"><f>SUM(A1:A2)</f><v>3</v></c><c r=\"H4\"><v>9</v></c></row>",
462 "<row r=\"5\"><c r=\"A5\"><v>5</v></c><c r=\"H5\"><f>A5</f><v>5</v></c></row>",
463 );
464 let parts: Vec<(String, Vec<u8>)> = vec![
465 (
466 "xl/workbook.xml".to_string(),
467 format!(concat!(
468 "<workbook {NS}><sheets><sheet name=\"Model\" sheetId=\"1\" r:id=\"rId1\"/><sheet name=\"Other\" sheetId=\"2\" state=\"hidden\" r:id=\"rId2\"/></sheets>",
469 "<externalReferences><externalReference r:id=\"rId3\"/></externalReferences>",
470 "<definedNames><definedName name=\"_xlnm.Print_Area\" localSheetId=\"0\">Model!$A$1:$B$2</definedName>",
471 "<definedName name=\"Base\">Model!$A$2</definedName><definedName name=\"Chain\">Base</definedName>",
472 "<definedName name=\"Frazaro.Build\">\"Frazaro 0.7.1; a stamp\"</definedName>",
473 "<definedName name=\"Used\">Model!$A$1</definedName><definedName name=\"VLAt_TimeRun\">1</definedName></definedNames></workbook>"), NS = NS).into_bytes(),
474 ),
475 (
476 "xl/_rels/workbook.xml.rels".to_string(),
477 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}/externalLink\" Target=\"externalLinks/externalLink1.xml\"/></Relationships>").into_bytes(),
478 ),
479 (
480 "xl/worksheets/sheet1.xml".to_string(),
481 format!("<worksheet {NS}><sheetData>{model}</sheetData></worksheet>").into_bytes(),
482 ),
483 (
484 "xl/worksheets/sheet2.xml".to_string(),
485 format!("<worksheet {NS}><sheetData><row r=\"1\"><c r=\"A1\"><v>1</v></c></row></sheetData></worksheet>").into_bytes(),
486 ),
487 (
488 "xl/externalLinks/externalLink1.xml".to_string(),
489 format!("<externalLink {NS}><externalBook r:id=\"rId1\"><sheetNames><sheetName val=\"Sheet1\"/></sheetNames></externalBook></externalLink>").into_bytes(),
490 ),
491 (
492 "xl/externalLinks/_rels/externalLink1.xml.rels".to_string(),
493 format!("<Relationships><Relationship Id=\"rId1\" Type=\"{REL}/externalLinkPath\" Target=\"Rates.xlsx\" TargetMode=\"External\"/></Relationships>").into_bytes(),
494 ),
495 ];
496 zip::write_stored(&parts).unwrap()
497 }
498
499 #[test]
500 fn each_walk_finds_its_case_and_leaves_the_rest_alone() {
501 let bytes = package_bytes();
502 let got = audit_text(&bytes, "t.xlsx").unwrap();
503 let want = concat!(
504 "(typed-over \"Model!B3\" 61 \"=A3*2\")\n",
505 "(typed-over \"Model!H4\" 9 \"=A4\")\n",
506 "(inconsistent \"Model!C3\" \"=A3+2\" \"=A3+1\")\n",
507 "(unused-name \"Chain\" \"Base\")\n",
508 "(empty-reference \"Model!D1\" \"Model!Z9\")\n",
509 "(hidden-sheet \"Other\" hidden)\n",
510 "(external-link \"Model!F1\" \"[Rates.xlsx]Sheet1!A1\")\n",
511 );
512 assert_eq!(got, want);
513 let package = Package::open(&bytes, "t.xlsx").unwrap();
514 let mut index = AuditIndex::new(&package);
515 for i in 0..package.sheets().len() {
516 package.walk_sheet(i, &mut index).unwrap();
517 }
518 let stats = audit(&index, &package, &mut Discard);
519 assert_eq!(
520 stats,
521 AuditStats {
522 typed_over: 2,
523 inconsistent: 1,
524 unused_names: 1,
525 empty_references: 1,
526 hidden_sheets: 1,
527 external_links: 1,
528 }
529 );
530 assert!(stats.any());
531 assert_eq!(
532 stats.line(),
533 "typed-over 2 inconsistent 1 unused-names 1 empty-references 1 hidden-sheets 1 external-links 1"
534 );
535 }
536
537 #[test]
538 fn the_neighbours_must_both_be_formulas_that_agree() {
539 let mut cells: BTreeMap<(u32, u32), Held> = BTreeMap::new();
540 let formula = |t: &str| Held {
541 formula: Some(t.to_string()),
542 value: None,
543 };
544 let value = |t: &str| Held {
545 formula: None,
546 value: Some(Value::Number(t.to_string())),
547 };
548 cells.insert((2, 1), formula("=A1*2"));
551 cells.insert((2, 3), value("7"));
552 cells.insert((2, 6), formula("=A6*2"));
553 assert_eq!(agreeing_neighbours(&cells, 3, 2), Some((1, "=A1*2")));
554 assert_eq!(agreeing_neighbours(&cells, 1, 2), None);
556 assert_eq!(agreeing_neighbours(&cells, 6, 2), None);
557 cells.insert((2, 1), value("1"));
559 assert_eq!(agreeing_neighbours(&cells, 3, 2), None);
560 cells.insert((2, 1), formula("=A1*3"));
561 assert_eq!(agreeing_neighbours(&cells, 3, 2), None);
562 cells.insert((2, 1), formula("=$A$1*2"));
564 cells.insert((2, 6), formula("=$A$1*2"));
565 assert_eq!(agreeing_neighbours(&cells, 3, 2), Some((1, "=$A$1*2")));
566 }
567
568 #[test]
569 fn a_name_is_used_by_a_formula_or_by_another_name() {
570 let mut used = HashSet::new();
571 note_names(&mut used, "=Rate*2+Model!Local+Spilled#+A1+Sales[Amount]");
572 assert_eq!(used.len(), 3);
573 assert!(used.contains("rate") && used.contains("local") && used.contains("spilled"));
574 note_names(&mut used, "Deep+Model!$B$2");
575 assert!(used.contains("deep"));
576 assert!(is_mark(&fold(crate::build::STAMP_NAME)));
578 assert!(is_mark("_xlnm.print_area") && is_mark("vlat_timerun"));
579 assert!(!is_mark("rate") && !is_mark("frazaro") && !is_mark("vlat"));
580 }
581
582 #[test]
583 fn each_finding_prints_in_the_corpus_notation() {
584 assert_eq!(
585 line(&Finding::TypedOver {
586 cell: "'Q1 Data'!B3",
587 value: "61",
588 expected: "=A3*2"
589 }),
590 "(typed-over \"'Q1 Data'!B3\" 61 \"=A3*2\")"
591 );
592 assert_eq!(
593 line(&Finding::Inconsistent {
594 cell: "Model!C3",
595 formula: "=A3+2",
596 expected: "=A3+1"
597 }),
598 "(inconsistent \"Model!C3\" \"=A3+2\" \"=A3+1\")"
599 );
600 assert_eq!(
601 line(&Finding::UnusedName {
602 name: "Model!Local",
603 refers_to: "Model!$B$2"
604 }),
605 "(unused-name \"Model!Local\" \"Model!$B$2\")"
606 );
607 assert_eq!(
608 line(&Finding::EmptyReference {
609 cell: "Model!D1",
610 target: "Model!Z9"
611 }),
612 "(empty-reference \"Model!D1\" \"Model!Z9\")"
613 );
614 assert_eq!(
615 line(&Finding::HiddenSheet {
616 name: "Secret",
617 state: Visibility::VeryHidden
618 }),
619 "(hidden-sheet \"Secret\" very-hidden)"
620 );
621 assert_eq!(
622 line(&Finding::ExternalLink {
623 cell: "Model!E2",
624 target: "[Rates.xlsx]Sheet1!A1"
625 }),
626 "(external-link \"Model!E2\" \"[Rates.xlsx]Sheet1!A1\")"
627 );
628 assert!(!AuditStats::default().any());
629 let into = include_bytes!("../../../scripts/build/into_golden.xlsx");
633 assert_eq!(audit_text(into, "into_golden.xlsx").unwrap(), "");
634 }
635
636 #[test]
643 fn the_audit_goldens_are_reproduced() {
644 let rows: [(&str, &[u8], &str); 5] = [
645 (
648 "scripts/reflect/opendocument_saved.ods",
649 include_bytes!("../../../scripts/reflect/opendocument_saved.ods"),
650 include_str!("../../../scripts/reflect/opendocument_saved_audit.vla"),
651 ),
652 (
655 "scripts/reflect/opendocument.ods",
656 include_bytes!("../../../scripts/reflect/opendocument.ods"),
657 include_str!("../../../scripts/reflect/opendocument_audit.vla"),
658 ),
659 (
660 "scripts/reflect/fixture.xlsx",
661 include_bytes!("../../../scripts/reflect/fixture.xlsx"),
662 include_str!("../../../scripts/reflect/fixture_audit.vla"),
663 ),
664 (
665 "scripts/reflect/changed.xlsx",
666 include_bytes!("../../../scripts/reflect/changed.xlsx"),
667 include_str!("../../../scripts/reflect/changed_audit.vla"),
668 ),
669 (
670 "scripts/build/fixture_golden.xlsx",
671 include_bytes!("../../../scripts/build/fixture_golden.xlsx"),
672 include_str!("../../../scripts/reflect/build_fixture_audit.vla"),
673 ),
674 ];
675 for (label, bytes, golden) in rows {
676 let got = audit_text(bytes, label)
677 .unwrap_or_else(|r| panic!("{label} did not read: {}", r.text));
678 let want = golden.replace("\r\n", "\n");
679 if got != want {
680 let line = got
681 .lines()
682 .zip(want.lines())
683 .position(|(a, b)| a != b)
684 .map(|i| i + 1)
685 .unwrap_or(got.lines().count().min(want.lines().count()) + 1);
686 panic!("{label}: the findings differ from the golden at line {line}");
687 }
688 }
689 }
690}