Skip to main content

zero_client/ivm/
filter.rs

1//! The `where` sub-graph: `Filter`, `FilterStart`, `FilterEnd`, `Exists`,
2//! `FanOut`, and `FanIn` (`packages/zql/src/ivm/filter.ts`,
3//! `filter-operators.ts`, `exists.ts`, `fan-out.ts`, and `fan-in.ts`).
4//!
5//! Filter operators have no `fetch`: a fetch through the sub-graph enters at
6//! `FilterStart`, which asks the chain whether each node passes.
7
8use super::*;
9use crate::ast::{Condition, CorrelatedSubqueryOperator};
10use crate::json::{self, Value};
11use std::cell::{Cell, RefCell};
12use std::collections::HashMap;
13use std::rc::{Rc, Weak};
14
15fn upgrade<T: ?Sized>(w: &RefCell<Weak<T>>) -> Option<Rc<T>> {
16    w.borrow().upgrade()
17}
18
19/// Filters through a pure predicate (`filter.ts`).
20pub struct Filter {
21    input: Rc<dyn FilterInput>,
22    predicate: RowPredicate,
23    output: RefCell<Weak<dyn FilterOutput>>,
24}
25
26impl Filter {
27    pub fn new(input: Rc<dyn FilterInput>, predicate: RowPredicate) -> Rc<Self> {
28        let op = Rc::new(Filter {
29            input: input.clone(),
30            predicate,
31            output: RefCell::new(no_filter_output()),
32        });
33        input.set_filter_output(Rc::downgrade(&op) as Weak<dyn FilterOutput>);
34        op
35    }
36}
37
38impl InputBase for Filter {
39    fn get_schema(&self) -> Rc<SourceSchema> {
40        self.input.get_schema()
41    }
42    fn destroy(&self) {
43        self.input.destroy()
44    }
45}
46
47impl FilterInput for Filter {
48    fn set_filter_output(&self, output: Weak<dyn FilterOutput>) {
49        *self.output.borrow_mut() = output;
50    }
51}
52
53impl Output for Filter {
54    fn push(&self, change: Change, _pusher: &dyn InputBase) {
55        if let Some(out) = upgrade(&self.output) {
56            filter_push(change, out.as_ref(), self, Some(&self.predicate));
57        }
58    }
59    fn reconcile(&self, _pusher: &dyn InputBase) {
60        if let Some(out) = upgrade(&self.output) {
61            out.reconcile(self);
62        }
63    }
64}
65
66impl FilterOutput for Filter {
67    fn begin_filter(&self) {
68        if let Some(out) = upgrade(&self.output) {
69            out.begin_filter();
70        }
71    }
72    fn end_filter(&self) {
73        if let Some(out) = upgrade(&self.output) {
74            out.end_filter();
75        }
76    }
77    fn filter(&self, node: &Node) -> bool {
78        (self.predicate)(&node.row) && upgrade(&self.output).is_some_and(|o| o.filter(node))
79    }
80}
81
82/// Adapts an `Input` to the `where` sub-graph (`filter-operators.ts`).
83pub struct FilterStart {
84    me: Weak<FilterStart>,
85    input: Rc<dyn Input>,
86    condition: Option<Condition>,
87    output: RefCell<Weak<dyn FilterOutput>>,
88}
89
90impl FilterStart {
91    pub fn new(input: Rc<dyn Input>, condition: Option<Condition>) -> Rc<Self> {
92        let op = Rc::new_cyclic(|me| FilterStart {
93            me: me.clone(),
94            input: input.clone(),
95            condition,
96            output: RefCell::new(no_filter_output()),
97        });
98        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
99        op
100    }
101
102    pub fn fetch(&self, req: &FetchRequest) -> NodeStream {
103        let me = self.me.clone();
104        let req = req.clone();
105        lazy(move || -> NodeStream {
106            let Some(me) = me.upgrade() else {
107                return empty();
108            };
109            let mut child = req.clone();
110            child.filter = merge_filters(req.filter.as_ref(), me.condition.as_ref());
111            let output = me.output.borrow().clone();
112            Box::new(FilterIterator::new(me.input.fetch(&child), output))
113        })
114    }
115}
116
117impl InputBase for FilterStart {
118    fn get_schema(&self) -> Rc<SourceSchema> {
119        self.input.get_schema()
120    }
121    fn destroy(&self) {
122        self.input.destroy()
123    }
124}
125
126impl FilterInput for FilterStart {
127    fn set_filter_output(&self, output: Weak<dyn FilterOutput>) {
128        *self.output.borrow_mut() = output;
129    }
130}
131
132impl Output for FilterStart {
133    fn push(&self, change: Change, _pusher: &dyn InputBase) {
134        if let Some(out) = upgrade(&self.output) {
135            out.push(change, self);
136        }
137    }
138    fn reconcile(&self, _pusher: &dyn InputBase) {
139        if let Some(out) = upgrade(&self.output) {
140            out.reconcile(self);
141        }
142    }
143}
144
145/// `FilterStart.fetch`'s generator: `beginFilter`, then `endFilter` once the
146/// stream ends or is dropped (the JS `finally`).
147struct FilterIterator {
148    input: Option<NodeStream>,
149    output: Weak<dyn FilterOutput>,
150}
151
152impl FilterIterator {
153    fn new(input: NodeStream, output: Weak<dyn FilterOutput>) -> Self {
154        if let Some(o) = output.upgrade() {
155            o.begin_filter();
156        }
157        FilterIterator {
158            input: Some(input),
159            output,
160        }
161    }
162
163    fn finish(&mut self) {
164        if self.input.take().is_some()
165            && let Some(o) = self.output.upgrade()
166        {
167            o.end_filter();
168        }
169    }
170}
171
172impl Iterator for FilterIterator {
173    type Item = Node;
174
175    fn next(&mut self) -> Option<Node> {
176        while let Some(node) = self.input.as_mut()?.next() {
177            if self.output.upgrade().is_some_and(|o| o.filter(&node)) {
178                return Some(node);
179            }
180        }
181        self.finish();
182        None
183    }
184}
185
186impl Drop for FilterIterator {
187    fn drop(&mut self) {
188        self.finish();
189    }
190}
191
192/// The request's filter and the operator's own, ANDed.
193pub fn merge_filters(req: Option<&Condition>, own: Option<&Condition>) -> Option<Condition> {
194    match (req, own) {
195        (r, None) => r.cloned(),
196        (None, Some(o)) => Some(o.clone()),
197        (Some(r), Some(o)) => Some(Condition::And(vec![r.clone(), o.clone()])),
198    }
199}
200
201/// Adapts the end of the `where` sub-graph back to an `Input`.
202pub struct FilterEnd {
203    start: Rc<FilterStart>,
204    input: Rc<dyn FilterInput>,
205    output: RefCell<Weak<dyn Output>>,
206}
207
208impl FilterEnd {
209    pub fn new(start: Rc<FilterStart>, input: Rc<dyn FilterInput>) -> Rc<Self> {
210        let op = Rc::new(FilterEnd {
211            start,
212            input: input.clone(),
213            output: RefCell::new(no_output()),
214        });
215        input.set_filter_output(Rc::downgrade(&op) as Weak<dyn FilterOutput>);
216        op
217    }
218}
219
220impl InputBase for FilterEnd {
221    fn get_schema(&self) -> Rc<SourceSchema> {
222        self.input.get_schema()
223    }
224    fn destroy(&self) {
225        self.input.destroy()
226    }
227}
228
229impl Input for FilterEnd {
230    fn set_output(&self, output: Weak<dyn Output>) {
231        *self.output.borrow_mut() = output;
232    }
233    fn fetch(&self, req: &FetchRequest) -> NodeStream {
234        self.start.fetch(req)
235    }
236}
237
238impl Output for FilterEnd {
239    fn push(&self, change: Change, _pusher: &dyn InputBase) {
240        if let Some(out) = upgrade(&self.output) {
241            out.push(change, self);
242        }
243    }
244    fn reconcile(&self, _pusher: &dyn InputBase) {
245        if let Some(out) = upgrade(&self.output) {
246            out.reconcile(self);
247        }
248    }
249}
250
251impl FilterOutput for FilterEnd {
252    fn begin_filter(&self) {}
253    fn end_filter(&self) {}
254    fn filter(&self, _node: &Node) -> bool {
255        true
256    }
257}
258
259/// Filters on whether a relationship is non-empty (`exists.ts`).
260pub struct Exists {
261    input: Rc<dyn FilterInput>,
262    relationship_name: String,
263    not: bool,
264    parent_join_key: Vec<String>,
265    no_size_reuse: bool,
266    cache: RefCell<HashMap<String, bool>>,
267    output: RefCell<Weak<dyn FilterOutput>>,
268    /// Set while processing a push, when relationships can be inconsistent,
269    /// to stop reusing cached sizes across rows with the same join key.
270    in_push: Cell<bool>,
271}
272
273impl Exists {
274    pub fn new(
275        input: Rc<dyn FilterInput>,
276        relationship_name: impl Into<String>,
277        parent_join_key: Vec<String>,
278        op: CorrelatedSubqueryOperator,
279    ) -> Rc<Self> {
280        let relationship_name = relationship_name.into();
281        let schema = input.get_schema();
282        assert!(
283            schema.relationship(&relationship_name).is_some(),
284            "Input schema missing {relationship_name}"
285        );
286        let op = Rc::new(Exists {
287            input: input.clone(),
288            no_size_reuse: parent_join_key == schema.primary_key,
289            relationship_name,
290            not: op == CorrelatedSubqueryOperator::NotExists,
291            parent_join_key,
292            cache: RefCell::default(),
293            output: RefCell::new(no_filter_output()),
294            in_push: Cell::new(false),
295        });
296        input.set_filter_output(Rc::downgrade(&op) as Weak<dyn FilterOutput>);
297        op
298    }
299
300    fn passes(&self, node: &Node, exists: Option<bool>) -> bool {
301        let e = exists.unwrap_or_else(|| self.fetch_size(node) > 0);
302        e != self.not
303    }
304
305    fn cache_key(&self, node: &Node) -> String {
306        let values: Vec<Value> = self
307            .parent_join_key
308            .iter()
309            .map(|k| node.row.get(k).cloned().unwrap_or(Value::Null))
310            .collect();
311        json::stringify(&Value::Array(values))
312    }
313
314    fn push_with_filter(&self, change: Change, exists: Option<bool>) {
315        if self.passes(change.node(), exists)
316            && let Some(out) = upgrade(&self.output)
317        {
318            out.push(change, self);
319        }
320    }
321
322    fn fetch_size(&self, node: &Node) -> usize {
323        let Some(relationship) = node.relationships.get(&self.relationship_name) else {
324            panic!(
325                "Exists: relationship \"{}\" not found on node",
326                self.relationship_name
327            );
328        };
329        relationship().count()
330    }
331
332    fn push_to_output(&self, change: Change) {
333        if let Some(out) = upgrade(&self.output) {
334            out.push(change, self);
335        }
336    }
337}
338
339impl InputBase for Exists {
340    fn get_schema(&self) -> Rc<SourceSchema> {
341        self.input.get_schema()
342    }
343    fn destroy(&self) {
344        self.input.destroy()
345    }
346}
347
348impl FilterInput for Exists {
349    fn set_filter_output(&self, output: Weak<dyn FilterOutput>) {
350        *self.output.borrow_mut() = output;
351    }
352}
353
354impl Output for Exists {
355    fn push(&self, change: Change, _pusher: &dyn InputBase) {
356        assert!(!self.in_push.get(), "Unexpected re-entrancy");
357        self.in_push.set(true);
358        struct Reset<'a>(&'a Cell<bool>);
359        impl Drop for Reset<'_> {
360            fn drop(&mut self) {
361                self.0.set(false);
362            }
363        }
364        let _reset = Reset(&self.in_push);
365        let Change::Child(node, child) = &change else {
366            return self.push_with_filter(change, None);
367        };
368        if child.relationship_name != self.relationship_name
369            || matches!(child.change, Change::Edit { .. } | Change::Child(..))
370        {
371            return self.push_with_filter(change, None);
372        }
373        let name = self.relationship_name.as_str();
374        match &child.change {
375            Change::Add(_) => {
376                let size = self.fetch_size(node);
377                if size == 1 {
378                    if self.not {
379                        let gone = node.clone().with(name, Rc::new(empty));
380                        self.push_to_output(Change::Remove(gone));
381                    } else {
382                        self.push_to_output(Change::Add(node.clone()));
383                    }
384                } else {
385                    self.push_with_filter(change.clone(), Some(size > 0));
386                }
387            }
388            Change::Remove(removed) => {
389                let size = self.fetch_size(node);
390                if size == 0 {
391                    if self.not {
392                        self.push_to_output(Change::Add(node.clone()));
393                    } else {
394                        let removed = removed.clone();
395                        let gone = node
396                            .clone()
397                            .with(name, Rc::new(move || from_vec(vec![removed.clone()])));
398                        self.push_to_output(Change::Remove(gone));
399                    }
400                } else {
401                    self.push_with_filter(change.clone(), Some(size > 0));
402                }
403            }
404            _ => {}
405        }
406    }
407
408    fn reconcile(&self, _pusher: &dyn InputBase) {
409        if let Some(out) = upgrade(&self.output) {
410            out.reconcile(self);
411        }
412    }
413}
414
415impl FilterOutput for Exists {
416    fn begin_filter(&self) {
417        if let Some(out) = upgrade(&self.output) {
418            out.begin_filter();
419        }
420    }
421
422    fn end_filter(&self) {
423        self.cache.borrow_mut().clear();
424        if let Some(out) = upgrade(&self.output) {
425            out.end_filter();
426        }
427    }
428
429    fn filter(&self, node: &Node) -> bool {
430        let mut exists = None;
431        if !self.no_size_reuse && !self.in_push.get() {
432            let key = self.cache_key(node);
433            let cached = self.cache.borrow().get(&key).copied();
434            exists = Some(cached.unwrap_or_else(|| {
435                let e = self.fetch_size(node) > 0;
436                self.cache.borrow_mut().insert(key, e);
437                e
438            }));
439        }
440        self.passes(node, exists) && upgrade(&self.output).is_some_and(|o| o.filter(node))
441    }
442}
443
444/// Forks the `where` sub-graph for an OR (`fan-out.ts`).
445pub struct FanOut {
446    input: Rc<dyn FilterInput>,
447    outputs: RefCell<Vec<Weak<dyn FilterOutput>>>,
448    fan_in: RefCell<Weak<FanIn>>,
449    destroy_count: Cell<usize>,
450}
451
452impl FanOut {
453    pub fn new(input: Rc<dyn FilterInput>) -> Rc<Self> {
454        let op = Rc::new(FanOut {
455            input: input.clone(),
456            outputs: RefCell::default(),
457            fan_in: RefCell::new(Weak::new()),
458            destroy_count: Cell::new(0),
459        });
460        input.set_filter_output(Rc::downgrade(&op) as Weak<dyn FilterOutput>);
461        op
462    }
463
464    pub fn set_fan_in(&self, fan_in: &Rc<FanIn>) {
465        *self.fan_in.borrow_mut() = Rc::downgrade(fan_in);
466    }
467
468    fn outputs(&self) -> Vec<Rc<dyn FilterOutput>> {
469        self.outputs
470            .borrow()
471            .iter()
472            .filter_map(Weak::upgrade)
473            .collect()
474    }
475}
476
477impl InputBase for FanOut {
478    fn get_schema(&self) -> Rc<SourceSchema> {
479        self.input.get_schema()
480    }
481    fn destroy(&self) {
482        let n = self.outputs.borrow().len();
483        assert!(
484            self.destroy_count.get() < n,
485            "FanOut already destroyed once for each output"
486        );
487        self.destroy_count.set(self.destroy_count.get() + 1);
488        if self.destroy_count.get() == n {
489            self.input.destroy();
490        }
491    }
492}
493
494impl FilterInput for FanOut {
495    fn set_filter_output(&self, output: Weak<dyn FilterOutput>) {
496        self.outputs.borrow_mut().push(output);
497    }
498}
499
500impl Output for FanOut {
501    fn push(&self, change: Change, _pusher: &dyn InputBase) {
502        let change_type = change.change_type();
503        for o in self.outputs() {
504            o.push(change.clone(), self);
505        }
506        let fan_in = upgrade(&self.fan_in).expect("fan-out must have a corresponding fan-in set!");
507        fan_in.fan_out_done_pushing_to_all_branches(change_type);
508    }
509
510    fn reconcile(&self, _pusher: &dyn InputBase) {
511        for o in self.outputs() {
512            o.reconcile(self);
513        }
514        if let Some(fan_in) = upgrade(&self.fan_in) {
515            fan_in.fan_out_done_reconciling();
516        }
517    }
518}
519
520impl FilterOutput for FanOut {
521    fn begin_filter(&self) {
522        for o in self.outputs() {
523            o.begin_filter();
524        }
525    }
526    fn end_filter(&self) {
527        for o in self.outputs() {
528            o.end_filter();
529        }
530    }
531    fn filter(&self, node: &Node) -> bool {
532        self.outputs().iter().any(|o| o.filter(node))
533    }
534}
535
536/// Merges the branches of an OR, removing duplicates (`fan-in.ts`).
537pub struct FanIn {
538    inputs: Vec<Rc<dyn FilterInput>>,
539    schema: Rc<SourceSchema>,
540    output: RefCell<Weak<dyn FilterOutput>>,
541    accumulated: RefCell<Vec<Change>>,
542}
543
544impl FanIn {
545    pub fn new(fan_out: &Rc<FanOut>, inputs: Vec<Rc<dyn FilterInput>>) -> Rc<Self> {
546        let schema = fan_out.get_schema();
547        let op = Rc::new(FanIn {
548            inputs: inputs.clone(),
549            schema: schema.clone(),
550            output: RefCell::new(no_filter_output()),
551            accumulated: RefCell::default(),
552        });
553        for input in &inputs {
554            input.set_filter_output(Rc::downgrade(&op) as Weak<dyn FilterOutput>);
555            assert!(
556                Rc::ptr_eq(&schema, &input.get_schema()),
557                "Schema mismatch in fan-in"
558            );
559        }
560        op
561    }
562
563    pub fn fan_out_done_pushing_to_all_branches(&self, fan_out_change_type: ChangeType) {
564        if self.inputs.is_empty() {
565            assert!(
566                self.accumulated.borrow().is_empty(),
567                "If there are no inputs then fan-in should not receive any pushes."
568            );
569            return;
570        }
571        let changes = std::mem::take(&mut *self.accumulated.borrow_mut());
572        let Some(out) = upgrade(&self.output) else {
573            return;
574        };
575        push_accumulated_changes(
576            changes,
577            out.as_ref(),
578            self,
579            fan_out_change_type,
580            &|a, _| a,
581            &|c| c,
582            None,
583        );
584    }
585
586    pub fn fan_out_done_reconciling(&self) {
587        if self.inputs.is_empty() {
588            return;
589        }
590        if let Some(out) = upgrade(&self.output) {
591            out.reconcile(self);
592        }
593    }
594}
595
596impl InputBase for FanIn {
597    fn get_schema(&self) -> Rc<SourceSchema> {
598        self.schema.clone()
599    }
600    fn destroy(&self) {
601        for i in &self.inputs {
602            i.destroy();
603        }
604    }
605}
606
607impl FilterInput for FanIn {
608    fn set_filter_output(&self, output: Weak<dyn FilterOutput>) {
609        *self.output.borrow_mut() = output;
610    }
611}
612
613impl Output for FanIn {
614    fn push(&self, change: Change, _pusher: &dyn InputBase) {
615        self.accumulated.borrow_mut().push(change);
616    }
617    fn reconcile(&self, _pusher: &dyn InputBase) {}
618}
619
620impl FilterOutput for FanIn {
621    fn begin_filter(&self) {
622        if let Some(out) = upgrade(&self.output) {
623            out.begin_filter();
624        }
625    }
626    fn end_filter(&self) {
627        if let Some(out) = upgrade(&self.output) {
628            out.end_filter();
629        }
630    }
631    fn filter(&self, node: &Node) -> bool {
632        upgrade(&self.output).is_some_and(|o| o.filter(node))
633    }
634}