1#![forbid(unsafe_code)]
2mod algo;
5mod block;
6mod inline;
7mod noise;
8mod unified;
9
10use std::cell::OnceCell;
11use std::collections::{HashMap, VecDeque};
12
13use serde::{Deserialize, Serialize};
14
15pub use block::{Block, BlockKind, normalize, split_blocks};
16pub use inline::{InlineOp, InlineSegment, inline_diff};
17pub use noise::NoiseCategory;
18pub use unified::{DiffLine, Hunk, LineKind, UnifiedDiff, unified_diff};
19
20pub fn align(a: &[u32], b: &[u32]) -> Vec<(usize, usize)> {
23 algo::diff(a, b)
24 .into_iter()
25 .filter_map(|e| match e {
26 Edit::Equal(i, j) => Some((i, j)),
27 _ => None,
28 })
29 .collect()
30}
31
32use algo::Edit;
33
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
35#[serde(rename_all = "camelCase")]
36pub enum ChangeType {
37 Added,
38 Removed,
39 Modified,
40 Moved,
41}
42
43#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
44#[serde(rename_all = "camelCase")]
45pub enum Significance {
46 Noise,
47 Substantive,
48}
49
50#[derive(Debug, Clone, Serialize, Deserialize)]
51#[serde(rename_all = "camelCase", default)]
52pub struct DiffOptions {
53 pub noise_categories: Vec<NoiseCategory>,
55 pub moved_is_noise: bool,
57 pub similarity_threshold: f64,
59}
60
61impl Default for DiffOptions {
62 fn default() -> Self {
63 Self {
64 noise_categories: vec![
65 NoiseCategory::Date,
66 NoiseCategory::RelativeTime,
67 NoiseCategory::Price,
68 NoiseCategory::Count,
69 NoiseCategory::Number,
70 ],
71 moved_is_noise: false,
72 similarity_threshold: 0.5,
73 }
74 }
75}
76
77#[derive(Debug, Clone, Serialize, Deserialize)]
78#[serde(rename_all = "camelCase")]
79pub struct BlockChange {
80 #[serde(rename = "type")]
81 pub change: ChangeType,
82 pub block_type: BlockKind,
83 pub significance: Significance,
84 #[serde(default, skip_serializing_if = "Vec::is_empty")]
85 pub noise_categories: Vec<NoiseCategory>,
86 #[serde(skip_serializing_if = "Option::is_none")]
87 pub old_index: Option<usize>,
88 #[serde(skip_serializing_if = "Option::is_none")]
89 pub new_index: Option<usize>,
90 #[serde(skip_serializing_if = "Option::is_none")]
91 pub old_text: Option<String>,
92 #[serde(skip_serializing_if = "Option::is_none")]
93 pub new_text: Option<String>,
94 #[serde(skip_serializing_if = "Option::is_none")]
95 pub old_hash: Option<String>,
96 #[serde(skip_serializing_if = "Option::is_none")]
97 pub new_hash: Option<String>,
98 #[serde(default, skip_serializing_if = "Vec::is_empty")]
99 pub inline: Vec<InlineSegment>,
100}
101
102#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
103#[serde(rename_all = "camelCase")]
104pub struct DiffStats {
105 pub old_blocks: usize,
106 pub new_blocks: usize,
107 pub unchanged: usize,
108 pub added: usize,
109 pub removed: usize,
110 pub modified: usize,
111 pub moved: usize,
112 pub noise: usize,
113 pub substantive: usize,
114}
115
116#[derive(Debug, Clone, Serialize, Deserialize)]
117#[serde(rename_all = "camelCase")]
118pub struct DiffReport {
119 pub changed: bool,
120 pub substantive: bool,
121 pub blocks: Vec<BlockChange>,
122 pub stats: DiffStats,
123}
124
125fn hex(h: &[u8; 32]) -> String {
126 const D: &[u8; 16] = b"0123456789abcdef";
127 let mut s = String::with_capacity(64);
128 for b in h {
129 s.push(D[(b >> 4) as usize] as char);
130 s.push(D[(b & 15) as usize] as char);
131 }
132 s
133}
134
135fn signature(norm: &str) -> Vec<u64> {
137 use std::hash::{BuildHasher, BuildHasherDefault, DefaultHasher};
138 let hasher = BuildHasherDefault::<DefaultHasher>::default();
139 let mut v: Vec<u64> = inline::tokenize(norm)
140 .into_iter()
141 .filter(|t| !t.trim().is_empty())
142 .map(|t| hasher.hash_one(t))
143 .collect();
144 v.sort_unstable();
145 v
146}
147
148fn dice(a: &[u64], b: &[u64]) -> f64 {
149 if a.len() + b.len() == 0 {
150 return 1.0;
151 }
152 let (mut i, mut j, mut common) = (0, 0, 0usize);
153 while i < a.len() && j < b.len() {
154 match a[i].cmp(&b[j]) {
155 std::cmp::Ordering::Less => i += 1,
156 std::cmp::Ordering::Greater => j += 1,
157 std::cmp::Ordering::Equal => {
158 common += 1;
159 i += 1;
160 j += 1;
161 }
162 }
163 }
164 2.0 * common as f64 / (a.len() + b.len()) as f64
165}
166
167const PAIR_WINDOW: usize = 8;
168
169fn intern<'a>(bs: &'a [Block], ids: &mut HashMap<(BlockKind, &'a str), u32>) -> Vec<u32> {
170 bs.iter()
171 .map(|b| {
172 let n = ids.len() as u32;
173 *ids.entry((b.kind, b.norm.as_str())).or_insert(n)
174 })
175 .collect()
176}
177
178pub fn diff(old: &str, new: &str) -> DiffReport {
179 diff_with(old, new, &DiffOptions::default())
180}
181
182pub fn diff_with(old: &str, new: &str, opts: &DiffOptions) -> DiffReport {
183 let ob = split_blocks(old);
184 let nb = split_blocks(new);
185 let mut ids = HashMap::new();
186 let oi = intern(&ob, &mut ids);
187 let ni = intern(&nb, &mut ids);
188 let edits = algo::diff(&oi, &ni);
189
190 let mut stats = DiffStats {
191 old_blocks: ob.len(),
192 new_blocks: nb.len(),
193 ..Default::default()
194 };
195 let mut events: Vec<(usize, BlockChange)> = Vec::new();
196
197 let mut consumed = vec![false; edits.len()];
199 let mut deleted: HashMap<u32, VecDeque<(usize, usize)>> = HashMap::new();
200 for (p, e) in edits.iter().enumerate() {
201 if let Edit::Delete(i) = *e {
202 deleted.entry(oi[i]).or_default().push_back((p, i));
203 }
204 }
205 for (p, e) in edits.iter().enumerate() {
206 if let Edit::Insert(j) = *e
207 && let Some((dp, i)) = deleted.get_mut(&ni[j]).and_then(VecDeque::pop_front)
208 {
209 consumed[dp] = true;
210 consumed[p] = true;
211 events.push((
212 p,
213 BlockChange {
214 change: ChangeType::Moved,
215 block_type: nb[j].kind,
216 significance: if opts.moved_is_noise {
217 Significance::Noise
218 } else {
219 Significance::Substantive
220 },
221 noise_categories: vec![],
222 old_index: Some(i),
223 new_index: Some(j),
224 old_text: Some(ob[i].text.clone()),
225 new_text: Some(nb[j].text.clone()),
226 old_hash: Some(hex(&ob[i].hash())),
227 new_hash: Some(hex(&nb[j].hash())),
228 inline: vec![],
229 },
230 ));
231 }
232 }
233
234 let ads_noise = opts
236 .noise_categories
237 .contains(&NoiseCategory::Advertisement);
238 let ad_block = |text: &str| ads_noise && noise::is_ad(text);
239 let sig = |text: &str| {
240 if ad_block(text) {
241 (Significance::Noise, vec![NoiseCategory::Advertisement])
242 } else {
243 (Significance::Substantive, vec![])
244 }
245 };
246 let added = |p: usize, j: usize| {
247 let (significance, noise_categories) = sig(&nb[j].text);
248 (
249 p,
250 BlockChange {
251 change: ChangeType::Added,
252 block_type: nb[j].kind,
253 significance,
254 noise_categories,
255 old_index: None,
256 new_index: Some(j),
257 old_text: None,
258 new_text: Some(nb[j].text.clone()),
259 old_hash: None,
260 new_hash: None,
261 inline: vec![],
262 },
263 )
264 };
265 let removed = |p: usize, i: usize| {
266 let (significance, noise_categories) = sig(&ob[i].text);
267 (
268 p,
269 BlockChange {
270 change: ChangeType::Removed,
271 block_type: ob[i].kind,
272 significance,
273 noise_categories,
274 old_index: Some(i),
275 new_index: None,
276 old_text: Some(ob[i].text.clone()),
277 new_text: None,
278 old_hash: None,
279 new_hash: None,
280 inline: vec![],
281 },
282 )
283 };
284
285 let osig: Vec<OnceCell<Vec<u64>>> = (0..ob.len()).map(|_| OnceCell::new()).collect();
286 let nsig: Vec<OnceCell<Vec<u64>>> = (0..nb.len()).map(|_| OnceCell::new()).collect();
287 let mut dels: Vec<(usize, usize)> = Vec::new();
288 let mut inss: Vec<(usize, usize)> = Vec::new();
289 let flush = |dels: &mut Vec<(usize, usize)>,
290 inss: &mut Vec<(usize, usize)>,
291 events: &mut Vec<(usize, BlockChange)>| {
292 let mut j = 0;
293 for &(dp, i) in dels.iter() {
294 let hi = (j + PAIR_WINDOW).min(inss.len());
295 let mut best: Option<(usize, f64)> = None;
297 for k in j..hi {
298 if ob[i].kind != nb[inss[k].1].kind {
299 continue;
300 }
301 let so = osig[i].get_or_init(|| signature(&ob[i].norm));
302 let sn = nsig[inss[k].1].get_or_init(|| signature(&nb[inss[k].1].norm));
303 let sim = dice(so, sn);
304 if sim >= opts.similarity_threshold && best.is_none_or(|(_, s)| sim > s) {
305 best = Some((k, sim));
306 if sim >= 0.8 {
307 break;
308 }
309 }
310 }
311 match best {
312 Some((k, _)) => {
313 for &(ip, jj) in &inss[j..k] {
314 events.push(added(ip, jj));
315 }
316 let (ip, jj) = inss[k];
317 j = k + 1;
318 let (o, n) = (&ob[i], &nb[jj]);
319 let (significance, noise_categories) =
320 match noise::classify(&o.norm, &n.norm, &opts.noise_categories) {
321 Some(c) => (Significance::Noise, c),
322 None => (Significance::Substantive, vec![]),
323 };
324 events.push((
325 dp.min(ip),
326 BlockChange {
327 change: ChangeType::Modified,
328 block_type: n.kind,
329 significance,
330 noise_categories,
331 old_index: Some(i),
332 new_index: Some(jj),
333 old_text: Some(o.text.clone()),
334 new_text: Some(n.text.clone()),
335 old_hash: Some(hex(&o.hash())),
336 new_hash: Some(hex(&n.hash())),
337 inline: inline_diff(&o.norm, &n.norm),
338 },
339 ));
340 }
341 None => events.push(removed(dp, i)),
342 }
343 }
344 for &(ip, jj) in &inss[j..] {
345 events.push(added(ip, jj));
346 }
347 dels.clear();
348 inss.clear();
349 };
350
351 for (p, e) in edits.iter().enumerate() {
352 match *e {
353 Edit::Equal(..) => {
354 stats.unchanged += 1;
355 flush(&mut dels, &mut inss, &mut events);
356 }
357 _ if consumed[p] => {}
358 Edit::Delete(i) => dels.push((p, i)),
359 Edit::Insert(j) => inss.push((p, j)),
360 }
361 }
362 flush(&mut dels, &mut inss, &mut events);
363
364 events.sort_by_key(|e| e.0);
365 let blocks: Vec<BlockChange> = events.into_iter().map(|e| e.1).collect();
366 for b in &blocks {
367 match b.change {
368 ChangeType::Added => stats.added += 1,
369 ChangeType::Removed => stats.removed += 1,
370 ChangeType::Modified => stats.modified += 1,
371 ChangeType::Moved => stats.moved += 1,
372 }
373 match b.significance {
374 Significance::Noise => stats.noise += 1,
375 Significance::Substantive => stats.substantive += 1,
376 }
377 }
378 DiffReport {
379 changed: !blocks.is_empty(),
380 substantive: stats.substantive > 0,
381 blocks,
382 stats,
383 }
384}