use std::error;
use std::fmt;
use std::sync::{Arc, RwLock};
#[cfg(test)]
use std::sync::{Barrier, Mutex, TryLockError};
use super::item::Item;
use crate::redact::Locked;
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Version(u64);
impl Version {
pub const ZERO: Self = Self(0);
pub const MAX: Self = Self(u64::MAX);
#[must_use]
pub const fn from_u64(value: u64) -> Self {
Self(value)
}
#[must_use]
pub const fn as_u64(self) -> u64 {
self.0
}
fn checked_add(self, delta: u64) -> Option<Self> {
self.0.checked_add(delta).map(Self)
}
}
impl fmt::Display for Version {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.0.fmt(formatter)
}
}
#[derive(Clone, Debug)]
pub struct Snapshot {
version: Version,
items: Arc<Vec<Item>>,
}
impl Snapshot {
#[must_use]
pub fn new(version: Version, items: Vec<Item>) -> Self {
Self::from_shared(version, Arc::new(items))
}
const fn from_shared(version: Version, items: Arc<Vec<Item>>) -> Self {
Self { version, items }
}
pub(crate) fn with_version(self, version: Version) -> Self {
Self {
version,
items: self.items,
}
}
#[must_use]
pub const fn version(&self) -> Version {
self.version
}
#[must_use]
pub fn items(&self) -> &[Item] {
self.items.as_slice()
}
#[must_use]
pub fn into_parts(self) -> (Version, Vec<Item>) {
let items = Arc::try_unwrap(self.items).unwrap_or_else(|items| items.as_ref().clone());
(self.version, items)
}
#[cfg(test)]
pub(crate) fn shares_items_with(&self, other: &Self) -> bool {
Arc::ptr_eq(&self.items, &other.items)
}
#[cfg(test)]
pub(crate) fn items_backing_ptr(&self) -> *const Vec<Item> {
Arc::as_ptr(&self.items)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum Error {
#[non_exhaustive]
VersionConflict {
expected: Version,
actual: Version,
},
#[non_exhaustive]
VersionOverflow {
current: Version,
delta: u64,
},
Poisoned,
}
impl fmt::Display for Error {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::VersionConflict { expected, actual } => write!(
formatter,
"transcript version conflict: expected {expected}, actual {actual}"
),
Self::VersionOverflow { current, delta } => write!(
formatter,
"transcript version overflow: current {current}, increment {delta}"
),
Self::Poisoned => formatter.write_str("transcript store lock poisoned"),
}
}
}
impl error::Error for Error {}
struct State {
version: Version,
items: Arc<Vec<Item>>,
staged_tail: Option<Vec<Item>>,
}
impl State {
fn has_staged_items(&self) -> bool {
self.staged_tail
.as_ref()
.is_some_and(|tail| !tail.is_empty())
}
fn materialize_staged_items(&mut self) {
let Some(mut tail) = self.staged_tail.take() else {
return;
};
if tail.is_empty() {
self.staged_tail = Some(tail);
return;
}
Arc::make_mut(&mut self.items).append(&mut tail);
self.staged_tail = Some(Vec::new());
}
fn snapshot(&self) -> Snapshot {
debug_assert!(!self.has_staged_items());
Snapshot::from_shared(self.version, Arc::clone(&self.items))
}
fn into_snapshot(mut self) -> Snapshot {
self.materialize_staged_items();
Snapshot::from_shared(self.version, self.items)
}
fn into_snapshot_with_suffix(mut self, mut suffix: Vec<Item>) -> Snapshot {
if let Some(tail) = &mut self.staged_tail {
tail.append(&mut suffix);
} else {
Arc::make_mut(&mut self.items).append(&mut suffix);
}
self.into_snapshot()
}
}
struct Core {
state: RwLock<State>,
#[cfg(test)]
commit_overlap: Mutex<Option<Arc<CommitOverlap>>>,
}
#[cfg(test)]
struct CommitOverlap {
writer_ready: Barrier,
reader_contending: Barrier,
commit_release: Barrier,
}
#[cfg(test)]
impl CommitOverlap {
fn new() -> Self {
Self {
writer_ready: Barrier::new(2),
reader_contending: Barrier::new(3),
commit_release: Barrier::new(2),
}
}
}
#[cfg(test)]
pub(super) struct CommitOverlapControl {
overlap: Arc<CommitOverlap>,
}
#[cfg(test)]
impl CommitOverlapControl {
pub(super) fn wait_for_writer(&self) {
self.overlap.writer_ready.wait();
}
pub(super) fn wait_for_reader(&self) {
self.overlap.reader_contending.wait();
}
pub(super) fn release_writer(&self) {
self.overlap.commit_release.wait();
}
}
impl Core {
fn debug_handle(&self, name: &str, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut handle = formatter.debug_struct(name);
match self.state.try_read() {
Ok(state) => handle.field("version", &state.version),
Err(_contended_or_poisoned) => handle.field("version", &Locked),
}
.finish()
}
#[cfg(test)]
fn test_before_read(&self) {
let overlap = self
.commit_overlap
.lock()
.expect("test overlap lock must be healthy")
.clone();
if let Some(overlap) = overlap {
assert!(
matches!(self.state.try_read(), Err(TryLockError::WouldBlock)),
"overlap seam requires the production write lock to be held"
);
overlap.reader_contending.wait();
}
}
#[cfg(test)]
fn test_before_commit(&self) {
let overlap = self
.commit_overlap
.lock()
.expect("test overlap lock must be healthy")
.clone();
if let Some(overlap) = overlap {
overlap.writer_ready.wait();
overlap.reader_contending.wait();
overlap.commit_release.wait();
*self
.commit_overlap
.lock()
.expect("test overlap lock must be healthy") = None;
}
}
fn items(&self) -> Result<Vec<Item>, Error> {
self.snapshot().map(|snapshot| snapshot.into_parts().1)
}
fn snapshot(&self) -> Result<Snapshot, Error> {
#[cfg(test)]
self.test_before_read();
{
let state = self.state.read().map_err(|_| Error::Poisoned)?;
if !state.has_staged_items() {
return Ok(state.snapshot());
}
}
let mut state = self.state.write().map_err(|_| Error::Poisoned)?;
state.materialize_staged_items();
Ok(state.snapshot())
}
fn version(&self) -> Result<Version, Error> {
#[cfg(test)]
self.test_before_read();
let state = self.state.read().map_err(|_| Error::Poisoned)?;
Ok(state.version)
}
fn append_batch(
&self,
mut candidate: Vec<Item>,
expected: Option<Version>,
) -> Result<Version, Error> {
let delta = candidate.len() as u64;
let mut state = self.state.write().map_err(|_| Error::Poisoned)?;
if let Some(expected) = expected {
if state.version != expected {
return Err(Error::VersionConflict {
expected,
actual: state.version,
});
}
}
let next = state
.version
.checked_add(delta)
.ok_or(Error::VersionOverflow {
current: state.version,
delta,
})?;
#[cfg(test)]
self.test_before_commit();
if let Some(tail) = &mut state.staged_tail {
tail.append(&mut candidate);
} else {
Arc::make_mut(&mut state.items).append(&mut candidate);
}
state.version = next;
Ok(next)
}
fn replace(&self, candidate: Vec<Item>, expected: Option<Version>) -> Result<Version, Error> {
let mut state = self.state.write().map_err(|_| Error::Poisoned)?;
if let Some(expected) = expected {
if state.version != expected {
return Err(Error::VersionConflict {
expected,
actual: state.version,
});
}
}
let next = state.version.checked_add(1).ok_or(Error::VersionOverflow {
current: state.version,
delta: 1,
})?;
#[cfg(test)]
self.test_before_commit();
state.items = Arc::new(candidate);
if let Some(tail) = &mut state.staged_tail {
tail.clear();
}
state.version = next;
Ok(next)
}
fn replace_snapshot(&self, candidate: Snapshot, expected: Version) -> Result<Version, Error> {
if let Some(next) = expected.checked_add(1) {
assert_eq!(
candidate.version(),
next,
"snapshot installed at a live boundary must carry that boundary's successor version"
);
}
let mut state = self.state.write().map_err(|_| Error::Poisoned)?;
if state.version != expected {
return Err(Error::VersionConflict {
expected,
actual: state.version,
});
}
let next = state.version.checked_add(1).ok_or(Error::VersionOverflow {
current: state.version,
delta: 1,
})?;
#[cfg(test)]
self.test_before_commit();
state.items = candidate.items;
if let Some(tail) = &mut state.staged_tail {
tail.clear();
}
state.version = next;
Ok(next)
}
}
#[derive(Clone)]
pub struct Store {
core: Arc<Core>,
}
impl fmt::Debug for Store {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.core.debug_handle("Store", formatter)
}
}
impl Store {
#[must_use]
pub fn new() -> Self {
Self::from_items(Vec::new())
}
#[must_use]
pub fn from_items(items: Vec<Item>) -> Self {
Self::from_state(Version::ZERO, items)
}
#[must_use]
pub fn restore(snapshot: Snapshot) -> Self {
let Snapshot { version, items } = snapshot;
Self::from_shared_state(version, items, None)
}
pub(crate) fn fork(&self) -> Result<Self, Error> {
let snapshot = self.core.snapshot()?;
Ok(Self::from_shared_state(
snapshot.version,
snapshot.items,
Some(Vec::new()),
))
}
pub(crate) fn version(&self) -> Result<Version, Error> {
self.core.version()
}
pub(crate) fn into_snapshot(self) -> Result<Snapshot, Error> {
match Arc::try_unwrap(self.core) {
Ok(core) => core
.state
.into_inner()
.map(State::into_snapshot)
.map_err(|_| Error::Poisoned),
Err(core) => core.snapshot(),
}
}
pub(crate) fn into_snapshot_with_suffix(self, suffix: Vec<Item>) -> Result<Snapshot, Error> {
match Arc::try_unwrap(self.core) {
Ok(core) => core
.state
.into_inner()
.map(|state| state.into_snapshot_with_suffix(suffix))
.map_err(|_| Error::Poisoned),
Err(core) => {
let mut snapshot = core.snapshot()?;
Arc::make_mut(&mut snapshot.items).extend(suffix);
Ok(snapshot)
}
}
}
#[cfg(test)]
pub(crate) fn into_items(self) -> Result<Vec<Item>, Error> {
self.into_snapshot().map(|snapshot| snapshot.into_parts().1)
}
fn from_state(version: Version, items: Vec<Item>) -> Self {
Self::from_shared_state(version, Arc::new(items), None)
}
fn from_shared_state(
version: Version,
items: Arc<Vec<Item>>,
staged_tail: Option<Vec<Item>>,
) -> Self {
Self {
core: Arc::new(Core {
state: RwLock::new(State {
version,
items,
staged_tail,
}),
#[cfg(test)]
commit_overlap: Mutex::new(None),
}),
}
}
#[must_use]
pub fn reader(&self) -> Reader {
Reader {
core: Arc::clone(&self.core),
}
}
#[must_use]
pub fn snapshot_reader(&self) -> SnapshotReader {
SnapshotReader {
core: Arc::clone(&self.core),
}
}
#[must_use]
pub fn appender(&self) -> Appender {
Appender {
core: Arc::clone(&self.core),
}
}
#[must_use]
pub fn replacer(&self) -> Replacer {
Replacer {
core: Arc::clone(&self.core),
}
}
}
impl Default for Store {
fn default() -> Self {
Self::new()
}
}
#[derive(Clone)]
pub struct Reader {
core: Arc<Core>,
}
impl fmt::Debug for Reader {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.core.debug_handle("Reader", formatter)
}
}
impl Reader {
pub fn items(&self) -> Result<Vec<Item>, Error> {
self.core.items()
}
}
#[derive(Clone)]
pub struct SnapshotReader {
core: Arc<Core>,
}
impl fmt::Debug for SnapshotReader {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.core.debug_handle("SnapshotReader", formatter)
}
}
impl SnapshotReader {
pub fn snapshot(&self) -> Result<Snapshot, Error> {
self.core.snapshot()
}
pub fn version(&self) -> Result<Version, Error> {
self.core.version()
}
}
#[derive(Clone)]
pub struct Appender {
core: Arc<Core>,
}
impl fmt::Debug for Appender {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.core.debug_handle("Appender", formatter)
}
}
impl Appender {
pub fn append(&self, item: Item) -> Result<Version, Error> {
self.core.append_batch(vec![item], None)
}
pub fn append_batch(&self, items: Vec<Item>) -> Result<Version, Error> {
self.core.append_batch(items, None)
}
pub fn append_batch_if_version(
&self,
items: Vec<Item>,
expected: Version,
) -> Result<Version, Error> {
self.core.append_batch(items, Some(expected))
}
}
#[derive(Clone)]
pub struct Replacer {
core: Arc<Core>,
}
impl fmt::Debug for Replacer {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.core.debug_handle("Replacer", formatter)
}
}
impl Replacer {
pub fn replace(&self, items: Vec<Item>) -> Result<Version, Error> {
self.core.replace(items, None)
}
pub fn replace_if_version(
&self,
items: Vec<Item>,
expected: Version,
) -> Result<Version, Error> {
self.core.replace(items, Some(expected))
}
pub(crate) fn install_snapshot_if_version(
&self,
snapshot: Snapshot,
expected: Version,
) -> Result<Version, Error> {
self.core.replace_snapshot(snapshot, expected)
}
}
#[cfg(test)]
pub(super) fn install_commit_overlap(store: &Store) -> CommitOverlapControl {
let overlap = Arc::new(CommitOverlap::new());
*store
.core
.commit_overlap
.lock()
.expect("test overlap lock must be healthy") = Some(Arc::clone(&overlap));
CommitOverlapControl { overlap }
}
#[cfg(test)]
pub(super) fn hold_write_lock(store: &Store, held: &Barrier, release: &Barrier) {
let _guard = store.core.state.write().expect("test lock starts healthy");
held.wait();
release.wait();
}
#[cfg(test)]
pub(crate) fn poison(store: &Store) {
let _guard = store.core.state.write().expect("test lock starts healthy");
panic!("intentional transcript-store poison");
}
#[cfg(feature = "serde")]
mod serde_impl {
use std::fmt::{self, Formatter};
use serde_core::de::{
Deserialize, Deserializer, Error as DeError, MapAccess, SeqAccess, Visitor,
};
use serde_core::ser::{Serialize, SerializeStruct, Serializer};
use super::{Snapshot, Version};
use crate::wire::{self, IdentifierSeed};
const SNAPSHOT_FIELDS: &[&str] = &["version", "items"];
impl Serialize for Version {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
serializer.serialize_u64(self.0)
}
}
impl<'de> Deserialize<'de> for Version {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
u64::deserialize(deserializer).map(Self::from_u64)
}
}
impl Serialize for Snapshot {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let mut record = serializer.serialize_struct("Snapshot", 2)?;
record.serialize_field("version", &self.version)?;
record.serialize_field("items", self.items())?;
record.end()
}
}
impl<'de> Deserialize<'de> for Snapshot {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_struct("Snapshot", SNAPSHOT_FIELDS, SnapshotVisitor)
}
}
struct SnapshotVisitor;
impl<'de> Visitor<'de> for SnapshotVisitor {
type Value = Snapshot;
fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
formatter.write_str("a transcript snapshot")
}
fn visit_seq<A>(self, mut sequence: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let version = wire::element(&mut sequence, 0)?;
let items = wire::element(&mut sequence, 1)?;
wire::end(&mut sequence, 2)?;
Ok(Snapshot::new(version, items))
}
fn visit_map<A>(self, mut entries: A) -> Result<Self::Value, A::Error>
where
A: MapAccess<'de>,
{
let mut version = None;
let mut items = None;
while let Some(field) = entries.next_key_seed(IdentifierSeed(SNAPSHOT_FIELDS))? {
match field.0.as_str() {
"version" => wire::accept(&mut version, entries.next_value()?, "version")?,
"items" => wire::accept(&mut items, entries.next_value()?, "items")?,
unknown => return Err(A::Error::unknown_field(unknown, SNAPSHOT_FIELDS)),
}
}
Ok(Snapshot::new(
wire::require(version, "version")?,
wire::require(items, "items")?,
))
}
}
}