ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
//! THE SNAPSHOT KEEPER: where a fused ranking already computed waits for the client's next stretch.
//!
//! ```text
//! Schema::build(root, …).data(SnapshotKeeper::new())        // the deployment, once
//!         │
//!         ▼  the FIRST ask — the fold runs, its answer is kept, and a page token names it
//! keeper.keep("travelSearchStretch", rows)      →  PageToken
//! keeper.read(&page_token, "travelSearchStretch", 20)  →  Stretch { rows[0..20], next }
//!         │
//!         ▼  the NEXT ask — no fold, no engine call, no tower walked
//! keeper.read(&next, "travelSearchStretch", 20)        →  Stretch { rows[20..40], next }
//! ```
//!
//! # The fused ranking ALREADY COMPUTED is the snapshot
//!
//! Nothing here re-asks anything. The ruled reason is the one the single-shot paragraph in this
//! module's parent states: resumption is a per-BACKEND capability — Lucene and Elasticsearch have
//! watermarks, tantivy has an offset rebuild, a raw ANN library has nothing at all — and a uniform
//! contract over that spread is a promise the framework cannot keep. So the framework never asks a
//! backend to resume. It holds the answer it already has and cuts stretches off it, which is a
//! promise it can keep for every backend at once, including the ones that can do nothing.
//!
//! What that buys is EXACT-WITHIN-SNAPSHOT: the rows a client walks are one ranking taken at one
//! moment, so a document indexed between two stretches neither appears twice nor pushes a row off
//! the end. What it costs is that the walk sees a ranking that is no longer current — which is the
//! honest half, and the reason a snapshot dies quickly rather than being kept warm.
//!
//! # It holds (R, V, score) ONLY, and the memory clause is why
//!
//! A kept row is the ROOT KEY, the fused score and the per-member evidence — never a hydrated
//! entity. Hydration happens per stretch and lazily, at the moment a stretch is cut, so what the
//! keeper's memory scales with is the number of live snapshots times their depth, and both are
//! knobs with shipped constants. A keeper that held rows would scale with somebody else's row
//! width, which is not a number this crate can bound.
//!
//! # It is SESSION-EPHEMERAL, and the eviction is TWO policies rather than one
//!
//! A page token is not a durable id and nothing may assume one still means anything later. Two
//! independent reapers say so:
//!
//! - **TTL** — a snapshot older than [`SnapshotKeeper::ttl`] is gone whether or not the store is
//!   under pressure. This is the one that makes a page token die with its session: a client that
//!   walked away leaves nothing behind.
//! - **LRU** — when the store is full, the least recently READ snapshot goes first. This is the one
//!   that bounds the store under load, and it reads recency rather than age on purpose: a client
//!   still walking its answer is the last one whose answer should be taken away.
//!
//! Both roads end in a NAMED refusal rather than an empty stretch. An empty answer and *your
//! answer is gone, ask again* are different facts and a client can act on only one of them.
//!
//! # The word is PAGE TOKEN, and the contrast with the keyset CURSOR is the whole reason
//!
//! [`crate::cursor`]'s `Cursor` is the record tier's word and it is a different thing wearing a
//! similar shape. The one sentence that separates them:
//!
//! > **A cursor CARRIES its position; a page token CLAIMS what the keeper is holding.**
//!
//! Everything else follows from that. A cursor is the boundary row's own ordering tuple, so it is
//! self-describing, the server stores nothing, and it is refused by the ORDER it was minted under.
//! A page token is a name for state, so the server stores everything, the bytes describe nothing,
//! and it is refused by the KEEPER that minted it and by the clock. Two vocabularies, kept apart at
//! every level: `Cursor`/`CursorError` against [`PageToken`]/[`PageTokenRefusal`],
//! `encode`/`decode` against [`Display`](core::fmt::Display)/[`FromStr`](core::str::FromStr),
//! `after`/`before` against `pageToken`. The one thing they share is the base64url spelling, which
//! they share on purpose — [`crate::cursor`]'s alphabet, its refusal of padding, and its *two
//! spellings of one token is one spelling too many* are this token's too, and there is exactly one
//! implementation of them.
//!
//! # It is the SEARCH grain, and exhaustive enumeration is not this road
//!
//! Search is top-K by design. A client that wants every row of a collection walks the record tier's
//! keyset, which pages a live table without holding anything. This keeper pages a RANKING, which is
//! a different question with a different promise, and the depth ceiling is where the difference is
//! written down: past it there are no more stretches, because past it there was never an answer.

