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 quiet-window debounce: a burst on one key becomes one intake.

use core::{hash::Hash, time::Duration};
use std::{
  collections::{BTreeMap, HashMap},
  time::Instant,
};

#[cfg(test)]
mod tests;

/// Where one pending key sits in the schedule: WHEN it ripens, and a sequence number underneath.
///
/// The sequence number is not a tiebreak for convenience — it is what makes the slot a KEY. Two keys
/// touched at the same `now` (a driver that reads the clock once per loop turn does this constantly)
/// would collide on the instant alone, and a map keyed on instants would need a bucket per instant
/// and a linear scan to take one key out of it. With the counter in the key there is exactly one
/// schedule entry per pending key, removable in `O(log n)` by the slot the index remembers.
///
/// Derived [`Ord`] compares `at` first and `seq` second, so the schedule's order is *ripening time,
/// then touch order* — which is also why the ripe list comes back in a deterministic order rather
/// than a hash one.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Slot {
  at: Instant,
  seq: u64,
}

/// Keys that ripen once they have been quiet for a window — a burst on one key is one intake.
///
/// [`touch`](Self::touch) RESETS the touched key's window rather than extending a shared one, so
/// `create` + `modify` + `modify` on an asset ripens once, at the last modify plus the window, and a
/// key nobody re-touched ripens on its own schedule regardless of how busy its neighbours are.
///
/// # The schedule is exact, and that is what makes the deadline honest
///
/// Two structures over the same set: an index from key to its slot, and the schedule from slot to
/// key. A re-touch REMOVES the key's old slot before inserting its new one, so the schedule never
/// holds an entry that has been superseded — and [`deadline`](Self::deadline) can therefore return
/// its head, `O(1)`, and have that head be the true earliest ripening.
///
/// The alternative — leaving superseded entries in place and skipping them at the far end — costs
/// the same asymptotics on the way in and a truthful deadline on the way out. A head that may be
/// stale is either scanned past on every call, which turns a burst of *n* touches into `O(n²)` of
/// looking, or believed, which wakes the driving loop once per superseded entry: a thousand
/// filesystem events on one file become a thousand wake-ups that find nothing. Removing on the way
/// in costs one extra `O(log n)` and makes both problems not exist.
///
/// A burst of *n* touches is `O(n log n)` either way, and nothing is ever rebuilt.
///
/// See the [module note](super) for the loop that drives this and for why nothing here reads a
/// clock.
#[derive(Debug)]
pub struct Debounce<K> {
  quiet: Duration,
  // The two halves of one set, and the invariant they are kept under is that they have the same
  // size: every pending key has exactly one slot, and every slot's key is pending.
  pending: HashMap<K, Slot>,
  due: BTreeMap<Slot, K>,
  // Only ever up. A reused sequence number would let a stale slot address a live entry, which is the
  // same reason the ack windows one layer over mint item ids from a counter rather than a slab.
  next_seq: u64,
}

impl<K> Debounce<K> {
  /// A debounce whose keys ripen `quiet` after their last touch.
  ///
  /// Not `const`, where [`Batcher::new`](super::Batcher::new) is: the index is a [`HashMap`], whose
  /// `new` is not a `const fn` on stable because the default hasher's state is not one.
  #[must_use]
  pub fn new(quiet: Duration) -> Self {
    Self {
      quiet,
      pending: HashMap::new(),
      due: BTreeMap::new(),
      next_seq: 0,
    }
  }

  /// The window a key must stay untouched for before it ripens.
  #[must_use]
  pub const fn quiet(&self) -> Duration {
    self.quiet
  }

  /// How many keys are pending — counted per KEY, so a burst on one of them counts once.
  #[must_use]
  pub fn len(&self) -> usize {
    self.pending.len()
  }

  /// Whether nothing is pending.
  #[must_use]
  pub fn is_empty(&self) -> bool {
    self.pending.is_empty()
  }

  /// The earliest instant at which any key ripens, or `None` where nothing is pending.
  ///
  /// This is the instant a driving loop parks until, and it is the TRUE earliest: a re-touched key
  /// leaves no superseded entry behind to be woken for. `None` says *park on arrivals alone*.
  #[must_use]
  pub fn deadline(&self) -> Option<Instant> {
    self.due.first_key_value().map(|(slot, _)| slot.at)
  }
}

impl<K: Hash + Eq> Debounce<K> {
  /// Every key whose window has elapsed by `now`, in ripening order, removed from the pending set.
  ///
  /// A key comes back exactly once per window: taking it here clears it, and the next
  /// [`touch`](Self::touch) opens a fresh window rather than resuming the old one.
  #[must_use = "the ripe keys are removed from the pending set — dropping them drops the intake"]
  pub fn ripe(&mut self, now: Instant) -> Vec<K> {
    let mut ripe = Vec::new();
    while let Some(head) = self.due.first_entry() {
      if head.key().at > now {
        break;
      }
      let key = head.remove();
      self.pending.remove(&key);
      ripe.push(key);
    }
    ripe
  }

  /// Drop `key`'s pending intake, answering whether there was one.
  ///
  /// What a retirement arriving mid-window spends: the work the burst was going to ask for is no
  /// longer wanted, and cancelling it is cheaper and more honest than letting it ripen into an
  /// analysis of something that has just been retired.
  pub fn cancel(&mut self, key: &K) -> bool {
    match self.pending.remove(key) {
      Some(slot) => {
        self.due.remove(&slot);
        true
      }
      None => false,
    }
  }
}

impl<K: Hash + Eq + Clone> Debounce<K> {
  /// Note activity on `key` at `now`: its window RESTARTS, ripening it `quiet` from here.
  ///
  /// One clone per touch, and it is the key's cost of appearing in both halves of the schedule —
  /// the index that finds its slot, and the schedule that orders it.
  ///
  /// An unrepresentable sum — an absurd `quiet` against an `Instant` near its platform ceiling —
  /// ripens the key at `now` instead. Degrading to *no debouncing* still does the work; the other
  /// direction would swallow the key forever.
  pub fn touch(&mut self, key: K, now: Instant) {
    let slot = Slot {
      at: now.checked_add(self.quiet).unwrap_or(now),
      seq: self.next_seq,
    };
    self.next_seq += 1;
    if let Some(superseded) = self.pending.insert(key.clone(), slot) {
      self.due.remove(&superseded);
    }
    self.due.insert(slot, key);
  }
}