Skip to main content

second_brain_core/
near_duplicates.rs

1//! Near-duplicate distillates: consolidation often distills one fact from
2//! several conversations, and the paraphrases crowd each other out of
3//! recall's top-k. The daemon finds the groups and applies a merge written
4//! elsewhere (it has no LLM); a pair the writer judged distinct or
5//! contradictory is recorded as reviewed so it is not offered again.
6
7use std::collections::{HashMap, HashSet};
8
9use anyhow::Result;
10use chrono::{DateTime, Utc};
11use rusqlite::{OptionalExtension, params};
12use serde::Serialize;
13use uuid::Uuid;
14
15use crate::index::{EMBEDDING_DIM, Indexes};
16use crate::retrieval::cosine;
17use crate::schema::{Memory, MemoryType, Relation, RelationType, Tier};
18use crate::session_dates::latest_session;
19use crate::sqlite_store::{MEMORY_COLS, SqliteStore, parse_uuid, row_to_memory};
20use crate::store::Store;
21
22/// Context of a separate or conflict review. A pair linked by a relation
23/// whose context is this, or starts with `REVIEW_CONTEXT:`, is not grouped
24/// again until the review is reopened.
25pub const REVIEW_CONTEXT: &str = "near-duplicate-review";
26/// A pair the model judged the same but could not merge without losing a
27/// fact; kept apart from `separate` so it can be reopened on its own.
28pub const UNMERGED_CONTEXT: &str = "near-duplicate-review:unmerged";
29pub const MAX_GROUP: usize = 4;
30/// ANN neighbours fetched per distillate. Raws and other projects share the
31/// index, so this leaves room beyond the three a full group needs.
32const NEIGHBOURS: usize = 10;
33const DISTILLATE: &str = "source = 'consolidation' AND tier = 'hot' AND superseded_by IS NULL";
34
35#[derive(Debug, Clone, Serialize)]
36pub struct NearDupMember {
37    pub id: Uuid,
38    pub content: String,
39    pub created_at: DateTime<Utc>,
40}
41
42#[derive(Debug, Clone, Serialize)]
43pub struct NearDupPair {
44    pub a: Uuid,
45    pub b: Uuid,
46    pub similarity: f32,
47}
48
49#[derive(Debug, Clone, Serialize)]
50pub struct NearDupGroup {
51    pub project_path: Option<String>,
52    pub memory_type: MemoryType,
53    pub members: Vec<NearDupMember>,
54    /// Every member pair at or above the threshold, closest first.
55    pub pairs: Vec<NearDupPair>,
56}
57
58/// One page of groups plus how many exist in all, from a single grouping
59/// pass so a caller can report the backlog without grouping twice.
60#[derive(Debug, Clone, Serialize)]
61pub struct NearDupListing {
62    pub groups: Vec<NearDupGroup>,
63    pub total: usize,
64}
65
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum ReviewVerdict {
68    Separate,
69    Conflict,
70    Unmerged,
71}
72
73impl ReviewVerdict {
74    fn relation(self) -> (RelationType, &'static str, &'static str) {
75        match self {
76            ReviewVerdict::Separate => (RelationType::RelatesTo, "relates_to", REVIEW_CONTEXT),
77            ReviewVerdict::Conflict => (RelationType::Contradicts, "contradicts", REVIEW_CONTEXT),
78            ReviewVerdict::Unmerged => (RelationType::RelatesTo, "relates_to", UNMERGED_CONTEXT),
79        }
80    }
81}
82
83#[derive(Debug, Clone, PartialEq)]
84pub enum MergeRefusal {
85    /// The member is gone, superseded or no longer hot: another merge or
86    /// peer got there first.
87    Stale(Uuid),
88    /// The request can never succeed as written.
89    Invalid(String),
90}
91
92#[derive(Debug, Clone, Serialize)]
93pub struct MergeReport {
94    pub merged_id: Uuid,
95    pub superseded: Vec<Uuid>,
96    pub markers_repointed: u64,
97}
98
99struct Candidate {
100    id: Uuid,
101    project_path: Option<String>,
102    memory_type: MemoryType,
103    created_at: DateTime<Utc>,
104    embedding: Vec<f32>,
105}
106
107/// Candidate indexes ordered by creation, and the above-threshold pairs
108/// among them as (candidate, candidate, similarity), closest first.
109type Grouping = (Vec<usize>, Vec<(usize, usize, f32)>);
110
111impl SqliteStore {
112    /// Groups of live distillates sharing a project and type whose cosine is
113    /// at least `threshold`, closest group first, at most `limit`, with the
114    /// total number of groups.
115    pub fn near_duplicate_groups(
116        &self,
117        indexes: &Indexes,
118        threshold: f32,
119        limit: usize,
120    ) -> Result<NearDupListing> {
121        let (candidates, groups) = self.group_near_duplicates(indexes, threshold)?;
122        let total = groups.len();
123        let groups: Vec<Grouping> = groups.into_iter().take(limit).collect();
124        let mut out = Vec::with_capacity(groups.len());
125        for (members, pairs) in groups {
126            let first = &candidates[members[0]];
127            let mut listed = Vec::with_capacity(members.len());
128            for &i in &members {
129                listed.push(NearDupMember {
130                    id: candidates[i].id,
131                    content: self.content_of(candidates[i].id)?,
132                    created_at: candidates[i].created_at,
133                });
134            }
135            out.push(NearDupGroup {
136                project_path: first.project_path.clone(),
137                memory_type: first.memory_type,
138                members: listed,
139                pairs: pairs
140                    .into_iter()
141                    .map(|(a, b, similarity)| NearDupPair {
142                        a: candidates[a].id,
143                        b: candidates[b].id,
144                        similarity,
145                    })
146                    .collect(),
147            });
148        }
149        Ok(NearDupListing { groups: out, total })
150    }
151
152    pub fn near_duplicate_group_count(&self, indexes: &Indexes, threshold: f32) -> Result<usize> {
153        Ok(self.group_near_duplicates(indexes, threshold)?.1.len())
154    }
155
156    /// The member checks `merge_distillates` makes, read-only, so a caller
157    /// can refuse a doomed merge before paying for its embedding.
158    pub fn check_merge(&self, member_ids: &[Uuid]) -> Result<Result<(), MergeRefusal>> {
159        if let Err(refusal) = check_member_ids(member_ids) {
160            return Ok(Err(refusal));
161        }
162        let mut found = Vec::with_capacity(member_ids.len());
163        for &id in member_ids {
164            found.push((id, self.get_memory(id)?));
165        }
166        Ok(merge_members(found).map(|_| ()))
167    }
168
169    /// One transaction: store `content` as a distillate of the members'
170    /// project and type, supersede every member by it and move each raw's
171    /// distillation marker onto it. Refused without writing anything unless
172    /// the members are 2 to 4 distinct live distillates of one project and
173    /// type.
174    pub fn merge_distillates(
175        &self,
176        member_ids: &[Uuid],
177        content: &str,
178        embedding: Vec<f32>,
179        model: &str,
180    ) -> Result<Result<MergeReport, MergeRefusal>> {
181        if let Err(refusal) = check_member_ids(member_ids) {
182            return Ok(Err(refusal));
183        }
184        if content.trim().is_empty() {
185            return Ok(Err(MergeRefusal::Invalid("content is empty".into())));
186        }
187        if embedding.len() != EMBEDDING_DIM {
188            return Ok(Err(MergeRefusal::Invalid(format!(
189                "embedding has {} dimensions, expected {EMBEDDING_DIM}",
190                embedding.len()
191            ))));
192        }
193        self.with_txn(|tx| {
194            let mut found = Vec::with_capacity(member_ids.len());
195            for &id in member_ids {
196                found.push((id, Self::memory_on_tx(tx, id)?));
197            }
198            let members = match merge_members(found) {
199                Ok(members) => members,
200                Err(refusal) => return Ok(Err(refusal)),
201            };
202            let first = &members[0];
203
204            let newest = members
205                .iter()
206                .max_by_key(|m| m.created_at)
207                .expect("check_member_ids guarantees two members");
208            let mut merged = Memory::new(
209                content.to_string(),
210                first.memory_type,
211                "consolidation".to_string(),
212                newest.source_id.clone(),
213            )
214            .with_project_path(first.project_path.clone())
215            .with_machine_id(self.machine_id().to_string());
216            // The merged fact is as old as its newest paraphrase, so recency
217            // ranking treats it like the members rather than as fresh news.
218            merged.created_at = newest.created_at;
219            merged.session_at = latest_session(&members);
220            merged.confidence = members
221                .iter()
222                .map(|m| m.confidence)
223                .fold(f32::MIN, f32::max);
224            merged.embedding = embedding;
225            self.store_memory_on_tx(tx, &merged)?;
226
227            let mut superseded = Vec::with_capacity(members.len());
228            for m in &members {
229                self.supersede_on_tx(tx, m.id, merged.id)?;
230                superseded.push(m.id);
231            }
232
233            let raws: Vec<Uuid> = {
234                let placeholders = vec!["?"; member_ids.len()].join(",");
235                let mut stmt = tx.prepare(&format!(
236                    "SELECT memory_id FROM distillation_log \
237                     WHERE distilled_id IN ({placeholders}) AND memory_id <> distilled_id \
238                     ORDER BY memory_id"
239                ))?;
240                let ids: Vec<String> = member_ids.iter().map(Uuid::to_string).collect();
241                let rows = stmt.query_map(rusqlite::params_from_iter(ids), |r| {
242                    parse_uuid(&r.get::<_, String>(0)?)
243                })?;
244                rows.collect::<rusqlite::Result<Vec<_>>>()?
245            };
246            for &raw in &raws {
247                self.mark_consolidated_on_tx(tx, raw, merged.id, model)?;
248                // Most raws were purged or archived long ago; a relation to a
249                // missing row would be dropped by every peer's import.
250                if Self::memory_on_tx(tx, raw)?.is_some() {
251                    self.store_relation_on_tx(
252                        tx,
253                        &Relation {
254                            from_id: merged.id,
255                            to_id: raw,
256                            relation_type: RelationType::DistilledFrom,
257                            strength: 1.0,
258                            context: Some(model.to_string()),
259                        },
260                    )?;
261                }
262            }
263
264            Ok(Ok(MergeReport {
265                merged_id: merged.id,
266                superseded,
267                markers_repointed: raws.len() as u64,
268            }))
269        })
270    }
271
272    /// Links every pair of `member_ids` with the verdict's relation and
273    /// context (see `ReviewVerdict::relation`); returns how many links were
274    /// new. A pair holds one edge per relation type, so a later `separate`
275    /// or `unmerged` verdict replaces the earlier one.
276    pub fn record_near_duplicate_review(
277        &self,
278        member_ids: &[Uuid],
279        verdict: ReviewVerdict,
280    ) -> Result<Result<u64, MergeRefusal>> {
281        if let Err(refusal) = check_member_ids(member_ids) {
282            return Ok(Err(refusal));
283        }
284        let (relation_type, type_name, context) = verdict.relation();
285        self.with_txn(|tx| {
286            for &id in member_ids {
287                if Self::memory_on_tx(tx, id)?.is_none() {
288                    return Ok(Err(MergeRefusal::Invalid(format!(
289                        "no memory with id {id}"
290                    ))));
291                }
292            }
293            let mut sorted = member_ids.to_vec();
294            sorted.sort();
295            let mut recorded = 0u64;
296            for (i, &a) in sorted.iter().enumerate() {
297                for &b in &sorted[i + 1..] {
298                    let exists: Option<i64> = tx
299                        .query_row(
300                            "SELECT 1 FROM relations WHERE from_id = ?1 AND to_id = ?2 \
301                             AND relation_type = ?3 AND context = ?4",
302                            params![a.to_string(), b.to_string(), type_name, context],
303                            |r| r.get(0),
304                        )
305                        .optional()?;
306                    if exists.is_some() {
307                        continue;
308                    }
309                    self.store_relation_on_tx(
310                        tx,
311                        &Relation {
312                            from_id: a,
313                            to_id: b,
314                            relation_type,
315                            strength: 1.0,
316                            context: Some(context.to_string()),
317                        },
318                    )?;
319                    recorded += 1;
320                }
321            }
322            Ok(Ok(recorded))
323        })
324    }
325
326    /// Deletes the review edges of `verdicts`, replicated as relation
327    /// deletes, so their pairs are grouped again on every peer. Returns how
328    /// many edges were removed; a rerun removes nothing.
329    pub fn reopen_near_duplicate_reviews(&self, verdicts: &[ReviewVerdict]) -> Result<u64> {
330        let mut edges = Vec::new();
331        {
332            let conn = self.reader();
333            for &verdict in verdicts {
334                let (relation_type, type_name, context) = verdict.relation();
335                let mut stmt = conn.prepare(
336                    "SELECT from_id, to_id, strength FROM relations \
337                     WHERE relation_type = ?1 AND context = ?2",
338                )?;
339                let rows = stmt.query_map(params![type_name, context], |r| {
340                    Ok(Relation {
341                        from_id: parse_uuid(&r.get::<_, String>(0)?)?,
342                        to_id: parse_uuid(&r.get::<_, String>(1)?)?,
343                        relation_type,
344                        strength: r.get::<_, f64>(2)? as f32,
345                        context: Some(context.to_string()),
346                    })
347                })?;
348                for edge in rows {
349                    edges.push(edge?);
350                }
351            }
352        }
353        self.with_txn(|tx| {
354            let mut removed = 0u64;
355            for edge in &edges {
356                if self.delete_relation_on_tx(tx, edge)? {
357                    removed += 1;
358                }
359            }
360            Ok(removed)
361        })
362    }
363
364    /// Holds one embedding per live distillate (about 1.5 KB each) and at
365    /// most `NEIGHBOURS` edges per distillate, never an all-pairs matrix.
366    fn group_near_duplicates(
367        &self,
368        indexes: &Indexes,
369        threshold: f32,
370    ) -> Result<(Vec<Candidate>, Vec<Grouping>)> {
371        let candidates = self.live_distillates()?;
372        let position: HashMap<Uuid, usize> = candidates
373            .iter()
374            .enumerate()
375            .map(|(i, c)| (c.id, i))
376            .collect();
377        let reviewed = self.reviewed_pairs()?;
378
379        let mut edges: HashMap<(usize, usize), f32> = HashMap::new();
380        for (i, c) in candidates.iter().enumerate() {
381            for (id, _) in indexes.vector_search(self, &c.embedding, NEIGHBOURS)? {
382                let Some(&j) = position.get(&id) else {
383                    continue;
384                };
385                let other = &candidates[j];
386                if j == i
387                    || other.project_path != c.project_path
388                    || other.memory_type != c.memory_type
389                {
390                    continue;
391                }
392                let key = (i.min(j), i.max(j));
393                if edges.contains_key(&key) {
394                    continue;
395                }
396                let (x, y) = (candidates[key.0].id, candidates[key.1].id);
397                if reviewed.contains(&(x.min(y), x.max(y))) {
398                    continue;
399                }
400                // The index stores quantized vectors, so its score only
401                // nominates; the stored embeddings decide.
402                let similarity = cosine(&c.embedding, &other.embedding);
403                if similarity >= threshold {
404                    edges.insert(key, similarity);
405                }
406            }
407        }
408
409        let mut edges: Vec<((usize, usize), f32)> = edges.into_iter().collect();
410        edges.sort_by(|(ka, sa), (kb, sb)| {
411            sb.total_cmp(sa)
412                .then_with(|| candidates[ka.0].id.cmp(&candidates[kb.0].id))
413                .then_with(|| candidates[ka.1].id.cmp(&candidates[kb.1].id))
414        });
415
416        let mut sets = DisjointSets::new(candidates.len());
417        for &((a, b), _) in &edges {
418            sets.union_capped(a, b, MAX_GROUP);
419        }
420        let mut by_root: HashMap<usize, Vec<usize>> = HashMap::new();
421        for &((a, b), _) in &edges {
422            for i in [a, b] {
423                let members = by_root.entry(sets.find(i)).or_default();
424                if !members.contains(&i) {
425                    members.push(i);
426                }
427            }
428        }
429        let mut groups: Vec<Grouping> = by_root
430            .into_values()
431            .filter(|members| members.len() > 1)
432            .map(|mut members| {
433                members.sort_by(|&x, &y| {
434                    candidates[x]
435                        .created_at
436                        .cmp(&candidates[y].created_at)
437                        .then_with(|| candidates[x].id.cmp(&candidates[y].id))
438                });
439                let pairs = edges
440                    .iter()
441                    .filter(|((a, b), _)| members.contains(a) && members.contains(b))
442                    .map(|&((a, b), s)| (a, b, s))
443                    .collect();
444                (members, pairs)
445            })
446            .collect();
447        groups.sort_by(|(ma, pa), (mb, pb)| {
448            pb[0]
449                .2
450                .total_cmp(&pa[0].2)
451                .then_with(|| candidates[ma[0]].id.cmp(&candidates[mb[0]].id))
452        });
453        Ok((candidates, groups))
454    }
455
456    fn live_distillates(&self) -> Result<Vec<Candidate>> {
457        let conn = self.reader();
458        let mut stmt = conn.prepare(&format!(
459            "SELECT {MEMORY_COLS}, embedding FROM memories \
460             WHERE {DISTILLATE} AND embedding IS NOT NULL ORDER BY id"
461        ))?;
462        let rows = stmt.query_map([], |r| row_to_memory(r, true))?;
463        let mut out = Vec::new();
464        for m in rows {
465            let m = m?;
466            if m.embedding.len() != EMBEDDING_DIM {
467                continue;
468            }
469            out.push(Candidate {
470                id: m.id,
471                project_path: m.project_path,
472                memory_type: m.memory_type,
473                created_at: m.created_at,
474                embedding: m.embedding,
475            });
476        }
477        Ok(out)
478    }
479
480    fn reviewed_pairs(&self) -> Result<HashSet<(Uuid, Uuid)>> {
481        let conn = self.reader();
482        let mut stmt = conn.prepare(
483            "SELECT from_id, to_id FROM relations WHERE context = ?1 OR context LIKE ?1 || ':%'",
484        )?;
485        let rows = stmt.query_map(params![REVIEW_CONTEXT], |r| {
486            Ok((
487                parse_uuid(&r.get::<_, String>(0)?)?,
488                parse_uuid(&r.get::<_, String>(1)?)?,
489            ))
490        })?;
491        let mut out = HashSet::new();
492        for pair in rows {
493            let (a, b) = pair?;
494            out.insert((a.min(b), a.max(b)));
495        }
496        Ok(out)
497    }
498
499    fn content_of(&self, id: Uuid) -> Result<String> {
500        let conn = self.reader();
501        Ok(conn.query_row(
502            "SELECT content FROM memories WHERE id = ?1",
503            params![id.to_string()],
504            |r| r.get(0),
505        )?)
506    }
507}
508
509/// Live distillates of one project and type, in request order.
510fn merge_members(found: Vec<(Uuid, Option<Memory>)>) -> Result<Vec<Memory>, MergeRefusal> {
511    let mut members = Vec::with_capacity(found.len());
512    for (id, memory) in found {
513        match memory {
514            None => return Err(MergeRefusal::Stale(id)),
515            Some(m) if m.source != "consolidation" => {
516                return Err(MergeRefusal::Invalid(format!("{id} is not a distillate")));
517            }
518            Some(m) if m.tier != Tier::Hot || m.superseded_by.is_some() => {
519                return Err(MergeRefusal::Stale(id));
520            }
521            Some(m) => members.push(m),
522        }
523    }
524    let first = &members[0];
525    if members
526        .iter()
527        .any(|m| m.project_path != first.project_path || m.memory_type != first.memory_type)
528    {
529        return Err(MergeRefusal::Invalid(
530            "members span more than one project or memory type".into(),
531        ));
532    }
533    Ok(members)
534}
535
536/// The shape every merge and review request must have: 2 to `MAX_GROUP`
537/// distinct ids.
538pub fn check_member_ids(member_ids: &[Uuid]) -> Result<(), MergeRefusal> {
539    if !(2..=MAX_GROUP).contains(&member_ids.len()) {
540        return Err(MergeRefusal::Invalid(format!(
541            "expected 2 to {MAX_GROUP} member ids, got {}",
542            member_ids.len()
543        )));
544    }
545    let distinct: HashSet<&Uuid> = member_ids.iter().collect();
546    if distinct.len() != member_ids.len() {
547        return Err(MergeRefusal::Invalid("member ids repeat".into()));
548    }
549    Ok(())
550}
551
552/// Union-find whose unions stop at a size cap, so a chain of close pairs
553/// cannot snowball into one group too large to merge in a single prompt.
554struct DisjointSets {
555    parent: Vec<usize>,
556    size: Vec<usize>,
557}
558
559impl DisjointSets {
560    fn new(n: usize) -> Self {
561        Self {
562            parent: (0..n).collect(),
563            size: vec![1; n],
564        }
565    }
566
567    fn find(&mut self, mut i: usize) -> usize {
568        while self.parent[i] != i {
569            self.parent[i] = self.parent[self.parent[i]];
570            i = self.parent[i];
571        }
572        i
573    }
574
575    fn union_capped(&mut self, a: usize, b: usize, cap: usize) {
576        let (ra, rb) = (self.find(a), self.find(b));
577        if ra == rb || self.size[ra] + self.size[rb] > cap {
578            return;
579        }
580        let (big, small) = if self.size[ra] >= self.size[rb] {
581            (ra, rb)
582        } else {
583            (rb, ra)
584        };
585        self.parent[small] = big;
586        self.size[big] += self.size[small];
587    }
588}