1use super::*;
6use std::cell::{Cell, RefCell};
7use std::cmp::Ordering;
8use std::collections::HashSet;
9use std::rc::{Rc, Weak};
10
11pub 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
102pub 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 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 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 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
338pub 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 let mut merged = node.clone();
368 for j in 0..iters.len() {
369 while let Some(head) = ¤t[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
387pub 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 let mut witnesses_left = Vec::new();
404 let mut witnesses_entered = Vec::new();
405 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 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 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 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 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
575pub 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
599pub 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
652pub 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 c @ Change::Child(..) => c,
675 }
676}
677
678pub 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}