ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
//! THE FOLD: N root-projected member lists in, one ranked fused list out.

use core::cmp::Reverse;

use super::{Fused, FusedScore, Fusion, Join, Rooted, Route, Sighting};

/// Fuse the members' lists into one ranked answer.
///
/// # The arithmetic, and the only two numbers it reads
///
/// Each member contributes `1 / (k + rank)` to every root it ranked, and a root's fused score is the
/// SUM of those contributions. `rank` is that member's ENGINE ordinal for the hit and `k` is
/// [`Fusion::Rrf`]'s damping constant; no score of any member enters, which is the property that
/// lets members whose currencies have never been compared be fused at all.
///
/// # The pipeline this is the end of
///
/// ```text
/// each member:  engine → floor → dedup → rank → root-project → Vec<Rooted<R, V>>
/// then:         fuse(those, fusion) → Vec<Fused<R, V>>
/// ```
///
/// The floor is the ONE semantic gate and it has already run: what arrives here is the survivors,
/// all of them, bounded per member only by the safety ceiling. So this function prunes NOTHING — a
/// root ranked by a single member at a poor ordinal still comes back, ranked below everything more
/// agreed upon, and *raise the floor* is what a caller who wants fewer results does.
///
/// # A member is counted ONCE per root, and the first sighting is the one counted
///
/// A member's list is meant to arrive collapsed at the root grain, so this is the case that should
/// not occur — and where it does, the second sighting is DROPPED WHOLE rather than added. Two
/// reasons, and the first is a defect the addition would create: a member that returned six segments
/// of one video would out-contribute genuine agreement between two members about a different video,
/// and the fused ranking would be measuring transcript density instead of relevance.
///
/// The second is that the drop makes this fold agree with itself across the grain. Root-projecting a
/// SELF-grain list produces exactly those repeats, and dropping all but the first keeps the best
/// segment per root — which is what the root grain would have handed over in the first place, since
/// a descending stream's first sighting is its best. *First occurrence wins* is the dedup stage's own
/// ruled law, applied where the same shape recurs.
///
/// # Ties keep the order they arrived in
///
/// No ruling sets a tie law, and the sort is STABLE, so roots with equal fused scores come back in
/// FIRST-SIGHTING order: the root some member ranked earliest, reading the member lists in the order
/// they were passed. That is deterministic and it is arbitrary, in that order of importance — it is
/// recorded here so a client does not read meaning into it.
///
/// The same stability orders the evidence: two members that contributed equally appear in the order
/// their lists were passed.
///
/// # `J` is the join's mechanism, and it is the LAST parameter for a measured reason
///
/// [`ranked_keys`](crate::ranked_keys) spells its dedup mechanism last and is called
/// `ranked_keys::<_, _, D>(…)`; this mirrors it. What forces the member lists to be `Vec`s rather
/// than `impl IntoIterator` is the same mirroring: a partial turbofish is **`E0107`** — *function
/// takes 5 generic arguments but 3 generic arguments were supplied* — so iterator generics for the
/// two collection layers would have made every call site spell `fuse::<_, _, HashJoin<_>, _, _>`.
/// The lists are built by a `map().collect()` at the projection anyway, so the concrete shape costs
/// the caller nothing it was not already holding.
pub fn fuse<R, V, J>(members: Vec<Vec<Rooted<R, V>>>, fusion: Fusion) -> Vec<Fused<R, V>>
where
  J: Join<R>,
{
  fuse_weighted::<R, V, J>(
    members
      .into_iter()
      .map(|list| (Route::<()>::DEFAULT_WEIGHT, list))
      .collect(),
    fusion,
  )
}

