Skip to main content

zero_client/ivm/
view.rs

1//! Materialized views: the entries a view holds, how changes apply to them
2//! (`packages/zql/src/ivm/view-apply-change.ts`), and `ArrayView`
3//! (`array-view.ts`).
4
5use super::*;
6use crate::ast::{Aggregate as AggregateSpec, AggregateFunction};
7use crate::format::Format;
8use crate::json::{Object, Value};
9use crate::keys::aggregate_columns as cols;
10use crate::protocol::ErroredQuery;
11use crate::strings;
12use std::cell::{Cell, RefCell};
13use std::cmp::Ordering;
14use std::rc::{Rc, Weak};
15
16/// A row in a materialized view, with the relationships the query asked
17/// for (`Entry` in `view.ts`).
18#[derive(Clone, Debug)]
19pub struct ViewEntry {
20    pub row: Row,
21    /// By name, in UTF-16 code unit order.
22    pub relationships: Vec<(String, ViewValue)>,
23    /// How many edges of the relationship reach this row.
24    ref_count: usize,
25}
26
27impl PartialEq for ViewEntry {
28    /// Equal rows with equal relationships. How many edges reach the row
29    /// doesn't matter.
30    fn eq(&self, other: &Self) -> bool {
31        self.row == other.row && self.relationships == other.relationships
32    }
33}
34
35impl ViewEntry {
36    fn new(row: Row) -> Self {
37        ViewEntry {
38            row,
39            relationships: Vec::new(),
40            ref_count: 1,
41        }
42    }
43
44    pub fn relationship(&self, name: &str) -> Option<&ViewValue> {
45        self.position(name).ok().map(|i| &self.relationships[i].1)
46    }
47
48    fn position(&self, name: &str) -> Result<usize, usize> {
49        self.relationships
50            .binary_search_by(|(k, _)| strings::utf16(k, name))
51    }
52
53    fn relationship_mut(&mut self, name: &str) -> Option<&mut ViewValue> {
54        self.position(name)
55            .ok()
56            .map(|i| &mut self.relationships[i].1)
57    }
58
59    fn set(&mut self, name: &str, value: ViewValue) {
60        match self.position(name) {
61            Ok(i) => self.relationships[i].1 = value,
62            Err(i) => self.relationships.insert(i, (name.to_owned(), value)),
63        }
64    }
65
66    /// The row with its relationships, as JS views present it: the
67    /// relationships after the row's columns, by name.
68    pub fn to_json(&self) -> Value {
69        let mut o: Object = (*self.row).clone();
70        for (name, value) in &self.relationships {
71            match value.to_json() {
72                Some(v) => {
73                    o.insert(name.clone(), v);
74                }
75                None => {
76                    o.remove(name);
77                }
78            }
79        }
80        Value::Object(o)
81    }
82}
83
84/// A relationship in a view: several rows, at most one, or an aggregate's
85/// value.
86#[derive(Clone, Debug, PartialEq)]
87pub enum ViewValue {
88    /// Shared with earlier snapshots until changed.
89    Many(Rc<Vec<ViewEntry>>),
90    One(Option<Box<ViewEntry>>),
91    /// The value of an aggregate (`count()`, `sum(...)`, …): a number, or
92    /// `null` for an empty `sum`, `avg`, `min` or `max`.
93    Value(Value),
94}
95
96impl ViewValue {
97    /// The value of an aggregate over no rows, as in SQL: `count` is 0, the
98    /// rest null (`emptyViewValue`).
99    pub fn empty(format: &Format) -> ViewValue {
100        if let Some(a) = &format.aggregate {
101            return ViewValue::Value(empty_aggregate_value(a));
102        }
103        if format.singular {
104            ViewValue::One(None)
105        } else {
106            ViewValue::Many(Rc::default())
107        }
108    }
109
110    /// The value as JS views present it; `None` for a missing singular row.
111    pub fn to_json(&self) -> Option<Value> {
112        match self {
113            ViewValue::Many(entries) => Some(Value::Array(
114                entries.iter().map(ViewEntry::to_json).collect(),
115            )),
116            ViewValue::One(entry) => entry.as_ref().map(|e| e.to_json()),
117            ViewValue::Value(v) => Some(v.clone()),
118        }
119    }
120
121    /// The rows; none for an aggregate's value.
122    pub fn entries(&self) -> Vec<&ViewEntry> {
123        match self {
124            ViewValue::Many(e) => e.iter().collect(),
125            ViewValue::One(e) => e.iter().map(|e| e.as_ref()).collect(),
126            ViewValue::Value(_) => Vec::new(),
127        }
128    }
129}
130
131/// `emptyAggregateValue`.
132pub fn empty_aggregate_value(aggregate: &AggregateSpec) -> Value {
133    if aggregate.fn_ == AggregateFunction::Count {
134        Value::Number(0.0)
135    } else {
136        Value::Null
137    }
138}
139
140fn child_format<'a>(format: &'a Format, name: &str) -> Option<&'a Format> {
141    format
142        .relationships
143        .iter()
144        .find(|(k, _)| k == name)
145        .map(|(_, f)| f)
146}
147
148fn child_schema<'a>(schema: &'a SourceSchema, name: &str) -> &'a SourceSchema {
149    schema
150        .relationship(name)
151        .unwrap_or_else(|| panic!("missing relationship schema {name}"))
152}
153
154/// Reports what JS asserts here (the view and its input disagree) and
155/// leaves the tree as it was: the push or hydration then fails.
156fn fail(message: &str) -> bool {
157    report(message);
158    false
159}
160
161fn list_mut<'a>(parent: &'a mut ViewEntry, relationship: &str) -> &'a mut Vec<ViewEntry> {
162    match parent.relationship_mut(relationship) {
163        Some(ViewValue::Many(list)) => Rc::make_mut(list),
164        _ => panic!("expected relationship array"),
165    }
166}
167
168fn singular_mut<'a>(parent: &'a mut ViewEntry, relationship: &str) -> Option<&'a mut ViewEntry> {
169    match parent.relationship_mut(relationship) {
170        Some(ViewValue::One(Some(entry))) => Some(entry),
171        _ => None,
172    }
173}
174
175/// `{...existing, ...row}`.
176fn apply_edit(entry: &mut ViewEntry, row: &Row) {
177    let existing = Rc::make_mut(&mut entry.row);
178    for (k, v) in row.iter() {
179        existing.insert(k.clone(), v.clone());
180    }
181}
182
183/// The index of `target`, or its insertion point. Probes the end first:
184/// hydration appends in order.
185fn search(view: &[ViewEntry], target: &Row, comparator: &Comparator) -> Result<usize, usize> {
186    let Some(last) = view.last() else {
187        return Err(0);
188    };
189    match comparator(&last.row, target) {
190        Ordering::Less => return Err(view.len()),
191        Ordering::Equal => return Ok(view.len() - 1),
192        Ordering::Greater => {}
193    }
194    view[..view.len() - 1].binary_search_by(|e| comparator(&e.row, target))
195}
196
197/// A new entry for `node`, with its relationships filled in.
198fn new_entry(node: &Node, schema: &SourceSchema, format: &Format) -> ViewEntry {
199    let mut entry = ViewEntry::new(node.row.clone());
200    initialize_relationships(&mut entry, node, schema, format);
201    entry
202}
203
204/// Fills in a new entry's relationships from its node.
205fn initialize_relationships(
206    entry: &mut ViewEntry,
207    node: &Node,
208    schema: &SourceSchema,
209    format: &Format,
210) {
211    for (name, stream) in node.relationships.iter() {
212        let child_schema = child_schema(schema, name);
213        let Some(child_format) = child_format(format, name) else {
214            continue;
215        };
216        if child_schema.is_hidden || child_format.singular {
217            // An aggregate starts at its empty value: a parent whose
218            // correlation value is null gets no row from the Join, but SQL
219            // still gives it 0 or null.
220            entry.set(name, ViewValue::empty(child_format));
221            for child in stream() {
222                apply(entry, &Change::Add(child), child_schema, name, child_format);
223            }
224        } else {
225            let mut list: Vec<ViewEntry> = Vec::new();
226            for child in stream() {
227                match search(&list, &child.row, &child_schema.compare_rows) {
228                    Ok(pos) => list[pos].ref_count += 1,
229                    Err(pos) => list.insert(pos, new_entry(&child, child_schema, child_format)),
230                }
231            }
232            entry.set(name, ViewValue::Many(Rc::new(list)));
233        }
234    }
235}
236
237/// Applies `change` to `parent`'s `relationship`. Returns whether the tree
238/// changed (JS returns the same entry when it did not).
239pub fn apply(
240    parent: &mut ViewEntry,
241    change: &Change,
242    schema: &SourceSchema,
243    relationship: &str,
244    format: &Format,
245) -> bool {
246    if schema.is_hidden {
247        return match change {
248            Change::Add(node) | Change::Remove(node) => {
249                let is_add = change.change_type() == ChangeType::Add;
250                let mut changed = false;
251                for (name, stream) in node.relationships.iter() {
252                    let child_schema = child_schema(schema, name);
253                    for child in stream() {
254                        let c = if is_add {
255                            Change::Add(child)
256                        } else {
257                            Change::Remove(child)
258                        };
259                        changed = apply(parent, &c, child_schema, name, format) || changed;
260                    }
261                }
262                changed
263            }
264            // A hidden row changed; a change to its relationships would have
265            // been split into a remove and an add.
266            Change::Edit { .. } => false,
267            Change::Child(_, child) => apply(
268                parent,
269                &child.change,
270                child_schema(schema, &child.relationship_name),
271                relationship,
272                format,
273            ),
274        };
275    }
276
277    // An aggregate relationship shows the bare value rather than its row:
278    // an add or edit sets it, a remove resets it to the empty value.
279    if let Some(aggregate) = &format.aggregate {
280        let value = match change {
281            Change::Add(node) | Change::Edit { node, .. } => {
282                node.row.get(cols::VALUE).cloned().unwrap_or(Value::Null)
283            }
284            Change::Remove(_) => empty_aggregate_value(aggregate),
285            Change::Child(..) => return false,
286        };
287        parent.set(relationship, ViewValue::Value(value));
288        return true;
289    }
290
291    let compare = &schema.compare_rows;
292    match change {
293        Change::Add(node) => {
294            if format.singular {
295                if let Some(old) = singular_mut(parent, relationship) {
296                    // Server data can do this, with two rows for a `one`
297                    // relationship.
298                    if compare(&old.row, &node.row) != Ordering::Equal {
299                        return fail(&format!(
300                            "Singular relationship '{relationship}' should not have multiple rows. You may need to declare this relationship with the `many` helper instead of the `one` helper in your schema."
301                        ));
302                    }
303                    old.ref_count += 1;
304                } else {
305                    let entry = new_entry(node, schema, format);
306                    parent.set(relationship, ViewValue::One(Some(Box::new(entry))));
307                }
308            } else {
309                let list = list_mut(parent, relationship);
310                match search(list, &node.row, compare) {
311                    Ok(pos) => list[pos].ref_count += 1,
312                    Err(pos) => list.insert(pos, new_entry(node, schema, format)),
313                }
314            }
315            true
316        }
317
318        Change::Remove(node) => {
319            if format.singular {
320                let Some(old) = singular_mut(parent, relationship) else {
321                    return fail("node does not exist");
322                };
323                if old.ref_count == 1 {
324                    parent.set(relationship, ViewValue::One(None));
325                } else {
326                    old.ref_count -= 1;
327                }
328            } else {
329                let list = list_mut(parent, relationship);
330                let Ok(pos) = search(list, &node.row, compare) else {
331                    return fail("node does not exist");
332                };
333                if list[pos].ref_count == 1 {
334                    list.remove(pos);
335                } else {
336                    list[pos].ref_count -= 1;
337                }
338            }
339            true
340        }
341
342        Change::Child(node, child) => {
343            let name = child.relationship_name.as_str();
344            let child_schema = child_schema(schema, name);
345            let Some(child_format) = child_format(format, name) else {
346                return false; // not in the view
347            };
348            if format.singular {
349                let Some(existing) = singular_mut(parent, relationship) else {
350                    return fail("node does not exist");
351                };
352                return apply(existing, &child.change, child_schema, name, child_format);
353            }
354            let list = list_mut(parent, relationship);
355            let Ok(pos) = search(list, &node.row, compare) else {
356                return fail("node does not exist");
357            };
358            apply(
359                &mut list[pos],
360                &child.change,
361                child_schema,
362                name,
363                child_format,
364            )
365        }
366
367        Change::Edit { node, old_node } => {
368            if format.singular {
369                let Some(existing) = singular_mut(parent, relationship) else {
370                    return fail("node does not exist");
371                };
372                apply_edit(existing, &node.row);
373                return true;
374            }
375            let list = list_mut(parent, relationship);
376            if compare(&old_node.row, &node.row) == Ordering::Equal {
377                let Ok(pos) = search(list, &old_node.row, compare) else {
378                    return fail("node does not exist");
379                };
380                apply_edit(&mut list[pos], &node.row);
381                return true;
382            }
383            // The sort key changed, so the row may move.
384            let Ok(old_pos) = search(list, &old_node.row, compare) else {
385                return fail("old node does not exist");
386            };
387            let raw = search(list, &node.row, compare);
388            let (found, pos) = match raw {
389                Ok(p) => (true, p),
390                Err(p) => (false, p),
391            };
392            // With one reference, a row landing where it was is only edited.
393            if list[old_pos].ref_count == 1 && (pos == old_pos || pos == old_pos + 1) {
394                apply_edit(&mut list[old_pos], &node.row);
395                return true;
396            }
397            // Move the row. With several references an edit arrives for
398            // each: a copy stays behind until the last one moves.
399            let old_entry = list[old_pos].clone();
400            let new_ref_count = old_entry.ref_count - 1;
401            let mut adjusted = pos;
402            if new_ref_count == 0 {
403                list.remove(old_pos);
404                if old_pos < pos {
405                    adjusted = pos - 1;
406                }
407            } else {
408                list[old_pos].ref_count = new_ref_count;
409            }
410            if found {
411                let rc = list[adjusted].ref_count;
412                apply_edit(&mut list[adjusted], &node.row);
413                list[adjusted].ref_count = rc + 1;
414            } else {
415                let mut moved = old_entry;
416                apply_edit(&mut moved, &node.row);
417                moved.ref_count = 1;
418                list.insert(adjusted, moved);
419            }
420            true
421        }
422    }
423}
424
425/// Applies an add for each node.
426fn add_all(
427    parent: &mut ViewEntry,
428    nodes: impl Iterator<Item = Node>,
429    schema: &SourceSchema,
430    relationship: &str,
431    format: &Format,
432) {
433    if schema.is_hidden || format.singular {
434        for node in nodes {
435            apply(parent, &Change::Add(node), schema, relationship, format);
436        }
437        return;
438    }
439    let list = list_mut(parent, relationship);
440    for node in nodes {
441        match search(list, &node.row, &schema.compare_rows) {
442            Ok(pos) => list[pos].ref_count += 1,
443            Err(pos) => list.insert(pos, new_entry(&node, schema, format)),
444        }
445    }
446}
447
448/// The result type of a view (`ResultType` in `typed-view.ts`).
449#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
450pub enum ResultType {
451    Unknown,
452    Cached,
453    Complete,
454    Error,
455}
456
457impl ResultType {
458    pub fn as_str(self) -> &'static str {
459        match self {
460            ResultType::Unknown => "unknown",
461            ResultType::Cached => "cached",
462            ResultType::Complete => "complete",
463            ResultType::Error => "error",
464        }
465    }
466}
467
468/// Called with a view's data and result type.
469pub type Listener = Rc<dyn Fn(&ViewValue, ResultType)>;
470
471struct ViewState {
472    root: ViewEntry,
473    dirty: bool,
474    committed_root: Option<ViewEntry>,
475    held: bool,
476    held_result_type: ResultType,
477    held_error: Option<ErroredQuery>,
478    result_type: ResultType,
479    error: Option<ErroredQuery>,
480}
481
482/// A materialized view of a pipeline's output (`array-view.ts`).
483///
484/// Listeners are notified on [`flush`](Self::flush), which the engine
485/// calls when a transaction commits.
486pub struct ArrayView {
487    input: Rc<dyn Input>,
488    format: Format,
489    schema: Rc<SourceSchema>,
490    state: RefCell<ViewState>,
491    listeners: Rc<RefCell<Vec<(u64, Listener)>>>,
492    next_listener_id: Cell<u64>,
493    on_destroy: RefCell<Option<Box<dyn Fn()>>>,
494}
495
496impl ArrayView {
497    /// Hydrates from `input`, starting as failed when `error` is set.
498    /// `complete` marks the result complete from the start.
499    pub fn new(
500        input: Rc<dyn Input>,
501        format: Format,
502        error: Option<ErroredQuery>,
503        complete: bool,
504    ) -> Rc<Self> {
505        let mut root = ViewEntry::new(Rc::new(Object::new()));
506        root.set("", ViewValue::empty(&format));
507        let result_type = if complete {
508            ResultType::Complete
509        } else if error.is_some() {
510            ResultType::Error
511        } else {
512            ResultType::Unknown
513        };
514        let error = if complete { None } else { error };
515        let view = Rc::new(ArrayView {
516            schema: input.get_schema(),
517            input: input.clone(),
518            format,
519            state: RefCell::new(ViewState {
520                root,
521                dirty: false,
522                committed_root: None,
523                held: false,
524                held_result_type: ResultType::Unknown,
525                held_error: None,
526                result_type,
527                error,
528            }),
529            listeners: Rc::default(),
530            next_listener_id: Cell::new(0),
531            on_destroy: RefCell::new(None),
532        });
533        input.set_output(Rc::downgrade(&view) as Weak<dyn Output>);
534        view.hydrate();
535        view
536    }
537
538    pub fn format(&self) -> &Format {
539        &self.format
540    }
541
542    /// The schema of the rows.
543    pub fn schema(&self) -> &SourceSchema {
544        &self.schema
545    }
546
547    /// The current rows.
548    pub fn data(&self) -> ViewValue {
549        let state = self.state.borrow();
550        let root = state.committed_root.as_ref().unwrap_or(&state.root);
551        root.relationship("").expect("view root").clone()
552    }
553
554    pub fn result_type(&self) -> ResultType {
555        self.state.borrow().result_type
556    }
557
558    /// Why the query failed, when the result type is `Error`.
559    pub fn error(&self) -> Option<ErroredQuery> {
560        self.state.borrow().error.clone()
561    }
562
563    pub fn set_on_destroy(&self, f: impl Fn() + 'static) {
564        *self.on_destroy.borrow_mut() = Some(Box::new(f));
565    }
566
567    /// Adds a listener, calls it with the current data, and returns a
568    /// function that removes it.
569    pub fn add_listener(
570        &self,
571        listener: impl Fn(&ViewValue, ResultType) + 'static,
572    ) -> Box<dyn Fn()> {
573        let id = self.next_listener_id.get();
574        self.next_listener_id.set(id + 1);
575        let listener: Listener = Rc::new(listener);
576        self.listeners.borrow_mut().push((id, listener.clone()));
577        let (data, ty) = self.listener_args();
578        listener(&data, ty);
579        let listeners = Rc::downgrade(&self.listeners);
580        Box::new(move || {
581            if let Some(l) = listeners.upgrade() {
582                l.borrow_mut().retain(|(i, _)| *i != id);
583            }
584        })
585    }
586
587    fn listener_args(&self) -> (ViewValue, ResultType) {
588        let ty = {
589            let s = self.state.borrow();
590            if s.committed_root.is_some() {
591                s.held_result_type
592            } else {
593                s.result_type
594            }
595        };
596        (self.data(), ty)
597    }
598
599    /// Calls each listener, reading the set again after every call, as JS
600    /// iterates a `Set` that changes while it is iterated: one removed
601    /// before its turn is skipped, one added is called in the same pass.
602    fn fire_listeners(&self) {
603        let (data, ty) = self.listener_args();
604        let mut last: Option<u64> = None;
605        loop {
606            let next = self
607                .listeners
608                .borrow()
609                .iter()
610                .find(|(id, _)| last.is_none_or(|l| *id > l))
611                .cloned();
612            let Some((id, listener)) = next else {
613                break;
614            };
615            last = Some(id);
616            listener(&data, ty);
617        }
618    }
619
620    pub fn destroy(&self) {
621        let f = self.on_destroy.borrow_mut().take();
622        if let Some(f) = f {
623            f();
624        }
625    }
626
627    fn hydrate(&self) {
628        let nodes = self.input.fetch(&FetchRequest::default());
629        {
630            let mut s = self.state.borrow_mut();
631            s.dirty = true;
632            add_all(&mut s.root, nodes, &self.schema, "", &self.format);
633        }
634        self.flush();
635    }
636
637    /// Keeps exposing the current snapshot until `release_data` or the next
638    /// `flush`.
639    pub fn hold_data(&self) {
640        let mut s = self.state.borrow_mut();
641        s.committed_root = Some(s.root.clone());
642        s.held = true;
643        s.held_result_type = s.result_type;
644        s.held_error = s.error.clone();
645    }
646
647    /// The result type and error listeners are told about now.
648    pub fn listener_result_type(&self) -> (ResultType, Option<ErroredQuery>) {
649        let s = self.state.borrow();
650        if s.committed_root.is_some() {
651            (s.held_result_type, s.held_error.clone())
652        } else {
653            (s.result_type, s.error.clone())
654        }
655    }
656
657    pub fn release_data(&self) {
658        self.state.borrow_mut().committed_root = None;
659    }
660
661    /// Notifies listeners if the view changed since the last flush.
662    pub fn flush(&self) {
663        {
664            let mut s = self.state.borrow_mut();
665            s.committed_root = None;
666            s.held = false;
667            if !s.dirty {
668                return;
669            }
670            s.dirty = false;
671        }
672        self.fire_listeners();
673    }
674
675    pub fn set_result_type(&self, ty: ResultType, error: Option<ErroredQuery>) {
676        let fire = {
677            let mut s = self.state.borrow_mut();
678            s.result_type = ty;
679            s.error = error;
680            if s.held {
681                s.dirty = true;
682                false
683            } else {
684                !s.dirty
685            }
686        };
687        if fire {
688            self.fire_listeners();
689        }
690    }
691
692    /// The server-confirmed result of an earlier sync is in the store.
693    pub fn mark_cached(&self) {
694        if self.result_type() == ResultType::Unknown {
695            self.set_result_type(ResultType::Cached, None);
696        }
697    }
698
699    pub fn unmark_cached(&self) {
700        if self.result_type() == ResultType::Cached {
701            self.set_result_type(ResultType::Unknown, None);
702        }
703    }
704}
705
706impl Output for ArrayView {
707    fn push(&self, change: Change, _pusher: &dyn InputBase) {
708        let mut s = self.state.borrow_mut();
709        if apply(&mut s.root, &change, &self.schema, "", &self.format) {
710            s.dirty = true;
711        }
712    }
713
714    fn has_reconcile(&self) -> bool {
715        false
716    }
717}