Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

21.1 KB
Raw Blame
//! Stage four as a state machine: an [`Engine`] carries one statement from
//! its first step to its [`Outcome`], asking the driver for rows one
//! [`Request`] at a time (taken back through [`Engine::feed_page`] and
//! [`Engine::feed_bins`]) and for a write to be applied as ops (taken back
//! through [`Engine::feed_ops`]).
//!
//! The engine does no I/O and holds no references, so it crosses a wasm
//! boundary as JSON: a driver in any language loops on [`Step`] until it is
//! [`Step::Done`]. Relations are fetched in plan order, each to completion,
//! and a joined relation's request carries the key values the rows so far
//! need (see [`KeyHint`]), which a driver may use to fetch less.
//!
//! An `INSERT` or `ALTER COLUMN` is one [`Step::Ops`]. An `UPDATE` or
//! `DELETE` first reads the rows its `WHERE` matches, through the same fetch
//! steps as a `SELECT`, then writes them all in one op.

#[cfg(test)]
mod test;

use std::collections::HashSet;

use models_databases::{DatabaseId, DatabaseOp, OpResult, RowId, TableId};
use serde::{Deserialize, Serialize};
use specta::Type;
use uuid::Uuid;

use crate::catalog::{Catalog, Table};
use crate::fold::{Bin, Cell, CellKey, Row, fold_bins, fold_relations};
use crate::resolve::{
    ComparisonOperator, DeleteQuery, Filter, Query, SelectQuery, UpdateQuery, Value, binding,
    column_key, compile, row_id_key, row_position_key,
};
use crate::run::{Answer, Outcome, OutcomeColumn, PAGE_LIMIT, Page, ROW_CAP, RunError, describe};
use crate::split::{GqlQuery, KeyHint, MAX_KEY_HINT_VALUES, Plan, RelationPlan, Shape, split};
use crate::write::{self, Sent};

/// What the driver does next.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Type)]
#[serde(tag = "step", rename_all = "camelCase")]
pub enum Step {
    /// Fetch one page and feed it to [`Engine::feed_page`].
    Fetch(Request),
    /// Fetch the bins of a `GroupSoup` query and feed them to
    /// [`Engine::feed_bins`].
    Bins(Request),
    /// Apply these ops to the database, together, and feed their results to
    /// [`Engine::feed_ops`].
    Ops {
        /// Identifies the request; the feed must quote it.
        id: u32,
        /// The database the ops are for.
        database: DatabaseId,
        /// The ops, in order.
        ops: Vec<DatabaseOp>,
    },
    /// The answer.
    Done(Outcome),
}

/// One fetch the engine wants.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Type)]
#[serde(rename_all = "camelCase")]
pub struct Request {
    /// Identifies the request; the feed must quote it.
    pub id: u32,
    /// What to ask the server.
    pub query: GqlQuery,
    /// The keys the rows must carry; the driver maps them to properties
    /// through the plan's bindings, or fetches every column.
    pub needs: Vec<Uuid>,
    /// Where to continue; `None` at the start of a relation.
    pub cursor: Option<String>,
    /// At most this many rows.
    #[specta(type = u32)]
    pub limit: usize,
}

/// One statement in flight.
#[derive(Debug, Clone)]
pub struct Engine {
    catalog: Catalog,
    /// The `SELECT` being fetched: the statement's own, or the one that
    /// finds an update's or delete's rows.
    read: Option<Read>,
    /// What the statement writes once its read is done.
    then: Option<Then>,
    requests: Requests,
}

/// The ids handed to requests, and the one a feed must answer with what
/// it asked for.
#[derive(Debug, Clone, Default)]
struct Requests {
    outstanding: Option<(u32, Awaiting)>,
    next: u32,
}

/// What the outstanding request waits on.
#[derive(Debug, Clone)]
enum Awaiting {
    Page,
    Bins,
    /// The results of the ops sent, read back as `Sent` says.
    OpResults(Sent),
}

