mod linear;
mod rrf;
pub use linear::LinearFusion;
pub use rrf::{Rrf, WeightedRrf};
use std::collections::hash_map::Entry;
use std::hash::Hash;
#[cfg(feature = "ahash")]
pub(crate) type FxMap<K, V> = ahash::AHashMap<K, V>;
#[cfg(not(feature = "ahash"))]
pub(crate) type FxMap<K, V> = std::collections::HashMap<K, V>;
use crate::core::{Candidate, MergePolicy, RankedList, Scored};
use crate::explain::{Explained, SourceContribution};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum FusionError {
WeightCountMismatch {
expected: usize,
got: usize,
},
}
impl std::fmt::Display for FusionError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::WeightCountMismatch { expected, got } => write!(
f,
"weight count mismatch: {expected} weights for {got} lists"
),
}
}
}
impl std::error::Error for FusionError {}
pub trait Fusion<Id, Metadata> {
type Input;
fn fuse(&self, lists: Vec<Self::Input>) -> Result<Vec<Scored<Id, Metadata>>, FusionError>;
fn fuse_explained(
&self,
lists: Vec<Self::Input>,
) -> Result<Vec<Explained<Id, Metadata>>, FusionError>;
}
struct Acc<Id, Metadata> {
scored: Scored<Id, Metadata>,
first_seen: usize,
}
pub(crate) fn accumulate_contributions<Id, Metadata, P>(
contributions: impl IntoIterator<Item = (Candidate<Id, Metadata>, f32)>,
policy: &P,
) -> Vec<Scored<Id, Metadata>>
where
Id: Eq + Hash + Clone,
P: MergePolicy<Metadata>,
{
let mut acc: FxMap<Id, Acc<Id, Metadata>> = FxMap::default();
let mut first_seen = 0usize;
for (candidate, contribution) in contributions {
match acc.entry(candidate.id.clone()) {
Entry::Occupied(mut entry) => {
let slot = entry.get_mut();
slot.scored.score += contribution;
policy.merge(&mut slot.scored.candidate.metadata, candidate.metadata);
}
Entry::Vacant(entry) => {
entry.insert(Acc {
scored: Scored {
candidate,
score: contribution,
},
first_seen,
});
first_seen += 1;
}
}
}
let mut out: Vec<Acc<Id, Metadata>> = acc.into_values().collect();
out.sort_unstable_by(|a, b| {
b.scored
.score
.total_cmp(&a.scored.score)
.then(a.first_seen.cmp(&b.first_seen))
});
out.into_iter().map(|a| a.scored).collect()
}
struct AccExplained<Id, Metadata> {
explained: Explained<Id, Metadata>,
first_seen: usize,
}
pub(crate) fn accumulate_explained<Id, Metadata, P>(
entries: impl IntoIterator<Item = (Candidate<Id, Metadata>, SourceContribution)>,
policy: &P,
) -> Vec<Explained<Id, Metadata>>
where
Id: Eq + Hash + Clone,
P: MergePolicy<Metadata>,
{
let mut acc: FxMap<Id, AccExplained<Id, Metadata>> = FxMap::default();
let mut first_seen = 0usize;
for (candidate, contribution) in entries {
match acc.entry(candidate.id.clone()) {
Entry::Occupied(mut entry) => {
let slot = entry.get_mut();
slot.explained.scored.score += contribution.partial_score;
slot.explained.contributions.push(contribution);
policy.merge(
&mut slot.explained.scored.candidate.metadata,
candidate.metadata,
);
}
Entry::Vacant(entry) => {
entry.insert(AccExplained {
explained: Explained {
scored: Scored {
candidate,
score: contribution.partial_score,
},
contributions: vec![contribution],
},
first_seen,
});
first_seen += 1;
}
}
}
let mut out: Vec<AccExplained<Id, Metadata>> = acc.into_values().collect();
out.sort_unstable_by(|a, b| {
b.explained
.scored
.score
.total_cmp(&a.explained.scored.score)
.then(a.first_seen.cmp(&b.first_seen))
});
out.into_iter().map(|a| a.explained).collect()
}
pub(crate) fn explained_rrf<Id, Metadata, P>(
k: f32,
lists: Vec<RankedList<Id, Metadata>>,
weights: Option<&[f32]>,
policy: &P,
) -> Vec<Explained<Id, Metadata>>
where
Id: Eq + Hash + Clone,
P: MergePolicy<Metadata>,
{
let entries = lists
.into_iter()
.enumerate()
.flat_map(|(list_index, list)| {
let weight = weights.map_or(1.0, |w| w[list_index]);
list.items
.into_iter()
.enumerate()
.map(move |(position, candidate)| {
let rank = position + 1;
(
candidate,
SourceContribution {
list_index,
rank,
partial_score: weight / (k + rank as f32),
},
)
})
});
accumulate_explained(entries, policy)
}
pub(crate) fn accumulate_rrf<Id, Metadata, P>(
k: f32,
lists: Vec<RankedList<Id, Metadata>>,
weights: Option<&[f32]>,
policy: &P,
) -> Vec<Scored<Id, Metadata>>
where
Id: Eq + Hash + Clone,
P: MergePolicy<Metadata>,
{
let contributions = lists
.into_iter()
.enumerate()
.flat_map(|(list_index, list)| {
let weight = weights.map_or(1.0, |w| w[list_index]);
list.items
.into_iter()
.enumerate()
.map(move |(position, candidate)| {
let rank = position + 1;
(candidate, weight / (k + rank as f32))
})
});
accumulate_contributions(contributions, policy)
}