1use 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
16fn 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
34type 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 gate_bound: Option<Row>,
116}
117
118pub 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 row_hidden_from_fetch: RefCell<Option<Row>>,
129 take_gate: RefCell<Weak<TakeGate>>,
130 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 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 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 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 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 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 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; };
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 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 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 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 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 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; }
496 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()); }
522 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 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
635pub 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
647pub 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
658pub struct Skip {
661 me: Weak<Skip>,
662 input: Rc<dyn Input>,
663 exclusive: bool,
664 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 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 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 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 pks: Vec<String>,
792}
793
794pub 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 let me = self.clone();
892 Box::new(state.pks.into_iter().flat_map(move |pk| {
893 let pk_constraint = me.deserialize_pk(&pk);
894 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 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 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}