1use super::btree::Tree;
9use super::*;
10use crate::ast::{Condition, Direction, OrderPart};
11use crate::json::{self, Value};
12use crate::schema::Table;
13use std::cell::{Cell, RefCell};
14use std::cmp::Ordering;
15use std::collections::{HashMap, HashSet};
16use std::rc::{Rc, Weak};
17
18#[derive(Clone)]
19struct Overlay {
20 epoch: u64,
21 change: SourceChange,
22}
23
24#[derive(Clone, Default)]
25struct Overlays {
26 add: Option<Row>,
27 remove: Option<Row>,
28}
29
30#[derive(Clone)]
31struct Index {
32 sort: Vec<OrderPart>,
33 compare: Comparator,
34 data: Tree<Row>,
35}
36
37impl Index {
38 fn new(sort: Vec<OrderPart>, data: Tree<Row>) -> Self {
39 let compare = make_comparator(&sort, false);
40 Index {
41 sort,
42 compare,
43 data,
44 }
45 }
46
47 fn contains(&self, row: &Row) -> bool {
48 self.data.get(row, &*self.compare).is_some()
49 }
50
51 fn add(&mut self, row: Row) {
53 self.data.add(row, &*self.compare);
54 }
55
56 fn delete(&mut self, row: &Row) -> bool {
58 self.data.delete(row, &*self.compare)
59 }
60
61 fn probe(&self, bound: HashMap<String, Bound>) -> impl Fn(&Row) -> Ordering + use<> {
64 let parts: Vec<(String, bool, Bound)> = self
65 .sort
66 .iter()
67 .map(|p| {
68 let b = bound.get(&p.field).cloned().unwrap_or(Bound::Value(None));
69 (p.field.clone(), p.direction == Direction::Asc, b)
70 })
71 .collect();
72 move |row: &Row| {
73 for (field, asc, b) in &parts {
74 let c = compare_bounds(&Bound::Value(row.get(field).cloned()), b);
75 if c != Ordering::Equal {
76 return if *asc { c } else { c.reverse() };
77 }
78 }
79 Ordering::Equal
80 }
81 }
82}
83
84#[derive(Clone, Debug)]
86enum Bound {
87 Value(Option<Value>),
88 Min,
89 Max,
90}
91
92fn compare_bounds(a: &Bound, b: &Bound) -> Ordering {
93 use Bound::*;
94 match (a, b) {
95 (Min, Min) | (Max, Max) => Ordering::Equal,
96 (Min, _) | (_, Max) => Ordering::Less,
97 (Max, _) | (_, Min) => Ordering::Greater,
98 (Value(x), Value(y)) => compare_values(x.as_ref(), y.as_ref()),
99 }
100}
101
102struct Connection {
103 input: RefCell<Weak<MemorySourceInput>>,
104 output: RefCell<Weak<dyn Output>>,
105 sort: Vec<OrderPart>,
106 split_edit_keys: Option<HashSet<String>>,
107 compare_rows: Comparator,
108 filters: Option<(Condition, RowPredicate)>,
109 last_pushed_epoch: Cell<u64>,
110}
111
112#[derive(Default)]
113struct State {
114 indexes: HashMap<String, Index>,
115 index_order: Vec<String>,
117 connections: Vec<Rc<Connection>>,
118 overlay: Option<Overlay>,
119 push_epoch: u64,
120}
121
122pub struct MemorySource {
124 me: Weak<MemorySource>,
125 table: Table,
126 primary_index_sort: Vec<OrderPart>,
127 primary_index_key: String,
128 state: RefCell<State>,
129}
130
131fn index_key(sort: &[OrderPart]) -> String {
132 let parts: Vec<Value> = sort
133 .iter()
134 .map(|p| {
135 Value::Array(vec![
136 Value::from(p.field.as_str()),
137 Value::from(p.direction.as_str()),
138 ])
139 })
140 .collect();
141 json::stringify(&Value::Array(parts))
142}
143
144impl MemorySource {
145 pub fn new(table: Table) -> Rc<Self> {
146 let primary_index_sort: Vec<OrderPart> = table
147 .primary_key
148 .iter()
149 .map(|k| OrderPart {
150 field: k.clone(),
151 direction: Direction::Asc,
152 })
153 .collect();
154 let primary_index_key = index_key(&primary_index_sort);
155 let mut state = State::default();
156 state.indexes.insert(
157 primary_index_key.clone(),
158 Index::new(primary_index_sort.clone(), Tree::new()),
159 );
160 state.index_order.push(primary_index_key.clone());
161 Rc::new_cyclic(|me| MemorySource {
162 me: me.clone(),
163 table,
164 primary_index_sort,
165 primary_index_key,
166 state: RefCell::new(state),
167 })
168 }
169
170 pub fn data(&self) -> Rc<Vec<Row>> {
172 Rc::new(self.primary_index().data.iter(None, false).collect())
173 }
174
175 pub fn is_empty(&self) -> bool {
177 self.primary_index().data.is_empty()
178 }
179
180 pub fn fork(&self) -> Rc<Self> {
183 let fork = MemorySource::new(self.table.clone());
184 let data = self.primary_index().data;
185 fork.state
186 .borrow_mut()
187 .indexes
188 .get_mut(&fork.primary_index_key)
189 .expect("primary index")
190 .data = data;
191 fork
192 }
193
194 pub fn has_connections(&self) -> bool {
196 !self.state.borrow().connections.is_empty()
197 }
198
199 pub fn contains(&self, row: &Row) -> bool {
201 self.primary_index().contains(row)
202 }
203
204 pub fn same_key(&self, a: &Row, b: &Row) -> bool {
206 (self.primary_index().compare)(a, b) == Ordering::Equal
207 }
208
209 pub fn index_keys(&self) -> Vec<String> {
211 self.state.borrow().index_order.clone()
212 }
213
214 fn primary_index(&self) -> Index {
215 self.state.borrow().indexes[&self.primary_index_key].clone()
216 }
217
218 fn disconnect(&self, connection: &Rc<Connection>) {
219 let mut state = self.state.borrow_mut();
220 let i = state
221 .connections
222 .iter()
223 .position(|c| Rc::ptr_eq(c, connection))
224 .expect("Connection not found");
225 state.connections.remove(i);
227 }
228
229 fn get_or_create_index(&self, sort: Vec<OrderPart>) -> Index {
230 let key = index_key(&sort);
231 let mut state = self.state.borrow_mut();
232 if let Some(index) = state.indexes.get(&key) {
233 return index.clone();
234 }
235 let mut index = Index::new(sort, Tree::new());
236 let mut rows: Vec<Row> = state.indexes[&self.primary_index_key]
237 .data
238 .iter(None, false)
239 .collect();
240 let compare = index.compare.clone();
241 rows.sort_by(|a, b| compare(a, b));
242 index.data = Tree::from_sorted(rows);
243 state.indexes.insert(key.clone(), index.clone());
244 state.index_order.push(key);
245 index
246 }
247
248 fn fetch(&self, req: FetchRequest, conn: Rc<Connection>) -> NodeStream {
249 let me = self.me.clone();
250 lazy(move || match me.upgrade() {
251 Some(source) => source.fetch_now(&req, &conn),
252 None => empty(),
253 })
254 }
255
256 fn fetch_now(&self, req: &FetchRequest, conn: &Rc<Connection>) -> NodeStream {
257 if let Some(multis) = &req.multi_constraints
258 && multis.iter().any(|m| !m.is_empty())
259 {
260 return self.fetch_multi(req, conn);
261 }
262 let primary_key = &self.table.primary_key;
263 let compare_rows = conn.compare_rows.clone();
264 let reverse = req.reverse;
265 let connection_comparator: Comparator = if reverse {
266 let c = compare_rows.clone();
267 Rc::new(move |a, b| c(b, a))
268 } else {
269 compare_rows.clone()
270 };
271
272 let conn_filter = conn.filters.as_ref().map(|(c, _)| c);
273 let merged_condition = match (conn_filter, &req.filter) {
274 (Some(c), Some(r)) => Some(Condition::And(vec![c.clone(), r.clone()])),
275 (c, r) => c.or(r.as_ref()).cloned(),
276 };
277 let merged_predicate =
278 merge_predicates(conn.filters.as_ref().map(|(_, p)| p.clone()), &req.filter);
279
280 let pk_constraint =
281 primary_key_constraint_from_filters(merged_condition.as_ref(), primary_key);
282 let fetch_or_pk = pk_constraint.as_ref().or(req.constraint.as_ref());
284
285 let mut index_sort: Vec<OrderPart> = fetch_or_pk
286 .map(|c| {
287 c.keys()
288 .into_iter()
289 .map(|k| OrderPart {
290 field: k.to_owned(),
291 direction: Direction::Asc,
292 })
293 .collect()
294 })
295 .unwrap_or_default();
296 if primary_key.len() > 1 || !fetch_or_pk.is_some_and(|c| c.matches_primary_key(primary_key))
299 {
300 index_sort.extend(conn.sort.iter().cloned());
301 }
302
303 let index = self.get_or_create_index(index_sort);
304 let index_compare = index.compare.clone();
305 let index_comparator: Comparator = if reverse {
306 let c = index_compare.clone();
307 Rc::new(move |a, b| c(b, a))
308 } else {
309 index_compare.clone()
310 };
311 let start_at = req.start.as_ref().map(|s| s.row.clone());
312
313 let rows = if let Some(constraint) = fetch_or_pk {
320 let mut scan_start: HashMap<String, Bound> = HashMap::new();
321 for part in &index.sort {
322 if scan_start.contains_key(&part.field) {
323 continue;
324 }
325 let asc = part.direction == Direction::Asc;
326 let b = if constraint.has(&part.field) {
327 Bound::Value(constraint.get(&part.field).cloned())
328 } else if asc != reverse {
329 Bound::Min
330 } else {
331 Bound::Max
332 };
333 scan_start.insert(part.field.clone(), b);
334 }
335 let probe = index.probe(scan_start);
336 index.data.iter(Some(&probe), reverse)
337 } else if let Some(start) = &start_at {
338 let c = index_compare.clone();
339 index.data.iter(Some(&|r: &Row| c(r, start)), reverse)
340 } else {
341 index.data.iter(None, reverse)
342 };
343
344 let (overlay, last_pushed) = {
345 let state = self.state.borrow();
346 (state.overlay.clone(), conn.last_pushed_epoch.get())
347 };
348 let overlay_active = overlay.as_ref().is_some_and(|o| last_pushed >= o.epoch);
349 if !overlay_active && req.start.is_none() && conn.filters.is_none() && req.filter.is_none()
351 {
352 let constraint = req.constraint.clone();
353 return Box::new(
354 rows.take_while(move |r| constraint.as_ref().is_none_or(|c| c.matches(r)))
355 .map(Node::new),
356 );
357 }
358
359 let rows: Stream<Row> = if pk_constraint.is_some() {
362 Box::new(rows.take(1))
363 } else {
364 Box::new(rows)
365 };
366 let overlay = overlay.filter(|o| last_pushed >= o.epoch);
367 let overlays = compute_overlays(
368 start_at.as_ref(),
369 req.constraint.as_ref(),
370 overlay.as_ref(),
371 &connection_comparator,
372 merged_predicate.as_ref(),
373 None,
374 );
375 let with_overlay = generate_with_overlay(rows, overlays, index_comparator);
376 let with_start =
377 generate_with_start(with_overlay, req.start.clone(), connection_comparator);
378 let with_constraint = generate_with_constraint(with_start, req.constraint.clone());
379 match merged_predicate {
380 Some(p) => Box::new(with_constraint.filter(move |n| p(&n.row))),
381 None => with_constraint,
382 }
383 }
384
385 fn fetch_multi(&self, req: &FetchRequest, conn: &Rc<Connection>) -> NodeStream {
386 let multis: Vec<Vec<Constraint>> = req
387 .multi_constraints
388 .iter()
389 .flatten()
390 .filter(|m| !m.is_empty())
391 .cloned()
392 .collect();
393 let (primary, rest) = multis.split_first().expect("a multi-constraint");
394 let rest = rest.to_vec();
395 let streams: Vec<NodeStream> = primary
396 .iter()
397 .map(|c| {
398 let mut sub = req.clone();
399 sub.constraint = Some(match &req.constraint {
400 Some(base) => base.merging(c),
401 None => c.clone(),
402 });
403 sub.multi_constraints = None;
404 self.fetch(sub, conn.clone())
405 })
406 .collect();
407 let compare_rows = conn.compare_rows.clone();
408 let reverse = req.reverse;
409 let merged = merge_sorted_streams(
410 streams,
411 Rc::new(move |a: &Node, b: &Node| {
412 if reverse {
413 compare_rows(&b.row, &a.row)
414 } else {
415 compare_rows(&a.row, &b.row)
416 }
417 }),
418 );
419 if rest.is_empty() {
420 return merged;
421 }
422 Box::new(merged.filter(move |n| rest.iter().all(|mc| mc.iter().any(|c| c.matches(&n.row)))))
423 }
424
425 pub fn push_adds(&self, rows: Vec<Row>) {
428 let can_bulk_load = {
429 let state = self.state.borrow();
430 state.connections.is_empty()
431 && state.indexes.len() == 1
432 && state.indexes[&self.primary_index_key].data.is_empty()
433 };
434 if !can_bulk_load {
435 for row in rows {
436 if has_failed() {
437 return;
438 }
439 self.push(SourceChange::Add(row));
440 }
441 return;
442 }
443 let mut state = self.state.borrow_mut();
444 let index = state
445 .indexes
446 .get_mut(&self.primary_index_key)
447 .expect("primary");
448 let compare = index.compare.clone();
449 let mut rows = rows;
450 rows.sort_by(|a, b| compare(a, b));
451 let mut deduped: Vec<Row> = Vec::with_capacity(rows.len());
453 for row in rows {
454 match deduped.last_mut() {
455 Some(last) if compare(last, &row) == Ordering::Equal => *last = row,
456 _ => deduped.push(row),
457 }
458 }
459 index.data = Tree::from_sorted(deduped);
460 }
461
462 fn gen_push_and_write_with_split_edit(&self, change: SourceChange) {
463 if let SourceChange::Edit { row, old_row } = &change {
464 let should_split = self.state.borrow().connections.iter().any(|conn| {
465 conn.split_edit_keys.as_ref().is_some_and(|keys| {
466 keys.iter()
467 .any(|k| !values_equal(row.get(k), old_row.get(k)))
468 })
469 });
470 if should_split {
471 let epoch = self.next_epoch();
472 self.gen_push_and_write(SourceChange::Remove(old_row.clone()), epoch);
473 if has_failed() {
474 return;
475 }
476 let epoch = self.next_epoch();
477 self.gen_push_and_write(SourceChange::Add(row.clone()), epoch);
478 return;
479 }
480 }
481 let epoch = self.next_epoch();
482 self.gen_push_and_write(change, epoch);
483 }
484
485 fn next_epoch(&self) -> u64 {
486 let mut state = self.state.borrow_mut();
487 state.push_epoch += 1;
488 state.push_epoch
489 }
490
491 fn gen_push_and_write(&self, change: SourceChange, epoch: u64) {
492 self.gen_push(&change, epoch);
493 if has_failed() {
495 return;
496 }
497 self.write_change(&change);
498 }
499
500 fn gen_push(&self, change: &SourceChange, epoch: u64) {
501 let primary = self.primary_index();
502 let check = match change {
503 SourceChange::Add(row) => (!primary.contains(row))
504 .then_some(())
505 .ok_or("Row already exists"),
506 SourceChange::Remove(row) | SourceChange::Edit { old_row: row, .. } => {
507 primary.contains(row).then_some(()).ok_or("Row not found")
508 }
509 };
510 if let Err(message) = check {
511 panic!("{message} {}", describe(change));
512 }
513
514 self.state.borrow_mut().overlay = Some(Overlay {
515 epoch,
516 change: change.clone(),
517 });
518 struct ClearOverlay<'a>(&'a RefCell<State>);
519 impl Drop for ClearOverlay<'_> {
520 fn drop(&mut self) {
521 self.0.borrow_mut().overlay = None;
522 }
523 }
524 let _clear = ClearOverlay(&self.state);
525
526 let mut i = 0;
529 loop {
530 let Some(conn) = self.state.borrow().connections.get(i).cloned() else {
531 break;
532 };
533 i += 1;
534 let output = conn.output.borrow().upgrade();
535 let input = conn.input.borrow().upgrade();
536 let (Some(output), Some(input)) = (output, input) else {
537 continue;
538 };
539 conn.last_pushed_epoch.set(epoch);
540 let output_change = match change {
541 SourceChange::Edit { row, old_row } => Change::Edit {
542 node: Node::new(row.clone()),
543 old_node: Node::new(old_row.clone()),
544 },
545 SourceChange::Add(row) => Change::Add(Node::new(row.clone())),
546 SourceChange::Remove(row) => Change::Remove(Node::new(row.clone())),
547 };
548 filter_push(
549 output_change,
550 output.as_ref(),
551 input.as_ref(),
552 conn.filters.as_ref().map(|(_, p)| p),
553 );
554 if has_failed() {
556 return;
557 }
558 }
559 let mut i = 0;
560 loop {
561 let Some(conn) = self.state.borrow().connections.get(i).cloned() else {
562 break;
563 };
564 i += 1;
565 let output = conn.output.borrow().upgrade();
566 let input = conn.input.borrow().upgrade();
567 if let (Some(output), Some(input)) = (output, input) {
568 output.reconcile(input.as_ref());
569 }
570 }
571 }
572
573 fn write_change(&self, change: &SourceChange) {
574 let mut state = self.state.borrow_mut();
575 let state = &mut *state;
576 for key in &state.index_order {
577 let index = state.indexes.get_mut(key).expect("index");
578 match change {
579 SourceChange::Add(row) => index.add(row.clone()),
580 SourceChange::Remove(row) => {
581 assert!(index.delete(row), "MemorySource: remove must succeed")
582 }
583 SourceChange::Edit { row, old_row } => {
584 assert!(
585 index.delete(old_row),
586 "MemorySource: edit remove must succeed"
587 );
588 index.add(row.clone());
589 }
590 }
591 }
592 }
593}
594
595fn describe(change: &SourceChange) -> String {
596 let s = |r: &Row| json::stringify(&Value::Object((**r).clone()));
597 match change {
598 SourceChange::Add(r) => format!("[0,{},null]", s(r)),
599 SourceChange::Remove(r) => format!("[1,{},null]", s(r)),
600 SourceChange::Edit { row, old_row } => format!("[2,{},{}]", s(row), s(old_row)),
601 }
602}
603
604impl Source for MemorySource {
605 fn table_schema(&self) -> &Table {
606 &self.table
607 }
608
609 fn connect(
610 &self,
611 sort: Option<Vec<OrderPart>>,
612 filters: Option<&Condition>,
613 split_edit_keys: Option<&HashSet<String>>,
614 ) -> Result<Rc<dyn SourceInput>, PipelineError> {
615 let (transformed, removed) = transform_filters(filters);
616 let unordered = sort.is_none();
617 let internal_sort = sort.unwrap_or_else(|| self.primary_index_sort.clone());
618 let conn_filters = match transformed {
619 Some(c) => {
620 let p = create_predicate(&c)?;
621 Some((c, p))
622 }
623 None => None,
624 };
625 if !unordered {
626 assert_ordering_includes_pk(&internal_sort, &self.table.primary_key)?;
627 }
628 let connection = Rc::new(Connection {
629 input: RefCell::new(Weak::new()),
630 output: RefCell::new(no_output()),
631 compare_rows: make_comparator(&internal_sort, false),
632 sort: internal_sort.clone(),
633 split_edit_keys: split_edit_keys.cloned(),
634 filters: conn_filters,
635 last_pushed_epoch: Cell::new(0),
636 });
637 let schema = Rc::new(SourceSchema {
638 table_name: self.table.name.clone(),
639 columns: self.table.columns.clone(),
640 primary_key: self.table.primary_key.clone(),
641 relationships: Vec::new(),
642 is_hidden: false,
643 system: crate::ast::System::Client,
644 compare_rows: connection.compare_rows.clone(),
645 sort: (!unordered).then_some(internal_sort),
646 });
647 let input = Rc::new(MemorySourceInput {
648 source: self.me.clone(),
649 connection: connection.clone(),
650 schema,
651 fully_applied_filters: !removed,
652 });
653 *connection.input.borrow_mut() = Rc::downgrade(&input);
654 self.state.borrow_mut().connections.push(connection);
655 Ok(input)
656 }
657
658 fn push(&self, change: SourceChange) {
659 self.gen_push_and_write_with_split_edit(change)
660 }
661}
662
663pub struct MemorySourceInput {
665 source: Weak<MemorySource>,
667 connection: Rc<Connection>,
668 schema: Rc<SourceSchema>,
669 fully_applied_filters: bool,
670}
671
672impl InputBase for MemorySourceInput {
673 fn get_schema(&self) -> Rc<SourceSchema> {
674 self.schema.clone()
675 }
676
677 fn destroy(&self) {
678 if let Some(source) = self.source.upgrade() {
679 source.disconnect(&self.connection);
680 }
681 }
682}
683
684impl Input for MemorySourceInput {
685 fn set_output(&self, output: Weak<dyn Output>) {
686 *self.connection.output.borrow_mut() = output;
687 }
688
689 fn fetch(&self, req: &FetchRequest) -> NodeStream {
690 match self.source.upgrade() {
691 Some(source) => source.fetch(req.clone(), self.connection.clone()),
692 None => empty(),
693 }
694 }
695}
696
697impl SourceInput for MemorySourceInput {
698 fn fully_applied_filters(&self) -> bool {
699 self.fully_applied_filters
700 }
701}
702
703pub fn assert_ordering_includes_pk(
705 ordering: &[OrderPart],
706 pk: &[String],
707) -> Result<(), PipelineError> {
708 let missing: Vec<&str> = pk
709 .iter()
710 .filter(|k| !ordering.iter().any(|p| &p.field == *k))
711 .map(String::as_str)
712 .collect();
713 if missing.is_empty() {
714 return Ok(());
715 }
716 Err(PipelineError::new(format!(
717 "Ordering must include all primary key fields. Missing: {}.",
718 missing.join(", ")
719 )))
720}
721
722fn merge_predicates(
723 conn: Option<RowPredicate>,
724 req_filter: &Option<Condition>,
725) -> Option<RowPredicate> {
726 let Some(req_filter) = req_filter else {
727 return conn;
728 };
729 let req: RowPredicate = create_predicate(req_filter).unwrap_or_else(|_| Rc::new(|_| false));
731 Some(match conn {
732 None => req,
733 Some(conn) => Rc::new(move |r| conn(r) && req(r)),
734 })
735}
736
737fn generate_with_constraint(nodes: NodeStream, constraint: Option<Constraint>) -> NodeStream {
738 match constraint {
739 None => nodes,
740 Some(c) => Box::new(nodes.take_while(move |n| c.matches(&n.row))),
741 }
742}
743
744fn generate_with_start(nodes: NodeStream, start: Option<Start>, compare: Comparator) -> NodeStream {
746 let Some(start) = start else {
747 return nodes;
748 };
749 let mut started = false;
750 Box::new(nodes.filter(move |n| {
751 if !started {
752 let c = compare(&n.row, &start.row);
753 started = match start.basis {
754 Basis::At => c != Ordering::Less,
755 Basis::After => c == Ordering::Greater,
756 };
757 }
758 started
759 }))
760}
761
762fn compute_overlays(
763 start_at: Option<&Row>,
764 constraint: Option<&Constraint>,
765 overlay: Option<&Overlay>,
766 start_at_compare: &Comparator,
767 filter: Option<&RowPredicate>,
768 multi_constraints: Option<&[Vec<Constraint>]>,
769) -> Overlays {
770 let mut o = match overlay.map(|o| &o.change) {
771 Some(SourceChange::Add(r)) => Overlays {
772 add: Some(r.clone()),
773 remove: None,
774 },
775 Some(SourceChange::Remove(r)) => Overlays {
776 add: None,
777 remove: Some(r.clone()),
778 },
779 Some(SourceChange::Edit { row, old_row }) => Overlays {
780 add: Some(row.clone()),
781 remove: Some(old_row.clone()),
782 },
783 None => Overlays::default(),
784 };
785 let keep = |o: &mut Overlays, f: &dyn Fn(&Row) -> bool| {
786 o.add = o.add.take().filter(|r| f(r));
787 o.remove = o.remove.take().filter(|r| f(r));
788 };
789 if let Some(start_at) = start_at {
790 keep(&mut o, &|r| start_at_compare(r, start_at) != Ordering::Less);
791 }
792 if let Some(c) = constraint {
793 keep(&mut o, &|r| c.matches(r));
794 }
795 for mc in multi_constraints.into_iter().flatten() {
796 if !mc.is_empty() {
797 keep(&mut o, &|r| mc.iter().any(|c| c.matches(r)));
798 }
799 }
800 if let Some(p) = filter {
801 keep(&mut o, &|r| p(r));
802 }
803 o
804}
805
806fn generate_with_overlay(rows: Stream<Row>, overlays: Overlays, compare: Comparator) -> NodeStream {
808 Box::new(OverlayIterator {
809 rows,
810 overlays,
811 compare,
812 add_yielded: false,
813 remove_skipped: false,
814 pending: None,
815 finished: false,
816 })
817}
818
819struct OverlayIterator {
820 rows: Stream<Row>,
821 overlays: Overlays,
822 compare: Comparator,
823 add_yielded: bool,
824 remove_skipped: bool,
825 pending: Option<Row>,
826 finished: bool,
827}
828
829impl Iterator for OverlayIterator {
830 type Item = Node;
831
832 fn next(&mut self) -> Option<Node> {
833 if let Some(p) = self.pending.take() {
834 return Some(Node::new(p));
835 }
836 if self.finished {
837 return None;
838 }
839 for row in self.rows.by_ref() {
840 let mut emit_add = None;
841 if !self.add_yielded
842 && let Some(add) = &self.overlays.add
843 && (self.compare)(add, &row) == Ordering::Less
844 {
845 self.add_yielded = true;
846 emit_add = Some(add.clone());
847 }
848 if !self.remove_skipped
849 && let Some(remove) = &self.overlays.remove
850 && (self.compare)(remove, &row) == Ordering::Equal
851 {
852 self.remove_skipped = true;
853 if let Some(add) = emit_add {
854 return Some(Node::new(add));
855 }
856 continue;
857 }
858 if let Some(add) = emit_add {
859 self.pending = Some(row);
860 return Some(Node::new(add));
861 }
862 return Some(Node::new(row));
863 }
864 self.finished = true;
865 if !self.add_yielded
866 && let Some(add) = &self.overlays.add
867 {
868 self.add_yielded = true;
869 return Some(Node::new(add.clone()));
870 }
871 None
872 }
873}
874
875pub type NodeComparator = Rc<dyn Fn(&Node, &Node) -> Ordering>;
877
878pub fn merge_sorted_streams(streams: Vec<NodeStream>, compare: NodeComparator) -> NodeStream {
883 lazy(move || {
884 let mut streams = streams;
885 let mut heads: Vec<Option<Node>> = streams.iter_mut().map(|s| s.next()).collect();
886 let mut refill: Option<usize> = None;
887 std::iter::from_fn(move || {
888 if let Some(i) = refill.take() {
889 heads[i] = streams[i].next();
890 }
891 let mut best: Option<usize> = None;
892 for (i, h) in heads.iter().enumerate() {
893 let Some(h) = h else { continue };
894 if best
895 .is_none_or(|b| compare(h, heads[b].as_ref().expect("head")) == Ordering::Less)
896 {
897 best = Some(i);
898 }
899 }
900 let i = best?;
901 refill = Some(i);
902 heads[i].take()
903 })
904 })
905}
906
907#[cfg(test)]
908mod tests {
909 use super::*;
910 use crate::json::Object;
911 use crate::map::OrderedMap;
912 use crate::schema::{Column, ValueType};
913
914 fn table() -> Table {
915 let col = |t| Column {
916 type_: t,
917 optional: false,
918 server_name: None,
919 };
920 let mut columns = OrderedMap::new();
921 columns.insert("id".to_owned(), col(ValueType::String));
922 columns.insert("n".to_owned(), col(ValueType::Number));
923 Table {
924 name: "t".to_owned(),
925 server_name: None,
926 columns,
927 primary_key: vec!["id".to_owned()],
928 }
929 }
930
931 fn row(id: &str, n: f64) -> Row {
932 let mut o = Object::new();
933 o.insert("id", Value::from(id));
934 o.insert("n", Value::Number(n));
935 Rc::new(o)
936 }
937
938 fn ids(s: NodeStream) -> Vec<String> {
939 s.map(|n| n.row.get("id").unwrap().as_str().unwrap().to_owned())
940 .collect()
941 }
942
943 fn sort(parts: &[(&str, Direction)]) -> Option<Vec<OrderPart>> {
944 Some(
945 parts
946 .iter()
947 .map(|(f, d)| OrderPart {
948 field: (*f).to_owned(),
949 direction: *d,
950 })
951 .collect(),
952 )
953 }
954
955 #[test]
956 fn fetches_in_order_with_constraints_and_starts() {
957 let source = MemorySource::new(table());
958 source.push_adds(vec![row("c", 1.0), row("a", 2.0), row("b", 1.0)]);
959 let input = source
960 .connect(
961 sort(&[("n", Direction::Asc), ("id", Direction::Desc)]),
962 None,
963 None,
964 )
965 .unwrap();
966 assert_eq!(ids(input.fetch(&FetchRequest::default())), ["c", "b", "a"]);
967 let reverse = FetchRequest {
968 reverse: true,
969 ..FetchRequest::default()
970 };
971 assert_eq!(ids(input.fetch(&reverse)), ["a", "b", "c"]);
972 let constrained = FetchRequest {
973 constraint: Some(Constraint::new(vec![(
974 "n".to_owned(),
975 Some(Value::Number(1.0)),
976 )])),
977 ..FetchRequest::default()
978 };
979 assert_eq!(ids(input.fetch(&constrained)), ["c", "b"]);
980 let after_c = FetchRequest {
981 start: Some(Start {
982 row: row("c", 1.0),
983 basis: Basis::After,
984 }),
985 ..FetchRequest::default()
986 };
987 assert_eq!(ids(input.fetch(&after_c)), ["b", "a"]);
988 assert!(
989 source
990 .connect(sort(&[("n", Direction::Asc)]), None, None)
991 .is_err()
992 );
993 }
994
995 #[test]
998 fn a_push_is_visible_to_fetches_it_triggers() {
999 let source = MemorySource::new(table());
1000 source.push_adds(vec![row("a", 1.0), row("c", 1.0)]);
1001 let input = source
1002 .connect(sort(&[("id", Direction::Asc)]), None, None)
1003 .unwrap();
1004 let seen: Rc<RefCell<Vec<Vec<String>>>> = Rc::default();
1005 let (i, s) = (Rc::downgrade(&input), seen.clone());
1006 let output = ClosureOutput::new(
1007 move |_| {
1008 let input = i.upgrade().unwrap();
1009 s.borrow_mut()
1010 .push(ids(input.fetch(&FetchRequest::default())));
1011 },
1012 || {},
1013 );
1014 input.set_output(Rc::downgrade(&output) as Weak<dyn Output>);
1015 source.push(SourceChange::Add(row("b", 1.0)));
1016 source.push(SourceChange::Edit {
1017 row: row("a", 5.0),
1018 old_row: row("a", 1.0),
1019 });
1020 source.push(SourceChange::Remove(row("c", 1.0)));
1021 assert_eq!(
1022 *seen.borrow(),
1023 [vec!["a", "b", "c"], vec!["a", "b", "c"], vec!["a", "b"]]
1024 );
1025 assert_eq!(ids(input.fetch(&FetchRequest::default())), ["a", "b"]);
1026 assert_eq!(source.data()[0].get("n"), Some(&Value::Number(5.0)));
1027 }
1028}