use std::collections::HashMap;
pub struct Diff {
pub text: String,
pub added: usize,
pub removed: usize,
pub changed: usize,
pub unchanged: usize,
pub focus_from: Option<String>,
pub focus_to: Option<String>,
pub focus_to_document: bool,
pub anonymous: usize,
pub moved: usize,
pub values_lost: Vec<LostValue>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LostValue {
pub uid: String,
pub role: String,
pub name: Option<String>,
pub was: String,
}
pub fn diff_snapshots(old: &str, new: &str) -> Diff {
let old_lines = uid_lines(old);
let new_lines = uid_lines(new);
let anonymous = new_lines.iter().filter(|(uid, _)| is_anonymous(uid)).count();
let old_lines: Vec<_> = old_lines.into_iter().filter(|(uid, _)| !is_anonymous(uid)).collect();
let new_lines: Vec<_> = new_lines.into_iter().filter(|(uid, _)| !is_anonymous(uid)).collect();
let old_by_uid: HashMap<&str, &str> = old_lines.iter().copied().collect();
let new_by_uid: HashMap<&str, &str> = new_lines.iter().copied().collect();
let mut added = Vec::new();
let mut removed = Vec::new();
let mut changed = Vec::new();
let mut unchanged: usize = 0;
let mut focus_from: Option<String> = None;
let mut focus_to: Option<String> = None;
let mut focus_to_document = false;
let mut values_lost = Vec::new();
for (uid, old_line) in &old_lines {
match new_by_uid.get(uid) {
None => removed.push(format!("- {old_line}")),
Some(new_line) => {
if old_line == new_line {
unchanged += 1;
} else if let Some(gained) = focus_only_change(old_line, new_line) {
if gained {
focus_to = Some((*uid).to_string());
focus_to_document = is_document_node(new_line);
} else {
focus_from = Some((*uid).to_string());
}
unchanged += 1;
} else {
if let Some(lost) = lost_value(uid, old_line, new_line) {
values_lost.push(lost);
}
changed.push(render_change(old_line, new_line));
}
}
}
}
for (uid, new_line) in &new_lines {
if !old_by_uid.contains_key(uid) {
added.push(format!("+ {new_line}"));
}
}
let moved = count_moved(&old_lines, &new_lines);
let observed_something = !added.is_empty()
|| !removed.is_empty()
|| !changed.is_empty()
|| moved > 0
|| focus_from.is_some()
|| focus_to.is_some();
let mut out = String::new();
for line in added.iter().chain(&removed).chain(&changed) {
out.push_str(line);
out.push('\n');
}
if moved > 0 {
out.push_str(&format!("> {moved} elements moved\n"));
}
if focus_from.is_some() || focus_to.is_some() {
let f = focus_from.as_deref().unwrap_or("none");
let t = focus_to.as_deref().unwrap_or("none");
out.push_str(&format!("focus: {f} -> {t}\n"));
}
if anonymous > 0 {
out.push_str(&format!("? {anonymous} nodes without stable ids (not compared)\n"));
}
if unchanged > 0 {
out.push_str(&format!("= {unchanged} unchanged elements\n"));
}
if !observed_something {
out.push_str("No changes detected.\n");
}
Diff {
text: out,
added: added.len(),
removed: removed.len(),
changed: changed.len(),
unchanged,
focus_from,
focus_to,
focus_to_document,
anonymous,
moved,
values_lost,
}
}
fn lost_value(uid: &str, old_line: &str, new_line: &str) -> Option<LostValue> {
let old_tokens = tokenize(old_line)?;
let was = value_token(&old_tokens)?;
if was.is_empty() {
return None;
}
let new_tokens = tokenize(new_line)?;
if !value_token(&new_tokens).is_none_or(str::is_empty) {
return None;
}
Some(LostValue {
uid: uid.to_string(),
role: old_tokens.get(1).copied().unwrap_or_default().to_string(),
name: old_tokens
.get(2)
.and_then(|t| t.strip_prefix('"'))
.and_then(|t| t.strip_suffix('"'))
.map(str::to_string),
was: was.to_string(),
})
}
fn value_token<'a>(tokens: &[&'a str]) -> Option<&'a str> {
tokens
.iter()
.find_map(|t| t.strip_prefix("value=\""))
.and_then(|t| t.strip_suffix('"'))
}
fn is_anonymous(uid: &str) -> bool {
uid.starts_with('e') && uid[1..].chars().all(|c| c.is_ascii_digit()) && uid.len() > 1
}
fn is_document_node(line: &str) -> bool {
line.split_whitespace().nth(1) == Some("RootWebArea")
}
fn focus_only_change(old_line: &str, new_line: &str) -> Option<bool> {
let (old_tokens, new_tokens) = (tokenize(old_line)?, tokenize(new_line)?);
let had = old_tokens.contains(&"focused");
let has = new_tokens.contains(&"focused");
if had == has {
return None;
}
let strip = |t: &Vec<&str>| -> Vec<String> {
t.iter().filter(|x| **x != "focused").map(|x| (*x).to_string()).collect()
};
if strip(&old_tokens) == strip(&new_tokens) { Some(has) } else { None }
}
fn count_moved(old_lines: &[(&str, &str)], new_lines: &[(&str, &str)]) -> usize {
let new_set: std::collections::HashSet<&str> = new_lines.iter().map(|(u, _)| *u).collect();
let old_order: Vec<&str> = old_lines.iter().map(|(u, _)| *u).filter(|u| new_set.contains(u)).collect();
let old_set: std::collections::HashSet<&str> = old_lines.iter().map(|(u, _)| *u).collect();
let new_order: Vec<&str> = new_lines.iter().map(|(u, _)| *u).filter(|u| old_set.contains(u)).collect();
old_order.iter().zip(&new_order).filter(|(a, b)| a != b).count()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Identity {
Same,
Different,
Unknown,
}
impl Identity {
pub fn from_loader(stored: Option<(&str, &str)>, live: Option<(&str, &str)>) -> Self {
match (stored, live) {
(Some(a), Some(b)) if a == b => Self::Same,
(Some(_), Some(_)) => Self::Different,
_ => Self::Unknown,
}
}
}
#[derive(Debug)]
pub struct Comparison {
pub text: String,
pub added: usize,
pub removed: usize,
pub changed: usize,
pub unchanged: usize,
pub moved: usize,
pub anonymous: usize,
pub focus_from: Option<String>,
pub focus_to: Option<String>,
pub focus_to_document: bool,
pub document_changed: bool,
pub identity_known: bool,
pub hint: Option<&'static str>,
pub values_lost: Vec<LostValue>,
}
pub fn compare(identity: Identity, old_text: &str, new_text: &str) -> Comparison {
if identity != Identity::Same {
let hint = if identity == Identity::Different {
"The page navigated, so uids from the previous snapshot no longer refer to anything. This is the new page; act on these uids."
} else {
"Could not read which document this is, so the previous snapshot cannot be compared against it. This is the page as it stands; act on these uids."
};
return Comparison {
text: new_text.to_string(),
added: 0,
removed: 0,
changed: 0,
unchanged: 0,
moved: 0,
anonymous: 0,
focus_from: None,
focus_to: None,
focus_to_document: false,
document_changed: identity == Identity::Different,
identity_known: identity != Identity::Unknown,
hint: Some(hint),
values_lost: Vec::new(),
};
}
let diff = diff_snapshots(old_text, new_text);
Comparison {
text: diff.text,
added: diff.added,
removed: diff.removed,
changed: diff.changed,
unchanged: diff.unchanged,
moved: diff.moved,
anonymous: diff.anonymous,
focus_from: diff.focus_from,
focus_to: diff.focus_to,
focus_to_document: diff.focus_to_document,
document_changed: false,
identity_known: true,
hint: None,
values_lost: diff.values_lost,
}
}
fn render_change(old_line: &str, new_line: &str) -> String {
let whole = || format!("~ {old_line} -> {new_line}");
let (Some(old_tokens), Some(new_tokens)) = (tokenize(old_line), tokenize(new_line)) else {
return whole();
};
let shared = old_tokens
.iter()
.zip(&new_tokens)
.take_while(|(a, b)| a == b)
.count();
if shared < 2 || shared == old_tokens.len() && shared == new_tokens.len() {
return whole();
}
let prefix = old_tokens[..shared].join(" ");
let old_rest = old_tokens[shared..].join(" ");
let new_rest = new_tokens[shared..].join(" ");
match (old_rest.is_empty(), new_rest.is_empty()) {
(true, _) => format!("~ {prefix} -> {new_rest}"),
(_, true) => format!("~ {prefix} {old_rest} ->"),
_ => format!("~ {prefix} {old_rest} -> {new_rest}"),
}
}
fn tokenize(line: &str) -> Option<Vec<&str>> {
let mut tokens = Vec::new();
let mut in_quotes = false;
let mut start = 0usize;
for (i, ch) in line.char_indices() {
match ch {
'"' => in_quotes = !in_quotes,
' ' if !in_quotes => {
if i > start {
tokens.push(&line[start..i]);
}
start = i + 1;
}
_ => {}
}
}
if in_quotes {
return None;
}
if start < line.len() {
tokens.push(&line[start..]);
}
Some(tokens)
}
fn uid_lines(text: &str) -> Vec<(&str, &str)> {
let mut out = Vec::new();
for line in text.lines() {
let trimmed = line.trim_start();
if let Some(rest) = trimmed.strip_prefix("uid=") {
let uid = rest.find(' ').map_or(rest, |i| &rest[..i]);
out.push((uid, trimmed));
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn moving_focus_is_reported_separately_from_content() {
let old = "uid=n1 link \"A\" focused\nuid=n2 button \"B\"\n";
let new = "uid=n1 link \"A\"\nuid=n2 button \"B\" focused\n";
let d = diff_snapshots(old, new);
assert_eq!(d.changed, 0, "focus moving is not a content change: {}", d.text);
assert_eq!(d.focus_from.as_deref(), Some("n1"), "{}", d.text);
assert_eq!(d.focus_to.as_deref(), Some("n2"), "{}", d.text);
assert!(!d.focus_to_document, "a button is not the document: {}", d.text);
}
#[test]
fn focus_landing_on_the_document_is_marked_as_such() {
let old = "uid=n1 RootWebArea \"Title\"\nuid=n2 paragraph \"text\"\n";
let new = "uid=n1 RootWebArea \"Title\" focused\nuid=n2 paragraph \"text\"\n";
let d = diff_snapshots(old, new);
assert_eq!(d.focus_to.as_deref(), Some("n1"), "the fact is still reported: {}", d.text);
assert!(d.focus_to_document, "{}", d.text);
assert!(d.text.contains("focus: none -> n1"), "the line is unchanged: {}", d.text);
}
#[test]
fn losing_focus_to_the_document_is_not_a_document_gain() {
let old = "uid=n1 RootWebArea \"Title\"\nuid=n2 textbox \"Email\" focused\n";
let new = "uid=n1 RootWebArea \"Title\"\nuid=n2 textbox \"Email\"\n";
let d = diff_snapshots(old, new);
assert_eq!(d.focus_from.as_deref(), Some("n2"));
assert_eq!(d.focus_to, None);
assert!(!d.focus_to_document, "nothing gained focus at all: {}", d.text);
}
#[test]
fn a_node_named_after_the_document_role_is_not_the_document() {
let old = "uid=n5 heading \"About RootWebArea\"\n";
let new = "uid=n5 heading \"About RootWebArea\" focused\n";
let d = diff_snapshots(old, new);
assert_eq!(d.focus_to.as_deref(), Some("n5"));
assert!(!d.focus_to_document, "the role is the second token, not any token: {}", d.text);
}
#[test]
fn sequential_uids_are_never_matched_between_snapshots() {
let old = "uid=n1 heading \"Same\"\nuid=e1 generic \"first pass\"\n";
let new = "uid=n1 heading \"Same\"\nuid=e1 generic \"totally different node\"\n";
let d = diff_snapshots(old, new);
assert_eq!(d.changed, 0, "e-uids carry no identity, so nothing can be said to have changed: {}", d.text);
assert_eq!(d.anonymous, 1, "but their presence is worth reporting: {}", d.text);
}
#[test]
fn a_reorder_does_not_read_as_no_change() {
let old = "uid=n1 listitem \"A\"\nuid=n2 listitem \"B\"\nuid=n3 listitem \"C\"\n";
let new = "uid=n3 listitem \"C\"\nuid=n1 listitem \"A\"\nuid=n2 listitem \"B\"\n";
let d = diff_snapshots(old, new);
assert!(d.moved > 0, "a reorder must not be invisible: {}", d.text);
assert!(!d.text.contains("No changes"), "{}", d.text);
}
#[test]
fn a_changed_line_has_no_empty_side() {
let old = "uid=n1 link \"A\"\n";
let new = "uid=n1 link \"A\" focusable\n";
let d = diff_snapshots(old, new);
assert!(!d.text.contains(" ->"), "empty left side leaves a double space: {:?}", d.text);
}
#[test]
fn a_changed_line_states_only_what_moved() {
let old = "uid=n11 textbox \"Email\" focusable value=\"\"\n";
let new = "uid=n11 textbox \"Email\" focusable value=\"a@b.c\"\n";
let d = diff_snapshots(old, new);
assert_eq!(
d.text.lines().next().unwrap(),
"~ uid=n11 textbox \"Email\" focusable value=\"\" -> value=\"a@b.c\"",
"shared tokens appear once"
);
}
#[test]
fn an_unbalanced_quote_falls_back_to_the_whole_line() {
let old = "uid=n7 link \"\"WCAG 2.1\" ref\n";
let new = "uid=n7 link \"\"WCAG 2.2\" ref\n";
let d = diff_snapshots(old, new);
let line = d.text.lines().next().unwrap();
assert!(
line.contains("uid=n7 link \"\"WCAG 2.1\" ref -> uid=n7 link \"\"WCAG 2.2\" ref"),
"expected whole-line form, got {line}"
);
}
#[test]
fn a_wholly_different_node_keeps_the_whole_line() {
let old = "uid=n3 button \"Save\"\n";
let new = "uid=n3 link \"Cancel\"\n";
let d = diff_snapshots(old, new);
let line = d.text.lines().next().unwrap();
assert_eq!(line, "~ uid=n3 button \"Save\" -> uid=n3 link \"Cancel\"");
}
#[test]
fn a_field_this_action_emptied_is_reported_as_a_lost_value() {
let old = "uid=n2 textbox \"Email\" value=\"hello@example.com\" focused\nuid=n5 status \"\"\n";
let new = "uid=n2 textbox \"Email\" focused\nuid=n5 status \"sent\"\n";
let d = diff_snapshots(old, new);
assert_eq!(d.values_lost.len(), 1, "{}", d.text);
let lost = &d.values_lost[0];
assert_eq!(lost.uid, "n2");
assert_eq!(lost.role, "textbox");
assert_eq!(lost.name.as_deref(), Some("Email"));
assert_eq!(lost.was, "hello@example.com");
}
#[test]
fn an_emptied_value_token_counts_the_same_as_a_missing_one() {
let old = "uid=n2 textbox \"Email\" value=\"a@b.c\"\n";
let new = "uid=n2 textbox \"Email\" value=\"\"\n";
assert_eq!(diff_snapshots(old, new).values_lost.len(), 1);
let d = diff_snapshots(new, old);
assert!(d.values_lost.is_empty(), "a field being filled is not a field being emptied");
}
#[test]
fn a_rewritten_value_is_not_a_lost_one() {
let old = "uid=n2 textbox \"Phone\" value=\"5551234567\"\n";
let new = "uid=n2 textbox \"Phone\" value=\"(555) 123-4567\"\n";
assert!(diff_snapshots(old, new).values_lost.is_empty());
}
#[test]
fn a_node_that_vanished_is_a_removal_not_a_lost_value() {
let old = "uid=n2 textbox \"Email\" value=\"a@b.c\"\n";
let new = "uid=n9 heading \"Thanks\"\n";
let d = diff_snapshots(old, new);
assert_eq!(d.removed, 1, "{}", d.text);
assert!(d.values_lost.is_empty(), "{}", d.text);
}
#[test]
fn no_value_is_claimed_lost_across_a_document_change() {
let old = "uid=n2 textbox \"Email\" value=\"a@b.c\"\n";
let new = "uid=n2 heading \"Other page\"\n";
for identity in [Identity::Different, Identity::Unknown] {
assert!(compare(identity, old, new).values_lost.is_empty(), "for {identity:?}");
}
}
#[test]
fn lost_values_handle_spaces_and_refuse_ambiguous_lines() {
let old = "uid=n2 textbox \"Address\" value=\"12 Rue de la Paix\"\n";
let new = "uid=n2 textbox \"Address\"\n";
assert_eq!(diff_snapshots(old, new).values_lost[0].was, "12 Rue de la Paix");
let old = "uid=n7 textbox \"\"odd\" value=\"x\"\n";
let new = "uid=n7 textbox \"\"odd\"\n";
assert!(diff_snapshots(old, new).values_lost.is_empty(), "no guess at token boundaries");
}
#[test]
fn an_unreadable_identity_does_not_claim_the_document_is_the_same() {
let old = "uid=n1 heading \"Old\"\n";
let new = "uid=n1 heading \"New\"\n";
let c = compare(Identity::Unknown, old, new);
assert!(!c.identity_known, "we could not tell: {c:?}");
assert_eq!(c.changed, 0, "so nothing may be reported as changed: {}", c.text);
assert_eq!(c.text, new, "the caller gets the page instead of a guess");
assert!(c.hint.is_some(), "and is told why");
}
#[test]
fn a_same_document_identity_still_diffs() {
let old = "uid=n1 heading \"Old\"\n";
let new = "uid=n1 heading \"New\"\n";
let c = compare(Identity::Same, old, new);
assert!(c.identity_known);
assert!(!c.document_changed);
assert_eq!(c.changed, 1, "{}", c.text);
}
#[test]
fn a_reload_to_the_same_url_is_a_different_document() {
let old = "uid=n1 heading \"Before\"\n";
let new = "uid=n1 heading \"After\"\n";
let c = compare(Identity::Different, old, new);
assert!(c.document_changed);
assert_eq!((c.added, c.removed, c.changed), (0, 0, 0));
}
#[test]
fn a_changed_document_reports_no_edits_whatever_the_snapshot_contains() {
let old = "uid=n1 heading \"Old page\"\n";
let new = "uid=n1 heading \"Save\n- and exit\"\nuid=n2 button \"Go\"\n";
let c = compare(Identity::Different, old, new);
assert!(c.document_changed);
assert_eq!((c.added, c.removed, c.changed), (0, 0, 0), "no edit can be claimed across documents");
assert_eq!(c.text, new, "the caller gets the destination page");
}
#[test]
fn counts_match_the_rendered_lines() {
let old = "uid=n1 heading \"A\"\nuid=n2 button \"B\"\n";
let new = "uid=n1 heading \"A changed\"\nuid=n3 link \"C\"\n";
let d = diff_snapshots(old, new);
assert_eq!((d.added, d.removed, d.changed, d.unchanged), (1, 1, 1, 0));
assert_eq!(d.text.lines().filter(|l| l.starts_with("+ ")).count(), d.added);
assert_eq!(d.text.lines().filter(|l| l.starts_with("- ")).count(), d.removed);
assert_eq!(d.text.lines().filter(|l| l.starts_with("~ ")).count(), d.changed);
}
#[test]
fn lines_follow_document_order() {
let old = "uid=n1 heading \"A\"\nuid=n2 button \"B\"\nuid=n3 link \"C\"\nuid=n4 link \"D\"\n";
let new = "uid=n1 heading \"A\"\nuid=n3 link \"C changed\"\nuid=n5 link \"E\"\nuid=n6 link \"F\"\n";
let result = diff_snapshots(old, new);
let lines: Vec<&str> = result.text.lines().filter(|l| !l.starts_with('=')).collect();
assert_eq!(
lines,
vec![
"+ uid=n5 link \"E\"",
"+ uid=n6 link \"F\"",
"- uid=n2 button \"B\"",
"- uid=n4 link \"D\"",
"~ uid=n3 link \"C\" -> \"C changed\"",
],
"added/removed/changed must each follow document order"
);
}
#[test]
fn no_changes() {
let snap = "uid=n1 heading \"Hello\"\nuid=n2 button \"OK\"\n";
let result = diff_snapshots(snap, snap);
assert!(result.text.contains("No changes"));
}
#[test]
fn added_element() {
let old = "uid=n1 heading \"Hello\"\n";
let new = "uid=n1 heading \"Hello\"\nuid=n2 button \"OK\"\n";
let result = diff_snapshots(old, new);
assert!(result.text.contains("+ uid=n2 button \"OK\""));
assert!(result.text.contains("= 1 unchanged"));
assert_eq!(result.added, 1);
assert_eq!(result.removed, 0);
assert_eq!(result.changed, 0);
}
#[test]
fn removed_element() {
let old = "uid=n1 heading \"Hello\"\nuid=n2 button \"OK\"\n";
let new = "uid=n1 heading \"Hello\"\n";
let result = diff_snapshots(old, new);
assert!(result.text.contains("- uid=n2 button \"OK\""));
assert_eq!(result.removed, 1);
}
#[test]
fn changed_element() {
let old = "uid=n1 textbox value=\"\"\n";
let new = "uid=n1 textbox value=\"hello\"\n";
let result = diff_snapshots(old, new);
assert!(result.text.contains("~ uid=n1 textbox"));
assert_eq!(result.changed, 1);
}
#[test]
fn mixed_changes() {
let old = "uid=n1 heading \"Title\"\nuid=n2 button \"Submit\"\nuid=n3 textbox value=\"\"\n";
let new = "uid=n1 heading \"Title\"\nuid=n3 textbox value=\"done\"\nuid=n4 heading \"Success\"\n";
let result = diff_snapshots(old, new);
assert!(result.text.contains("+ uid=n4"));
assert!(result.text.contains("- uid=n2"));
assert!(result.text.contains("~ uid=n3"));
assert!(result.text.contains("= 1 unchanged"));
}
#[test]
fn indented_lines() {
let old = " uid=n1 heading \"Hello\"\n uid=n2 button \"OK\"\n";
let new = " uid=n1 heading \"Hello\"\n uid=n3 link \"New\"\n";
let result = diff_snapshots(old, new);
assert!(result.text.contains("+ uid=n3"));
assert!(result.text.contains("- uid=n2"));
}
}