use core::{
  fmt,
  num::NonZeroUsize,
  str::FromStr,
  sync::atomic::{AtomicU64, Ordering},
  time::Duration,
};
use std::{
  any::Any,
  collections::{BTreeMap, HashMap, hash_map::RandomState},
  hash::{BuildHasher, Hasher},
  sync::{Arc, Mutex},
  time::Instant,
};

/// HOW MANY SNAPSHOTS one keeper holds before the least recently read one goes.
///
/// TIER ONE of a PROTECTIVE number: this bounds what every client together may make one deployment
/// hold, so tier two is a launch's own word and there is no tier three — see the module's knob
/// table in the parent's three-tier note.
///
/// 128 against [`DEFAULT_SNAPSHOT_DEPTH`]'s 1000 is the arithmetic that makes the pair a bound
/// rather than a wish: a kept row is a root key, an `f64` and one evidence entry per member that
/// saw it, so a hundred bytes is the right order and the product is single-digit megabytes. The
/// number is SELF-DECLARED UNTUNED — no deployment has been measured under it.
pub const DEFAULT_SNAPSHOT_CAPACITY: NonZeroUsize = match NonZeroUsize::new(128) {
  Some(capacity) => capacity,
  None => unreachable!(),
};

/// HOW LONG a snapshot outlives the ask that made it.
///
/// TIER ONE of a PROTECTIVE number, for [`DEFAULT_SNAPSHOT_CAPACITY`]'s reason.
///
/// Five minutes is a paging session's own order — long enough that a reader who scrolls, reads a
/// result and comes back still has an answer, short enough that a ranking never goes stale in a way
/// a person would notice. SELF-DECLARED UNTUNED.
pub const DEFAULT_SNAPSHOT_TTL: Duration = Duration::from_secs(300);

/// HOW DEEP a kept ranking goes — the shipped ceiling on one snapshot's length.
///
/// TIER ONE of a PROTECTIVE number that DOES have a tier three, and it is the only one of the three
/// that does: this one is asked at a QUESTION's grain rather than the store's, so the request's own
/// `depth` composes with it — in MIN-TIGHTEN FORM, through [`route_depth`](super::route_depth), the
/// same one function every other wall in this pipeline is spelled by. A request may ask for a
/// shallower snapshot and can never ask for a deeper one.
///
/// A thousand is where *page through a ranking* stops being the question a person is asking. SELF-
/// DECLARED UNTUNED.
pub const DEFAULT_SNAPSHOT_DEPTH: NonZeroUsize = match NonZeroUsize::new(1000) {
  Some(depth) => depth,
  None => unreachable!(),
};

/// The one page token frame version this build writes and reads.
const VERSION: u8 = 1;

/// The frame: a version byte, the keeper's identity, the snapshot's serial and the offset.
const FRAME: usize = 1 + IDENTITY + 8 + 8;

/// The width of a keeper's identity.
const IDENTITY: usize = 16;

/// What makes two keepers' identities distinct even when a process mints them in one instant.
static SERIAL: AtomicU64 = AtomicU64::new(0);

/// WHICH KEEPER minted a page token — the identity a page token carries so another keeper
/// refuses it.
///
/// # It is DISTINCTNESS first and unguessability second, and both are honest
///
/// The job is separation: a page token names the store that is holding its rows, and every other
/// store — a sibling keeper in one process, the same deployment after a restart, another deployment
/// entirely — refuses it by name instead of reaching into a table where the serial might happen to
/// land on somebody else's answer. The serial alone would do that job.
///
/// The 128 bits are the second half: the rows behind a page token are one client's search results,
/// so a value another client could GUESS would be a way to read them. The bits come from
/// [`RandomState`], which is seeded from the operating system once per thread — the same source
/// that makes this crate's hash maps collision-resistant. It is NOT a cryptographic random number
/// generator and this note does not claim it is: a deployment whose threat model needs one puts an
/// authenticated session in front of the schema, which is the tier that layer belongs to.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct KeeperId([u8; IDENTITY]);

