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