use std::{
collections::{BTreeMap, HashMap, VecDeque},
time::Instant,
vec::Vec,
};
use crate::{
event::{Event, EventKind},
options::{Debounce, DebounceConfig},
subscription::Subscription,
};
#[cfg(test)]
mod tests;
type Key<C> = (Subscription, Vec<C>);
#[derive(Debug, Clone)]
struct Buffered<C, V> {
first_seen: Instant,
emit_at: Instant,
seq: u64,
event: Event<C, V>,
}
enum Collapse {
KeepBuffered,
ReplaceWithIncoming,
BecomeModified,
Annihilate,
}
#[derive(Debug)]
pub(crate) struct Coalescer<C, V> {
default: Option<DebounceConfig>,
policies: HashMap<Subscription, Option<DebounceConfig>>,
per_sub_len: HashMap<Subscription, usize>,
buffer: BTreeMap<Key<C>, Buffered<C, V>>,
ready: VecDeque<(Instant, Event<C, V>)>,
next_seq: u64,
}
impl<C, V> Coalescer<C, V>
where
C: Ord + Clone,
V: Clone,
{
pub(crate) fn new(default: Option<DebounceConfig>) -> Self {
Self {
default,
policies: HashMap::new(),
per_sub_len: HashMap::new(),
buffer: BTreeMap::new(),
ready: VecDeque::new(),
next_seq: 0,
}
}
pub(crate) fn set_policy(&mut self, sub: Subscription, policy: Debounce) {
match policy {
Debounce::Inherit => {
self.policies.remove(&sub);
}
Debounce::Off => {
self.policies.insert(sub, None);
}
Debounce::Custom(config) => {
self.policies.insert(sub, Some(config));
}
}
}
pub(crate) fn forget_subscription(&mut self, sub: Subscription) {
self.drop_subscription(sub);
self.policies.remove(&sub);
}
fn effective_policy(&self, sub: Subscription) -> Option<DebounceConfig> {
match self.policies.get(&sub) {
Some(policy) => *policy,
None => self.default,
}
}
fn structural_cap(&self) -> usize {
self
.default
.map_or(DebounceConfig::DEFAULT_MAX_BUFFERED, |config| {
config.max_buffered()
})
}
#[cfg(test)]
pub(crate) fn has_policy(&self, sub: Subscription) -> bool {
self.policies.contains_key(&sub)
}
fn bump_seq(&mut self) -> u64 {
let seq = self.next_seq;
self.next_seq += 1;
seq
}
#[must_use = "an overflowed subscription is owed a dominating parked Rescan"]
pub(crate) fn admit(&mut self, ev: Event<C, V>, now: Instant) -> Option<Subscription> {
if ev.is_rescan() {
self.flush_subscription(ev.subscription(), now);
self.ready.push_back((now, ev));
None
} else if ev.move_from().is_some() {
self.flush_subscription(ev.subscription(), now);
self.ready.push_back((now, ev));
None
} else if matches!(
ev.kind(),
EventKind::Created | EventKind::Modified | EventKind::Removed
) {
match self.effective_policy(ev.subscription()) {
None => {
self.ready.push_back((now, ev));
None
}
Some(config) => self.coalesce(ev, now, config),
}
} else {
self.flush_subscription(ev.subscription(), now);
self.ready.push_back((now, ev));
None
}
}
pub(crate) fn next_deadline(&self) -> Option<Instant> {
let buffered = self.buffer.values().map(|b| b.emit_at).min();
let ready = self.ready.front().map(|(at, _)| *at);
match (buffered, ready) {
(Some(a), Some(b)) => Some(a.min(b)),
(a, b) => a.or(b),
}
}
pub(crate) fn drain_ready(&mut self, now: Instant, out: &mut Vec<Event<C, V>>) {
while let Some((at, _)) = self.ready.front() {
if *at <= now {
let (_, event) = self.ready.pop_front().expect("front just observed");
out.push(event);
} else {
break;
}
}
let mut due: Vec<(Subscription, u64, Key<C>)> = self
.buffer
.iter()
.filter(|(_, b)| b.emit_at <= now)
.map(|(k, b)| (k.0, b.seq, k.clone()))
.collect();
due.sort_by_key(|(sub, seq, _)| (*sub, *seq));
for (_, _, key) in due {
let entry = self.buffer.remove(&key).expect("key just collected");
self.dec_per_sub(key.0);
out.push(entry.event);
}
}
pub(crate) fn flush_all(&mut self, out: &mut Vec<Event<C, V>>) {
out.extend(self.ready.drain(..).map(|(_, event)| event));
let mut tail: Vec<(Subscription, u64, Event<C, V>)> = std::mem::take(&mut self.buffer)
.into_iter()
.map(|((sub, _path), b)| (sub, b.seq, b.event))
.collect();
tail.sort_by_key(|(sub, seq, _)| (*sub, *seq));
out.extend(tail.into_iter().map(|(_, _, event)| event));
self.per_sub_len.clear();
}
fn coalesce(
&mut self,
ev: Event<C, V>,
now: Instant,
config: DebounceConfig,
) -> Option<Subscription> {
let key = (ev.subscription(), ev.key().to_vec());
let (quiet, max_hold) = (config.quiet_window(), config.max_hold());
let seq = self.bump_seq();
let Some(buffered) = self.buffer.get_mut(&key) else {
let sub = ev.subscription();
if self.buffer.len() >= self.structural_cap() {
return Some(sub);
}
if self.per_sub_len.get(&sub).copied().unwrap_or(0) >= config.max_buffered() {
return Some(sub);
}
let entry = Buffered {
first_seen: now,
emit_at: Self::deadline(now, now, quiet, max_hold),
seq,
event: ev,
};
self.buffer.insert(key, entry);
*self.per_sub_len.entry(sub).or_insert(0) += 1;
return None;
};
let first_seen = buffered.first_seen;
match Self::collapse(buffered.event.kind(), ev.kind()) {
Collapse::KeepBuffered => {
buffered.event.set_epoch(ev.epoch());
buffered.emit_at = Self::deadline(first_seen, now, quiet, max_hold);
buffered.seq = seq;
}
Collapse::ReplaceWithIncoming => {
buffered.event = ev;
buffered.emit_at = Self::deadline(first_seen, now, quiet, max_hold);
buffered.seq = seq;
}
Collapse::BecomeModified => {
let mut synthetic = Event::synthetic(
ev.subscription(),
ev.key().to_vec(),
ev.location().clone(),
EventKind::Modified,
ev.epoch(),
);
synthetic.set_value(ev.value().cloned());
buffered.event = synthetic;
buffered.emit_at = Self::deadline(first_seen, now, quiet, max_hold);
buffered.seq = seq;
}
Collapse::Annihilate => {
self.buffer.remove(&key);
self.dec_per_sub(key.0);
}
}
None
}
fn dec_per_sub(&mut self, sub: Subscription) {
use std::collections::hash_map::Entry;
match self.per_sub_len.entry(sub) {
Entry::Occupied(mut occupied) => {
let count = occupied.get_mut();
debug_assert!(*count > 0, "a zero fresh-entry count was left in the map");
*count = count.saturating_sub(1);
if *count == 0 {
occupied.remove();
}
}
Entry::Vacant(_) => {
debug_assert!(
false,
"a buffered entry was removed for a subscription with no fresh-entry count"
);
}
}
}
fn collapse(buffered: &EventKind<C>, incoming: &EventKind<C>) -> Collapse {
use EventKind::{Created, Modified, Removed};
match (buffered, incoming) {
(Created, Removed) => Collapse::Annihilate,
(Removed, Created) => Collapse::BecomeModified,
(Modified | Removed, Removed) | (Removed, Modified) => Collapse::ReplaceWithIncoming,
_ => Collapse::KeepBuffered,
}
}
fn deadline(
first_seen: Instant,
now: Instant,
quiet_window: core::time::Duration,
max_hold: core::time::Duration,
) -> Instant {
let settle = now.checked_add(quiet_window).unwrap_or_else(far_future);
let cap = first_seen.checked_add(max_hold).unwrap_or_else(far_future);
settle.min(cap)
}
pub(crate) fn flush_subscription(&mut self, sub: Subscription, now: Instant) {
let mut entries = self.subscription_entries(sub);
entries.sort_by_key(|(seq, _)| *seq);
let flushed = entries.len();
for (_, key) in entries {
let entry = self.buffer.remove(&key).expect("key just collected");
self.ready.push_back((now, entry.event));
}
let counted = self.per_sub_len.remove(&sub).unwrap_or(0);
debug_assert!(
counted == flushed,
"fresh-entry count drifted from the buffer: counted {counted}, flushed {flushed}"
);
}
pub(crate) fn drop_subscription(&mut self, sub: Subscription) {
let entries = self.subscription_entries(sub);
let dropped = entries.len();
for (_, key) in entries {
self.buffer.remove(&key);
}
let counted = self.per_sub_len.remove(&sub).unwrap_or(0);
debug_assert!(
counted == dropped,
"fresh-entry count drifted from the buffer: counted {counted}, dropped {dropped}"
);
self.ready.retain(|(_, event)| event.subscription() != sub);
}
fn subscription_entries(&self, sub: Subscription) -> Vec<(u64, Key<C>)> {
self
.buffer
.range((sub, Vec::new())..)
.take_while(|((s, _), _)| *s == sub)
.map(|(k, b)| (b.seq, k.clone()))
.collect()
}
}
fn far_future() -> Instant {
Instant::now() + std::time::Duration::from_secs(100 * 365 * 24 * 60 * 60)
}