Skip to main content

zero_client/ivm/
memory_source.rs

1//! A source of rows held in memory, kept in sorted order
2//! (`packages/zql/src/ivm/memory-source.ts`).
3//!
4//! Each index is a persistent B+ tree (`btree.rs`), as in Swift. A fork
5//! shares the tree, a write copies only the nodes on its path, and a fetch
6//! in progress keeps reading the rows it started with.
7
8use 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    /// Adds `row`, replacing an equal one.
52    fn add(&mut self, row: Row) {
53        self.data.add(row, &*self.compare);
54    }
55
56    /// Removes the row equal to `row`; whether there was one.
57    fn delete(&mut self, row: &Row) -> bool {
58        self.data.delete(row, &*self.compare)
59    }
60
61    /// `probe` for a scan starting at `bound`: the ordering of a row against
62    /// the bound.
63    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/// A bound in an index scan: a value, or below or above every value.
85#[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 keys in the order they were made: the order writes go in.
116    index_order: Vec<String>,
117    connections: Vec<Rc<Connection>>,
118    overlay: Option<Overlay>,
119    push_epoch: u64,
120}
121
122/// A table's rows in memory.
123pub 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    /// The rows, in primary key order.
171    pub fn data(&self) -> Rc<Vec<Row>> {
172        Rc::new(self.primary_index().data.iter(None, false).collect())
173    }
174
175    /// Whether the source has no rows.
176    pub fn is_empty(&self) -> bool {
177        self.primary_index().data.is_empty()
178    }
179
180    /// A source with the same rows that shares them until either is written
181    /// (`fork`). It has no connections and only the primary index.
182    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    /// Whether a pipeline reads the source.
195    pub fn has_connections(&self) -> bool {
196        !self.state.borrow().connections.is_empty()
197    }
198
199    /// Whether the source has a row with `row`'s primary key.
200    pub fn contains(&self, row: &Row) -> bool {
201        self.primary_index().contains(row)
202    }
203
204    /// Whether `a` and `b` have the same primary key.
205    pub fn same_key(&self, a: &Row, b: &Row) -> bool {
206        (self.primary_index().compare)(a, b) == Ordering::Equal
207    }
208
209    /// For tests: the keys of the indexes built so far.
210    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        // Indexes are kept for the life of the source (see the JS comment).
226        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        // The primary key constraint is more limiting than the constraint.
283        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        // Constraining by the whole primary key yields one row, so the
297        // requested sort does not matter.
298        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        // Start a constrained scan at the first row with the constraint's
314        // values, whatever the direction of the following sort parts. A
315        // column the sort names twice keeps its first bound: the comparator
316        // decides on that part, and a later part for the column only sees
317        // equal values. (JS takes the last, so a sort like
318        // `text desc, text asc` starts past every match.)
319        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        // Fast path: no overlay, no start, and no filters.
350        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        // `req.constraint` and not the primary key constraint, which comes
360        // from the filters and acts as one.
361        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    /// Pushes an add for each of `rows`. When nothing is connected and the
426    /// source is empty, builds the primary index in one pass instead.
427    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        // Equal rows: the last wins, as `add` replaces.
452        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        // JS's throw skips the write.
494        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        // Index-based, like iterating the live JS array: a pipeline can
527        // disconnect while a push is in flight.
528        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            // JS's throw ends the push here, before the other connections.
555            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
663/// A pipeline's connection to a [`MemorySource`].
664pub struct MemorySourceInput {
665    /// Weak: a view can outlive the client and its sources.
666    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
703/// `assertOrderingIncludesPK`.
704pub 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    // FilterStart's conditions were checked when the pipeline was built.
730    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
744/// `generateWithStart`: skips rows before `start`.
745fn 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
806/// `generateWithOverlayInner`: splices the in-flight push into `rows`.
807fn 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
875/// Orders nodes.
876pub type NodeComparator = Rc<dyn Fn(&Node, &Node) -> Ordering>;
877
878/// `mergeSortedStreams`: an N-way merge of streams sorted by `compare`. The
879/// stream of the node emitted last is pulled again only when the next node
880/// is asked for, as the JS generator does on resume. Ties go to the earlier
881/// stream.
882pub 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    /// An output that fetches back through the source while a push is in
996    /// flight sees the pushed row, as it will be once written.
997    #[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}