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 key dedup's MECHANISM: [`Seen`], and the two memberships a declaration chooses between.

use std::collections::HashSet;

/// A membership over the keys already admitted — the dedup stage's one moving part.
///
/// # Why the dedup exists at all
///
/// An engine is NOT trusted to answer with unique keys. The store faces are open traits, so a
/// third-party backend owes no keyed-replace guarantee, and a slot rebuilt out of step with its
/// source can hold two entries under one address. The framework therefore collapses the hit stream
/// itself, by key, immediately after the engine — before rank is minted and before either tier
/// spends anything on a hit.
///
/// **First occurrence wins.** The stream is score-descending, so the first sighting of a key IS its
/// best score, and the Max representative falls out with no knob to choose it. The later duplicate
/// is dropped whole — its rank goes with it, leaving one of the holes [`Ranked::rank`] describes.
///
/// # Why the mechanism is DECLARED rather than fixed
///
/// It is a BOUNDS choice on the key type, which is the one kind of implementation detail a
/// declaration has to be able to make:
///
/// | word | this trait's implementor | what the key must satisfy |
/// |---|---|---|
/// | `dedup(hash)` | [`HashSeen`] | [`Hash`](core::hash::Hash) + [`Eq`] |
/// | `dedup(eq)` | [`EqSeen`] | [`PartialEq`] |
///
/// `hash` is the default because every key a node macro emits today is built from the closed
/// segment vocabulary and every member of it hashes, so the default always compiles. `eq` is the
/// open-posture escape: it asks less of the type, and a key that cannot hash — a float coordinate
/// in an address, a foreign type with no `Hash` impl — is retrievable through it.
///
/// # `Clone` is the mechanism's own cost, and it is on BOTH rows
///
/// A membership OWNS the keys it has seen, and the survivor list owns them too, so one of the two
/// holds a copy. That is the cost of a set beside a result list and it is uniform — it does not
/// belong to `hash` or to `eq`, and it does not disturb the choice the declaration is actually
/// making, which is `Hash + Eq` against `PartialEq`.
///
/// A framework widening is an ARM rather than a redesign: an ordered membership (`dedup(ord)`) is
/// one more implementor of this trait and one more word in the grammar, and no signature above it
/// moves.
pub trait Seen<K> {
  /// An empty membership.
  ///
  /// Declared here rather than through [`Default`], so the walk can mint one from the type
  /// parameter alone without every implementor's key having to be `Default` too — which the derived
  /// `#[derive(Default)]` on a key-holding collection would have demanded.
  fn empty() -> Self;

  /// Admit `key` if it has not been seen, and say whether it was admitted.
  ///
  /// `false` is *this is a duplicate*, which the walk drops. The key is taken by reference because
  /// the walk keeps it: what is stored here is the membership's own copy.
  fn admit(&mut self, key: &K) -> bool;
}

/// `dedup(hash)` — membership through a [`HashSet`], the default.
///
/// One hash and one bucket probe per hit, which is what a stream of any size wants. What it asks of
/// the key is `Hash + Eq`, and `Eq` rather than `PartialEq` is the set's own requirement rather
/// than this crate's: a hash table has no meaning for a key that is not equal to itself.
#[derive(Debug)]
pub struct HashSeen<K>(HashSet<K>);

impl<K> Seen<K> for HashSeen<K>
where
  K: core::hash::Hash + Eq + Clone,
{
  #[inline]
  fn empty() -> Self {
    Self(HashSet::new())
  }

  #[inline]
  fn admit(&mut self, key: &K) -> bool {
    if self.0.contains(key) {
      return false;
    }
    self.0.insert(key.clone());
    true
  }
}

/// `dedup(eq)` — membership through a list walked by field-wise equality.
///
/// Quadratic in the number of SURVIVORS, and that is stated rather than hidden: it is the price of
/// asking only [`PartialEq`] of the key, and the survivor count is bounded by what a retrieve
/// returns rather than by the corpus. A declaration reaches for this word when its key cannot hash,
/// which is exactly when the alternative is not retrieving at all.
#[derive(Debug)]
pub struct EqSeen<K>(Vec<K>);

impl<K> Seen<K> for EqSeen<K>
where
  K: PartialEq + Clone,
{
  #[inline]
  fn empty() -> Self {
    Self(Vec::new())
  }

  #[inline]
  fn admit(&mut self, key: &K) -> bool {
    if self.0.iter().any(|seen| seen == key) {
      return false;
    }
    self.0.push(key.clone());
    true
  }
}

#[cfg(test)]
mod tests;