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 sorted `Vec` behind an `Rc`. A fetch holds the `Rc` it
5//! started with, and a write copies the `Vec` if a fetch still holds it, so
6//! a fetch in progress keeps reading the rows it started with, as Swift's
7//! copy-on-write B-tree does.
8
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: 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    /// Adds `row`, replacing an equal one.
52    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    /// Removes the row equal to `row`; whether there was one.
60    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    /// `probe` for a scan starting at `bound`: the ordering of a row against
71    /// the bound.
72    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/// A bound in an index scan: a value, or below or above every value.
94#[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 keys in the order they were made: the order writes go in.
125    index_order: Vec<String>,
126    connections: Vec<Rc<Connection>>,
127    overlay: Option<Overlay>,
128    push_epoch: u64,
129}
130
131/// A table's rows in memory.
132pub 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    /// The rows, in primary key order.
180    pub fn data(&self) -> Rc<Vec<Row>> {
181        self.primary_index().data
182    }
183
184    /// A source with the same rows that shares them until either is written
185    /// (`fork`). It has no connections and only the primary index.
186    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    /// Whether a pipeline reads the source.
199    pub fn has_connections(&self) -> bool {
200        !self.state.borrow().connections.is_empty()
201    }
202
203    /// Whether the source has a row with `row`'s primary key.
204    pub fn contains(&self, row: &Row) -> bool {
205        self.primary_index().search(row).is_ok()
206    }
207
208    /// Whether `a` and `b` have the same primary key.
209    pub fn same_key(&self, a: &Row, b: &Row) -> bool {
210        (self.primary_index().compare)(a, b) == Ordering::Equal
211    }
212
213    /// For tests: the keys of the indexes built so far.
214    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        // Indexes are kept for the life of the source (see the JS comment).
230        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        // The primary key constraint is more limiting than the constraint.
284        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        // Constraining by the whole primary key yields one row, so the
298        // requested sort does not matter.
299        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        // Start a constrained scan at the first row with the constraint's
315        // values, whatever the direction of the following sort parts. A
316        // column the sort names twice keeps its first bound: the comparator
317        // decides on that part, and a later part for the column only sees
318        // equal values. (JS takes the last, so a sort like
319        // `text desc, text asc` starts past every match.)
320        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        // Fast path: no overlay, no start, and no filters.
359        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        // `req.constraint` and not the primary key constraint, which comes
369        // from the filters and acts as one.
370        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    /// Pushes an add for each of `rows`. When nothing is connected and the
435    /// source is empty, builds the primary index in one pass instead.
436    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        // Equal rows: the last wins, as `add` replaces.
461        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        // JS's throw skips the write.
503        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        // Index-based, like iterating the live JS array: a pipeline can
540        // disconnect while a push is in flight.
541        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            // JS's throw ends the push here, before the other connections.
568            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
676/// A pipeline's connection to a [`MemorySource`].
677pub struct MemorySourceInput {
678    /// Weak: a view can outlive the client and its sources.
679    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
716/// The first index of a scan from `probe`: forward, the first row not
717/// before it; in reverse, the last row not after it (-1 for none).
718fn 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
726/// An index's rows from a position, ascending or descending.
727struct 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
746/// `assertOrderingIncludesPK`.
747pub 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    // FilterStart's conditions were checked when the pipeline was built.
773    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
787/// `generateWithStart`: skips rows before `start`.
788fn 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
849/// `generateWithOverlayInner`: splices the in-flight push into `rows`.
850fn 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
918/// Orders nodes.
919pub type NodeComparator = Rc<dyn Fn(&Node, &Node) -> Ordering>;
920
921/// `mergeSortedStreams`: an N-way merge of streams sorted by `compare`. The
922/// stream of the node emitted last is pulled again only when the next node
923/// is asked for, as the JS generator does on resume. Ties go to the earlier
924/// stream.
925pub 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    /// An output that fetches back through the source while a push is in
1039    /// flight sees the pushed row, as it will be once written.
1040    #[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}