Skip to main content

zero_client/ivm/
union_fan.rs

1//! `UnionFanOut` and `UnionFanIn`, which fork and merge a pipeline for an OR
2//! with flipped subqueries (`union-fan-out.ts`, `union-fan-in.ts`), and
3//! `pushAccumulatedChanges` (`push-accumulated.ts`), which `FanIn` shares.
4
5use super::*;
6use std::cell::{Cell, RefCell};
7use std::cmp::Ordering;
8use std::collections::HashSet;
9use std::rc::{Rc, Weak};
10
11/// Forks a pipeline for an OR with flipped subqueries (`union-fan-out.ts`).
12pub struct UnionFanOut {
13    destroy_count: Cell<usize>,
14    fan_in: RefCell<Weak<UnionFanIn>>,
15    input: Rc<dyn Input>,
16    outputs: RefCell<Vec<Weak<dyn Output>>>,
17}
18
19impl UnionFanOut {
20    pub fn new(input: Rc<dyn Input>) -> Rc<Self> {
21        let op = Rc::new(UnionFanOut {
22            destroy_count: Cell::new(0),
23            fan_in: RefCell::new(Weak::new()),
24            input: input.clone(),
25            outputs: RefCell::default(),
26        });
27        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
28        op
29    }
30
31    fn set_fan_in(&self, fan_in: &Rc<UnionFanIn>) {
32        assert!(
33            self.fan_in.borrow().upgrade().is_none(),
34            "FanIn already set for this FanOut"
35        );
36        *self.fan_in.borrow_mut() = Rc::downgrade(fan_in);
37    }
38
39    fn fan_in(&self) -> Rc<UnionFanIn> {
40        self.fan_in
41            .borrow()
42            .upgrade()
43            .expect("UnionFanOut has no fan-in")
44    }
45
46    fn outputs(&self) -> Vec<Rc<dyn Output>> {
47        self.outputs
48            .borrow()
49            .iter()
50            .filter_map(Weak::upgrade)
51            .collect()
52    }
53}
54
55impl InputBase for UnionFanOut {
56    fn get_schema(&self) -> Rc<SourceSchema> {
57        self.input.get_schema()
58    }
59    fn destroy(&self) {
60        let n = self.outputs.borrow().len();
61        assert!(
62            self.destroy_count.get() < n,
63            "FanOut already destroyed once for each output"
64        );
65        self.destroy_count.set(self.destroy_count.get() + 1);
66        if self.destroy_count.get() == n {
67            self.input.destroy();
68        }
69    }
70}
71
72impl Input for UnionFanOut {
73    fn set_output(&self, output: Weak<dyn Output>) {
74        self.outputs.borrow_mut().push(output);
75    }
76    fn fetch(&self, req: &FetchRequest) -> NodeStream {
77        self.input.fetch(req)
78    }
79}
80
81impl Output for UnionFanOut {
82    fn push(&self, change: Change, _pusher: &dyn InputBase) {
83        let fan_in = self.fan_in();
84        fan_in.fan_out_started_pushing();
85        let change_type = change.change_type();
86        for o in self.outputs() {
87            o.push(change.clone(), self);
88        }
89        fan_in.fan_out_done_pushing(change_type);
90    }
91
92    fn reconcile(&self, _pusher: &dyn InputBase) {
93        let fan_in = self.fan_in();
94        fan_in.fan_out_started_reconciling();
95        for o in self.outputs() {
96            o.reconcile(self);
97        }
98        fan_in.fan_out_done_reconciling();
99    }
100}
101
102/// Merges the branches of a `UnionFanOut` (`union-fan-in.ts`).
103pub struct UnionFanIn {
104    inputs: Vec<Rc<dyn Input>>,
105    schema: Rc<SourceSchema>,
106    fan_out_push_started: Cell<bool>,
107    fan_out_reconcile_started: Cell<bool>,
108    output: RefCell<Weak<dyn Output>>,
109    accumulated: RefCell<Vec<Change>>,
110    /// Relationships the branches add (flipped joins' witnesses).
111    branch_rels: HashSet<String>,
112}
113
114impl UnionFanIn {
115    pub fn new(fan_out: &Rc<UnionFanOut>, inputs: Vec<Rc<dyn Input>>) -> Rc<Self> {
116        let fan_out_schema = fan_out.get_schema();
117        assert!(
118            fan_out_schema.sort.is_some(),
119            "UnionFanIn requires sorted input"
120        );
121        let mut relationships = fan_out_schema.relationships.clone();
122        let mut from_branches = HashSet::new();
123        for input in &inputs {
124            let s = input.get_schema();
125            assert!(
126                fan_out_schema.table_name == s.table_name,
127                "Table name mismatch in union fan-in: {} !== {}",
128                fan_out_schema.table_name,
129                s.table_name
130            );
131            assert!(
132                fan_out_schema.primary_key == s.primary_key,
133                "Primary key mismatch in union fan-in"
134            );
135            assert!(
136                fan_out_schema.system == s.system,
137                "System mismatch in union fan-in"
138            );
139            for (name, rel) in &s.relationships {
140                if fan_out_schema.relationship(name).is_some() {
141                    continue;
142                }
143                assert!(
144                    from_branches.insert(name.clone()),
145                    "Relationship {name} exists in multiple upstream inputs to union fan-in"
146                );
147                relationships.push((name.clone(), rel.clone()));
148            }
149        }
150        let mut schema = (*fan_out_schema).clone();
151        schema.relationships = relationships;
152        let op = Rc::new(UnionFanIn {
153            inputs: inputs.clone(),
154            schema: Rc::new(schema),
155            fan_out_push_started: Cell::new(false),
156            fan_out_reconcile_started: Cell::new(false),
157            output: RefCell::new(no_output()),
158            accumulated: RefCell::default(),
159            branch_rels: from_branches,
160        });
161        fan_out.set_fan_in(&op);
162        for input in &inputs {
163            input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
164        }
165        op
166    }
167
168    fn output(&self) -> Option<Rc<dyn Output>> {
169        self.output.borrow().upgrade()
170    }
171
172    /// A change from inside the fan-out/fan-in sub-graph, which only a
173    /// flipped join's child produces. An add or remove is forwarded when no
174    /// other branch has the row.
175    fn push_internal_change(&self, change: Change, pusher: &dyn InputBase) {
176        if change.change_type() == ChangeType::Child {
177            if let Some(out) = self.output() {
178                out.push(change, self);
179            }
180            return;
181        }
182        assert!(
183            matches!(change, Change::Add(_) | Change::Remove(_)),
184            "UnionFanIn: expected add or remove change type, got {}",
185            change.change_type() as u8
186        );
187        let mut had_match = false;
188        for input in &self.inputs {
189            if is_same(input.as_ref(), pusher) {
190                had_match = true;
191                continue;
192            }
193            let constraint = Constraint::from_row(&change.node().row, &self.schema.primary_key);
194            let req = FetchRequest {
195                constraint: Some(constraint),
196                ..FetchRequest::default()
197            };
198            if input.fetch(&req).next().is_some() {
199                // Another branch keeps the row; it gained or lost this
200                // branch's witnesses.
201                if let Some(out) = self.output() {
202                    let rels = &self.branch_rels;
203                    push_witness_deltas(
204                        change.node(),
205                        change.change_type(),
206                        &|n| rels.contains(n),
207                        out.as_ref(),
208                        self,
209                    );
210                }
211                return;
212            }
213        }
214        assert!(
215            had_match,
216            "Pusher was not one of the inputs to union-fan-in!"
217        );
218        if let Some(out) = self.output() {
219            out.push(change, self);
220        }
221    }
222
223    fn fan_out_started_pushing(&self) {
224        assert!(
225            !self.fan_out_push_started.get(),
226            "UnionFanIn: fanOutStartedPushing called while already pushing"
227        );
228        self.fan_out_push_started.set(true);
229    }
230
231    fn fan_out_done_pushing(&self, fan_out_change_type: ChangeType) {
232        assert!(
233            self.fan_out_push_started.get(),
234            "UnionFanIn: fanOutDonePushing called without fanOutStartedPushing"
235        );
236        self.fan_out_push_started.set(false);
237        let changes = std::mem::take(&mut *self.accumulated.borrow_mut());
238        if self.inputs.is_empty() || changes.is_empty() {
239            return;
240        }
241        let Some(out) = self.output() else {
242            return;
243        };
244        let schema = self.schema.clone();
245        let rels = &self.branch_rels;
246        push_accumulated_changes(
247            changes,
248            out.as_ref(),
249            self,
250            fan_out_change_type,
251            &merge_relationships,
252            &|c| make_add_empty_relationships(&schema, c),
253            Some(&|n| rels.contains(n)),
254        );
255    }
256
257    fn fan_out_started_reconciling(&self) {
258        assert!(
259            !self.fan_out_reconcile_started.get(),
260            "UnionFanIn: fanOutStartedReconciling called while already reconciling"
261        );
262        self.fan_out_reconcile_started.set(true);
263    }
264
265    fn fan_out_done_reconciling(&self) {
266        assert!(
267            self.fan_out_reconcile_started.get(),
268            "UnionFanIn: fanOutDoneReconciling called without fanOutStartedReconciling"
269        );
270        self.fan_out_reconcile_started.set(false);
271        if self.inputs.is_empty() {
272            return;
273        }
274        if let Some(out) = self.output() {
275            out.reconcile(self);
276        }
277    }
278}
279
280impl InputBase for UnionFanIn {
281    fn get_schema(&self) -> Rc<SourceSchema> {
282        self.schema.clone()
283    }
284    fn destroy(&self) {
285        for i in &self.inputs {
286            i.destroy();
287        }
288    }
289}
290
291impl Input for UnionFanIn {
292    fn set_output(&self, output: Weak<dyn Output>) {
293        *self.output.borrow_mut() = output;
294    }
295
296    fn fetch(&self, req: &FetchRequest) -> NodeStream {
297        let streams: Vec<NodeStream> = self.inputs.iter().map(|i| i.fetch(req)).collect();
298        let compare_rows = self.schema.compare_rows.clone();
299        let reverse = req.reverse;
300        let compare: NodeComparator = Rc::new(move |a: &Node, b: &Node| {
301            if reverse {
302                compare_rows(&b.row, &a.row)
303            } else {
304                compare_rows(&a.row, &b.row)
305            }
306        });
307        let names: Vec<String> = self
308            .schema
309            .relationship_names()
310            .into_iter()
311            .map(str::to_owned)
312            .collect();
313        Box::new(merge_fetches(streams, compare).map(move |mut node| {
314            merge_empty(&mut node.relationships, &names);
315            node
316        }))
317    }
318}
319
320impl Output for UnionFanIn {
321    fn push(&self, change: Change, pusher: &dyn InputBase) {
322        if !self.fan_out_push_started.get() {
323            return self.push_internal_change(change, pusher);
324        }
325        self.accumulated.borrow_mut().push(change);
326    }
327
328    fn reconcile(&self, _pusher: &dyn InputBase) {
329        if self.fan_out_reconcile_started.get() {
330            return;
331        }
332        if let Some(out) = self.output() {
333            out.reconcile(self);
334        }
335    }
336}
337
338/// `mergeFetches`: merges sorted branch streams, uniting the relationships
339/// of a row that several branches yield (the first branch wins a conflict).
340pub fn merge_fetches(fetches: Vec<NodeStream>, compare: NodeComparator) -> NodeStream {
341    lazy(move || {
342        let mut iters = fetches;
343        let mut current: Vec<Option<Node>> = iters.iter_mut().map(|i| i.next()).collect();
344        let mut last: Option<Node> = None;
345        std::iter::from_fn(move || {
346            loop {
347                let mut min: Option<usize> = None;
348                for (i, c) in current.iter().enumerate() {
349                    let Some(c) = c else { continue };
350                    if min.is_none_or(|m| {
351                        compare(c, current[m].as_ref().expect("head")) == Ordering::Less
352                    }) {
353                        min = Some(i);
354                    }
355                }
356                let i = min?;
357                let node = current[i].take().expect("head");
358                current[i] = iters[i].next();
359                if last
360                    .as_ref()
361                    .is_some_and(|l| compare(l, &node) == Ordering::Equal)
362                {
363                    continue;
364                }
365                // The same row at the head of another branch: union its
366                // relationships in rather than dropping it.
367                let mut merged = node.clone();
368                for j in 0..iters.len() {
369                    while let Some(head) = &current[j]
370                        && compare(head, &node) == Ordering::Equal
371                    {
372                        merged.relationships = head.relationships.merging(&merged.relationships);
373                        current[j] = iters[j].next();
374                    }
375                }
376                last = Some(node);
377                return Some(merged);
378            }
379        })
380    })
381}
382
383type MergeFn<'a> = &'a dyn Fn(Change, Change) -> Change;
384type FillFn<'a> = &'a dyn Fn(Change) -> Change;
385type IsBranchRel<'a> = Option<&'a dyn Fn(&str) -> bool>;
386
387/// `pushAccumulatedChanges` (`push-accumulated.ts`): pushes the single
388/// change that the changes collected from an OR's branches amount to.
389pub fn push_accumulated_changes(
390    accumulated: Vec<Change>,
391    output: &dyn Output,
392    pusher: &dyn InputBase,
393    fan_out_change_type: ChangeType,
394    merge: MergeFn,
395    add_empty: FillFn,
396    is_branch_rel: IsBranchRel,
397) {
398    if accumulated.is_empty() {
399        return;
400    }
401    // Witness changes of a nested union pass through around this fan-in's
402    // change: removals before, additions after.
403    let mut witnesses_left = Vec::new();
404    let mut witnesses_entered = Vec::new();
405    // One change per type, in the order the types first appeared.
406    let mut candidates: Vec<(ChangeType, Change)> = Vec::new();
407    for change in accumulated {
408        if let (Some(is_branch), Change::Child(_, child)) = (is_branch_rel, &change)
409            && is_branch(&child.relationship_name)
410        {
411            if child.change.change_type() == ChangeType::Remove {
412                witnesses_left.push(change);
413            } else {
414                witnesses_entered.push(change);
415            }
416            continue;
417        }
418        let t = change.change_type();
419        if fan_out_change_type == ChangeType::Child && t != ChangeType::Child {
420            assert!(
421                !candidates.iter().any(|(ct, _)| *ct == t),
422                "Fan-in:child expected at most one {} when fan-out is of type child",
423                t as u8
424            );
425        }
426        match candidates.iter().position(|(ct, _)| *ct == t) {
427            Some(i) => {
428                let prev = candidates.remove(i).1;
429                candidates.insert(i, (t, merge(prev, change)));
430            }
431            None => candidates.push((t, change)),
432        }
433    }
434    assert!(
435        !candidates.is_empty(),
436        "Fan-in: witness changes without a change for their row"
437    );
438    for c in witnesses_left {
439        output.push(c, pusher);
440    }
441    push_collapsed(
442        candidates,
443        output,
444        pusher,
445        fan_out_change_type,
446        merge,
447        add_empty,
448        is_branch_rel,
449    );
450    for c in witnesses_entered {
451        output.push(c, pusher);
452    }
453}
454
455fn push_collapsed(
456    candidates: Vec<(ChangeType, Change)>,
457    output: &dyn Output,
458    pusher: &dyn InputBase,
459    fan_out_change_type: ChangeType,
460    merge: MergeFn,
461    add_empty: FillFn,
462    is_branch_rel: IsBranchRel,
463) {
464    let types: Vec<ChangeType> = candidates.iter().map(|(t, _)| *t).collect();
465    let get = |t: ChangeType| {
466        candidates
467            .iter()
468            .find(|(ct, _)| *ct == t)
469            .map(|(_, c)| c.clone())
470    };
471    use ChangeType::*;
472    match fan_out_change_type {
473        Remove => {
474            assert!(types == [Remove], "Fan-in:remove expected all removes");
475            output.push(add_empty(get(Remove).expect("remove")), pusher);
476        }
477        Add => {
478            assert!(types == [Add], "Fan-in:add expected all adds");
479            output.push(add_empty(get(Add).expect("add")), pusher);
480        }
481        Edit => {
482            assert!(
483                types.iter().all(|t| matches!(t, Add | Remove | Edit)),
484                "Fan-in:edit expected all adds, removes, or edits"
485            );
486            let add = get(Add);
487            let remove = get(Remove);
488            let edit = get(Edit);
489            // The row stays: branches it left take their witnesses, branches
490            // it entered bring theirs, as child changes around the edit.
491            if let Some(is_branch) = is_branch_rel
492                && (edit.is_some() || (add.is_some() && remove.is_some()))
493            {
494                if let Some(r) = &remove {
495                    push_witness_deltas(r.node(), Remove, is_branch, output, pusher);
496                }
497                let strip = |n: &Node| {
498                    let mut r = Relationships::default();
499                    for (k, v) in n.relationships.iter() {
500                        if !is_branch(k) {
501                            r.set(k, Some(v.clone()));
502                        }
503                    }
504                    Node {
505                        row: n.row.clone(),
506                        relationships: r,
507                    }
508                };
509                let change = edit.unwrap_or_else(|| Change::Edit {
510                    node: strip(add.as_ref().expect("add").node()),
511                    old_node: strip(remove.as_ref().expect("remove").node()),
512                });
513                output.push(add_empty(change), pusher);
514                if let Some(a) = &add {
515                    push_witness_deltas(a.node(), Add, is_branch, output, pusher);
516                }
517                return;
518            }
519            // An edit supersedes adds and removes.
520            if let Some(mut e) = edit {
521                if let Some(a) = add {
522                    e = merge(e, a);
523                }
524                if let Some(r) = remove {
525                    e = merge(e, r);
526                }
527                output.push(add_empty(e), pusher);
528                return;
529            }
530            // A branch turned the edit into a remove and another into an add.
531            match (add, remove) {
532                (Some(a), Some(r)) => output.push(
533                    add_empty(Change::Edit {
534                        node: a.node().clone(),
535                        old_node: r.node().clone(),
536                    }),
537                    pusher,
538                ),
539                (a, r) => output.push(add_empty(a.or(r).expect("add or remove")), pusher),
540            }
541        }
542        Child => {
543            assert!(
544                types.iter().all(|t| matches!(t, Add | Remove | Child)),
545                "Fan-in:child expected all adds, removes, or children"
546            );
547            assert!(
548                types.len() <= 2,
549                "Fan-in:child expected at most 2 types on a child change from fan-out"
550            );
551            // A branch that kept the child change takes precedence.
552            if let Some(child) = get(Child) {
553                let left = get(Remove);
554                let entered = get(Add);
555                if let (Some(is_branch), Some(l)) = (is_branch_rel, &left) {
556                    push_witness_deltas(l.node(), Remove, is_branch, output, pusher);
557                }
558                output.push(child, pusher);
559                if let (Some(is_branch), Some(e)) = (is_branch_rel, &entered) {
560                    push_witness_deltas(e.node(), Add, is_branch, output, pusher);
561                }
562                return;
563            }
564            let add = get(Add);
565            let remove = get(Remove);
566            assert!(
567                add.is_none() || remove.is_none(),
568                "Fan-in:child expected either add or remove, not both"
569            );
570            output.push(add_empty(add.or(remove).expect("add or remove")), pusher);
571        }
572    }
573}
574
575/// The row stays, but gained (`add`) or lost (`remove`) every witness in
576/// its branch relationships: one child change per witness.
577pub fn push_witness_deltas(
578    node: &Node,
579    change_type: ChangeType,
580    is_branch_rel: &dyn Fn(&str) -> bool,
581    output: &dyn Output,
582    pusher: &dyn InputBase,
583) {
584    for (name, children) in node.relationships.iter() {
585        if !is_branch_rel(name) {
586            continue;
587        }
588        for child in children() {
589            let change = if change_type == ChangeType::Add {
590                Change::Add(child)
591            } else {
592                Change::Remove(child)
593            };
594            output.push(Change::child(node.clone(), name, change), pusher);
595        }
596    }
597}
598
599/// `mergeRelationships`: puts `right`'s relationships into `left` where
600/// `left` lacks them.
601pub fn merge_relationships(left: Change, right: Change) -> Change {
602    let merged = |l: &Node, r: &Node| Node {
603        row: l.row.clone(),
604        relationships: r.relationships.merging(&l.relationships),
605    };
606    match (left, right) {
607        (Change::Add(l), Change::Add(r)) => Change::Add(merged(&l, &r)),
608        (Change::Remove(l), Change::Remove(r)) => Change::Remove(merged(&l, &r)),
609        (
610            Change::Edit {
611                node: l,
612                old_node: lo,
613            },
614            Change::Edit {
615                node: r,
616                old_node: ro,
617            },
618        ) => Change::Edit {
619            node: merged(&l, &r),
620            old_node: merged(&lo, &ro),
621        },
622        (Change::Child(l, child), Change::Child(r, _)) => Change::Child(merged(&l, &r), child),
623        (
624            Change::Edit {
625                node: l,
626                old_node: lo,
627            },
628            Change::Add(r),
629        ) => Change::Edit {
630            node: merged(&l, &r),
631            old_node: lo,
632        },
633        (
634            Change::Edit {
635                node: l,
636                old_node: lo,
637            },
638            Change::Remove(r),
639        ) => Change::Edit {
640            node: l,
641            old_node: merged(&lo, &r),
642        },
643        (left, right) if left.change_type() != ChangeType::Edit => panic!(
644            "mergeRelationships: when types differ, left.type must be edit, got left.type={}, right.type={}",
645            left.change_type() as u8,
646            right.change_type() as u8
647        ),
648        _ => panic!("mergeRelationships: unexpected right change"),
649    }
650}
651
652/// `makeAddEmptyRelationships(schema)(change)`.
653pub fn make_add_empty_relationships(schema: &SourceSchema, change: Change) -> Change {
654    if schema.relationships.is_empty() {
655        return change;
656    }
657    let names: Vec<String> = schema
658        .relationship_names()
659        .into_iter()
660        .map(str::to_owned)
661        .collect();
662    let fill = |mut n: Node| {
663        merge_empty(&mut n.relationships, &names);
664        n
665    };
666    match change {
667        Change::Add(n) => Change::Add(fill(n)),
668        Change::Remove(n) => Change::Remove(fill(n)),
669        Change::Edit { node, old_node } => Change::Edit {
670            node: fill(node),
671            old_node: fill(old_node),
672        },
673        // Only the path to the change has relationships.
674        c @ Change::Child(..) => c,
675    }
676}
677
678/// Adds an empty stream for each of `names` that `relationships` lacks.
679pub fn merge_empty(relationships: &mut Relationships, names: &[String]) {
680    for name in names {
681        if relationships.get(name).is_none() {
682            relationships.set(name, Some(Rc::new(empty)));
683        }
684    }
685}