impl KeeperId {
  /// A fresh identity — distinct from every other by the serial, unguessable by the seed.
  fn fresh() -> Self {
    let mut bytes = [0_u8; IDENTITY];
    let serial = SERIAL.fetch_add(1, Ordering::Relaxed);
    for (half, slot) in bytes.as_chunks_mut::<8>().0.iter_mut().enumerate() {
      let mut hasher = RandomState::new().build_hasher();
      hasher.write_u64(serial);
      hasher.write_usize(half);
      *slot = hasher.finish().to_be_bytes();
    }
    Self(bytes)
  }
}

/// A CLAIM on a stretch of a kept ranking: which keeper is holding it, which snapshot, and how far
/// in this client has read.
///
/// # It is opaque OUTSIDE and typed INSIDE, and a client never builds one
///
/// There is no public constructor. A page token comes from [`SnapshotKeeper::keep`] or from the
/// `next` of a [`Stretch`], travels to a client as one base64url string through
/// [`Display`](core::fmt::Display), and comes back through
/// [`FromStr`](core::str::FromStr). The three numbers inside are the framework's business and the
/// absence of a constructor is what keeps them so: an offset a client could write is an offset a
/// client could walk past the end of, or into the middle of somebody else's arithmetic.
///
/// # The verbs are `Display`/`FromStr` where the keyset cursor's are `encode`/`decode`
///
/// Deliberately, and the module note says why: the two tokens must not be reachable by the same
/// words. These are also the two traits Rust already has for *a value with one string form*, so the
/// choice costs nothing beyond not colliding.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct PageToken {
  keeper: KeeperId,
  snapshot: u64,
  from: u64,
}

impl PageToken {
  /// A page token for `snapshot` at `from`, minted by `keeper`.
  const fn new(keeper: KeeperId, snapshot: u64, from: u64) -> Self {
    Self {
      keeper,
      snapshot,
      from,
    }
  }

  /// How many rows of the snapshot this page token has already walked past.
  ///
  /// The one number a caller outside the keeper has any use for: it is the *you are here* a face
  /// can show, and it is the offset the next stretch starts at.
  #[inline]
  #[must_use]
  pub const fn walked(&self) -> u64 {
    self.from
  }

  /// The frame, big-endian throughout — the keeper first, so two keepers' page tokens differ in
  /// their first bytes rather than in their last.
  fn frame(&self) -> [u8; FRAME] {
    let mut bytes = [0_u8; FRAME];
    bytes[0] = VERSION;
    bytes[1..1 + IDENTITY].copy_from_slice(&self.keeper.0);
    bytes[1 + IDENTITY..9 + IDENTITY].copy_from_slice(&self.snapshot.to_be_bytes());
    bytes[9 + IDENTITY..FRAME].copy_from_slice(&self.from.to_be_bytes());
    bytes
  }
}

/// The one string a client ever holds.
///
/// [`crate::cursor`]'s spelling, from [`crate::cursor`]'s own implementation: base64url, no
/// padding, and a padded or otherwise off-alphabet string refused coming back rather than
/// tolerated. One base64url in this crate, so a token cannot be legal at one tier and illegal at
/// the other.
impl fmt::Display for PageToken {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    f.write_str(&crate::cursor::text::encode(&self.frame()))
  }
}

/// The page token `text` spells, or why it is not one.
///
/// Refuses rather than guessing at every step, which is the untrusted-input obligation the keyset
/// cursor's own codec states and this one inherits: a page token is bytes a client had, and
/// answering a plausible claim for bytes the framework did not write is how a forged token becomes
/// a stranger's search results.
impl FromStr for PageToken {
  type Err = PageTokenRefusal;

  fn from_str(text: &str) -> Result<Self, Self::Err> {
    let bytes = crate::cursor::text::decode(text).ok_or(PageTokenRefusal::Malformed)?;
    let frame: [u8; FRAME] = bytes.as_slice().try_into().map_err(|_| {
      // A WIDTH CHECK IS THE WHOLE CHECK for a fixed frame, which is the codec doctrine's own
      // sentence: nothing inside is self-describing, so a frame of the wrong length is not a page
      // token this build wrote and no arm of it can be read.
      PageTokenRefusal::Malformed
    })?;
    if frame[0] != VERSION {
      return Err(PageTokenRefusal::Malformed);
    }
    let mut keeper = [0_u8; IDENTITY];
    keeper.copy_from_slice(&frame[1..1 + IDENTITY]);
    let mut snapshot = [0_u8; 8];
    snapshot.copy_from_slice(&frame[1 + IDENTITY..9 + IDENTITY]);
    let mut from = [0_u8; 8];
    from.copy_from_slice(&frame[9 + IDENTITY..FRAME]);
    Ok(Self::new(
      KeeperId(keeper),
      u64::from_be_bytes(snapshot),
      u64::from_be_bytes(from),
    ))
  }
}

