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 JOIN's mechanism: [`Join`], and the two memberships a fused face chooses between.

use std::collections::HashMap;

/// Where each root already sits in the fold's accumulator — the join's one moving part.
///
/// # Why the mechanism is a parameter, and not a `HashMap` written into the fold
///
/// It is a BOUNDS choice on the ROOT type, which is the same choice [`Seen`](crate::Seen) already
/// carries for the key type one stage up. The dedup ruling settled it there — `dedup(hash)` wants
/// `Hash + Eq` and `dedup(eq)` asks only `PartialEq`, so *a key that cannot hash is retrievable* —
/// and a root key is a PREFIX of such a key, built out of the same segments, so it inherits the
/// property rather than escaping it. A fold that hardcoded a hash map would make a graph whose roots
/// do not hash unfusable while every one of its members retrieves.
///
/// | mechanism | what the root must satisfy |
/// |---|---|
/// | [`HashJoin`] | [`Hash`](core::hash::Hash) + [`Eq`] |
/// | [`EqJoin`] | [`PartialEq`] |
///
/// # The contract, which the fold depends on and cannot check
///
/// An implementor assigns indices DENSELY FROM ZERO in admission order: the first root it admits is
/// `0`, the next `1`, and a root it has already admitted answers with the index it was given. So
/// when [`place`](Self::place) answers `None`, the accumulator's current length IS the index that
/// root just took, and the fold pushes there.
///
/// Both shipped implementors get that for free by deriving the index from their own length, which
/// is why the contract is stated rather than defended: a mechanism that assigned indices some other
/// way would have to go out of its way to.
pub trait Join<R> {
  /// An empty membership.
  ///
  /// Declared here rather than through [`Default`] for [`Seen::empty`](crate::Seen::empty)'s reason:
  /// the fold mints one from the type parameter alone, and a derived `Default` on a root-holding
  /// collection would have demanded `R: Default` as well.
  fn empty() -> Self;

  /// Where `root` sits — or `None`, having admitted it at the next index.
  ///
  /// By reference because the fold keeps the root: what is stored here is the membership's own copy.
  fn place(&mut self, root: &R) -> Option<usize>;
}

/// The join through a [`HashMap`] — one hash and one bucket probe per contribution.
///
/// What every emitted root key satisfies today, and the mechanism a fused face takes unless its root
/// cannot hash.
#[derive(Debug)]
pub struct HashJoin<R>(HashMap<R, usize>);

impl<R> Join<R> for HashJoin<R>
where
  R: core::hash::Hash + Eq + Clone,
{
  #[inline]
  fn empty() -> Self {
    Self(HashMap::new())
  }

  #[inline]
  fn place(&mut self, root: &R) -> Option<usize> {
    if let Some(at) = self.0.get(root) {
      return Some(*at);
    }
    self.0.insert(root.clone(), self.0.len());
    None
  }
}

/// The join through a list walked by field-wise equality — quadratic in the number of DISTINCT
/// ROOTS, and that is stated rather than hidden.
///
/// The bound it asks is [`PartialEq`] alone, which is the whole point: a root carrying a float
/// coordinate or a foreign type with no `Hash` impl fuses through here and through nothing else. The
/// distinct-root count is bounded by the members' intake ceilings rather than by the corpus, so the
/// walk is bounded too — but it is the escape rather than the default, exactly as
/// [`EqSeen`](crate::EqSeen) is.
#[derive(Debug)]
pub struct EqJoin<R>(Vec<R>);

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

  #[inline]
  fn place(&mut self, root: &R) -> Option<usize> {
    if let Some(at) = self.0.iter().position(|seen| seen == root) {
      return Some(at);
    }
    self.0.push(root.clone());
    None
  }
}

#[cfg(test)]
mod tests;