Skip to main content

pagesift_diff/
lib.rs

1#![forbid(unsafe_code)]
2//! 同一 URL 两份 Markdown 快照的块级差异对比,并区分噪声变化。
3
4mod 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
20/// 两个 id 序列的对齐(patience 取锚点、锚点间 Myers),返回相等位置对 `(i, j)`,按序递增。
21/// 给块级合并用:调用方把块映射成 id(相同内容同一个 id)。
22pub 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    /// 哪些类别的变化算噪声;不在其中的类别(如价格)按实质变化处理。
54    pub noise_categories: Vec<NoiseCategory>,
55    /// 纯移动是否算噪声。
56    pub moved_is_noise: bool,
57    /// 判定"同一块被修改"的词级相似度下限,0 到 1。
58    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
135/// 块的词集合签名:非空白词的哈希,已排序,用于 Dice 相似度。
136fn 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    // 先配对移动:同一哈希在别处被删除又被插入
198    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    // 广告位整块出现、消失、换成别的广告:按噪声算(启用了 Advertisement 时)
235    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            // 顺序候选相似度够高就直接采用,省掉窗口内的其余比较
296            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}