/// Why a page token cannot be honoured.
///
/// # It is a REFUSAL where the keyset cursor's is an ERROR, and the difference is who is answering
///
/// `CursorError` is a CODEC's report: these bytes are not a position in this order. Every arm of it
/// is a fact about the string. This type has one arm of that kind ([`Malformed`](Self::Malformed))
/// and four of another: the string was perfectly well formed and the KEEPER is declining it — the
/// snapshot has aged out, been evicted, belongs to another store, or was minted at another field.
/// A refusal is what this crate calls an answer of that shape, so that is the word.
///
/// # Every arm ends in *ask again*, and none of them is an empty stretch
///
/// A client holding a refused page token has one road: put the question again and take a fresh
/// snapshot. Saying so by name is the whole point — an empty list would tell the same client that
/// it had reached the end of its answer, which is a different fact and leads to a different screen.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum PageTokenRefusal {
  /// The string is not a page token this build wrote: off-alphabet, padded, the wrong width, or a
  /// frame version this build does not read.
  Malformed,
  /// A well-formed page token minted by ANOTHER keeper — a sibling store, or this deployment
  /// before it restarted. Snapshots do not survive the process that computed them.
  Foreign,
  /// The snapshot was still held and had aged past the keeper's TTL.
  Expired,
  /// No such snapshot: evicted to make room for a newer one, or never minted here at all.
  Unknown,
  /// The page token was minted at another field and names another answer.
  ///
  /// The field it was minted at is carried so the sentence can say both halves. It is `'static`
  /// because a road's name is an emitted literal.
  Crossed {
    /// The field that minted this page token.
    minted_at: &'static str,
    /// The field it was handed back to.
    asked_at: String,
  },
}

impl fmt::Display for PageTokenRefusal {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match self {
      Self::Malformed => f.write_str("this is not a page token this build wrote"),
      Self::Foreign => f.write_str(
        "this page token was minted by another keeper and its answer is not held here — ask the \
         question again",
      ),
      Self::Expired => {
        f.write_str("this page token's answer has expired — ask the question again for a fresh one")
      }
      Self::Unknown => f.write_str(
        "this page token's answer is no longer held — ask the question again for a fresh one",
      ),
      Self::Crossed {
        minted_at,
        asked_at,
      } => write!(
        f,
        "this page token was minted at `{minted_at}` and cannot be handed back to `{asked_at}`",
      ),
    }
  }
}

impl core::error::Error for PageTokenRefusal {}

/// One stretch of a kept ranking, and the claim on the next one.
///
/// The crate's own word for *the next piece of a ranking*, which the single-shot note used for the
/// re-ask road before there was a keeper to take it over.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Stretch<T> {
  rows: Vec<T>,
  next: Option<PageToken>,
}

impl<T> Stretch<T> {
  /// NO ROWS AND NOTHING AFTER THEM — what a road answers a request that asked for no rows.
  ///
  /// The edge-zero law's own shape at this grain: `first: 0` is not a smaller question but no
  /// question at all, so it is answered before any keeper is asked and the absent claim is honest —
  /// there is no stretch after a question nobody put.
  #[inline]
  #[must_use]
  pub const fn empty() -> Self {
    Self {
      rows: Vec::new(),
      next: None,
    }
  }

  /// The rows of this stretch, in the ranking's own order.
  #[inline]
  #[must_use]
  pub fn rows(&self) -> &[T] {
    &self.rows
  }

  /// The claim on the stretch after this one, or [`None`] at the end of the ranking.
  ///
  /// **[`None`] is the END and never a refusal.** A client that reaches it has walked the whole
  /// snapshot; a client whose page token was declined never got a `Stretch` at all.
  #[inline]
  #[must_use]
  pub const fn next(&self) -> Option<&PageToken> {
    self.next.as_ref()
  }

  /// Both halves, nothing cloned — what an emitted face takes to build its own answer.
  #[inline]
  #[must_use]
  pub fn into_components(self) -> (Vec<T>, Option<PageToken>) {
    (self.rows, self.next)
  }
}

