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
//! The ack windows: what a sender still owes itself, and what a consumer still owes its sender.
//!
//! Three pieces, and each answers one question:
//!
//! - [`Outbound`] — a SENDER's per-edge window. Which items are still outstanding, and how far the
//!   contiguous released prefix reaches. That prefix is the watermark, and it is the only position
//!   that is safe to make durable: a gap means an item behind it is not settled, so resuming past
//!   it would skip work.
//! - [`Owed`] — a CONSUMER's obligation for one delivery. Which items it has released so far, and
//!   the [`Custody`] it will say so on exactly once. A delivery the intake JOINED owes several
//!   tokens rather than one, which is the custody's business and not this type's: an obligation
//!   releases keys and settles once either way.
//! - [`Lineage`] — the join [`Chained`](super::AckMode::Chained) is built on. Which input each
//!   output descends from, and how many outputs an input is still waiting on.
//!
//! The lineage lives HERE and never on the wire. The sender already knows which input it was
//! processing when it emitted an output, so attributing the output costs a map entry; putting the
//! parent id in the message would put it in the app's declared struct, which is the envelope this
//! layer's design removed.
//!
//! # The keys are UNIQUE FOREVER, and that is load-bearing
//!
//! Everything here is keyed by a delivery item's id, and an answer for one can arrive LATE — after
//! its delivery was retracted, after the item was re-emitted under a new id. Both maps stay correct
//! through that for one reason: a [`Resident`](super::Resident) and a
//! [`ChangeIntake`](super::ChangeIntake) mint ids from a counter that only ever goes up, so a
//! retracted id belongs to nothing afterwards and the late answer is inert.
//!
//! That is what rules a slot allocator — `slab` and anything else that hands a freed key to the
//! next allocation — out of these two maps. Under reuse the late answer names an id that a
//! DIFFERENT item now holds, and the join releases an input whose output never landed: no panic, no
//! refusal, a silently skipped item. One scenario run under both minters shows the two outcomes —
//! `a_reused_id_settles_the_wrong_input_and_a_monotonic_one_refuses_it`.
//!
//! A generational key (`slotmap`) would survive the reuse, but it does not fit either: the key such
//! a map mints never crosses the wire, so an answer's own id would still have to be translated
//! through a hash map — the one already here, with a slot behind it. The counted comparison is
//! `the_outstanding_set_is_counted_against_a_ring_and_a_slot_map`.

use std::collections::{HashMap, HashSet, VecDeque, hash_map::Entry};

use core::{any::Any, hash::Hash};

use smol_bytes::Utf8Bytes;

use crate::operator::Receipts;

use super::{
  NodeName,
  fate::Fate,
  lifecycle::{Lifecycle, Observation},
  message::{Ack, AckReceiver, Answer, Custody, ReceiptMap, Unreceipted},
};

/// One item as its sender tracks it: the key, and whether the consumer has released it.
#[derive(Debug)]
struct Tracked<K> {
  key: K,
  released: bool,
}

/// One delivery in flight, in send order.
#[derive(Debug)]
struct Flight<K> {
  items: Vec<Tracked<K>>,
  // `None` once the delivery has been answered or hung up. Keeping the slot rather than removing
  // the flight is what preserves ORDER, and order is the whole of the watermark.
  ack: Option<AckReceiver<K>>,
}

/// ONE answer as its sender reads it: who did the work, what they said, and which keys it spoke
/// for.
///
/// The two key lists are different questions and neither answers the other:
///
/// - [`covered`](Self::covered) is every key the answer was ABOUT — the whole delivery. It is what a
///   journal is keyed by, and the reason it exists is [`Failed`](Lifecycle::Failed): a failure
///   releases nothing and is exactly the observation worth writing down, so a pairing built out of
///   released keys alone would lose every row a reader is looking for.
/// - [`released`](Self::released) is the subset that CROSSED from held to released in this harvest,
///   each exactly once ever. It is what retires a [`Lineage`].
#[derive(Debug)]
pub struct Answered<K> {
  worker: Utf8Bytes,
  observation: Observation,
  message: Option<Box<dyn Any + Send + Sync>>,
  receipts: ReceiptMap<K>,
  covered: Vec<K>,
  released: Vec<K>,
}