/// A read's progress.
#[derive(Debug, Clone)]
struct Read {
    columns: Vec<OutcomeColumn>,
    plan: Plan,
    /// The rows of every relation fetched so far, `FROM` first.
    fetched: Vec<Vec<Row>>,
    /// The relation being fetched.
    current: usize,
    /// The current relation's query, its key hint filled in once its
    /// relation starts.
    query: Option<GqlQuery>,
    truncated: bool,
}

/// A write waiting on the rows its read finds.
#[derive(Debug, Clone)]
enum Then {
    Update(UpdateQuery),
    Delete(DeleteQuery),
}

impl Engine {
    /// Compile a statement and take its first step.
    pub fn start(catalog: &Catalog, sql: &str) -> Result<(Engine, Step), RunError> {
        let mut engine = Engine::new(catalog);
        let step = match compile(catalog, sql)? {
            Query::Select(select) => engine.begin_read(select)?,
            Query::Insert(insert) => {
                let op = write::insert(catalog, &insert)?;
                engine.send(insert.table, Sent::Rows, op)?
            }
            Query::AlterColumnType(alter) => {
                let op = write::alter(catalog, &alter)?;
                let sent = Sent::Column {
                    table: alter.table,
                    column: alter.column,
                    to: alter.to,
                };
                engine.send(alter.table, sent, op)?
            }
            Query::Update(update) => {
                let read = update.read.clone();
                engine.then = Some(Then::Update(update));
                engine.begin_read(read)?
            }
            Query::Delete(delete) => {
                let read = delete.read.clone();
                engine.then = Some(Then::Delete(delete));
                engine.begin_read(read)?
            }
        };
        Ok((engine, step))
    }

    /// Plan a resolved `SELECT` and ask for its first fetch.
    pub fn from_select(catalog: &Catalog, select: SelectQuery) -> Result<(Engine, Step), RunError> {
        let mut engine = Engine::new(catalog);
        let step = engine.begin_read(select)?;
        Ok((engine, step))
    }

    fn new(catalog: &Catalog) -> Engine {
        Engine {
            catalog: catalog.clone(),
            read: None,
            then: None,
            requests: Requests::default(),
        }
    }

    /// Take one page of the outstanding request. Cells may be keyed by
    /// property definition, as a source reads them; the engine keys a
    /// joined relation's cells itself (see [`column_key`]).
    pub fn feed_page(&mut self, request_id: u32, page: Page) -> Result<Step, RunError> {
        match self.requests.answer(request_id)? {
            Awaiting::Page => {}
            awaiting => return Err(awaiting.refuse(request_id, Answer::Page)),
        }
        let read = reading(&mut self.read)?;
        let keyed = keyed(&self.catalog, read, page.rows)?;
        let rows = read.current_rows()?;
        rows.extend(keyed);
        if rows.len() >= ROW_CAP {
            rows.truncate(ROW_CAP);
            read.truncated = true;
            return self.finish_relation();
        }
        match page.next {
            Some(cursor) => request(read, &mut self.requests, Some(cursor)),
            None => self.finish_relation(),
        }
    }

    /// Take the bins of the outstanding request.
    pub fn feed_bins(&mut self, request_id: u32, bins: Vec<Bin>) -> Result<Step, RunError> {
        match self.requests.answer(request_id)? {
            Awaiting::Bins => {}
            awaiting => return Err(awaiting.refuse(request_id, Answer::Bins)),
        }
        let read = reading(&mut self.read)?;
        let rows = fold_bins(&self.catalog, &read.plan, bins)?;
        let outcome = read.outcome(rows, Vec::new());
        self.finish_read(outcome)
    }

    /// Take the results of the outstanding ops, one per op.
    pub fn feed_ops(&mut self, request_id: u32, results: Vec<OpResult>) -> Result<Step, RunError> {
        match self.requests.answer(request_id)? {
            Awaiting::OpResults(sent) => Ok(Step::Done(write::outcome(&sent, &results)?)),
            awaiting => Err(awaiting.refuse(request_id, Answer::OpResults)),
        }
    }

