Skip to main content

datacraft_query/
native_exec.rs

1//! Native select-query execution (step 27.1, item M12).
2//!
3//! The MSysQueries decoder (M3) exposes the stored query verbatim; this
4//! module executes the qualified subset over materialized port rows:
5//! select queries over one or more tables with **equality** joins
6//! (inner/left/right), Access boolean WHERE expressions (the expression
7//! service's grammar — `And`/`Or`/`Not`, `In`, `Is [Not] Null`, `Like`,
8//! `Between`, brackets and double-quoted text), `Table.*` wildcards and
9//! ORDER BY entries.
10//!
11//! Everything outside that subset answers a precise
12//! [`NativeExecError::Unsupported`]: other query flavors, GROUP BY/HAVING,
13//! parameters, select modifiers (DISTINCT/TOP/PERCENT), computed columns,
14//! self-joins and non-equality joins. Identifiers are whitelisted against
15//! the schema (LESSONS #5) before any evaluation; ambiguous bare names are
16//! refused instead of resolved by insertion order. A deterministic row cap
17//! protects the process from crafted cartesian joins (LESSONS #7).
18
19use std::collections::BTreeSet;
20
21use crate::native_query::{NativeQuery, NativeQueryKind};
22use crate::query_engine::QueryResult;
23use datacraft_types::{FieldValue, TableDef};
24
25mod join;
26mod project;
27
28use join::{JoinPlan, PartialRow};
29use project::{OrderKey, Projection, filter_rows, parse_column, parse_expression};
30
31/// Deterministic guard against crafted cartesian joins.
32pub const MAX_JOINED_ROWS: usize = 1_000_000;
33
34/// Why a native query could not execute; every variant carries a precise,
35/// locatable detail.
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub enum NativeExecError {
38    /// A decoded construct is outside the executable dialect.
39    Unsupported {
40        /// What is unsupported and why.
41        reason: String,
42    },
43    /// A FROM entry names no source table.
44    UnknownTable {
45        /// The unknown table.
46        table: String,
47    },
48    /// A field reference names no column of its table.
49    UnknownField {
50        /// Qualifying table, when the reference was qualified.
51        table: Option<String>,
52        /// The unknown field.
53        field: String,
54    },
55    /// A bare field name exists in more than one source table.
56    AmbiguousField {
57        /// The ambiguous field.
58        field: String,
59    },
60    /// An expression does not parse or fails to evaluate.
61    BadExpression {
62        /// The stored expression source.
63        source: String,
64        /// Concrete reason.
65        detail: String,
66    },
67    /// The join would materialize more rows than the guard allows.
68    TooManyRows {
69        /// The capped row count.
70        rows: usize,
71        /// The configured limit.
72        limit: usize,
73    },
74}
75
76impl std::fmt::Display for NativeExecError {
77    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
78        match self {
79            Self::Unsupported { reason } => write!(f, "unsupported: {reason}"),
80            Self::UnknownTable { table } => {
81                write!(f, "table {table:?} not found in the query's sources")
82            }
83            Self::UnknownField {
84                table: Some(table),
85                field,
86            } => write!(f, "field {field:?} is not a field of {table:?}"),
87            Self::UnknownField { table: None, field } => {
88                write!(f, "field {field:?} is not a field of any source table")
89            }
90            Self::AmbiguousField { field } => {
91                write!(f, "field {field:?} is ambiguous across the query's tables")
92            }
93            Self::BadExpression { source, detail } => {
94                write!(f, "native query expression {source:?}: {detail}")
95            }
96            Self::TooManyRows { rows, limit } => write!(
97                f,
98                "the query would materialize {rows} joined rows — the limit is {limit}"
99            ),
100        }
101    }
102}
103
104impl std::error::Error for NativeExecError {}
105
106/// Executes one decoded native query over materialized source rows.
107/// `sources` pairs every FROM table with its rows; lookups are
108/// case-insensitive.
109pub fn run(
110    query: &NativeQuery,
111    sources: &[(&TableDef, Vec<Vec<FieldValue>>)],
112) -> Result<QueryResult, NativeExecError> {
113    run_with_limit(query, sources, MAX_JOINED_ROWS)
114}
115
116fn run_with_limit(
117    query: &NativeQuery,
118    sources: &[(&TableDef, Vec<Vec<FieldValue>>)],
119    limit: usize,
120) -> Result<QueryResult, NativeExecError> {
121    validate_query(query)?;
122
123    let mut from_tables: Vec<&TableDef> = Vec::new();
124    let mut from_rows: Vec<&[Vec<FieldValue>]> = Vec::new();
125    let mut seen: BTreeSet<String> = BTreeSet::new();
126    for name in &query.tables {
127        if !seen.insert(name.to_lowercase()) {
128            return unsupported(format!(
129                "native query {:?}: duplicate table {name:?} (self-joins need aliases and stay \
130                 unsupported)",
131                query.name
132            ));
133        }
134        let Some((table, rows)) = sources
135            .iter()
136            .find(|(table, _)| table.name.eq_ignore_ascii_case(name))
137        else {
138            return Err(NativeExecError::UnknownTable {
139                table: name.clone(),
140            });
141        };
142        from_tables.push(*table);
143        from_rows.push(rows.as_slice());
144    }
145    let unique_bare = project::unique_bare_fields(&from_tables);
146
147    let mut bound = vec![false; from_tables.len()];
148    bound[0] = true;
149    let mut rows: Vec<PartialRow> = from_rows[0]
150        .iter()
151        .map(|values| {
152            let mut cells = vec![None; from_tables.len()];
153            cells[0] = Some(values.clone());
154            PartialRow { cells }
155        })
156        .collect();
157    join::check_limit(rows.len(), limit)?;
158
159    let mut pending: Vec<JoinPlan> = query
160        .joins
161        .iter()
162        .map(|join| join::parse(join, &from_tables))
163        .collect::<Result<_, _>>()?;
164    loop {
165        let mut applied = false;
166        let mut index = 0;
167        while index < pending.len() {
168            let plan = pending[index].clone();
169            let a_bound = bound[plan.a.0];
170            let b_bound = bound[plan.b.0];
171            match (a_bound, b_bound) {
172                (true, true) => {
173                    if plan.kind != crate::native_query::NativeJoinKind::Inner {
174                        return unsupported(format!(
175                            "outer join {:?} is outside the subset — it must connect a new table",
176                            plan.source
177                        ));
178                    }
179                    rows.retain(|row| {
180                        join::equal(
181                            &row.value(plan.a.0, plan.a.1),
182                            &row.value(plan.b.0, plan.b.1),
183                        )
184                    });
185                    pending.remove(index);
186                    applied = true;
187                }
188                (true, false) | (false, true) => {
189                    let new_is_a = !a_bound;
190                    let (new_pos, new_col, bound_pos, bound_col) = if new_is_a {
191                        (plan.a.0, plan.a.1, plan.b.0, plan.b.1)
192                    } else {
193                        (plan.b.0, plan.b.1, plan.a.0, plan.a.1)
194                    };
195                    rows = join::bind_new(
196                        rows,
197                        from_tables[new_pos],
198                        from_rows[new_pos],
199                        new_pos,
200                        new_col,
201                        bound_pos,
202                        bound_col,
203                        plan.kind,
204                        new_is_a,
205                        limit,
206                    )?;
207                    bound[new_pos] = true;
208                    pending.remove(index);
209                    applied = true;
210                }
211                (false, false) => index += 1,
212            }
213        }
214        if !applied {
215            break;
216        }
217    }
218    if let Some(plan) = pending.first() {
219        return unsupported(format!(
220            "join {:?} does not connect to the FROM tables in their decoded order",
221            plan.source
222        ));
223    }
224    for position in 0..from_tables.len() {
225        if !bound[position] {
226            rows = join::cross(rows, position, from_rows[position], limit)?;
227        }
228    }
229
230    let mut filters = Vec::with_capacity(query.criteria.len());
231    for criterion in &query.criteria {
232        let expression = parse_expression(criterion, &from_tables)?;
233        filters.push((criterion.clone(), expression));
234    }
235    rows = filter_rows(rows, &filters, &from_tables, &unique_bare)?;
236
237    let mut orders = Vec::with_capacity(query.order_by.len());
238    for order in &query.order_by {
239        let expression = parse_expression(&order.field, &from_tables)?;
240        let Some((position, column)) = project::resolve_field(&expression, &from_tables) else {
241            return unsupported(format!(
242                "ORDER BY {:?} is computed — only field references sort",
243                order.field
244            ));
245        };
246        orders.push(OrderKey {
247            position,
248            column,
249            descending: order.descending,
250        });
251    }
252    project::sort_rows(&mut rows, &orders);
253
254    let mut projections: Vec<Projection> = Vec::new();
255    for column in &query.columns {
256        projections.extend(parse_column(column, &from_tables)?);
257    }
258    if projections.is_empty() {
259        return unsupported(format!("native query {:?} projects no columns", query.name));
260    }
261    Ok(project::project(&rows, &projections))
262}
263
264fn validate_query(query: &NativeQuery) -> Result<(), NativeExecError> {
265    if query.kind != NativeQueryKind::Select {
266        return unsupported(format!(
267            "native query {:?} is a {} query — only select queries execute",
268            query.name,
269            kind_label(query.kind)
270        ));
271    }
272    if !query.group_by.is_empty() || !query.having.is_empty() {
273        return unsupported(format!(
274            "native query {:?}: group by / having are outside the executable subset",
275            query.name
276        ));
277    }
278    if !query.parameters.is_empty() {
279        return unsupported(format!(
280            "native query {:?}: parameters are outside the executable subset",
281            query.name
282        ));
283    }
284    if query.select_flags & !0x01 != 0 {
285        return unsupported(format!(
286            "native query {:?}: select modifiers (distinct/top/percent) are outside the \
287             executable subset",
288            query.name
289        ));
290    }
291    if query.tables.is_empty() {
292        return unsupported(format!("native query {:?} has no source table", query.name));
293    }
294    Ok(())
295}
296
297fn unsupported<T>(reason: String) -> Result<T, NativeExecError> {
298    Err(NativeExecError::Unsupported { reason })
299}
300
301fn kind_label(kind: NativeQueryKind) -> &'static str {
302    match kind {
303        NativeQueryKind::Select => "select",
304        NativeQueryKind::Crosstab => "crosstab",
305        NativeQueryKind::Delete => "delete",
306        NativeQueryKind::Update => "update",
307        NativeQueryKind::Append => "append",
308        NativeQueryKind::MakeTable => "make-table",
309        NativeQueryKind::DataDefinition => "data-definition",
310        NativeQueryKind::Passthrough => "pass-through",
311        NativeQueryKind::Union => "union",
312    }
313}
314
315#[cfg(test)]
316mod tests;