/// One snapshot as the store holds it: the rows, the field that minted them, and when.
struct Kept {
  /// The rows, type-erased — see [`SnapshotKeeper`]'s note on why one store serves every road.
  ///
  /// `Send` and NOT `Send + Sync`, which is the narrowest honest bound and measured rather than
  /// copied: `Mutex<T>` is `Sync` whenever `T` is `Send`, so the keeper is a shareable citizen
  /// without ever asking a household's ROOT KEY to be `Sync` — a demand no other seat on the search
  /// road makes of it.
  rows: Box<dyn Any + Send>,
  /// The field that minted this snapshot.
  road: &'static str,
  /// When it was minted — the TTL's clock.
  born: Instant,
  /// The recency key it currently sits at in the LRU index.
  touched: u64,
}

/// The store itself, behind the keeper's lock.
struct Store {
  kept: HashMap<u64, Kept>,
  /// Recency, least-recent first — the LRU order, kept as an index so eviction is a first-entry
  /// read rather than a scan of the whole store.
  recency: BTreeMap<u64, u64>,
  /// The next recency key, and separately the next snapshot serial.
  clock: u64,
  serial: u64,
}

/// A BOUNDED IN-MEMORY STORE of fused rankings, keyed by opaque page tokens and installed once by
/// a deployment.
///
/// # ONE KEEPER PER SCHEMA, and the type erasure is what makes that legal
///
/// Every other citizen in this family — `SqlDoor<Db>`, `FoldDoor<E, T>`, `TowerDoor<T>` — is keyed
/// by a type parameter, because the parameter IS the routing and a resolver must reach its own
/// instance. This one is not, and the reason is the opposite of theirs: there is nothing to route.
/// A snapshot's rows are one recipe's own, but which recipe is answered by the PAGE TOKEN rather
/// than by the lookup, so a per-recipe keeper would give a deployment one install line per recipe
/// and several stores to size separately, all bounding one process's memory. So the rows are held
/// as [`Any`] and a deployment writes `.data(SnapshotKeeper::new())` once.
///
/// The erasure is not a hole. A page token names the field it was minted at, so a downcast that
/// could fail is refused BEFORE it is attempted, by name, as
/// [`PageTokenRefusal::Crossed`] — and a mismatch that somehow reached the downcast is refused the
/// same way rather than unwrapped.
///
/// # It is CLONE and shared, and the lock is never held across an await
///
/// Cheap to clone, like every door: the store is behind one [`Arc`]. What is behind the lock is a
/// hash map and a `BTreeMap`, and every operation on it is a handful of moves with no I/O, no
/// allocation of anybody else's making, and no `.await` anywhere — so the guard is taken and
/// dropped inside one synchronous call and a resolver's future stays `Send` without holding
/// anything.
///
/// # The knobs, and how each one sits against the three-tier law
///
/// | knob | class | tier 1 | tier 2 | tier 3 |
/// |---|---|---|---|---|
/// | capacity | protective | [`DEFAULT_SNAPSHOT_CAPACITY`] | [`with_capacity`](Self::with_capacity) | **none, and honestly** |
/// | TTL | protective | [`DEFAULT_SNAPSHOT_TTL`] | [`with_ttl`](Self::with_ttl) | **none, and honestly** |
/// | depth | protective | [`DEFAULT_SNAPSHOT_DEPTH`] | [`with_depth`](Self::with_depth) | the request's own `depth`, min-tighten |
///
/// The first two have no tier three because they are not asked at a QUESTION's grain. Capacity and
/// TTL are properties of one shared store: every client's snapshots sit in it, so a number one
/// request named would be a number it named for its neighbours. The protective law's min-tighten
/// form does not rescue them either — tightening a shared store means evicting other clients'
/// answers sooner, which is a wire parameter whose only effect is on somebody else. Depth is the
/// one of the three that IS one question's own — *how deep an answer do I want kept* — so it
/// composes with the request's `depth` exactly as every other wall in this pipeline does.
pub struct SnapshotKeeper {
  identity: KeeperId,
  store: Arc<Mutex<Store>>,
  capacity: NonZeroUsize,
  ttl: Duration,
  depth: NonZeroUsize,
}

