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
//! Tier A: the walk that turns an engine's raw hit stream into ranked, deduped keys.

use core::cmp::Ordering;

use super::{Ranked, Seen};
use crate::Scored;

/// The pipeline, in its ruled order: **engine → floor → dedup → rank → tier A**.
///
/// ONE implementation for both flavours and both tiers. It is generic over the ENGINE CALL — what
/// arrives is whatever [`FulltextRead::search`](crate::FulltextRead::search) or
/// [`VectorRead::knn`](crate::VectorRead::knn) produced, read back into keys — and over the
/// dedup MECHANISM, which is the
/// only thing a declaration gets to choose. Nothing about a flavour reaches this function, which is
/// why there is no full-text copy of it beside a vector one.
///
/// # The four stages, and why the order is not negotiable
///
/// 1. **The engine** answers in SCORE-DESCENDING order. Every stage below reads that as a
///    precondition; an engine that violates it gets a short answer rather than a wrong one, which
///    the floor's early termination makes structural.
/// 2. **The floor terminates the walk.** The first hit below it ends the loop — not `filter`, not a
///    `retain` afterwards. On a descending stream the two agree about the RESULT and disagree about
///    the WORK: an unbounded engine tail is walked in full by the filtering spelling and is never
///    touched by this one. That is the whole payoff of applying the floor at the engine stage, and
///    it is why the stage is where it is rather than a convenience anywhere later.
/// 3. **Dedup, immediately, on the engine's own key list.** First seen wins, which on a descending
///    stream is the best score. At the SELF key grain — the engine's own key, exactly as the
///    pipeline was ruled. A root-grain collapse is a later line and there is no projection knob
///    here for one.
/// 4. **Rank is minted over the RAW stream**, counted before either prune. A duplicate consumes its
///    ordinal and a pruned hit consumes its ordinal, so the numbers on the survivors have holes and
///    the holes are the point — see [`Ranked`].
///
/// # `limit` is a budget rather than a promise
///
/// The walk stops once `limit` survivors exist. A shorter answer is legal and expected: the engine
/// may run dry, and the floor may cut the tail. THE WALK IS SINGLE-SHOT — there is no cursor slot,
/// and nothing here holds a position between calls — so a caller continuing at THIS grain does so
/// by re-asking with a wider budget and dropping everything at or below the last rank it saw.
///
/// Paging exists one layer up and does not change that sentence: [`SnapshotKeeper`](crate::SnapshotKeeper)
/// holds the FOLD's answer and cuts stretches off it, so a client walking a ranking never reaches
/// this function a second time.
///
/// `usize::MAX` is what tier B passes: it needs every above-floor key, because its own filter is
/// what decides how many of them survive to fill a page.
///
/// # A score that is not comparable ends the walk
///
/// The test is `score >= floor`, so a `NaN` — for which every comparison is false — reads as below
/// the floor and terminates. That is the conservative reading and the honest one: a hit whose score
/// cannot be placed against the floor cannot be shown to have cleared it.
pub fn ranked_keys<K, S, D>(
  hits: impl IntoIterator<Item = Scored<K, S>>,
  floor: &S,
  limit: usize,
) -> Vec<Ranked<K, S>>
where
  S: PartialOrd,
  D: Seen<K>,
{
  walk(hits, floor, limit, D::empty())
}

/// The walk above with ONE KEY ALREADY SEEN — the similar-by-example door's self exclusion, and it
/// is the DEDUP STAGE rather than a filter beside it.
///
/// Everything [`ranked_keys`] states holds here unchanged — the four stages in their ruled order,
/// the floor that terminates rather than filters, the budget that is not a promise, the
/// incomparable score that ends the walk. It IS that walk; the seed is the only difference.
///
/// # The exclusion IS the membership, pre-seeded, and every property that matters falls out of that
///
/// *Exclude the example itself* has three obligations, and neither a `retain` before the walk nor
/// one after it pays all three:
///
/// 1. **The rank hole stays.** [`Ranked::rank`] is the ordinal in the ENGINE's raw stream and holes
///    are never re-densified. The example is its own nearest neighbour, so it arrives FIRST — and
///    filtering BEFORE the walk would renumber every hit behind it, handing back a page whose ranks
///    claim positions the engine never gave them. Seeding the membership consumes the example's
///    ordinal exactly as a duplicate consumes one, because in this walk it IS one.
/// 2. **`limit` counts NEIGHBOURS.** A skipped key is not a survivor, so a budget of 10 fills with
///    10 other entities. Filtering AFTER the walk would hand back `limit - 1` whenever the example
///    cleared the floor, which is nearly always.
/// 3. **No new bound.** [`Seen::admit`] is the whole of what is asked of the key, and the
///    declaration's own `dedup` word already demands it — `Hash + Eq` or `PartialEq`, either of
///    which decides *is this the example*. The exclusion costs the emitted door no demand its raw
///    siblings do not already make.
///
/// # It excludes ONE key and takes it by reference
///
/// One, because the door is *similar to THIS entity*; by reference, because the membership takes
/// whatever copy it needs on its own terms and the caller's key stays the caller's.
pub fn ranked_keys_excluding<K, S, D>(
  hits: impl IntoIterator<Item = Scored<K, S>>,
  floor: &S,
  limit: usize,
  excluded: &K,
) -> Vec<Ranked<K, S>>
where
  S: PartialOrd,
  D: Seen<K>,
{
  let mut admitted = D::empty();
  // Discarded deliberately: an empty membership admits everything, so the answer here is known and
  // the CALL is the seed. The walk below is what spends it.
  let _ = admitted.admit(excluded);
  walk(hits, floor, limit, admitted)
}

/// THE WALK, written once — the four stages both doors above share, differing only in what the
/// membership starts as.
///
/// PRIVATE, because a membership is not a parameter a caller should be handed: the two public
/// spellings are *nothing seen yet* and *this one key seen*, and those are the two the ruled
/// pipeline has a meaning for.
fn walk<K, S, D>(
  hits: impl IntoIterator<Item = Scored<K, S>>,
  floor: &S,
  limit: usize,
  mut admitted: D,
) -> Vec<Ranked<K, S>>
where
  S: PartialOrd,
  D: Seen<K>,
{
  let mut ranked = Vec::new();
  if limit == 0 {
    return ranked;
  }
  // The RAW stream's ordinal, incremented once per hit the engine yielded — never per survivor.
  let mut rank: u64 = 0;
  for hit in hits {
    // `partial_cmp` rather than `!(score >= floor)`: the two say the same thing and only this one
    // says what happens when the answer is `None`, which is the whole of the incomparable case.
    match hit.score_ref().partial_cmp(floor) {
      Some(Ordering::Greater | Ordering::Equal) => {}
      Some(Ordering::Less) | None => break,
    }
    rank = rank.saturating_add(1);
    let (key, score) = hit.into_components();
    if !admitted.admit(&key) {
      continue;
    }
    ranked.push(Ranked::new(score, rank, key));
    if ranked.len() == limit {
      break;
    }
  }
  ranked
}

#[cfg(test)]
mod tests;