use core::{hash::Hash, num::NonZeroU64};
use std::{collections::HashMap, sync::Arc, vec::Vec};
use arc_swap::ArcSwap;
use iradix::sync::Radix;
use tributary_proto::ScopeId;
use crate::{
interest::Interest,
subscription::{InstanceId, Subscription},
view::WatchView,
};
#[cfg(test)]
mod tests;
pub(crate) struct Published<C, V, H> {
pub(crate) roots: Radix<C, RootRecord<C, H>>,
pub(crate) covers: Radix<C, CoverEntry<V>>,
}
#[derive(Clone)]
pub(crate) struct CoverEntry<V> {
subs: Vec<(Subscription, V)>,
}
impl<V> CoverEntry<V> {
fn new() -> Self {
Self { subs: Vec::new() }
}
fn push(&mut self, sub: Subscription, value: V) {
self.subs.push((sub, value));
}
fn remove_all(&mut self, departing: &std::collections::HashSet<Subscription>) {
self.subs.retain(|(sub, _)| !departing.contains(sub));
}
fn remove(&mut self, sub: Subscription) {
self.subs.retain(|(s, _)| *s != sub);
}
fn is_empty(&self) -> bool {
self.subs.is_empty()
}
pub(crate) fn value(&self) -> &V {
&self
.subs
.iter()
.max_by_key(|(sub, _)| *sub)
.expect("a present cover entry holds at least one live subscription")
.1
}
pub(crate) fn value_of(&self, sub: Subscription) -> Option<&V> {
self
.subs
.iter()
.find(|(s, _)| *s == sub)
.map(|(_, value)| value)
}
}
pub(crate) type Shared<C, V, H> = Arc<ArcSwap<Published<C, V, H>>>;
#[derive(Debug, Clone)]
pub(crate) struct RootRecord<C, H> {
pub(crate) key: Vec<C>,
pub(crate) handle: H,
pub(crate) subscribers: Vec<Subscription>,
pub(crate) retained_cover: Option<Vec<Vec<C>>>,
}
impl<C, H> RootRecord<C, H> {
fn covered_outside(&self, key: &[C]) -> bool
where
C: PartialEq,
{
self.retained_cover.as_ref().is_some_and(|cover| {
!cover
.iter()
.any(|prefix| key.starts_with(prefix.as_slice()))
})
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum WatchOutcome<C, H> {
Covered {
fs_root: H,
sub: Subscription,
outside_cover: bool,
},
Widen {
new_root_key: Vec<C>,
repointed: Vec<Subscription>,
unwatch: Vec<H>,
sub: Subscription,
},
Disjoint {
root_key: Vec<C>,
sub: Subscription,
},
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum UnwatchOutcome<C, H> {
Dropped {
shrink: Option<(H, Vec<Vec<C>>)>,
},
RootEmptied {
fs_root: H,
},
}
#[derive(Debug, Clone)]
struct SubRecord<C, H> {
root: H,
key: Vec<C>,
interest: Interest,
}
#[derive(Debug, Clone)]
struct PendingWatch<C, V> {
key: Vec<C>,
value: V,
interest: Interest,
}
pub(crate) struct Subsumer<C, V, H> {
index: Radix<C, RootRecord<C, H>>,
covers: Radix<C, CoverEntry<V>>,
by_handle: HashMap<H, Vec<C>>,
subs: HashMap<Subscription, SubRecord<C, H>>,
pending: HashMap<Subscription, PendingWatch<C, V>>,
instance: InstanceId,
next_sub: NonZeroU64,
shared: Shared<C, V, H>,
}
impl<C, V, H> core::fmt::Debug for Subsumer<C, V, H>
where
C: core::fmt::Debug,
V: core::fmt::Debug,
H: core::fmt::Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("Subsumer")
.field("by_handle", &self.by_handle)
.field("subs", &self.subs)
.field("pending", &self.pending)
.finish_non_exhaustive()
}
}
impl<C, V, H> Default for Subsumer<C, V, H>
where
C: Ord + Clone,
V: Clone,
H: Copy + Eq + Hash,
{
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<C, V, H> Subsumer<C, V, H> {
pub(crate) fn publish_empty(&self) {
self.shared.store(Arc::new(Published {
roots: Radix::new(),
covers: Radix::new(),
}));
}
}
impl<C, V, H> Subsumer<C, V, H>
where
C: Ord + Clone,
V: Clone,
H: Copy + Eq + Hash,
{
pub(crate) fn new() -> Self {
let index = Radix::new();
let covers = Radix::new();
let shared = Arc::new(ArcSwap::from_pointee(Published {
roots: index.clone(),
covers: covers.clone(),
}));
Self {
index,
covers,
by_handle: HashMap::new(),
subs: HashMap::new(),
pending: HashMap::new(),
instance: InstanceId::mint(),
next_sub: NonZeroU64::MIN,
shared,
}
}
pub(crate) fn instance(&self) -> InstanceId {
self.instance
}
pub(crate) fn view(&self) -> WatchView<C, V, H> {
WatchView::new(self.shared.clone())
}
fn publish(&self) {
self.shared.store(Arc::new(Published {
roots: self.index.clone(),
covers: self.covers.clone(),
}));
}
fn cover_add(&mut self, sub: Subscription, key: &[C], value: V) {
let mut txn = self.covers.txn();
let mut entry = txn.get(key).cloned().unwrap_or_else(CoverEntry::new);
entry.push(sub, value);
txn.insert(key, entry);
self.covers = txn.commit();
}
fn cover_remove(&mut self, sub: Subscription, key: &[C]) {
let mut txn = self.covers.txn();
if let Some(mut entry) = txn.get(key).cloned() {
entry.remove(sub);
if entry.is_empty() {
txn.remove(key);
} else {
txn.insert(key, entry);
}
}
self.covers = txn.commit();
}
pub(crate) fn plan_watch(
&mut self,
key: &[C],
value: V,
interest: Interest,
) -> WatchOutcome<C, H> {
let sub = self.mint_subscription();
self.pending.insert(
sub,
PendingWatch {
key: key.to_vec(),
value,
interest,
},
);
if let Some(record) = self.index.get_ancestor(key) {
let outside_cover = record.covered_outside(key);
return WatchOutcome::Covered {
fs_root: record.handle,
sub,
outside_cover,
};
}
let mut unwatch = Vec::new();
let mut repointed = Vec::new();
for record in self.index.descendants(key) {
repointed.extend_from_slice(&record.subscribers);
unwatch.push(record.handle);
}
if !unwatch.is_empty() {
return WatchOutcome::Widen {
new_root_key: key.to_vec(),
repointed,
unwatch,
sub,
};
}
WatchOutcome::Disjoint {
root_key: key.to_vec(),
sub,
}
}
pub(crate) fn commit_watch(
&mut self,
outcome: &WatchOutcome<C, H>,
fs_root: H,
fs_root_key: &[C],
) {
match outcome {
WatchOutcome::Covered { sub, .. } => {
let PendingWatch {
key,
value,
interest,
} = self.take_pending(*sub);
let root_key = self
.by_handle
.get(&fs_root)
.expect("covered root is live")
.clone();
let mut txn = self.index.txn();
let mut record = txn.get(&root_key).expect("covered root record").clone();
record.subscribers.push(*sub);
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
self.cover_add(*sub, &key, value);
self.subs.insert(
*sub,
SubRecord {
root: fs_root,
key,
interest,
},
);
self.publish();
}
WatchOutcome::Disjoint { sub, .. } => {
let PendingWatch {
value, interest, ..
} = self.take_pending(*sub);
let root_key = fs_root_key.to_vec();
let record = RootRecord {
key: root_key.clone(),
handle: fs_root,
subscribers: std::vec![*sub],
retained_cover: None,
};
let mut txn = self.index.txn();
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
self.by_handle.insert(fs_root, root_key.clone());
self.cover_add(*sub, &root_key, value);
self.subs.insert(
*sub,
SubRecord {
root: fs_root,
key: root_key,
interest,
},
);
self.publish();
}
WatchOutcome::Widen {
repointed,
unwatch,
sub,
..
} => {
let PendingWatch {
value, interest, ..
} = self.take_pending(*sub);
let root_key = fs_root_key.to_vec();
let mut subscribers = repointed.clone();
subscribers.push(*sub);
let record = RootRecord {
key: root_key.clone(),
handle: fs_root,
subscribers,
retained_cover: None,
};
let mut txn = self.index.txn();
txn.remove_descendants(root_key.as_slice());
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
for old in unwatch {
self.by_handle.remove(old);
}
self.by_handle.insert(fs_root, root_key.clone());
for &moved in repointed {
self
.subs
.get_mut(&moved)
.expect("re-pointed subscription is live")
.root = fs_root;
}
self.cover_add(*sub, &root_key, value);
self.subs.insert(
*sub,
SubRecord {
root: fs_root,
key: root_key,
interest,
},
);
self.publish();
}
}
}
pub(crate) fn abort_watch(&mut self, outcome: &WatchOutcome<C, H>) {
let sub = match outcome {
WatchOutcome::Covered { sub, .. }
| WatchOutcome::Widen { sub, .. }
| WatchOutcome::Disjoint { sub, .. } => *sub,
};
self.pending.remove(&sub);
}
pub(crate) fn plan_unwatch(&mut self, sub: Subscription) -> Option<UnwatchOutcome<C, H>> {
let record = self.subs.remove(&sub)?;
let root_key = self
.by_handle
.get(&record.root)
.expect("live subscription's root is live")
.clone();
let mut txn = self.index.txn();
let mut root = txn.get(&root_key).expect("live root record").clone();
root.subscribers.retain(|&s| s != sub);
let emptied = root.subscribers.is_empty();
let survivors = root.subscribers.clone();
if emptied {
txn.remove(root_key.as_slice());
} else {
txn.insert(root_key.as_slice(), root);
}
self.index = txn.commit();
self.cover_remove(sub, &record.key);
let outcome = if emptied {
self.by_handle.remove(&record.root);
UnwatchOutcome::RootEmptied {
fs_root: record.root,
}
} else {
let shrink = self.detect_shrink(&root_key, record.root, &survivors);
UnwatchOutcome::Dropped { shrink }
};
self.publish();
Some(outcome)
}
fn detect_shrink(
&self,
root_key: &[C],
root_handle: H,
survivors: &[Subscription],
) -> Option<(H, Vec<Vec<C>>)> {
let survivor_keys: Vec<Vec<C>> = survivors
.iter()
.map(|s| {
self
.subs
.get(s)
.map(|record| record.key.clone())
.expect("a surviving subscriber is live in the side table")
})
.collect();
let recorded = self
.index
.get(root_key)
.and_then(|record| record.retained_cover.clone());
match recorded {
None => {
if survivor_keys.iter().any(|key| key.as_slice() == root_key) {
return None;
}
Some((root_handle, antichain(survivor_keys)))
}
Some(cover) => {
let survivor_antichain = antichain(survivor_keys);
let contained = survivor_antichain
.iter()
.all(|key| cover.iter().any(|c| key.starts_with(c.as_slice())));
(contained && survivor_antichain != cover).then_some((root_handle, survivor_antichain))
}
}
}
pub(crate) fn retained_cover_for(
&self,
handle: H,
newcomer: Option<&[C]>,
) -> Option<Vec<Vec<C>>> {
let root_key = self.by_handle.get(&handle)?;
let record = self.index.get(root_key)?;
let mut subscriber_keys: Vec<Vec<C>> = record
.subscribers
.iter()
.map(|s| {
self
.subs
.get(s)
.map(|sub_record| sub_record.key.clone())
.expect("a live root's subscriber is live in the side table")
})
.collect();
if let Some(extra) = newcomer {
subscriber_keys.push(extra.to_vec());
}
if subscriber_keys
.iter()
.any(|key| key.as_slice() == root_key.as_slice())
{
return None;
}
Some(antichain(subscriber_keys))
}
pub(crate) fn set_retained_cover(&mut self, handle: H, cover: Option<Vec<Vec<C>>>) {
let Some(root_key) = self.by_handle.get(&handle).cloned() else {
return;
};
let mut txn = self.index.txn();
let Some(mut record) = txn.get(&root_key).cloned() else {
return;
};
record.retained_cover = cover;
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
self.publish();
}
pub(crate) fn degrade_retained_cover(&mut self, handle: H) {
let Some(root_key) = self.by_handle.get(&handle).cloned() else {
return;
};
let Some(record) = self.index.get(&root_key) else {
return;
};
if record.retained_cover.as_ref().is_none_or(Vec::is_empty) {
return;
}
let mut record = record.clone();
record.retained_cover = Some(Vec::new());
let mut txn = self.index.txn();
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
self.publish();
}
#[cfg(test)]
pub(crate) fn retained_cover_of(&self, handle: H) -> Option<Vec<Vec<C>>> {
let root_key = self.by_handle.get(&handle)?;
self.index.get(root_key)?.retained_cover.clone()
}
pub(crate) fn entry(&self, fs_root: H) -> Option<&RootRecord<C, H>> {
let key = self.by_handle.get(&fs_root)?;
self.index.get(key)
}
pub(crate) fn force_remove_root(&mut self, handle: H) -> Vec<Subscription> {
let Some(root_key) = self.by_handle.remove(&handle) else {
return Vec::new();
};
let mut txn = self.index.txn();
let record = txn
.remove(root_key.as_slice())
.expect("force-removed root record");
self.index = txn.commit();
let mut departing_by_key: std::collections::BTreeMap<
Vec<C>,
std::collections::HashSet<Subscription>,
> = std::collections::BTreeMap::new();
for &sub in &record.subscribers {
if let Some(sub_record) = self.subs.remove(&sub) {
departing_by_key
.entry(sub_record.key)
.or_default()
.insert(sub);
}
}
let mut txn = self.covers.txn();
for (key, departing) in departing_by_key {
if let Some(mut entry) = txn.get(&key).cloned() {
entry.remove_all(&departing);
if entry.is_empty() {
txn.remove(&key);
} else {
txn.insert(key.as_slice(), entry);
}
}
}
self.covers = txn.commit();
self.publish();
record.subscribers
}
pub(crate) fn rebind_root(&mut self, old: H, new: H) {
let Some(root_key) = self.by_handle.get(&old).cloned() else {
return;
};
let mut txn = self.index.txn();
let Some(mut record) = txn.get(&root_key).cloned() else {
return;
};
record.handle = new;
let subscribers = record.subscribers.clone();
txn.insert(root_key.as_slice(), record);
self.index = txn.commit();
self.by_handle.remove(&old);
self.by_handle.insert(new, root_key);
for sub in subscribers {
if let Some(side) = self.subs.get_mut(&sub) {
side.root = new;
}
}
self.publish();
}
pub(crate) fn subscription_key(&self, sub: Subscription) -> Option<&[C]> {
self.subs.get(&sub).map(|record| record.key.as_slice())
}
pub(crate) fn subscription_root(&self, sub: Subscription) -> Option<H>
where
H: Copy,
{
self.subs.get(&sub).map(|record| record.root)
}
pub(crate) fn subscription_interest(&self, sub: Subscription) -> Option<Interest> {
self.subs.get(&sub).map(|record| record.interest)
}
pub(crate) fn subscription_value(&self, sub: Subscription) -> Option<&V> {
let key = self.subs.get(&sub)?.key.as_slice();
self.covers.get(key)?.value_of(sub)
}
pub(crate) fn fs_path_preserves_plan(&self, fs_root_key: &[C], planned_unwatch: &[H]) -> bool {
if self.index.get_ancestor(fs_root_key).is_some() {
return false;
}
let now: std::collections::HashSet<H> = self
.index
.descendants(fs_root_key)
.map(|record| record.handle)
.collect();
let planned: std::collections::HashSet<H> = planned_unwatch.iter().copied().collect();
now == planned
}
#[cfg(all(test, feature = "tokio"))]
pub(crate) fn pending_len(&self) -> usize {
self.pending.len()
}
#[cfg(test)]
pub(crate) fn roots(&self) -> impl Iterator<Item = (&[C], H)> {
self
.index
.values()
.map(|record| (record.key.as_slice(), record.handle))
}
fn mint_subscription(&mut self) -> Subscription {
let next = self.next_sub;
self.next_sub = self
.next_sub
.checked_add(1)
.expect("subscription id space (u64) exhausted");
Subscription::new(self.instance, ScopeId::new(next))
}
fn take_pending(&mut self, sub: Subscription) -> PendingWatch<C, V> {
self
.pending
.remove(&sub)
.expect("commit_watch consumes its own plan's pending entry (not yet aborted)")
}
}
fn antichain<C: Ord + Clone>(mut keys: Vec<Vec<C>>) -> Vec<Vec<C>> {
keys.sort();
keys.dedup();
keys
.iter()
.filter(|key| {
!keys
.iter()
.any(|other| other.len() < key.len() && key.starts_with(other.as_slice()))
})
.cloned()
.collect()
}