impl SnapshotKeeper {
  /// A keeper at the three shipped constants, with a fresh identity.
  #[must_use]
  pub fn new() -> Self {
    Self {
      identity: KeeperId::fresh(),
      store: Arc::new(Mutex::new(Store {
        kept: HashMap::new(),
        recency: BTreeMap::new(),
        clock: 0,
        serial: 0,
      })),
      capacity: DEFAULT_SNAPSHOT_CAPACITY,
      ttl: DEFAULT_SNAPSHOT_TTL,
      depth: DEFAULT_SNAPSHOT_DEPTH,
    }
  }

  /// TIER TWO for the capacity: how many snapshots this deployment holds at once.
  #[must_use]
  pub const fn with_capacity(mut self, capacity: NonZeroUsize) -> Self {
    self.capacity = capacity;
    self
  }

  /// TIER TWO for the TTL: how long this deployment's snapshots outlive the ask that made them.
  #[must_use]
  pub const fn with_ttl(mut self, ttl: Duration) -> Self {
    self.ttl = ttl;
    self
  }

  /// TIER TWO for the depth: how deep this deployment's rankings are kept.
  #[must_use]
  pub const fn with_depth(mut self, depth: NonZeroUsize) -> Self {
    self.depth = depth;
    self
  }

  /// How many snapshots this keeper holds at once.
  #[inline]
  #[must_use]
  pub const fn capacity(&self) -> NonZeroUsize {
    self.capacity
  }

  /// How long a snapshot outlives the ask that made it.
  #[inline]
  #[must_use]
  pub const fn ttl(&self) -> Duration {
    self.ttl
  }

  /// THE CEILING ON ONE SNAPSHOT'S LENGTH — what a road caps its capture at.
  ///
  /// The road reads this and hands it to [`route_depth`](super::route_depth) as the declared
  /// ceiling, so a request asking for less gets less and a request asking for more gets this.
  #[inline]
  #[must_use]
  pub const fn depth(&self) -> NonZeroUsize {
    self.depth
  }

  /// How many snapshots are held right now — live ones only; expired rows are swept first.
  ///
  /// Written for a deployment that wants to watch its own store, and for the tests that pin the
  /// eviction laws.
  #[must_use]
  pub fn held(&self) -> usize {
    let mut store = self.locked();
    self.sweep(&mut store);
    store.kept.len()
  }

