use core::mem;
use happenstance_core::{
AppendCondition, AppendError, Event, EventStore, Query, ReadOptions, SequencePosition,
SequencedEvent, collect,
};
use super::{Op, read_options, render, resolve, select};
const CEILING: SequencePosition = match SequencePosition::new(u64::MAX) {
Some(position) => position,
None => SequencePosition::FIRST,
};
#[derive(Debug, Default)]
pub(super) struct TrailingModel {
expected: Vec<Event>,
known: Vec<SequencedEvent>,
returned: Vec<(usize, SequencePosition)>,
deferred: Vec<Deferred>,
}
#[derive(Debug)]
struct Deferred {
op: usize,
condition: AppendCondition,
held: usize,
accepted: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Prediction {
Rejected,
Accepted,
Undecided,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Placed {
At(SequencePosition),
Between {
above: Option<SequencePosition>,
below: Option<SequencePosition>,
},
}
impl TrailingModel {
fn exact(&self, index: usize) -> Option<SequencePosition> {
self.known
.get(index)
.map(|event| event.position)
.or_else(|| {
self.returned
.iter()
.find(|(at, _)| *at == index)
.map(|(_, position)| *position)
})
}
fn placed(&self, index: usize) -> Placed {
if let Some(position) = self.exact(index) {
return Placed::At(position);
}
Placed::Between {
above: (0..index).rev().find_map(|at| self.exact(at)),
below: (index.saturating_add(1)..self.expected.len()).find_map(|at| self.exact(at)),
}
}
fn predict(&self, condition: &AppendCondition, held: usize) -> Prediction {
let mut undecided = false;
for (index, event) in self.expected.iter().take(held).enumerate() {
let Some((low, high)) = range(self.placed(index)) else {
undecided = true;
continue;
};
if condition.is_violated_by(low, event.event_type(), event.tags()) {
return Prediction::Rejected;
}
if condition.is_violated_by(high, event.event_type(), event.tags()) {
undecided = true;
}
}
if undecided {
Prediction::Undecided
} else {
Prediction::Accepted
}
}
fn counts(&self) -> String {
format!("visible {}, held {}", self.known.len(), self.expected.len())
}
fn check_log(&self, observed: &[SequencedEvent]) -> Result<(), String> {
if observed.len() > self.expected.len() {
return Err(format!(
"the log shows {} event(s), and only {} were accepted ({})",
observed.len(),
self.expected.len(),
self.counts()
));
}
for (index, (seen, wanted)) in observed.iter().zip(&self.expected).enumerate() {
if &seen.event != wanted {
return Err(format!(
"the event at index {index} is not the one accepted there, so the \
read is not a prefix of the accepted log: read back {:?}, \
appended {wanted:?} ({})",
seen.event,
self.counts()
));
}
}
self.check_never_retreats(observed)?;
for (earlier, later) in observed.iter().zip(observed.iter().skip(1)) {
if later.position <= earlier.position {
return Err(format!(
"positions must be unique and strictly increasing in assignment \
order, but {} follows {} ({})",
later.position,
earlier.position,
self.counts()
));
}
}
for (index, (before, now)) in self.known.iter().zip(observed).enumerate() {
if before.position != now.position {
return Err(format!(
"the event at index {index} was shown at {}, and is now shown at \
{} ({})",
before.position,
now.position,
self.counts()
));
}
}
self.check_returned(observed)
}
fn check_never_retreats(&self, observed: &[SequencedEvent]) -> Result<(), String> {
if observed.len() < self.known.len() {
return Err(format!(
"the frontier went backward: a full read showed {} event(s) and a \
later one shows {}. The trailing model assumes visibility never \
moves backward, which no clause states yet ({})",
self.known.len(),
observed.len(),
self.counts()
));
}
Ok(())
}
fn check_returned(&self, observed: &[SequencedEvent]) -> Result<(), String> {
let highest = observed.last().map(|event| event.position);
for &(index, returned) in &self.returned {
match observed.get(index) {
Some(seen) if seen.position != returned => {
return Err(format!(
"`append` returned {returned} for the batch ending at index \
{index}, and the log shows that event at {} ({})",
seen.position,
self.counts()
));
}
Some(_) => {}
None => {
if let Some(highest) = highest
&& highest >= returned
{
return Err(format!(
"{highest} is visible while the batch `append` returned \
{returned} for is not, and position order is visibility \
order (ES-10) ({})",
self.counts()
));
}
}
}
}
Ok(())
}
fn check_read(
&self,
before: usize,
query: &Query,
options: ReadOptions,
observed: &[SequencedEvent],
) -> Result<(), String> {
let explained = (before..=self.known.len()).any(|visible| {
self.known
.get(..visible)
.is_some_and(|prefix| select(prefix, query, options) == observed)
});
if explained {
Ok(())
} else {
Err(format!(
"read({query:?}, {options:?}) returned {}, which no frontier between \
the {before} event(s) visible before it and the {} visible after it \
explains; over all of them the model expected {} ({})",
render(observed),
self.known.len(),
render(&select(&self.known, query, options)),
self.counts()
))
}
}
fn rejudge(&mut self) -> Result<(), String> {
let pending = mem::take(&mut self.deferred);
for deferred in pending {
match (
self.predict(&deferred.condition, deferred.held),
deferred.accepted,
) {
(Prediction::Undecided, _) => self.deferred.push(deferred),
(Prediction::Rejected, false) | (Prediction::Accepted, true) => {}
(Prediction::Rejected, true) => {
return Err(format!(
"op {} was accepted under {:?}, and a held event is now known \
to violate it ({})",
deferred.op,
deferred.condition,
self.counts()
));
}
(Prediction::Accepted, false) => {
return Err(format!(
"op {} was rejected under {:?}, and no held event is now able \
to violate it ({})",
deferred.op,
deferred.condition,
self.counts()
));
}
}
}
Ok(())
}
fn accept(&mut self, events: &[Event], written: SequencePosition) -> Result<(), String> {
let floor = self
.known
.last()
.map(|event| event.position)
.max(self.returned.last().map(|(_, position)| *position));
if let Some(floor) = floor
&& written <= floor
{
return Err(format!(
"`append` returned {written}, which is not above {floor}, a position \
an earlier batch already holds ({})",
self.counts()
));
}
self.expected.extend(events.iter().cloned());
if let Some(last) = self.expected.len().checked_sub(1) {
self.returned.push((last, written));
}
Ok(())
}
async fn reconcile<S: EventStore>(&mut self, store: &S) -> Result<(), String> {
let observed = match collect(store.read(&Query::all(), ReadOptions::new())).await {
Ok(events) => events,
Err(err) => return Err(format!("reading the whole log failed: {err:?}")),
};
self.check_log(&observed)?;
self.known = observed;
self.rejudge()
}
pub(super) async fn apply<S: EventStore>(
&mut self,
store: &S,
index: usize,
op: &Op,
) -> Result<(), String> {
match op {
Op::Append { events } => {
let written = match store.append(events, None).await {
Ok(position) => position,
Err(err) => {
return Err(format!("an unconditional append was refused: {err:?}"));
}
};
self.accept(events, written)?;
self.reconcile(store).await
}
Op::AppendConditional {
events,
query,
anchor,
} => {
let condition = AppendCondition::new(query.clone())
.after_every_guard_opt(resolve(&self.known, *anchor));
self.append_conditional(store, index, events, condition)
.await?;
self.reconcile(store).await
}
Op::Read {
query,
from,
to,
backwards,
limit,
} => {
let before = self.known.len();
let options = read_options(&self.known, *from, *to, *backwards, *limit);
let observed = match collect(store.read(query, options)).await {
Ok(events) => events,
Err(err) => return Err(format!("the read failed: {err:?}")),
};
self.reconcile(store).await?;
self.check_read(before, query, options, &observed)
}
}
}
async fn append_conditional<S: EventStore>(
&mut self,
store: &S,
index: usize,
events: &[Event],
condition: AppendCondition,
) -> Result<(), String> {
let held = self.expected.len();
let predicted = self.predict(&condition, held);
let result = store.append(events, Some(&condition)).await;
let accepted = match (predicted, result) {
(
Prediction::Rejected | Prediction::Undecided,
Err(AppendError::ConditionViolated(_)),
) => false,
(Prediction::Accepted | Prediction::Undecided, Ok(written)) => {
self.accept(events, written)?;
true
}
(Prediction::Rejected, Ok(written)) => {
return Err(format!(
"the append was accepted at {written}, but a held event violates \
{condition:?} ({})",
self.counts()
));
}
(Prediction::Accepted, Err(AppendError::ConditionViolated(violated))) => {
return Err(format!(
"the append was rejected as {violated:?}, but no held event can \
violate {condition:?} ({})",
self.counts()
));
}
(_, Err(other)) => {
return Err(format!("a conditional append failed outright: {other:?}"));
}
};
if predicted == Prediction::Undecided {
self.deferred.push(Deferred {
op: index,
condition,
held,
accepted,
});
}
Ok(())
}
}
fn range(placed: Placed) -> Option<(SequencePosition, SequencePosition)> {
match placed {
Placed::At(position) => Some((position, position)),
Placed::Between { above, below } => {
let low = match above {
Some(above) => above.next()?,
None => SequencePosition::FIRST,
};
let high = match below {
Some(below) => SequencePosition::new(below.get().checked_sub(1)?)?,
None => CEILING,
};
(low <= high).then_some((low, high))
}
}
}
#[cfg(test)]
mod tests;