linkmarks_core/
dedupe.rs

1//! Local deterministic dedupe by canonical URL.
2//!
3//! Algorithm:
4//! 1. Group by `canonical_url`.
5//! 2. Within each group, pick the canonical record (oldest
6//!    `created_at`, ties broken by lowest `id`).
7//! 3. Report all conflicts: same canonical URL but differing title /
8//!    tags / collection.
9//!
10//! Per SPEC.md §Feature 5, the CLI exposes `--dry-run` (default) and
11//! `--apply`. Apply is gated on an explicit token at the CLI layer.
12//! This crate provides the algorithm; the CLI provides the gate.
13
14use crate::model::Bookmark;
15use serde::{Deserialize, Serialize};
16use std::collections::BTreeMap;
17
18/// A single conflict record. Two bookmarks share `canonical_url` but
19/// disagree on a field.
20#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
21pub struct ConflictRecord {
22    /// The shared canonical URL.
23    pub canonical_url: String,
24    /// The chosen canonical record (oldest `created_at`, lowest id).
25    pub chosen_id: String,
26    /// The IDs of the conflicting records (excluding the chosen one).
27    pub conflicting_ids: Vec<String>,
28    /// Field names where the conflicting records disagree with the
29    /// chosen record.
30    pub differing_fields: Vec<String>,
31}
32
33/// Full dedupe report.
34#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
35pub struct DedupeReport {
36    /// Number of distinct canonical URLs after dedupe.
37    pub canonical_count: usize,
38    /// Number of records that were merged into a canonical record.
39    pub merged_count: usize,
40    /// Conflicts found (canonical URL with disagreement).
41    pub conflicts: Vec<ConflictRecord>,
42}
43
44/// Run the dedupe algorithm.
45///
46/// `bookmarks` is the input set (any order). The output report is
47/// deterministic: the same input produces the same report bytes across
48/// runs.
49///
50/// Returned `Vec<Bookmark>` is the canonical set (one record per
51/// canonical URL).
52pub fn dedupe(bookmarks: &[Bookmark]) -> (Vec<Bookmark>, DedupeReport) {
53    // Group by canonical URL using BTreeMap for stable iteration.
54    let mut groups: BTreeMap<String, Vec<&Bookmark>> = BTreeMap::new();
55    for b in bookmarks {
56        groups.entry(b.canonical_url.clone()).or_default().push(b);
57    }
58
59    let mut canonical: Vec<Bookmark> = Vec::with_capacity(groups.len());
60    let mut conflicts: Vec<ConflictRecord> = Vec::new();
61    let mut merged = 0usize;
62
63    for (canonical_url, group) in &groups {
64        // Pick canonical: oldest created_at, tie-break lowest id.
65        let chosen = group
66            .iter()
67            .min_by(|a, b| {
68                a.created_at
69                    .cmp(&b.created_at)
70                    .then_with(|| a.id.0.cmp(&b.id.0))
71            })
72            .expect("non-empty group");
73
74        // Detect conflicts.
75        let mut differing: Vec<String> = Vec::new();
76        let mut conflicting_ids: Vec<String> = Vec::new();
77        for b in group {
78            if b.id == chosen.id {
79                continue;
80            }
81            let mut differs = false;
82            if b.title != chosen.title {
83                if !differing.iter().any(|f| f == "title") {
84                    differing.push("title".to_string());
85                }
86                differs = true;
87            }
88            if b.tags != chosen.tags {
89                if !differing.iter().any(|f| f == "tags") {
90                    differing.push("tags".to_string());
91                }
92                differs = true;
93            }
94            if b.collection != chosen.collection {
95                if !differing.iter().any(|f| f == "collection") {
96                    differing.push("collection".to_string());
97                }
98                differs = true;
99            }
100            if differs {
101                conflicting_ids.push(b.id.0.clone());
102            }
103        }
104        if !conflicting_ids.is_empty() {
105            conflicts.push(ConflictRecord {
106                canonical_url: canonical_url.clone(),
107                chosen_id: chosen.id.0.clone(),
108                conflicting_ids,
109                differing_fields: differing,
110            });
111        }
112
113        merged += group.len() - 1;
114        canonical.push((*chosen).clone());
115    }
116
117    let report = DedupeReport {
118        canonical_count: canonical.len(),
119        merged_count: merged,
120        conflicts,
121    };
122
123    (canonical, report)
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129    use crate::model::{BookmarkId, SourceKind, SourceRef};
130    use chrono::{TimeZone, Utc};
131
132    fn mk(id: &str, canonical: &str, title: &str, created_secs: i64) -> Bookmark {
133        Bookmark {
134            id: BookmarkId(id.into()),
135            original_url: format!("https://example.com/{id}"),
136            canonical_url: canonical.into(),
137            title: title.into(),
138            description: None,
139            tags: vec![],
140            collection: None,
141            created_at: Utc.timestamp_opt(created_secs, 0).unwrap(),
142            updated_at: Utc.timestamp_opt(created_secs, 0).unwrap(),
143            source: SourceRef {
144                kind: SourceKind::Manual,
145                external_id: None,
146                imported_at: Utc.timestamp_opt(0, 0).unwrap(),
147                raw: None,
148            },
149            content_type: None,
150            archived: false,
151        }
152    }
153
154    #[test]
155    fn dedupes_by_canonical_url() {
156        let bs = vec![
157            mk("a", "https://example.com/x", "Title A", 100),
158            mk("b", "https://example.com/x", "Title A", 200),
159            mk("c", "https://example.com/y", "Title C", 150),
160        ];
161        let (canon, report) = dedupe(&bs);
162        assert_eq!(canon.len(), 2);
163        assert_eq!(report.merged_count, 1);
164        assert_eq!(report.canonical_count, 2);
165        assert!(report.conflicts.is_empty());
166    }
167
168    #[test]
169    fn picks_oldest_as_canonical() {
170        let bs = vec![
171            mk("a", "https://example.com/x", "Newer", 200),
172            mk("b", "https://example.com/x", "Older", 100),
173        ];
174        let (canon, _) = dedupe(&bs);
175        assert_eq!(canon.len(), 1);
176        assert_eq!(canon[0].id.0, "b");
177    }
178
179    #[test]
180    fn tie_break_by_id() {
181        let bs = vec![
182            mk("zzz", "https://example.com/x", "Same time", 100),
183            mk("aaa", "https://example.com/x", "Same time", 100),
184        ];
185        let (canon, _) = dedupe(&bs);
186        assert_eq!(canon[0].id.0, "aaa");
187    }
188
189    #[test]
190    fn reports_conflict_on_title_mismatch() {
191        let bs = vec![
192            mk("a", "https://example.com/x", "Title A", 100),
193            mk("b", "https://example.com/x", "Title B", 200),
194        ];
195        let (_, report) = dedupe(&bs);
196        assert_eq!(report.conflicts.len(), 1);
197        assert!(report.conflicts[0]
198            .differing_fields
199            .iter()
200            .any(|f| f == "title"));
201    }
202
203    #[test]
204    fn report_is_deterministic() {
205        let bs = vec![
206            mk("a", "https://example.com/x", "A", 100),
207            mk("b", "https://example.com/x", "B", 200),
208            mk("c", "https://example.com/y", "C", 150),
209        ];
210        let (_, r1) = dedupe(&bs);
211        let (_, r2) = dedupe(&bs);
212        let s1 = serde_json::to_string(&r1).unwrap();
213        let s2 = serde_json::to_string(&r2).unwrap();
214        assert_eq!(s1, s2);
215    }
216}
linkmarks_core/dedupe.rs

linkmarks_core/
dedupe.rs