impl<K> Answered<K> {
  /// The node whose work this describes — the consumer that answered, never the sender harvesting
  /// it.
  #[inline]
  #[must_use]
  pub fn worker(&self) -> &NodeName {
    NodeName::new(&self.worker)
  }

  /// What the answer said.
  #[inline]
  #[must_use]
  pub const fn observation(&self) -> &Observation {
    &self.observation
  }

  /// The [`Fate`]'s extra message, as `M` — `None` on an ordinary arrival, and `None` where `M` is
  /// not the type the answering party sent.
  ///
  /// It is the SENDER's half of the generic ending: the terminal itself reaches every tap in the
  /// arrangement, and whatever the ending carried beyond the terminal reaches the one party the
  /// oneshot belonged to.
  #[inline]
  #[must_use]
  pub fn message<M: Any>(&self) -> Option<&M> {
    self
      .message
      .as_ref()
      .and_then(|message| message.downcast_ref())
  }

  /// The consumer's RECEIPT for the item keyed `key`, as `R` — the WINDOW's half of the acked give.
  ///
  /// The same read [`Settled::receipt`](super::Settled::receipt) is, one layer up: a sender that
  /// harvests its window rather than waiting on one token still gets its consumers' answers, and
  /// this is where it reads them.
  ///
  /// # Errors
  ///
  /// [`Unreceipted::Silent`] where the consumer stated nothing for this item, and
  /// [`Unreceipted::Mismatched`] where it stated a receipt of another type. The two waiting arms cannot
  /// arise here — a harvested answer is an answer that ARRIVED.
  #[inline]
  pub fn receipt<R: Any>(&self, key: &K) -> Result<&R, Unreceipted>
  where
    K: Eq + Hash,
  {
    let receipt = self
      .receipts
      .as_ref()
      .and_then(|receipts| receipts.get(key))
      .ok_or(Unreceipted::Silent)?;
    receipt.downcast_ref().ok_or(Unreceipted::Mismatched)
  }

  /// [`receipt`](Self::receipt) AT THE TYPE THE MESSAGE DECLARED — the window's door with teeth.
  ///
  /// [`Settled::receipt_of`](super::Settled::receipt_of)'s read one layer up, for the sender that
  /// harvests its window rather than waiting on one token — and keyed by `K` for the same reason, so
  /// the message is named here rather than inferred.
  ///
  /// # Errors
  ///
  /// [`receipt`](Self::receipt)'s, unchanged.
  #[inline]
  pub fn receipt_of<M>(&self, key: &K) -> Result<&M::Receipt, Unreceipted>
  where
    K: Eq + Hash,
    M: Receipts,
    M::Receipt: Any,
  {
    self.receipt::<M::Receipt>(key)
  }

  /// Every key this answer spoke for, released or held.
  #[inline]
  #[must_use]
  pub fn covered(&self) -> &[K] {
    &self.covered
  }

  /// The keys this answer crossed from held to released.
  #[inline]
  #[must_use]
  pub fn released(&self) -> &[K] {
    &self.released
  }
}

/// What one [`Outbound::harvest`] found: the answers that arrived, each still holding the keys it
/// spoke for.
///
/// One list and not two, which is the pairing this type exists for. Two flat lists — the
/// observations on one side, the released keys on the other — cannot say WHICH answer released
/// which key, and a row per `(root, node)` needs exactly that: the root comes off the key and the
/// node and the station come off the answer.
#[derive(Debug)]
pub struct Harvest<K> {
  answers: Vec<Answered<K>>,
}

impl<K> Harvest<K> {
  /// The answers, in the order they were collected.
  #[inline]
  #[must_use]
  pub fn answers(&self) -> &[Answered<K>] {
    &self.answers
  }

