second-brain-core 0.10.0

Core library for second-brain: KuzuDB graph storage, BGE embeddings, and weighted query engine
Documentation
use std::collections::{HashMap, HashSet};

use uuid::Uuid;

pub const RRF_K: f32 = 60.0;

/// Reciprocal rank fusion over any number of ranked id lists. Each list
/// contributes 1/(k + rank) with 1-based ranks; ids on multiple lists sum.
/// Ties break on the id bytes so fusion is deterministic across runs.
pub fn fuse(rankings: &[&[Uuid]], k: f32, top: usize) -> Vec<(Uuid, f32)> {
    let mut scores: HashMap<Uuid, f32> = HashMap::new();
    for list in rankings {
        for (rank, id) in list.iter().enumerate() {
            *scores.entry(*id).or_insert(0.0) += 1.0 / (k + (rank + 1) as f32);
        }
    }
    let mut fused: Vec<(Uuid, f32)> = scores.into_iter().collect();
    fused.sort_by(|a, b| {
        b.1.partial_cmp(&a.1)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.0.cmp(&b.0))
    });
    fused.truncate(top);
    fused
}

/// `fuse`, except the first `floor` ids of every list are always kept, so a
/// strong hit on one list alone cannot be crowded out by ids sitting midway
/// down several. The rest fill by RRF score up to `top`; with a floor wide
/// enough the result runs past `top`. Ordered by RRF score like `fuse`.
pub fn fuse_with_floor(rankings: &[&[Uuid]], k: f32, top: usize, floor: usize) -> Vec<(Uuid, f32)> {
    let all = fuse(rankings, k, usize::MAX);
    let kept: HashSet<Uuid> = rankings
        .iter()
        .flat_map(|list| list.iter().take(floor).copied())
        .collect();
    let mut fill = top.saturating_sub(kept.len());
    all.into_iter()
        .filter(|(id, _)| {
            if kept.contains(id) {
                true
            } else if fill > 0 {
                fill -= 1;
                true
            } else {
                false
            }
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    fn ids(n: usize) -> Vec<Uuid> {
        (0..n).map(|_| Uuid::new_v4()).collect()
    }

    #[test]
    fn id_on_both_lists_outranks_single_list_leaders() {
        let shared = Uuid::new_v4();
        let dense = [vec![shared], ids(3)].concat();
        let lexical = [ids(2), vec![shared]].concat();

        let fused = fuse(&[&dense, &lexical], RRF_K, 10);
        assert_eq!(
            fused[0].0, shared,
            "rank 1 + rank 3 must beat any single-list id"
        );
        let expected = 1.0 / (RRF_K + 1.0) + 1.0 / (RRF_K + 3.0);
        assert!((fused[0].1 - expected).abs() < 1e-6);
    }

    #[test]
    fn preserves_order_within_a_single_list() {
        let dense = ids(5);
        let fused = fuse(&[&dense], RRF_K, 10);
        let fused_ids: Vec<Uuid> = fused.iter().map(|(id, _)| *id).collect();
        assert_eq!(fused_ids, dense);
    }

    #[test]
    fn truncates_to_top() {
        let dense = ids(200);
        assert_eq!(fuse(&[&dense], RRF_K, 100).len(), 100);
    }

    #[test]
    fn deterministic_on_score_ties() {
        let a = ids(4);
        let b: Vec<Uuid> = a.iter().rev().cloned().collect();
        // Every id gets rank r in one list and (n+1-r) in the other: all tie.
        let first = fuse(&[&a, &b], RRF_K, 10);
        let second = fuse(&[&a, &b], RRF_K, 10);
        assert_eq!(first, second);
    }

    #[test]
    fn a_zero_floor_is_plain_fusion() {
        let dense = ids(40);
        let lexical = [ids(10), dense[5..25].to_vec()].concat();
        assert_eq!(
            fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 0),
            fuse(&[&dense, &lexical], RRF_K, 20)
        );
    }

    #[test]
    fn the_floor_keeps_a_dense_only_rank_30_item_that_fusion_drops() {
        let dense = ids(60);
        let lexical: Vec<Uuid> = dense[30..60].to_vec();
        let buried = dense[29];

        let plain = fuse(&[&dense, &lexical], RRF_K, 20);
        assert!(!plain.iter().any(|(id, _)| *id == buried));

        let floored = fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 30);
        assert!(floored.iter().any(|(id, _)| *id == buried));
        for id in dense[..30].iter().chain(&lexical[..30]) {
            assert!(floored.iter().any(|(f, _)| f == id));
        }
        assert!(
            floored.windows(2).all(|w| w[0].1 >= w[1].1),
            "the floored list stays in RRF order"
        );
    }

    #[test]
    fn the_floor_fills_to_top_by_rrf_when_it_admits_fewer() {
        let dense = ids(50);
        let lexical = ids(50);
        let floored = fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 5);
        assert_eq!(floored.len(), 20);
        assert_eq!(floored, fuse(&[&dense, &lexical], RRF_K, 20));
    }
}