Skip to main content

zero_client/ivm/
take.rs

1//! `Take`, `Skip`, and `Cap` (`packages/zql/src/ivm/take.ts`, `skip.ts`,
2//! and `cap.ts`).
3
4use super::*;
5use crate::ast::Bound;
6use crate::json::{self, Value};
7use std::cell::RefCell;
8use std::cmp::Ordering;
9use std::collections::{HashMap, HashSet};
10use std::rc::{Rc, Weak};
11
12fn upgrade<T: ?Sized>(w: &RefCell<Weak<T>>) -> Option<Rc<T>> {
13    w.borrow().upgrade()
14}
15
16/// `{key: [tag, ...partition values]}` as JS's `JSON.stringify`.
17fn state_key<'a>(tag: &str, values: impl Iterator<Item = Option<&'a Value>>) -> String {
18    let mut array = vec![Value::String(tag.to_owned())];
19    array.extend(values.map(|v| v.cloned().unwrap_or(Value::Null)));
20    json::stringify(&Value::Array(array))
21}
22
23fn fetch_first(input: &dyn Input, req: FetchRequest) -> Option<Node> {
24    input.fetch(&req).next()
25}
26
27fn start(row: &Row, basis: Basis) -> Option<Start> {
28    Some(Start {
29        row: row.clone(),
30        basis,
31    })
32}
33
34/// The first fetch of a `Take` or `Cap` partition: passes the first
35/// `limit` nodes of its input and hands the rows it counted to `store` once
36/// it is done, as the JS generator's `finally` does.
37///
38/// A node counts once the next one is asked for, as in the generator, which
39/// resumes after the `yield`. A consumer that stops early, even right after
40/// the last node, leaves the generator suspended: JS stores what it counted
41/// and asserts, so the query fails.
42/// Hands a hydrated partition's rows to its operator.
43type StoreRows = Box<dyn Fn(&[Row])>;
44
45struct Hydration {
46    input: Option<NodeStream>,
47    limit: usize,
48    rows: Vec<Row>,
49    pending: Option<Row>,
50    store: StoreRows,
51}
52
53impl Hydration {
54    fn new(input: NodeStream, limit: usize, store: StoreRows) -> Self {
55        Hydration {
56            input: Some(input),
57            limit,
58            rows: Vec::new(),
59            pending: None,
60            store,
61        }
62    }
63
64    fn finish(&mut self) {
65        self.input = None;
66        (self.store)(&self.rows);
67    }
68}
69
70impl Iterator for Hydration {
71    type Item = Node;
72
73    fn next(&mut self) -> Option<Node> {
74        self.input.as_ref()?;
75        if let Some(row) = self.pending.take() {
76            self.rows.push(row);
77            if self.rows.len() == self.limit {
78                self.finish();
79                return None;
80            }
81        }
82        match self.input.as_mut()?.next() {
83            Some(node) => {
84                self.pending = Some(node.row.clone());
85                Some(node)
86            }
87            None => {
88                self.finish();
89                None
90            }
91        }
92    }
93}
94
95impl Drop for Hydration {
96    fn drop(&mut self) {
97        if self.input.is_some() {
98            self.finish();
99            report("Unexpected early return prevented full hydration");
100        }
101    }
102}
103
104#[derive(Clone, Debug)]
105struct TakeState {
106    size: usize,
107    bound: Option<Row>,
108}
109
110#[derive(Clone)]
111struct DirtyPartition {
112    constraint: Option<Constraint>,
113    /// The bound reported to an upstream `TakeGate` until reconcile, so a
114    /// removal does not unbound the gate during the push.
115    gate_bound: Option<Row>,
116}
117
118/// Implements `limit`: passes the first `limit` nodes of its input and
119/// keeps a bound, the last accepted row, to decide on pushes (`take.ts`).
120/// Counts globally or per value of a partition key.
121pub struct Take {
122    me: Weak<Take>,
123    input: Rc<dyn Input>,
124    limit: usize,
125    partition_key: Option<Vec<String>>,
126    storage: RefCell<HashMap<String, TakeState>>,
127    /// A row hidden from fetches while a split push is in flight.
128    row_hidden_from_fetch: RefCell<Option<Row>>,
129    take_gate: RefCell<Weak<TakeGate>>,
130    /// Partitions with removals in phase one that reconcile must refill, in
131    /// insertion order.
132    dirty_partitions: RefCell<Vec<(String, DirtyPartition)>>,
133    output: RefCell<Weak<dyn Output>>,
134}
135
136impl Take {
137    pub fn new(
138        input: Rc<dyn Input>,
139        limit: usize,
140        partition_key: Option<Vec<String>>,
141    ) -> Result<Rc<Self>, PipelineError> {
142        let schema = input.get_schema();
143        let Some(sort) = &schema.sort else {
144            return Err(PipelineError::new("Take requires sorted input"));
145        };
146        assert_ordering_includes_pk(sort, &schema.primary_key)?;
147        let op = Rc::new_cyclic(|me| Take {
148            me: me.clone(),
149            input: input.clone(),
150            limit,
151            partition_key,
152            storage: RefCell::default(),
153            row_hidden_from_fetch: RefCell::new(None),
154            take_gate: RefCell::new(Weak::new()),
155            dirty_partitions: RefCell::default(),
156            output: RefCell::new(no_output()),
157        });
158        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
159        Ok(op)
160    }
161
162    pub fn set_take_gate(&self, gate: &Rc<TakeGate>) {
163        *self.take_gate.borrow_mut() = Rc::downgrade(gate);
164    }
165
166    fn emit(&self, change: Change) {
167        if let Some(out) = upgrade(&self.output) {
168            out.push(change, self);
169        }
170    }
171
172    fn gate_open(&self) {
173        if let Some(g) = upgrade(&self.take_gate) {
174            g.open();
175        }
176    }
177
178    fn gate_close(&self) {
179        if let Some(g) = upgrade(&self.take_gate) {
180            g.close();
181        }
182    }
183
184    fn compare_rows(&self) -> Comparator {
185        self.input.get_schema().compare_rows.clone()
186    }
187
188    fn dirty(&self, key: &str) -> Option<DirtyPartition> {
189        self.dirty_partitions
190            .borrow()
191            .iter()
192            .find(|(k, _)| k == key)
193            .map(|(_, d)| d.clone())
194    }
195
196    fn state(&self, key: &str) -> Option<TakeState> {
197        self.storage.borrow().get(key).cloned()
198    }
199
200    fn set_state(&self, key: &str, size: usize, bound: Option<Row>) {
201        self.storage
202            .borrow_mut()
203            .insert(key.to_owned(), TakeState { size, bound });
204    }
205
206    fn row_key(&self, row: &Row) -> String {
207        let keys = self.partition_key.as_deref().unwrap_or_default();
208        state_key("take", keys.iter().map(|k| row.get(k)))
209    }
210
211    fn constraint_key(&self, constraint: Option<&Constraint>) -> String {
212        match (&self.partition_key, constraint) {
213            (Some(keys), Some(c)) => state_key("take", keys.iter().map(|k| c.get(k))),
214            _ => state_key("take", std::iter::empty()),
215        }
216    }
217
218    fn state_and_constraint(&self, row: &Row) -> (Option<TakeState>, String, Option<Constraint>) {
219        let key = self.row_key(row);
220        let state = self.state(&key);
221        let constraint = match (&state, &self.partition_key) {
222            (Some(_), Some(pk)) => Some(Constraint::from_row(row, pk)),
223            _ => None,
224        };
225        (state, key, constraint)
226    }
227
228    fn fetch_now(self: &Rc<Self>, req: FetchRequest) -> NodeStream {
229        // A flipped join fetches its child without a constraint, so a limited
230        // flipped EXISTS gets here. JS throws, and `materialize` with it.
231        if let Some(pk) = &self.partition_key
232            && !constraint_contains_partition_key(req.constraint.as_ref(), Some(pk))
233        {
234            report("Partitioned take does not allow unpartitioned fetches");
235            return empty();
236        }
237        let key = self.constraint_key(req.constraint.as_ref());
238        let Some(state) = self.state(&key) else {
239            if constraint_matches_partition_key(
240                req.constraint.as_ref(),
241                self.partition_key.as_deref(),
242            ) {
243                return self.initial_fetch(req, key);
244            }
245            return empty();
246        };
247        let Some(bound) = state.bound else {
248            return empty();
249        };
250        let me = self.clone();
251        let compare = self.compare_rows();
252        let mut it = Some(self.input.fetch(&req));
253        let mut count = 0;
254        let mut yielded = false;
255        Box::new(std::iter::from_fn(move || {
256            // Count the node yielded last on resume, as the JS generator does.
257            if yielded {
258                yielded = false;
259                count += 1;
260                if count >= me.limit {
261                    it = None;
262                }
263            }
264            while let Some(node) = it.as_mut()?.next() {
265                if compare(&bound, &node.row) == Ordering::Less {
266                    break;
267                }
268                let hidden = me.row_hidden_from_fetch.borrow().clone();
269                if hidden.is_some_and(|h| compare(&h, &node.row) == Ordering::Equal) {
270                    continue;
271                }
272                yielded = true;
273                return Some(node);
274            }
275            it = None;
276            None
277        }))
278    }
279
280    /// The first fetch of a partition: hydrates its state. The state is
281    /// written once the stream ends, as in the JS `finally`.
282    fn initial_fetch(self: &Rc<Self>, req: FetchRequest, key: String) -> NodeStream {
283        assert!(req.start.is_none(), "Start should be undefined");
284        assert!(!req.reverse, "Reverse should be false");
285        if self.limit == 0 {
286            return empty();
287        }
288        let me = self.clone();
289        let limit = self.limit;
290        Box::new(Hydration::new(
291            self.input.fetch(&req),
292            limit,
293            Box::new(move |rows: &[Row]| me.set_state(&key, rows.len(), rows.last().cloned())),
294        ))
295    }
296
297    fn push_add_or_remove(&self, change: Change) {
298        let (state, key, constraint) = self.state_and_constraint(&change.node().row);
299        let Some(state) = state else {
300            return;
301        };
302        let compare = self.compare_rows();
303        match &change {
304            Change::Add(node) => {
305                if state.size < self.limit {
306                    if self.dirty(&key).is_some() {
307                        // With an unresolved deficit, only admit rows before
308                        // the bound, so reconcile can backfill earlier rows in
309                        // order.
310                        match &state.bound {
311                            Some(b) if compare(&node.row, b) == Ordering::Less => {}
312                            _ => return,
313                        }
314                    }
315                    let next_size = state.size + 1;
316                    if next_size == self.limit {
317                        self.dirty_partitions
318                            .borrow_mut()
319                            .retain(|(k, _)| *k != key);
320                    }
321                    let bound = match &state.bound {
322                        Some(b) if compare(b, &node.row) != Ordering::Less => b.clone(),
323                        _ => node.row.clone(),
324                    };
325                    self.set_state(&key, next_size, Some(bound));
326                    self.emit(change);
327                    return;
328                }
329                // size == limit
330                let Some(bound) = &state.bound else {
331                    return;
332                };
333                if compare(&node.row, bound) != Ordering::Less {
334                    return;
335                }
336                let (bound_node, before_bound_node) = if self.limit == 1 {
337                    let first = fetch_first(
338                        self.input.as_ref(),
339                        FetchRequest {
340                            constraint: constraint.clone(),
341                            start: start(bound, Basis::At),
342                            ..FetchRequest::default()
343                        },
344                    );
345                    (first, None)
346                } else {
347                    let mut it = self.input.fetch(&FetchRequest {
348                        constraint: constraint.clone(),
349                        start: start(bound, Basis::At),
350                        reverse: true,
351                        ..FetchRequest::default()
352                    });
353                    let first = it.next();
354                    (first, it.next())
355                };
356                let bound_node = bound_node.expect("Take: boundNode must be found during fetch");
357                // Remove before add to keep output size <= limit.
358                let new_bound = match &before_bound_node {
359                    Some(b) if compare(&node.row, &b.row) != Ordering::Greater => b.row.clone(),
360                    _ => node.row.clone(),
361                };
362                self.set_state(&key, state.size, Some(new_bound));
363                self.push_with_row_hidden_from_fetch(&node.row, Change::Remove(bound_node));
364                self.emit(change);
365            }
366            Change::Remove(node) => {
367                let Some(bound) = &state.bound else {
368                    return; // after the bound
369                };
370                let comp_to_bound = compare(&node.row, bound);
371                if comp_to_bound == Ordering::Greater
372                    || (comp_to_bound == Ordering::Less && self.limit == 1)
373                {
374                    return;
375                }
376                let before_bound_node = fetch_first(
377                    self.input.as_ref(),
378                    FetchRequest {
379                        constraint: constraint.clone(),
380                        start: start(bound, Basis::After),
381                        reverse: true,
382                        ..FetchRequest::default()
383                    },
384                );
385                let final_bound = if state.size - 1 == 0 {
386                    None
387                } else if comp_to_bound == Ordering::Less {
388                    Some(bound.clone())
389                } else {
390                    before_bound_node.map(|n| n.row)
391                };
392                if self.dirty(&key).is_none() {
393                    // Snapshot the bound before the first removal for
394                    // upstream gates.
395                    self.dirty_partitions.borrow_mut().push((
396                        key.clone(),
397                        DirtyPartition {
398                            constraint,
399                            gate_bound: Some(bound.clone()),
400                        },
401                    ));
402                }
403                self.set_state(&key, state.size - 1, final_bound);
404                self.emit(change);
405            }
406            Change::Child(node, _) => {
407                if let Some(bound) = &state.bound
408                    && compare(&node.row, bound) != Ordering::Greater
409                {
410                    self.emit(change);
411                }
412            }
413            Change::Edit { .. } => {}
414        }
415    }
416
417    fn push_edit_change(&self, change: Change) {
418        let Change::Edit { node, old_node } = &change else {
419            unreachable!()
420        };
421        if let Some(pk) = &self.partition_key {
422            assert!(
423                row_equals_for_compound_key(&old_node.row, &node.row, pk),
424                "Unexpected change of partition key"
425            );
426        }
427        let (state, key, constraint) = self.state_and_constraint(&old_node.row);
428        let Some(state) = state else {
429            return;
430        };
431        let bound = state.bound.clone().expect("Bound should be set");
432        let compare = self.compare_rows();
433        let old_cmp = compare(&old_node.row, &bound);
434        let new_cmp = compare(&node.row, &bound);
435        let fetch_one = |s: Option<Start>, reverse: bool| {
436            fetch_first(
437                self.input.as_ref(),
438                FetchRequest {
439                    constraint: constraint.clone(),
440                    start: s,
441                    reverse,
442                    ..FetchRequest::default()
443                },
444            )
445        };
446        let replace_bound_and_forward = |change: Change| {
447            self.set_state(&key, state.size, Some(node.row.clone()));
448            self.emit(change);
449        };
450
451        match old_cmp {
452            Ordering::Equal => {
453                // The bound row changed.
454                match new_cmp {
455                    Ordering::Equal => self.emit(change.clone()),
456                    Ordering::Less => {
457                        if self.limit == 1 {
458                            return replace_bound_and_forward(change.clone());
459                        }
460                        // The new row stays in, but might no longer be the
461                        // bound.
462                        let before = fetch_one(start(&bound, Basis::After), true)
463                            .expect("Take: beforeBoundNode must be found during fetch");
464                        self.set_state(&key, state.size, Some(before.row));
465                        self.emit(change.clone());
466                    }
467                    Ordering::Greater => {
468                        // The first row at the old bound is the new bound.
469                        self.gate_open();
470                        let new_bound = fetch_one(start(&bound, Basis::At), false);
471                        self.gate_close();
472                        let new_bound =
473                            new_bound.expect("Take: newBoundNode must be found during fetch");
474                        if compare(&new_bound.row, &node.row) == Ordering::Equal {
475                            return replace_bound_and_forward(change.clone());
476                        }
477                        // The new row is out of bounds: remove the old row,
478                        // add the new bound.
479                        self.set_state(&key, state.size, Some(new_bound.row.clone()));
480                        self.push_with_row_hidden_from_fetch(
481                            &new_bound.row,
482                            Change::Remove(old_node.clone()),
483                        );
484                        self.emit(Change::Add(new_bound));
485                    }
486                }
487            }
488            Ordering::Greater => {
489                assert!(
490                    new_cmp != Ordering::Equal,
491                    "Invalid state. Row has duplicate primary key"
492                );
493                if new_cmp == Ordering::Greater {
494                    return; // both outside
495                }
496                // Old was outside, new is inside: push out the old bound.
497                let mut it = self.input.fetch(&FetchRequest {
498                    constraint: constraint.clone(),
499                    start: start(&bound, Basis::At),
500                    reverse: true,
501                    ..FetchRequest::default()
502                });
503                let old_bound = it
504                    .next()
505                    .expect("Take: oldBoundNode must be found during fetch");
506                let new_bound = it
507                    .next()
508                    .expect("Take: newBoundNode must be found during fetch");
509                drop(it);
510                self.set_state(&key, state.size, Some(new_bound.row));
511                self.push_with_row_hidden_from_fetch(&node.row, Change::Remove(old_bound));
512                self.emit(Change::Add(node.clone()));
513            }
514            Ordering::Less => {
515                assert!(
516                    new_cmp != Ordering::Equal,
517                    "Invalid state. Row has duplicate primary key"
518                );
519                if new_cmp == Ordering::Less {
520                    return self.emit(change.clone()); // both inside
521                }
522                // Old was inside, new is past the bound: the row after the
523                // bound or the new row is the new bound.
524                self.gate_open();
525                let after = fetch_one(start(&bound, Basis::After), false);
526                self.gate_close();
527                let after = after.expect("Take: afterBoundNode must be found during fetch");
528                if compare(&after.row, &node.row) == Ordering::Equal {
529                    return replace_bound_and_forward(change.clone());
530                }
531                self.emit(Change::Remove(old_node.clone()));
532                self.set_state(&key, state.size, Some(after.row.clone()));
533                self.emit(Change::Add(after));
534            }
535        }
536    }
537
538    fn push_with_row_hidden_from_fetch(&self, row: &Row, change: Change) {
539        *self.row_hidden_from_fetch.borrow_mut() = Some(row.clone());
540        self.emit(change);
541        *self.row_hidden_from_fetch.borrow_mut() = None;
542    }
543}
544
545impl TakeBoundProvider for Take {
546    fn get_bound(&self, constraint: Option<&Constraint>) -> Option<Row> {
547        if let Some(pk) = &self.partition_key
548            && !constraint_contains_partition_key(constraint, Some(pk))
549        {
550            return None;
551        }
552        let key = self.constraint_key(constraint);
553        if let Some(dirty) = self.dirty(&key) {
554            // Phase one: keep upstream gates at the bound before the removals.
555            return dirty.gate_bound;
556        }
557        let state = self.state(&key)?;
558        if state.size < self.limit {
559            return None;
560        }
561        state.bound
562    }
563}
564
565impl InputBase for Take {
566    fn get_schema(&self) -> Rc<SourceSchema> {
567        self.input.get_schema()
568    }
569    fn destroy(&self) {
570        self.input.destroy()
571    }
572}
573
574impl Input for Take {
575    fn set_output(&self, output: Weak<dyn Output>) {
576        *self.output.borrow_mut() = output;
577    }
578
579    fn fetch(&self, req: &FetchRequest) -> NodeStream {
580        let me = self.me.clone();
581        let req = req.clone();
582        lazy(move || -> NodeStream {
583            match me.upgrade() {
584                Some(me) => me.fetch_now(req),
585                None => empty(),
586            }
587        })
588    }
589}
590
591impl Output for Take {
592    fn push(&self, change: Change, _pusher: &dyn InputBase) {
593        if matches!(change, Change::Edit { .. }) {
594            self.push_edit_change(change);
595        } else {
596            self.push_add_or_remove(change);
597        }
598    }
599
600    fn reconcile(&self, _pusher: &dyn InputBase) {
601        let dirty = std::mem::take(&mut *self.dirty_partitions.borrow_mut());
602        for (key, d) in dirty {
603            let state = self
604                .state(&key)
605                .expect("Take: dirty partition must exist in storage");
606            assert!(
607                self.limit > state.size,
608                "Take: dirty partition must have a deficit"
609            );
610            let deficit = self.limit - state.size;
611            self.gate_open();
612            let to_push: Vec<Node> = self
613                .input
614                .fetch(&FetchRequest {
615                    constraint: d.constraint.clone(),
616                    start: state.bound.as_ref().and_then(|b| start(b, Basis::After)),
617                    ..FetchRequest::default()
618                })
619                .take(deficit)
620                .collect();
621            self.gate_close();
622            let mut size = state.size;
623            for node in to_push {
624                size += 1;
625                self.set_state(&key, size, Some(node.row.clone()));
626                self.emit(Change::Add(node));
627            }
628        }
629        if let Some(out) = upgrade(&self.output) {
630            out.reconcile(self);
631        }
632    }
633}
634
635/// `constraintMatchesPartitionKey`: the constraint is on exactly the
636/// partition key, or neither is set.
637pub fn constraint_matches_partition_key(
638    constraint: Option<&Constraint>,
639    partition_key: Option<&[String]>,
640) -> bool {
641    match (constraint, partition_key) {
642        (Some(c), Some(pk)) => pk.len() == c.len() && pk.iter().all(|k| c.has(k)),
643        (c, pk) => c.is_none() && pk.is_none(),
644    }
645}
646
647/// `constraintContainsPartitionKey`.
648pub fn constraint_contains_partition_key(
649    constraint: Option<&Constraint>,
650    partition_key: Option<&[String]>,
651) -> bool {
652    match (constraint, partition_key) {
653        (Some(c), Some(pk)) => pk.iter().all(|k| c.has(k)),
654        _ => false,
655    }
656}
657
658/// Sets where the pipeline starts: no row before the bound is output
659/// (`skip.ts`).
660pub struct Skip {
661    me: Weak<Skip>,
662    input: Rc<dyn Input>,
663    exclusive: bool,
664    /// The bound's row.
665    bound_row: Row,
666    comparator: Comparator,
667    predicate: RowPredicate,
668    output: RefCell<Weak<dyn Output>>,
669}
670
671impl Skip {
672    pub fn new(input: Rc<dyn Input>, bound: &Bound) -> Rc<Self> {
673        let schema = input.get_schema();
674        assert!(schema.sort.is_some(), "Skip requires sorted input");
675        let bound_row: Row = Rc::new(bound.row.clone());
676        let comparator = schema.compare_rows.clone();
677        let exclusive = bound.exclusive;
678        let predicate: RowPredicate = {
679            let (bound_row, comparator) = (bound_row.clone(), comparator.clone());
680            Rc::new(move |row: &Row| match comparator(&bound_row, row) {
681                Ordering::Less => true,
682                Ordering::Equal => !exclusive,
683                Ordering::Greater => false,
684            })
685        };
686        let op = Rc::new_cyclic(|me| Skip {
687            me: me.clone(),
688            input: input.clone(),
689            exclusive,
690            bound_row,
691            comparator,
692            predicate,
693            output: RefCell::new(no_output()),
694        });
695        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
696        op
697    }
698
699    /// The start of a fetch, or `None` if it yields nothing.
700    fn get_start(&self, req: &FetchRequest) -> Option<Option<Start>> {
701        let bound_start = Start {
702            row: self.bound_row.clone(),
703            basis: if self.exclusive {
704                Basis::After
705            } else {
706                Basis::At
707            },
708        };
709        let Some(req_start) = &req.start else {
710            return Some((!req.reverse).then_some(bound_start));
711        };
712        let cmp = (self.comparator)(&self.bound_row, &req_start.row);
713        if !req.reverse {
714            // The skip bound is after the requested start.
715            return Some(Some(match cmp {
716                Ordering::Greater => bound_start,
717                Ordering::Equal if self.exclusive || req_start.basis == Basis::After => Start {
718                    row: self.bound_row.clone(),
719                    basis: Basis::After,
720                },
721                Ordering::Equal => bound_start,
722                Ordering::Less => req_start.clone(),
723            }));
724        }
725        // Reverse: a bound after the start leaves nothing.
726        match cmp {
727            Ordering::Greater => None,
728            Ordering::Equal if !self.exclusive && req_start.basis == Basis::At => {
729                Some(Some(bound_start))
730            }
731            Ordering::Equal => None,
732            Ordering::Less => Some(Some(req_start.clone())),
733        }
734    }
735}
736
737impl InputBase for Skip {
738    fn get_schema(&self) -> Rc<SourceSchema> {
739        self.input.get_schema()
740    }
741    fn destroy(&self) {
742        self.input.destroy()
743    }
744}
745
746impl Input for Skip {
747    fn set_output(&self, output: Weak<dyn Output>) {
748        *self.output.borrow_mut() = output;
749    }
750
751    fn fetch(&self, req: &FetchRequest) -> NodeStream {
752        let me = self.me.clone();
753        let req = req.clone();
754        lazy(move || -> NodeStream {
755            let Some(me) = me.upgrade() else {
756                return empty();
757            };
758            let Some(start) = me.get_start(&req) else {
759                return empty();
760            };
761            let stream = me.input.fetch(&FetchRequest {
762                start,
763                ..req.clone()
764            });
765            if !req.reverse {
766                return stream;
767            }
768            let predicate = me.predicate.clone();
769            Box::new(stream.take_while(move |n| predicate(&n.row)))
770        })
771    }
772}
773
774impl Output for Skip {
775    fn push(&self, change: Change, _pusher: &dyn InputBase) {
776        if let Some(out) = upgrade(&self.output) {
777            filter_push(change, out.as_ref(), self, Some(&self.predicate));
778        }
779    }
780    fn reconcile(&self, _pusher: &dyn InputBase) {
781        if let Some(out) = upgrade(&self.output) {
782            out.reconcile(self);
783        }
784    }
785}
786
787#[derive(Clone)]
788struct CapState {
789    size: usize,
790    /// Serialized primary keys, in the order they joined the set.
791    pks: Vec<String>,
792}
793
794/// A count-based limit for EXISTS subqueries that needs no order: it tracks
795/// membership by primary key (`cap.ts`).
796pub struct Cap {
797    me: Weak<Cap>,
798    input: Rc<dyn Input>,
799    limit: usize,
800    partition_key: Option<Vec<String>>,
801    primary_key: Vec<String>,
802    storage: RefCell<HashMap<String, CapState>>,
803    output: RefCell<Weak<dyn Output>>,
804}
805
806impl Cap {
807    pub fn new(input: Rc<dyn Input>, limit: usize, partition_key: Option<Vec<String>>) -> Rc<Self> {
808        let primary_key = input.get_schema().primary_key.clone();
809        let op = Rc::new_cyclic(|me| Cap {
810            me: me.clone(),
811            input: input.clone(),
812            limit,
813            partition_key,
814            primary_key,
815            storage: RefCell::default(),
816            output: RefCell::new(no_output()),
817        });
818        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
819        op
820    }
821
822    fn emit(&self, change: Change) {
823        if let Some(out) = upgrade(&self.output) {
824            out.push(change, self);
825        }
826    }
827
828    fn state(&self, key: &str) -> Option<CapState> {
829        self.storage.borrow().get(key).cloned()
830    }
831
832    fn set_state(&self, key: &str, size: usize, pks: Vec<String>) {
833        self.storage
834            .borrow_mut()
835            .insert(key.to_owned(), CapState { size, pks });
836    }
837
838    fn row_key(&self, row: &Row) -> String {
839        let keys = self.partition_key.as_deref().unwrap_or_default();
840        state_key("cap", keys.iter().map(|k| row.get(k)))
841    }
842
843    fn constraint_key(&self, constraint: Option<&Constraint>) -> String {
844        match (&self.partition_key, constraint) {
845            (Some(keys), Some(c)) => state_key("cap", keys.iter().map(|k| c.get(k))),
846            _ => state_key("cap", std::iter::empty()),
847        }
848    }
849
850    fn serialize_pk(&self, row: &Row) -> String {
851        let values = self
852            .primary_key
853            .iter()
854            .map(|k| row.get(k).cloned().unwrap_or(Value::Null))
855            .collect();
856        json::stringify(&Value::Array(values))
857    }
858
859    fn deserialize_pk(&self, pk: &str) -> Constraint {
860        let values = match json::parse(pk) {
861            Ok(Value::Array(values)) => values,
862            _ => Vec::new(),
863        };
864        let mut c = Constraint::default();
865        for (i, k) in self.primary_key.iter().enumerate() {
866            c.set(k, values.get(i).cloned());
867        }
868        c
869    }
870
871    fn fetch_now(self: &Rc<Self>, req: FetchRequest) -> NodeStream {
872        assert!(req.start.is_none(), "Cap does not support start");
873        assert!(!req.reverse, "Cap does not support reverse");
874        assert!(
875            self.partition_key.is_none()
876                || (req.constraint.is_some()
877                    && constraint_matches_partition_key(
878                        req.constraint.as_ref(),
879                        self.partition_key.as_deref()
880                    )),
881            "Cap fetch: constraint must match partition key when partitioned"
882        );
883        let key = self.constraint_key(req.constraint.as_ref());
884        let Some(state) = self.state(&key) else {
885            return self.initial_fetch(req, key);
886        };
887        if state.size == 0 {
888            return empty();
889        }
890        // Point lookups by the tracked primary keys.
891        let me = self.clone();
892        Box::new(state.pks.into_iter().flat_map(move |pk| {
893            let pk_constraint = me.deserialize_pk(&pk);
894            // Keep the partition key so partitioned operators upstream keep
895            // their scope.
896            let constraint = match &req.constraint {
897                Some(c) => c.merging(&pk_constraint),
898                None => pk_constraint,
899            };
900            me.input.fetch(&FetchRequest {
901                constraint: Some(constraint),
902                ..FetchRequest::default()
903            })
904        }))
905    }
906
907    fn initial_fetch(self: &Rc<Self>, req: FetchRequest, key: String) -> NodeStream {
908        if self.limit == 0 {
909            return empty();
910        }
911        assert!(
912            constraint_matches_partition_key(
913                req.constraint.as_ref(),
914                self.partition_key.as_deref()
915            ),
916            "Constraint should match partition key"
917        );
918        let me = self.clone();
919        Box::new(Hydration::new(
920            self.input.fetch(&req),
921            self.limit,
922            Box::new(move |rows: &[Row]| {
923                let pks = rows.iter().map(|r| me.serialize_pk(r)).collect();
924                me.set_state(&key, rows.len(), pks)
925            }),
926        ))
927    }
928}
929
930impl InputBase for Cap {
931    fn get_schema(&self) -> Rc<SourceSchema> {
932        self.input.get_schema()
933    }
934    fn destroy(&self) {
935        self.input.destroy()
936    }
937}
938
939impl Input for Cap {
940    fn set_output(&self, output: Weak<dyn Output>) {
941        *self.output.borrow_mut() = output;
942    }
943
944    fn fetch(&self, req: &FetchRequest) -> NodeStream {
945        let me = self.me.clone();
946        let req = req.clone();
947        lazy(move || -> NodeStream {
948            match me.upgrade() {
949                Some(me) => me.fetch_now(req),
950                None => empty(),
951            }
952        })
953    }
954}
955
956impl Output for Cap {
957    fn push(&self, change: Change, _pusher: &dyn InputBase) {
958        if let Change::Edit { node, old_node } = &change {
959            if let Some(pk) = &self.partition_key {
960                assert!(
961                    row_equals_for_compound_key(&old_node.row, &node.row, pk),
962                    "Unexpected change of partition key"
963                );
964            }
965            let key = self.row_key(&old_node.row);
966            let Some(state) = self.state(&key) else {
967                return;
968            };
969            let old_pk = self.serialize_pk(&old_node.row);
970            if state.pks.contains(&old_pk) {
971                let new_pk = self.serialize_pk(&node.row);
972                if old_pk != new_pk {
973                    let pks = state
974                        .pks
975                        .iter()
976                        .map(|p| {
977                            if *p == old_pk {
978                                new_pk.clone()
979                            } else {
980                                p.clone()
981                            }
982                        })
983                        .collect();
984                    self.set_state(&key, state.size, pks);
985                }
986                self.emit(change);
987            }
988            return;
989        }
990        let key = self.row_key(&change.node().row);
991        let Some(state) = self.state(&key) else {
992            return;
993        };
994        let pk = self.serialize_pk(&change.node().row);
995        match &change {
996            Change::Add(_) => {
997                if state.size < self.limit {
998                    let mut pks = state.pks;
999                    pks.push(pk);
1000                    self.set_state(&key, state.size + 1, pks);
1001                    self.emit(change);
1002                }
1003            }
1004            Change::Remove(node) => {
1005                let Some(i) = state.pks.iter().position(|p| *p == pk) else {
1006                    return;
1007                };
1008                let mut pks = state.pks;
1009                pks.remove(i);
1010                let new_size = state.size - 1;
1011                // Refill with the first row not in the set.
1012                let pk_set: HashSet<&String> = pks.iter().collect();
1013                let constraint = self
1014                    .partition_key
1015                    .as_ref()
1016                    .map(|k| Constraint::from_row(&node.row, k));
1017                let replacement = self
1018                    .input
1019                    .fetch(&FetchRequest {
1020                        constraint,
1021                        ..FetchRequest::default()
1022                    })
1023                    .find(|c| !pk_set.contains(&self.serialize_pk(&c.row)));
1024                match replacement {
1025                    Some(replacement) => {
1026                        // Without the replacement while the remove is
1027                        // forwarded.
1028                        self.set_state(&key, new_size, pks.clone());
1029                        self.emit(change);
1030                        pks.push(self.serialize_pk(&replacement.row));
1031                        self.set_state(&key, new_size + 1, pks);
1032                        self.emit(Change::Add(replacement));
1033                    }
1034                    None => {
1035                        self.set_state(&key, new_size, pks);
1036                        self.emit(change);
1037                    }
1038                }
1039            }
1040            Change::Child(..) => {
1041                if state.pks.contains(&pk) {
1042                    self.emit(change);
1043                }
1044            }
1045            Change::Edit { .. } => {}
1046        }
1047    }
1048
1049    fn reconcile(&self, _pusher: &dyn InputBase) {
1050        if let Some(out) = upgrade(&self.output) {
1051            out.reconcile(self);
1052        }
1053    }
1054}