  /// Every `(key, answer)` PAIR this harvest found — every key each answer spoke for, beside the
  /// answer that spoke for it.
  #[inline]
  pub fn pairs(&self) -> impl Iterator<Item = (&K, &Answered<K>)> {
    self
      .answers
      .iter()
      .flat_map(|answer| answer.covered.iter().map(move |key| (key, answer)))
  }

  /// The keys that crossed from held to released in THIS harvest — each exactly once, ever.
  #[inline]
  pub fn released(&self) -> impl Iterator<Item = &K> {
    self
      .answers
      .iter()
      .flat_map(|answer| answer.released.iter())
  }

  /// Whether no answer arrived at all.
  #[inline]
  #[must_use]
  pub fn is_empty(&self) -> bool {
    self.answers.is_empty()
  }

  /// The answers, owned.
  #[inline]
  #[must_use]
  pub fn into_answers(self) -> Vec<Answered<K>> {
    self.answers
  }
}

/// A sender's window over ONE edge.
///
/// The window holds keys and flags, never payloads: what was sent has already moved on, and what is
/// owed back is bookkeeping. That is what makes [`Chained`](super::AckMode::Chained) affordable —
/// withholding an ack costs a few words per item and never a copy of the item.
#[derive(Debug)]
pub struct Outbound<K> {
  flights: VecDeque<Flight<K>>,
  position: Option<K>,
  lost: usize,
}

impl<K> Outbound<K> {
  /// An empty window at no position.
  #[inline]
  #[must_use]
  pub const fn new() -> Self {
    Self {
      flights: VecDeque::new(),
      position: None,
      lost: 0,
    }
  }

  /// [`new`](Self::new), with room for `deliveries` in flight before the window grows.
  ///
  /// The unit is DELIVERIES and not items, because that is what the window is a queue of: a page of
  /// 256 answered as one batch is one entry here, and a sender that keeps `n` pages outstanding
  /// before it waits for an answer is the one who knows `n`.
  ///
  /// It delegates rather than repeating the empty value: [`new`](Self::new) is where a field's
  /// default is written down, and a second spelling of it is a second place to be wrong.
  #[inline]
  #[must_use]
  pub fn with_capacity(deliveries: usize) -> Self {
    Self {
      flights: VecDeque::with_capacity(deliveries),
      ..Self::new()
    }
  }

  /// Record that `keys` went out as one delivery, answered on `ack`.
  ///
  /// The keys are appended in the order given, and that order IS the window's order — the watermark
  /// walks it, so a sender that emits out of order gets a watermark that advances no further than
  /// its own earliest gap.
  pub fn record(&mut self, keys: impl IntoIterator<Item = K>, ack: AckReceiver<K>) {
    self.flights.push_back(Flight {
      items: keys
        .into_iter()
        .map(|key| Tracked {
          key,
          released: false,
        })
        .collect(),
      ack: Some(ack),
    });
  }

  /// The watermark: the last key of the contiguous released prefix, or `None` while the first item
  /// is still outstanding.
  #[inline]
  #[must_use]
  pub const fn position(&self) -> Option<&K> {
    self.position.as_ref()
  }

  /// How many deliveries hung up without answering since the last [`rewind`](Self::rewind).
  ///
  /// Non-zero is the signal a re-readable source acts on: the items those deliveries carried will
  /// never be released, so the window has to be rewound and the page re-pulled.
  #[inline]
  #[must_use]
  pub const fn lost(&self) -> usize {
    self.lost
  }

  /// How many items are sent and not yet released.
  #[must_use]
  pub fn outstanding(&self) -> usize {
    self
      .flights
      .iter()
      .map(|flight| flight.items.iter().filter(|item| !item.released).count())
      .sum()
  }

  /// Whether everything sent has been released.
  #[inline]
  #[must_use]
  pub fn is_drained(&self) -> bool {
    self.flights.is_empty()
  }

