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}