    /// Plan a read and ask for its first fetch.
    fn begin_read(&mut self, select: SelectQuery) -> Result<Step, RunError> {
        for relation in &select.relations {
            table(&self.catalog, relation.table)?;
        }
        let columns = describe(
            &self.catalog,
            &select.items,
            &select.labels,
            &select.bindings,
            &select.relations,
        )?;
        let plan = split(&self.catalog, select);
        let read = self.read.insert(Read {
            columns,
            plan,
            fetched: Vec::new(),
            current: 0,
            query: None,
            truncated: false,
        });
        begin_relation(read, &mut self.requests)
    }

    /// A relation is complete: give it its row ids and positions, then move
    /// on or fold.
    fn finish_relation(&mut self) -> Result<Step, RunError> {
        let read = reading(&mut self.read)?;
        let table = read.current_relation()?.relation.table;
        let bound = |key: Uuid| binding(&read.plan.bindings, key).is_some();
        let (id_key, position_key) = (row_id_key(table), row_position_key(table));
        let (ids, positions) = (bound(id_key), bound(position_key));
        // Sources list rows in any order (Soup: newest first); the fold sees
        // them in table order, as the server's row store keeps them, so an
        // unordered result or its groups come out alike on both.
        let rows = read.current_rows()?;
        rows.sort_by(table_order);
        for row in rows {
            if ids {
                row.cells.insert(id_key, Cell::Row(row.id));
            }
            if positions && let Some(position) = &row.position {
                row.cells
                    .insert(position_key, Cell::Text(position.to_string()));
            }
        }
        read.current += 1;
        if read.current < read.plan.relations.len() {
            return begin_relation(read, &mut self.requests);
        }
        let fetched = std::mem::take(&mut read.fetched);
        let (rows, row_ids) = fold_relations(&self.catalog, &read.plan, fetched);
        let row_ids = match read.plan.shape {
            Shape::Rows(_) => row_ids,
            Shape::Aggregate { .. } => Vec::new(),
        };
        let outcome = read.outcome(rows, row_ids);
        self.finish_read(outcome)
    }

    /// The read's answer, or for a write, the op it makes of the rows found.
    fn finish_read(&mut self, found: Outcome) -> Result<Step, RunError> {
        let Some(then) = self.then.take() else {
            return Ok(Step::Done(found));
        };
        if found.truncated {
            return Err(RunError::TooManyRows { limit: ROW_CAP });
        }
        let read = match &then {
            Then::Update(update) => &update.read,
            Then::Delete(delete) => &delete.read,
        };
        if let Some((position, row)) = named_rows(read.table(), read.where_.as_ref())
            .into_iter()
            .enumerate()
            .find(|(_, row)| !found.row_ids.contains(row))
        {
            return Err(RunError::NoSuchRow {
                position: position + 1,
                row,
            });
        }
        let (table, op) = match &then {
            Then::Update(update) => (update.table, write::update(&self.catalog, update, &found)?),
            Then::Delete(delete) => (delete.table, write::delete(delete.table, &found)),
        };
        match op {
            Some(op) => self.send(table, Sent::Rows, op),
            None => Ok(Step::Done(Outcome::default())),
        }
    }

    /// Ask for one op to be applied to the database `table` belongs to.
    fn send(&mut self, table_id: TableId, sent: Sent, op: DatabaseOp) -> Result<Step, RunError> {
        let database = table(&self.catalog, table_id)?.database_id;
        Ok(Step::Ops {
            id: self.requests.issue(Awaiting::OpResults(sent)),
            database,
            ops: vec![op],
        })
    }
}

impl Requests {
    /// A new request's id, now the one outstanding, waiting on `awaiting`.
    fn issue(&mut self, awaiting: Awaiting) -> u32 {
        let id = self.next;
        self.next += 1;
        self.outstanding = Some((id, awaiting));
        id
    }

    /// What `request_id`, which must be the outstanding request, waits on.
    /// The request is spent either way.
    fn answer(&mut self, request_id: u32) -> Result<Awaiting, RunError> {
        match self.outstanding.take() {
            Some((expected, awaiting)) if expected == request_id => Ok(awaiting),
            Some((expected, _)) => Err(RunError::WrongRequest {
                expected,
                fed: request_id,
            }),
            None => Err(RunError::NothingOutstanding { fed: request_id }),
        }
    }
}