  /// Collect every answer that has arrived, apply it, and advance the watermark.
  ///
  /// Applying is deliberately ONE pass over the window after every answer has been merged, rather
  /// than a scan per answer: a batch of 256 answered by four consumers is four merges and one walk.
  pub fn harvest(&mut self) -> Harvest<K>
  where
    K: Clone + Eq + Hash,
  {
    // Which ANSWER named each key, and not merely that some answer did. The attribution is what
    // turns a harvest into `(key, answer)` pairs, and it costs one map entry per released key on a
    // pass that was already walking them.
    //
    // These two are EMPTY and not reserved, and that is the measured choice rather than an omission:
    // a harvest runs on every pass and most passes find nothing, so the idle cost of the pass is
    // whatever these two constructors do. `new` allocates nothing at all; a `with_capacity` sized
    // from the flight count would allocate on every idle look for answers that did not arrive.
    // `answer_capacity_is_taken_where_the_size_is_known_and_not_where_it_is_guessed` pins both
    // halves of that.
    let mut answered: HashMap<K, usize> = HashMap::new();
    let mut answers: Vec<Answered<K>> = Vec::new();
    for flight in &mut self.flights {
      let Some(ack) = flight.ack.as_ref() else {
        continue;
      };
      match ack.take() {
        Answer::Settled(settled) => {
          let (keys, worker, observation, message, receipts) = settled.into_parts();
          let at = answers.len();
          // The answer's own key count, taken before the set is consumed. It is the exact ceiling on
          // what this answer can cross — a key crosses at most once, and only a key the answer named
          // crosses at all — so the list below is sized once here instead of doubling its way to a
          // page. Unlike the two above, this vector is built only where an answer actually arrived,
          // which is why the size is known rather than guessed.
          let named = keys.len();
          for key in keys {
            answered.insert(key, at);
          }
          answers.push(Answered {
            worker,
            observation,
            message,
            receipts,
            // Everything this delivery carried. A flight is answered exactly once — the oneshot
            // makes sure of it — so nothing here has been released by an earlier answer, and the
            // list is the whole delivery whatever the answer released.
            covered: flight.items.iter().map(|item| item.key.clone()).collect(),
            released: Vec::with_capacity(named),
          });
          flight.ack = None;
        }
        Answer::Waiting => {}
        Answer::HungUp => {
          // The consumer dropped the oneshot. Every item this delivery carried stays held, which is
          // the safe answer and also a stuck watermark — so the count is published for a source to
          // act on rather than swallowed here.
          flight.ack = None;
          self.lost += 1;
        }
      }
    }

    // Only the items that CROSSED — a key answered twice, or answered by a consumer of a different
    // edge, transitions nothing and is reported nowhere. That is what makes the released list safe
    // to retire a lineage with: each output is retired exactly once.
    if !answered.is_empty() {
      for flight in &mut self.flights {
        for item in &mut flight.items {
          if item.released {
            continue;
          }
          if let Some(&at) = answered.get(&item.key) {
            item.released = true;
            answers[at].released.push(item.key.clone());
          }
        }
      }
    }

    self.advance();
    Harvest { answers }
  }

  /// Walk the contiguous released prefix off the front, remembering the last key crossed.
  ///
  /// ITEM by item and not delivery by delivery. A batch is answered per item — 250 of 256 released
  /// and 6 held is the ordinary case — so a watermark that could only cross whole deliveries would
  /// stall a 256-item page on one held row, and the position it reported would be the one before the
  /// page rather than the one before the gap.
  fn advance(&mut self) {
    while let Some(flight) = self.flights.front_mut() {
      let crossed = flight
        .items
        .iter()
        .position(|item| !item.released)
        .unwrap_or(flight.items.len());
      if let Some(last) = flight.items.drain(..crossed).next_back() {
        self.position = Some(last.key);
      }
      if !flight.items.is_empty() {
        // A gap inside this delivery. Everything behind it stays where it is, whatever its own
        // answer said: resuming past a held item would skip it.
        return;
      }
      self.flights.pop_front();
    }
  }

