use core::{
fmt,
num::NonZeroUsize,
str::FromStr,
sync::atomic::{AtomicU64, Ordering},
time::Duration,
};
use std::{
any::Any,
collections::{BTreeMap, HashMap, hash_map::RandomState},
hash::{BuildHasher, Hasher},
sync::{Arc, Mutex},
time::Instant,
};
pub const DEFAULT_SNAPSHOT_CAPACITY: NonZeroUsize = match NonZeroUsize::new(128) {
Some(capacity) => capacity,
None => unreachable!(),
};
pub const DEFAULT_SNAPSHOT_TTL: Duration = Duration::from_secs(300);
pub const DEFAULT_SNAPSHOT_DEPTH: NonZeroUsize = match NonZeroUsize::new(1000) {
Some(depth) => depth,
None => unreachable!(),
};
const VERSION: u8 = 1;
const FRAME: usize = 1 + IDENTITY + 8 + 8;
const IDENTITY: usize = 16;
static SERIAL: AtomicU64 = AtomicU64::new(0);
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct KeeperId([u8; IDENTITY]);
impl KeeperId {
fn fresh() -> Self {
let mut bytes = [0_u8; IDENTITY];
let serial = SERIAL.fetch_add(1, Ordering::Relaxed);
for (half, slot) in bytes.as_chunks_mut::<8>().0.iter_mut().enumerate() {
let mut hasher = RandomState::new().build_hasher();
hasher.write_u64(serial);
hasher.write_usize(half);
*slot = hasher.finish().to_be_bytes();
}
Self(bytes)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct PageToken {
keeper: KeeperId,
snapshot: u64,
from: u64,
}
impl PageToken {
const fn new(keeper: KeeperId, snapshot: u64, from: u64) -> Self {
Self {
keeper,
snapshot,
from,
}
}
#[inline]
#[must_use]
pub const fn walked(&self) -> u64 {
self.from
}
fn frame(&self) -> [u8; FRAME] {
let mut bytes = [0_u8; FRAME];
bytes[0] = VERSION;
bytes[1..1 + IDENTITY].copy_from_slice(&self.keeper.0);
bytes[1 + IDENTITY..9 + IDENTITY].copy_from_slice(&self.snapshot.to_be_bytes());
bytes[9 + IDENTITY..FRAME].copy_from_slice(&self.from.to_be_bytes());
bytes
}
}
impl fmt::Display for PageToken {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&crate::cursor::text::encode(&self.frame()))
}
}
impl FromStr for PageToken {
type Err = PageTokenRefusal;
fn from_str(text: &str) -> Result<Self, Self::Err> {
let bytes = crate::cursor::text::decode(text).ok_or(PageTokenRefusal::Malformed)?;
let frame: [u8; FRAME] = bytes.as_slice().try_into().map_err(|_| {
PageTokenRefusal::Malformed
})?;
if frame[0] != VERSION {
return Err(PageTokenRefusal::Malformed);
}
let mut keeper = [0_u8; IDENTITY];
keeper.copy_from_slice(&frame[1..1 + IDENTITY]);
let mut snapshot = [0_u8; 8];
snapshot.copy_from_slice(&frame[1 + IDENTITY..9 + IDENTITY]);
let mut from = [0_u8; 8];
from.copy_from_slice(&frame[9 + IDENTITY..FRAME]);
Ok(Self::new(
KeeperId(keeper),
u64::from_be_bytes(snapshot),
u64::from_be_bytes(from),
))
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum PageTokenRefusal {
Malformed,
Foreign,
Expired,
Unknown,
Crossed {
minted_at: &'static str,
asked_at: String,
},
}
impl fmt::Display for PageTokenRefusal {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Malformed => f.write_str("this is not a page token this build wrote"),
Self::Foreign => f.write_str(
"this page token was minted by another keeper and its answer is not held here — ask the \
question again",
),
Self::Expired => {
f.write_str("this page token's answer has expired — ask the question again for a fresh one")
}
Self::Unknown => f.write_str(
"this page token's answer is no longer held — ask the question again for a fresh one",
),
Self::Crossed {
minted_at,
asked_at,
} => write!(
f,
"this page token was minted at `{minted_at}` and cannot be handed back to `{asked_at}`",
),
}
}
}
impl core::error::Error for PageTokenRefusal {}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Stretch<T> {
rows: Vec<T>,
next: Option<PageToken>,
}
impl<T> Stretch<T> {
#[inline]
#[must_use]
pub const fn empty() -> Self {
Self {
rows: Vec::new(),
next: None,
}
}
#[inline]
#[must_use]
pub fn rows(&self) -> &[T] {
&self.rows
}
#[inline]
#[must_use]
pub const fn next(&self) -> Option<&PageToken> {
self.next.as_ref()
}
#[inline]
#[must_use]
pub fn into_components(self) -> (Vec<T>, Option<PageToken>) {
(self.rows, self.next)
}
}
struct Kept {
rows: Box<dyn Any + Send>,
road: &'static str,
born: Instant,
touched: u64,
}
struct Store {
kept: HashMap<u64, Kept>,
recency: BTreeMap<u64, u64>,
clock: u64,
serial: u64,
}
pub struct SnapshotKeeper {
identity: KeeperId,
store: Arc<Mutex<Store>>,
capacity: NonZeroUsize,
ttl: Duration,
depth: NonZeroUsize,
}
impl SnapshotKeeper {
#[must_use]
pub fn new() -> Self {
Self {
identity: KeeperId::fresh(),
store: Arc::new(Mutex::new(Store {
kept: HashMap::new(),
recency: BTreeMap::new(),
clock: 0,
serial: 0,
})),
capacity: DEFAULT_SNAPSHOT_CAPACITY,
ttl: DEFAULT_SNAPSHOT_TTL,
depth: DEFAULT_SNAPSHOT_DEPTH,
}
}
#[must_use]
pub const fn with_capacity(mut self, capacity: NonZeroUsize) -> Self {
self.capacity = capacity;
self
}
#[must_use]
pub const fn with_ttl(mut self, ttl: Duration) -> Self {
self.ttl = ttl;
self
}
#[must_use]
pub const fn with_depth(mut self, depth: NonZeroUsize) -> Self {
self.depth = depth;
self
}
#[inline]
#[must_use]
pub const fn capacity(&self) -> NonZeroUsize {
self.capacity
}
#[inline]
#[must_use]
pub const fn ttl(&self) -> Duration {
self.ttl
}
#[inline]
#[must_use]
pub const fn depth(&self) -> NonZeroUsize {
self.depth
}
#[must_use]
pub fn held(&self) -> usize {
let mut store = self.locked();
self.sweep(&mut store);
store.kept.len()
}
pub fn keep<T>(&self, road: &'static str, rows: Vec<T>) -> PageToken
where
T: Send + 'static,
{
let mut store = self.locked();
self.sweep(&mut store);
while store.kept.len() >= self.capacity.get() {
let Some((&touched, &oldest)) = store.recency.iter().next() else {
break;
};
store.recency.remove(&touched);
store.kept.remove(&oldest);
}
let snapshot = store.serial;
store.serial = store.serial.wrapping_add(1);
let touched = store.clock;
store.clock = store.clock.wrapping_add(1);
store.recency.insert(touched, snapshot);
store.kept.insert(
snapshot,
Kept {
rows: Box::new(rows),
road,
born: Instant::now(),
touched,
},
);
PageToken::new(self.identity, snapshot, 0)
}
pub fn read<T>(
&self,
page_token: &PageToken,
road: &str,
want: NonZeroUsize,
) -> Result<Stretch<T>, PageTokenRefusal>
where
T: Clone + Send + 'static,
{
if page_token.keeper != self.identity {
return Err(PageTokenRefusal::Foreign);
}
let mut store = self.locked();
let answer = self.cut(&mut store, page_token, road, want);
self.sweep(&mut store);
answer
}
fn cut<T>(
&self,
store: &mut Store,
page_token: &PageToken,
road: &str,
want: NonZeroUsize,
) -> Result<Stretch<T>, PageTokenRefusal>
where
T: Clone + Send + 'static,
{
let Some(kept) = store.kept.get(&page_token.snapshot) else {
return Err(PageTokenRefusal::Unknown);
};
if kept.born.elapsed() > self.ttl {
let touched = kept.touched;
store.kept.remove(&page_token.snapshot);
store.recency.remove(&touched);
return Err(PageTokenRefusal::Expired);
}
let crossed = || PageTokenRefusal::Crossed {
minted_at: kept.road,
asked_at: road.to_owned(),
};
if kept.road != road {
return Err(crossed());
}
let rows = kept.rows.downcast_ref::<Vec<T>>().ok_or_else(crossed)?;
let from = usize::try_from(page_token.from)
.unwrap_or(usize::MAX)
.min(rows.len());
let to = from.saturating_add(want.get()).min(rows.len());
let stretch = rows[from..to].to_vec();
let next = (to < rows.len()).then(|| {
PageToken::new(
self.identity,
page_token.snapshot,
u64::try_from(to).unwrap_or(u64::MAX),
)
});
let touched = store.clock;
store.clock = store.clock.wrapping_add(1);
if let Some(kept) = store.kept.get_mut(&page_token.snapshot) {
let stale = core::mem::replace(&mut kept.touched, touched);
store.recency.remove(&stale);
store.recency.insert(touched, page_token.snapshot);
}
Ok(Stretch {
rows: stretch,
next,
})
}
fn sweep(&self, store: &mut Store) {
let ttl = self.ttl;
let dead: Vec<u64> = store
.kept
.iter()
.filter(|(_, kept)| kept.born.elapsed() > ttl)
.map(|(&snapshot, _)| snapshot)
.collect();
for snapshot in dead {
if let Some(kept) = store.kept.remove(&snapshot) {
store.recency.remove(&kept.touched);
}
}
}
fn locked(&self) -> std::sync::MutexGuard<'_, Store> {
self
.store
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner)
}
}
impl Default for SnapshotKeeper {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl Clone for SnapshotKeeper {
fn clone(&self) -> Self {
Self {
identity: self.identity,
store: Arc::clone(&self.store),
capacity: self.capacity,
ttl: self.ttl,
depth: self.depth,
}
}
}
impl fmt::Debug for SnapshotKeeper {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("SnapshotKeeper")
.field("capacity", &self.capacity)
.field("ttl", &self.ttl)
.field("depth", &self.depth)
.finish_non_exhaustive()
}
}
#[cfg(feature = "async-graphql")]
impl SnapshotKeeper {
#[must_use]
pub fn install<Q, M, S>(
self,
builder: async_graphql::SchemaBuilder<Q, M, S>,
) -> async_graphql::SchemaBuilder<Q, M, S>
where
Q: async_graphql::ObjectType + 'static,
M: async_graphql::ObjectType + 'static,
S: async_graphql::SubscriptionType + 'static,
{
builder.data(self)
}
}
#[cfg(feature = "async-graphql")]
pub fn installed_keeper<'ctx>(
ctx: &'ctx async_graphql::Context<'_>,
word: &str,
) -> async_graphql::Result<&'ctx SnapshotKeeper> {
async_graphql::Context::data_opt::<SnapshotKeeper>(ctx).ok_or_else(|| {
async_graphql::Error::new(format!(
"`{word}` pages a kept answer and this schema installed no keeper to hold one — the \
deployment writes `SnapshotKeeper::new().install(builder)` once",
))
})
}
#[cfg(test)]
mod tests;