Skip to main content

happenstance_core/
query.rs

1//! Queries: how callers select the slice of the log they care about.
2
3use alloc::boxed::Box;
4use alloc::vec::Vec;
5
6use crate::error::InvalidQuery;
7use crate::event::{EventType, SequencePosition};
8use crate::tag::Tags;
9
10/// One clause of a [`Query`].
11///
12/// An event matches an item when **both** hold:
13///
14/// * its type is one of `types` — OR semantics, and an empty `types` matches any
15///   type;
16/// * its tags contain **all** of `tags` — AND semantics, and an empty `tags`
17///   matches any tags.
18///
19/// At least one of the two must be non-empty; an item constraining neither would
20/// match everything, which is [`Query::all`]'s job.
21///
22/// # Examples
23///
24/// ```
25/// use happenstance_core::{QueryItem, Tags};
26///
27/// // "Any StudentSubscribed or StudentUnsubscribed event for course c1."
28/// let item = QueryItem::new(
29///     ["StudentSubscribed", "StudentUnsubscribed"],
30///     Tags::from_pairs([("course", "c1")])?,
31/// )?;
32///
33/// assert_eq!(item.types().len(), 2);
34/// # Ok::<(), Box<dyn core::error::Error>>(())
35/// ```
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub struct QueryItem {
38    types: Box<[EventType]>,
39    tags: Tags,
40}
41
42impl QueryItem {
43    /// Creates a query item.
44    ///
45    /// Types are deduplicated and sorted so that two items expressing the same
46    /// constraint compare equal.
47    ///
48    /// # Errors
49    ///
50    /// Returns [`InvalidQuery::UnconstrainedItem`] if both `types` and `tags`
51    /// are empty, or [`InvalidQuery::EventType`] if a type string is invalid.
52    ///
53    /// The `InvalidQuery: From<T::Error>` bound is what lets this accept both
54    /// `&str` (fallible conversion) and an already-built [`EventType`]
55    /// (infallible), rather than forcing callers into one or the other.
56    pub fn new<T>(types: impl IntoIterator<Item = T>, tags: Tags) -> Result<Self, InvalidQuery>
57    where
58        T: TryInto<EventType>,
59        InvalidQuery: From<T::Error>,
60    {
61        let types: Vec<EventType> = types
62            .into_iter()
63            .map(|ty| ty.try_into().map_err(InvalidQuery::from))
64            .collect::<Result<_, _>>()?;
65
66        if types.is_empty() && tags.is_empty() {
67            return Err(InvalidQuery::UnconstrainedItem);
68        }
69
70        Ok(Self::canonical(types, tags))
71    }
72
73    /// Creates an item from at least one type the caller already holds.
74    ///
75    /// Total: it returns `QueryItem`, not a `Result`. [`new`](Self::new) has
76    /// two ways to fail, and neither can reach this signature. A built
77    /// [`EventType`] has already been validated, and a separate `first`
78    /// parameter means the item always constrains at least one type, so it can
79    /// never be the unconstrained item `new` refuses. Equal inputs produce `==`
80    /// items through either constructor, because both share one sort and dedup.
81    ///
82    /// Reach for [`new`](Self::new) instead when the types are strings, or
83    /// arrive as a sequence whose length you do not know, and for
84    /// [`of_types`](Self::of_types) when there are also no tags. Both validate
85    /// and can refuse, which is why they return a `Result`. Splitting off the
86    /// head is how "at least one" becomes a fact of the signature here: a slice
87    /// or iterator parameter says nothing about its length, so a total
88    /// constructor over one would have to panic or accept the empty item (ADR-0069).
89    ///
90    /// # Examples
91    ///
92    /// ```
93    /// use happenstance_core::{EventType, QueryItem, Tags};
94    ///
95    /// const COURSE_DEFINED: EventType = EventType::from_static("CourseDefined");
96    /// let tags = Tags::from_pairs([("course", "c1")])?;
97    ///
98    /// // No further types, and no `?` on the item.
99    /// let item = QueryItem::of(COURSE_DEFINED, [], tags);
100    ///
101    /// assert_eq!(item.types(), [COURSE_DEFINED]);
102    /// # Ok::<(), happenstance_core::InvalidTag>(())
103    /// ```
104    #[must_use]
105    pub fn of(first: EventType, rest: impl IntoIterator<Item = EventType>, tags: Tags) -> Self {
106        Self::canonical(core::iter::once(first).chain(rest).collect(), tags)
107    }
108
109    /// The one place both constructors canonicalise. Types are sorted and
110    /// deduplicated so that two items expressing the same constraint compare
111    /// equal. Whether the item constrains anything is the caller's to have
112    /// established: `new` checks it, and `of`'s signature guarantees it.
113    fn canonical(mut types: Vec<EventType>, tags: Tags) -> Self {
114        types.sort_unstable();
115        types.dedup();
116        Self {
117            types: types.into_boxed_slice(),
118            tags,
119        }
120    }
121
122    /// Creates an item constrained only by type.
123    ///
124    /// # Errors
125    ///
126    /// Returns [`InvalidQuery::UnconstrainedItem`] if `types` is empty, or
127    /// [`InvalidQuery::EventType`] if a type string is invalid.
128    pub fn of_types<T>(types: impl IntoIterator<Item = T>) -> Result<Self, InvalidQuery>
129    where
130        T: TryInto<EventType>,
131        InvalidQuery: From<T::Error>,
132    {
133        Self::new(types, Tags::empty())
134    }
135
136    /// Creates an item constrained only by tags.
137    ///
138    /// # Errors
139    ///
140    /// Returns [`InvalidQuery::UnconstrainedItem`] if `tags` is empty.
141    pub fn tagged(tags: Tags) -> Result<Self, InvalidQuery> {
142        Self::new(core::iter::empty::<EventType>(), tags)
143    }
144
145    /// The types this item accepts, sorted. Empty means "any type".
146    pub fn types(&self) -> &[EventType] {
147        &self.types
148    }
149
150    /// The tags an event must carry. Empty means "any tags".
151    pub fn tags(&self) -> &Tags {
152        &self.tags
153    }
154
155    /// Whether an event with this type and these tags matches.
156    pub fn matches(&self, event_type: &EventType, tags: &Tags) -> bool {
157        let type_ok = self.types.is_empty() || self.types.binary_search(event_type).is_ok();
158        type_ok && tags.contains_all(&self.tags)
159    }
160}
161
162/// A filter over the log.
163///
164/// Modelled as an enum rather than a `Vec<QueryItem>` because the specification
165/// requires a query to hold at least one item **or** to match everything. An
166/// empty item list is not a legal query, and is not representable from outside
167/// this crate: [`Items`](Self::Items) is `#[non_exhaustive]`, so the only way in
168/// is [`from_items`](Self::from_items), which refuses an empty sequence.
169///
170/// That seal is load-bearing rather than tidy. An `AppendCondition` built on a
171/// query with no items is a condition nothing can ever violate — a conditional
172/// append that is silently unconditional, which is a lost update with no
173/// diagnostic anywhere.
174///
175/// Items combine with OR: an event matches the query when it matches any item.
176///
177/// # Examples
178///
179/// ```
180/// use happenstance_core::{Event, Query, QueryItem, Tags};
181///
182/// let query = Query::from_items([
183///     QueryItem::of_types(["CourseDefined"])?,
184///     QueryItem::tagged(Tags::from_pairs([("student", "s1")])?)?,
185/// ])?;
186///
187/// let event = Event::new("CourseDefined", &b"{}"[..])?;
188/// assert!(query.matches(event.event_type(), event.tags()));
189///
190/// assert!(Query::all().matches(event.event_type(), event.tags()));
191/// # Ok::<(), Box<dyn core::error::Error>>(())
192/// ```
193#[derive(Debug, Clone, PartialEq, Eq, Default)]
194pub enum Query {
195    /// Matches every event in the store.
196    #[default]
197    All,
198    /// Matches events satisfying at least one item.
199    ///
200    /// `#[non_exhaustive]` so that no downstream crate can build one directly.
201    /// Inside this crate the variant is ordinary; outside it, it is matchable
202    /// but not constructible.
203    ///
204    /// **Downstream, the tuple spelling is not one of the ways to match it.**
205    /// `Query::Items(..)` is `error[E0603]: tuple variant `Items` is private`,
206    /// because a tuple pattern resolves through the variant's *constructor* and
207    /// `#[non_exhaustive]` is precisely what makes that constructor crate-private.
208    /// The struct spellings reach the fields without naming the constructor, so
209    /// `Query::Items { .. }` and `Query::Items { 0: held, .. }` both compile.
210    /// Measured on 1.97.1 by `query_items_is_not_constructible_downstream` in
211    /// `happenstance-testkit`. Most callers want [`Query::items`] and never meet
212    /// this.
213    #[non_exhaustive]
214    Items(Box<[QueryItem]>),
215}
216
217impl Query {
218    /// The query that matches everything.
219    pub fn all() -> Self {
220        Self::All
221    }
222
223    /// Builds a query from one or more items.
224    ///
225    /// # Errors
226    ///
227    /// Returns [`InvalidQuery::NoItems`] if `items` is empty. Use
228    /// [`Query::all`] to match everything.
229    pub fn from_items(items: impl IntoIterator<Item = QueryItem>) -> Result<Self, InvalidQuery> {
230        let items: Vec<QueryItem> = items.into_iter().collect();
231        if items.is_empty() {
232            return Err(InvalidQuery::NoItems);
233        }
234        Ok(Self::Items(items.into_boxed_slice()))
235    }
236
237    /// Convenience for the single-item case.
238    ///
239    /// Infallible, and typed that way: one item is never zero items, so the
240    /// `Result` this used to return could not be `Err` and only taught callers
241    /// to write a `?` that never fired.
242    #[must_use]
243    pub fn from_item(item: QueryItem) -> Self {
244        Self::Items(alloc::vec![item].into_boxed_slice())
245    }
246
247    /// The items, or `None` for [`Query::All`].
248    pub fn items(&self) -> Option<&[QueryItem]> {
249        match self {
250            Self::All => None,
251            Self::Items(items) => Some(items),
252        }
253    }
254
255    /// Whether this query matches everything.
256    pub const fn is_all(&self) -> bool {
257        matches!(self, Self::All)
258    }
259
260    /// Whether an event with this type and these tags matches.
261    ///
262    /// Adapters that can push filtering down into storage should do so and use
263    /// this only as a reference; adapters that cannot may filter in memory with
264    /// it directly.
265    pub fn matches(&self, event_type: &EventType, tags: &Tags) -> bool {
266        match self {
267            Self::All => true,
268            Self::Items(items) => items.iter().any(|item| item.matches(event_type, tags)),
269        }
270    }
271}
272
273/// How to traverse the matched events.
274///
275/// # Examples
276///
277/// ```
278/// use happenstance_core::{ReadOptions, SequencePosition};
279///
280/// // The specification's own example: the 50 events at or before position 321,
281/// // newest first.
282/// let options = ReadOptions::new()
283///     .from(SequencePosition::new(321).expect("non-zero"))
284///     .backwards()
285///     .limit(50);
286///
287/// assert!(options.backwards);
288/// assert_eq!(options.limit, Some(50));
289/// ```
290///
291/// A closed window, which is what `to` is for — a backfill worker owning
292/// `[1, H]` while a tail worker owns everything above it:
293///
294/// ```
295/// use happenstance_core::{ReadOptions, SequencePosition};
296///
297/// let head = SequencePosition::new(53_000_000).expect("non-zero");
298/// let backfill = ReadOptions::new().from(SequencePosition::FIRST).to(head);
299///
300/// assert_eq!(backfill.to, Some(head));
301/// ```
302///
303/// A limit of zero reads nothing, which is what makes `.limit(budget - fetched)`
304/// safe at parity:
305///
306/// ```
307/// use happenstance_core::ReadOptions;
308///
309/// assert_eq!(ReadOptions::new().limit(0).limit, Some(0));
310/// ```
311#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
312#[non_exhaustive]
313pub struct ReadOptions {
314    /// Where to start, **inclusive**. `None` starts at the first event when
315    /// reading forwards, or the last when reading backwards.
316    ///
317    /// A threshold, not a seek: `from` need not name an event that exists. A
318    /// read from a position nothing occupies yields the next matching event
319    /// above it (or below, reading backwards), rather than erroring or coming
320    /// back empty.
321    pub from: Option<SequencePosition>,
322    /// Where to stop, **inclusive**. `None` reads to the end.
323    ///
324    /// Under [`backwards`](Self::backwards), `from` remains the starting
325    /// (higher) bound and `to` the stopping (lower) one — the two swap roles in
326    /// position order, not in meaning.
327    pub to: Option<SequencePosition>,
328    /// Read in descending position order instead of ascending.
329    pub backwards: bool,
330    /// Stop after this many events. `None` reads all matches; `Some(0)` reads
331    /// none.
332    pub limit: Option<usize>,
333}
334
335impl ReadOptions {
336    /// Default options: forwards, from the beginning, unlimited.
337    pub const fn new() -> Self {
338        Self {
339            from: None,
340            to: None,
341            backwards: false,
342            limit: None,
343        }
344    }
345
346    /// Starts at `position`, inclusive.
347    #[must_use]
348    pub const fn from(mut self, position: SequencePosition) -> Self {
349        self.from = Some(position);
350        self
351    }
352
353    /// Reads newest-first.
354    ///
355    /// One-way: there is no `forwards()`, because the default already is.
356    #[must_use]
357    pub const fn backwards(mut self) -> Self {
358        self.backwards = true;
359        self
360    }
361
362    /// Stops at `position`, inclusive.
363    ///
364    /// This is the caller-side spelling of a window, and it must not be confused
365    /// with a store's internal pagination: **one `read` is one sample; *n*
366    /// chunked reads are *n* samples.** Nothing in the contract makes two `read`
367    /// calls one snapshot. What makes stitching windows together sound is the
368    /// visibility invariant — no event ever becomes visible below a position a
369    /// reader has already observed — and not any isolation promise about `read`.
370    #[must_use]
371    pub const fn to(mut self, position: SequencePosition) -> Self {
372        self.to = Some(position);
373        self
374    }
375
376    /// Reads at most `limit` events.
377    ///
378    /// **A limit of zero reads nothing.** This is a deliberate divergence from
379    /// the DCB reference implementation, which treats `limit: 0` as unlimited
380    /// through JavaScript falsiness — a coherent reading of `0` in a language
381    /// where `0` is falsy, and not one available here. It matches SQL's
382    /// `LIMIT 0` and every paging API instead.
383    ///
384    /// The caller this protects is the one writing `.limit(budget - fetched)`:
385    /// under the old behaviour, reaching parity turned a paging loop into a full
386    /// scan of the log, silently.
387    #[must_use]
388    pub const fn limit(mut self, limit: usize) -> Self {
389        self.limit = Some(limit);
390        self
391    }
392}
393
394#[cfg(feature = "serde")]
395mod serde_impls {
396    //! Wire mirrors. **Every field is written on every serialisation** — no
397    //! `skip_serializing_if`, no `#[serde(default)]` — and neither attribute may
398    //! come back (WF-2; ADR-0016 §3 and §4).
399    //!
400    //! Skipping makes the encoding positional in a format that is not
401    //! self-describing: postcard has no field names to resynchronise against, so
402    //! an absent `types` is read as whatever the next field's bytes happen to
403    //! be. The saving was one byte per absent field. `#[serde(default)]` costs
404    //! nothing on the write side and only widens what the decoder accepts,
405    //! which is a second undocumented format nothing describes.
406    //!
407    use super::{Query, QueryItem};
408    use crate::event::EventType;
409    use crate::tag::Tags;
410    use alloc::boxed::Box;
411    use alloc::vec::Vec;
412    use serde::{Deserialize, Deserializer, Serialize, Serializer};
413
414    #[derive(Serialize, Deserialize)]
415    #[serde(rename = "QueryItem")]
416    struct QueryItemWire {
417        types: Box<[EventType]>,
418        tags: Tags,
419    }
420
421    /// The borrowing counterpart of [`QueryItemWire`], used on the way **out**.
422    ///
423    /// Same `rename`, same field names in the same order. `&[EventType]` and
424    /// `Box<[EventType]>` are both a seq in serde's data model, so the bytes are
425    /// unchanged; what goes is `self.types().into()`, which allocated a boxed
426    /// slice and deep-cloned every `EventType` into it, and `self.tags().clone()`,
427    /// which allocated one `String` per tag. Measured at 64 tags: 139 heap
428    /// operations owned against 11 borrowed, for 516 bytes of postcard
429    /// (`experiments/event-clone-allocations/results/clone-cost.md`).
430    #[derive(Serialize)]
431    #[serde(rename = "QueryItem")]
432    struct QueryItemRef<'a> {
433        types: &'a [EventType],
434        tags: &'a Tags,
435    }
436
437    impl Serialize for QueryItem {
438        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
439            QueryItemRef {
440                types: self.types(),
441                tags: self.tags(),
442            }
443            .serialize(serializer)
444        }
445    }
446
447    impl<'de> Deserialize<'de> for QueryItem {
448        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
449            let wire = QueryItemWire::deserialize(deserializer)?;
450            Self::new(wire.types.into_vec(), wire.tags).map_err(serde::de::Error::custom)
451        }
452    }
453
454    /// Mirror of [`Query`], carrying the tag that `Option` could not.
455    ///
456    /// The previous encoding wrote `All` as `serialize_none` and `Items` as
457    /// `serialize_some`, which loses in a way that is easy to miss coming from
458    /// C#. `Nullable<T>` is a distinct runtime type carrying its own `bool`, so
459    /// `T?` and `T` are never the same value; in serde's data model `Option` is
460    /// **transparent** — `serialize_some(v)` emits exactly the bytes `v` emits.
461    /// So `Some(Query::Items(..))` was byte-identical to `Query::Items(..)`,
462    /// `Some(Query::All)` and `None::<Query>` were both `null`, and `All`
463    /// occupied the format's null: the value every buggy peer emits by accident.
464    ///
465    /// Externally tagged rather than internally tagged because an internal tag
466    /// requires a self-describing format and postcard is not one. The tag costs
467    /// one byte there (`All` is `[00]`) and buys `null != "All"` in JSON.
468    #[derive(Serialize, Deserialize)]
469    #[serde(rename = "Query")]
470    enum QueryWire {
471        All,
472        Items(Vec<QueryItem>),
473    }
474
475    /// The borrowing counterpart of [`QueryWire`].
476    ///
477    /// Same `rename` and the same two variants in the same order, so the external
478    /// tag is the same byte. `Items(&'a [QueryItem])` emits the seq that
479    /// `Items(Vec<QueryItem>)` emitted; what goes is `items.to_vec()`, which deep-
480    /// cloned every item — each of which owns a `Tags` and a `Box<[EventType]>` —
481    /// to hand the derive a value it could have borrowed.
482    #[derive(Serialize)]
483    #[serde(rename = "Query")]
484    enum QueryRef<'a> {
485        All,
486        Items(&'a [QueryItem]),
487    }
488
489    impl Serialize for Query {
490        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
491            match self {
492                Self::All => QueryRef::All,
493                Self::Items(items) => QueryRef::Items(items),
494            }
495            .serialize(serializer)
496        }
497    }
498
499    impl<'de> Deserialize<'de> for Query {
500        /// Rejects a zero-item `Items`.
501        ///
502        /// Deserialisation is the other door into a private invariant, and
503        /// `Query::from_items` is the only thing that enforces it. An empty
504        /// item list is not "match nothing" — it is a query no event can
505        /// satisfy arriving where the caller asked for a filter.
506        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
507            match QueryWire::deserialize(deserializer)? {
508                QueryWire::All => Ok(Self::All),
509                QueryWire::Items(items) => {
510                    Self::from_items(items).map_err(serde::de::Error::custom)
511                }
512            }
513        }
514    }
515
516    // WF-12 (ADR-0016 §13): `ReadOptions` is not on the wire, and no wire
517    // mirror lives here for it. `from`/`to` are a store-local position with no
518    // meaning at another store, and `backwards`/`limit` are traversal choices
519    // a reader makes for itself, not a value any message carries. It appears
520    // in no envelope this crate defines; giving it `Serialize`/`Deserialize`
521    // anyway would make a decoder's willingness to accept it a promise this
522    // crate never intended to keep.
523}
524
525#[cfg(test)]
526mod tests {
527    #![allow(clippy::unwrap_used)]
528
529    use super::*;
530
531    fn ty(value: &str) -> EventType {
532        EventType::new(value).unwrap()
533    }
534
535    fn tags(pairs: &[(&str, &str)]) -> Tags {
536        Tags::from_pairs(pairs.iter().copied()).unwrap()
537    }
538
539    #[test]
540    fn empty_query_is_unrepresentable() {
541        assert!(matches!(Query::from_items([]), Err(InvalidQuery::NoItems)));
542    }
543
544    #[test]
545    fn unconstrained_item_is_rejected() {
546        assert!(matches!(
547            QueryItem::new(core::iter::empty::<EventType>(), Tags::empty()),
548            Err(InvalidQuery::UnconstrainedItem)
549        ));
550    }
551
552    #[test]
553    fn types_are_ord_within_an_item() {
554        let item = QueryItem::of_types(["B", "A", "B"]).unwrap();
555        assert_eq!(item.types().len(), 2);
556        assert!(item.matches(&ty("A"), &Tags::empty()));
557        assert!(item.matches(&ty("B"), &Tags::empty()));
558        assert!(!item.matches(&ty("C"), &Tags::empty()));
559    }
560
561    #[test]
562    fn tags_are_and_within_an_item() {
563        let item = QueryItem::tagged(tags(&[("course", "c1"), ("student", "s1")])).unwrap();
564
565        assert!(item.matches(&ty("Any"), &tags(&[("course", "c1"), ("student", "s1")])));
566        // A superset still matches.
567        assert!(item.matches(
568            &ty("Any"),
569            &tags(&[("course", "c1"), ("student", "s1"), ("extra", "e")])
570        ));
571        // A partial overlap does not.
572        assert!(!item.matches(&ty("Any"), &tags(&[("course", "c1")])));
573    }
574
575    #[test]
576    fn items_are_or_across_a_query() {
577        let query = Query::from_items([
578            QueryItem::of_types(["A"]).unwrap(),
579            QueryItem::tagged(tags(&[("student", "s1")])).unwrap(),
580        ])
581        .unwrap();
582
583        assert!(query.matches(&ty("A"), &Tags::empty()));
584        assert!(query.matches(&ty("Z"), &tags(&[("student", "s1")])));
585        assert!(!query.matches(&ty("Z"), &tags(&[("student", "s2")])));
586    }
587
588    #[test]
589    fn item_combines_type_and_tags_with_and() {
590        let item = QueryItem::new(["A"], tags(&[("course", "c1")])).unwrap();
591
592        assert!(item.matches(&ty("A"), &tags(&[("course", "c1")])));
593        assert!(!item.matches(&ty("A"), &tags(&[("course", "c2")])));
594        assert!(!item.matches(&ty("B"), &tags(&[("course", "c1")])));
595    }
596
597    #[test]
598    fn zero_limit_means_zero_events() {
599        // This test previously asserted the opposite, and the old behaviour is
600        // worth naming rather than just deleting: `limit` stored
601        // `NonZeroUsize::new(limit)`, so zero became `None` — unlimited — before
602        // any adapter saw it. A paging loop writing `.limit(budget - fetched)`
603        // therefore read the whole log at exactly the moment its budget ran out.
604        assert_eq!(ReadOptions::new().limit(0).limit, Some(0));
605        assert_eq!(
606            ReadOptions::new().limit,
607            None,
608            "unset still means unlimited"
609        );
610    }
611
612    #[test]
613    fn to_is_recorded_and_independent_of_from() {
614        let lower = SequencePosition::new(10).unwrap();
615        let upper = SequencePosition::new(20).unwrap();
616        let options = ReadOptions::new().from(lower).to(upper);
617
618        assert_eq!(options.from, Some(lower));
619        assert_eq!(options.to, Some(upper));
620        // Direction does not reassign the fields; it reverses what they bound.
621        assert_eq!(options.backwards().to, Some(upper));
622    }
623
624    #[test]
625    fn from_item_is_infallible_and_yields_one_item() {
626        let query = Query::from_item(QueryItem::of_types(["A"]).unwrap());
627        assert_eq!(query.items().map(<[_]>::len), Some(1));
628    }
629}