  /// Retract everything sent past the watermark, and report the keys retracted in send order.
  ///
  /// What it is FOR: a delivery that hung up will never be released, so the window would sit at a
  /// stuck watermark forever. A re-readable source rewinds and re-pulls from
  /// [`position`](Self::position); the retracted items come back under fresh keys, and keyed replace
  /// is what makes the second write of the same content harmless.
  ///
  /// It retracts the WHOLE tail rather than only the lost delivery, because the tail was produced
  /// from positions past the lost one and the re-pull will produce it again. Answers still in flight
  /// for the retracted deliveries are discarded; that costs a duplicate delivery and never a loss.
  pub fn rewind(&mut self) -> Vec<K> {
    // The front of the deque is settled-and-popped by `advance`, so everything still here is at or
    // past the watermark and every one of it is retracted.
    let retracted = core::mem::take(&mut self.flights)
      .into_iter()
      .flat_map(|flight| flight.items.into_iter().map(|item| item.key))
      .collect();
    self.lost = 0;
    retracted
  }
}

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

/// What a consumer owes for ONE delivery.
///
/// The obligation is settled exactly once, because the oneshot is. A consumer that releases some of
/// a batch and holds the rest settles once with the partial set — 250 of 256 released and 6 held is
/// an ordinary answer — and the six come back on the sender's next pass.
#[derive(Debug)]
pub struct Owed<K> {
  ack: Option<Custody<K>>,
  pending: HashSet<K>,
  released: HashSet<K>,
  receipts: ReceiptMap<K>,
}

impl<K> Owed<K> {
  /// Open an obligation for `keys`, answerable on the custody `ack` carried.
  ///
  /// `None` is a delivery that arrived with no token — legal, and it makes this obligation a
  /// bookkeeping one: it tracks what was released and [`settle`](Self::settle) answers nobody. See
  /// [`Delivery`](super::Delivery)'s own note for who holds the token when.
  pub fn open(keys: impl IntoIterator<Item = K>, ack: Option<Custody<K>>) -> Self
  where
    K: Eq + Hash,
  {
    Self {
      ack,
      pending: keys.into_iter().collect(),
      released: HashSet::new(),
      receipts: None,
    }
  }

  /// Release `key`. Unknown keys are ignored — an obligation only ever speaks for what it was
  /// opened with.
  pub fn release(&mut self, key: K)
  where
    K: Eq + Hash,
  {
    if self.pending.remove(&key) {
      self.released.insert(key);
    }
  }

  /// Answer the item keyed `key` with `receipt` — the VALUE its producer is waiting for.
  ///
  /// Held here rather than passed to [`settle`](Self::settle) because the two are stated at
  /// different moments and by different code: a receipt is produced while the item is being processed,
  /// and the settle happens once, afterwards, for the whole delivery — and under
  /// [`Chained`](super::AckMode::Chained) a whole pass later, after the outputs the item produced
  /// have themselves been released. An obligation that carries the receipt survives that wait without
  /// anything else having to.
  ///
  /// Unknown keys are kept rather than ignored, which is the OPPOSITE of
  /// [`release`](Self::release)'s posture and deliberate: a release for a key this obligation never
  /// held would settle somebody else's item, while a receipt is inert until a caller asks for that key
  /// — so refusing it here would cost the one case where a consumer states an answer for an item its
  /// own driver has already decided.
  pub fn receipt<R>(&mut self, key: K, receipt: R)
  where
    K: Eq + Hash,
    R: Any + Send + Sync,
  {
    self
      .receipts
      .get_or_insert_with(Box::default)
      .insert(key, Box::new(receipt));
  }