impl Awaiting {
    /// The refusal of `fed` as the answer to `request`, which waits on this.
    fn refuse(&self, request: u32, fed: Answer) -> RunError {
        RunError::WrongAnswer {
            request,
            expected: match self {
                Awaiting::Page => Answer::Page,
                Awaiting::Bins => Answer::Bins,
                Awaiting::OpResults(_) => Answer::OpResults,
            },
            fed,
        }
    }
}

impl Read {
    /// The plan of the relation being fetched.
    fn current_relation(&self) -> Result<&RelationPlan, RunError> {
        self.plan
            .relations
            .get(self.current)
            .ok_or(RunError::Internal {
                invariant: "the relation being fetched is in the plan",
            })
    }

    /// The rows of the relation being fetched, so far.
    fn current_rows(&mut self) -> Result<&mut Vec<Row>, RunError> {
        self.fetched
            .get_mut(self.current)
            .ok_or(RunError::Internal {
                invariant: "the relation being fetched has begun",
            })
    }

    /// The rows the current relation needs: for the `FROM` table, the rows
    /// its `WHERE` names by id; for a joined one, the values it is joined on.
    /// `None` past [`MAX_KEY_HINT_VALUES`].
    fn key_hint(&self) -> Option<KeyHint> {
        if self.current == 0 {
            return self.named_rows_hint();
        }
        self.join_hint()
    }

    /// The rows a `WHERE row_id IN (…)` names, which never pushes into
    /// `propf`, as row ids the source may narrow its fetch to.
    fn named_rows_hint(&self) -> Option<KeyHint> {
        let rows = named_rows(self.plan.table(), self.plan.residual.as_ref());
        if rows.is_empty() || rows.len() > MAX_KEY_HINT_VALUES {
            return None;
        }
        Some(KeyHint {
            column: None,
            values: rows
                .iter()
                .map(|row| Cell::Entities(vec![row.to_string()]))
                .collect(),
        })
    }

    /// The values the current relation is joined on, from the rows of the
    /// relation on the other side of the join's first equality, one member
    /// each.
    fn join_hint(&self) -> Option<KeyHint> {
        let join = self
            .plan
            .joins
            .iter()
            .find(|join| join.relation == self.current)?;
        let (left, right) = *join.on.first()?;
        let owner = binding(&self.plan.bindings, left)?;
        let mut seen: HashSet<CellKey> = HashSet::new();
        let mut values: Vec<Cell> = Vec::new();
        for cell in self
            .fetched
            .get(owner.relation)?
            .iter()
            .filter_map(|row| row.cells.get(&left))
        {
            for member in members(cell) {
                if seen.insert(CellKey::from(&member)) {
                    if values.len() == MAX_KEY_HINT_VALUES {
                        return None;
                    }
                    values.push(member);
                }
            }
        }
        Some(KeyHint {
            column: binding(&self.plan.bindings, right)?.column,
            values,
        })
    }

    fn outcome(&self, rows: crate::fold::Table, row_ids: Vec<RowId>) -> Outcome {
        Outcome {
            columns: self.columns.clone(),
            rows,
            row_ids,
            read_tables: self
                .plan
                .relations
                .iter()
                .map(|relation| relation.relation.table)
                .collect(),
            truncated: self.truncated,
            ..Outcome::default()
        }
    }
}

/// Start fetching the current relation, with the join's key hint filled
/// in.
fn begin_relation(read: &mut Read, requests: &mut Requests) -> Result<Step, RunError> {
    read.fetched.push(Vec::new());
    let mut query = read.current_relation()?.query.clone();
    if let GqlQuery::GroupSoup { .. } = query {
        return Ok(Step::Bins(Request {
            id: requests.issue(Awaiting::Bins),
            query,
            needs: Vec::new(),
            cursor: None,
            limit: 0,
        }));
    }
    if let Some(hint) = read.key_hint() {
        match &mut query {
            GqlQuery::Soup { key_hint, .. } => *key_hint = Some(hint),
            GqlQuery::People { ids } => {
                *ids = Some(
                    hint.values
                        .into_iter()
                        .filter_map(|cell| match cell {
                            Cell::Entities(mut ids) => ids.pop(),
                            Cell::Text(id) => Some(id),
                            _ => None,
                        })
                        .collect(),
                )
            }
            GqlQuery::GroupSoup { .. } => {}
        }
    }
    read.query = Some(query);
    request(read, requests, None)
}

