Skip to main content

happenstance_core/
memory.rs

1//! An in-memory reference event store.
2
3use alloc::vec::Vec;
4use core::sync::atomic::{AtomicU64, Ordering};
5use std::sync::{OnceLock, PoisonError, RwLock};
6
7use futures_core::Stream;
8
9use crate::append::AppendCondition;
10use crate::error::{AppendError, ConditionViolated};
11use crate::event::{Event, SequencePosition, SequencedEvent};
12use crate::identity::{EventId, RecordedAt, StoreId};
13use crate::query::{Query, ReadOptions};
14use crate::store::SendEventStore;
15
16/// The reference implementation of [`EventStore`](crate::EventStore).
17///
18/// It exists for three reasons, in order of importance:
19///
20/// 1. it is the oracle the conformance suite is validated against, so that a
21///    failing adapter is known to be the adapter's fault and not the suite's;
22/// 2. it makes this crate's examples runnable, so the documentation cannot
23///    drift from the API;
24/// 3. it lets application code be written and tested before any real adapter
25///    exists.
26///
27/// It is **not** built for scale. [`read`](crate::EventStore::read) snapshots
28/// the matching events under the lock and streams from that snapshot, so a read
29/// never holds the lock across a poll — correct, and deliberately simple.
30/// Snapshot cost: payloads are [`Bytes`](bytes::Bytes), so a snapshot bumps
31/// refcounts rather than copying data — but each event still costs `t + 2`.
32///
33/// Positions are dense and start at 1. The specification permits gaps, so
34/// nothing may depend on that.
35///
36/// # Examples
37///
38/// The full DCB loop — read a decision model, then append conditioned on it:
39///
40/// ```
41/// use happenstance_core::{
42///     AppendCondition, Event, EventStore, MemoryEventStore, Query, QueryItem, Tags,
43///     read_decision_model,
44/// };
45///
46/// # #[tokio::main(flavor = "current_thread")]
47/// # async fn main() -> Result<(), Box<dyn core::error::Error>> {
48/// let store = MemoryEventStore::new();
49///
50/// // "Has course c1 already been defined?"
51/// let query = Query::from_item(QueryItem::new(
52///     ["CourseDefined"],
53///     Tags::from_pairs([("course", "c1")])?,
54/// )?);
55///
56/// let (events, last_seen) = read_decision_model(&store, &query).await?;
57/// assert!(events.is_empty());
58///
59/// let defined = Event::new("CourseDefined", &b"{\"capacity\":2}"[..])?
60///     .with_tags(Tags::from_pairs([("course", "c1")])?);
61///
62/// // Append only if nothing matching has appeared since we looked.
63/// let condition = AppendCondition::new(query.clone()).after_every_guard_opt(last_seen);
64/// store.append(&[defined.clone()], Some(&condition)).await?;
65///
66/// // Replaying the same command now fails — the course exists.
67/// let err = store.append(&[defined], Some(&condition)).await.unwrap_err();
68/// assert!(err.is_condition_violated());
69/// # Ok(())
70/// # }
71/// ```
72#[derive(Debug)]
73pub struct MemoryEventStore {
74    events: RwLock<Vec<SequencedEvent>>,
75    store_id: StoreId,
76}
77
78impl Default for MemoryEventStore {
79    fn default() -> Self {
80        Self::new()
81    }
82}
83
84impl MemoryEventStore {
85    /// Creates an empty store with a fresh incarnation identifier.
86    #[must_use]
87    pub fn new() -> Self {
88        Self::with_store_id(next_store_id())
89    }
90
91    /// Creates an empty store with a caller-chosen incarnation.
92    ///
93    /// Exists for the rule that a reopened store must not reissue an identity:
94    /// "reopening" an in-memory store is constructing a new one, and the rule
95    /// needs to distinguish "the same store again" from "a different store".
96    #[must_use]
97    pub fn with_store_id(store_id: StoreId) -> Self {
98        Self {
99            events: RwLock::new(Vec::new()),
100            store_id,
101        }
102    }
103
104    /// The incarnation this store mints identities under.
105    #[must_use]
106    pub const fn store_id(&self) -> StoreId {
107        self.store_id
108    }
109
110    /// Creates a store pre-loaded with `events`, assigned dense positions from
111    /// 1.
112    ///
113    /// Useful for arranging test fixtures without going through
114    /// [`append`](crate::EventStore::append).
115    pub fn with_events(events: impl IntoIterator<Item = Event>) -> Self {
116        let store = Self::new();
117        let recorded_at = now();
118        let sequenced = events
119            .into_iter()
120            .enumerate()
121            .map(|(index, event)| {
122                let position = position_at(index);
123                SequencedEvent::new(
124                    position,
125                    EventId::new(store.store_id, position),
126                    recorded_at,
127                    event,
128                )
129            })
130            .collect();
131
132        Self {
133            events: RwLock::new(sequenced),
134            store_id: store.store_id,
135        }
136    }
137
138    /// Reconstructs a store from a snapshot of what a durable medium held.
139    ///
140    /// The counterpart of [`snapshot`](Self::snapshot), and deliberately not
141    /// [`with_events`](Self::with_events): that one *arranges* a store, assigning
142    /// fresh positions, identities and a time, which is what a caller wants when
143    /// seeding a fixture. This one *reopens* one, preserving every store-assigned
144    /// fact on every event — which is what a real adapter's open does, because it
145    /// reads rows it wrote rather than re-accepting events. A store whose reopen
146    /// restamps hands every auditor the time of the last restart.
147    ///
148    /// # Examples
149    ///
150    /// ```
151    /// # use happenstance_core::{Event, EventStore, MemoryEventStore};
152    /// # async fn demo() -> Result<(), Box<dyn core::error::Error>> {
153    /// let store = MemoryEventStore::new();
154    /// store.append(&[Event::new("Issued", &b"{}"[..])?], None).await?;
155    ///
156    /// // What a durable medium would have kept, and what reopening finds.
157    /// let reopened = MemoryEventStore::restore(store.store_id(), store.snapshot());
158    /// assert_eq!(reopened.snapshot(), store.snapshot());
159    /// # Ok(())
160    /// # }
161    /// ```
162    #[must_use]
163    pub fn restore(store_id: StoreId, events: impl IntoIterator<Item = SequencedEvent>) -> Self {
164        Self {
165            events: RwLock::new(events.into_iter().collect()),
166            store_id,
167        }
168    }
169
170    /// The number of events held.
171    pub fn len(&self) -> usize {
172        self.read_guard().len()
173    }
174
175    /// Whether the store is empty.
176    pub fn is_empty(&self) -> bool {
177        self.read_guard().is_empty()
178    }
179
180    /// The position most recently assigned, or `None` if the store is empty.
181    pub fn last_position(&self) -> Option<SequencePosition> {
182        self.read_guard().last().map(|event| event.position)
183    }
184
185    /// A snapshot of every event held, in position order.
186    pub fn snapshot(&self) -> Vec<SequencedEvent> {
187        self.read_guard().clone()
188    }
189
190    /// Reads through the lock, recovering from poisoning.
191    ///
192    /// A panic in another thread while holding the lock cannot have left this
193    /// store inconsistent: every mutation happens in one `extend` under the
194    /// write lock, and the validation that precedes it does not mutate. So
195    /// poisoning carries no information here and is ignored rather than
196    /// propagated as a spurious failure.
197    fn read_guard(&self) -> std::sync::RwLockReadGuard<'_, Vec<SequencedEvent>> {
198        self.events.read().unwrap_or_else(PoisonError::into_inner)
199    }
200}
201
202/// A fresh incarnation identifier.
203///
204/// Process-local and monotonic, which is enough here and would not be enough
205/// anywhere else: nothing an in-memory store holds outlives the process, so
206/// there is no persistent state a second incarnation could be confused with. A
207/// durable adapter has the harder job — mint at database creation, and re-mint
208/// when that state is restored or cloned.
209///
210/// The salt keeps two runs from minting the same identifier, so a test that
211/// writes one down cannot accidentally pass by matching a later process's.
212fn next_store_id() -> StoreId {
213    static COUNTER: AtomicU64 = AtomicU64::new(1);
214    static SALT: OnceLock<u64> = OnceLock::new();
215
216    // `unsigned_abs` rather than a cast, and `0` where there is no clock: the
217    // salt only has to separate two *runs*, and the counter below is what
218    // separates two stores within one.
219    let salt = *SALT.get_or_init(|| wall_clock_millis().unwrap_or(0).unsigned_abs());
220
221    let ordinal = COUNTER.fetch_add(1, Ordering::Relaxed);
222
223    let mut bytes = [0u8; 16];
224    bytes[..8].copy_from_slice(&salt.to_be_bytes());
225    bytes[8..].copy_from_slice(&ordinal.to_be_bytes());
226    StoreId::from_bytes(bytes)
227}
228
229/// The host clock, as milliseconds since the Unix epoch.
230///
231/// A clock that is behind the epoch, or a target that has none at all, yields
232/// zero rather than failing: `append` has no error variant for "the clock is
233/// broken", and inventing one would put a store failure in the caller's path
234/// for a value the caller cannot act on.
235fn now() -> RecordedAt {
236    RecordedAt::from_millis(wall_clock_millis().unwrap_or(0))
237}
238
239/// Milliseconds since the Unix epoch, or `None` on a target with no clock.
240///
241/// **`SystemTime::now()` panics on `wasm32-unknown-unknown`.** It does not
242/// return an error — there is no clock behind it, and the call aborts. That
243/// target is the entire reason the bare `EventStore` flavour exists, so a
244/// reference store that cannot even be *constructed* there is one nobody can
245/// develop against the platform the contract was shaped for. This function is
246/// the seam that keeps `MemoryEventStore::new()` total on every target.
247///
248/// The workspace gate compiles for `wasm32` but does not run there; CI does,
249/// which is how this was found. A `cfg` is the only available answer: `std`
250/// exposes no fallible clock, and reaching for a JavaScript one would put a
251/// `wasm-bindgen` dependency in the contract crate to serve a store that exists
252/// for tests and examples.
253#[cfg(not(all(target_arch = "wasm32", target_os = "unknown")))]
254fn wall_clock_millis() -> Option<i64> {
255    use std::time::{SystemTime, UNIX_EPOCH};
256
257    SystemTime::now()
258        .duration_since(UNIX_EPOCH)
259        .ok()
260        .map(|since| i64::try_from(since.as_millis()).unwrap_or(i64::MAX))
261}
262
263/// No clock on this target; see the sibling above.
264///
265/// Every event a store on this target accepts is therefore stamped
266/// `RecordedAt::from_millis(0)`. That is honest rather than convenient: VT-9's
267/// own falsifier names "a target that cannot supply a wall clock at append
268/// time", and this is one. It costs the rules nothing — they assert that a
269/// recorded time is *stable*, never that it is recent — and an adapter for this
270/// platform that has a real clock (a Durable Object does) supplies its own.
271#[cfg(all(target_arch = "wasm32", target_os = "unknown"))]
272fn wall_clock_millis() -> Option<i64> {
273    None
274}
275
276/// The dense position for a zero-based index.
277fn position_at(index: usize) -> SequencePosition {
278    let raw = u64::try_from(index)
279        .unwrap_or(u64::MAX - 1)
280        .saturating_add(1);
281    SequencePosition::new(raw).unwrap_or(SequencePosition::FIRST)
282}
283
284/// [`MemoryEventStore`]'s error type, which is uninhabited.
285///
286/// An uninhabited error is worth having: it proves the contract does not
287/// *require* a fallible read path, and it documents at the type level that this
288/// store has no failure modes of its own.
289#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
290#[error("unreachable: the in-memory event store cannot fail")]
291pub enum MemoryStoreError {}
292
293impl SendEventStore for MemoryEventStore {
294    type Error = MemoryStoreError;
295
296    fn read(
297        &self,
298        query: &Query,
299        options: ReadOptions,
300    ) -> impl Stream<Item = Result<SequencedEvent, Self::Error>> + Send {
301        let guard = self.read_guard();
302
303        // Filter, order and limit under the lock, then release it. The stream
304        // that leaves this function borrows nothing.
305        let matched = guard
306            .iter()
307            .filter(|event| query.matches(event.event_type(), event.tags()));
308
309        // After filtering and ordering, never before: `limit` cuts the result
310        // set the caller would otherwise have seen. A limit of zero yields
311        // nothing, which is the point of it being `Option<usize>`.
312        //
313        // `unwrap_or(usize::MAX)` is how `Option<usize>` reaches `take`. No
314        // store can hold `usize::MAX` events, so the unlimited case is
315        // unchanged and pays nothing for the branch it no longer takes.
316        let limit = options.limit.unwrap_or(usize::MAX);
317
318        // `from` is the starting bound and `to` the stopping one, so reading
319        // backwards swaps which side of the position order each sits on. Both
320        // are inclusive in both directions.
321        //
322        // Where `take` sits in each chain is load-bearing at both ends. Below
323        // `rev()` and below both bounds filters, so it cuts the *result* set
324        // and never the *scanned* one — one link earlier it is the wrong
325        // implementation ES-14 `[FROZEN]` rejects, and in the backwards branch
326        // it would return the lowest matching positions instead of the
327        // highest. Above `cloned()`, so the tail beyond `limit` is never
328        // cloned: collecting first and cutting afterwards made `limit(1)` cost
329        // what an unlimited read costs, which is the whole of the reduction
330        // `limit` is supposed to buy.
331        let selected: Vec<SequencedEvent> = if options.backwards {
332            matched
333                .rev()
334                .filter(|event| options.from.is_none_or(|from| event.position <= from))
335                .filter(|event| options.to.is_none_or(|to| event.position >= to))
336                .take(limit)
337                .cloned()
338                .collect()
339        } else {
340            matched
341                .filter(|event| options.from.is_none_or(|from| event.position >= from))
342                .filter(|event| options.to.is_none_or(|to| event.position <= to))
343                .take(limit)
344                .cloned()
345                .collect()
346        };
347
348        drop(guard);
349        Snapshot(selected.into_iter())
350    }
351
352    async fn append(
353        &self,
354        events: &[Event],
355        condition: Option<&AppendCondition>,
356    ) -> Result<SequencePosition, AppendError<Self::Error>> {
357        // Emptiness first, and **above the lock** — ES-20 `[FROZEN]`.
358        //
359        // The specification defines `Events` as a non-empty collection, so there
360        // is no position to return. Adapters must reject this rather than invent
361        // one. The *precedence* is the part that was wrong here until phase 3:
362        // evaluating the condition first made `append(&[], Some(&c))` answer
363        // `NoEvents` or `ConditionViolated` depending on what the store happened
364        // to hold, so two conformant adapters could disagree — and a caller whose
365        // retry loop branches on `is_condition_violated()` sees the DCB
366        // concurrency signal for what is unambiguously its own bug and retries
367        // forever. `ConditionViolated` means "rebuild the decision model and try
368        // again"; an empty batch will still be empty next time.
369        //
370        // It is checked above the lock because emptiness is a precondition on the
371        // **argument**, not a question about the store. Nothing in the log can
372        // change the answer, so taking a write lock to find out would be a lock
373        // acquired to learn something already known.
374        if events.is_empty() {
375            return Err(AppendError::NoEvents);
376        }
377
378        // From here the whole operation runs under one write lock, which is what
379        // makes it atomic: no reader can observe a partially-applied batch, and
380        // no concurrent appender can slip between the condition check and the
381        // write. That race is precisely what an append condition exists to
382        // prevent, so getting it wrong here would make the reference
383        // implementation useless as an oracle.
384        let mut stored = self.events.write().unwrap_or_else(PoisonError::into_inner);
385
386        if let Some(condition) = condition {
387            let conflict = stored.iter().find(|existing| {
388                condition.is_violated_by(existing.position, existing.event_type(), existing.tags())
389            });
390
391            if let Some(conflict) = conflict {
392                // Returning without touching `stored` is what "a rejected
393                // append leaves the store byte-identical" means.
394                return Err(AppendError::ConditionViolated(ConditionViolated::at(
395                    conflict.position,
396                )));
397            }
398        }
399
400        let first_index = stored.len();
401        let recorded_at = now();
402        stored.extend(events.iter().enumerate().map(|(offset, event)| {
403            let position = position_at(first_index + offset);
404            // A locally appended event's identity is this store's incarnation
405            // paired with the position just assigned, so `id.position()` and
406            // `position` agree here. They part company only for an event that
407            // arrived through ingest, which this store has no way to accept.
408            SequencedEvent::new(
409                position,
410                EventId::new(self.store_id, position),
411                recorded_at,
412                event.clone(),
413            )
414        }));
415
416        Ok(position_at(first_index + events.len() - 1))
417    }
418
419    async fn head(&self) -> Result<Option<SequencePosition>, Self::Error> {
420        // The whole log is behind one lock, so the highest visible position is
421        // the last element. An adapter over SQL answers with
422        // `SELECT max(position)`; what neither may do is cache it outside the
423        // transaction that assigns it, which is what makes a second handle
424        // observe a stale head.
425        Ok(self.read_guard().last().map(|event| event.position))
426    }
427
428    async fn contains_event_id(&self, id: EventId) -> Result<bool, Self::Error> {
429        // A scan, because this store has no index and never will — it exists to
430        // be correct and readable, not fast. The shape an adapter uses is
431        // `WHERE origin_store = ? AND origin_position = ?`.
432        Ok(self.read_guard().iter().any(|event| event.id == id))
433    }
434}
435
436/// The stream returned by [`MemoryEventStore::read`].
437///
438/// Owns its events, so it borrows nothing from the store and is `Send`.
439#[derive(Debug)]
440struct Snapshot(alloc::vec::IntoIter<SequencedEvent>);
441
442impl Stream for Snapshot {
443    type Item = Result<SequencedEvent, MemoryStoreError>;
444
445    fn poll_next(
446        self: core::pin::Pin<&mut Self>,
447        _cx: &mut core::task::Context<'_>,
448    ) -> core::task::Poll<Option<Self::Item>> {
449        core::task::Poll::Ready(self.get_mut().0.next().map(Ok))
450    }
451}
452
453#[cfg(test)]
454mod tests {
455    #![allow(clippy::unwrap_used)]
456
457    // Only ONE flavour is imported for method-call syntax. Importing both
458    // `EventStore` and `SendEventStore` makes `store.read(..)` ambiguous,
459    // because `MemoryEventStore` satisfies both; see the `store` module
460    // documentation. The `SendEventStore` path is exercised below through
461    // fully-qualified calls.
462    use super::{AppendCondition, Event, MemoryEventStore, Query, ReadOptions};
463    use crate::store::EventStore;
464    use crate::{QueryItem, SequencePosition, Tags, collect};
465
466    fn event(event_type: &str) -> Event {
467        Event::new(event_type, &b"{}"[..]).unwrap()
468    }
469
470    #[tokio::test]
471    async fn append_assigns_dense_positions_from_one() {
472        let store = MemoryEventStore::new();
473
474        let last = store.append(&[event("A"), event("B")], None).await.unwrap();
475        assert_eq!(last.get(), 2);
476
477        let all = collect(store.read(&Query::all(), ReadOptions::new()))
478            .await
479            .unwrap();
480        assert_eq!(
481            all.iter().map(|e| e.position.get()).collect::<Vec<_>>(),
482            [1, 2]
483        );
484    }
485
486    #[tokio::test]
487    async fn rejected_append_leaves_the_store_untouched() {
488        let store = MemoryEventStore::new();
489        store.append(&[event("A")], None).await.unwrap();
490        let before = store.snapshot();
491
492        let condition = AppendCondition::new(Query::from_item(QueryItem::of_types(["A"]).unwrap()));
493        let err = store
494            .append(&[event("B"), event("C")], Some(&condition))
495            .await
496            .unwrap_err();
497
498        assert!(err.is_condition_violated());
499        assert_eq!(store.snapshot(), before);
500    }
501
502    #[tokio::test]
503    async fn empty_append_is_rejected() {
504        let store = MemoryEventStore::new();
505        assert!(store.append(&[], None).await.is_err());
506    }
507
508    #[tokio::test]
509    async fn empty_append_is_refused_before_the_condition_is_evaluated() {
510        // ES-20's precedence, at the reference implementation. The conformance
511        // suite carries the same claim as
512        // `empty_batch_is_refused_before_the_condition_is_evaluated`; this is
513        // here as well because `MemoryEventStore` is the oracle the suite is
514        // validated against, and the ordering used to be wrong in both.
515        let store = MemoryEventStore::new();
516        store.append(&[event("Blocker")], None).await.unwrap();
517
518        let condition =
519            AppendCondition::new(Query::from_item(QueryItem::of_types(["Blocker"]).unwrap()));
520        let err = store.append(&[], Some(&condition)).await.unwrap_err();
521
522        assert!(
523            !err.is_condition_violated(),
524            "an empty batch is the caller's own bug, and `ConditionViolated` \
525             means `retry`: a caller branching on it loops forever. Got {err:?}"
526        );
527    }
528
529    #[tokio::test]
530    async fn with_events_matches_append() {
531        let seeded = MemoryEventStore::with_events([event("A"), event("B")]);
532        let appended = MemoryEventStore::new();
533        appended
534            .append(&[event("A"), event("B")], None)
535            .await
536            .unwrap();
537
538        let seeded_snapshot = seeded.snapshot();
539        let appended_snapshot = appended.snapshot();
540
541        // Two stores cannot agree on identity or recorded time — those are facts
542        // about *which* store accepted the event and *when*, and the whole point
543        // of `StoreId` is that two incarnations differ. What `with_events`
544        // claims is parity of position and payload, so that is what is compared.
545        let shape = |events: &[crate::SequencedEvent]| {
546            events
547                .iter()
548                .map(|event| (event.position, event.event.clone()))
549                .collect::<Vec<_>>()
550        };
551        assert_eq!(shape(&seeded_snapshot), shape(&appended_snapshot));
552
553        // And each store stamps its own incarnation, which is the property that
554        // makes the comparison above the right one.
555        assert!(
556            seeded_snapshot
557                .iter()
558                .all(|event| event.id.store() == seeded.store_id())
559        );
560        assert!(
561            appended_snapshot
562                .iter()
563                .all(|event| event.id.store() == appended.store_id())
564        );
565        assert_ne!(
566            seeded.store_id(),
567            appended.store_id(),
568            "two stores are two incarnations"
569        );
570    }
571
572    #[tokio::test]
573    async fn append_stamps_identity_from_its_own_incarnation() {
574        let store = MemoryEventStore::new();
575        store.append(&[event("A"), event("B")], None).await.unwrap();
576
577        let snapshot = store.snapshot();
578        assert_eq!(snapshot.len(), 2);
579
580        for sequenced in &snapshot {
581            assert_eq!(sequenced.id.store(), store.store_id());
582            // For a locally appended event the two positions agree; they part
583            // company only for an event accepted through ingest, which this
584            // store cannot do.
585            assert_eq!(sequenced.id.position(), sequenced.position);
586        }
587
588        assert_ne!(
589            snapshot[0].id, snapshot[1].id,
590            "two events, two identities, even with equal payloads"
591        );
592    }
593
594    #[tokio::test]
595    async fn structurally_equal_events_get_distinct_identities() {
596        // Structural equality is not identity: appending the same event twice
597        // must produce two events, not one, and a content hash would collapse
598        // them.
599        let store = MemoryEventStore::new();
600        let twice = [event("A"), event("A")];
601        assert_eq!(twice[0], twice[1], "the two events are structurally equal");
602
603        store.append(&twice, None).await.unwrap();
604
605        let snapshot = store.snapshot();
606        assert_eq!(snapshot.len(), 2);
607        assert_ne!(snapshot[0].position, snapshot[1].position);
608        assert_ne!(snapshot[0].id, snapshot[1].id);
609    }
610
611    #[tokio::test]
612    async fn implements_the_non_send_flavour_too() {
613        // Compiles only because `SendEventStore` implies `EventStore`. This is
614        // the property that lets every consumer bind the weaker trait.
615        async fn count<S: EventStore>(store: &S) -> usize {
616            collect(store.read(&Query::all(), ReadOptions::new()))
617                .await
618                .map(|events| events.len())
619                .unwrap_or_default()
620        }
621
622        let store = MemoryEventStore::new();
623        store.append(&[event("A")], None).await.unwrap();
624        assert_eq!(count(&store).await, 1);
625    }
626
627    #[test]
628    fn send_flavour_stream_is_send_in_generic_code() {
629        // ES-2, first half. On the `Send` flavour it is the *stream* that is
630        // `Send`, not merely the future producing it.
631        //
632        // The bound is written at the *definition*, so inside the function the
633        // compiler knows nothing about `S` beyond what `SendEventStore`
634        // promises, and the obligation is discharged before monomorphisation.
635        // Its predecessor asserted `Send` on a concrete store, where auto-trait
636        // leakage from the hidden type satisfied it whatever the trait said: it
637        // passed unchanged with `Send` struck from the `trait_variant`
638        // attribute, which is what "cannot fail" means.
639        //
640        // This alone does NOT reject the `async fn read(..) -> Result<impl
641        // Stream, E>` refactor — after it, `read` returns a future, the future
642        // is `Send`, and this still passes. `spawns_from_generic` is what
643        // rejects that, which is why both exist. ES-2 names only this one.
644        fn assert_stream_is_send<S: crate::SendEventStore>(store: &S, query: &Query) {
645            fn is_send<T: Send>(_: &T) {}
646            is_send(&crate::SendEventStore::read(
647                store,
648                query,
649                ReadOptions::new(),
650            ));
651        }
652
653        assert_stream_is_send(&MemoryEventStore::new(), &Query::all());
654    }
655
656    #[tokio::test]
657    async fn spawns_from_generic() {
658        // ES-2's second half, and ES-3. The composition the `Send` flavour
659        // exists to buy: hold a read across an await inside `tokio::spawn`.
660        // This is the test that rejects `async fn read(..) -> Result<impl
661        // Stream, E>` — `trait_variant` appends `Send` to the outermost `impl
662        // Future` and nothing else, so after that refactor the stream held
663        // across `collect`'s await is `!Send` and this stops compiling.
664        //
665        // Each bound was removed in turn and the compiler asked. Two are
666        // load-bearing and one is not:
667        //   Sync     REQUIRED. Removing it: "future cannot be sent between
668        //            threads safely / captured value is not `Send`".
669        //            `Arc<S>: Send` needs `S: Send + Sync`, and the body also
670        //            holds `&*store` across an await, which needs `&S: Send` —
671        //            that is `S: Sync` again (ES-3).
672        //   'static  REQUIRED. Removing it: `error[E0310]: the parameter type
673        //            `S` may not live long enough`. `tokio::spawn` erases the
674        //            future into a task that outlives this frame.
675        //   Send     REDUNDANT. Removing it still compiles: `trait_variant`
676        //            emits `pub trait SendEventStore: Send`, so the supertrait
677        //            already supplies it. Kept because it states the requirement
678        //            at the signature rather than hiding it in the derivation —
679        //            but nobody should later "discover" it is doing work here.
680        fn spawns_from_generic<S: crate::SendEventStore + Send + Sync + 'static>(
681            store: alloc::sync::Arc<S>,
682        ) -> tokio::task::JoinHandle<usize> {
683            tokio::spawn(async move {
684                // Bound rather than inlined: edition 2024 RPITIT captures every
685                // in-scope lifetime, so the stream borrows the `&Query` even
686                // though its hidden type owns everything. Inlining is E0716.
687                let query = Query::all();
688                let stream = crate::SendEventStore::read(&*store, &query, ReadOptions::new());
689
690                // `map_or` rather than `?` or a binding, deliberately.
691                // `S::Error` carries no `Send` bound, so a `Result<_, S::Error>`
692                // held across the *next* await would make this future `!Send`.
693                // Collapsing to a `usize` first is what lets both awaits sit in
694                // one spawned task.
695                //
696                // And this line does not relax later. ES-6 is `[FROZEN]`, and
697                // ADR-0009 settled it the other way round from what an earlier
698                // version of this comment expected: `Error` keeps
699                // `core::error::Error + 'static` on both ports and both
700                // flavours, and the stronger property is a marker trait that
701                // generic code asks for. A caller who needs the error itself
702                // across an await adds that bound to its own signature and pays
703                // for it there; the port never grows one.
704                let seen = collect(stream).await.map_or(0, |events| events.len());
705
706                // Read-then-append: a second await against the same borrow, so
707                // `&S` really does cross two suspension points.
708                let appended = crate::SendEventStore::append(&*store, &[event("Spawned")], None)
709                    .await
710                    .is_ok();
711
712                seen + usize::from(appended)
713            })
714        }
715
716        let store = alloc::sync::Arc::new(MemoryEventStore::new());
717        store.append(&[event("A")], None).await.unwrap();
718
719        let counted = spawns_from_generic(alloc::sync::Arc::clone(&store))
720            .await
721            .unwrap();
722        assert_eq!(counted, 2);
723        assert_eq!(store.len(), 2);
724    }
725
726    /// The port a provided method would be added to, in miniature.
727    ///
728    /// [`EventStore`](crate::EventStore) has no provided method today, so ES-3
729    /// and ES-4's rule has nothing on the real port to assert against — and a
730    /// rule that can assert nothing is decorative. This trait is the smallest
731    /// thing carrying the two properties the clauses are about: it goes through
732    /// the same `trait_variant::make` the port does, and its provided body
733    /// holds `&self` across an `await`. What is under test is the *derivation*,
734    /// not this trait.
735    ///
736    /// A free generic helper — [`read_decision_model`](crate::read_decision_model)
737    /// is the obvious candidate — cannot stand in, and the reason is worth
738    /// recording because it looks like it should. A helper bound
739    /// `S: EventStore` calls the **bare** flavour's `read`, whose opaque stream
740    /// carries no `Send` inside generic code, so asserting `Send` on that
741    /// helper's future would be false rather than merely weak. Only a
742    /// `trait_variant`-derived twin has a `Send` flavour of the same body.
743    #[trait_variant::make(SendProbe: Send)]
744    trait Probe {
745        /// The required half, standing in for `EventStore::head`.
746        async fn value(&self) -> u64;
747
748        /// The provided half, in ES-4's hand-desugared spelling.
749        ///
750        /// **Not `async fn`.** `trait_variant` clones the `default` block into
751        /// the variant with `asyncness: None` and does not rewrite the body, so
752        /// an `async fn` provided method becomes a non-`async` function
753        /// containing `.await`: `error[E0728]`. That is ES-4's whole content.
754        ///
755        /// **`where Self: Sync`, at the point of use and nowhere else.** The
756        /// `async move` block captures `&self`, and `&Self: Send` holds exactly
757        /// when `Self: Sync`. Taken here, only callers of this method pay for
758        /// it; moved onto the trait or into the `trait_variant` attribute,
759        /// every adapter pays — including the `!Send` edge store the bare
760        /// flavour exists for, which is not `Sync` and could not implement the
761        /// trait at all (ES-3).
762        ///
763        /// Strike the clause and rustc's own `help:` proposes
764        /// `#[trait_variant::make(SendProbe: Send where Self: Sync)]` — the
765        /// attribute-level fix ES-3 names as the wrong one. The suggestion is
766        /// the reason this is worth a compiled test rather than a note: it is
767        /// one keystroke, it is offered by the compiler, and it silently moves
768        /// the obligation onto every implementer.
769        fn doubled(&self) -> impl Future<Output = u64>
770        where
771            Self: Sync,
772        {
773            // `self.value()` is awaited while `&self` is live, which is what
774            // makes this an ES-3 body rather than a decorative one.
775            async move { self.value().await * 2 }
776        }
777    }
778
779    /// Something to instantiate the assertion at. `MemoryEventStore` is not
780    /// used: the claim is about `trait_variant`'s derivation, and borrowing the
781    /// store would only suggest it was about the store.
782    struct Doubler(u64);
783
784    impl SendProbe for Doubler {
785        async fn value(&self) -> u64 {
786            self.0
787        }
788    }
789
790    #[test]
791    fn provided_method_future_is_send_in_generic_code() {
792        // ES-3 and ES-4. The bound is written at the *definition*, so inside
793        // this function the compiler knows nothing about `S` beyond what
794        // `SendProbe + Sync` promises and the obligation is discharged before
795        // monomorphisation. Asserting against a concrete store instead is the
796        // defect that retired `read_stream_is_send`: an auto-trait leaks out of
797        // the hidden type and satisfies the assertion whatever the trait says.
798        //
799        // Two independent things have to hold for this to compile, and they
800        // fail in different places. The *variant's* copy of the provided body
801        // must prove `Send` at its own definition — strike `where Self: Sync`
802        // and the trait above stops compiling, which is ES-3's rejection. And
803        // `trait_variant` must actually have appended `Send` to the cloned
804        // return type — if it stopped doing so, the trait would still compile
805        // and this line is what would notice.
806        fn assert_provided_future_is_send<S: SendProbe + Sync>(probe: &S) {
807            fn is_send<T: Send>(_: &T) {}
808            // Fully qualified, so the assertion names *which* flavour's body
809            // it is about. Method syntax does resolve here — `S`'s only
810            // declared bound is `SendProbe`, so the blanket `Probe` impl
811            // `trait_variant` emits is not a candidate — but it would be
812            // `error[E0034]` the moment this were written against a concrete
813            // store, which satisfies both. That is the module documentation's
814            // warning, and it is also why the qualification is not merely
815            // decoration: it is the spelling that survives the rewrite.
816            is_send(&SendProbe::doubled(probe));
817        }
818
819        // ES-4's "under both flavours **simultaneously**". One body, and it has
820        // to type-check on the bare flavour as well — which is the flavour a
821        // `wasm32` adapter implements and where nothing is `Send`. The bound is
822        // again at the definition, so this says something about the trait
823        // rather than about `Doubler`.
824        fn bare_flavour_offers_the_same_body<S: Probe + Sync>(
825            probe: &S,
826        ) -> impl Future<Output = u64> {
827            Probe::doubled(probe)
828        }
829
830        assert_provided_future_is_send(&Doubler(21));
831
832        // Naming it is what instantiates it, in the shape `store.rs`'s ES-5
833        // assertion uses: the claim is in the signature, so there is nothing to
834        // run and awaiting the future would only exercise `Doubler`.
835        let _ = bare_flavour_offers_the_same_body::<Doubler>;
836    }
837
838    #[tokio::test]
839    async fn tags_filter_with_and_semantics() {
840        let store = MemoryEventStore::new();
841        store
842            .append(
843                &[
844                    event("A").with_tags(Tags::from_pairs([("course", "c1")]).unwrap()),
845                    event("A").with_tags(
846                        Tags::from_pairs([("course", "c1"), ("student", "s1")]).unwrap(),
847                    ),
848                ],
849                None,
850            )
851            .await
852            .unwrap();
853
854        let query = Query::from_item(
855            QueryItem::tagged(Tags::from_pairs([("course", "c1"), ("student", "s1")]).unwrap())
856                .unwrap(),
857        );
858
859        let matched = collect(store.read(&query, ReadOptions::new()))
860            .await
861            .unwrap();
862        assert_eq!(matched.len(), 1);
863        assert_eq!(matched[0].position.get(), 2);
864    }
865    // ---------------------------------------------------------------------
866    // ES-14: `limit` truncates the filtered, ordered result set — and does so
867    // without first materialising the part it is about to throw away.
868    // ---------------------------------------------------------------------
869
870    /// A store whose matches are deliberately scattered.
871    ///
872    /// Neither the head nor the tail of the log is a match, and the two tag
873    /// values interleave, so an implementation that limited the *scanned* set
874    /// rather than the *result* set answers differently from one that does not
875    /// — which a uniformly-matching store would hide.
876    async fn scattered() -> MemoryEventStore {
877        let store = MemoryEventStore::new();
878        let mut batch = Vec::new();
879        for index in 0..12u32 {
880            let event_type = if index % 3 == 0 { "A" } else { "B" };
881            let course = if index % 2 == 0 { "c1" } else { "c2" };
882            batch
883                .push(event(event_type).with_tags(Tags::from_pairs([("course", course)]).unwrap()));
884        }
885        store.append(&batch, None).await.unwrap();
886        store
887    }
888
889    /// Every query/option combination the matrix below walks.
890    fn matrix() -> Vec<(Query, ReadOptions)> {
891        let queries = [
892            Query::all(),
893            Query::from_item(QueryItem::of_types(["A"]).unwrap()),
894            Query::from_item(
895                QueryItem::tagged(Tags::from_pairs([("course", "c1")]).unwrap()).unwrap(),
896            ),
897            Query::from_items([
898                QueryItem::of_types(["A"]).unwrap(),
899                QueryItem::tagged(Tags::from_pairs([("course", "c2")]).unwrap()).unwrap(),
900            ])
901            .unwrap(),
902        ];
903
904        let mut combinations = Vec::new();
905        for query in queries {
906            for backwards in [false, true] {
907                for from in [None, Some(3), Some(9)] {
908                    for to in [None, Some(10)] {
909                        let mut options = ReadOptions::new();
910                        if backwards {
911                            options = options.backwards();
912                        }
913                        if let Some(from) = from {
914                            options = options.from(SequencePosition::new(from).unwrap());
915                        }
916                        if let Some(to) = to {
917                            options = options.to(SequencePosition::new(to).unwrap());
918                        }
919                        combinations.push((query.clone(), options));
920                    }
921                }
922            }
923        }
924        combinations
925    }
926
927    #[tokio::test]
928    async fn read_limit_is_the_first_n_of_the_unlimited_read() {
929        // ES-14 `[FROZEN]`, stated as an oracle that shares no step with the
930        // implementation's truncation: the unlimited read *is* the filtered,
931        // ordered result set, so `limit(n)` must equal its first `n` — whatever
932        // the read path does internally to get there.
933        //
934        // This is the property the H2 remediation must preserve. It is what
935        // rejects `.take(limit)` hoisted one link too far, above the bounds
936        // filters or above `rev()`, where it would limit the SCANNED set: on
937        // this store the two answers differ across most of the matrix, because
938        // the head and the tail of the log are misses.
939        let store = scattered().await;
940
941        for (query, options) in matrix() {
942            let unlimited = collect(store.read(&query, options)).await.unwrap();
943
944            for limit in [0usize, 1, 2, 5, 100] {
945                let limited = collect(store.read(&query, options.limit(limit)))
946                    .await
947                    .unwrap();
948                let expected = &unlimited[..limit.min(unlimited.len())];
949
950                assert_eq!(
951                    limited.iter().map(|e| e.position).collect::<Vec<_>>(),
952                    expected.iter().map(|e| e.position).collect::<Vec<_>>(),
953                    "limit({limit}) must be the first {limit} of the unlimited \
954                     read for {options:?}, not a truncation of a differently \
955                     ordered or differently filtered set"
956                );
957            }
958        }
959    }
960
961    #[tokio::test]
962    async fn backwards_limit_takes_the_highest_matches_not_the_lowest() {
963        // The ordering invariant `rev()`-before-`take()` protects, stated on
964        // its own because the matrix above compares two reads through the same
965        // code path and this compares one read against hand-written positions.
966        //
967        // The layout is Miss, Hit, Hit, Hit, Miss: a `take` above `rev()` would
968        // hand back the two LOWEST matching positions, and a `take` above the
969        // query filter would hand back nothing at all, because position 1 is a
970        // miss. Both are the shape ES-14 `[FROZEN]` rejects.
971        let store = MemoryEventStore::new();
972        let hit = Tags::from_pairs([("course", "c1")]).unwrap();
973        let miss = Tags::from_pairs([("course", "c2")]).unwrap();
974        store
975            .append(
976                &[
977                    event("A").with_tags(miss.clone()),
978                    event("A").with_tags(hit.clone()),
979                    event("A").with_tags(hit.clone()),
980                    event("A").with_tags(hit),
981                    event("A").with_tags(miss),
982                ],
983                None,
984            )
985            .await
986            .unwrap();
987
988        let query = Query::from_item(
989            QueryItem::tagged(Tags::from_pairs([("course", "c1")]).unwrap()).unwrap(),
990        );
991
992        let backwards = collect(store.read(&query, ReadOptions::new().backwards().limit(2)))
993            .await
994            .unwrap();
995        assert_eq!(
996            backwards
997                .iter()
998                .map(|e| e.position.get())
999                .collect::<Vec<_>>(),
1000            [4, 3],
1001            "backwards `limit(2)` must be the two highest MATCHING positions, \
1002             in descending order"
1003        );
1004
1005        let forwards = collect(store.read(&query, ReadOptions::new().limit(2)))
1006            .await
1007            .unwrap();
1008        assert_eq!(
1009            forwards
1010                .iter()
1011                .map(|e| e.position.get())
1012                .collect::<Vec<_>>(),
1013            [2, 3],
1014            "forwards `limit(2)` must be the two lowest MATCHING positions"
1015        );
1016    }
1017
1018    /// This file's own source, so the read path's shape can be asserted rather
1019    /// than reasoned about — the pattern `mod module_doc` uses in `store.rs`.
1020    const SOURCE: &str = include_str!("memory.rs");
1021
1022    /// The body of `SendEventStore::read`, cut out of the production source.
1023    ///
1024    /// Cut *above* this test module on purpose. [`SOURCE`] includes this module
1025    /// too, and every needle the assertion looks for is spelled here as a
1026    /// literal, so an uncut haystack would be satisfied by the test itself.
1027    fn read_body() -> &'static str {
1028        let production = SOURCE.split("#[cfg(test)]").next().unwrap();
1029        let open = production.find("    fn read(").unwrap();
1030        let close = production[open..].find("    async fn append(").unwrap();
1031        &production[open..open + close]
1032    }
1033
1034    #[test]
1035    fn read_takes_the_limit_before_it_clones() {
1036        // ES-14 `[FROZEN]` requires `limit` to truncate the filtered, ordered
1037        // set. It does not require that set to be MATERIALISED first, and
1038        // materialising it is what this store used to do: `.cloned()` ran over
1039        // every match and `Vec::truncate` then dropped the tail it had just
1040        // finished cloning. Measured, `limit(1)` against a million matching
1041        // events cost what `limit(None)` cost to four significant figures —
1042        // 4,000,020 heap operations against 4,000,038 — to return one event.
1043        //
1044        // No behavioural test can see that. The two spellings agree on every
1045        // input by construction, which is why the matrix above is a regression
1046        // guard and not a red test; and an allocation count is out of reach in
1047        // this crate, because `unsafe_code = "forbid"` bars a counting global
1048        // allocator. So the shape is pinned instead, in both directions ES-14
1049        // and the measurement care about:
1050        //
1051        //   * BELOW `rev()` and below both bounds filters, so `take` can never
1052        //     limit the SCANNED set — the wrong implementation ES-14 rejects;
1053        //   * ABOVE `cloned()`, so it never copies a tail it is about to drop.
1054        //
1055        // A pin on source shape is the instrument of last resort, and it is
1056        // used here for the reason `store.rs` uses one: the obligation is real,
1057        // it is not a type, and nothing else in the gate can see it.
1058        const STEPS: &[(&str, &str)] = &[
1059            ("query-filter", ".filter(|event| query.matches"),
1060            ("rev", ".rev()"),
1061            ("bound-filter", ".filter(|event| options."),
1062            ("take", ".take("),
1063            ("cloned", ".cloned()"),
1064            ("collect", ".collect()"),
1065        ];
1066
1067        let body = read_body();
1068        let mut seen: Vec<(usize, &str)> = Vec::new();
1069        for (label, needle) in STEPS {
1070            let mut at = 0;
1071            while let Some(offset) = body[at..].find(needle) {
1072                seen.push((at + offset, label));
1073                at += offset + needle.len();
1074            }
1075        }
1076        seen.sort_unstable();
1077        let order: Vec<&str> = seen.into_iter().map(|(_, label)| label).collect();
1078
1079        assert_eq!(
1080            order,
1081            [
1082                // one scan, shared by both branches
1083                "query-filter",
1084                // backwards: reversed, then bounded, then LIMITED, then cloned
1085                "rev",
1086                "bound-filter",
1087                "bound-filter",
1088                "take",
1089                "cloned",
1090                "collect",
1091                // forwards: the same chain without the reversal
1092                "bound-filter",
1093                "bound-filter",
1094                "take",
1095                "cloned",
1096                "collect",
1097            ],
1098            "`MemoryEventStore::read` must apply `take(limit)` below `rev()` \
1099             and below both bounds filters — above either it would limit the \
1100             scanned set, which ES-14 [FROZEN] rejects — and above `cloned()`, \
1101             so the discarded tail is never cloned at all"
1102        );
1103
1104        assert!(
1105            !body.contains("truncate"),
1106            "`MemoryEventStore::read` still truncates after collecting, so \
1107             every match beyond `limit` is cloned and then dropped"
1108        );
1109    }
1110}