/// [`fuse`] with a WEIGHT on every member — the edge fact [`Route::weight`] carries, spent.
///
/// # It is the same fold and not a second one
///
/// A member's term becomes `w / (k + rank)`, and everything else is unchanged: no score of any
/// member enters, the ordinal is still the engine's raw one, a member is still counted once per
/// root, and the sort is still stable. At `w = 1` for every member this IS [`fuse`], which is why
/// that function delegates rather than repeating the walk — one arithmetic, one place.
///
/// # The weight rides the MEMBER and not the hit
///
/// A route's weight is what a PARENT believes about that route, so it multiplies every term the
/// route contributes and nothing about which terms those are. A per-hit weight would be a score,
/// and scores do not fuse.
///
/// # The evidence CARRIES the weighted contribution, and is ordered by it
///
/// [`Fused::evidence`] is ordered by contribution, and the contribution a member actually made is
/// the weighted one — so a heavily-weighted member that ranked a root third can lead the evidence
/// over a barely-weighted one that ranked it first, which is what the weight was set to mean.
///
/// The number is KEPT rather than dropped after the sort (#296-L2): each entry is a
/// [`Sighting`](super::Sighting) holding it beside the member's own evidence. The fold already had
/// it in a local — carrying is not computing anything new, and it is the only thing that lets a
/// reader tell a nose from a mile.
///
/// The RANK it was computed from is kept with it (#296-L3). This walk destructures `rank` out of
/// every hit and used to drop it the moment the term was multiplied; the term alone cannot be run
/// backwards — `w / (k + rank)` is two unknowns in one equation and the weight never crosses the
/// wire — so the input to RRF is carried rather than left to be inferred from an output.
pub fn fuse_weighted<R, V, J>(
  members: Vec<(f64, Vec<Rooted<R, V>>)>,
  fusion: Fusion,
) -> Vec<Fused<R, V>>
where
  J: Join<R>,
{
  // Irrefutable while `Fusion` has one variant, and `E0005` at this line the day it grows a second
  // — which is the whole reason the strategy is an enum. `#[non_exhaustive]` is invisible inside the
  // crate that declares it, so the binding is legal here and a wildcard would hide that error.
  let Fusion::Rrf { k } = fusion;
  let k = u64::from(k);

  let mut join = J::empty();
  // Four parallel accumulators rather than a struct of four fields, because the join's contract is
  // stated in terms of an INDEX and these are what it indexes. Dense and in admission order, so a
  // `None` from `place` lands at the current length.
  let mut roots: Vec<R> = Vec::new();
  let mut scores: Vec<f64> = Vec::new();
  let mut evidence: Vec<Vec<Sighting<V>>> = Vec::new();
  let mut counted: Vec<Option<usize>> = Vec::new();

  for (member, (weight, list)) in members.into_iter().enumerate() {
    for hit in list {
      let (root, rank, seen) = hit.into_components();
      let at = match join.place(&root) {
        Some(at) => at,
        None => {
          roots.push(root);
          scores.push(0.0);
          evidence.push(Vec::new());
          counted.push(None);
          roots.len() - 1
        }
      };
      if counted[at] == Some(member) {
        continue;
      }
      counted[at] = Some(member);
      let contribution = weight * contribution(k, rank);
      scores[at] += contribution;
      evidence[at].push(Sighting::new(contribution, rank, seen));
    }
  }

  let mut fused: Vec<Fused<R, V>> = roots
    .into_iter()
    .zip(scores)
    .zip(evidence)
    .map(|((root, score), mut seen)| {
      // `total_cmp` rather than `partial_cmp` + an `expect`: the contributions are finite and
      // positive by construction, and a total comparison is the one spelling that needs no sentence
      // about what would happen if they were not.
      seen.sort_by(|a, b| b.contribution().total_cmp(&a.contribution()));
      Fused::new(
        FusedScore::new(score).expect("a sum of finite weighted contributions is never NaN"),
        root,
        seen,
      )
    })
    .collect();
  // `sort_by_key` + `Reverse` rather than a reversed comparator, which is clippy's own reading of
  // the same descent — and it is STABLE either way, which is what leaves equal scores in
  // first-sighting order.
  fused.sort_by_key(|row| Reverse(row.score()));
  fused
}

/// One member's RRF term for a hit at `rank`, damped by `k`.
///
/// # The denominator floor, and the one input it exists for
///
/// `rank` is the 1-based engine ordinal, so `k + rank` is at least 1 for every input the pipeline
/// produces and the clamp is never reached. It covers the one value that is not an ordinal — a `0`
/// handed in by a caller who passed a list POSITION instead — for which the division would be an
/// infinity, and an infinity in a sum is a root that outranks everything for a reason that is not
/// about the corpus. Clamped and finite is the answer that stays diagnosable.
///
/// `saturating_add` for the other end: `k + rank` cannot wrap into a small denominator and turn the
/// worst hit in a stream into the best one in the answer.
#[inline]
fn contribution(k: u64, rank: u64) -> f64 {
  1.0 / k.saturating_add(rank).max(1) as f64
}

#[cfg(test)]
mod tests;