/// The next page of the current relation.
fn request(read: &Read, requests: &mut Requests, cursor: Option<String>) -> Result<Step, RunError> {
    let relation = read.current_relation()?;
    let fetched = read.fetched.get(read.current).map_or(0, Vec::len);
    let query = read.query.clone().ok_or(RunError::Internal {
        invariant: "a relation's query is set when it starts",
    })?;
    Ok(Step::Fetch(Request {
        id: requests.issue(Awaiting::Page),
        query,
        needs: relation.needs.clone(),
        cursor,
        limit: ROW_CAP.saturating_sub(fetched).min(PAGE_LIMIT),
    }))
}

/// A joined relation's cells under the keys the plan uses for it: a cell
/// keyed by one of its table's definitions moves to that column's key for
/// this relation. The `FROM` relation's keys are its definitions already,
/// and a cell keyed some other way is kept as is.
fn keyed(catalog: &Catalog, read: &Read, rows: Vec<Row>) -> Result<Vec<Row>, RunError> {
    if read.current == 0 {
        return Ok(rows);
    }
    let table = table(catalog, read.current_relation()?.relation.table)?;
    Ok(rows
        .into_iter()
        .map(|row| Row {
            id: row.id,
            position: row.position,
            cells: row
                .cells
                .into_iter()
                .map(|(key, cell)| {
                    if table.columns.iter().any(|column| column.id == key) {
                        (column_key(read.current, key), cell)
                    } else {
                        (key, cell)
                    }
                })
                .collect(),
        })
        .collect())
}

/// A table the statement reads or writes.
fn table(catalog: &Catalog, id: TableId) -> Result<&Table, RunError> {
    catalog
        .tables
        .iter()
        .find(|table| table.id == id)
        .ok_or(RunError::TableNotInCatalog { table: id })
}

/// The rows of `table` a `WHERE row_id = …` or `WHERE row_id IN (…)` names.
/// A write's must all exist: naming a row is not a search.
fn named_rows(table: TableId, filter: Option<&Filter>) -> Vec<RowId> {
    let row_id = row_id_key(table);
    let ids = |values: &[Value]| -> Vec<RowId> {
        values
            .iter()
            .filter_map(|value| match value {
                Value::Entity(id) => id.parse().ok(),
                _ => None,
            })
            .collect()
    };
    match filter {
        Some(Filter::Comparison {
            column,
            operator: ComparisonOperator::Equal,
            value,
        }) if *column == row_id => ids(std::slice::from_ref(value)),
        Some(Filter::In {
            column,
            values,
            negated: false,
        }) if *column == row_id => ids(values),
        _ => Vec::new(),
    }
}

/// The read in flight; pages and bins are only asked for while reading.
fn reading(read: &mut Option<Read>) -> Result<&mut Read, RunError> {
    read.as_mut().ok_or(RunError::Internal {
        invariant: "pages and bins are only asked for while reading",
    })
}

/// Position, then id, as `database_rows` orders a table; rows without a
/// position (`people`) keep the order they came in, after any that have one.
fn table_order(left: &Row, right: &Row) -> std::cmp::Ordering {
    use std::cmp::Ordering;
    match (&left.position, &right.position) {
        (Some(left_position), Some(right_position)) => left_position
            .cmp(right_position)
            .then(left.id.cmp(&right.id)),
        (Some(_), None) => Ordering::Less,
        (None, Some(_)) => Ordering::Greater,
        (None, None) => Ordering::Equal,
    }
}

/// A cell one member at a time, so a driver can read a hint as a list of
/// ids or options.
fn members(cell: &Cell) -> Vec<Cell> {
    match cell {
        Cell::Entities(ids) => ids
            .iter()
            .map(|id| Cell::Entities(vec![id.clone()]))
            .collect(),
        Cell::Options(ids) => ids.iter().map(|id| Cell::Options(vec![*id])).collect(),
        other => vec![other.clone()],
    }
}