  /// KEEP a fused ranking, and answer the page token that claims its first stretch.
  ///
  /// `road` is the field that computed the rows — carried so a page token handed back to a
  /// different field is refused by name instead of downcast into somebody else's answer.
  ///
  /// The rows are taken as they stand. CAPPING IS THE CALLER'S, not this method's, and the split is
  /// deliberate: the depth ceiling composes with the request's own `depth` through the pipeline's
  /// one wall function, which lives where the request is read. A keeper that truncated here would
  /// be a second place the same number is enforced, and the two could come to disagree.
  pub fn keep<T>(&self, road: &'static str, rows: Vec<T>) -> PageToken
  where
    T: Send + 'static,
  {
    let mut store = self.locked();
    self.sweep(&mut store);
    // ROOM FIRST, and the loser is the least recently READ rather than the oldest: a client still
    // walking its answer is the last one whose answer should be taken away.
    while store.kept.len() >= self.capacity.get() {
      let Some((&touched, &oldest)) = store.recency.iter().next() else {
        break;
      };
      store.recency.remove(&touched);
      store.kept.remove(&oldest);
    }
    let snapshot = store.serial;
    store.serial = store.serial.wrapping_add(1);
    let touched = store.clock;
    store.clock = store.clock.wrapping_add(1);
    store.recency.insert(touched, snapshot);
    store.kept.insert(
      snapshot,
      Kept {
        rows: Box::new(rows),
        road,
        born: Instant::now(),
        touched,
      },
    );
    PageToken::new(self.identity, snapshot, 0)
  }

  /// READ the stretch a page token claims — `want` rows of it, and the claim on what follows.
  ///
  /// This is the ONE road to a stretch: the field that just kept a snapshot reads its first stretch
  /// through the same call a client's second page token arrives at, so page one and page nine are
  /// the same arithmetic and there is no first-page path to get separately wrong.
  ///
  /// # Refusals, in the order they are reached
  ///
  /// [`Foreign`](PageTokenRefusal::Foreign) before anything is looked up — a page token from
  /// another store names a serial that means nothing here, and looking it up first would let
  /// another keeper's page token collide with one of ours. Then
  /// [`Unknown`](PageTokenRefusal::Unknown), [`Expired`](PageTokenRefusal::Expired) and
  /// [`Crossed`](PageTokenRefusal::Crossed). A page token whose offset is past the end of its
  /// snapshot is NOT a refusal: it is an empty stretch with no next, which is what *you have read
  /// all of it* means.
  pub fn read<T>(
    &self,
    page_token: &PageToken,
    road: &str,
    want: NonZeroUsize,
  ) -> Result<Stretch<T>, PageTokenRefusal>
  where
    T: Clone + Send + 'static,
  {
    if page_token.keeper != self.identity {
      return Err(PageTokenRefusal::Foreign);
    }
    let mut store = self.locked();
    // THE PAGE TOKEN'S OWN SNAPSHOT IS RESOLVED BEFORE THE SWEEP, and the order IS the refusal: an
    // aged snapshot swept first would come back as [`PageTokenRefusal::Unknown`], which says *the
    // store gave your answer up* where the true sentence is *the clock took it*. Both roads end in
    // *ask again*, so the distinction buys the client nothing — and it buys whoever is reading the
    // logs the difference between a TTL to lengthen and a capacity to raise.
    let answer = self.cut(&mut store, page_token, road, want);
    self.sweep(&mut store);
    answer
  }

  /// [`read`](Self::read)'s middle: everything that happens with the page token's own snapshot in
  /// hand.
  ///
  /// Split out so the sweep can run after it on every road — including the refusing ones — with one
  /// call rather than one per arm.
  fn cut<T>(
    &self,
    store: &mut Store,
    page_token: &PageToken,
    road: &str,
    want: NonZeroUsize,
  ) -> Result<Stretch<T>, PageTokenRefusal>
  where
    T: Clone + Send + 'static,
  {
    let Some(kept) = store.kept.get(&page_token.snapshot) else {
      return Err(PageTokenRefusal::Unknown);
    };
    if kept.born.elapsed() > self.ttl {
      let touched = kept.touched;
      store.kept.remove(&page_token.snapshot);
      store.recency.remove(&touched);
      return Err(PageTokenRefusal::Expired);
    }
    let crossed = || PageTokenRefusal::Crossed {
      minted_at: kept.road,
      asked_at: road.to_owned(),
    };
    if kept.road != road {
      return Err(crossed());
    }
    // UNREACHABLE THROUGH THE ROAD WORD, and refused rather than unwrapped anyway: one field keeps
    // one row type, so a road that matched has already settled the type. What this arm covers is a
    // caller that reached past the road word, and the honest answer for it is the same sentence —
    // this page token does not name your answer.
    let rows = kept.rows.downcast_ref::<Vec<T>>().ok_or_else(crossed)?;
    let from = usize::try_from(page_token.from)
      .unwrap_or(usize::MAX)
      .min(rows.len());
    let to = from.saturating_add(want.get()).min(rows.len());
    let stretch = rows[from..to].to_vec();
    let next = (to < rows.len()).then(|| {
      PageToken::new(
        self.identity,
        page_token.snapshot,
        u64::try_from(to).unwrap_or(u64::MAX),
      )
    });

    // THE READ IS WHAT REFRESHES RECENCY, which is the L of LRU: a snapshot nobody has come back
    // to is the one the store can afford to lose.
    let touched = store.clock;
    store.clock = store.clock.wrapping_add(1);
    if let Some(kept) = store.kept.get_mut(&page_token.snapshot) {
      let stale = core::mem::replace(&mut kept.touched, touched);
      store.recency.remove(&stale);
      store.recency.insert(touched, page_token.snapshot);
    }

    Ok(Stretch {
      rows: stretch,
      next,
    })
  }

  /// Drop every snapshot the TTL has taken, whether or not the store is under pressure.
  ///
  /// Run on every operation rather than on a timer: a keeper owns no task and starts no thread — a
  /// store that nobody is using has nothing to reap, and one that is being used reaps itself on the
  /// way past. That is what makes the TTL a MEMORY BOUND and not only a refusal.
  ///
  /// WHERE in the operation differs, and each position is deliberate: [`keep`](Self::keep) sweeps
  /// BEFORE evicting, so a live snapshot is never given up to make room for one an aged snapshot
  /// was already holding; [`read`](Self::read) sweeps AFTER resolving, so the page token in hand
  /// is answered by the clock rather than by the sweep's own tidying — see its note.
  fn sweep(&self, store: &mut Store) {
    let ttl = self.ttl;
    let dead: Vec<u64> = store
      .kept
      .iter()
      .filter(|(_, kept)| kept.born.elapsed() > ttl)
      .map(|(&snapshot, _)| snapshot)
      .collect();
    for snapshot in dead {
      if let Some(kept) = store.kept.remove(&snapshot) {
        store.recency.remove(&kept.touched);
      }
    }
  }

  /// The store, taken back from a poisoned lock rather than panicked over.
  ///
  /// A keeper holds cached answers and nothing else. A thread that panicked while holding this lock
  /// left a hash map and a `BTreeMap` behind, both of which are whole — every mutation here is a
  /// pair of inserts with nothing between them that can unwind — and the worst a recovered guard
  /// can carry is a snapshot whose recency key is stale, which costs one eviction ordering and
  /// nothing else. Poisoning a whole deployment's paging because one request's thread died is the
  /// larger failure.
  fn locked(&self) -> std::sync::MutexGuard<'_, Store> {
    self
      .store
      .lock()
      .unwrap_or_else(std::sync::PoisonError::into_inner)
  }
}

