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