Skip to main content

zero_client/ivm/
join_utils.rs

1//! Helpers shared by `Join` and `FlippedJoin` (`join-utils.ts`), and the
2//! join index (`join-index.ts`).
3
4use super::*;
5use crate::json::{self, Value};
6use std::cell::RefCell;
7use std::cmp::Ordering;
8use std::collections::{HashMap, HashSet, VecDeque};
9use std::rc::Rc;
10
11/// `generateWithOverlay`: applies the in-flight child change `overlay` to a
12/// sorted child stream, so a parent that has yet to receive the change sees
13/// the children as they were.
14pub fn generate_with_overlay(
15    stream: NodeStream,
16    overlay: Change,
17    schema: Rc<SourceSchema>,
18) -> NodeStream {
19    Box::new(OrderedOverlay {
20        stream,
21        overlay,
22        schema,
23        applied: false,
24        edit_old_applied: false,
25        edit_new_applied: false,
26        queue: VecDeque::new(),
27        finished: false,
28    })
29}
30
31struct OrderedOverlay {
32    stream: NodeStream,
33    overlay: Change,
34    schema: Rc<SourceSchema>,
35    applied: bool,
36    edit_old_applied: bool,
37    edit_new_applied: bool,
38    queue: VecDeque<Node>,
39    finished: bool,
40}
41
42impl Iterator for OrderedOverlay {
43    type Item = Node;
44
45    fn next(&mut self) -> Option<Node> {
46        let compare = self.schema.compare_rows.clone();
47        loop {
48            if let Some(n) = self.queue.pop_front() {
49                return Some(n);
50            }
51            if self.finished {
52                return None;
53            }
54            let Some(node) = self.stream.next() else {
55                self.finished = true;
56                if !self.applied {
57                    match &self.overlay {
58                        Change::Remove(n) => {
59                            self.applied = true;
60                            return Some(n.clone());
61                        }
62                        Change::Edit { old_node, .. } => {
63                            assert!(
64                                self.edit_new_applied,
65                                "edit overlay: new node must be applied before old node"
66                            );
67                            self.edit_old_applied = true;
68                            self.applied = true;
69                            return Some(old_node.clone());
70                        }
71                        _ => {}
72                    }
73                }
74                assert!(
75                    self.applied,
76                    "overlayGenerator: overlay was never applied to any fetched node"
77                );
78                return None;
79            };
80            let mut yield_node = true;
81            if !self.applied {
82                match &self.overlay {
83                    Change::Add(n) => {
84                        if compare(&n.row, &node.row) == Ordering::Equal {
85                            self.applied = true;
86                            yield_node = false;
87                        }
88                    }
89                    Change::Remove(n) => {
90                        if compare(&n.row, &node.row) == Ordering::Less {
91                            self.applied = true;
92                            self.queue.push_back(n.clone());
93                        }
94                    }
95                    Change::Edit { node: n, old_node } => {
96                        if !self.edit_old_applied
97                            && compare(&old_node.row, &node.row) == Ordering::Less
98                        {
99                            self.edit_old_applied = true;
100                            if self.edit_new_applied {
101                                self.applied = true;
102                            }
103                            self.queue.push_back(old_node.clone());
104                        }
105                        if !self.edit_new_applied && compare(&n.row, &node.row) == Ordering::Equal {
106                            self.edit_new_applied = true;
107                            if self.edit_old_applied {
108                                self.applied = true;
109                            }
110                            yield_node = false;
111                        }
112                    }
113                    Change::Child(n, child) => {
114                        if compare(&n.row, &node.row) == Ordering::Equal {
115                            self.applied = true;
116                            self.queue
117                                .push_back(overlay_child(&node, child, &self.schema));
118                            yield_node = false;
119                        }
120                    }
121                }
122            }
123            if yield_node {
124                self.queue.push_back(node);
125            }
126        }
127    }
128}
129
130/// `node` with the child change applied to the relationship it is on.
131fn overlay_child(node: &Node, child: &ChildChange, schema: &SourceSchema) -> Node {
132    let name = child.relationship_name.as_str();
133    let original = node
134        .relationships
135        .get(name)
136        .expect("overlay: relationship on node")
137        .clone();
138    let child_schema = schema
139        .relationship(name)
140        .expect("overlay: relationship in schema")
141        .clone();
142    let change = child.change.clone();
143    node.clone().with(
144        name,
145        Rc::new(move || generate_with_overlay(original(), change.clone(), child_schema.clone())),
146    )
147}
148
149/// `generateWithOverlayUnordered`: the overlay for an unordered child
150/// stream. Removed rows go first; added rows are suppressed by primary key.
151pub fn generate_with_overlay_unordered(
152    stream: NodeStream,
153    overlay: Change,
154    schema: Rc<SourceSchema>,
155) -> NodeStream {
156    Box::new(UnorderedOverlay {
157        stream,
158        overlay,
159        schema,
160        injected: false,
161        suppressed: false,
162    })
163}
164
165struct UnorderedOverlay {
166    stream: NodeStream,
167    overlay: Change,
168    schema: Rc<SourceSchema>,
169    injected: bool,
170    suppressed: bool,
171}
172
173impl Iterator for UnorderedOverlay {
174    type Item = Node;
175
176    fn next(&mut self) -> Option<Node> {
177        if !self.injected {
178            self.injected = true;
179            match &self.overlay {
180                Change::Remove(n) => return Some(n.clone()),
181                Change::Edit { old_node, .. } => return Some(old_node.clone()),
182                _ => {}
183            }
184        }
185        let pk = &self.schema.primary_key;
186        for node in self.stream.by_ref() {
187            if !self.suppressed {
188                match &self.overlay {
189                    Change::Add(n) | Change::Edit { node: n, .. } => {
190                        if row_equals_for_compound_key(&n.row, &node.row, pk) {
191                            self.suppressed = true;
192                            continue;
193                        }
194                    }
195                    Change::Child(n, child) => {
196                        if row_equals_for_compound_key(&n.row, &node.row, pk) {
197                            self.suppressed = true;
198                            return Some(overlay_child(&node, child, &self.schema));
199                        }
200                    }
201                    Change::Remove(_) => {}
202                }
203            }
204            return Some(node);
205        }
206        assert!(
207            self.suppressed || self.overlay.change_type() == ChangeType::Remove,
208            "overlayGenerator: overlay was never applied to any fetched node"
209        );
210        None
211    }
212}
213
214pub fn row_equals_for_compound_key(a: &Row, b: &Row, key: &[String]) -> bool {
215    key.iter()
216        .all(|k| compare_values(a.get(k), b.get(k)) == Ordering::Equal)
217}
218
219pub fn is_join_match(
220    parent: &Row,
221    parent_key: &[String],
222    child: &Row,
223    child_key: &[String],
224) -> bool {
225    parent_key
226        .iter()
227        .zip(child_key)
228        .all(|(p, c)| values_equal(parent.get(p), child.get(c)))
229}
230
231/// `buildJoinConstraint`: `target_key` mapped to `source_row`'s `source_key`
232/// values, or `None` if one is null (a null key matches nothing).
233pub fn build_join_constraint(
234    source_row: &Row,
235    source_key: &[String],
236    target_key: &[String],
237) -> Option<Constraint> {
238    let mut c = Constraint::default();
239    for (s, t) in source_key.iter().zip(target_key) {
240        let value = source_row.get(s);
241        if matches!(value, Some(Value::Null)) {
242            return None;
243        }
244        c.set(t, value.cloned());
245    }
246    Some(c)
247}
248
249/// `canonicalKey`: a string key over `keys`, tagged by type so `1` and `"1"`
250/// differ.
251pub fn canonical_key(row: &Row, keys: &[String]) -> String {
252    canonical_key_with(keys, |k| row.get(k))
253}
254
255/// [`canonical_key`] of a constraint's values.
256pub fn canonical_key_of_constraint(constraint: &Constraint, keys: &[String]) -> String {
257    canonical_key_with(keys, |k| constraint.get(k))
258}
259
260fn canonical_key_with<'a>(keys: &[String], get: impl Fn(&str) -> Option<&'a Value>) -> String {
261    let mut s = String::new();
262    for (i, k) in keys.iter().enumerate() {
263        if i > 0 {
264            s.push('\0');
265        }
266        match get(k) {
267            None | Some(Value::Null) => s.push('n'),
268            Some(Value::String(v)) => {
269                s.push('s');
270                s.push_str(v);
271            }
272            Some(Value::Number(n)) => {
273                s.push('d');
274                s.push_str(&json::number::format(*n));
275            }
276            Some(Value::Bool(b)) => s.push(if *b { 't' } else { 'f' }),
277            Some(v) => {
278                s.push('j');
279                s.push_str(&json::stringify(v));
280            }
281        }
282    }
283    s
284}
285
286/// The partitions of indexed parents that share a join key, as fetch
287/// constraints; `[None]` for an unpartitioned index (`join-index.ts`).
288pub type ParentPartitions = Vec<Option<Constraint>>;
289
290struct Partition {
291    constraint: Constraint,
292    pks: HashSet<String>,
293}
294
295#[derive(Default)]
296struct JoinIndexState {
297    unpartitioned: HashMap<String, HashSet<String>>,
298    /// Join key, then partition key. Partitions keep insertion order.
299    partitioned: HashMap<String, (Vec<String>, HashMap<String, Partition>)>,
300    size: usize,
301}
302
303/// An index from join key to the parent rows that have it. `Join` and
304/// `FlippedJoin` skip the parent fetch of a child change when no indexed
305/// parent can see it.
306pub struct JoinIndex {
307    parent_key: Vec<String>,
308    primary_key: Vec<String>,
309    join_key_is_pk: bool,
310    partition_key: Option<Vec<String>>,
311    state: RefCell<JoinIndexState>,
312}
313
314impl JoinIndex {
315    pub fn new(
316        parent_key: Vec<String>,
317        primary_key: Vec<String>,
318        partition_key: Option<Vec<String>>,
319    ) -> Rc<Self> {
320        Rc::new(JoinIndex {
321            join_key_is_pk: parent_key == primary_key,
322            parent_key,
323            primary_key,
324            partition_key,
325            state: RefCell::default(),
326        })
327    }
328
329    /// The number of parent rows indexed.
330    pub fn size(&self) -> usize {
331        self.state.borrow().size
332    }
333
334    fn pk_of(&self, row: &Row, join_key: &str) -> String {
335        if self.join_key_is_pk {
336            join_key.to_owned()
337        } else {
338            canonical_key(row, &self.primary_key)
339        }
340    }
341
342    pub fn add(&self, row: &Row) {
343        let Some(join_key) = join_key_of(row, &self.parent_key) else {
344            return;
345        };
346        let pk = self.pk_of(row, &join_key);
347        let mut state = self.state.borrow_mut();
348        let state = &mut *state;
349        let Some(partition_key) = &self.partition_key else {
350            if state.unpartitioned.entry(join_key).or_default().insert(pk) {
351                state.size += 1;
352            }
353            return;
354        };
355        let part_key = canonical_key(row, partition_key);
356        let (order, partitions) = state.partitioned.entry(join_key).or_default();
357        let partition = partitions.entry(part_key.clone()).or_insert_with(|| {
358            order.push(part_key);
359            Partition {
360                constraint: Constraint::from_row(row, partition_key),
361                pks: HashSet::new(),
362            }
363        });
364        if partition.pks.insert(pk) {
365            state.size += 1;
366        }
367    }
368
369    pub fn remove(&self, row: &Row) {
370        let Some(join_key) = join_key_of(row, &self.parent_key) else {
371            return;
372        };
373        let pk = self.pk_of(row, &join_key);
374        let mut state = self.state.borrow_mut();
375        let state = &mut *state;
376        let Some(partition_key) = &self.partition_key else {
377            if let Some(pks) = state.unpartitioned.get_mut(&join_key)
378                && pks.remove(&pk)
379            {
380                state.size -= 1;
381                if pks.is_empty() {
382                    state.unpartitioned.remove(&join_key);
383                }
384            }
385            return;
386        };
387        let Some((order, partitions)) = state.partitioned.get_mut(&join_key) else {
388            return;
389        };
390        let part_key = canonical_key(row, partition_key);
391        let Some(partition) = partitions.get_mut(&part_key) else {
392            return;
393        };
394        if partition.pks.remove(&pk) {
395            state.size -= 1;
396            if partition.pks.is_empty() {
397                partitions.remove(&part_key);
398                order.retain(|k| *k != part_key);
399                if partitions.is_empty() {
400                    state.partitioned.remove(&join_key);
401                }
402            }
403        }
404    }
405
406    /// The partitions of the indexed parents whose join key matches
407    /// `child_row` over `child_key`, or `None` if there are none.
408    pub fn lookup(&self, child_row: &Row, child_key: &[String]) -> Option<ParentPartitions> {
409        let join_key = join_key_of(child_row, child_key)?;
410        let state = self.state.borrow();
411        if self.partition_key.is_none() {
412            return state
413                .unpartitioned
414                .contains_key(&join_key)
415                .then(|| vec![None]);
416        }
417        let (order, partitions) = state.partitioned.get(&join_key)?;
418        Some(
419            order
420                .iter()
421                .map(|k| Some(partitions[k].constraint.clone()))
422                .collect(),
423        )
424    }
425}
426
427/// The canonical join key of `row`, or `None` if part of it is null.
428fn join_key_of(row: &Row, key: &[String]) -> Option<String> {
429    if key.iter().any(|k| matches!(row.get(k), Some(Value::Null))) {
430        return None;
431    }
432    Some(canonical_key(row, key))
433}