  /// [`receipt`](Self::receipt) AT THE TYPE THE MESSAGE DECLARED — the obligation's door with teeth.
  ///
  /// [`Ack::receipting_of`](super::Ack::receipting_of)'s twin on the road that holds the answer
  /// across a pass: a consumer under [`Chained`](super::AckMode::Chained) states its receipt while
  /// the item is being processed and settles a whole pass later, and the obligation is what carries
  /// it in between. The check belongs where the value is STATED, which is here — and the message is
  /// named rather than inferred for its sibling's reason: an obligation is keyed by `K` and speaks
  /// for a whole delivery.
  pub fn receipt_of<M>(&mut self, key: K, receipt: M::Receipt)
  where
    K: Eq + Hash,
    M: Receipts,
    M::Receipt: Any + Send + Sync,
  {
    self.receipt(key, receipt);
  }

  /// The same, for a receipt that is ALREADY BOXED — what a driver carrying one across its own pass
  /// hands over without boxing it twice.
  pub(crate) fn receipting(&mut self, key: K, receipt: Box<dyn Any + Send + Sync>)
  where
    K: Eq + Hash,
  {
    self
      .receipts
      .get_or_insert_with(Box::default)
      .insert(key, receipt);
  }

  /// Decide `key` WITHOUT releasing it — the answer a shared obligation needs to be able to give.
  ///
  /// A withheld key is named in no released set, so its sender holds it and re-delivers, exactly as
  /// a failed one is held. The difference from leaving it pending is that the obligation can now
  /// COMPLETE: a member delivery whose three items joined three groups cannot answer at all until
  /// every one of them has been decided, and two of those groups failing must not keep the third's
  /// release from ever being spoken.
  pub fn withhold(&mut self, key: &K)
  where
    K: Eq + Hash,
  {
    self.pending.remove(key);
  }

  /// Whether every item this delivery carried has been DECIDED — released, or
  /// [`withheld`](Self::withhold).
  ///
  /// For an ordinary delivery the two readings are the same, because nothing withholds: the driver
  /// releases what its operator finished and leaves the rest pending. A SHARED obligation is where
  /// they part — see [`withhold`](Self::withhold).
  #[inline]
  #[must_use]
  pub fn is_complete(&self) -> bool {
    self.pending.is_empty()
  }

  /// Whether the answer has already been sent.
  #[inline]
  #[must_use]
  pub const fn is_settled(&self) -> bool {
    self.ack.is_none()
  }

  /// How many items are still held.
  #[inline]
  #[must_use]
  pub fn held(&self) -> usize {
    self.pending.len()
  }

  /// Answer as `worker`, releasing whatever has been released so far and stating `lifecycle`.
  ///
  /// The name is passed HERE rather than held on the obligation, because an obligation is opened by
  /// the transport and answered by the node: the party that knows whose work it was is the one
  /// making this call.
  ///
  /// `false` when there was nothing left to answer with — either it was already settled, or the
  /// sender had stopped waiting. Neither is an error: a sender that hung up has already treated the
  /// delivery as held.
  ///
  /// `I: Clone` is [`Custody`]'s: a JOINED delivery states one outcome to every member's token, and
  /// a one-token delivery clones nothing.
  pub fn settle<I>(&mut self, worker: impl Into<Utf8Bytes>, lifecycle: Lifecycle<I>) -> bool
  where
    K: Eq + Hash,
    I: core::any::Any + Clone + Send + Sync,
  {
    let Some(ack) = self.ack.take() else {
      return false;
    };
    ack.send(
      Ack::new(core::mem::take(&mut self.released), worker, lifecycle)
        .carrying(self.receipts.take()),
    )
  }

  /// Answer as `worker` with a TERMINAL FATE, CREDITING every item this delivery carried.
  ///
  /// The difference from [`settle`](Self::settle) is the released set, and it is the fate's whole
  /// consequence: an ordinary answer releases what the consumer finished and leaves the rest to come
  /// back, while an ending means nothing is coming back — so a key left outstanding here would stall
  /// the sender's watermark forever on an item that no longer exists. Pending and released are
  /// therefore credited together.
  ///
  /// `false` when there was nothing left to answer with, exactly as [`settle`](Self::settle)'s is.
  ///
  /// `M: Clone` is [`Custody`]'s, for the reason its own [`fate`](Custody::fate) states.
  pub fn settle_fate<M>(&mut self, worker: impl Into<Utf8Bytes>, fate: Fate<M>) -> bool
  where
    K: Eq + Hash,
    M: Any + Clone + Send + Sync,
  {
    let Some(ack) = self.ack.take() else {
      return false;
    };
    let credited: HashSet<K> = self.released.drain().chain(self.pending.drain()).collect();
    ack.fate(credited, worker, fate)
  }
}

