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
20use algo::Edit;
21
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
23#[serde(rename_all = "camelCase")]
24pub enum ChangeType {
25    Added,
26    Removed,
27    Modified,
28    Moved,
29}
30
31#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
32#[serde(rename_all = "camelCase")]
33pub enum Significance {
34    Noise,
35    Substantive,
36}
37
38#[derive(Debug, Clone, Serialize, Deserialize)]
39#[serde(rename_all = "camelCase", default)]
40pub struct DiffOptions {
41    /// 哪些类别的变化算噪声；不在其中的类别（如价格）按实质变化处理。
42    pub noise_categories: Vec<NoiseCategory>,
43    /// 纯移动是否算噪声。
44    pub moved_is_noise: bool,
45    /// 判定"同一块被修改"的词级相似度下限，0 到 1。
46    pub similarity_threshold: f64,
47}
48
49impl Default for DiffOptions {
50    fn default() -> Self {
51        Self {
52            noise_categories: vec![
53                NoiseCategory::Date,
54                NoiseCategory::RelativeTime,
55                NoiseCategory::Price,
56                NoiseCategory::Count,
57                NoiseCategory::Number,
58            ],
59            moved_is_noise: false,
60            similarity_threshold: 0.5,
61        }
62    }
63}
64
65#[derive(Debug, Clone, Serialize, Deserialize)]
66#[serde(rename_all = "camelCase")]
67pub struct BlockChange {
68    #[serde(rename = "type")]
69    pub change: ChangeType,
70    pub block_type: BlockKind,
71    pub significance: Significance,
72    #[serde(default, skip_serializing_if = "Vec::is_empty")]
73    pub noise_categories: Vec<NoiseCategory>,
74    #[serde(skip_serializing_if = "Option::is_none")]
75    pub old_index: Option<usize>,
76    #[serde(skip_serializing_if = "Option::is_none")]
77    pub new_index: Option<usize>,
78    #[serde(skip_serializing_if = "Option::is_none")]
79    pub old_text: Option<String>,
80    #[serde(skip_serializing_if = "Option::is_none")]
81    pub new_text: Option<String>,
82    #[serde(skip_serializing_if = "Option::is_none")]
83    pub old_hash: Option<String>,
84    #[serde(skip_serializing_if = "Option::is_none")]
85    pub new_hash: Option<String>,
86    #[serde(default, skip_serializing_if = "Vec::is_empty")]
87    pub inline: Vec<InlineSegment>,
88}
89
90#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
91#[serde(rename_all = "camelCase")]
92pub struct DiffStats {
93    pub old_blocks: usize,
94    pub new_blocks: usize,
95    pub unchanged: usize,
96    pub added: usize,
97    pub removed: usize,
98    pub modified: usize,
99    pub moved: usize,
100    pub noise: usize,
101    pub substantive: usize,
102}
103
104#[derive(Debug, Clone, Serialize, Deserialize)]
105#[serde(rename_all = "camelCase")]
106pub struct DiffReport {
107    pub changed: bool,
108    pub substantive: bool,
109    pub blocks: Vec<BlockChange>,
110    pub stats: DiffStats,
111}
112
113fn hex(h: &[u8; 32]) -> String {
114    const D: &[u8; 16] = b"0123456789abcdef";
115    let mut s = String::with_capacity(64);
116    for b in h {
117        s.push(D[(b >> 4) as usize] as char);
118        s.push(D[(b & 15) as usize] as char);
119    }
120    s
121}
122
123/// 块的词集合签名：非空白词的哈希，已排序，用于 Dice 相似度。
124fn signature(norm: &str) -> Vec<u64> {
125    use std::hash::{BuildHasher, BuildHasherDefault, DefaultHasher};
126    let hasher = BuildHasherDefault::<DefaultHasher>::default();
127    let mut v: Vec<u64> = inline::tokenize(norm)
128        .into_iter()
129        .filter(|t| !t.trim().is_empty())
130        .map(|t| hasher.hash_one(t))
131        .collect();
132    v.sort_unstable();
133    v
134}
135
136fn dice(a: &[u64], b: &[u64]) -> f64 {
137    if a.len() + b.len() == 0 {
138        return 1.0;
139    }
140    let (mut i, mut j, mut common) = (0, 0, 0usize);
141    while i < a.len() && j < b.len() {
142        match a[i].cmp(&b[j]) {
143            std::cmp::Ordering::Less => i += 1,
144            std::cmp::Ordering::Greater => j += 1,
145            std::cmp::Ordering::Equal => {
146                common += 1;
147                i += 1;
148                j += 1;
149            }
150        }
151    }
152    2.0 * common as f64 / (a.len() + b.len()) as f64
153}
154
155const PAIR_WINDOW: usize = 8;
156
157fn intern<'a>(bs: &'a [Block], ids: &mut HashMap<(BlockKind, &'a str), u32>) -> Vec<u32> {
158    bs.iter()
159        .map(|b| {
160            let n = ids.len() as u32;
161            *ids.entry((b.kind, b.norm.as_str())).or_insert(n)
162        })
163        .collect()
164}
165
166pub fn diff(old: &str, new: &str) -> DiffReport {
167    diff_with(old, new, &DiffOptions::default())
168}
169
170pub fn diff_with(old: &str, new: &str, opts: &DiffOptions) -> DiffReport {
171    let ob = split_blocks(old);
172    let nb = split_blocks(new);
173    let mut ids = HashMap::new();
174    let oi = intern(&ob, &mut ids);
175    let ni = intern(&nb, &mut ids);
176    let edits = algo::diff(&oi, &ni);
177
178    let mut stats = DiffStats {
179        old_blocks: ob.len(),
180        new_blocks: nb.len(),
181        ..Default::default()
182    };
183    let mut events: Vec<(usize, BlockChange)> = Vec::new();
184
185    // 先配对移动：同一哈希在别处被删除又被插入
186    let mut consumed = vec![false; edits.len()];
187    let mut deleted: HashMap<u32, VecDeque<(usize, usize)>> = HashMap::new();
188    for (p, e) in edits.iter().enumerate() {
189        if let Edit::Delete(i) = *e {
190            deleted.entry(oi[i]).or_default().push_back((p, i));
191        }
192    }
193    for (p, e) in edits.iter().enumerate() {
194        if let Edit::Insert(j) = *e
195            && let Some((dp, i)) = deleted.get_mut(&ni[j]).and_then(VecDeque::pop_front)
196        {
197            consumed[dp] = true;
198            consumed[p] = true;
199            events.push((
200                p,
201                BlockChange {
202                    change: ChangeType::Moved,
203                    block_type: nb[j].kind,
204                    significance: if opts.moved_is_noise {
205                        Significance::Noise
206                    } else {
207                        Significance::Substantive
208                    },
209                    noise_categories: vec![],
210                    old_index: Some(i),
211                    new_index: Some(j),
212                    old_text: Some(ob[i].text.clone()),
213                    new_text: Some(nb[j].text.clone()),
214                    old_hash: Some(hex(&ob[i].hash())),
215                    new_hash: Some(hex(&nb[j].hash())),
216                    inline: vec![],
217                },
218            ));
219        }
220    }
221
222    let added = |p: usize, j: usize| {
223        (
224            p,
225            BlockChange {
226                change: ChangeType::Added,
227                block_type: nb[j].kind,
228                significance: Significance::Substantive,
229                noise_categories: vec![],
230                old_index: None,
231                new_index: Some(j),
232                old_text: None,
233                new_text: Some(nb[j].text.clone()),
234                old_hash: None,
235                new_hash: None,
236                inline: vec![],
237            },
238        )
239    };
240    let removed = |p: usize, i: usize| {
241        (
242            p,
243            BlockChange {
244                change: ChangeType::Removed,
245                block_type: ob[i].kind,
246                significance: Significance::Substantive,
247                noise_categories: vec![],
248                old_index: Some(i),
249                new_index: None,
250                old_text: Some(ob[i].text.clone()),
251                new_text: None,
252                old_hash: None,
253                new_hash: None,
254                inline: vec![],
255            },
256        )
257    };
258
259    let osig: Vec<OnceCell<Vec<u64>>> = (0..ob.len()).map(|_| OnceCell::new()).collect();
260    let nsig: Vec<OnceCell<Vec<u64>>> = (0..nb.len()).map(|_| OnceCell::new()).collect();
261    let mut dels: Vec<(usize, usize)> = Vec::new();
262    let mut inss: Vec<(usize, usize)> = Vec::new();
263    let flush = |dels: &mut Vec<(usize, usize)>,
264                 inss: &mut Vec<(usize, usize)>,
265                 events: &mut Vec<(usize, BlockChange)>| {
266        let mut j = 0;
267        for &(dp, i) in dels.iter() {
268            let hi = (j + PAIR_WINDOW).min(inss.len());
269            // 顺序候选相似度够高就直接采用，省掉窗口内的其余比较
270            let mut best: Option<(usize, f64)> = None;
271            for k in j..hi {
272                if ob[i].kind != nb[inss[k].1].kind {
273                    continue;
274                }
275                let so = osig[i].get_or_init(|| signature(&ob[i].norm));
276                let sn = nsig[inss[k].1].get_or_init(|| signature(&nb[inss[k].1].norm));
277                let sim = dice(so, sn);
278                if sim >= opts.similarity_threshold && best.is_none_or(|(_, s)| sim > s) {
279                    best = Some((k, sim));
280                    if sim >= 0.8 {
281                        break;
282                    }
283                }
284            }
285            match best {
286                Some((k, _)) => {
287                    for &(ip, jj) in &inss[j..k] {
288                        events.push(added(ip, jj));
289                    }
290                    let (ip, jj) = inss[k];
291                    j = k + 1;
292                    let (o, n) = (&ob[i], &nb[jj]);
293                    let (significance, noise_categories) =
294                        match noise::classify(&o.norm, &n.norm, &opts.noise_categories) {
295                            Some(c) => (Significance::Noise, c),
296                            None => (Significance::Substantive, vec![]),
297                        };
298                    events.push((
299                        dp.min(ip),
300                        BlockChange {
301                            change: ChangeType::Modified,
302                            block_type: n.kind,
303                            significance,
304                            noise_categories,
305                            old_index: Some(i),
306                            new_index: Some(jj),
307                            old_text: Some(o.text.clone()),
308                            new_text: Some(n.text.clone()),
309                            old_hash: Some(hex(&o.hash())),
310                            new_hash: Some(hex(&n.hash())),
311                            inline: inline_diff(&o.norm, &n.norm),
312                        },
313                    ));
314                }
315                None => events.push(removed(dp, i)),
316            }
317        }
318        for &(ip, jj) in &inss[j..] {
319            events.push(added(ip, jj));
320        }
321        dels.clear();
322        inss.clear();
323    };
324
325    for (p, e) in edits.iter().enumerate() {
326        match *e {
327            Edit::Equal(..) => {
328                stats.unchanged += 1;
329                flush(&mut dels, &mut inss, &mut events);
330            }
331            _ if consumed[p] => {}
332            Edit::Delete(i) => dels.push((p, i)),
333            Edit::Insert(j) => inss.push((p, j)),
334        }
335    }
336    flush(&mut dels, &mut inss, &mut events);
337
338    events.sort_by_key(|e| e.0);
339    let blocks: Vec<BlockChange> = events.into_iter().map(|e| e.1).collect();
340    for b in &blocks {
341        match b.change {
342            ChangeType::Added => stats.added += 1,
343            ChangeType::Removed => stats.removed += 1,
344            ChangeType::Modified => stats.modified += 1,
345            ChangeType::Moved => stats.moved += 1,
346        }
347        match b.significance {
348            Significance::Noise => stats.noise += 1,
349            Significance::Substantive => stats.substantive += 1,
350        }
351    }
352    DiffReport {
353        changed: !blocks.is_empty(),
354        substantive: stats.substantive > 0,
355        blocks,
356        stats,
357    }
358}
pagesift_diff/lib.rs

pagesift_diff/
lib.rs
