use super::CorrelationStatus;
use super::atoms::ComparisonUnitAtom;
#[derive(Default)]
pub(crate) struct U64IdentityHasher(u64);
impl std::hash::Hasher for U64IdentityHasher {
#[inline]
fn finish(&self) -> u64 {
self.0
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.0 = i;
}
#[inline]
fn write(&mut self, bytes: &[u8]) {
for &b in bytes {
self.0 = self.0.rotate_left(8) ^ u64::from(b);
}
}
}
pub(crate) type U64BuildHasher = std::hash::BuildHasherDefault<U64IdentityHasher>;
#[derive(Clone, Debug)]
pub struct TaggedAtom {
pub atom: ComparisonUnitAtom,
pub status: CorrelationStatus,
}
pub fn correlate_atoms(
atoms1: &[ComparisonUnitAtom],
atoms2: &[ComparisonUnitAtom],
) -> Vec<TaggedAtom> {
let mut out = Vec::new();
do_lcs(atoms1, atoms2, &mut out);
out
}
fn tag_all(atoms: &[ComparisonUnitAtom], status: CorrelationStatus, out: &mut Vec<TaggedAtom>) {
for a in atoms {
out.push(TaggedAtom {
atom: a.clone(),
status,
});
}
}
fn do_lcs(cul1: &[ComparisonUnitAtom], cul2: &[ComparisonUnitAtom], out: &mut Vec<TaggedAtom>) {
if cul1.is_empty() && cul2.is_empty() {
return;
}
if cul2.is_empty() {
tag_all(cul1, CorrelationStatus::Deleted, out);
return;
}
if cul1.is_empty() {
tag_all(cul2, CorrelationStatus::Inserted, out);
return;
}
let mut best_len = 0usize;
let mut best_i1 = usize::MAX;
let mut best_i2 = usize::MAX;
let mut i1 = 0;
while i1 + best_len < cul1.len() {
let mut i2 = 0;
while i2 + best_len < cul2.len() {
let mut len = 0;
let (mut t1, mut t2) = (i1, i2);
while t1 < cul1.len() && t2 < cul2.len() && cul1[t1].sha1_hash == cul2[t2].sha1_hash {
t1 += 1;
t2 += 1;
len += 1;
}
if len > best_len {
best_len = len;
best_i1 = i1;
best_i2 = i2;
}
i2 += 1;
}
i1 += 1;
}
if best_len == 0 {
tag_all(cul1, CorrelationStatus::Deleted, out);
tag_all(cul2, CorrelationStatus::Inserted, out);
return;
}
do_lcs(&cul1[..best_i1], &cul2[..best_i2], out);
tag_all(
&cul2[best_i2..best_i2 + best_len],
CorrelationStatus::Equal,
out,
);
do_lcs(
&cul1[best_i1 + best_len..],
&cul2[best_i2 + best_len..],
out,
);
}
use super::atoms::{ComparisonUnit, CorrelatedSequence};
use super::{ComparisonUnitGroupType, WmlComparerSettings};
use crate::namespaces::{PT, W};
use crate::xmllinq::Dom;
fn atom_is_ppr(dom: &Dom, a: &ComparisonUnitAtom) -> bool {
dom.name_is(a.content_element, &W::p_pr())
}
fn unit_is_single_atom_ppr(dom: &Dom, u: &ComparisonUnit) -> bool {
matches!(u, ComparisonUnit::Word(w) if w.contents.len() == 1 && atom_is_ppr(dom, &w.contents[0]))
}
fn unit_para_has_numpr(dom: &Dom, u: &ComparisonUnit) -> bool {
let p_name = W::name("p");
let num_pr = W::num_pr();
let mut found = false;
u.try_for_each_atom(&mut |atom| {
for &ae in atom.ancestor_elements.iter() {
if !dom.name_is(ae, &p_name.clone()) {
continue;
}
if let Some(ppr) = dom.element(ae, &W::p_pr()) {
found = dom.element(ppr, &num_pr).is_some();
}
return false;
}
true
});
found
}
fn unit_para_ilvl(dom: &Dom, u: &ComparisonUnit) -> Option<u32> {
let p_name = W::name("p");
let num_pr = W::num_pr();
let ilvl_name = W::name("ilvl");
let mut out: Option<u32> = None;
u.try_for_each_atom(&mut |atom| {
for &ae in atom.ancestor_elements.iter() {
if !dom.name_is(ae, &p_name.clone()) {
continue;
}
out = (|| {
let ppr = dom.element(ae, &W::p_pr())?;
let num = dom.element(ppr, &num_pr)?;
let Some(il) = dom.element(num, &ilvl_name) else {
return Some(0);
};
dom.attribute(il, &W::val()).and_then(|v| v.parse().ok())
})();
return false;
}
true
});
out
}
fn first_list_cluster_end(dom: &Dom, cul: &[ComparisonUnit]) -> usize {
let mut saw_sub = false;
let mut end = 0usize;
for (i, u) in cul.iter().enumerate() {
let empty = !unit_has_text_token(dom, u);
if empty {
end = i + 1;
continue;
}
let ilvl = unit_para_ilvl(dom, u).unwrap_or(0);
if saw_sub && ilvl == 0 {
return end;
}
if ilvl >= 1 {
saw_sub = true;
}
end = i + 1;
}
end
}
fn legal_mid_splice_cut(dom: &Dom, cu: &[ComparisonUnit]) -> Option<usize> {
let mut markers = 0usize;
for (i, u) in cu.iter().enumerate() {
if as_group(u).is_none() {
continue;
}
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
let mut heading_level: Option<u32> = None;
for a in u.descendant_atoms() {
for &ae in a.ancestor_elements.iter() {
if !dom.name_is(ae, &W::name("p")) {
continue;
}
if let Some(ppr) = dom.element(ae, &W::p_pr())
&& let Some(ps) = dom.element(ppr, &W::p_style())
{
let v = dom
.attribute(ps, &W::val())
.unwrap_or("")
.to_ascii_lowercase();
if let Some(rest) = v.strip_prefix("heading") {
heading_level = rest.parse().ok().or(Some(1));
} else if v == "title" {
heading_level = Some(0);
}
}
break;
}
if heading_level.is_some() {
break;
}
}
let first = toks.first().map(|s| s.as_str()).unwrap_or("");
let num_prefix = {
let digits: String = first.chars().take_while(|c| c.is_ascii_digit()).collect();
!digits.is_empty()
&& (first.len() == digits.len()
|| first[digits.len()..].chars().all(|c| c == '.' || c == ')'))
&& toks.len() <= 10
};
let is_section = num_prefix || heading_level.is_some_and(|h| h >= 2);
if is_section {
markers += 1;
if markers >= 3 {
return Some(i + 1);
}
}
}
None
}
fn looks_like_memo_doc(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut saw_memo_title = false;
let mut saw_to = false;
let mut saw_from = false;
for u in cu.iter().take(12) {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
let joined = toks.join(" ").to_ascii_lowercase();
if joined.starts_with("memorandum") {
saw_memo_title = true;
}
if toks.first().is_some_and(|t| t.eq_ignore_ascii_case("to")) {
saw_to = true;
}
if toks.first().is_some_and(|t| t.eq_ignore_ascii_case("from")) {
saw_from = true;
}
}
saw_memo_title || (saw_to && saw_from)
}
fn memo_header_cut(dom: &Dom, cu: &[ComparisonUnit]) -> Option<usize> {
let mut saw_header = false;
for (i, u) in cu.iter().enumerate() {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
let first = toks.first().map(|s| s.as_str()).unwrap_or("");
if first.eq_ignore_ascii_case("to")
|| first.eq_ignore_ascii_case("from")
|| first.eq_ignore_ascii_case("date")
|| first.eq_ignore_ascii_case("re")
|| first.eq_ignore_ascii_case("memorandum")
{
saw_header = true;
}
if first.eq_ignore_ascii_case("dear") {
return Some(i + 1);
}
if saw_header
&& toks.len() >= 8
&& !first.eq_ignore_ascii_case("to")
&& !first.eq_ignore_ascii_case("from")
&& !first.eq_ignore_ascii_case("date")
&& !first.eq_ignore_ascii_case("re")
{
return Some(i);
}
}
if saw_header {
Some(cu.len().min(12))
} else {
None
}
}
fn looks_like_math_borderbox_doc(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut saw = false;
for u in cu.iter().take(30) {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
let joined = toks.join(" ").to_ascii_lowercase();
if joined.contains("borderbox")
|| joined.contains("m:box")
|| joined.contains("m:borderbox")
|| (joined.contains("border") && joined.contains("box") && joined.contains("math"))
{
saw = true;
break;
}
}
saw
}
fn looks_like_math_doc(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
for u in cu.iter().take(30) {
if !unit_has_text_token(dom, u) {
continue;
}
let clean = u.try_for_each_atom(&mut |a| {
if dom
.name(a.content_element)
.is_some_and(|n| n.local_name() == "oMath" || n.local_name() == "oMathPara")
{
return false;
}
!a.ancestor_elements.iter().copied().any(|ae| {
dom.name(ae)
.is_some_and(|n| n.local_name() == "oMath" || n.local_name() == "oMathPara")
})
});
if !clean {
return true;
}
}
false
}
fn is_alpha_list_label_token(t: &str) -> bool {
let lower = t.to_ascii_lowercase();
matches!(
lower.as_str(),
"one"
| "two"
| "three"
| "four"
| "five"
| "six"
| "seven"
| "eight"
| "nine"
| "ten"
| "a"
| "b"
| "c"
| "d"
| "e"
| "f"
| "g"
| "h"
| "i"
| "j"
| "k"
| "l"
| "m"
| "n"
| "o"
| "p"
| "q"
| "r"
| "s"
| "t"
| "u"
| "v"
| "w"
| "x"
| "y"
| "z"
| "ii"
| "iii"
| "iv"
| "vi"
| "vii"
| "viii"
| "ix"
) || (t.len() <= 3 && t.chars().all(|c| c.is_ascii_digit()))
}
fn looks_like_short_alpha_list(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut contentful = 0usize;
let mut alpha_labels = 0usize;
for u in cu {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
contentful += 1;
if contentful > 4 {
return false;
}
if toks.len() > 2 {
return false;
}
if toks.iter().any(|t| t.chars().count() > 8) {
return false;
}
if toks.iter().any(|t| is_alpha_list_label_token(t)) {
alpha_labels += 1;
}
}
(1..=4).contains(&contentful) && alpha_labels * 2 >= contentful
}
fn looks_like_short_alpha_list_cluster(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut contentful = 0usize;
let mut single = 0usize;
let mut alpha_labels = 0usize;
for u in cu {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
contentful += 1;
if contentful > 20 {
return false;
}
if toks.len() > 2 {
return false;
}
if toks.iter().any(|t| t.chars().count() > 12) {
return false;
}
if toks.len() == 1 && toks[0].chars().count() <= 5 {
single += 1;
}
if toks.iter().any(|t| is_alpha_list_label_token(t)) {
alpha_labels += 1;
}
}
(5..=20).contains(&contentful) && single * 2 >= contentful && alpha_labels * 2 >= contentful
}
fn looks_like_short_title_page(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut contentful = 0usize;
let mut markers = 0usize;
for u in cu {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
contentful += 1;
if contentful > 14 {
return false;
}
let joined = toks.join(" ").to_ascii_lowercase();
if joined.contains("agreement")
|| joined.contains("prepared by")
|| joined.contains("memorandum")
|| joined.contains("apprenticeship")
|| joined.contains("@")
|| joined.contains("march ")
|| joined.contains("january ")
|| joined.contains("february ")
|| joined.contains("april ")
|| joined.contains("may ")
|| joined.contains("june ")
|| joined.contains("july ")
|| joined.contains("august ")
|| joined.contains("september ")
|| joined.contains("october ")
|| joined.contains("november ")
|| joined.contains("december ")
|| (joined.starts_with('[') && joined.ends_with(']'))
|| joined == "to"
|| joined == "from"
|| joined == "date"
|| joined == "re"
{
markers += 1;
}
}
(4..=12).contains(&contentful) && markers >= 2
}
fn looks_like_short_label_stubs(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut contentful = 0usize;
let mut stubs = 0usize;
for u in cu {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
contentful += 1;
if contentful > 12 {
return false;
}
let is_stub = (toks.len() == 1 && toks[0].chars().count() <= 3)
|| (toks.len() <= 2 && toks.iter().all(|t| t.chars().count() <= 5));
if is_stub {
stubs += 1;
}
}
(4..=12).contains(&contentful) && stubs * 2 >= contentful
}
fn looks_like_fields_html_doc(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
for u in cu.iter().take(20) {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
let joined = toks.join(" ").to_ascii_lowercase();
if joined.contains("html input type") {
return true;
}
}
false
}
fn looks_like_short_annotation_doc(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
let mut contentful = 0usize;
let mut saw_marker = false;
for u in cu {
let toks = para_text_token_list(dom, u);
if toks.is_empty() {
continue;
}
contentful += 1;
if contentful > 6 {
return false;
}
let joined = toks.join(" ").to_ascii_lowercase();
if joined.contains("suggest")
|| joined.contains("leave a comment")
|| joined.contains("oftentimes")
{
saw_marker = true;
}
}
saw_marker && (1..=6).contains(&contentful)
}
fn mostly_list_paras(dom: &Dom, paras: &[Vec<ComparisonUnit>]) -> bool {
let contentful: Vec<&Vec<ComparisonUnit>> = paras
.iter()
.filter(|p| p.iter().any(|cu| !unit_is_single_atom_ppr(dom, cu)))
.collect();
if contentful.is_empty() {
return false;
}
let with_num = contentful
.iter()
.filter(|p| p.iter().any(|cu| unit_para_has_numpr(dom, cu)))
.count();
with_num * 2 >= contentful.len()
}
const SHORT_LIST_ITEM_MAX_CONTENT_UNITS: usize = 12;
fn short_item_list_paras(dom: &Dom, paras: &[Vec<ComparisonUnit>]) -> bool {
let contentful: Vec<&Vec<ComparisonUnit>> = paras
.iter()
.filter(|p| p.iter().any(|cu| !unit_is_single_atom_ppr(dom, cu)))
.collect();
if contentful.is_empty() {
return false;
}
contentful.iter().all(|p| {
let n = p
.iter()
.filter(|cu| !unit_is_single_atom_ppr(dom, cu))
.count();
n <= SHORT_LIST_ITEM_MAX_CONTENT_UNITS
})
}
fn short_item_list_groups(dom: &Dom, xs: &[&ComparisonUnit]) -> bool {
if xs.is_empty() {
return false;
}
xs.iter()
.all(|u| unit_text_token_count(dom, u) <= SHORT_LIST_ITEM_MAX_CONTENT_UNITS)
}
fn unit_first_atom_is_ppr(dom: &Dom, u: &ComparisonUnit) -> bool {
u.first_atom().is_some_and(|a| atom_is_ppr(dom, a))
}
fn unit_last_atom_is_ppr(dom: &Dom, u: &ComparisonUnit) -> bool {
u.last_atom().is_some_and(|a| atom_is_ppr(dom, a))
}
fn word_first_not_ppr(dom: &Dom, u: &ComparisonUnit) -> bool {
match u {
ComparisonUnit::Word(w) => w.contents.first().is_none_or(|a| !atom_is_ppr(dom, a)),
ComparisonUnit::Group(_) => false,
}
}
fn take_while_count_rev(slice: &[ComparisonUnit], pred: impl Fn(&ComparisonUnit) -> bool) -> usize {
slice.iter().rev().take_while(|u| pred(u)).count()
}
pub fn find_index_of_next_para_mark(dom: &Dom, cul: &[ComparisonUnit]) -> usize {
cul.iter()
.position(|u| unit_last_atom_is_ppr(dom, u))
.unwrap_or(cul.len())
}
pub fn split_at_paragraph_mark(dom: &Dom, cua: &[ComparisonUnit]) -> Vec<Vec<ComparisonUnit>> {
match cua.iter().position(|u| unit_first_atom_is_ppr(dom, u)) {
None => vec![cua.to_vec()],
Some(i) => vec![cua[..i].to_vec(), cua[i..].to_vec()],
}
}
pub fn longest_common_run(
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
) -> (usize, usize, usize) {
longest_common_run_with_dom(None, cul1, cul2, None)
}
fn longest_common_run_with_dom(
dom: Option<&Dom>,
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
settings: Option<&WmlComparerSettings>,
) -> (usize, usize, usize) {
longest_common_run_indexed(dom, cul1, cul2, settings)
}
#[inline]
fn extend_common_run(
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
i1: usize,
i2: usize,
) -> usize {
let (mut t1, mut t2) = (i1, i2);
let mut len = 0;
while t1 < cul1.len() && t2 < cul2.len() && cul1[t1].sha1_key128() == cul2[t2].sha1_key128() {
t1 += 1;
t2 += 1;
len += 1;
}
len
}
#[inline]
fn common_run_content_score(
dom: Option<&Dom>,
cul1: &[ComparisonUnit],
i1: usize,
len: usize,
settings: Option<&WmlComparerSettings>,
prefix: Option<&[usize]>,
) -> usize {
if let Some(p) = prefix {
debug_assert_eq!(p.len(), cul1.len() + 1);
return p[i1 + len] - p[i1];
}
if let (Some(d), Some(s)) = (dom, settings) {
run_non_separator_text_len(d, &cul1[i1..i1 + len], s)
} else {
len
}
}
fn unit_non_separator_text_len(
dom: &Dom,
unit: &ComparisonUnit,
settings: &WmlComparerSettings,
) -> usize {
let mut score = 0usize;
match unit {
ComparisonUnit::Word(w) => {
for a in &w.contents {
if dom.name_is(a.content_element, &W::t()) {
score += dom
.value_str(a.content_element)
.chars()
.filter(|ch| !settings.word_separators.contains(ch) && !ch.is_whitespace())
.count();
}
}
}
ComparisonUnit::Group(g) => {
for c in &g.contents {
score += unit_non_separator_text_len(dom, c, settings);
}
}
}
score
}
fn non_separator_prefix_sums(
dom: &Dom,
cul: &[ComparisonUnit],
settings: &WmlComparerSettings,
) -> Vec<usize> {
let mut prefix = Vec::with_capacity(cul.len() + 1);
prefix.push(0);
for u in cul {
let s = unit_non_separator_text_len(dom, u, settings);
prefix.push(prefix.last().copied().unwrap_or(0) + s);
}
prefix
}
#[inline]
fn consider_candidate(
best: &mut Option<(usize, usize, usize, usize)>,
cand: (usize, usize, usize, usize),
) {
let better = match best {
None => true,
Some(b) => cand.0 > b.0 || (cand.0 == b.0 && cand.1 > b.1),
};
if better {
*best = Some(cand);
}
}
#[cfg(test)]
fn longest_common_run_scan(
dom: Option<&Dom>,
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
settings: Option<&WmlComparerSettings>,
) -> (usize, usize, usize) {
let prefix = match (dom, settings) {
(Some(d), Some(s)) => Some(non_separator_prefix_sums(d, cul1, s)),
_ => None,
};
let mut best: Option<(usize, usize, usize, usize)> = None;
for i1 in 0..cul1.len() {
for i2 in 0..cul2.len() {
let len = extend_common_run(cul1, cul2, i1, i2);
if len > 0 {
let content =
common_run_content_score(dom, cul1, i1, len, settings, prefix.as_deref());
consider_candidate(&mut best, (content, len, i1, i2));
}
}
}
best.map(|(_, len, i1, i2)| (i1, i2, len))
.unwrap_or((0, 0, 0))
}
fn longest_common_run_indexed(
dom: Option<&Dom>,
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
settings: Option<&WmlComparerSettings>,
) -> (usize, usize, usize) {
let prefix = match (dom, settings) {
(Some(d), Some(s)) => Some(non_separator_prefix_sums(d, cul1, s)),
_ => None,
};
let mut index: std::collections::HashMap<u64, Vec<usize>, U64BuildHasher> =
std::collections::HashMap::with_capacity_and_hasher(cul2.len(), U64BuildHasher::default());
for (i2, u) in cul2.iter().enumerate() {
index.entry(u.sha1_key()).or_default().push(i2);
}
let mut best: Option<(usize, usize, usize, usize)> = None;
for i1 in 0..cul1.len() {
let Some(positions) = index.get(&cul1[i1].sha1_key()) else {
continue;
};
for &i2 in positions {
if i1 > 0 && i2 > 0 && cul1[i1 - 1].sha1_key128() == cul2[i2 - 1].sha1_key128() {
continue;
}
let len = extend_common_run(cul1, cul2, i1, i2);
if len > 0 {
let content =
common_run_content_score(dom, cul1, i1, len, settings, prefix.as_deref());
consider_candidate(&mut best, (content, len, i1, i2));
}
}
}
best.map(|(_, len, i1, i2)| (i1, i2, len))
.unwrap_or((0, 0, 0))
}
fn run_real_text_len(dom: &Dom, run: &[ComparisonUnit]) -> usize {
run.iter()
.flat_map(|u| u.descendant_atoms())
.filter(|a| dom.name_is(a.content_element, &W::t()))
.map(|a| dom.value_str(a.content_element).trim().chars().count())
.sum()
}
fn run_non_separator_text_len(
dom: &Dom,
run: &[ComparisonUnit],
settings: &WmlComparerSettings,
) -> usize {
run.iter()
.flat_map(|u| u.descendant_atoms())
.filter(|a| dom.name_is(a.content_element, &W::t()))
.map(|a| {
dom.value_str(a.content_element)
.chars()
.filter(|ch| !settings.word_separators.contains(ch) && !ch.is_whitespace())
.count()
})
.sum()
}
fn significant_body_tokens(dom: &Dom, cu: &[ComparisonUnit]) -> std::collections::HashSet<String> {
para_text_tokens_from_units(dom, cu)
.into_iter()
.filter(|t| t.chars().count() >= 3 && !t.starts_with("file_") && t != "docx" && t != "doc")
.collect()
}
fn body_token_overlap_ratio(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> f64 {
let a = significant_body_tokens(dom, cu1);
let b = significant_body_tokens(dom, cu2);
if a.is_empty() || b.is_empty() {
return 0.0;
}
let inter = a.intersection(&b).count() as f64;
let min = a.len().min(b.len()) as f64;
inter / min
}
const STAMP_CONFETTI_MAX_BODY_OVERLAP: f64 = 0.55;
const RELATED_STAMP_MIN_BODY_TOKENS: usize = 40;
fn is_related_stamped_variant(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
let a = significant_body_tokens(dom, cu1);
let b = significant_body_tokens(dom, cu2);
let min_n = a.len().min(b.len());
let ratio = body_token_overlap_ratio(dom, cu1, cu2);
if min_n < RELATED_STAMP_MIN_BODY_TOKENS {
return false;
}
ratio >= STAMP_CONFETTI_MAX_BODY_OVERLAP
}
fn should_stamp_confetti(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
!is_related_stamped_variant(dom, cu1, cu2)
}
fn first_contentful_para_text(dom: &Dom, cu: &[ComparisonUnit]) -> Option<String> {
first_contentful_group_index(dom, cu).map(|i| {
let mut text = String::new();
for a in cu[i].descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
text
})
}
fn first_contentful_group_index(dom: &Dom, cu: &[ComparisonUnit]) -> Option<usize> {
cu.iter()
.position(|u| as_group(u).is_some() && run_real_text_len(dom, std::slice::from_ref(u)) > 0)
}
const STAMP_RESIDUAL_PAIR_MIN_JACCARD: f64 = 0.25;
const STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG: f64 = 0.10;
const STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG_BODY: f64 = 0.05;
const STAMP_RESIDUAL_PAIR_MIN_SHARED_SIG: usize = 3;
const STAMP_RESIDUAL_PAIR_MIN_SHARED_SIG_SHORT: usize = 2;
const STAMP_RESIDUAL_ORDERED_PREFIX_MIN_SIG: usize = 2;
const STAMP_RESIDUAL_PAIR_SHORT_MAX_TOKENS: usize = 8;
const STAMP_RESIDUAL_LAST_SIG_MAX_TOKENS: usize = 16;
const STAMP_RESIDUAL_CONNECTORS: &[&str] = &["and", "or", "the", "for", "with", "to"];
fn significant_tokens(
tokens: &std::collections::HashSet<String>,
) -> std::collections::HashSet<String> {
tokens
.iter()
.filter(|t| t.chars().count() >= 4)
.cloned()
.collect()
}
fn shared_connector_tokens(
left: &std::collections::HashSet<String>,
right: &std::collections::HashSet<String>,
) -> usize {
left.iter()
.filter(|t| {
t.chars().count() == 3
&& STAMP_RESIDUAL_CONNECTORS
.iter()
.any(|c| t.eq_ignore_ascii_case(c))
&& right.iter().any(|r| r.eq_ignore_ascii_case(t))
})
.count()
}
fn unit_text_token_count(dom: &Dom, u: &ComparisonUnit) -> usize {
let mut count = 0usize;
let mut in_token = false;
u.try_for_each_atom(&mut |a| {
if dom.name_is(a.content_element, &W::t()) {
for c in dom.value_str(a.content_element).chars() {
if c.is_alphanumeric() {
if !in_token {
count += 1;
in_token = true;
}
} else {
in_token = false;
}
}
}
true
});
count
}
fn unit_has_text_token(dom: &Dom, u: &ComparisonUnit) -> bool {
!u.try_for_each_atom(&mut |a| {
if dom.name_is(a.content_element, &W::t())
&& dom
.value_str(a.content_element)
.chars()
.any(|c| c.is_alphanumeric())
{
return false;
}
true
})
}
fn para_text_token_list(dom: &Dom, u: &ComparisonUnit) -> Vec<String> {
let mut text = String::new();
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
text.split(|c: char| !c.is_alphanumeric())
.filter(|t| !t.is_empty())
.map(|t| t.to_ascii_lowercase())
.collect()
}
fn para_text_tokens_joined(dom: &Dom, u: &ComparisonUnit) -> std::collections::HashSet<String> {
para_text_token_list(dom, u).into_iter().collect()
}
fn last_significant_token(ordered: &[String]) -> Option<&str> {
ordered
.iter()
.rev()
.find(|t| t.chars().count() >= 4)
.map(|s| s.as_str())
}
fn ordered_shared_prefix_sig(left: &[String], right: &[String]) -> usize {
let li: Vec<&str> = left
.iter()
.filter(|t| t.chars().count() >= 4)
.map(|s| s.as_str())
.collect();
let rj: Vec<&str> = right
.iter()
.filter(|t| t.chars().count() >= 4)
.map(|s| s.as_str())
.collect();
let mut n = 0usize;
for (a, b) in li.iter().zip(rj.iter()) {
if a.eq_ignore_ascii_case(b) {
n += 1;
} else {
break;
}
}
n
}
fn stamp_residual_pairs(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> Vec<(usize, usize)> {
if rest1.is_empty() || rest2.is_empty() || rest1.len() > 6 {
return Vec::new();
}
let left_ord: Vec<_> = rest1.iter().map(|u| para_text_token_list(dom, u)).collect();
let right_ord: Vec<_> = rest2.iter().map(|u| para_text_token_list(dom, u)).collect();
let left: Vec<std::collections::HashSet<String>> = left_ord
.iter()
.map(|v| v.iter().cloned().collect())
.collect();
let right: Vec<std::collections::HashSet<String>> = right_ord
.iter()
.map(|v| v.iter().cloned().collect())
.collect();
let mut candidates: Vec<(u8, f64, usize, usize)> = Vec::new();
for (i, li) in left.iter().enumerate() {
if li.is_empty() {
continue;
}
let li_sig = significant_tokens(li);
let li_last = last_significant_token(&left_ord[i]);
for (j, rj) in right.iter().enumerate() {
if rj.is_empty() {
continue;
}
let rj_sig = significant_tokens(rj);
let shared_sig = li_sig.intersection(&rj_sig).count();
let short_pair = li.len() <= STAMP_RESIDUAL_PAIR_SHORT_MAX_TOKENS
&& rj.len() <= STAMP_RESIDUAL_PAIR_SHORT_MAX_TOKENS;
let last_sig_len_ok = li.len() <= STAMP_RESIDUAL_LAST_SIG_MAX_TOKENS
&& rj.len() <= STAMP_RESIDUAL_LAST_SIG_MAX_TOKENS;
let last_sig_match = last_sig_len_ok
&& li_last.is_some()
&& li_last == last_significant_token(&right_ord[j]);
let connector_only =
short_pair && i == 0 && shared_sig == 0 && shared_connector_tokens(li, rj) > 0;
let ordered_prefix = rest2.len() <= 20
&& ordered_shared_prefix_sig(&left_ord[i], &right_ord[j])
>= STAMP_RESIDUAL_ORDERED_PREFIX_MIN_SIG;
let last_appears_in_next = li_last.is_some_and(|tok| {
!M135_OFF_DIAG_BOILER
.iter()
.any(|b| tok.eq_ignore_ascii_case(b))
&& right_ord[j].iter().any(|t| t.eq_ignore_ascii_case(tok))
});
let off_diag_body = i >= 1
&& j > i
&& last_appears_in_next
&& rest1.len() <= 4
&& rest2.len() <= 4
&& li.len() <= STAMP_RESIDUAL_LAST_SIG_MAX_TOKENS
&& rj.len() <= STAMP_RESIDUAL_LAST_SIG_MAX_TOKENS;
let min_sig = if last_sig_match || connector_only || ordered_prefix || off_diag_body {
1
} else if short_pair {
STAMP_RESIDUAL_PAIR_MIN_SHARED_SIG_SHORT
} else {
STAMP_RESIDUAL_PAIR_MIN_SHARED_SIG
};
if shared_sig < min_sig && !connector_only && !ordered_prefix {
continue;
}
let jacc = token_jaccard(li, rj);
let min_jacc = if last_sig_match {
if short_pair {
STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG
} else {
STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG_BODY
}
} else if off_diag_body {
STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG_BODY
} else if connector_only || ordered_prefix {
STAMP_RESIDUAL_PAIR_MIN_JACCARD_LAST_SIG
} else {
STAMP_RESIDUAL_PAIR_MIN_JACCARD
};
if jacc + 1e-12 >= min_jacc {
let tier: u8 = if last_sig_match {
3
} else if off_diag_body {
2
} else {
1
};
candidates.push((tier, jacc, i, j));
}
}
}
candidates.sort_by(|a, b| {
b.0.cmp(&a.0)
.then_with(|| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal))
.then_with(|| a.3.cmp(&b.3))
.then_with(|| a.2.cmp(&b.2))
});
let mut used_i = std::collections::HashSet::new();
let mut used_j = std::collections::HashSet::new();
let mut pairs = Vec::new();
for (_tier, _jacc, i, j) in candidates {
if used_i.contains(&i) || used_j.contains(&j) {
continue;
}
used_i.insert(i);
used_j.insert(j);
pairs.push((i, j));
}
pairs.sort_by_key(|&(_, j)| j);
pairs
}
fn stamp_confetti_then_replace(
dom: &mut Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
settings: &WmlComparerSettings,
) -> Option<Vec<CorrelatedSequence>> {
let residual_flag_settings = {
let mut s2 = settings.clone();
s2.in_stamp_residual = true;
s2
};
let settings = &residual_flag_settings;
let i1 = first_contentful_group_index(dom, cu1)?;
let i2 = first_contentful_group_index(dom, cu2)?;
let mut stamp_seqs = lcs(dom, vec![cu1[i1].clone()], vec![cu2[i2].clone()], settings);
let mut rest1 = Vec::new();
rest1.extend_from_slice(&cu1[..i1]);
rest1.extend_from_slice(&cu1[i1 + 1..]);
let mut rest2 = Vec::new();
rest2.extend_from_slice(&cu2[..i2]);
rest2.extend_from_slice(&cu2[i2 + 1..]);
if (3..=10).contains(&rest1.len())
&& (3..=10).contains(&rest2.len())
&& residual_looks_like_colon_list(dom, &rest1)
&& residual_looks_like_colon_list(dom, &rest2)
{
let mut left: Vec<ComparisonUnit> = rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
return Some(stamp_seqs);
}
let pairs = stamp_residual_pairs(dom, &rest1, &rest2);
let off_diagonal_pair = pairs.iter().any(|&(i, j)| i != j);
if rest1.len() == rest2.len()
&& (2..=6).contains(&rest1.len())
&& !off_diagonal_pair
&& para_zip_diagonal_dominant(dom, &rest1, &rest2)
&& {
let covers_body = pairs.iter().any(|&(i, _)| i >= 1);
let (min_d, avg_d, max_body) = m123_diagonal_stats(dom, &rest1, &rest2);
let path_a = !covers_body && max_body + 1e-12 >= 0.09;
let path_b = min_d + 1e-12 >= 0.14 && avg_d + 1e-12 >= 0.16;
path_a || path_b
}
{
for (a, b) in rest1.iter().zip(rest2.iter()) {
let mut nested = lcs(dom, vec![a.clone()], vec![b.clone()], settings);
stamp_seqs.append(&mut nested);
}
return Some(stamp_seqs);
}
if pairs.is_empty() {
if (2..=6).contains(&rest1.len()) && rest2.len() >= 8 {
stamp_seqs.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
let peel_body = rest1.len() >= 2 && {
let sub_toks = para_text_token_list(dom, &rest2[1]);
let last = last_significant_token(&sub_toks);
let body = para_text_tokens_joined(dom, &rest1[1]);
let title = para_text_tokens_joined(dom, &rest1[0]);
last.is_some_and(|tok| {
let key = tok.to_ascii_lowercase();
body.iter().any(|t| t.eq_ignore_ascii_case(&key))
&& !title.iter().any(|t| t.eq_ignore_ascii_case(&key))
})
};
if peel_body {
if residual_sets_share_content_sig(dom, &rest1, &rest2) {
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2[1..].iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
return Some(stamp_seqs);
}
let mut nested = lcs(
dom,
vec![rest1[0].clone(), rest1[1].clone()],
vec![rest2[1].clone()],
settings,
);
stamp_seqs.append(&mut nested);
} else {
let title_toks = para_text_tokens_joined(dom, &rest1[0]);
let sub_toks = para_text_tokens_joined(dom, &rest2[1]);
let nest_j = token_jaccard(&title_toks, &sub_toks);
let nest_shared = significant_tokens(&title_toks)
.intersection(&significant_tokens(&sub_toks))
.count();
if nest_j + 1e-12 >= 0.08 || nest_shared >= 1 {
let mut nested = lcs(
dom,
vec![rest1[0].clone()],
vec![rest2[1].clone()],
settings,
);
stamp_seqs.append(&mut nested);
if rest1.len() >= 2 {
stamp_seqs.push(CorrelatedSequence::deleted(vec![rest1[1].clone()]));
}
} else {
stamp_seqs.push(CorrelatedSequence::inserted(rest2[1..].to_vec()));
stamp_seqs.push(CorrelatedSequence::deleted(rest1.clone()));
return Some(stamp_seqs);
}
}
if rest2.len() > 2 {
stamp_seqs.push(CorrelatedSequence::inserted(rest2[2..].to_vec()));
}
if rest1.len() > 2 {
stamp_seqs.push(CorrelatedSequence::deleted(rest1[2..].to_vec()));
}
return Some(stamp_seqs);
}
if (2..=6).contains(&rest2.len()) && rest1.len() >= 8 {
const PEEL_BODY_SECTION_LABELS: &[&str] =
&["formatting", "format", "style", "styles", "options"];
let peel_body = rest2.len() >= 2 && rest1.len() >= 2 && {
let sub_toks = para_text_token_list(dom, &rest1[1]);
let last = last_significant_token(&sub_toks);
let body = para_text_tokens_joined(dom, &rest2[1]);
let title = para_text_tokens_joined(dom, &rest1[0]);
last.is_some_and(|tok| {
let key = tok.to_ascii_lowercase();
if PEEL_BODY_SECTION_LABELS
.iter()
.any(|b| key.eq_ignore_ascii_case(b))
{
return false;
}
body.iter().any(|t| t.eq_ignore_ascii_case(&key))
&& !title.iter().any(|t| t.eq_ignore_ascii_case(&key))
})
};
if peel_body {
stamp_seqs.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
let mut nested = lcs(
dom,
vec![rest1[0].clone(), rest1[1].clone()],
vec![rest2[1].clone()],
settings,
);
stamp_seqs.append(&mut nested);
if rest2.len() > 2 {
stamp_seqs.push(CorrelatedSequence::inserted(rest2[2..].to_vec()));
}
if rest1.len() > 2 {
stamp_seqs.push(CorrelatedSequence::deleted(rest1[2..].to_vec()));
}
return Some(stamp_seqs);
}
let k = (rest2.len() + 1).min(rest1.len());
let head1 = rest1[..k].to_vec();
let share = residual_shared_sig_count(dom, &rest1, &rest2);
let short_demo_title = rest2
.first()
.is_some_and(|u| residual_title_ends_demo(dom, u));
let m131_ok = if rest1.len() <= 40 {
share >= 1
} else if rest1.len() <= 80 && short_demo_title && share >= 1 {
true
} else {
share >= 5 && {
let t1 = para_text_tokens_from_units(dom, rest1.as_slice());
let t2 = para_text_tokens_from_units(dom, rest2.as_slice());
token_jaccard(&t1, &t2) + 1e-12 >= 0.12
}
};
if m131_ok {
let mut left: Vec<ComparisonUnit> = head1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
if rest1.len() > k {
stamp_seqs.push(CorrelatedSequence::deleted(rest1[k..].to_vec()));
}
return Some(stamp_seqs);
}
}
if (3..=6).contains(&rest1.len())
&& (3..=6).contains(&rest2.len())
&& residual_title_ends_demo(dom, &rest2[0])
&& residual_has_this_body_after_non_this(dom, &rest2)
&& residual_first_body_starts_this(dom, &rest1)
{
let this_idx = residual_first_this_body_index(dom, &rest2).unwrap_or(1);
stamp_seqs.push(CorrelatedSequence::inserted(rest2[..this_idx].to_vec()));
stamp_seqs.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
let bodies1 = rest1[1..].to_vec();
let bodies2 = rest2[this_idx..].to_vec();
let mut left: Vec<ComparisonUnit> = bodies1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = bodies2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
return Some(stamp_seqs);
}
if (2..=6).contains(&rest1.len())
&& (2..=6).contains(&rest2.len())
&& residual_sets_weakly_related(dom, &rest1, &rest2)
{
let mut left: Vec<ComparisonUnit> = rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
return Some(stamp_seqs);
}
if (2..=6).contains(&rest1.len())
&& (2..=6).contains(&rest2.len())
&& rest1.len() >= 2
&& rest2.len() >= 2
&& residual_title_ends_demo(dom, &rest2[0])
&& residual_bodies_this_cousins(dom, &rest1, &rest2)
{
stamp_seqs.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
stamp_seqs.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
let bodies1 = rest1[1..].to_vec();
let bodies2 = rest2[1..].to_vec();
let mut left: Vec<ComparisonUnit> = bodies1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = bodies2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
stamp_seqs.append(&mut nested);
return Some(stamp_seqs);
}
if !rest2.is_empty() {
stamp_seqs.push(CorrelatedSequence::inserted(rest2));
}
if !rest1.is_empty() {
stamp_seqs.push(CorrelatedSequence::deleted(rest1));
}
return Some(stamp_seqs);
}
const STAMP_ENDZIP_MAX_TOKENS: usize = 4;
let mut pairs = pairs;
{
let used_i: std::collections::HashSet<usize> = pairs.iter().map(|&(i, _)| i).collect();
let used_j: std::collections::HashSet<usize> = pairs.iter().map(|&(_, j)| j).collect();
let unpaired_i: Vec<usize> = (0..rest1.len()).filter(|i| !used_i.contains(i)).collect();
let unpaired_j: Vec<usize> = (0..rest2.len()).filter(|j| !used_j.contains(j)).collect();
if let (Some(&i), Some(&j)) = (unpaired_i.last(), unpaired_j.last()) {
let li = para_text_tokens_joined(dom, &rest1[i]);
let rj = para_text_tokens_joined(dom, &rest2[j]);
let shared_sig = significant_tokens(&li)
.intersection(&significant_tokens(&rj))
.count();
let short_titles =
li.len() <= STAMP_ENDZIP_MAX_TOKENS && rj.len() <= STAMP_ENDZIP_MAX_TOKENS;
if shared_sig == 0 && short_titles {
pairs.push((i, j));
pairs.sort_by_key(|&(_, j)| j);
}
}
}
let pair_by_j: std::collections::HashMap<usize, usize> =
pairs.iter().map(|&(i, j)| (j, i)).collect();
let paired_i: std::collections::HashSet<usize> = pairs.iter().map(|&(i, _)| i).collect();
let mut emitted_i: std::collections::HashSet<usize> = std::collections::HashSet::new();
let mut insert_buf: Vec<ComparisonUnit> = Vec::new();
let flush_inserts = |buf: &mut Vec<ComparisonUnit>, out: &mut Vec<CorrelatedSequence>| {
if !buf.is_empty() {
out.push(CorrelatedSequence::inserted(std::mem::take(buf)));
}
};
for (j, b) in rest2.iter().enumerate() {
if let Some(&i) = pair_by_j.get(&j) {
flush_inserts(&mut insert_buf, &mut stamp_seqs);
let mut early_del = Vec::new();
for (k, r1) in rest1.iter().enumerate().take(i) {
if emitted_i.contains(&k) || paired_i.contains(&k) {
continue;
}
early_del.push(r1.clone());
emitted_i.insert(k);
}
if !early_del.is_empty() {
stamp_seqs.push(CorrelatedSequence::deleted(early_del));
}
emitted_i.insert(i);
let mut nested = lcs(dom, vec![rest1[i].clone()], vec![b.clone()], settings);
stamp_seqs.append(&mut nested);
} else {
insert_buf.push(b.clone());
}
}
flush_inserts(&mut insert_buf, &mut stamp_seqs);
let unpaired: Vec<ComparisonUnit> = rest1
.into_iter()
.enumerate()
.filter(|(i, _)| !emitted_i.contains(i))
.map(|(_, u)| u)
.collect();
if !unpaired.is_empty() {
stamp_seqs.push(CorrelatedSequence::deleted(unpaired));
}
Some(stamp_seqs)
}
fn windows_related(cul1: &[ComparisonUnit], cul2: &[ComparisonUnit]) -> bool {
let (small, large) = if cul1.len() <= cul2.len() {
(cul1, cul2)
} else {
(cul2, cul1)
};
let large_hashes: std::collections::HashSet<&str> = large.iter().map(|u| u.sha1()).collect();
let hits = small
.iter()
.filter(|u| large_hashes.contains(u.sha1()))
.count();
hits * 5 >= small.len()
}
fn para_text_tokens(dom: &Dom, u: &ComparisonUnit) -> std::collections::HashSet<String> {
para_text_tokens_from_units(dom, std::slice::from_ref(u))
}
fn para_text_tokens_from_units(
dom: &Dom,
units: &[ComparisonUnit],
) -> std::collections::HashSet<String> {
let mut text = String::new();
for u in units {
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
text.push(' ');
}
text.split(|c: char| !c.is_alphanumeric())
.filter(|t| !t.is_empty())
.map(|t| t.to_ascii_lowercase())
.collect()
}
fn token_jaccard(
a: &std::collections::HashSet<String>,
b: &std::collections::HashSet<String>,
) -> f64 {
if a.is_empty() && b.is_empty() {
return 1.0;
}
let inter = a.intersection(b).count() as f64;
let uni = a.union(b).count() as f64;
if uni == 0.0 { 0.0 } else { inter / uni }
}
fn rehash_words_by_text_content(dom: &Dom, units: &mut [ComparisonUnit]) {
use crate::util::sha1::{sha1_fingerprint, sha1_hex};
for u in units.iter_mut() {
if let ComparisonUnit::Word(w) = u {
let mut text = String::new();
for a in &w.contents {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
if !text.is_empty() {
w.sha1_hash = sha1_hex(&text);
w.sha1_key = sha1_fingerprint(&w.sha1_hash);
w.sha1_key128 = crate::util::sha1::sha1_fingerprint128(&w.sha1_hash);
}
}
}
}
const M128_BOILERPLATE_SIG: &[&str] = &[
"this",
"that",
"with",
"from",
"have",
"been",
"will",
"used",
"text",
"both",
"document",
"documents",
"demonstrates",
"demonstrate",
"showing",
"shows",
"style",
"styles",
"formatting",
"format",
"demo",
"demos",
"bold",
"italic",
"underline",
"color",
"font",
"size",
"line",
"spacing",
];
const M135_OFF_DIAG_BOILER: &[&str] = &[
"this",
"that",
"with",
"from",
"have",
"been",
"will",
"used",
"both",
"document",
"documents",
"demonstrates",
"demonstrate",
"showing",
"shows",
"style",
"styles",
"formatting",
"format",
"demo",
"demos",
];
fn residual_title_ends_demo(dom: &Dom, title: &ComparisonUnit) -> bool {
let toks = para_text_token_list(dom, title);
last_significant_token(&toks).is_some_and(|t| t.eq_ignore_ascii_case("demo"))
}
fn residual_para_starts_this(dom: &Dom, u: &ComparisonUnit) -> bool {
para_text_token_list(dom, u)
.first()
.is_some_and(|t| t.eq_ignore_ascii_case("this"))
}
fn residual_first_body_starts_this(dom: &Dom, rest: &[ComparisonUnit]) -> bool {
rest.len() >= 2 && residual_para_starts_this(dom, &rest[1])
}
fn residual_first_this_body_index(dom: &Dom, rest: &[ComparisonUnit]) -> Option<usize> {
rest.iter()
.enumerate()
.skip(1)
.find(|(_, u)| residual_para_starts_this(dom, u))
.map(|(i, _)| i)
}
fn residual_has_this_body_after_non_this(dom: &Dom, rest: &[ComparisonUnit]) -> bool {
let Some(this_i) = residual_first_this_body_index(dom, rest) else {
return false;
};
this_i >= 2 && !residual_para_starts_this(dom, &rest[1])
}
fn residual_bodies_this_cousins(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> bool {
if rest1.len() < 2 || rest2.len() < 2 {
return false;
}
let mut left = std::collections::HashSet::new();
let mut right = std::collections::HashSet::new();
let mut left_ord: Vec<String> = Vec::new();
let mut right_ord: Vec<String> = Vec::new();
for u in &rest1[1..] {
let toks = para_text_token_list(dom, u);
if left_ord.is_empty() {
left_ord = toks.clone();
}
left.extend(toks);
}
for u in &rest2[1..] {
let toks = para_text_token_list(dom, u);
if right_ord.is_empty() {
right_ord = toks.clone();
}
right.extend(toks);
}
if left.is_empty() || right.is_empty() {
return false;
}
let both_this = left_ord
.first()
.is_some_and(|t| t.eq_ignore_ascii_case("this"))
&& right_ord
.first()
.is_some_and(|t| t.eq_ignore_ascii_case("this"));
if both_this {
return true;
}
let j = token_jaccard(&left, &right);
let shared_sig = significant_tokens(&left)
.intersection(&significant_tokens(&right))
.count();
j + 1e-12 >= 0.05 && shared_sig >= 1
}
fn residual_sets_share_content_sig(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> bool {
residual_shared_sig_count(dom, rest1, rest2) >= 1
}
fn residual_shared_sig_count(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> usize {
let mut left = std::collections::HashSet::new();
let mut right = std::collections::HashSet::new();
for u in rest1 {
left.extend(para_text_token_list(dom, u));
}
for u in rest2 {
right.extend(para_text_token_list(dom, u));
}
significant_tokens(&left)
.intersection(&significant_tokens(&right))
.filter(|t| {
!M128_BOILERPLATE_SIG
.iter()
.any(|b| t.eq_ignore_ascii_case(b))
})
.count()
}
fn residual_looks_like_colon_list(dom: &Dom, rest: &[ComparisonUnit]) -> bool {
if rest.is_empty() {
return false;
}
let with_colon = rest
.iter()
.filter(|u| {
let mut text = String::new();
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
text.contains(':')
})
.count();
with_colon * 2 >= rest.len()
}
fn residual_sets_weakly_related(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> bool {
let mut left = std::collections::HashSet::new();
let mut right = std::collections::HashSet::new();
for u in rest1 {
left.extend(para_text_token_list(dom, u));
}
for u in rest2 {
right.extend(para_text_token_list(dom, u));
}
if left.is_empty() || right.is_empty() {
return false;
}
let j = token_jaccard(&left, &right);
let shared_sig: std::collections::HashSet<String> = significant_tokens(&left)
.intersection(&significant_tokens(&right))
.cloned()
.collect();
if j + 1e-12 < 0.04 || shared_sig.is_empty() {
return false;
}
shared_sig.iter().any(|t| {
!M128_BOILERPLATE_SIG
.iter()
.any(|b| t.eq_ignore_ascii_case(b))
})
}
fn m123_diagonal_stats(
dom: &Dom,
rest1: &[ComparisonUnit],
rest2: &[ComparisonUnit],
) -> (f64, f64, f64) {
if rest1.is_empty() || rest1.len() != rest2.len() {
return (0.0, 0.0, 0.0);
}
let n = rest1.len();
let mut min_d = f64::INFINITY;
let mut sum = 0.0_f64;
let mut max_body = 0.0_f64;
for i in 0..n {
let j = token_jaccard(
¶_text_tokens(dom, &rest1[i]),
¶_text_tokens(dom, &rest2[i]),
);
sum += j;
if j < min_d {
min_d = j;
}
if i >= 1 && j > max_body {
max_body = j;
}
}
if !min_d.is_finite() {
min_d = 0.0;
}
(min_d, sum / n as f64, max_body)
}
fn para_zip_diagonal_dominant(dom: &Dom, cul1: &[ComparisonUnit], cul2: &[ComparisonUnit]) -> bool {
let n = cul1.len();
if n == 0 || n != cul2.len() {
return false;
}
let left: Vec<_> = cul1.iter().map(|u| para_text_tokens(dom, u)).collect();
let right: Vec<_> = cul2.iter().map(|u| para_text_tokens(dom, u)).collect();
let mut diagonal_wins = 0usize;
let mut diag_sum = 0.0_f64;
for i in 0..n {
let diag = token_jaccard(&left[i], &right[i]);
diag_sum += diag;
let mut best_off = 0.0_f64;
for (j, rj) in right.iter().enumerate() {
if j == i {
continue;
}
best_off = best_off.max(token_jaccard(&left[i], rj));
}
if diag > 0.0 && diag + 1e-9 >= best_off {
diagonal_wins += 1;
}
}
let avg = diag_sum / (n as f64);
let avg_ok = avg >= 0.08 || (n <= 4 && diagonal_wins * 2 >= n && avg >= 0.04);
diagonal_wins * 2 >= n && avg_ok
}
fn first_paras_share_last_sig(dom: &Dom, cul1: &[ComparisonUnit], cul2: &[ComparisonUnit]) -> bool {
let (Some(a), Some(b)) = (cul1.first(), cul2.first()) else {
return false;
};
let la = para_text_token_list(dom, a);
let lb = para_text_token_list(dom, b);
match (last_significant_token(&la), last_significant_token(&lb)) {
(Some(x), Some(y)) => x.eq_ignore_ascii_case(y),
_ => false,
}
}
fn body_residual_unrelated(dom: &Dom, cul1: &[ComparisonUnit], cul2: &[ComparisonUnit]) -> bool {
if cul1.len() < 2 || cul2.len() < 2 {
return false;
}
let left = para_text_tokens_from_units(dom, &cul1[1..]);
let right = para_text_tokens_from_units(dom, &cul2[1..]);
let left_sig = significant_tokens(&left);
let right_sig = significant_tokens(&right);
!left_sig.intersection(&right_sig).any(|t| {
!M128_BOILERPLATE_SIG
.iter()
.any(|b| t.eq_ignore_ascii_case(b))
})
}
fn cascade(
left: Vec<ComparisonUnit>,
right: Vec<ComparisonUnit>,
out: &mut Vec<CorrelatedSequence>,
) {
match (left.is_empty(), right.is_empty()) {
(false, true) => out.push(CorrelatedSequence::deleted(left)),
(true, false) => out.push(CorrelatedSequence::inserted(right)),
(false, false) => out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
)),
(true, true) => {}
}
}
pub fn do_lcs_algorithm(
dom: &mut Dom,
unknown: CorrelatedSequence,
settings: &WmlComparerSettings,
) -> Vec<CorrelatedSequence> {
let cul1 = unknown.com_units_1.unwrap_or_default();
let cul2 = unknown.com_units_2.unwrap_or_default();
let mut out = Vec::new();
if !cul1.is_empty() && cul2.is_empty() {
out.push(CorrelatedSequence::deleted(cul1));
return out;
}
if cul1.is_empty() && !cul2.is_empty() {
out.push(CorrelatedSequence::inserted(cul2));
return out;
}
if cul1.is_empty() && cul2.is_empty() {
return out;
}
if settings.merge_replaced_paragraphs {
let all_words1 = cul1.iter().all(|c| matches!(c, ComparisonUnit::Word(_)));
let all_words2 = cul2.iter().all(|c| matches!(c, ComparisonUnit::Word(_)));
if all_words1 && all_words2 {
let pil1: Vec<usize> = cul1
.iter()
.enumerate()
.filter(|(_, cu)| unit_is_single_atom_ppr(dom, cu))
.map(|(i, _)| i)
.collect();
let pil2: Vec<usize> = cul2
.iter()
.enumerate()
.filter(|(_, cu)| unit_is_single_atom_ppr(dom, cu))
.map(|(i, _)| i)
.collect();
let ends_at_pil = |cul: &[ComparisonUnit]| {
cul.last()
.is_some_and(|cu| unit_is_single_atom_ppr(dom, cu))
};
let xor_single = (pil1.len() == 1) != (pil2.len() == 1);
let both_multi = pil1.len() > 1 && pil2.len() > 1 && pil1.len() != pil2.len();
if std::env::var("JUB_TRACE").is_ok() {
eprintln!(
"[gate2] n1={} n2={} pil1={} pil2={} xor={} multi={} end1={} end2={}",
cul1.len(),
cul2.len(),
pil1.len(),
pil2.len(),
xor_single,
both_multi,
ends_at_pil(&cul1),
ends_at_pil(&cul2)
);
}
if !pil1.is_empty()
&& !pil2.is_empty()
&& (xor_single || both_multi)
&& ends_at_pil(&cul1)
&& ends_at_pil(&cul2)
{
let entries = |cul: &[ComparisonUnit]| -> Vec<(String, usize)> {
cul.iter()
.filter(|cu| !unit_is_single_atom_ppr(dom, cu))
.filter_map(|cu| {
let text: String = cu
.descendant_atoms()
.iter()
.filter(|dca| dom.name_is(dca.content_element, &W::t()))
.map(|dca| dom.value_str(dca.content_element))
.collect();
let letters = text.chars().filter(|c| c.is_alphanumeric()).count();
if letters > 0 {
Some((cu.sha1().to_string(), letters))
} else {
None
}
})
.collect()
};
let e1 = entries(&cul1);
let e2 = entries(&cul2);
let h2: std::collections::HashSet<&str> =
e2.iter().map(|(h, _)| h.as_str()).collect();
let shared: Vec<&(String, usize)> =
e1.iter().filter(|(h, _)| h2.contains(h.as_str())).collect();
let union = e1.len() + e2.len() - shared.len();
let jaccard = if union > 0 {
shared.len() as f64 / union as f64
} else {
0.0
};
let has_strong_share = shared.iter().any(|(_, lc)| *lc >= 5);
let both_compact = e1.len() <= 16 && e2.len() <= 16;
let text_tokens = |cul: &[ComparisonUnit]| -> std::collections::HashSet<String> {
cul.iter()
.filter(|cu| !unit_is_single_atom_ppr(dom, cu))
.filter_map(|cu| {
let text: String = cu
.descendant_atoms()
.iter()
.filter(|dca| dom.name_is(dca.content_element, &W::t()))
.map(|dca| dom.value_str(dca.content_element))
.collect();
let t = text.trim().to_lowercase();
if t.chars().any(|c| c.is_alphanumeric()) {
Some(t)
} else {
None
}
})
.collect()
};
let text_ok = if both_multi {
let t1 = text_tokens(&cul1);
let t2 = text_tokens(&cul2);
let shared_t = t1.intersection(&t2).count();
let union_t = t1.len() + t2.len() - shared_t;
let tj = if union_t > 0 {
shared_t as f64 / union_t as f64
} else {
0.0
};
tj < 0.2
} else {
true
};
let starts_at_body_head = |cul: &[ComparisonUnit]| -> bool {
let body_name = W::name("body");
let p_name = W::name("p");
let tbl_name = W::tbl();
let Some(first_cu) = cul.first() else {
return false;
};
let atoms = first_cu.descendant_atoms();
let Some(first_atom) = atoms.first() else {
return false;
};
let mut body_para = None;
for &ae in first_atom.ancestor_elements.iter() {
if dom.name_is(ae, &p_name.clone())
&& let Some(par) = dom.parent(ae)
&& dom.name_is(par, &body_name.clone())
{
body_para = Some((ae, par));
break;
}
}
let Some((para, body)) = body_para else {
return false;
};
for child in dom.elements(body, None) {
let nm = dom.name(child);
if nm == Some(p_name.clone()) || nm == Some(tbl_name.clone()) {
return child == para;
}
}
false
};
let ends_at_body_tail = |cul: &[ComparisonUnit]| -> bool {
let body_name = W::name("body");
let p_name = W::name("p");
let t_name = W::t();
let Some(last_cu) = cul.last() else {
return false;
};
let atoms = last_cu.descendant_atoms();
let Some(last_atom) = atoms.last() else {
return false;
};
let mut body_block = None;
for &ae in last_atom.ancestor_elements.iter() {
if let Some(par) = dom.parent(ae)
&& dom.name_is(par, &body_name.clone())
{
body_block = Some((ae, par));
break;
}
}
let Some((block, body)) = body_block else {
return false;
};
let mut seen = false;
for child in dom.elements(body, None) {
if child == block {
seen = true;
continue;
}
if !seen {
continue;
}
let nm = dom.name(child);
if nm != Some(p_name.clone()) {
if nm == Some(W::sect_pr()) {
continue;
}
return false;
}
let mut has_text = false;
dom.for_each_descendant_element(child, Some(&t_name), |el| {
if !dom.value_str(el).trim().is_empty() {
has_text = true;
}
});
if has_text {
return false;
}
}
true
};
let wholesale = starts_at_body_head(&cul1)
&& starts_at_body_head(&cul2)
&& ends_at_body_tail(&cul1)
&& ends_at_body_tail(&cul2);
if jaccard < 0.2 && !(has_strong_share && both_compact) && wholesale && text_ok {
let split_paras = |cul: &[ComparisonUnit]| -> Vec<Vec<ComparisonUnit>> {
let mut paras = Vec::new();
let mut cur = Vec::new();
for cu in cul {
cur.push(cu.clone());
if unit_is_single_atom_ppr(dom, cu) {
paras.push(std::mem::take(&mut cur));
}
}
if !cur.is_empty() {
paras.push(cur);
}
paras
};
let paras_a = split_paras(&cul1);
let paras_b = split_paras(&cul2);
if shared.is_empty()
&& both_multi
&& mostly_list_paras(dom, ¶s_a)
&& mostly_list_paras(dom, ¶s_b)
&& short_item_list_paras(dom, ¶s_a)
&& short_item_list_paras(dom, ¶s_b)
{
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
return out;
}
let lead_b: Vec<ComparisonUnit> = paras_b[..paras_b.len() - 1]
.iter()
.flat_map(|p| p.iter().cloned())
.collect();
if !lead_b.is_empty() {
out.push(CorrelatedSequence::inserted(lead_b));
}
let carrier_b = paras_b.last().unwrap();
let carrier_a = ¶s_a[0];
let b_words: Vec<ComparisonUnit> = carrier_b[..carrier_b.len() - 1].to_vec();
if !b_words.is_empty() {
out.push(CorrelatedSequence::inserted(b_words));
}
let a_words: Vec<ComparisonUnit> = carrier_a[..carrier_a.len() - 1].to_vec();
if !a_words.is_empty() {
out.push(CorrelatedSequence::deleted(a_words));
}
if paras_a.len() > 1 {
out.push(CorrelatedSequence::deleted(vec![
carrier_a.last().unwrap().clone(),
]));
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Equal,
vec![carrier_a.last().unwrap().clone()],
vec![carrier_b.last().unwrap().clone()],
));
}
let tail_a: Vec<ComparisonUnit> = paras_a[1..]
.iter()
.flat_map(|p| p.iter().cloned())
.collect();
if !tail_a.is_empty() {
out.push(CorrelatedSequence::deleted(tail_a));
}
return out;
}
}
}
}
let (mut i1, mut i2, mut len) = if settings.merge_replaced_paragraphs {
longest_common_run_with_dom(Some(dom), &cul1, &cul2, Some(settings))
} else {
longest_common_run(&cul1, &cul2)
};
while len > 1 {
if !unit_is_single_atom_ppr(dom, &cul1[i1]) {
break;
}
len -= 1;
if len == 0 {
break;
}
i1 += 1;
i2 += 1;
}
let is_only_paragraph_mark = len == 1 && unit_is_single_atom_ppr(dom, &cul1[i1]);
if len > 0 && len <= 3 {
let common = &cul1[i1..i1 + len];
let all_words = common.iter().all(|c| matches!(c, ComparisonUnit::Word(_)));
if all_words {
let content_other_than_word_split = common.iter().any(|cs| {
let atoms = cs.descendant_atoms();
let other_than_text = atoms
.iter()
.any(|dca| !dom.name_is(dca.content_element, &W::t()));
if other_than_text {
return true;
}
atoms.iter().any(|dca| {
let v = dom.value_str(dca.content_element);
let ch = v.chars().next().unwrap_or('\0');
let is_word_split = ('\u{4e00}'..='\u{9fff}').contains(&ch)
|| settings.word_separators.contains(&ch);
!is_word_split
})
});
if !content_other_than_word_split {
len = 0;
}
}
}
if !is_only_paragraph_mark && len > 0 {
let common_all_words = cul1[i1..i1 + len]
.iter()
.all(|c| matches!(c, ComparisonUnit::Word(_)));
if common_all_words {
let max_len = cul1.len().max(cul2.len());
let ratio_len = if settings.merge_replaced_paragraphs {
cul1[i1..i1 + len]
.iter()
.filter(|cs| {
!cs.descendant_atoms().iter().all(|dca| {
if !dom.name_is(dca.content_element, &W::t()) {
return false;
}
let v = dom.value_str(dca.content_element);
!v.is_empty()
&& v.chars().all(|ch| settings.word_separators.contains(&ch))
})
})
.count()
} else {
len
};
if max_len > 0 && (ratio_len as f64) / (max_len as f64) < settings.detail_threshold {
len = 0;
}
}
}
let sides_pure_words = cul1.iter().all(|c| matches!(c, ComparisonUnit::Word(_)))
&& cul2.iter().all(|c| matches!(c, ComparisonUnit::Word(_)));
let sides_words_or_rows = cul1.iter().all(|c| match c {
ComparisonUnit::Word(_) => true,
ComparisonUnit::Group(g) => g.group_type == ComparisonUnitGroupType::Row,
}) && cul2.iter().all(|c| match c {
ComparisonUnit::Word(_) => true,
ComparisonUnit::Group(g) => g.group_type == ComparisonUnitGroupType::Row,
});
if settings.merge_replaced_paragraphs
&& len > 0
&& len <= 3
&& !is_only_paragraph_mark
&& sides_words_or_rows
&& cul1[i1..i1 + len]
.iter()
.all(|c| matches!(c, ComparisonUnit::Word(_)))
{
let pmarks1 = cul1
.iter()
.filter(|u| unit_last_atom_is_ppr(dom, u))
.count();
let pmarks2 = cul2
.iter()
.filter(|u| unit_last_atom_is_ppr(dom, u))
.count();
let multi_para_unrelated = !settings.in_stamp_residual && (pmarks1 > 1 || pmarks2 > 1) && {
let raw1 = para_text_tokens_from_units(dom, &cul1);
let raw2 = para_text_tokens_from_units(dom, &cul2);
let stamped = false;
let t1 = significant_tokens(&raw1);
let t2 = significant_tokens(&raw2);
!stamped && !t1.is_empty() && !t2.is_empty() && {
let inter = t1.intersection(&t2).count() as f64;
inter / (t1.len().min(t2.len()) as f64) + 1e-12 < 0.08
}
};
if (sides_pure_words && pmarks1 == 1 && pmarks2 == 1) || multi_para_unrelated {
let mut alpha = String::new();
for u in &cul1[i1..i1 + len] {
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
for ch in dom.value_str(a.content_element).chars() {
if ch.is_ascii_alphabetic() {
alpha.push(ch.to_ascii_lowercase());
}
}
}
}
}
const GLUE: &[&str] = &[
"a", "an", "and", "are", "as", "at", "be", "by", "for", "from", "in", "is", "it",
"of", "on", "or", "the", "to", "with", "text",
];
if GLUE.contains(&alpha.as_str()) || (multi_para_unrelated && alpha.is_empty()) {
len = 0;
}
}
}
if len > 0
&& !is_only_paragraph_mark
&& settings.merge_replaced_paragraphs
&& cul1[i1..i1 + len]
.iter()
.all(|c| matches!(c, ComparisonUnit::Word(_)))
&& containing_paragraph_is_duplicated(dom, &cul1, i1)
{
len = 0;
}
if len > 0
&& settings.merge_replaced_paragraphs
&& (count_gt(&cul1, ComparisonUnitGroupType::Table) > 0
|| count_gt(&cul2, ComparisonUnitGroupType::Table) > 0
|| count_gt(&cul1, ComparisonUnitGroupType::Row) > 0
|| count_gt(&cul2, ComparisonUnitGroupType::Row) > 0)
&& cul1[i1..i1 + len].iter().all(|u| {
u.descendant_atoms().iter().all(|a| {
!dom.name_is(a.content_element, &W::t())
|| dom.value_str(a.content_element).trim().is_empty()
})
})
{
len = 0;
}
if len > 0
&& len <= 2
&& !is_only_paragraph_mark
&& settings.merge_replaced_paragraphs
&& cul1.len().min(cul2.len()) > 32
&& run_real_text_len(dom, &cul1[i1..i1 + len]) < 15
&& !windows_related(&cul1, &cul2)
{
len = 0;
}
if len == 0 {
return step_h(dom, &cul1, &cul2, settings);
}
let (mut rem_left, mut rem_right) = (0usize, 0usize);
{
let common_seq = &cul1[i1..i1 + len];
if matches!(common_seq[0], ComparisonUnit::Word(_))
&& common_seq.iter().any(|cu| unit_first_atom_is_ppr(dom, cu))
{
rem_left = take_while_count_rev(&cul1[..i1], |cu| word_first_not_ppr(dom, cu));
rem_right = take_while_count_rev(&cul2[..i2], |cu| word_first_not_ppr(dom, cu));
}
}
let before_left = i1 - rem_left;
let before_right = i2 - rem_right;
cascade(
cul1[..before_left].to_vec(),
cul2[..before_right].to_vec(),
&mut out,
);
cascade(
cul1[before_left..i1].to_vec(),
cul2[before_right..i2].to_vec(),
&mut out,
);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Equal,
cul1[i1..i1 + len].to_vec(),
cul2[i2..i2 + len].to_vec(),
));
let end1 = i1 + len;
let end2 = i2 + len;
let remaining1 = &cul1[end1..];
let remaining2 = &cul2[end2..];
let last_eq = &cul1[i1 + len - 1];
let last_not_ppr = matches!(last_eq, ComparisonUnit::Word(_))
&& last_eq
.descendant_atoms()
.last()
.is_some_and(|a| !atom_is_ppr(dom, a));
if last_not_ppr {
let idx1 = find_index_of_next_para_mark(dom, remaining1);
let idx2 = find_index_of_next_para_mark(dom, remaining2);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
remaining1[..idx1].to_vec(),
remaining2[..idx2].to_vec(),
));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
remaining1[idx1..].to_vec(),
remaining2[idx2..].to_vec(),
));
return out;
}
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
remaining1.to_vec(),
remaining2.to_vec(),
));
out
}
fn as_group(u: &ComparisonUnit) -> Option<&super::atoms::ComparisonUnitGroup> {
match u {
ComparisonUnit::Group(g) => Some(g),
ComparisonUnit::Word(_) => None,
}
}
fn count_gt(units: &[ComparisonUnit], gt: ComparisonUnitGroupType) -> usize {
units
.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == gt))
.count()
}
fn count_words(units: &[ComparisonUnit]) -> usize {
units
.iter()
.filter(|u| matches!(u, ComparisonUnit::Word(_)))
.count()
}
fn group_contents(u: &ComparisonUnit) -> Vec<ComparisonUnit> {
match u {
ComparisonUnit::Group(g) => g.contents.clone(),
ComparisonUnit::Word(_) => vec![],
}
}
fn last_atom_overall_is_ppr(dom: &Dom, units: &[ComparisonUnit]) -> Option<bool> {
let mut last = None;
for u in units {
if let Some(a) = u.descendant_atoms().last() {
last = Some(atom_is_ppr(dom, a));
}
}
last
}
fn containing_paragraph_is_duplicated(dom: &Dom, units: &[ComparisonUnit], pos: usize) -> bool {
let mut texts: Vec<String> = vec![String::new()];
let mut idx_of_pos = 0usize;
for (i, u) in units.iter().enumerate() {
if i == pos {
idx_of_pos = texts.len() - 1;
}
let atoms = u.descendant_atoms();
let is_pmark = !atoms.is_empty()
&& atoms
.iter()
.all(|a| dom.name_is(a.content_element, &W::p_pr()));
if is_pmark {
texts.push(String::new());
continue;
}
let is_group_para = matches!(u, ComparisonUnit::Group(_))
&& atoms
.iter()
.any(|a| dom.name_is(a.content_element, &W::p_pr()));
if is_group_para {
let text: String = atoms
.iter()
.filter(|a| dom.name_is(a.content_element, &W::t()))
.map(|a| dom.value_str(a.content_element))
.collect();
texts.push(text);
texts.push(String::new());
if i == pos {
idx_of_pos = texts.len() - 2;
}
continue;
}
let last = texts.last_mut().expect("non-empty");
for a in atoms {
if dom.name_is(a.content_element, &W::t()) {
last.push_str(&dom.value_str(a.content_element));
}
}
}
let target = &texts[idx_of_pos];
if target.trim().is_empty() {
return false;
}
texts
.iter()
.enumerate()
.any(|(i, t)| i != idx_of_pos && t == target)
}
fn step_h(
dom: &mut Dom,
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
settings: &WmlComparerSettings,
) -> Vec<CorrelatedSequence> {
use ComparisonUnitGroupType::*;
let mut out = Vec::new();
let left_len = cul1.len();
let left_tables = count_gt(cul1, Table);
let left_rows = count_gt(cul1, Row);
let left_paras = count_gt(cul1, Paragraph);
let left_textboxes = count_gt(cul1, Textbox);
let left_words = count_words(cul1);
let right_len = cul2.len();
let right_tables = count_gt(cul2, Table);
let right_rows = count_gt(cul2, Row);
let right_paras = count_gt(cul2, Paragraph);
let right_textboxes = count_gt(cul2, Textbox);
let right_words = count_words(cul2);
let left_only_wrt = left_len == left_words + left_rows + left_textboxes;
let right_only_wrt = right_len == right_words + right_rows + right_textboxes;
if (left_words > 0 || right_words > 0)
&& (left_rows > 0 || right_rows > 0 || left_textboxes > 0 || right_textboxes > 0)
&& left_only_wrt
&& right_only_wrt
{
let key = |u: &ComparisonUnit| -> &'static str {
match u {
ComparisonUnit::Word(_) => "Word",
ComparisonUnit::Group(g) => match g.group_type {
Row => "Row",
Textbox => "Textbox",
_ => "Row", },
}
};
let lg = crate::util::group_adjacent(cul1.iter().cloned(), |u| key(u));
let rg = crate::util::group_adjacent(cul2.iter().cloned(), |u| key(u));
if std::env::var("JUBARTE_TRACE").is_ok() {
let toks = |units: &[ComparisonUnit]| -> Vec<String> {
let raw = para_text_tokens_from_units(dom, units);
significant_tokens(&raw).into_iter().take(8).collect()
};
let lgs: Vec<String> = lg
.iter()
.map(|g| format!("{}:{}", g.0, g.1.len()))
.collect();
let rgs: Vec<String> = rg
.iter()
.map(|g| format!("{}:{}", g.0, g.1.len()))
.collect();
eprintln!("H1seam lg=[{}] rg=[{}]", lgs.join(","), rgs.join(","));
if lg.len() == 1 {
let all: Vec<ComparisonUnit> =
rg.iter().flat_map(|g| g.1.iter().cloned()).collect();
eprintln!("H1seam t1={:?} t2={:?}", toks(&lg[0].1), toks(&all));
}
}
let group_textless = |dom: &Dom, units: &[ComparisonUnit]| -> bool {
units.iter().all(|u| {
u.descendant_atoms().iter().all(|a| {
!dom.name_is(a.content_element, &W::t())
|| dom.value_str(a.content_element).trim().is_empty()
})
})
};
let (mut il, mut ir) = (0usize, 0usize);
loop {
let (before_l, before_r) = (il, ir);
let bare_pmarks = |units: &[ComparisonUnit]| -> bool {
units.len() <= 3 && units.iter().all(|u| unit_is_single_atom_ppr(dom, u))
};
if lg[il].0 == "Word"
&& rg[ir].0 == "Word"
&& ir == 0
&& bare_pmarks(&rg[ir].1)
&& !group_textless(dom, &lg[il].1)
{
out.push(CorrelatedSequence::inserted(rg[ir].1.clone()));
ir += 1;
} else if lg[il].0 == rg[ir].0 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
lg[il].1.clone(),
rg[ir].1.clone(),
));
il += 1;
ir += 1;
} else if lg[il].0 == "Word"
&& lg[il]
.1
.last()
.is_some_and(|u| !unit_last_atom_is_ppr(dom, u))
&& rg[ir].0 == "Row"
{
out.push(CorrelatedSequence::inserted(rg[ir].1.clone()));
ir += 1;
} else if rg[ir].0 == "Word"
&& rg[ir]
.1
.last()
.is_some_and(|u| !unit_last_atom_is_ppr(dom, u))
&& lg[il].0 == "Row"
{
out.push(CorrelatedSequence::deleted(lg[il].1.clone()));
il += 1;
} else if lg[il].0 == "Word" && rg[ir].0 != "Word" {
out.push(CorrelatedSequence::deleted(lg[il].1.clone()));
il += 1;
} else if lg[il].0 != "Word" && rg[ir].0 == "Word" {
out.push(CorrelatedSequence::inserted(rg[ir].1.clone()));
ir += 1;
}
if il == lg.len() && ir == rg.len() {
return out;
}
if ir == rg.len() {
for g in &lg[il..] {
out.push(CorrelatedSequence::deleted(g.1.clone()));
}
return out;
}
if il == lg.len() {
for g in &rg[ir..] {
out.push(CorrelatedSequence::inserted(g.1.clone()));
}
return out;
}
if il == before_l && ir == before_r {
out.push(CorrelatedSequence::deleted(
lg[il..].iter().flat_map(|g| g.1.clone()).collect(),
));
out.push(CorrelatedSequence::inserted(
rg[ir..].iter().flat_map(|g| g.1.clone()).collect(),
));
return out;
}
}
}
if left_tables > 0
&& right_tables > 0
&& left_paras > 0
&& right_paras > 0
&& (left_len > 1 || right_len > 1)
{
let key = |u: &ComparisonUnit| -> &'static str {
if as_group(u).is_some_and(|g| g.group_type == Table) {
"Table"
} else {
"Para"
}
};
let contentful_count = |units: &[ComparisonUnit]| -> usize {
units
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == Paragraph)
&& unit_has_text_token(dom, u)
})
.count()
};
let first_contentful_tokens =
|units: &[ComparisonUnit]| -> std::collections::HashSet<String> {
units
.iter()
.find(|u| {
as_group(u).is_some_and(|g| g.group_type == Paragraph)
&& unit_has_text_token(dom, u)
})
.map(|u| para_text_tokens(dom, u))
.unwrap_or_default()
};
let lg = crate::util::group_adjacent(cul1.iter().cloned(), |u| key(u));
let rg = crate::util::group_adjacent(cul2.iter().cloned(), |u| key(u));
let (mut il, mut ir) = (0usize, 0usize);
loop {
if lg[il].0 == rg[ir].0 {
let one_title_each = settings.merge_replaced_paragraphs
&& lg[il].0 == "Para"
&& contentful_count(&lg[il].1) == 1
&& contentful_count(&rg[ir].1) == 1
&& {
let j = token_jaccard(
&first_contentful_tokens(&lg[il].1),
&first_contentful_tokens(&rg[ir].1),
);
j + 1e-12 < 0.12
};
if one_title_each {
let (lt, le): (Vec<_>, Vec<_>) = lg[il]
.1
.iter()
.cloned()
.partition(|u| unit_has_text_token(dom, u));
let (rt, re): (Vec<_>, Vec<_>) = rg[ir]
.1
.iter()
.cloned()
.partition(|u| unit_has_text_token(dom, u));
if lg[il].1.len() == rg[ir].1.len() {
if !rt.is_empty() {
out.push(CorrelatedSequence::inserted(rt));
}
if !lt.is_empty() {
out.push(CorrelatedSequence::deleted(lt));
}
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
lt,
rt,
));
}
let n_eq = le.len().min(re.len());
if n_eq > 0 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
le[..n_eq].to_vec(),
re[..n_eq].to_vec(),
));
}
if le.len() > n_eq {
out.push(CorrelatedSequence::deleted(le[n_eq..].to_vec()));
}
if re.len() > n_eq {
out.push(CorrelatedSequence::inserted(re[n_eq..].to_vec()));
}
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
lg[il].1.clone(),
rg[ir].1.clone(),
));
}
il += 1;
ir += 1;
} else if lg[il].0 == "Para" && rg[ir].0 == "Table" {
out.push(CorrelatedSequence::deleted(lg[il].1.clone()));
il += 1;
} else if lg[il].0 == "Table" && rg[ir].0 == "Para" {
out.push(CorrelatedSequence::inserted(rg[ir].1.clone()));
ir += 1;
}
if il == lg.len() && ir == rg.len() {
return out;
}
if ir == rg.len() {
for g in &lg[il..] {
out.push(CorrelatedSequence::deleted(g.1.clone()));
}
return out;
}
if il == lg.len() {
for g in &rg[ir..] {
out.push(CorrelatedSequence::inserted(g.1.clone()));
}
return out;
}
}
}
let left_only_ptt_m201 = left_len == left_tables + left_paras + left_textboxes;
let right_only_ptt_m201 = right_len == right_tables + right_paras + right_textboxes;
if settings.merge_replaced_paragraphs
&& left_only_ptt_m201
&& right_only_ptt_m201
&& left_textboxes == 0
&& right_textboxes == 0
&& left_len >= 1
&& right_len >= 1
&& left_len <= 12
&& right_len <= 12
{
let contentful_paras = |units: &[ComparisonUnit]| -> usize {
units
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == Paragraph)
&& unit_has_text_token(dom, u)
})
.count()
};
let first_contentful_idx = |units: &[ComparisonUnit]| -> Option<usize> {
units.iter().position(|u| {
as_group(u).is_some_and(|g| g.group_type == Paragraph)
&& unit_has_text_token(dom, u)
})
};
let lc = contentful_paras(cul1);
let rc = contentful_paras(cul2);
let prose_vs_table = left_len <= 6
&& right_len <= 6
&& ((left_tables == 0 && lc == 1 && right_tables == 1 && rc == 0)
|| (right_tables == 0 && rc == 1 && left_tables == 1 && lc == 0));
if prose_vs_table {
for u in cul2 {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in cul1 {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return out;
}
if (left_tables == 1) ^ (right_tables == 1)
&& lc >= 1
&& rc >= 1
&& left_len <= 5
&& right_len <= 5
&& let (Some(li), Some(ri)) = (first_contentful_idx(cul1), first_contentful_idx(cul2))
{
let j_title = token_jaccard(
¶_text_tokens(dom, &cul1[li]),
¶_text_tokens(dom, &cul2[ri]),
);
if j_title + 1e-12 >= 0.9 {
let rest1: Vec<ComparisonUnit> = cul1
.iter()
.enumerate()
.filter(|(i, _)| *i != li)
.map(|(_, u)| u.clone())
.collect();
let rest2: Vec<ComparisonUnit> = cul2
.iter()
.enumerate()
.filter(|(i, _)| *i != ri)
.map(|(_, u)| u.clone())
.collect();
let rc_rest = contentful_paras(&rest1);
let rr_rest = contentful_paras(&rest2);
let rt1 = count_gt(&rest1, Table);
let rt2 = count_gt(&rest2, Table);
let residual_pvt = (rt1 == 0 && rc_rest == 1 && rt2 == 1 && rr_rest == 0)
|| (rt2 == 0 && rr_rest == 1 && rt1 == 1 && rc_rest == 0);
if residual_pvt && !rest1.is_empty() && !rest2.is_empty() {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[li].clone()],
vec![cul2[ri].clone()],
));
for u in &rest2 {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &rest1 {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return out;
}
}
}
let m208 = left_tables == 1
&& lc == 1
&& left_len <= 5
&& right_tables == 0
&& rc == right_paras
&& rc >= 4
&& right_len == right_paras;
if m208 && let Some(ti) = first_contentful_idx(cul1) {
let last_p = cul2.len() - 1;
let j_first = token_jaccard(
¶_text_tokens(dom, &cul1[ti]),
¶_text_tokens(dom, &cul2[0]),
);
let j_last = token_jaccard(
¶_text_tokens(dom, &cul2[last_p]),
¶_text_tokens(dom, &cul1[ti]),
);
if j_first + 1e-12 < 0.15 && j_last + 1e-12 < 0.15 {
for u in &cul2[..last_p] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[ti].clone()],
vec![cul2[last_p].clone()],
));
for (i, u) in cul1.iter().enumerate() {
if i == ti {
continue;
}
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return out;
}
}
}
if left_tables == 1
&& left_len == 1
&& right_tables == 1
&& right_len == 1
&& let Some(r) = super::lcs_table::do_lcs_algorithm_for_table(dom, cul1, cul2, settings)
{
return r;
}
let left_only_ptt = left_len == left_tables + left_paras + left_textboxes;
let right_only_ptt = right_len == right_tables + right_paras + right_textboxes;
if left_only_ptt && right_only_ptt {
if settings.merge_replaced_paragraphs
&& left_tables == 0
&& right_tables == 0
&& left_paras >= 4
&& right_paras >= 4
&& left_paras != right_paras
{
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cul1),
¶_text_tokens_from_units(dom, cul2),
);
let list_left: Vec<&ComparisonUnit> = cul1
.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == Paragraph))
.filter(|u| unit_has_text_token(dom, u))
.collect();
let list_right: Vec<&ComparisonUnit> = cul2
.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == Paragraph))
.filter(|u| unit_has_text_token(dom, u))
.collect();
let mostly = |xs: &[&ComparisonUnit]| {
if xs.is_empty() {
return false;
}
let n = xs.iter().filter(|u| unit_para_has_numpr(dom, u)).count();
n * 2 >= xs.len()
};
let cut = first_list_cluster_end(dom, cul1);
let has_nested = list_left
.iter()
.any(|u| unit_para_ilvl(dom, u).unwrap_or(0) >= 1);
if body_j + 1e-12 < 0.25
&& mostly(&list_left)
&& mostly(&list_right)
&& short_item_list_groups(dom, &list_left)
&& short_item_list_groups(dom, &list_right)
&& has_nested
&& cut >= 2
&& cut < cul1.len()
&& !list_right.is_empty()
{
out.push(CorrelatedSequence::inserted(vec![cul2[0].clone()]));
out.push(CorrelatedSequence::deleted(cul1[..cut].to_vec()));
if cul2.len() > 1 {
out.push(CorrelatedSequence::inserted(cul2[1..].to_vec()));
}
if cut < cul1.len() {
out.push(CorrelatedSequence::deleted(cul1[cut..].to_vec()));
}
return out;
}
}
if settings.merge_replaced_paragraphs
&& left_tables == 0
&& right_tables == 0
&& left_paras != right_paras
&& left_paras >= 2
&& right_paras >= 2
{
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cul1),
¶_text_tokens_from_units(dom, cul2),
);
let list_left = cul1
.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == Paragraph))
.filter(|u| unit_has_text_token(dom, u))
.collect::<Vec<_>>();
let list_right = cul2
.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == Paragraph))
.filter(|u| unit_has_text_token(dom, u))
.collect::<Vec<_>>();
let mostly = |xs: &[&ComparisonUnit]| {
if xs.is_empty() {
return false;
}
let n = xs.iter().filter(|u| unit_para_has_numpr(dom, u)).count();
n * 2 >= xs.len()
};
if body_j + 1e-12 < 0.12
&& mostly(&list_left)
&& mostly(&list_right)
&& short_item_list_groups(dom, &list_left)
&& short_item_list_groups(dom, &list_right)
{
for u in cul2 {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in cul1 {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return out;
}
}
let m168_para_ok = left_tables == 0
&& right_tables == 0
&& left_textboxes == 0
&& right_textboxes == 0
&& left_paras == left_len
&& right_paras == right_len
&& (3..=10).contains(&left_paras)
&& (3..=8).contains(&right_paras)
&& left_paras != right_paras;
if settings.merge_replaced_paragraphs && m168_para_ok {
let a0 = para_text_token_list(dom, &cul1[0]);
let b0 = para_text_token_list(dom, &cul2[0]);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b));
let last_diff = match (last_significant_token(&a0), last_significant_token(&b0)) {
(Some(x), Some(y)) => !x.eq_ignore_ascii_case(y),
_ => true,
};
let body_j = if left_paras >= 2 && right_paras >= 2 {
token_jaccard(
¶_text_tokens_from_units(dom, &cul1[1..]),
¶_text_tokens_from_units(dom, &cul2[1..]),
)
} else {
1.0
};
if first_same
&& last_diff
&& (2..=4).contains(&a0.len())
&& (2..=4).contains(&b0.len())
&& body_j + 1e-12 < 0.12
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[0].clone()],
));
for u in &cul2[1..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &cul1[1..] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return out;
}
}
let title_demo_unrelated_body = left_paras == 3
&& right_paras == 3
&& first_paras_share_last_sig(dom, cul1, cul2)
&& body_residual_unrelated(dom, cul1, cul2)
&& {
let d0 = token_jaccard(
¶_text_tokens(dom, &cul1[0]),
¶_text_tokens(dom, &cul2[0]),
);
let d1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let d2 = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
d0 > 0.0 && d1 + 1e-12 < 0.08 && d2 + 1e-12 < 0.08
};
let a1_n_zip = if left_paras >= 2 {
para_text_tokens(dom, &cul1[1]).len()
} else {
0
};
let b1_n_zip = if right_paras >= 2 {
para_text_tokens(dom, &cul2[1]).len()
} else {
0
};
let skip_zip_for_m149 = title_demo_unrelated_body
&& ((a1_n_zip > 0 && a1_n_zip <= 6) || (b1_n_zip > 0 && b1_n_zip <= 6))
&& {
let style_body = |u: &ComparisonUnit| {
para_text_token_list(dom, u).iter().any(|t| {
t.eq_ignore_ascii_case("heading")
|| t.eq_ignore_ascii_case("paragraph")
|| t.eq_ignore_ascii_case("style")
})
};
left_paras >= 2
&& right_paras >= 2
&& !style_body(&cul1[1])
&& !style_body(&cul2[1])
};
let skip_zip_for_m153 = title_demo_unrelated_body && a1_n_zip > 6 && b1_n_zip > 6;
let is_m151_residual_pair = |left: &ComparisonUnit, right: &ComparisonUnit| {
residual_para_starts_this(dom, left) && residual_para_starts_this(dom, right) && {
let a1 = para_text_token_list(dom, left);
let b1 = para_text_token_list(dom, right);
ordered_shared_prefix_sig(&a1, &b1) == 1
&& a1.get(1).is_some_and(|t| t.eq_ignore_ascii_case("text"))
&& b1
.get(1)
.is_some_and(|t| t.eq_ignore_ascii_case("document"))
}
};
let skip_zip_for_m151 = left_paras == 3
&& right_paras == 3
&& first_paras_share_last_sig(dom, cul1, cul2)
&& is_m151_residual_pair(&cul1[1], &cul2[1]);
let m151_residual_window = left_paras == 2
&& right_paras == 2
&& left_paras == left_len
&& right_paras == right_len
&& is_m151_residual_pair(&cul1[0], &cul2[0]);
if settings.merge_replaced_paragraphs && m151_residual_window {
out.push(CorrelatedSequence::inserted(vec![cul2[0].clone()]));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[1].clone()],
));
out.push(CorrelatedSequence::deleted(vec![cul1[1].clone()]));
return out;
}
let skip_zip_for_m197 =
left_paras == 3 && right_paras == 3 && first_paras_share_last_sig(dom, cul1, cul2) && {
let j0 = token_jaccard(
¶_text_tokens(dom, &cul1[0]),
¶_text_tokens(dom, &cul2[0]),
);
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let j2 = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
let a1 = para_text_token_list(dom, &cul1[1]);
let b1 = para_text_token_list(dom, &cul2[1]);
let a0f = a1.first().map(|s| s.as_str()).unwrap_or("");
let b0f = b1.first().map(|s| s.as_str()).unwrap_or("");
let this_x_demo = (a0f.eq_ignore_ascii_case("this")
&& b0f.eq_ignore_ascii_case("demonstrating"))
|| (a0f.eq_ignore_ascii_case("demonstrating")
&& b0f.eq_ignore_ascii_case("this"));
j0 + 1e-12 < 0.12 && j1 + 1e-12 < 0.12 && j2 + 1e-12 < 0.12 && !this_x_demo
};
if settings.merge_replaced_paragraphs
&& skip_zip_for_m197
&& left_paras == left_len
&& right_paras == right_len
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[0].clone()],
));
out.push(CorrelatedSequence::inserted(vec![cul2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![cul1[1].clone()]));
out.push(CorrelatedSequence::inserted(vec![cul2[2].clone()]));
out.push(CorrelatedSequence::deleted(vec![cul1[2].clone()]));
return out;
}
let skip_zip_for_m210 = left_paras == 3
&& right_paras == 3
&& first_paras_share_last_sig(dom, cul1, cul2)
&& residual_para_starts_this(dom, &cul1[1])
&& residual_para_starts_this(dom, &cul2[1])
&& {
let t0a = para_text_tokens(dom, &cul1[0]);
let t0b = para_text_tokens(dom, &cul2[0]);
let has_center =
t0a.iter().any(|t| t == "center") && t0b.iter().any(|t| t == "center");
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let j2 = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
has_center
&& j1 + 1e-12 >= 0.17
&& j1 + 1e-12 < 0.20
&& j2 + 1e-12 >= 0.25
&& j2 + 1e-12 < 0.32
};
if settings.merge_replaced_paragraphs
&& skip_zip_for_m210
&& left_paras == left_len
&& right_paras == right_len
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[0].clone()],
));
out.push(CorrelatedSequence::inserted(vec![cul2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![cul1[1].clone()]));
out.push(CorrelatedSequence::inserted(vec![cul2[2].clone()]));
out.push(CorrelatedSequence::deleted(vec![cul1[2].clone()]));
return out;
}
let skip_zip_for_m165 = left_paras == 3
&& right_paras == 3
&& first_paras_share_last_sig(dom, cul1, cul2)
&& residual_para_starts_this(dom, &cul1[1])
&& residual_para_starts_this(dom, &cul2[1])
&& {
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let j2 = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
j1 + 1e-12 >= 0.55 && j2 + 1e-12 < 0.10
};
let skip_zip_for_m180 = left_paras == 3
&& right_paras == 3
&& first_paras_share_last_sig(dom, cul1, cul2)
&& residual_para_starts_this(dom, &cul1[1])
&& residual_para_starts_this(dom, &cul2[1])
&& {
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let a2 = para_text_token_list(dom, &cul1[2]);
let b2 = para_text_token_list(dom, &cul2[2]);
let j2_raw = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
let content = |toks: &[String]| -> std::collections::HashSet<String> {
toks.iter()
.filter(|t| {
t.chars().any(|c| c.is_ascii_alphanumeric()) && t.chars().count() >= 3
})
.map(|t| t.to_ascii_lowercase())
.collect()
};
let sa = content(&a2);
let sb = content(&b2);
const FORMAT_BOILER: &[&str] = &[
"bold",
"text",
"italic",
"underline",
"formatting",
"format",
"style",
"styles",
"font",
"fonts",
"this",
"that",
"with",
"from",
"into",
"used",
"for",
"and",
"the",
];
let inter: std::collections::HashSet<&String> = sa.intersection(&sb).collect();
let inter_real: Vec<&String> = inter
.iter()
.copied()
.filter(|w| !FORMAT_BOILER.iter().any(|b| w.eq_ignore_ascii_case(b)))
.collect();
let j2c = if inter_real.is_empty() {
0.0
} else {
let uni = sa.union(&sb).count() as f64;
if uni > 0.0 {
inter_real.len() as f64 / uni
} else {
0.0
}
};
let both_long = a2.len() >= 6 && b2.len() >= 6;
let real_nonempty = |toks: &[String]| -> bool {
content(toks)
.iter()
.any(|w| !FORMAT_BOILER.iter().any(|b| w.eq_ignore_ascii_case(b)))
};
let asymmetric_short =
(a2.len() >= 2 && a2.len() <= 4 && b2.len() >= 6 && real_nonempty(&a2))
|| (b2.len() >= 2 && b2.len() <= 4 && a2.len() >= 6 && real_nonempty(&b2));
j1 + 1e-12 >= 0.12
&& j1 + 1e-12 < 0.55
&& j2c + 1e-12 < 0.05
&& (both_long && j2_raw + 1e-12 < 0.15 || asymmetric_short)
};
let skip_zip_for_m183 = {
left_paras == 3
&& right_paras == 4
&& first_paras_share_last_sig(dom, cul1, cul2)
&& residual_para_starts_this(dom, &cul1[1])
&& residual_para_starts_this(dom, &cul2[1])
&& {
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let a_last = para_text_token_list(dom, &cul1[left_paras - 1]);
let b_last = para_text_token_list(dom, &cul2[right_paras - 1]);
let j_last = token_jaccard(
¶_text_tokens(dom, &cul1[left_paras - 1]),
¶_text_tokens(dom, &cul2[right_paras - 1]),
);
j1 + 1e-12 >= 0.15
&& j1 + 1e-12 < 0.55
&& j_last + 1e-12 < 0.12
&& a_last.len() >= 4
&& b_last.len() >= 4
}
};
let skip_zip_for_m173 =
left_paras == 3 && right_paras == 3 && first_paras_share_last_sig(dom, cul1, cul2) && {
let j1 = token_jaccard(
¶_text_tokens(dom, &cul1[1]),
¶_text_tokens(dom, &cul2[1]),
);
let a2 = para_text_token_list(dom, &cul1[2]);
let b2 = para_text_token_list(dom, &cul2[2]);
let j2 = token_jaccard(
¶_text_tokens(dom, &cul1[2]),
¶_text_tokens(dom, &cul2[2]),
);
let glue = ["is", "and", "a", "the", "of", "in", "to", "for"];
let mut shared_glue: std::collections::HashSet<String> =
std::collections::HashSet::new();
for t in &a2 {
if glue.iter().any(|g| t.eq_ignore_ascii_case(g))
&& b2.iter().any(|u| u.eq_ignore_ascii_case(t))
{
shared_glue.insert(t.to_ascii_lowercase());
}
}
let share_glue_n = shared_glue.len();
let strip = |toks: &[String]| -> std::collections::HashSet<String> {
toks.iter()
.filter(|t| {
!glue.iter().any(|g| t.eq_ignore_ascii_case(g))
&& t.chars().count() >= 3
})
.cloned()
.collect()
};
let sa = strip(&a2);
let sb = strip(&b2);
let j2_content = if sa.is_empty() && sb.is_empty() {
0.0
} else {
let inter = sa.intersection(&sb).count() as f64;
let uni = sa.union(&sb).count() as f64;
if uni > 0.0 { inter / uni } else { 0.0 }
};
j1 + 1e-12 >= 0.15
&& j1 + 1e-12 < 0.55
&& share_glue_n >= 2
&& j2_content + 1e-12 > 0.0
&& j2_content + 1e-12 < 0.15
&& j2 + 1e-12 >= 0.15
&& j2 + 1e-12 < 0.35
&& a2.len() >= 4
&& b2.len() >= 4
};
let skip_zip_for_m161 = {
let last_i = left_paras.saturating_sub(1);
let is_doc_title = |toks: &[String]| {
toks.len() == 2
&& toks[0].eq_ignore_ascii_case("document")
&& toks[1].eq_ignore_ascii_case("title")
};
let last_doc_title_vs_long = left_paras >= 2
&& left_paras == right_paras
&& (left_paras == 2 || left_paras == 3)
&& {
let a_last = para_text_token_list(dom, &cul1[last_i]);
let b_last = para_text_token_list(dom, &cul2[last_i]);
(is_doc_title(&a_last) && b_last.len() > 6)
|| (is_doc_title(&b_last) && a_last.len() > 6)
};
if !last_doc_title_vs_long {
false
} else if left_paras == 3 {
first_paras_share_last_sig(dom, cul1, cul2)
&& token_jaccard(
¶_text_tokens(dom, &cul1[0]),
¶_text_tokens(dom, &cul2[0]),
) + 1e-12
>= 0.5
} else {
true
}
};
if settings.merge_replaced_paragraphs
&& left_tables == 0
&& right_tables == 0
&& left_textboxes == 0
&& right_textboxes == 0
&& left_paras >= 2
&& left_paras == right_paras
&& left_paras == left_len
&& right_paras == right_len
&& left_paras <= 12
&& para_zip_diagonal_dominant(dom, cul1, cul2)
&& !skip_zip_for_m149
&& !skip_zip_for_m153
&& !skip_zip_for_m151
&& !skip_zip_for_m165
&& !skip_zip_for_m173
&& !skip_zip_for_m180
&& !skip_zip_for_m183
&& !skip_zip_for_m161
{
for (l, r) in cul1.iter().zip(cul2.iter()) {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![l.clone()],
vec![r.clone()],
));
}
return out;
}
if settings.merge_replaced_paragraphs
&& left_tables == 0
&& right_tables == 0
&& left_textboxes == 0
&& right_textboxes == 0
&& left_paras == left_len
&& right_paras == right_len
&& (2..=6).contains(&left_paras)
&& (2..=6).contains(&right_paras)
&& left_paras.abs_diff(right_paras) <= 2
&& (!(left_paras == right_paras && para_zip_diagonal_dominant(dom, cul1, cul2))
|| (skip_zip_for_m149 && a1_n_zip > 0 && a1_n_zip <= 6 && a1_n_zip <= b1_n_zip)
|| skip_zip_for_m151
|| skip_zip_for_m153
|| skip_zip_for_m165
|| skip_zip_for_m173
|| skip_zip_for_m180
|| skip_zip_for_m183
|| skip_zip_for_m161)
&& first_paras_share_last_sig(dom, cul1, cul2)
{
let rest1 = &cul1[1..];
let rest2 = &cul2[1..];
let m144 = rest1.len() >= 2 && rest1.len() > rest2.len();
let m146 = rest1.len() >= 2 && rest2.len() > rest1.len() && rest2.len() <= 6;
let m142 = body_residual_unrelated(dom, cul1, cul2);
let first_residual_j = if !rest1.is_empty() && !rest2.is_empty() {
token_jaccard(
¶_text_tokens(dom, &rest1[0]),
¶_text_tokens(dom, &rest2[0]),
)
} else {
1.0
};
let a0_n = if rest1.is_empty() {
0
} else {
para_text_tokens(dom, &rest1[0]).len()
};
let b0_n = if rest2.is_empty() {
0
} else {
para_text_tokens(dom, &rest2[0]).len()
};
let short_first_residual = (a0_n > 0 && a0_n <= 6) || (b0_n > 0 && b0_n <= 6);
let residual_looks_like_style_body = |u: &ComparisonUnit| {
let toks = para_text_token_list(dom, u);
toks.iter().any(|t| {
t.eq_ignore_ascii_case("heading")
|| t.eq_ignore_ascii_case("paragraph")
|| t.eq_ignore_ascii_case("style")
})
};
let m149 = rest1.len() == 2
&& rest2.len() == 2
&& m142
&& first_residual_j + 1e-12 < 0.08
&& short_first_residual
&& !residual_looks_like_style_body(&rest1[0])
&& !residual_looks_like_style_body(&rest2[0]);
let m153 = rest1.len() == 2
&& rest2.len() == 2
&& m142
&& first_residual_j + 1e-12 < 0.08
&& a0_n > 6
&& b0_n > 6;
let m151 = rest1.len() == 2
&& rest2.len() == 2
&& residual_para_starts_this(dom, &rest1[0])
&& residual_para_starts_this(dom, &rest2[0])
&& {
let a0 = para_text_token_list(dom, &rest1[0]);
let b0 = para_text_token_list(dom, &rest2[0]);
ordered_shared_prefix_sig(&a0, &b0) == 1
&& a0.get(1).is_some_and(|t| t.eq_ignore_ascii_case("text"))
&& b0
.get(1)
.is_some_and(|t| t.eq_ignore_ascii_case("document"))
};
let m165 = skip_zip_for_m165;
let m173 = skip_zip_for_m173;
let m180 = skip_zip_for_m180;
let m183 = skip_zip_for_m183;
let m161 = skip_zip_for_m161;
let m163 = rest1.len() >= 2
&& rest2.len() >= 2
&& residual_para_starts_this(dom, &rest2[0])
&& rest1.iter().all(|u| {
let n = para_text_tokens(dom, u).len();
(1..=3).contains(&n)
})
&& rest2[1..].iter().all(|u| {
let n = para_text_tokens(dom, u).len();
(2..=6).contains(&n)
})
&& rest2[1..].iter().any(|u| {
para_text_token_list(dom, u)
.iter()
.any(|t| t.eq_ignore_ascii_case("item"))
});
if m144
|| m146
|| m149
|| m151
|| m153
|| m142
|| m165
|| m173
|| m180
|| m183
|| m161
|| m163
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[0].clone()],
));
if m183 && rest1.len() >= 2 && rest2.len() >= 2 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[0].clone()],
));
if rest2.len() > rest1.len() {
for u in &rest2[1..rest2.len() - 1] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
out.push(CorrelatedSequence::inserted(vec![
rest2[rest2.len() - 1].clone(),
]));
out.push(CorrelatedSequence::deleted(vec![
rest1[rest1.len() - 1].clone(),
]));
} else {
for u in &rest1[1..rest1.len() - 1] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
out.push(CorrelatedSequence::inserted(vec![
rest2[rest2.len() - 1].clone(),
]));
out.push(CorrelatedSequence::deleted(vec![
rest1[rest1.len() - 1].clone(),
]));
}
} else if m163 {
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
let items2 = &rest2[1..];
let n = rest1.len().min(items2.len());
for i in 0..n {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[i].clone()],
vec![items2[i].clone()],
));
}
for u in rest1.iter().skip(n) {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
for u in items2.iter().skip(n) {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
} else if m161 && rest1.len() >= 2 && rest2.len() >= 2 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[0].clone()],
));
out.push(CorrelatedSequence::inserted(vec![rest2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[1].clone()]));
} else if m161 && rest1.len() == 1 && rest2.len() == 1 {
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
} else if (m165 || m180) && rest1.len() == 2 && rest2.len() == 2 {
let first_j = token_jaccard(
¶_text_tokens(dom, &rest1[0]),
¶_text_tokens(dom, &rest2[0]),
);
let both_long_res = unit_text_token_count(dom, &rest1[1]) >= 6
&& unit_text_token_count(dom, &rest2[1]) >= 6;
let pure_both = first_j + 1e-12 < 0.15
|| (both_long_res && first_j + 1e-12 >= 0.46 && first_j + 1e-12 < 0.50);
if m180 && pure_both {
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
out.push(CorrelatedSequence::inserted(vec![rest2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[1].clone()]));
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[0].clone()],
));
out.push(CorrelatedSequence::inserted(vec![rest2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[1].clone()]));
}
} else if m173 && rest1.len() == 2 && rest2.len() == 2 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[0].clone()],
));
let mut left = group_contents(&rest1[1]);
let mut right = group_contents(&rest2[1]);
while left.last().is_some_and(|u| unit_is_single_atom_ppr(dom, u)) {
left.pop();
}
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested = lcs(dom, left, right, &residual_settings);
out.append(&mut nested);
} else if m149 {
if b0_n > 0 && b0_n < a0_n {
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
} else {
out.push(CorrelatedSequence::deleted(vec![rest1[0].clone()]));
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
}
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[1].clone()],
vec![rest2[1].clone()],
));
} else if m151 || m153 {
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[1].clone()],
));
out.push(CorrelatedSequence::deleted(vec![rest1[1].clone()]));
} else if m146
&& rest2.len() >= 2
&& residual_para_starts_this(dom, &rest1[0])
&& residual_para_starts_this(dom, &rest2[0])
&& ordered_shared_prefix_sig(
¶_text_token_list(dom, &rest1[0]),
¶_text_token_list(dom, &rest2[0]),
) < 2
{
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2[1..].iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
} else if m144
&& !rest2.is_empty()
&& residual_para_starts_this(dom, &rest2[0])
&& {
let this_cousins = residual_para_starts_this(dom, &rest1[0])
&& ordered_shared_prefix_sig(
¶_text_token_list(dom, &rest1[0]),
¶_text_token_list(dom, &rest2[0]),
) < 2;
let short_list_item = para_text_tokens(dom, &rest1[0]).len() <= 2;
this_cousins || short_list_item
}
{
out.push(CorrelatedSequence::inserted(vec![rest2[0].clone()]));
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2[1..].iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
} else if m144 && rest1.len() == 2 && rest2.len() == 1 {
let mut a0: Vec<ComparisonUnit> = group_contents(&rest1[0]);
let mut a1: Vec<ComparisonUnit> = group_contents(&rest1[1]);
let mut b: Vec<ComparisonUnit> = group_contents(&rest2[0]);
rehash_words_by_text_content(dom, &mut a0);
rehash_words_by_text_content(dom, &mut a1);
rehash_words_by_text_content(dom, &mut b);
let mut lcp = 0usize;
while lcp < a0.len().min(b.len()) && a0[lcp].sha1() == b[lcp].sha1() {
lcp += 1;
}
let mut split_at = lcp;
if lcp >= 8 && lcp < b.len() && a0.len() > lcp && a0.len() - lcp <= 2 {
let mut i = lcp;
while i < b.len().saturating_sub(1) {
i += 1;
let text = match &b[i - 1] {
ComparisonUnit::Word(w) => w
.contents
.iter()
.filter_map(|a| {
if dom.name_is(a.content_element, &W::t()) {
Some(dom.value_str(a.content_element))
} else {
None
}
})
.collect::<String>(),
_ => String::new(),
};
if text.chars().any(|c| c.is_alphanumeric()) {
break;
}
}
if i < b.len() {
split_at = i;
}
}
if lcp >= 8 && split_at > 0 && split_at < b.len() {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a0,
b[..split_at].to_vec(),
));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a1,
b[split_at..].to_vec(),
));
} else {
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
}
} else if m144
&& rest1.len() == 3
&& rest2.len() == 2
&& residual_para_starts_this(dom, &rest1[0])
&& residual_para_starts_this(dom, &rest2[0])
&& {
let a0 = para_text_token_list(dom, &rest1[0]);
let b0 = para_text_token_list(dom, &rest2[0]);
let a1 = para_text_token_list(dom, &rest1[1]);
ordered_shared_prefix_sig(&a0, &b0) >= 3
&& b0.last().is_some_and(|t| t.eq_ignore_ascii_case("text"))
&& a1.len() >= 2
&& a1[0].eq_ignore_ascii_case("this")
&& a1[1].eq_ignore_ascii_case("text")
}
{
let mut b0 = group_contents(&rest2[0]);
rehash_words_by_text_content(dom, &mut b0);
let mut peel_from = b0.len();
while peel_from > 0 && unit_is_single_atom_ppr(dom, &b0[peel_from - 1]) {
peel_from -= 1;
}
peel_from = peel_from.saturating_sub(1);
let b0_main = b0[..peel_from].to_vec();
let b0_peel = b0[peel_from..].to_vec();
let mut a0 = group_contents(&rest1[0]);
rehash_words_by_text_content(dom, &mut a0);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a0,
b0_main,
));
let mut a1 = group_contents(&rest1[1]);
rehash_words_by_text_content(dom, &mut a1);
let mut peel = b0_peel;
rehash_words_by_text_content(dom, &mut peel);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a1,
peel,
));
out.push(CorrelatedSequence::inserted(vec![rest2[1].clone()]));
out.push(CorrelatedSequence::deleted(vec![rest1[2].clone()]));
} else if m146
&& rest1.len() == 2
&& rest2.len() == 3
&& residual_para_starts_this(dom, &rest1[0])
&& residual_para_starts_this(dom, &rest2[0])
&& {
let a0 = para_text_token_list(dom, &rest1[0]);
let b0 = para_text_token_list(dom, &rest2[0]);
ordered_shared_prefix_sig(&a0, &b0) >= 4
&& a0.get(3).is_some_and(|t| t.eq_ignore_ascii_case("font"))
&& b0.get(3).is_some_and(|t| t.eq_ignore_ascii_case("font"))
}
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![rest1[0].clone()],
vec![rest2[0].clone()],
));
let mut a1 = group_contents(&rest1[1]);
let mut b1 = group_contents(&rest2[1]);
let mut b2 = group_contents(&rest2[2]);
rehash_words_by_text_content(dom, &mut a1);
rehash_words_by_text_content(dom, &mut b1);
rehash_words_by_text_content(dom, &mut b2);
let word_text = |dom: &Dom, u: &ComparisonUnit| -> String {
match u {
ComparisonUnit::Word(w) => w
.contents
.iter()
.filter_map(|a| {
if dom.name_is(a.content_element, &W::t()) {
Some(dom.value_str(a.content_element))
} else {
None
}
})
.collect(),
_ => String::new(),
}
};
let font_idx = a1
.iter()
.position(|u| word_text(dom, u).eq_ignore_ascii_case("font"));
if let Some(fi) = font_idx {
if fi + 1 < a1.len() {
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested1 = lcs(dom, a1[..=fi].to_vec(), b1, &residual_settings);
out.append(&mut nested1);
let mut nested2 =
lcs(dom, a1[fi + 1..].to_vec(), b2, &residual_settings);
out.append(&mut nested2);
} else {
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut right = b1;
right.extend(b2);
let mut nested = lcs(dom, a1, right, &residual_settings);
out.append(&mut nested);
}
} else {
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut right = b1;
right.extend(b2);
let mut nested = lcs(dom, a1, right, &residual_settings);
out.append(&mut nested);
}
} else if m144 || m146 {
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
} else if rest1.len() == 1
&& rest2.len() == 2
&& residual_para_starts_this(dom, &rest1[0])
&& residual_para_starts_this(dom, &rest2[0])
&& {
let a0 = para_text_token_list(dom, &rest1[0]);
let b0 = para_text_token_list(dom, &rest2[0]);
ordered_shared_prefix_sig(&a0, &b0) >= 3
&& a0
.get(2)
.is_some_and(|t| t.eq_ignore_ascii_case("demonstrates"))
&& b0
.get(2)
.is_some_and(|t| t.eq_ignore_ascii_case("demonstrates"))
&& b0.len() <= 8
&& a0.len() > b0.len()
}
{
let mut a0 = group_contents(&rest1[0]);
let mut b0 = group_contents(&rest2[0]);
let mut b1 = group_contents(&rest2[1]);
rehash_words_by_text_content(dom, &mut a0);
rehash_words_by_text_content(dom, &mut b0);
rehash_words_by_text_content(dom, &mut b1);
let mut lcp = 0usize;
while lcp < a0.len().min(b0.len()) && a0[lcp].sha1() == b0[lcp].sha1() {
lcp += 1;
}
if lcp >= 3 && lcp < a0.len() {
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut nested1 = lcs(dom, a0[..lcp].to_vec(), b0, &residual_settings);
out.append(&mut nested1);
let mut left_tail = a0[lcp..].to_vec();
while left_tail
.last()
.is_some_and(|u| unit_is_single_atom_ppr(dom, u))
{
left_tail.pop();
}
let mut nested2 = lcs(dom, left_tail, b1, &residual_settings);
out.append(&mut nested2);
} else {
for r in rest2 {
out.push(CorrelatedSequence::inserted(vec![r.clone()]));
}
for l in rest1 {
out.push(CorrelatedSequence::deleted(vec![l.clone()]));
}
}
} else if m142
&& rest1.len() == 2
&& rest2.len() == 2
&& first_residual_j + 1e-12 >= 0.12
{
let mut left: Vec<ComparisonUnit> =
rest1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
rest2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
} else {
for r in rest2 {
out.push(CorrelatedSequence::inserted(vec![r.clone()]));
}
for l in rest1 {
out.push(CorrelatedSequence::deleted(vec![l.clone()]));
}
}
return out;
}
}
if settings.merge_replaced_paragraphs
&& left_tables == 0
&& right_tables == 0
&& left_textboxes == 0
&& right_textboxes == 0
&& left_paras == left_len
&& right_paras == right_len
&& (1..=6).contains(&left_paras)
&& (1..=6).contains(&right_paras)
&& left_paras != right_paras
&& residual_sets_weakly_related(dom, cul1, cul2)
{
let (base_rest, next_body) = if left_paras == 2 && right_paras == 1 {
(Some((&cul1[0], &cul1[1])), Some(&cul2[0]))
} else if left_paras == 3
&& right_paras == 2
&& first_paras_share_last_sig(dom, cul1, cul2)
&& token_jaccard(
¶_text_tokens(dom, &cul1[0]),
¶_text_tokens(dom, &cul2[0]),
) + 1e-12
>= 0.99
{
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[0].clone()],
vec![cul2[0].clone()],
));
(Some((&cul1[1], &cul1[2])), Some(&cul2[1]))
} else {
(None, None)
};
if let (Some((a0u, a1u)), Some(bu)) = (base_rest, next_body) {
let mut a0: Vec<ComparisonUnit> = group_contents(a0u);
let mut a1: Vec<ComparisonUnit> = group_contents(a1u);
let mut b: Vec<ComparisonUnit> = group_contents(bu);
rehash_words_by_text_content(dom, &mut a0);
rehash_words_by_text_content(dom, &mut a1);
rehash_words_by_text_content(dom, &mut b);
let mut lcp = 0usize;
while lcp < a0.len().min(b.len()) && a0[lcp].sha1() == b[lcp].sha1() {
lcp += 1;
}
let mut split_at = lcp;
if lcp >= 8 && lcp < b.len() && a0.len() > lcp && a0.len() - lcp <= 2 {
let mut i = lcp;
while i < b.len().saturating_sub(1) {
i += 1;
let text = match &b[i - 1] {
ComparisonUnit::Word(w) => w
.contents
.iter()
.filter_map(|a| {
if dom.name_is(a.content_element, &W::t()) {
Some(dom.value_str(a.content_element))
} else {
None
}
})
.collect::<String>(),
_ => String::new(),
};
if text.chars().any(|c| c.is_alphanumeric()) {
break;
}
}
if i < b.len() {
split_at = i;
}
}
if lcp >= 8 && split_at > 0 && split_at < b.len() {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a0,
b[..split_at].to_vec(),
));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
a1,
b[split_at..].to_vec(),
));
return out;
}
}
let mut left: Vec<ComparisonUnit> = cul1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = cul2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
return out;
}
let left: Vec<ComparisonUnit> = cul1.iter().flat_map(group_contents).collect();
let right: Vec<ComparisonUnit> = cul2.iter().flat_map(group_contents).collect();
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
left,
right,
));
return out;
}
if let (Some(fl), Some(fr)) = (
cul1.first().and_then(as_group),
cul2.first().and_then(as_group),
) {
if fl.group_type == Row && fr.group_type == Row {
let mut lc: Vec<Option<ComparisonUnit>> =
fl.contents.iter().cloned().map(Some).collect();
let mut rc: Vec<Option<ComparisonUnit>> =
fr.contents.iter().cloned().map(Some).collect();
while lc.len() < rc.len() {
lc.push(None);
}
while rc.len() < lc.len() {
rc.push(None);
}
for (l, r) in lc.into_iter().zip(rc) {
match (l, r) {
(Some(l), Some(r)) => out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![l],
vec![r],
)),
(None, Some(r)) => out.push(CorrelatedSequence::inserted(group_contents(&r))),
(Some(l), None) => out.push(CorrelatedSequence::deleted(group_contents(&l))),
(None, None) => {}
}
}
cascade(cul1[1..].to_vec(), cul2[1..].to_vec(), &mut out);
return out;
}
if fl.group_type == Cell && fr.group_type == Cell {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
fl.contents.clone(),
fr.contents.clone(),
));
cascade(cul1[1..].to_vec(), cul2[1..].to_vec(), &mut out);
return out;
}
}
if !cul1.is_empty() && !cul2.is_empty() {
let l_word = matches!(cul1[0], ComparisonUnit::Word(_));
let r_row = as_group(&cul2[0]).is_some_and(|g| g.group_type == Row);
if l_word && r_row {
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
return out;
}
let l_row = as_group(&cul1[0]).is_some_and(|g| g.group_type == Row);
let r_word = matches!(cul2[0], ComparisonUnit::Word(_));
if r_word && l_row {
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
return out;
}
let l_ppr = last_atom_overall_is_ppr(dom, cul1);
let r_ppr = last_atom_overall_is_ppr(dom, cul2);
if let (Some(l_ppr), Some(r_ppr)) = (l_ppr, r_ppr) {
if l_ppr && !r_ppr {
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
return out;
} else if !l_ppr && r_ppr {
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
return out;
}
}
}
let is_block_group = |u: &ComparisonUnit| {
as_group(u).is_some_and(|g| {
matches!(
g.group_type,
ComparisonUnitGroupType::Paragraph | ComparisonUnitGroupType::Table
)
})
};
let block_level = |units: &[ComparisonUnit]| {
matches!(units.first(), Some(u) if is_block_group(u))
&& matches!(units.last(), Some(u) if is_block_group(u))
};
if settings.merge_replaced_paragraphs && (block_level(cul1) || block_level(cul2)) {
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
return out;
}
out.push(CorrelatedSequence::deleted(cul1.to_vec()));
out.push(CorrelatedSequence::inserted(cul2.to_vec()));
out
}
pub fn detect_unrelated_sources(
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
) -> Option<Vec<CorrelatedSequence>> {
if !block_groups_fully_disjoint(cu1, cu2) {
return None;
}
Some(vec![
CorrelatedSequence::deleted(cu1.to_vec()),
CorrelatedSequence::inserted(cu2.to_vec()),
])
}
fn block_groups_fully_disjoint(cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
let groups1: Vec<&str> = cu1
.iter()
.filter_map(|u| as_group(u).map(|_| u.sha1()))
.collect();
let groups2: Vec<&str> = cu2
.iter()
.filter_map(|u| as_group(u).map(|_| u.sha1()))
.collect();
if groups1.len() <= 3 || groups2.len() <= 3 {
return false;
}
!groups1.iter().any(|h| groups2.contains(h))
}
fn flatten_groups_one_level(cu: &[ComparisonUnit]) -> Vec<ComparisonUnit> {
if cu.iter().any(|u| matches!(u, ComparisonUnit::Group(_))) {
cu.iter().flat_map(group_contents).collect()
} else {
cu.to_vec()
}
}
fn group_has_drawing_or_pict(dom: &Dom, u: &ComparisonUnit) -> bool {
u.descendant_atoms().iter().any(|a| {
let Some(n) = dom.name(a.content_element) else {
return false;
};
n == W::drawing()
|| n == W::pict()
|| n == W::name("object")
|| n.local_name() == "AlternateContent"
|| n.local_name() == "drawing"
|| n.local_name() == "pict"
})
}
fn contentful_group_sha1s<'a>(dom: &Dom, cu: &'a [ComparisonUnit]) -> Vec<&'a str> {
cu.iter()
.filter_map(|u| {
as_group(u)?;
let has_text = run_real_text_len(dom, std::slice::from_ref(u)) > 0;
if !has_text && !group_has_drawing_or_pict(dom, u) {
return None;
}
Some(u.sha1())
})
.collect()
}
fn tokens_once<'a>(
cell: &'a std::cell::OnceCell<std::collections::HashSet<String>>,
dom: &Dom,
cu: &[ComparisonUnit],
) -> &'a std::collections::HashSet<String> {
cell.get_or_init(|| para_text_tokens_from_units(dom, cu))
}
fn has_common_run_ge(left: &[ComparisonUnit], right: &[ComparisonUnit], target: usize) -> bool {
if target == 0 {
return true;
}
if left.len() < target || right.len() < target {
return false;
}
const B: u64 = 0x0000_0100_0000_01b3;
let key = |u: &ComparisonUnit| -> u64 {
let k = u.sha1_key128();
(k as u64) ^ ((k >> 64) as u64)
};
let mut bpow = 1u64;
for _ in 0..target - 1 {
bpow = bpow.wrapping_mul(B);
}
let window_hashes = |units: &[ComparisonUnit]| -> Vec<u64> {
let mut hashes = Vec::with_capacity(units.len() + 1 - target);
let mut h = 0u64;
for u in &units[..target] {
h = h.wrapping_mul(B).wrapping_add(key(u));
}
hashes.push(h);
for i in 1..=units.len() - target {
h = h
.wrapping_sub(key(&units[i - 1]).wrapping_mul(bpow))
.wrapping_mul(B)
.wrapping_add(key(&units[i + target - 1]));
hashes.push(h);
}
hashes
};
let right_set: std::collections::HashSet<u64> = window_hashes(right).into_iter().collect();
window_hashes(left)
.into_iter()
.any(|h| right_set.contains(&h))
}
pub fn detect_unrelated_sources_word_mode(
dom: &mut Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
settings: &WmlComparerSettings,
) -> Option<Vec<CorrelatedSequence>> {
let full_tokens_1: std::cell::OnceCell<std::collections::HashSet<String>> =
std::cell::OnceCell::new();
let full_tokens_2: std::cell::OnceCell<std::collections::HashSet<String>> =
std::cell::OnceCell::new();
let groups1 = contentful_group_sha1s(dom, cu1);
let groups2 = contentful_group_sha1s(dom, cu2);
let (n1, n2) = (groups1.len(), groups2.len());
let has_table = |cu: &[ComparisonUnit]| {
cu.iter()
.any(|u| as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table))
};
let (short_cu, short_n, long_n) = if n1 <= n2 {
(cu1, n1, n2)
} else {
(cu2, n2, n1)
};
let stamped = matches!(
(
first_contentful_para_text(dom, cu1),
first_contentful_para_text(dom, cu2),
),
(Some(t1), Some(t2))
if t1.to_ascii_lowercase().starts_with("file_")
&& t2.to_ascii_lowercase().starts_with("file_")
);
let disjoint = !groups1.iter().any(|h| groups2.contains(h));
if n1 == 3
&& n2 == 2
&& !has_table(cu1)
&& !has_table(cu2)
&& cu1
.first()
.is_some_and(|u| residual_title_ends_demo(dom, u))
&& cu2
.first()
.is_some_and(|u| !residual_title_ends_demo(dom, u))
&& {
let t1 = para_text_tokens(dom, &cu1[0]);
let t2 = para_text_tokens(dom, &cu2[0]);
let b1 = para_text_tokens_from_units(dom, &cu1[1..]);
let b2 = para_text_tokens_from_units(dom, &cu2[1..]);
token_jaccard(&t1, &t2) + 1e-12 < 0.05 && token_jaccard(&b1, &b2) + 1e-12 < 0.05
}
{
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
let stamped_body_unrelated =
stamped && n2 == short_n && long_n > 20 && (2..=20).contains(&short_n) && {
let rest = |cu: &[ComparisonUnit]| -> std::collections::HashSet<String> {
match first_contentful_group_index(dom, cu) {
Some(i) if i + 1 < cu.len() => para_text_tokens_from_units(dom, &cu[i + 1..]),
_ => std::collections::HashSet::new(),
}
};
let b1 = rest(cu1);
let b2 = rest(cu2);
if b1.is_empty() || b2.is_empty() {
true
} else {
token_jaccard(&b1, &b2) + 1e-12 < 0.15
}
};
if stamped_body_unrelated {
if should_stamp_confetti(dom, cu1, cu2) {
return stamp_confetti_then_replace(dom, cu1, cu2, settings);
}
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
{
let contentful_n = |cu: &[ComparisonUnit]| -> usize {
cu.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count()
};
let cn1 = contentful_n(cu1);
let cn2 = contentful_n(cu2);
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& cn1 >= 6
&& (3..=10).contains(&cn2)
&& looks_like_short_label_stubs(dom, cu2)
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let j = token_jaccard(b1, b2);
let with_num = cu1
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.filter(|u| unit_para_has_numpr(dom, u))
.count();
let base_list_frac = with_num as f64 / cn1 as f64;
if !b1.is_empty() && j + 1e-12 < 0.25 && base_list_frac + 1e-12 >= 0.5 {
let right_c: Vec<ComparisonUnit> = cu2
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.cloned()
.collect();
let mut peel_n = 0usize;
for u in &right_c {
let toks = para_text_token_list(dom, u);
let first = toks.first().map(|t| t.as_str()).unwrap_or("");
if first.chars().count() >= 3 {
peel_n += 1;
} else {
break;
}
}
if peel_n >= 1 && peel_n < right_c.len() {
let mut out = Vec::new();
let mut consumed = 0usize;
let mut contentful_seen = 0usize;
for u in cu2 {
let is_c = as_group(u).is_some() && unit_has_text_token(dom, u);
if is_c {
if contentful_seen >= peel_n {
break;
}
contentful_seen += 1;
}
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
consumed += 1;
}
let residual: Vec<ComparisonUnit> = cu2[consumed..].to_vec();
let mut left: Vec<ComparisonUnit> =
cu1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
residual.iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 100_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
out.extend(lcs(dom, left, right, &residual_settings));
return Some(out);
}
for u in residual {
out.push(CorrelatedSequence::inserted(vec![u]));
}
out.push(CorrelatedSequence::deleted(cu1.to_vec()));
return Some(out);
}
}
}
}
if settings.merge_replaced_paragraphs
&& short_n >= 4
&& long_n > short_n
&& !has_table(cu1)
&& !has_table(cu2)
&& n1 >= 4
&& n2 >= 4
{
let body_j = token_jaccard(
tokens_once(&full_tokens_1, dom, cu1),
tokens_once(&full_tokens_2, dom, cu2),
);
let cl: Vec<&ComparisonUnit> = cu1
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
let cr: Vec<&ComparisonUnit> = cu2
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
let mostly_list = |xs: &[&ComparisonUnit]| -> bool {
if xs.is_empty() {
return false;
}
let with_num = xs.iter().filter(|u| unit_para_has_numpr(dom, u)).count();
with_num * 2 >= xs.len()
};
let cut = first_list_cluster_end(dom, cu1);
let has_nested = cl.iter().any(|u| unit_para_ilvl(dom, u).unwrap_or(0) >= 1);
let next_uniform_short = {
let first = cr
.first()
.map(|u| para_text_token_list(dom, u))
.unwrap_or_default();
!cr.is_empty()
&& first.len() == 1
&& cr.iter().all(|u| {
let t = para_text_token_list(dom, u);
t.len() == 1 && t[0].eq_ignore_ascii_case(&first[0])
})
};
if body_j + 1e-12 < 0.25
&& mostly_list(&cl)
&& mostly_list(&cr)
&& short_item_list_groups(dom, &cl)
&& short_item_list_groups(dom, &cr)
&& has_nested
&& cut >= 2
&& cut < cu1.len()
&& !cu2.is_empty()
&& !(next_uniform_short && body_j + 1e-12 < 0.12)
{
let mut out = Vec::new();
out.push(CorrelatedSequence::inserted(vec![cu2[0].clone()]));
out.push(CorrelatedSequence::deleted(cu1[..cut].to_vec()));
if cut < cu1.len() || cu2.len() > 1 {
if cu2.len() > 1 {
out.push(CorrelatedSequence::inserted(cu2[1..].to_vec()));
}
if cut < cu1.len() {
out.push(CorrelatedSequence::deleted(cu1[cut..].to_vec()));
}
}
return Some(out);
}
}
if settings.merge_replaced_paragraphs
&& short_n >= 2
&& long_n > short_n
&& !has_table(cu1)
&& !has_table(cu2)
{
let body_j = token_jaccard(
tokens_once(&full_tokens_1, dom, cu1),
tokens_once(&full_tokens_2, dom, cu2),
);
let cl: Vec<&ComparisonUnit> = cu1
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
let cr: Vec<&ComparisonUnit> = cu2
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
let mostly_list = |xs: &[&ComparisonUnit]| -> bool {
if xs.is_empty() {
return false;
}
let with_num = xs.iter().filter(|u| unit_para_has_numpr(dom, u)).count();
with_num * 2 >= xs.len()
};
if body_j + 1e-12 < 0.12
&& mostly_list(&cl)
&& mostly_list(&cr)
&& short_item_list_groups(dom, &cl)
&& short_item_list_groups(dom, &cr)
{
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
let unit_textless = |u: &ComparisonUnit| -> bool {
u.descendant_atoms().iter().all(|a| {
!dom.name_is(a.content_element, &W::t())
|| dom.value_str(a.content_element).trim().is_empty()
}) && !group_has_drawing_or_pict(dom, u)
};
let textless_multi =
|cu: &[ComparisonUnit]| -> bool { cu.len() >= 3 && cu.iter().all(unit_textless) };
if textless_multi(cu2) && !groups1.is_empty() && !has_table(cu1) && !has_table(cu2) {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
if textless_multi(cu1) && !groups2.is_empty() && !has_table(cu1) && !has_table(cu2) {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
if settings.merge_replaced_paragraphs
&& (1..=2).contains(&n1)
&& n2 >= 5
&& !has_table(cu1)
&& !has_table(cu2)
&& {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let sig1 = significant_tokens(b1);
!b1.is_empty() && sig1.len() <= 8 && token_jaccard(b1, b2) + 1e-12 < 0.05
}
{
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
if settings.merge_replaced_paragraphs
&& (1..=4).contains(&n1)
&& (2..=30).contains(&n2)
&& !has_table(cu1)
&& has_table(cu2)
&& {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let sig1 = significant_tokens(b1);
!b1.is_empty() && sig1.len() <= 24 && token_jaccard(b1, b2) + 1e-12 < 0.05
}
{
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
if settings.merge_replaced_paragraphs && n1 <= 4 && n2 > n1 && has_table(cu1) {
let n_tbl = |cu: &[ComparisonUnit]| -> usize {
cu.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table)
})
.count()
};
if n_tbl(cu1) == 1 && n_tbl(cu2) >= 3 && n_tbl(cu2) * 2 >= n2 {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.05 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& looks_like_fields_html_doc(dom, cu2)
&& (looks_like_short_alpha_list(dom, cu1) || looks_like_short_annotation_doc(dom, cu1))
{
let mut left: Vec<ComparisonUnit> = cu1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = cu2.iter().flat_map(group_contents).collect();
if !left.is_empty() && !right.is_empty() && left.len().saturating_mul(right.len()) <= 50_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
return Some(lcs(dom, left, right, &residual_settings));
}
}
if settings.merge_replaced_paragraphs
&& short_ooxml_property_demo(dom, cu1)
&& !has_table(cu2)
&& (looks_like_short_alpha_list(dom, cu2) || looks_like_short_alpha_list_cluster(dom, cu2))
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.10 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& (looks_like_short_alpha_list(dom, cu1) || looks_like_short_alpha_list_cluster(dom, cu1))
&& short_ooxml_property_demo(dom, cu2)
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.10 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& n1 >= 8
&& (looks_like_short_alpha_list(dom, cu2) || looks_like_short_alpha_list_cluster(dom, cu2))
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let next_ok = !b2.is_empty()
|| looks_like_short_alpha_list(dom, cu2)
|| looks_like_short_alpha_list_cluster(dom, cu2);
if !b1.is_empty() && next_ok && token_jaccard(b1, b2) + 1e-12 < 0.05 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& n2 >= 8
&& (looks_like_short_alpha_list(dom, cu1) || looks_like_short_alpha_list_cluster(dom, cu1))
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let base_ok = !b1.is_empty()
|| looks_like_short_alpha_list(dom, cu1)
|| looks_like_short_alpha_list_cluster(dom, cu1);
if base_ok && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.05 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
if settings.merge_replaced_paragraphs && !has_table(cu1) && !has_table(cu2) {
let left_toks: Vec<Vec<String>> = cu1
.iter()
.filter(|u| as_group(u).is_some())
.map(|u| para_text_token_list(dom, u))
.filter(|t| !t.is_empty())
.collect();
let right_toks: Vec<Vec<String>> = cu2
.iter()
.filter(|u| as_group(u).is_some())
.map(|u| para_text_token_list(dom, u))
.filter(|t| !t.is_empty())
.collect();
if (3..=8).contains(&left_toks.len()) && right_toks.len() == 1 && right_toks[0].len() >= 20
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.05 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
}
if settings.merge_replaced_paragraphs && !has_table(cu2) {
let bb = looks_like_math_borderbox_doc(dom, cu2) || looks_like_math_doc(dom, cu2);
let cn1 = cu1
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count();
let cn2 = cu2
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count();
if bb && cn1 >= 30 && (5..=120).contains(&cn2) {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.15 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& (looks_like_math_borderbox_doc(dom, cu1) || looks_like_math_doc(dom, cu1))
{
let cn1 = cu1
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count();
let cn2 = cu2
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count();
if cn2 >= 30 && (5..=120).contains(&cn1) {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if !b1.is_empty() && !b2.is_empty() && token_jaccard(b1, b2) + 1e-12 < 0.15 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
}
if settings.merge_replaced_paragraphs && has_table(cu1) && !has_table(cu2) {
let contentful_idxs: Vec<usize> = cu2
.iter()
.enumerate()
.filter(|(_, u)| as_group(u).is_some() && unit_has_text_token(dom, u))
.map(|(i, _)| i)
.collect();
let is_num_stat = |u: &ComparisonUnit| -> bool {
let toks = para_text_token_list(dom, u);
!toks.is_empty()
&& toks[0].eq_ignore_ascii_case("num")
&& toks.len() >= 2
&& (toks[1].eq_ignore_ascii_case("words")
|| toks[1].eq_ignore_ascii_case("chars")
|| toks[1].eq_ignore_ascii_case("pages")
|| toks[1].eq_ignore_ascii_case("characters")
|| toks[1].eq_ignore_ascii_case("paragraphs"))
};
let num_run = contentful_idxs
.iter()
.take_while(|&&i| is_num_stat(&cu2[i]))
.count();
if num_run >= 3 {
let peel_end = contentful_idxs[num_run - 1];
let mut out = Vec::new();
out.push(CorrelatedSequence::inserted(cu2[..=peel_end].to_vec()));
let residual: Vec<ComparisonUnit> = cu2[peel_end + 1..].to_vec();
if residual.is_empty() {
out.push(CorrelatedSequence::deleted(cu1.to_vec()));
return Some(out);
}
let text_empty_group = |u: &ComparisonUnit| -> bool {
as_group(u).is_some() && !unit_has_text_token(dom, u)
};
let mut res_i = 0usize;
while res_i < residual.len() && text_empty_group(&residual[res_i]) {
out.push(CorrelatedSequence::inserted(vec![residual[res_i].clone()]));
res_i += 1;
}
let mut base_i = 0usize;
while base_i < cu1.len() && text_empty_group(&cu1[base_i]) {
out.push(CorrelatedSequence::deleted(vec![cu1[base_i].clone()]));
base_i += 1;
}
let residual_rest = residual[res_i..].to_vec();
let base_rest = cu1[base_i..].to_vec();
if residual_rest.is_empty() {
if !base_rest.is_empty() {
out.push(CorrelatedSequence::deleted(base_rest));
}
return Some(out);
}
if base_rest.is_empty() {
for u in residual_rest {
out.push(CorrelatedSequence::inserted(vec![u]));
}
return Some(out);
}
let mut left: Vec<ComparisonUnit> = base_rest.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
residual_rest.iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 100_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
out.extend(lcs(dom, left, right, &residual_settings));
return Some(out);
}
for u in residual_rest {
out.push(CorrelatedSequence::inserted(vec![u]));
}
out.push(CorrelatedSequence::deleted(base_rest));
return Some(out);
}
}
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& (1..=4).contains(&n1)
&& (1..=4).contains(&n2)
{
let contentful = |cu: &[ComparisonUnit]| -> Vec<ComparisonUnit> {
cu.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.cloned()
.collect()
};
let left_c = contentful(cu1);
let right_c = contentful(cu2);
let base_long = left_c
.first()
.is_some_and(|u| unit_text_token_count(dom, u) >= 8);
let next_stubs =
!right_c.is_empty() && right_c.iter().all(|u| unit_text_token_count(dom, u) <= 2);
if base_long && next_stubs && !left_c.is_empty() && right_c.len() >= 2 {
let first_tok = |u: &ComparisonUnit| -> Option<String> {
para_text_token_list(dom, u)
.into_iter()
.find(|t| t.chars().count() >= 3)
.map(|t| t.to_ascii_lowercase())
};
let t1 = first_tok(&left_c[0]);
let t2 = first_tok(&right_c[0]);
let titles_differ = match (t1.as_deref(), t2.as_deref()) {
(Some(a), Some(b)) => a != b,
_ => false,
};
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
if titles_differ && token_jaccard(b1, b2) + 1e-12 < 0.25 {
let peel_r = 1usize.min(right_c.len().saturating_sub(1));
let mut out = Vec::new();
for u in &right_c[..peel_r] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
let mut left: Vec<ComparisonUnit> =
left_c.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
right_c[peel_r..].iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 50_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
out.extend(lcs(dom, left, right, &residual_settings));
return Some(out);
}
for u in &right_c[peel_r..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &left_c {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
if !out.is_empty() {
return Some(out);
}
}
}
}
{
let contentful_n = |cu: &[ComparisonUnit]| -> usize {
cu.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count()
};
let cn1 = contentful_n(cu1);
let cn2 = contentful_n(cu2);
let next_shape =
looks_like_short_title_page(dom, cu2) || looks_like_short_label_stubs(dom, cu2);
if settings.merge_replaced_paragraphs
&& !has_table(cu1)
&& !has_table(cu2)
&& (1..=3).contains(&cn1)
&& (4..=12).contains(&cn2)
&& next_shape
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let j = token_jaccard(b1, b2);
let next_ok = !b2.is_empty() || looks_like_short_label_stubs(dom, cu2);
if !b1.is_empty() && next_ok && j + 1e-12 < 0.05 {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
}
if settings.merge_replaced_paragraphs
&& n2 == short_n
&& (1..=8).contains(&short_n)
&& long_n >= 4
&& has_table(cu2)
&& !ooxml_x_short_table_demo(dom, cu1, cu2)
&& !both_tables_unrelated_free_mesh(dom, cu1, cu2, n1, n2)
&& !short_cell_table_x_long_table_doc(dom, cu1, cu2, n1, n2)
&& {
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let next_sig = significant_tokens(b2);
if next_sig.is_empty() || next_sig.len() > 24 || b1.is_empty() {
false
} else {
token_jaccard(b1, b2) + 1e-12 < 0.05
}
}
&& {
if !has_table(cu1) {
true
} else if !disjoint {
false
} else {
let non_tbl = cu1
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type != ComparisonUnitGroupType::Table)
&& (run_real_text_len(dom, std::slice::from_ref(u)) > 0
|| group_has_drawing_or_pict(dom, u))
})
.count();
non_tbl >= 4
}
}
{
if has_table(cu1) {
let n_tbl_next = cu2
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table)
})
.count();
if n_tbl_next >= 2 {
return None;
}
}
if long_multitable_x_short_table_free_mesh(dom, cu1, cu2, n1, n2) {
} else {
let n_tbl_base = cu1
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table)
})
.count();
let n_tbl_next = cu2
.iter()
.filter(|u| {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table)
})
.count();
let first_c = cu2
.iter()
.position(|u| as_group(u).is_some() && unit_has_text_token(dom, u));
if n_tbl_base >= 2
&& n_tbl_next == 1
&& long_n >= 20
&& let Some(fc) = first_c
&& fc + 1 < cu2.len()
{
return Some(vec![
CorrelatedSequence::inserted(cu2[..=fc].to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
CorrelatedSequence::inserted(cu2[fc + 1..].to_vec()),
]);
}
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
}
{
let stamped_pair = matches!(
(
first_contentful_para_text(dom, cu1),
first_contentful_para_text(dom, cu2),
),
(Some(t1), Some(t2))
if t1.to_ascii_lowercase().starts_with("file_")
&& t2.to_ascii_lowercase().starts_with("file_")
);
let long_mt = long_multitable_x_short_table_free_mesh(dom, cu1, cu2, n1, n2);
let free_mesh_demos = !stamped_pair
&& (parallel_sectioned_demos(dom, cu1, cu2)
|| (short_ooxml_property_demo(dom, cu1) && short_ooxml_property_demo(dom, cu2))
|| (titles_share_last_sig(dom, cu1, cu2) && n1 <= 50 && n2 <= 50)
|| ooxml_x_short_table_demo(dom, cu1, cu2)
|| ooxml_x_short_prose_demo(dom, cu1, cu2, n1, n2)
|| both_tables_unrelated_free_mesh(dom, cu1, cu2, n1, n2)
|| short_cell_table_x_long_table_doc(dom, cu1, cu2, n1, n2)
|| short_demos_share_first_title_token(dom, cu1, cu2, n1, n2)
|| long_mt)
&& n1 != n2
&& n1 <= if long_mt { 300 } else { 80 }
&& n2 <= 80;
if short_demo_list_x_prose(dom, cu1, cu2, n1, n2) {
let contentful = |cu: &[ComparisonUnit]| -> Vec<ComparisonUnit> {
cu.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.cloned()
.collect()
};
let left_c = contentful(cu1);
let right_c = contentful(cu2);
if !left_c.is_empty() && !right_c.is_empty() {
let z = left_c.len().min(right_c.len());
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
let mut out = Vec::new();
for i in 0..z {
let mut left: Vec<ComparisonUnit> = group_contents(&left_c[i]);
let mut right: Vec<ComparisonUnit> = group_contents(&right_c[i]);
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
if left.is_empty() && right.is_empty() {
continue;
}
if left.is_empty() {
out.push(CorrelatedSequence::inserted(right));
} else if right.is_empty() {
out.push(CorrelatedSequence::deleted(left));
} else {
out.extend(lcs(dom, left, right, &residual_settings));
}
}
for u in &right_c[z..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &left_c[z..] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return Some(out);
}
}
if free_mesh_demos
&& short_ooxml_property_demo(dom, cu1)
&& short_ooxml_property_demo(dom, cu2)
{
let contentful = |cu: &[ComparisonUnit]| -> Vec<ComparisonUnit> {
cu.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.cloned()
.collect()
};
let left_c = contentful(cu1);
let right_c = contentful(cu2);
if left_c.len() >= 2 && right_c.len() >= 2 {
let first_tok = |u: &ComparisonUnit| -> Option<String> {
para_text_token_list(dom, u)
.into_iter()
.find(|t| t.chars().count() >= 3)
.map(|t| t.to_ascii_lowercase())
};
let t1 = first_tok(&left_c[0]);
let t2 = first_tok(&right_c[0]);
let titles_differ = match (t1.as_deref(), t2.as_deref()) {
(Some(a), Some(b)) => a != b,
_ => true,
};
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
let residual_tok_set =
|groups: &[ComparisonUnit]| -> std::collections::HashSet<String> {
let mut s = std::collections::HashSet::new();
for u in groups {
for t in para_text_token_list(dom, u) {
let lower = t.to_ascii_lowercase();
if lower.chars().count() >= 2 {
s.insert(lower);
}
}
}
s
};
let residual_j = if left_c.len() >= 2 && right_c.len() >= 2 {
token_jaccard(
&residual_tok_set(&left_c[1..]),
&residual_tok_set(&right_c[1..]),
)
} else {
0.0
};
let peel_titles = titles_differ && residual_j + 1e-12 < 0.10;
if peel_titles {
let sampleish = |u: &ComparisonUnit| -> bool {
let lower = para_text_token_list(dom, u)
.into_iter()
.map(|t| t.to_ascii_lowercase())
.collect::<Vec<_>>();
lower.iter().any(|t| {
t == "sample" || t == "color" || t == "text" || t.contains("sample")
}) && lower.len() >= 3
};
let mut peel_r = 0usize;
while peel_r < right_c.len().min(3) && !sampleish(&right_c[peel_r]) {
peel_r += 1;
if peel_r >= right_c.len() {
break;
}
}
peel_r = peel_r.max(1).min(right_c.len().saturating_sub(1));
let peel_l = 1usize.min(left_c.len().saturating_sub(1));
let mut out = Vec::new();
for u in &right_c[..peel_r] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &left_c[..peel_l] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
let mut left: Vec<ComparisonUnit> =
left_c[peel_l..].iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
right_c[peel_r..].iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 600_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.extend(lcs(dom, left, right, &residual_settings));
return Some(out);
}
for u in &right_c[peel_r..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &left_c[peel_l..] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
if !out.is_empty() {
return Some(out);
}
} else if !titles_differ && residual_j + 1e-12 < 0.25 {
let z = 2usize.min(left_c.len()).min(right_c.len());
let mut out = Vec::new();
for i in 0..z {
let mut left: Vec<ComparisonUnit> = group_contents(&left_c[i]);
let mut right: Vec<ComparisonUnit> = group_contents(&right_c[i]);
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
if left.is_empty() && right.is_empty() {
continue;
}
if left.is_empty() {
out.push(CorrelatedSequence::inserted(right));
} else if right.is_empty() {
out.push(CorrelatedSequence::deleted(left));
} else {
out.extend(lcs(dom, left, right, &residual_settings));
}
}
let residual_has_sample = |groups: &[ComparisonUnit]| -> bool {
groups.iter().any(|u| {
para_text_token_list(dom, u)
.into_iter()
.any(|t| t.eq_ignore_ascii_case("sample"))
})
};
let left_res = &left_c[z..];
let right_res = &right_c[z..];
let both_sample =
residual_has_sample(left_res) && residual_has_sample(right_res);
if both_sample && !left_res.is_empty() && !right_res.is_empty() {
let mut left: Vec<ComparisonUnit> =
left_res.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
right_res.iter().flat_map(group_contents).collect();
if left.len().saturating_mul(right.len()) <= 600_000 {
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.extend(lcs(dom, left, right, &residual_settings));
if !out.is_empty() {
return Some(out);
}
}
}
for u in right_res {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in left_res {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
if !out.is_empty() {
return Some(out);
}
}
}
}
if free_mesh_demos && both_tables_unrelated_free_mesh(dom, cu1, cu2, n1, n2) {
let is_tbl = |u: &ComparisonUnit| -> bool {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table)
};
let peel_leading_nontbl = |cu: &[ComparisonUnit]| -> usize {
let mut n = 0usize;
for u in cu {
if is_tbl(u) {
break;
}
n += 1;
}
n.min(cu.len().saturating_sub(1))
};
let peel_l = peel_leading_nontbl(cu1);
let peel_r = peel_leading_nontbl(cu2);
if peel_r >= 2 {
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.0;
let mut out = Vec::new();
for u in &cu2[..peel_r] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &cu1[..peel_l] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
let mut left: Vec<ComparisonUnit> =
cu1[peel_l..].iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> =
cu2[peel_r..].iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 600_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
out.extend(lcs(dom, left, right, &residual_settings));
return Some(out);
}
for u in &cu2[peel_r..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &cu1[peel_l..] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
if !out.is_empty() {
return Some(out);
}
}
}
if free_mesh_demos {
let mut left: Vec<ComparisonUnit> = cu1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = cu2.iter().flat_map(group_contents).collect();
if !left.is_empty()
&& !right.is_empty()
&& left.len().saturating_mul(right.len()) <= 600_000
{
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
let short_prop =
short_ooxml_property_demo(dom, cu1) && short_ooxml_property_demo(dom, cu2);
let ooxml_tbl = ooxml_x_short_table_demo(dom, cu1, cu2);
let both_tbl = both_tables_unrelated_free_mesh(dom, cu1, cu2, n1, n2);
let cell_tbl = short_cell_table_x_long_table_doc(dom, cu1, cu2, n1, n2);
let long_mt = long_multitable_x_short_table_free_mesh(dom, cu1, cu2, n1, n2);
residual_settings.detail_threshold =
if short_prop || ooxml_tbl || both_tbl || cell_tbl || long_mt {
0.0
} else {
0.005
};
return Some(lcs(dom, left, right, &residual_settings));
}
return None;
}
}
let ok_counts = (short_n > 3 && long_n > 3)
|| ((2..=3).contains(&short_n) && long_n > 3 && !has_table(short_cu))
|| (stamped && disjoint && (2..=6).contains(&short_n) && long_n > 6 && n2 == short_n);
if !ok_counts {
return None;
}
if !disjoint {
return None;
}
{
let b1 = tokens_once(&full_tokens_1, dom, cu1);
let b2 = tokens_once(&full_tokens_2, dom, cu2);
let s1 = significant_tokens(b1);
let s2 = significant_tokens(b2);
let j = token_jaccard(b1, b2);
if s1.len() >= 40
&& s2.len() >= 40
&& j + 1e-12 >= 0.08
&& j + 1e-12 < 0.35
&& (15..=120).contains(&n1)
&& (15..=120).contains(&n2)
&& settings.merge_replaced_paragraphs
{
if looks_like_memo_doc(dom, cu1)
&& let Some(hcut) = memo_header_cut(dom, cu1)
{
let mut out = Vec::new();
out.push(CorrelatedSequence::deleted(cu1[..hcut].to_vec()));
out.push(CorrelatedSequence::inserted(cu2.to_vec()));
if hcut < cu1.len() {
out.push(CorrelatedSequence::deleted(cu1[hcut..].to_vec()));
}
return Some(out);
}
if looks_like_memo_doc(dom, cu2) {
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
if let Some(cut) = legal_mid_splice_cut(dom, cu2) {
let mut out = Vec::new();
if cut > 0 {
out.push(CorrelatedSequence::inserted(cu2[..cut].to_vec()));
}
out.push(CorrelatedSequence::deleted(cu1.to_vec()));
if cut < cu2.len() {
out.push(CorrelatedSequence::inserted(cu2[cut..].to_vec()));
}
return Some(out);
}
return None;
}
}
let left = flatten_groups_one_level(cu1);
let right = flatten_groups_one_level(cu2);
let confetti_ok = stamped && should_stamp_confetti(dom, cu1, cu2);
if left.is_empty() || right.is_empty() {
if confetti_ok {
return stamp_confetti_then_replace(dom, cu1, cu2, settings);
}
if stamped {
return None;
}
return Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
]);
}
let skip_word_lcs = settings.merge_replaced_paragraphs
&& left.len() >= 256
&& right.len() >= 256
&& {
let right_group_keys: std::collections::HashSet<u128> = right
.iter()
.filter(|u| matches!(u, ComparisonUnit::Group(_)))
.map(ComparisonUnit::sha1_key128)
.collect();
!left.iter().any(|u| {
matches!(u, ComparisonUnit::Group(_)) && right_group_keys.contains(&u.sha1_key128())
})
}
&& {
let mut lt = String::new();
for u in &left {
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
lt.push_str(&dom.value_str(a.content_element));
}
}
}
let lt = lt.to_ascii_lowercase();
!(lt.contains("file_") || lt.contains(".docx") || lt.contains(".doc"))
}
&& {
let max_len = left.len().max(right.len());
let target = ((settings.detail_threshold * max_len as f64).ceil() as usize).max(2);
!has_common_run_ge(&left, &right, target)
};
let (_i1, _i2, len) = if skip_word_lcs {
(0, 0, 0)
} else if settings.merge_replaced_paragraphs {
longest_common_run_with_dom(Some(dom), &left, &right, Some(settings))
} else {
longest_common_run(&left, &right)
};
if len > 0 {
let i1 = _i1;
let common = &left[i1..i1 + len];
let common_all_words = common.iter().all(|c| matches!(c, ComparisonUnit::Word(_)));
if common_all_words {
let max_len = left.len().max(right.len());
let ratio_len = common
.iter()
.filter(|cs| {
!cs.descendant_atoms().iter().all(|dca| {
if !dom.name_is(dca.content_element, &W::t()) {
return false;
}
let v = dom.value_str(dca.content_element);
!v.is_empty() && v.chars().all(|ch| settings.word_separators.contains(&ch))
})
})
.count();
let stamp_run = {
let mut text = String::new();
for u in common {
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
}
let lower = text.to_ascii_lowercase();
lower.contains("file_") || lower.contains(".docx") || lower.contains(".doc")
};
if stamp_run {
if confetti_ok {
return stamp_confetti_then_replace(dom, cu1, cu2, settings);
}
return None;
}
if max_len > 0
&& (ratio_len as f64) / (max_len as f64) >= settings.detail_threshold
&& run_real_text_len(dom, common) > 0
{
if confetti_ok {
return stamp_confetti_then_replace(dom, cu1, cu2, settings);
}
return None;
}
} else if run_real_text_len(dom, common) >= 3 {
return None;
}
}
if confetti_ok {
return stamp_confetti_then_replace(dom, cu1, cu2, settings);
}
if stamped {
return None;
}
if let (Some(t1), Some(t2)) = (cu1.first(), cu2.first()) {
let a0 = para_text_token_list(dom, t1);
let b0 = para_text_token_list(dom, t2);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b));
let last_diff = match (last_significant_token(&a0), last_significant_token(&b0)) {
(Some(x), Some(y)) => !x.eq_ignore_ascii_case(y),
_ => true,
};
let body_j = if cu1.len() >= 2 && cu2.len() >= 2 {
token_jaccard(
¶_text_tokens_from_units(dom, &cu1[1..]),
¶_text_tokens_from_units(dom, &cu2[1..]),
)
} else {
1.0
};
if first_same
&& last_diff
&& (2..=4).contains(&a0.len())
&& (2..=4).contains(&b0.len())
&& body_j + 1e-12 < 0.12
&& (3..=10).contains(&cu1.len())
&& (2..=8).contains(&cu2.len())
{
let mut tleft = group_contents(t1);
let mut tright = group_contents(t2);
rehash_words_by_text_content(dom, &mut tleft);
rehash_words_by_text_content(dom, &mut tright);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
let mut out = lcs(dom, tleft, tright, &residual_settings);
for u in &cu2[1..] {
out.push(CorrelatedSequence::inserted(vec![u.clone()]));
}
for u in &cu1[1..] {
out.push(CorrelatedSequence::deleted(vec![u.clone()]));
}
return Some(out);
}
}
if (2..=4).contains(&cu2.len())
&& cu1.len() >= 5
&& residual_title_ends_demo(dom, &cu2[0])
&& para_text_token_list(dom, &cu2[0])
.iter()
.any(|t| t.eq_ignore_ascii_case("and"))
&& residual_looks_like_colon_list(dom, &cu1[1..])
{
let mut left: Vec<ComparisonUnit> = cu1.iter().flat_map(group_contents).collect();
let mut right: Vec<ComparisonUnit> = cu2.iter().flat_map(group_contents).collect();
rehash_words_by_text_content(dom, &mut left);
rehash_words_by_text_content(dom, &mut right);
let mut residual_settings = settings.clone();
residual_settings.detail_threshold = 0.005;
return Some(lcs(dom, left, right, &residual_settings));
}
{
let is_para_group = |u: &ComparisonUnit| {
as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Paragraph)
};
let ends_pil =
|v: &[ComparisonUnit]| v.last().is_some_and(|cu| unit_is_single_atom_ppr(dom, cu));
let has_text = |v: &[ComparisonUnit]| {
v.iter().any(|cu| {
cu.descendant_atoms().iter().any(|dca| {
dom.name_is(dca.content_element, &W::t())
&& !dom.value_str(dca.content_element).trim().is_empty()
})
})
};
let counts_differ = n1 != n2;
let both_tables = has_table(cu1) && has_table(cu2);
let parallel_sections = parallel_sectioned_demos(dom, cu1, cu2);
let short_prop_demos =
short_ooxml_property_demo(dom, cu1) && short_ooxml_property_demo(dom, cu2);
let last_sig_titles = titles_share_last_sig(dom, cu1, cu2) && n1 <= 50 && n2 <= 50;
let ooxml_tbl = ooxml_x_short_table_demo(dom, cu1, cu2);
if let (Some(first_a), Some(last_b)) = (cu1.first(), cu2.last())
&& counts_differ
&& !both_tables
&& !parallel_sections
&& !short_prop_demos
&& !last_sig_titles
&& !ooxml_tbl
&& is_para_group(first_a)
&& is_para_group(last_b)
{
let carrier_a = group_contents(first_a);
let carrier_b = group_contents(last_b);
if ends_pil(&carrier_a) && ends_pil(&carrier_b) && has_text(&carrier_b) {
let mut out = Vec::new();
if cu2.len() > 1 {
out.push(CorrelatedSequence::inserted(cu2[..cu2.len() - 1].to_vec()));
}
let b_words = carrier_b[..carrier_b.len() - 1].to_vec();
if !b_words.is_empty() {
out.push(CorrelatedSequence::inserted(b_words));
}
let a_words = carrier_a[..carrier_a.len() - 1].to_vec();
if !a_words.is_empty() {
out.push(CorrelatedSequence::deleted(a_words));
}
if cu1.len() > 1 {
out.push(CorrelatedSequence::deleted(vec![
carrier_a.last().unwrap().clone(),
]));
out.push(CorrelatedSequence::deleted(cu1[1..].to_vec()));
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Equal,
vec![carrier_a.last().unwrap().clone()],
vec![carrier_b.last().unwrap().clone()],
));
}
return Some(out);
}
}
}
if parallel_sectioned_demos(dom, cu1, cu2) {
return None;
}
if has_table(cu1)
&& has_table(cu2)
&& let (Some(i1), Some(i2)) = (
first_contentful_group_index(dom, cu1),
first_contentful_group_index(dom, cu2),
)
{
let a0 = para_text_token_list(dom, &cu1[i1]);
let b0 = para_text_token_list(dom, &cu2[i2]);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b));
if first_same && !a0.is_empty() && !b0.is_empty() {
let last_diff = match (last_significant_token(&a0), last_significant_token(&b0)) {
(Some(x), Some(y)) => !x.eq_ignore_ascii_case(y),
_ => true,
};
let sa: std::collections::HashSet<String> = a0.iter().cloned().collect();
let sb: std::collections::HashSet<String> = b0.iter().cloned().collect();
if last_diff && token_jaccard(&sa, &sb) + 1e-12 < 0.55 {
return None;
}
}
}
Some(vec![
CorrelatedSequence::inserted(cu2.to_vec()),
CorrelatedSequence::deleted(cu1.to_vec()),
])
}
fn section_letter_labels(dom: &Dom, cu: &[ComparisonUnit]) -> std::collections::HashSet<char> {
let mut labels = std::collections::HashSet::new();
for u in cu {
if as_group(u).is_none() {
continue;
}
if !unit_has_text_token(dom, u) {
continue;
}
let mut lead = String::new();
for a in u.descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
lead.push_str(&dom.value_str(a.content_element));
if lead.len() >= 8 {
break;
}
}
}
let t = lead.trim_start();
let b = t.as_bytes();
if b.len() >= 2 && b[0].is_ascii_uppercase() && b[1] == b')' {
labels.insert(b[0] as char);
}
}
labels
}
fn parallel_sectioned_demos(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
let l1 = section_letter_labels(dom, cu1);
let l2 = section_letter_labels(dom, cu2);
if l1.len() < 3 || l2.len() < 3 {
return false;
}
l1.intersection(&l2).count() >= 3
}
fn short_table_title_demo(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
if !has_table_units(cu) {
return false;
}
let contentful = cu
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.count();
if contentful == 0 || contentful > 8 {
return false;
}
let Some(i) = first_contentful_group_index(dom, cu) else {
return false;
};
let mut text = String::new();
for a in cu[i].descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
let lower = text.to_ascii_lowercase();
lower.contains("table") || lower.contains("rtl")
}
fn ooxml_x_short_table_demo(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
(short_ooxml_property_demo(dom, cu1) && short_table_title_demo(dom, cu2))
|| (short_ooxml_property_demo(dom, cu2) && short_table_title_demo(dom, cu1))
}
fn ooxml_x_short_prose_demo(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
let (ooxml_cu, prose_cu, prose_n) =
if short_ooxml_property_demo(dom, cu1) && !short_ooxml_property_demo(dom, cu2) {
(cu1, cu2, n2)
} else if short_ooxml_property_demo(dom, cu2) && !short_ooxml_property_demo(dom, cu1) {
(cu2, cu1, n1)
} else {
return false;
};
let _ = ooxml_cu;
if has_table_units(prose_cu) || !(1..=4).contains(&prose_n) {
return false;
}
let contentful: Vec<_> = prose_cu
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
if !(1..=2).contains(&contentful.len()) {
return false;
}
let title = para_text_token_list(dom, contentful[0])
.into_iter()
.map(|t| t.to_ascii_lowercase())
.collect::<Vec<_>>();
let joined = title.join(" ");
if title.iter().any(|t| t == "demo" || t == "tester")
|| joined.contains("demonstrates")
|| joined.contains("document shows")
{
return false;
}
true
}
fn short_cell_table_x_long_table_doc(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
if !has_table_units(cu1) || !has_table_units(cu2) {
return false;
}
let (short_n, long_n, short_cu) = if n1 <= n2 {
(n1, n2, cu1)
} else {
(n2, n1, cu2)
};
if !(1..=4).contains(&short_n) || !(15..=80).contains(&long_n) {
return false;
}
let mut non_tbl_content = 0usize;
let mut saw_tbl = false;
for u in short_cu {
let Some(g) = as_group(u) else { continue };
let toks = para_text_token_list(dom, u);
if g.group_type == ComparisonUnitGroupType::Table {
saw_tbl = true;
continue;
}
if toks.is_empty() {
continue;
}
non_tbl_content += 1;
if toks.len() > 2 {
return false;
}
let first = toks[0].to_ascii_lowercase();
if first.starts_with("sd") || first.contains("demo") || first == "table" {
return false;
}
}
if !saw_tbl || non_tbl_content > 1 {
return false;
}
let short_toks = para_text_tokens_from_units(dom, short_cu);
if short_toks.len() < 4 || short_toks.len() > 40 {
return false;
}
if short_toks.iter().any(|t| t.chars().count() > 24) {
return false;
}
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cu1),
¶_text_tokens_from_units(dom, cu2),
);
body_j + 1e-12 < 0.12
}
fn both_tables_unrelated_free_mesh(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
if n1 < 10 || n2 < 10 || n1 > 40 || n2 > 40 || n1 == n2 {
return false;
}
if !has_table_units(cu1) || !has_table_units(cu2) {
return false;
}
let n_tbl = |cu: &[ComparisonUnit]| -> usize {
cu.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table))
.count()
};
if n_tbl(cu1).max(n_tbl(cu2)) < 4 {
return false;
}
let (Some(i1), Some(i2)) = (
first_contentful_group_index(dom, cu1),
first_contentful_group_index(dom, cu2),
) else {
return false;
};
let a0 = para_text_token_list(dom, &cu1[i1]);
let b0 = para_text_token_list(dom, &cu2[i2]);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b));
if first_same {
return false;
}
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cu1),
¶_text_tokens_from_units(dom, cu2),
);
body_j + 1e-12 < 0.08
}
fn long_multitable_x_short_table_free_mesh(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
let (long_n, short_n, long_cu, short_cu) = if n1 >= n2 {
(n1, n2, cu1, cu2)
} else {
(n2, n1, cu2, cu1)
};
if !(30..=300).contains(&long_n) || !(2..=60).contains(&short_n) {
return false;
}
if !has_table_units(long_cu) || !has_table_units(short_cu) {
return false;
}
let n_tbl = |cu: &[ComparisonUnit]| -> usize {
cu.iter()
.filter(|u| as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table))
.count()
};
if n_tbl(long_cu) < 4 || n_tbl(short_cu) < 1 {
return false;
}
let (Some(i1), Some(i2)) = (
first_contentful_group_index(dom, cu1),
first_contentful_group_index(dom, cu2),
) else {
return false;
};
let a0 = para_text_token_list(dom, &cu1[i1]);
let b0 = para_text_token_list(dom, &cu2[i2]);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b));
if first_same {
return false;
}
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cu1),
¶_text_tokens_from_units(dom, cu2),
);
body_j + 1e-12 < 0.10
}
fn short_ooxml_property_demo(dom: &Dom, cu: &[ComparisonUnit]) -> bool {
if cu.len() > 50 {
return false;
}
let Some(i) = first_contentful_group_index(dom, cu) else {
return false;
};
let mut text = String::new();
for a in cu[i].descendant_atoms() {
if dom.name_is(a.content_element, &W::t()) {
text.push_str(&dom.value_str(a.content_element));
}
}
let lower = text.to_ascii_lowercase();
lower.contains("ooxml")
|| lower.contains("tester")
|| lower.contains("st_onoff")
|| lower.contains("w:b")
|| lower.contains("w:i")
|| lower.contains("w:sz")
|| lower.contains("w:color")
|| lower.contains("w:strike")
|| lower.contains("w:highlight")
|| lower.contains("w:rfonts")
|| lower.contains("rfonts")
|| lower.contains("half-point")
}
fn short_demos_share_first_title_token(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
if !(3..=15).contains(&n1) || !(3..=15).contains(&n2) || n1 == n2 {
return false;
}
if has_table_units(cu1) || has_table_units(cu2) {
return false;
}
let (Some(i1), Some(i2)) = (
first_contentful_group_index(dom, cu1),
first_contentful_group_index(dom, cu2),
) else {
return false;
};
let a0 = para_text_token_list(dom, &cu1[i1]);
let b0 = para_text_token_list(dom, &cu2[i2]);
let first_same = a0
.first()
.zip(b0.first())
.is_some_and(|(a, b)| a.eq_ignore_ascii_case(b) && a.chars().count() >= 3);
if !first_same {
return false;
}
let first = a0[0].to_ascii_lowercase();
const GENERIC_STYLE: &[&str] = &[
"font", "track", "green", "right", "left", "center", "title", "project", "one", "this",
];
if GENERIC_STYLE.contains(&first.as_str()) {
return false;
}
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cu1),
¶_text_tokens_from_units(dom, cu2),
);
body_j + 1e-12 < 0.45
}
fn short_demo_list_x_prose(
dom: &Dom,
cu1: &[ComparisonUnit],
cu2: &[ComparisonUnit],
n1: usize,
n2: usize,
) -> bool {
if !(2..=6).contains(&n1) || !(2..=6).contains(&n2) {
return false;
}
if has_table_units(cu1) || has_table_units(cu2) {
return false;
}
let ends_demo = |cu: &[ComparisonUnit]| -> bool {
let Some(i) = first_contentful_group_index(dom, cu) else {
return false;
};
let toks = para_text_token_list(dom, &cu[i]);
last_significant_token(&toks).is_some_and(|t| t.eq_ignore_ascii_case("demo"))
};
if !ends_demo(cu1) || !ends_demo(cu2) {
return false;
}
let listish = |cu: &[ComparisonUnit]| -> bool {
let xs: Vec<&ComparisonUnit> = cu
.iter()
.filter(|u| as_group(u).is_some() && unit_has_text_token(dom, u))
.collect();
if xs.len() < 2 {
return false;
}
let with_num = xs.iter().filter(|u| unit_para_has_numpr(dom, u)).count();
if with_num * 2 >= xs.len() {
return true;
}
let text_list = xs
.iter()
.filter(|u| {
let t = para_text_token_list(dom, u);
let Some(first) = t.first() else {
return false;
};
let f = first.to_ascii_lowercase();
(f == "first" || f == "second" || f == "third" || f == "fourth")
&& t.iter().any(|w| w.eq_ignore_ascii_case("item"))
})
.count();
text_list >= 2 && text_list * 2 >= xs.len().saturating_sub(2)
};
let l1 = listish(cu1);
let l2 = listish(cu2);
if l1 == l2 {
return false;
}
let body_j = token_jaccard(
¶_text_tokens_from_units(dom, cu1),
¶_text_tokens_from_units(dom, cu2),
);
body_j + 1e-12 < 0.25
}
fn has_table_units(cu: &[ComparisonUnit]) -> bool {
cu.iter()
.any(|u| as_group(u).is_some_and(|g| g.group_type == ComparisonUnitGroupType::Table))
}
fn titles_share_last_sig(dom: &Dom, cu1: &[ComparisonUnit], cu2: &[ComparisonUnit]) -> bool {
let (Some(i1), Some(i2)) = (
first_contentful_group_index(dom, cu1),
first_contentful_group_index(dom, cu2),
) else {
return false;
};
let a0 = para_text_token_list(dom, &cu1[i1]);
let b0 = para_text_token_list(dom, &cu2[i2]);
match (last_significant_token(&a0), last_significant_token(&b0)) {
(Some(x), Some(y)) if x.eq_ignore_ascii_case(y) && x.chars().count() >= 4 => {
let xl = x.to_ascii_lowercase();
matches!(xl.as_str(), "document" | "tester" | "test")
}
_ => false,
}
}
pub fn set_after_unids(dom: &mut Dom, unknown: &CorrelatedSequence) {
let a1 = match &unknown.com_units_1 {
Some(v) if v.len() == 1 => v,
_ => return,
};
let a2 = match &unknown.com_units_2 {
Some(v) if v.len() == 1 => v,
_ => return,
};
let (Some(g1), Some(g2)) = (as_group(&a1[0]), as_group(&a2[0])) else {
return;
};
if g1.group_type != g2.group_type {
return;
}
let take_thru = match g1.group_type {
ComparisonUnitGroupType::Paragraph => W::p(),
ComparisonUnitGroupType::Table => W::tbl(),
ComparisonUnitGroupType::Row => W::name("tr"),
ComparisonUnitGroupType::Cell => W::name("tc"),
ComparisonUnitGroupType::Textbox => W::name("txbxContent"),
};
let da1 = a1[0].descendant_atoms();
let da2 = a2[0].descendant_atoms();
let Some(first1) = da1.first() else { return };
let mut relevant = Vec::new();
for &ae in first1.ancestor_elements.iter() {
relevant.push(ae);
if dom.name_is(ae, &take_thru.clone()) {
break;
}
}
let unid_list: Vec<String> = relevant
.iter()
.filter_map(|&a| dom.attribute(a, &PT::unid()).map(|s| s.to_string()))
.collect();
let footnotes = W::name("footnotes");
let endnotes = W::name("endnotes");
let mut to_set: Vec<(crate::xmllinq::NodeId, String)> = Vec::new();
for atom in &da2 {
for (&anc, unid) in atom.ancestor_elements.iter().zip(unid_list.iter()) {
let nm = dom.name(anc);
if nm == Some(footnotes.clone()) || nm == Some(endnotes.clone()) {
continue;
}
if dom.attribute(anc, &PT::unid()).is_none() {
continue; }
to_set.push((anc, unid.clone()));
}
}
for (anc, unid) in to_set {
dom.set_attribute_value(anc, &PT::unid(), Some(&unid));
}
}
#[derive(Clone, Copy)]
struct CorrelatedHashRun {
left_start: usize,
right_start: usize,
len: usize,
}
fn correlated_hash_run_threshold(
cul1: &[ComparisonUnit],
cul2: &[ComparisonUnit],
bi1: usize,
bi2: usize,
best_len: usize,
) -> bool {
match best_len {
1 => {
cul1[bi1].descendant_content_atoms_count() > 16
&& cul2[bi2].descendant_content_atoms_count() > 16
}
2 | 3 => {
let s1: usize = cul1[bi1..bi1 + best_len]
.iter()
.map(|z| z.descendant_content_atoms_count())
.sum();
let s2: usize = cul2[bi2..bi2 + best_len]
.iter()
.map(|z| z.descendant_content_atoms_count())
.sum();
s1 > 32 && s2 > 32
}
n if n > 3 => true,
_ => false,
}
}
#[cfg(test)]
fn correlated_hash_run_scan(unknown: &CorrelatedSequence) -> Option<CorrelatedHashRun> {
use ComparisonUnitGroupType::*;
let cul1 = unknown.com_units_1.as_deref().unwrap_or(&[]);
let cul2 = unknown.com_units_2.as_deref().unwrap_or(&[]);
if cul1.len().min(cul2.len()) < 3 {
return None;
}
let first_ok = |u: &ComparisonUnit| {
as_group(u).is_some_and(|g| matches!(g.group_type, Paragraph | Table | Row))
};
if !cul1.first().is_some_and(first_ok) || !cul2.first().is_some_and(first_ok) {
return None;
}
let (mut best_len, mut best_atoms, mut bi1, mut bi2) = (0usize, 0usize, usize::MAX, usize::MAX);
for i1 in 0..cul1.len() {
for i2 in 0..cul2.len() {
let (mut len, mut atoms, mut t1, mut t2) = (0usize, 0usize, i1, i2);
loop {
let m = match (
cul1.get(t1).and_then(as_group),
cul2.get(t2).and_then(as_group),
) {
(Some(g1), Some(g2)) => {
g1.group_type == g2.group_type
&& g1.correlated_sha1_hash.is_some()
&& g1.correlated_sha1_hash == g2.correlated_sha1_hash
}
_ => false,
};
if m {
atoms += cul1[t1].descendant_content_atoms_count();
t1 += 1;
t2 += 1;
len += 1;
if t1 == cul1.len() || t2 == cul2.len() {
if atoms > best_atoms {
(best_len, best_atoms, bi1, bi2) = (len, atoms, i1, i2);
}
break;
}
} else {
if atoms > best_atoms {
(best_len, best_atoms, bi1, bi2) = (len, atoms, i1, i2);
}
break;
}
}
}
}
if !correlated_hash_run_threshold(cul1, cul2, bi1, bi2, best_len) {
return None;
}
Some(CorrelatedHashRun {
left_start: bi1,
right_start: bi2,
len: best_len,
})
}
fn correlated_hash_run_indexed(unknown: &CorrelatedSequence) -> Option<CorrelatedHashRun> {
use ComparisonUnitGroupType::*;
use std::collections::HashMap;
let cul1 = unknown.com_units_1.as_deref().unwrap_or(&[]);
let cul2 = unknown.com_units_2.as_deref().unwrap_or(&[]);
if cul1.len().min(cul2.len()) < 3 {
return None;
}
let first_ok = |u: &ComparisonUnit| {
as_group(u).is_some_and(|g| matches!(g.group_type, Paragraph | Table | Row))
};
if !cul1.first().is_some_and(first_ok) || !cul2.first().is_some_and(first_ok) {
return None;
}
let mut index: HashMap<(ComparisonUnitGroupType, &str), Vec<usize>> =
HashMap::with_capacity(cul2.len());
for (i2, u) in cul2.iter().enumerate() {
if let Some(g) = as_group(u)
&& let Some(h) = g.correlated_sha1_hash.as_deref()
{
index.entry((g.group_type, h)).or_default().push(i2);
}
}
let (mut best_len, mut best_atoms, mut bi1, mut bi2) = (0usize, 0usize, usize::MAX, usize::MAX);
for i1 in 0..cul1.len() {
let Some(g1) = as_group(&cul1[i1]) else {
continue;
};
let Some(h1) = g1.correlated_sha1_hash.as_deref() else {
continue;
};
let Some(starts) = index.get(&(g1.group_type, h1)) else {
continue;
};
for &i2 in starts {
let (mut len, mut atoms, mut t1, mut t2) = (0usize, 0usize, i1, i2);
loop {
let m = match (
cul1.get(t1).and_then(as_group),
cul2.get(t2).and_then(as_group),
) {
(Some(ga), Some(gb)) => {
ga.group_type == gb.group_type
&& ga.correlated_sha1_hash.is_some()
&& ga.correlated_sha1_hash == gb.correlated_sha1_hash
}
_ => false,
};
if m {
atoms += cul1[t1].descendant_content_atoms_count();
t1 += 1;
t2 += 1;
len += 1;
if t1 == cul1.len() || t2 == cul2.len() {
if atoms > best_atoms {
(best_len, best_atoms, bi1, bi2) = (len, atoms, i1, i2);
}
break;
}
} else {
if atoms > best_atoms {
(best_len, best_atoms, bi1, bi2) = (len, atoms, i1, i2);
}
break;
}
}
}
}
if !correlated_hash_run_threshold(cul1, cul2, bi1, bi2, best_len) {
return None;
}
Some(CorrelatedHashRun {
left_start: bi1,
right_start: bi2,
len: best_len,
})
}
fn correlated_hash_run(unknown: &CorrelatedSequence) -> Option<CorrelatedHashRun> {
crate::perf::inc_corr_run_scans();
let run = correlated_hash_run_indexed(unknown);
if run.is_some() {
crate::perf::inc_corr_run_hits();
}
run
}
pub fn process_correlated_hashes(unknown: &CorrelatedSequence) -> Option<Vec<CorrelatedSequence>> {
let run = correlated_hash_run(unknown)?;
let cul1 = unknown.com_units_1.as_deref().unwrap_or(&[]);
let cul2 = unknown.com_units_2.as_deref().unwrap_or(&[]);
let mut out = Vec::new();
cascade(
cul1[..run.left_start].to_vec(),
cul2[..run.right_start].to_vec(),
&mut out,
);
for i in 0..run.len {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![cul1[run.left_start + i].clone()],
vec![cul2[run.right_start + i].clone()],
));
}
cascade(
cul1[run.left_start + run.len..].to_vec(),
cul2[run.right_start + run.len..].to_vec(),
&mut out,
);
Some(out)
}
fn process_correlated_hashes_owned(
mut unknown: CorrelatedSequence,
) -> Result<Vec<CorrelatedSequence>, CorrelatedSequence> {
let Some(run) = correlated_hash_run(&unknown) else {
return Err(unknown);
};
let mut cul1 = unknown.com_units_1.take().unwrap_or_default();
let mut cul2 = unknown.com_units_2.take().unwrap_or_default();
let after1 = cul1.split_off(run.left_start + run.len);
let matched1 = cul1.split_off(run.left_start);
let after2 = cul2.split_off(run.right_start + run.len);
let matched2 = cul2.split_off(run.right_start);
let mut out = Vec::with_capacity(run.len + 2);
cascade(cul1, cul2, &mut out);
for (left, right) in matched1.into_iter().zip(matched2) {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
vec![left],
vec![right],
));
}
cascade(after1, after2, &mut out);
Ok(out)
}
fn first_direct_atom(u: &ComparisonUnit) -> Option<&ComparisonUnitAtom> {
match u {
ComparisonUnit::Word(w) => w.contents.first(),
ComparisonUnit::Group(_) => None,
}
}
fn unit_first_direct_atom_is_ppr(dom: &Dom, u: &ComparisonUnit) -> bool {
first_direct_atom(u).is_some_and(|a| atom_is_ppr(dom, a))
}
pub fn find_common_at_beginning_and_end(
dom: &Dom,
unknown: &CorrelatedSequence,
settings: &WmlComparerSettings,
) -> Option<Vec<CorrelatedSequence>> {
let cul1 = unknown.com_units_1.as_deref().unwrap_or(&[]);
let cul2 = unknown.com_units_2.as_deref().unwrap_or(&[]);
let n1 = cul1.len();
let n2 = cul2.len();
let length_to_compare = n1.min(n2);
let mut ccb = 0;
while ccb < length_to_compare && cul1[ccb].sha1() == cul2[ccb].sha1() {
ccb += 1;
}
if ccb != 0 && (ccb as f64) / (length_to_compare as f64) < settings.detail_threshold {
ccb = 0;
}
if ccb != 0 {
let mut out = Vec::new();
out.push(CorrelatedSequence::paired(
CorrelationStatus::Equal,
cul1[..ccb].to_vec(),
cul2[..ccb].to_vec(),
));
let (rem_l, rem_r) = (n1 - ccb, n2 - ccb);
if rem_l != 0 && rem_r == 0 {
out.push(CorrelatedSequence::deleted(cul1[ccb..].to_vec()));
} else if rem_l == 0 && rem_r != 0 {
out.push(CorrelatedSequence::inserted(cul2[ccb..].to_vec()));
} else if rem_l != 0 && rem_r != 0 {
let both_words = matches!(cul1[0], ComparisonUnit::Word(_))
&& matches!(cul2[0], ComparisonUnit::Word(_));
let mut handled = false;
if both_words {
let bl = cul1[ccb - 1].descendant_atoms().first().copied();
let br = cul2[ccb - 1].descendant_atoms().first().copied();
if let (Some(bl), Some(br)) = (bl, br)
&& !atom_is_ppr(dom, bl)
&& !atom_is_ppr(dom, br)
{
let s1 = split_at_paragraph_mark(dom, &cul1[ccb..]);
let s2 = split_at_paragraph_mark(dom, &cul2[ccb..]);
if s1.len() == 1 && s2.len() == 1 {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
s1[0].clone(),
s2[0].clone(),
));
handled = true;
} else if s1.len() == 2 && s2.len() == 2 {
let tail_pmark_only = |part: &[ComparisonUnit]| {
!part.is_empty() && part.iter().all(|u| unit_is_single_atom_ppr(dom, u))
};
let t1 = tail_pmark_only(&s1[1]);
let t2 = tail_pmark_only(&s2[1]);
if t1 != t2 {
} else {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
s1[0].clone(),
s2[0].clone(),
));
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
s1[1].clone(),
s2[1].clone(),
));
handled = true;
}
}
}
}
if !handled {
out.push(CorrelatedSequence::paired(
CorrelationStatus::Unknown,
cul1[ccb..].to_vec(),
cul2[ccb..].to_vec(),
));
}
}
return Some(out);
}
let mut cce = 0;
while cce < length_to_compare && cul1[n1 - 1 - cce].sha1() == cul2[n2 - 1 - cce].sha1() {
cce += 1;
}
while cce > 1 {
let unit = &cul1[n1 - cce]; if !unit_is_single_atom_ppr(dom, unit) {
break;
}
cce -= 1;
}
let is_only_paragraph_mark =
(cce == 1 || cce == 2) && unit_is_single_atom_ppr(dom, &cul1[n1 - 1]);
if !is_only_paragraph_mark
&& cce != 0
&& (cce as f64) / (length_to_compare as f64) < settings.detail_threshold
{
cce = 0;
}
if is_only_paragraph_mark {
cce = 0; }
if cce == 0 {
return None;
}
let (mut rem_lp, mut rem_rp) = (0usize, 0usize);
let common_end_seq = &cul1[n1 - cce..]; if matches!(common_end_seq.first(), Some(ComparisonUnit::Word(_)))
&& common_end_seq
.iter()
.any(|cu| unit_first_direct_atom_is_ppr(dom, cu))
{
rem_lp = take_while_count_rev(&cul1[..n1 - cce], |cu| word_first_not_ppr(dom, cu));
rem_rp = take_while_count_rev(&cul2[..n2 - cce], |cu| word_first_not_ppr(dom, cu));
}
let mut out = Vec::new();
let before_l = n1 - rem_lp - cce;
let before_r = n2 - rem_rp - cce;
cascade(
cul1[..before_l].to_vec(),
cul2[..before_r].to_vec(),
&mut out,
);
cascade(
cul1[before_l..before_l + rem_lp].to_vec(),
cul2[before_r..before_r + rem_rp].to_vec(),
&mut out,
);
out.push(CorrelatedSequence::paired(
CorrelationStatus::Equal,
cul1[n1 - cce..].to_vec(),
cul2[n2 - cce..].to_vec(),
));
Some(out)
}
pub fn resolve_correlated_sequences(
dom: &mut Dom,
mut cs_list: Vec<CorrelatedSequence>,
settings: &WmlComparerSettings,
) -> Vec<CorrelatedSequence> {
loop {
let Some(idx) = cs_list
.iter()
.position(|cs| cs.correlation_status == CorrelationStatus::Unknown)
else {
return cs_list;
};
let unknown = cs_list.remove(idx);
set_after_unids(dom, &unknown);
let resolved = match process_correlated_hashes_owned(unknown) {
Ok(r) => r,
Err(unknown) => match find_common_at_beginning_and_end(dom, &unknown, settings) {
Some(r) => r,
None => do_lcs_algorithm(dom, unknown, settings),
},
};
cs_list.splice(idx..idx, resolved);
}
}
pub fn lcs(
dom: &mut Dom,
cu1: Vec<ComparisonUnit>,
cu2: Vec<ComparisonUnit>,
settings: &WmlComparerSettings,
) -> Vec<CorrelatedSequence> {
resolve_correlated_sequences(
dom,
vec![CorrelatedSequence::paired(
CorrelationStatus::Unknown,
cu1,
cu2,
)],
settings,
)
}
#[cfg(test)]
mod correlated_hash_owned_tests {
use super::*;
use crate::comparer::atoms::{ComparisonUnitGroup, ComparisonUnitWord};
use crate::util::sha1::sha1_fingerprint;
use crate::xmllinq::NodeId;
fn group(hash: &str, correlated: &str) -> ComparisonUnit {
let atom = ComparisonUnitAtom::new(NodeId(0), Vec::<NodeId>::new(), format!("atom-{hash}"));
ComparisonUnit::Group(ComparisonUnitGroup {
correlation_status: CorrelationStatus::Nil,
group_type: ComparisonUnitGroupType::Paragraph,
contents: vec![ComparisonUnit::Word(ComparisonUnitWord::new(vec![atom]))],
level: 0,
sha1_key: sha1_fingerprint(hash),
sha1_key128: crate::util::sha1::sha1_fingerprint128(hash),
sha1_hash: hash.to_string(),
correlated_sha1_hash: Some(correlated.to_string()),
structure_sha1_hash: None,
atom_count_memo: std::cell::Cell::new(usize::MAX),
})
}
fn correlated_unknown() -> CorrelatedSequence {
let left = vec![
group("left-prefix", "left-only"),
group("left-0", "match-0"),
group("left-1", "match-1"),
group("left-2", "match-2"),
group("left-3", "match-3"),
group("left-suffix", "left-tail"),
];
let right = vec![
group("right-prefix", "right-only"),
group("right-0", "match-0"),
group("right-1", "match-1"),
group("right-2", "match-2"),
group("right-3", "match-3"),
group("right-suffix", "right-tail"),
];
CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right)
}
fn signature(
sequences: &[CorrelatedSequence],
) -> Vec<(CorrelationStatus, Vec<String>, Vec<String>)> {
sequences
.iter()
.map(|sequence| {
let left = sequence
.com_units_1
.as_deref()
.unwrap_or_default()
.iter()
.map(|unit| unit.sha1().to_string())
.collect();
let right = sequence
.com_units_2
.as_deref()
.unwrap_or_default()
.iter()
.map(|unit| unit.sha1().to_string())
.collect();
(sequence.correlation_status, left, right)
})
.collect()
}
fn unit_string_buffers(sequences: &[CorrelatedSequence]) -> Vec<usize> {
let mut pointers: Vec<usize> = sequences
.iter()
.flat_map(|sequence| {
sequence
.com_units_1
.iter()
.chain(sequence.com_units_2.iter())
.flat_map(|units| units.iter())
})
.map(|unit| unit.sha1().as_ptr() as usize)
.collect();
pointers.sort_unstable();
pointers
}
#[test]
fn owned_correlated_hash_resolution_matches_reference_output() {
let unknown = correlated_unknown();
let expected = process_correlated_hashes(&unknown).expect("reference resolves");
let actual = process_correlated_hashes_owned(unknown).expect("owned path resolves");
assert_eq!(signature(&actual), signature(&expected));
}
#[test]
fn owned_correlated_hash_resolution_moves_unit_buffers() {
let unknown = correlated_unknown();
let original_buffers = unit_string_buffers(std::slice::from_ref(&unknown));
let actual = process_correlated_hashes_owned(unknown).expect("owned path resolves");
assert_eq!(unit_string_buffers(&actual), original_buffers);
}
}
#[cfg(test)]
mod correlated_hash_idx_tests {
use super::*;
use crate::comparer::atoms::{ComparisonUnitGroup, ComparisonUnitWord};
use crate::util::sha1::sha1_fingerprint;
use crate::xmllinq::NodeId;
fn group_atoms(
hash: &str,
correlated: Option<&str>,
group_type: ComparisonUnitGroupType,
atom_count: usize,
) -> ComparisonUnit {
let atoms: Vec<ComparisonUnitAtom> = (0..atom_count.max(1))
.map(|i| {
ComparisonUnitAtom::new(
NodeId(i as u32),
Vec::<NodeId>::new(),
format!("atom-{hash}-{i}"),
)
})
.collect();
let word = ComparisonUnit::Word(ComparisonUnitWord::new(atoms));
ComparisonUnit::Group(ComparisonUnitGroup {
correlation_status: CorrelationStatus::Nil,
group_type,
contents: vec![word],
level: 0,
sha1_key: sha1_fingerprint(hash),
sha1_key128: crate::util::sha1::sha1_fingerprint128(hash),
sha1_hash: hash.to_string(),
correlated_sha1_hash: correlated.map(|s| s.to_string()),
structure_sha1_hash: None,
atom_count_memo: std::cell::Cell::new(usize::MAX),
})
}
fn run_eq(a: Option<CorrelatedHashRun>, b: Option<CorrelatedHashRun>) {
assert_eq!(
a.map(|r| (r.left_start, r.right_start, r.len)),
b.map(|r| (r.left_start, r.right_start, r.len)),
);
}
#[test]
fn indexed_matches_scan_on_owned_fixture() {
let left = vec![
group_atoms("lp", Some("lo"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("l0", Some("m0"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("l1", Some("m1"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("l2", Some("m2"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("l3", Some("m3"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("ls", Some("lt"), ComparisonUnitGroupType::Paragraph, 1),
];
let right = vec![
group_atoms("rp", Some("ro"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("r0", Some("m0"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("r1", Some("m1"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("r2", Some("m2"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("r3", Some("m3"), ComparisonUnitGroupType::Paragraph, 1),
group_atoms("rs", Some("rt"), ComparisonUnitGroupType::Paragraph, 1),
];
let unknown = CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right);
run_eq(
correlated_hash_run_scan(&unknown),
correlated_hash_run_indexed(&unknown),
);
assert!(correlated_hash_run(&unknown).is_some());
}
#[test]
fn indexed_matches_scan_first_found_tiebreak() {
let mk = |tag: &str, corr: &str| {
group_atoms(tag, Some(corr), ComparisonUnitGroupType::Paragraph, 2)
};
let left = vec![
mk("lx", "x"),
mk("la0", "a0"),
mk("la1", "a1"),
mk("la2", "a2"),
mk("la3", "a3"),
mk("ly", "y"),
mk("lb0", "a0"),
mk("lb1", "a1"),
mk("lb2", "a2"),
mk("lb3", "a3"),
];
let right = vec![
mk("rz", "z"),
mk("ra0", "a0"),
mk("ra1", "a1"),
mk("ra2", "a2"),
mk("ra3", "a3"),
mk("rw", "w"),
mk("rb0", "a0"),
mk("rb1", "a1"),
mk("rb2", "a2"),
mk("rb3", "a3"),
];
let unknown = CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right);
let scan = correlated_hash_run_scan(&unknown).expect("scan");
let idx = correlated_hash_run_indexed(&unknown).expect("idx");
assert_eq!(
(scan.left_start, scan.right_start, scan.len),
(idx.left_start, idx.right_start, idx.len)
);
assert_eq!(scan.left_start, 1);
assert_eq!(scan.right_start, 1);
assert_eq!(scan.len, 4);
}
#[test]
fn indexed_matches_scan_threshold_decline_len1() {
let left = vec![
group_atoms("a", Some("m"), ComparisonUnitGroupType::Paragraph, 5),
group_atoms("b", Some("x"), ComparisonUnitGroupType::Paragraph, 5),
group_atoms("c", Some("y"), ComparisonUnitGroupType::Paragraph, 5),
];
let right = vec![
group_atoms("d", Some("m"), ComparisonUnitGroupType::Paragraph, 5),
group_atoms("e", Some("u"), ComparisonUnitGroupType::Paragraph, 5),
group_atoms("f", Some("v"), ComparisonUnitGroupType::Paragraph, 5),
];
let unknown = CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right);
run_eq(
correlated_hash_run_scan(&unknown),
correlated_hash_run_indexed(&unknown),
);
assert!(correlated_hash_run_scan(&unknown).is_none());
}
#[test]
fn indexed_matches_scan_random_trials() {
struct Lcg(u64);
impl Lcg {
fn below(&mut self, n: u32) -> u32 {
self.0 = self
.0
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
((self.0 >> 33) as u32) % n
}
}
let corrs = ["c0", "c1", "c2", "c3", "uniq"];
let mut rng = Lcg(0xC0FF_EE42_DEAD_BEEF);
for trial in 0..800 {
let n = 3 + rng.below(8) as usize;
let m = 3 + rng.below(8) as usize;
let mut left = Vec::with_capacity(n);
let mut right = Vec::with_capacity(m);
for i in 0..n {
let c = corrs[rng.below(corrs.len() as u32) as usize];
let atoms = 1 + rng.below(20) as usize;
left.push(group_atoms(
&format!("L{trial}-{i}"),
Some(c),
ComparisonUnitGroupType::Paragraph,
atoms,
));
}
for i in 0..m {
let c = corrs[rng.below(corrs.len() as u32) as usize];
let atoms = 1 + rng.below(20) as usize;
right.push(group_atoms(
&format!("R{trial}-{i}"),
Some(c),
ComparisonUnitGroupType::Paragraph,
atoms,
));
}
if rng.below(10) == 0
&& let ComparisonUnit::Group(g) = &mut left[0]
{
g.correlated_sha1_hash = None;
}
let unknown = CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right);
let scan = correlated_hash_run_scan(&unknown);
let idx = correlated_hash_run_indexed(&unknown);
assert_eq!(
scan.map(|r| (r.left_start, r.right_start, r.len)),
idx.map(|r| (r.left_start, r.right_start, r.len)),
"trial {trial}"
);
}
}
#[test]
fn production_process_matches_scan_oracle_signature() {
let left = vec![
group_atoms("p", Some("pre"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("0", Some("k0"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("1", Some("k1"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("2", Some("k2"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("3", Some("k3"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("s", Some("suf"), ComparisonUnitGroupType::Paragraph, 2),
];
let right = vec![
group_atoms("P", Some("PRE"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("0", Some("k0"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("1", Some("k1"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("2", Some("k2"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("3", Some("k3"), ComparisonUnitGroupType::Paragraph, 2),
group_atoms("S", Some("SUF"), ComparisonUnitGroupType::Paragraph, 2),
];
let unknown = CorrelatedSequence::paired(CorrelationStatus::Unknown, left, right);
let got = process_correlated_hashes(&unknown).expect("resolve");
let run = correlated_hash_run_scan(&unknown).expect("scan run");
assert_eq!(
correlated_hash_run(&unknown).map(|r| (r.left_start, r.right_start, r.len)),
Some((run.left_start, run.right_start, run.len))
);
assert!(!got.is_empty());
}
}
#[cfg(test)]
mod indexed_lcr_tests {
use super::*;
use crate::comparer::atoms::ComparisonUnitWord;
use crate::util::sha1::sha1_fingerprint;
fn mk_word(hash: &str) -> ComparisonUnit {
ComparisonUnit::Word(ComparisonUnitWord {
correlation_status: CorrelationStatus::Nil,
contents: Vec::new(),
sha1_key: sha1_fingerprint(hash),
sha1_key128: crate::util::sha1::sha1_fingerprint128(hash),
sha1_hash: hash.to_string(),
})
}
fn mk_word_key(hash: &str, key: u64) -> ComparisonUnit {
ComparisonUnit::Word(ComparisonUnitWord {
correlation_status: CorrelationStatus::Nil,
contents: Vec::new(),
sha1_key: key,
sha1_key128: crate::util::sha1::sha1_fingerprint128(hash),
sha1_hash: hash.to_string(),
})
}
fn mk_seq(hashes: &[&str]) -> Vec<ComparisonUnit> {
hashes.iter().map(|h| mk_word(h)).collect()
}
struct Lcg(u64);
impl Lcg {
fn below(&mut self, n: u32) -> u32 {
self.0 = self
.0
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
((self.0 >> 33) as u32) % n
}
}
#[test]
fn indexed_matches_scan_random() {
const ALPHABET: &[&str] = &["A", "B", "C", "D"];
let mut rng = Lcg(0x9E37_79B9_7F4A_7C15);
for trial in 0..5000 {
let n = rng.below(13) as usize;
let m = rng.below(13) as usize;
let a: Vec<ComparisonUnit> = (0..n)
.map(|_| mk_word(ALPHABET[rng.below(ALPHABET.len() as u32) as usize]))
.collect();
let b: Vec<ComparisonUnit> = (0..m)
.map(|_| mk_word(ALPHABET[rng.below(ALPHABET.len() as u32) as usize]))
.collect();
let expect = longest_common_run_scan(None, &a, &b, None);
let got = longest_common_run_indexed(None, &a, &b, None);
assert_eq!(
got,
expect,
"trial {trial}: indexed != scan\n a={:?}\n b={:?}",
a.iter().map(|u| u.sha1()).collect::<Vec<_>>(),
b.iter().map(|u| u.sha1()).collect::<Vec<_>>(),
);
}
}
#[test]
fn indexed_matches_scan_edge_cases() {
let cases: &[(Vec<ComparisonUnit>, Vec<ComparisonUnit>)] = &[
(mk_seq(&[]), mk_seq(&[])),
(mk_seq(&["A"]), mk_seq(&[])),
(mk_seq(&[]), mk_seq(&["A"])),
(mk_seq(&["A"]), mk_seq(&["A"])),
(mk_seq(&["A"]), mk_seq(&["B"])),
(mk_seq(&["A", "A", "A"]), mk_seq(&["A", "A"])),
(mk_seq(&["A", "B", "C"]), mk_seq(&["C", "B", "A"])),
(mk_seq(&["A", "B", "A", "B"]), mk_seq(&["A", "B", "A", "B"])),
];
for (a, b) in cases {
assert_eq!(
longest_common_run_indexed(None, a, b, None),
longest_common_run_scan(None, a, b, None),
);
}
}
#[test]
fn indexed_handles_key_collision() {
let k = 0xDEAD_BEEF_u64;
let a = vec![mk_word_key("X", k), mk_word_key("Z", k)];
let b = vec![mk_word_key("Y", k), mk_word_key("Z", k)];
let got = longest_common_run_indexed(None, &a, &b, None);
assert_eq!(got, longest_common_run_scan(None, &a, &b, None));
assert_eq!(got, (1, 1, 1), "collision must not fabricate an X==Y match");
}
}