/// The per-input refcount [`Chained`](super::AckMode::Chained) joins on.
///
/// One input becomes zero, one or many outputs, and a chained node may not release the input until
/// every one of them has been released downstream — an AND-join across the fan-out, not a first-one
/// wins. An input that produced NOTHING is complete at once, which is the case a refcount handles
/// silently and a "wait for a child" rule would deadlock on.
#[derive(Debug)]
pub struct Lineage<In, Out> {
  parent: HashMap<Out, In>,
  outstanding: HashMap<In, usize>,
}

impl<In, Out> Lineage<In, Out> {
  /// An empty lineage.
  #[inline]
  #[must_use]
  pub fn new() -> Self {
    Self {
      parent: HashMap::new(),
      outstanding: HashMap::new(),
    }
  }

  /// Record that `input` produced `outputs`.
  ///
  /// `true` when the input is ALREADY complete — it produced nothing, so there is nothing to wait
  /// for and the caller releases it now.
  pub fn expect(&mut self, input: In, outputs: impl IntoIterator<Item = Out>) -> bool
  where
    In: Eq + Hash + Clone,
    Out: Eq + Hash,
  {
    let mut count = 0usize;
    for output in outputs {
      self.parent.insert(output, input.clone());
      count += 1;
    }
    if count == 0 {
      return true;
    }
    *self.outstanding.entry(input).or_insert(0) += count;
    false
  }

  /// Retire `output`, released downstream.
  ///
  /// The input is returned when this was its LAST outstanding output — that is the moment a chained
  /// node releases its input. An output this lineage never saw returns `None`, which is what a
  /// duplicate answer or an answer for another edge's key looks like.
  pub fn retire(&mut self, output: &Out) -> Option<In>
  where
    In: Eq + Hash,
    Out: Eq + Hash,
  {
    let input = self.parent.remove(output)?;
    let Entry::Occupied(mut entry) = self.outstanding.entry(input) else {
      // Unreachable while `expect` is the only writer: a parent link exists only alongside its
      // count. Reported as `None` rather than asserted, because the consequence of being wrong is a
      // held item and a re-delivery, not a wrong release.
      return None;
    };
    *entry.get_mut() -= 1;
    if *entry.get() == 0 {
      return Some(entry.remove_entry().0);
    }
    None
  }

  /// Forget `output` without retiring it — what a [`rewind`](Outbound::rewind) does to the outputs
  /// it retracted.
  ///
  /// The input's count drops with it, and the caller re-[`expect`](Self::expect)s the same input
  /// when it re-sends. It NEVER reports completion, because a retracted output was not released;
  /// treating it as one would release an input whose effect never landed.
  pub fn retract(&mut self, output: &Out) -> Option<In>
  where
    In: Eq + Hash + Clone,
    Out: Eq + Hash,
  {
    let input = self.parent.remove(output)?;
    if let Entry::Occupied(mut entry) = self.outstanding.entry(input.clone()) {
      *entry.get_mut() -= 1;
      if *entry.get() == 0 {
        entry.remove_entry();
      }
    }
    Some(input)
  }

  /// How many inputs are still waiting on an output.
  #[inline]
  #[must_use]
  pub fn waiting(&self) -> usize {
    self.outstanding.len()
  }

  /// Whether nothing is.
  #[inline]
  #[must_use]
  pub fn is_empty(&self) -> bool {
    self.outstanding.is_empty() && self.parent.is_empty()
  }
}

impl<In, Out> Default for Lineage<In, Out> {
  #[inline]
  fn default() -> Self {
    Self::new()
  }
}

#[cfg(test)]
mod tests;