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 set fold's MECHANISM: [`Bests`], and the two accumulators a declaration chooses between —
//! [`Seen`](super::Seen)'s family one grain over.

use std::collections::HashMap;

use crate::Scored;

/// A KEYED ACCUMULATOR over the entities a set query has scored so far — the fold's one moving part.
///
/// # Why an accumulator and not the membership beside it
///
/// The dedup stage asks *have I seen this key* and drops the second sighting; the set fold asks
/// *what has this key scored so far* and COMBINES the second sighting into the first. The two
/// questions want the same capability of a key — some way to tell two of them apart — and different
/// things of the container, so [`Seen`](super::Seen) answers one and this answers the other. The
/// grain is the reason both exist: a set query runs the engine once per QUERY VECTOR, so one entity
/// legitimately appears in several of the engine's answers, and collapsing it the dedup's way would
/// throw away every contribution but the first.
///
/// # Why the mechanism is DECLARED rather than fixed
///
/// It is the same BOUNDS choice on the key type the dedup word already makes, which is why the same
/// word makes it:
///
/// | word | this trait's implementor | what the key must satisfy |
/// |---|---|---|
/// | `dedup(hash)` | [`HashBests`] | [`Hash`](core::hash::Hash) + [`Eq`] |
/// | `dedup(eq)` | [`EqBests`] | [`PartialEq`] |
///
/// A declaration that reached for `eq` because its key cannot hash must not find the set road
/// closed to it for the same reason, and a declaration on `hash` must not silently pay a linear
/// scan. So the word picks both members of the pair, and a framework widening is an ARM — an
/// ordered accumulator arrives as one more implementor of this trait beside one more implementor of
/// [`Seen`](super::Seen), and no signature above either moves.
///
/// # No `Clone` on either row, which is where the two families differ
///
/// A membership holds a COPY of every key the survivor list also holds, so both its implementors
/// bound `K: Clone`. An accumulator holds the key ITSELF — the fold's output is the accumulator's
/// contents rather than a list beside it — so nothing here clones and nothing here asks a key to be
/// cloneable.
pub trait Bests<K, S> {
  /// An empty accumulator.
  ///
  /// Declared here rather than through [`Default`], for the reason [`Seen::empty`](super::Seen)
  /// gives: the fold mints one from the type parameters alone, and a derived `Default` on a
  /// key-holding collection would have demanded `K: Default` of every caller.
  fn empty() -> Self;

  /// Fold `score` into `key`'s running total, `combine` deciding how a later sighting joins an
  /// earlier one.
  ///
  /// The key is taken BY VALUE: an accumulator that already holds this key drops the newcomer, and
  /// one that does not keeps it — either way the fold owns exactly one copy, and the caller has
  /// finished with it.
  ///
  /// `combine` receives the two in SIGHTING ORDER — the running total first, the newcomer second —
  /// so a non-commutative fold is spelled once at the call and read the same way here.
  fn fold(&mut self, key: K, score: S, combine: impl FnOnce(S, S) -> S);

  /// Every key and its final score, in no particular order.
  ///
  /// Unordered because the fold's own answer is not the accumulator's order: a set score is only
  /// known once every query vector has been walked, so the sort belongs after this call and the
  /// container that could have kept an order has nothing to have kept one BY.
  fn drain(self) -> Vec<Scored<K, S>>;
}

/// `dedup(hash)` — accumulation through a [`HashMap`], the default.
///
/// Two hashes per sighting rather than one, which is the price of taking the running total OUT to
/// combine it: an occupied entry cannot lend its value to a closure that consumes it and put the
/// result back through the same borrow. A stream of any size still wants this over the scan below.
#[derive(Debug)]
pub struct HashBests<K, S>(HashMap<K, S>);

impl<K, S> Bests<K, S> for HashBests<K, S>
where
  K: core::hash::Hash + Eq,
{
  #[inline]
  fn empty() -> Self {
    Self(HashMap::new())
  }

  #[inline]
  fn fold(&mut self, key: K, score: S, combine: impl FnOnce(S, S) -> S) {
    let folded = match self.0.remove(&key) {
      Some(running) => combine(running, score),
      None => score,
    };
    self.0.insert(key, folded);
  }

  #[inline]
  fn drain(self) -> Vec<Scored<K, S>> {
    self
      .0
      .into_iter()
      .map(|(key, score)| Scored::new(key, score))
      .collect()
  }
}

/// `dedup(eq)` — accumulation through a list walked by field-wise equality.
///
/// Quadratic in the number of DISTINCT ENTITIES, stated rather than hidden exactly as
/// [`EqSeen`](super::EqSeen) states its own: it is the price of asking only [`PartialEq`] of the
/// key, the entity count is bounded by what a retrieve returns rather than by the corpus, and a
/// declaration reaches for this word when the alternative is not retrieving at all.
///
/// The remove-and-reinsert is what keeps FIRST-SIGHTING ORDER, which costs a shift per repeat
/// sighting on a container that is already linear to search. Order is not load-bearing for the
/// answer — [`drain`](Bests::drain) promises none and the fold sorts afterwards — but it is what
/// makes a tie between two equal set scores resolve the same way twice.
#[derive(Debug)]
pub struct EqBests<K, S>(Vec<Scored<K, S>>);

impl<K, S> Bests<K, S> for EqBests<K, S>
where
  K: PartialEq,
{
  #[inline]
  fn empty() -> Self {
    Self(Vec::new())
  }

  #[inline]
  fn fold(&mut self, key: K, score: S, combine: impl FnOnce(S, S) -> S) {
    match self.0.iter().position(|held| held.data_ref() == &key) {
      Some(at) => {
        let (held, running) = self.0.remove(at).into_components();
        self
          .0
          .insert(at, Scored::new(held, combine(running, score)));
      }
      None => self.0.push(Scored::new(key, score)),
    }
  }

  #[inline]
  fn drain(self) -> Vec<Scored<K, S>> {
    self.0
  }
}

#[cfg(test)]
mod tests;