impl Default for SnapshotKeeper {
  #[inline]
  fn default() -> Self {
    Self::new()
  }
}

/// Written out rather than derived, for the reason every shared citizen in this crate writes its
/// own: the point of cloning a keeper is that the clone reaches the SAME store under the SAME
/// identity, which a derive would also do — and would silently stop doing the day a field is added
/// whose clone is a copy.
impl Clone for SnapshotKeeper {
  fn clone(&self) -> Self {
    Self {
      identity: self.identity,
      store: Arc::clone(&self.store),
      capacity: self.capacity,
      ttl: self.ttl,
      depth: self.depth,
    }
  }
}

/// Written out because the store behind the lock is somebody else's rows and a `Debug` that took
/// the lock to print them would be a deadlock waiting for a re-entrant formatter. What a reader
/// wants here is the SHAPE of the keeper — its three knobs — which needs no lock at all.
impl fmt::Debug for SnapshotKeeper {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    f.debug_struct("SnapshotKeeper")
      .field("capacity", &self.capacity)
      .field("ttl", &self.ttl)
      .field("depth", &self.depth)
      .finish_non_exhaustive()
  }
}

#[cfg(feature = "async-graphql")]
impl SnapshotKeeper {
  /// INSTALL this keeper on a schema being built — the one act a deployment performs for it.
  ///
  /// ```ignore
  /// let schema = SnapshotKeeper::new()
  ///   .with_ttl(Duration::from_secs(60))
  ///   .install(Schema::build(TravelQueries, EmptyMutation, EmptySubscription))
  ///   .finish();
  /// ```
  ///
  /// A named act rather than a bare `.data(keeper)`, for the family's own reason: the KEYING is the
  /// contract. Unlike its siblings the key carries no parameter, so this line is written ONCE for a
  /// whole schema however many recipes it publishes — see the type's note on why the routing lives
  /// in the page token instead.
  #[must_use]
  pub fn install<Q, M, S>(
    self,
    builder: async_graphql::SchemaBuilder<Q, M, S>,
  ) -> async_graphql::SchemaBuilder<Q, M, S>
  where
    Q: async_graphql::ObjectType + 'static,
    M: async_graphql::ObjectType + 'static,
    S: async_graphql::SubscriptionType + 'static,
  {
    builder.data(self)
  }
}

/// THE KEEPER A PAGED FIELD READS, or the line a deployment is missing.
///
/// The twin of [`installed_road`](crate::installed_road), refusing for the same reason it does: a
/// paged field's whole contract is that an answer is being held somewhere, and a framework with
/// nowhere to hold one has no fallback to reach for. Answering an unpaged list instead would be a
/// field that silently stops paging, which is the failure a client cannot see.
#[cfg(feature = "async-graphql")]
pub fn installed_keeper<'ctx>(
  ctx: &'ctx async_graphql::Context<'_>,
  word: &str,
) -> async_graphql::Result<&'ctx SnapshotKeeper> {
  async_graphql::Context::data_opt::<SnapshotKeeper>(ctx).ok_or_else(|| {
    async_graphql::Error::new(format!(
      "`{word}` pages a kept answer and this schema installed no keeper to hold one — the \
       deployment writes `SnapshotKeeper::new().install(builder)` once",
    ))
  })
}

#[cfg(test)]
mod tests;