ingraph/drive/pair.rs
1//! The BY-KEY JOIN: where a keyed group's members wait for each other, and what a complete one
2//! carries with it.
3//!
4//! # Complete or not at all
5//!
6//! A `subscribe(…)` container's keyed group is delivered as ONE input — the emitted `Paired(A, B)`
7//! variant — and it is delivered only when every member has arrived for that key. A message whose
8//! counterparts are not there yet waits HERE; the straights beside it never touch this buffer,
9//! because an independent flow has nothing to wait for.
10//!
11//! # There is no deadline, and that is the ruling rather than an omission
12//!
13//! A half-arrived group waits indefinitely. No timeout, no policy: the member that did arrive is
14//! still in its sender's ack window — its [`Owing`](super::Owing) stays open while a
15//! [`Share`] of it sits here — so the sender's watermark sticks, and the upstream's own lag sweep
16//! re-pulls the flow that stopped. That is the safety net the design names, and a knob here would
17//! be one before there was a case for one. Dropping the buffer is the other end of it: the shares
18//! go, the tokens disconnect, and every sender reads that as held.
19//!
20//! # What the framework holds and what the declaration writes
21//!
22//! The members carry DIFFERENT message types, so the slots a partial group keeps are a struct only
23//! that node's own expansion can spell. This module holds the part that is the same for every
24//! group — the keyed table, the shares that accumulate against a key, and the completion — and
25//! [`Group`] is the seam the spelled part meets it at.
26
27use core::hash::Hash;
28
29use std::collections::HashMap;
30
31use super::{ItemId, message::Share};
32
33/// How a member of a keyed group states the key it JOINS ON.
34///
35/// # Why it is a value and not a trait on the message
36///
37/// The obvious seat is the message type — `impl Joins for Frame` — and it is the wrong one for
38/// [`Sink`](super::Sink)'s reason: two nodes joining the same upstream on different fields would be
39/// two impls for one app-owned type, which is `E0119` and unfixable. A projection INSTALLED at the
40/// wiring has no such question, and it is the shape
41/// [`Attributes`](super::Attributes) already takes for the same kind of read.
42///
43/// One value answers for every member — `impl Joins<Frame>` and `impl Joins<Segment>` on one
44/// projection, with one `Key` — which is what "joined by key" means: the members meet at a type
45/// they all produce.
46pub trait Joins<T> {
47 /// The key the group is joined by.
48 type Key;
49
50 /// The key `message` joins under.
51 fn key(&self, message: &T) -> Self::Key;
52}
53
54/// A keyed group's PARTIAL state: one slot per member, and what a full set becomes.
55///
56/// Written by the node's own expansion, because the slots are one `Option` per member and the
57/// members are different types. The framework only ever asks the one question below.
58///
59/// # `complete` gives the group BACK
60///
61/// `Result<Complete, Self>` rather than `Option<Complete>` on `&mut self`, so that a group which is
62/// not ready cannot be half-emptied by the asking: an implementation that takes a member out and
63/// then finds another missing has already lost the first. Taking the whole value and handing it
64/// back is the shape where that mistake is not expressible.
65pub trait Group: Default {
66 /// The complete group — the payload the emitted `Paired` variant carries.
67 type Complete;
68
69 /// The complete group, or this partial one back unchanged.
70 fn complete(self) -> Result<Self::Complete, Self>;
71}
72
73/// One key's half-arrived group: the members that came, and what they are owed on.
74#[derive(Debug)]
75struct Waiting<G> {
76 slots: G,
77 // One per member MESSAGE and not per member slot: a second message for a slot that is already
78 // filled replaces the value and keeps both shares, so the pair's outcome answers every delivery
79 // that carried the key. See `Pairing::arrive`.
80 shares: Vec<Share<ItemId>>,
81}
82
83impl<G: Default> Default for Waiting<G> {
84 fn default() -> Self {
85 Self {
86 slots: G::default(),
87 shares: Vec::new(),
88 }
89 }
90}
91
92/// The by-key join buffer of ONE keyed group.
93///
94/// One per node, because a container has one group: `key` on a `upstream(…)` entry JOINS the group
95/// rather than opening one, so there is nothing here to tell two of them apart.
96#[derive(Debug)]
97pub struct Pairing<K, G> {
98 waiting: HashMap<K, Waiting<G>>,
99}
100
101impl<K, G> Pairing<K, G> {
102 /// An empty buffer.
103 #[inline]
104 #[must_use]
105 pub fn new() -> Self {
106 Self {
107 waiting: HashMap::new(),
108 }
109 }
110
111 /// How many keys have a group waiting for a member.
112 #[inline]
113 #[must_use]
114 pub fn waiting(&self) -> usize {
115 self.waiting.len()
116 }
117
118 /// Whether nothing is waiting.
119 #[inline]
120 #[must_use]
121 pub fn is_empty(&self) -> bool {
122 self.waiting.is_empty()
123 }
124}
125
126impl<K, G> Pairing<K, G>
127where
128 K: Eq + Hash,
129 G: Group,
130{
131 /// Put a member's message into the group under `key`, and answer the group if that COMPLETED it.
132 ///
133 /// `fill` is the member's own slot — the one line only the node's expansion can write — and
134 /// `share` is what that message's delivery is owed. The answer carries every share the key
135 /// collected, which is what a joined delivery's [`Custody`](super::Custody) is built from.
136 ///
137 /// # A second message for a filled slot REPLACES it, and both shares are kept
138 ///
139 /// Two frames for one key before the segment arrives is not an error and not a queue: keyed
140 /// replace is this layer's law — a re-delivery is harmless because the last state wins — so the
141 /// slot takes the newer value. What must not happen is the older message being forgotten: its
142 /// sender is still waiting, so its share stays, and the pair's outcome answers both deliveries
143 /// alike. Nothing is dropped and nothing is answered for work that did not happen.
144 pub fn arrive(
145 &mut self,
146 key: K,
147 share: Share<ItemId>,
148 fill: impl FnOnce(&mut G),
149 ) -> Option<(G::Complete, Vec<Share<ItemId>>)> {
150 // Taken OUT and put back rather than filled in place: [`Group::complete`] consumes the group,
151 // which is what makes a half-emptied one unspellable, and an entry cannot hand its value over.
152 let mut waiting = self.waiting.remove(&key).unwrap_or_default();
153 fill(&mut waiting.slots);
154 waiting.shares.push(share);
155 let Waiting { slots, shares } = waiting;
156 match slots.complete() {
157 Ok(complete) => Some((complete, shares)),
158 Err(slots) => {
159 self.waiting.insert(key, Waiting { slots, shares });
160 None
161 }
162 }
163 }
164}
165
166impl<K, G> Default for Pairing<K, G> {
167 #[inline]
168 fn default() -> Self {
169 Self::new()
170 }
171}
172
173#[cfg(test)]
174mod tests;