Skip to main content

uqa_graph/cypher/
executor.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Read-only Cypher executor: walks a `CypherQuery` AST and lowers it
8//! onto graph operators against a [`GraphStore`].
9//!
10//! Semantics follow Apache AGE 1.6.0 (verified against a live
11//! container): agtype total ordering for `ORDER BY` and comparisons,
12//! three-valued boolean logic with strict boolean inputs, C-style
13//! integer division / modulo (`n % 0` returns `n`, matching AGE),
14//! float `^` power, end-exclusive list slices, end-inclusive
15//! `range()`, byte-length `size()` on strings, unanchored `=~`, and
16//! graph entities that render as `::vertex` / `::edge` / `::path`.
17//!
18//! Supported clauses: `MATCH` (node, 1-hop rel, variable-length rel,
19//! path variables), `OPTIONAL MATCH`, `WHERE`, `RETURN` (with
20//! `DISTINCT`, `ORDER BY`, `SKIP`, `LIMIT`), `WITH`, and `UNWIND`. Mutation
21//! clauses live in [`crate::cypher::writer::CypherWriter`].
22
23use std::collections::{BTreeMap, BTreeSet};
24
25use uqa_core::{Edge, EdgeId, Value, Vertex, VertexId};
26
27use crate::agtype;
28use crate::cypher::ast::{
29    BinaryOp, CaseExpr, CypherClause, CypherExpr, CypherQuery, FunctionCall, InList, IsNotNull,
30    IsNull, ListComprehension, ListIndex, ListLiteral, ListSlice, Literal, MapLiteral, MatchClause,
31    NodePattern, OrderByItem, Parameter, PathElement, PathPattern, PropertyAccess, RelDirection,
32    RelPattern, ReturnItem, UnaryOp, UnwindClause, Variable,
33};
34use crate::store::GraphStore;
35use crate::types::Direction;
36
37/// One row in the binding table threaded through the clause pipeline.
38/// Variables can resolve to vertex / edge / arbitrary value bindings.
39#[derive(Debug, Clone)]
40pub enum Binding {
41    Vertex(Vertex),
42    Edge(Edge),
43    Value(Value),
44    /// Variable-length relationship binding: ordered list of edges.
45    EdgeList(Vec<Edge>),
46}
47
48impl Binding {
49    fn property(&self, key: &str) -> Value {
50        match self {
51            Binding::Vertex(v) => v.properties.get(key).cloned().unwrap_or(Value::Null),
52            Binding::Edge(e) => e.properties.get(key).cloned().unwrap_or(Value::Null),
53            Binding::Value(v) => value_property(v, key).unwrap_or(Value::Null),
54            Binding::EdgeList(_) => Value::Null,
55        }
56    }
57
58    fn to_value(&self) -> Result<Value, CypherError> {
59        match self {
60            Binding::Vertex(v) => agtype::vertex_to_value(v).map_err(Into::into),
61            Binding::Edge(e) => agtype::edge_to_value(e).map_err(Into::into),
62            Binding::Value(v) => Ok(v.clone()),
63            Binding::EdgeList(edges) => Ok(Value::List(
64                edges
65                    .iter()
66                    .map(agtype::edge_to_value)
67                    .collect::<Result<_, _>>()?,
68            )),
69        }
70    }
71}
72
73/// Property lookup on an evaluated value (map, entity envelope, or
74/// null). `None` signals "not addressable" so callers can raise AGE's
75/// `scalar object must be a vertex or edge` error.
76fn value_property(value: &Value, key: &str) -> Option<Value> {
77    if let Some(props) = agtype::entity_properties(value) {
78        return Some(props.get(key).cloned().unwrap_or(Value::Null));
79    }
80    match value {
81        Value::Map(map) => Some(map.get(key).cloned().unwrap_or(Value::Null)),
82        Value::Null => Some(Value::Null),
83        _ => None,
84    }
85}
86
87/// A row in the binding table: variable name -> bound value.
88pub type BindingRow = BTreeMap<String, Binding>;
89
90/// Result row produced by RETURN / WITH (column name -> value).
91pub type ResultRow = BTreeMap<String, Value>;
92
93#[derive(Debug, thiserror::Error, PartialEq)]
94pub enum CypherError {
95    #[error("undefined variable {0:?}")]
96    UndefinedVariable(String),
97    #[error("undefined parameter {0:?}")]
98    UndefinedParameter(String),
99    #[error("unsupported clause: {0}")]
100    Unsupported(String),
101    #[error("{0}")]
102    TypeError(String),
103    #[error("parse error: {0}")]
104    Parse(String),
105    #[error("relation \"{0}\" does not exist")]
106    MissingLabelRelation(String),
107    #[error("storage error: {0}")]
108    Storage(String),
109    #[error("storage error: {0}")]
110    Backend(#[source] crate::GraphStorageError),
111    #[error("serialization failure: {0}")]
112    SerializationFailure(String),
113}
114
115impl From<crate::cypher::parser::ParseError> for CypherError {
116    fn from(err: crate::cypher::parser::ParseError) -> Self {
117        CypherError::Parse(err.to_string())
118    }
119}
120
121impl From<agtype::AgtypeConversionError> for CypherError {
122    fn from(err: agtype::AgtypeConversionError) -> Self {
123        CypherError::Storage(err.to_string())
124    }
125}
126
127impl From<crate::store::GraphStoreError> for CypherError {
128    fn from(err: crate::store::GraphStoreError) -> Self {
129        match err {
130            crate::store::GraphStoreError::Backend(source) => Self::Backend(source),
131            crate::store::GraphStoreError::SerializationFailure(message) => {
132                Self::SerializationFailure(message)
133            }
134            other => Self::Storage(other.to_string()),
135        }
136    }
137}
138
139impl From<uqa_storage::StorageBackendError> for CypherError {
140    fn from(error: uqa_storage::StorageBackendError) -> Self {
141        Self::Backend(error.into())
142    }
143}
144
145fn boolean_cast_error(value: &Value) -> CypherError {
146    CypherError::TypeError(format!(
147        "cannot cast agtype {} to type boolean",
148        agtype::agtype_type_name(value)
149    ))
150}
151
152/// Strict boolean coercion (AGE): booleans pass through, null is
153/// three-valued unknown, anything else raises a cast error.
154fn strict_bool(value: &Value) -> Result<Option<bool>, CypherError> {
155    match value {
156        Value::Bool(b) => Ok(Some(*b)),
157        Value::Null => Ok(None),
158        other => Err(boolean_cast_error(other)),
159    }
160}
161
162const MAX_EXACT_F64_INTEGER: i64 = 9_007_199_254_740_992;
163
164fn usize_to_i64(value: usize, context: &str) -> Result<i64, CypherError> {
165    i64::try_from(value).map_err(|_| {
166        CypherError::TypeError(format!(
167            "{context} {value} exceeds the agtype integer range"
168        ))
169    })
170}
171
172fn nonnegative_i64_to_usize(value: i64, context: &str) -> Result<usize, CypherError> {
173    if value < 0 {
174        return Err(CypherError::TypeError(format!(
175            "{context} must not be negative, got {value}"
176        )));
177    }
178    usize::try_from(value).map_err(|_| {
179        CypherError::TypeError(format!(
180            "{context} {value} exceeds the platform index range"
181        ))
182    })
183}
184
185fn nonnegative_i64_to_u64(value: i64, context: &str) -> Result<u64, CypherError> {
186    u64::try_from(value)
187        .map_err(|_| CypherError::TypeError(format!("{context} must not be negative, got {value}")))
188}
189
190fn exact_i64_to_f64(value: i64, context: &str) -> Result<f64, CypherError> {
191    if (-MAX_EXACT_F64_INTEGER..=MAX_EXACT_F64_INTEGER).contains(&value) {
192        Ok(value as f64)
193    } else {
194        Err(CypherError::TypeError(format!(
195            "{context} {value} cannot be represented exactly as a float"
196        )))
197    }
198}
199
200fn trunc_f64_to_i64(value: f64, context: &str) -> Result<i64, CypherError> {
201    if !value.is_finite() {
202        return Err(CypherError::TypeError(format!(
203            "{context} must be finite, got {value}"
204        )));
205    }
206    let truncated = value.trunc();
207    if !(-9_223_372_036_854_775_808.0..9_223_372_036_854_775_808.0).contains(&truncated) {
208        return Err(CypherError::TypeError(format!(
209            "{context} {value} is outside the agtype integer range"
210        )));
211    }
212    Ok(truncated as i64)
213}
214
215/// Read-only execution context.
216pub struct CypherExecutor<'a, G: GraphStore> {
217    pub store: &'a G,
218    pub graph: &'a str,
219    pub params: BTreeMap<String, Value>,
220}
221
222/// Intermediate state while a path pattern binds: the row so far, the
223/// vertex the pattern currently stands on (anonymous nodes have no
224/// variable to look up), and the ordered vertex / edge trail (for
225/// `p = (...)` path variables).
226#[derive(Debug, Clone)]
227struct MatchState {
228    row: BindingRow,
229    position: Option<Vertex>,
230    trail: Vec<Value>,
231}
232
233impl<'a, G: GraphStore> CypherExecutor<'a, G> {
234    pub fn new(store: &'a G, graph: &'a str) -> Self {
235        Self {
236            store,
237            graph,
238            params: BTreeMap::new(),
239        }
240    }
241
242    pub fn with_params(mut self, params: BTreeMap<String, Value>) -> Self {
243        self.params = params;
244        self
245    }
246
247    pub fn execute(
248        &self,
249        query: &CypherQuery,
250    ) -> Result<(Vec<String>, Vec<ResultRow>), CypherError> {
251        let mut bindings: Vec<BindingRow> = vec![BTreeMap::new()];
252        let mut columns: Vec<String> = Vec::new();
253        let mut rows: Vec<ResultRow> = Vec::new();
254        for clause in &query.clauses {
255            match clause {
256                CypherClause::Match(m) => {
257                    bindings = self.exec_match(m, &bindings)?;
258                }
259                CypherClause::With(w) => {
260                    let (cols, projected) = self.exec_return_like(
261                        &w.items,
262                        w.distinct,
263                        w.order_by.as_deref(),
264                        w.skip.as_ref(),
265                        w.limit.as_ref(),
266                        &bindings,
267                    )?;
268                    let mut next = Vec::with_capacity(projected.len());
269                    for row in projected {
270                        if let Some(filter) = &w.r#where {
271                            if !self.where_passes(filter, &row)? {
272                                continue;
273                            }
274                        }
275                        next.push(Self::row_to_bindings(&cols, &row));
276                    }
277                    bindings = next;
278                }
279                CypherClause::Return(r) => {
280                    let (cols, ret_rows) = self.exec_return_like(
281                        &r.items,
282                        r.distinct,
283                        r.order_by.as_deref(),
284                        r.skip.as_ref(),
285                        r.limit.as_ref(),
286                        &bindings,
287                    )?;
288                    columns = cols;
289                    rows = ret_rows;
290                }
291                CypherClause::Unwind(clause) => {
292                    bindings = self.exec_unwind(clause, bindings)?;
293                }
294                CypherClause::Create(_)
295                | CypherClause::Merge(_)
296                | CypherClause::Set(_)
297                | CypherClause::Delete(_) => {
298                    return Err(CypherError::Unsupported(format!("{clause:?}")));
299                }
300            }
301        }
302        Ok((columns, rows))
303    }
304
305    pub(crate) fn row_to_bindings(cols: &[String], row: &ResultRow) -> BindingRow {
306        let mut out = BindingRow::new();
307        for col in cols {
308            if let Some(v) = row.get(col) {
309                out.insert(col.clone(), Binding::Value(v.clone()));
310            }
311        }
312        out
313    }
314
315    pub(crate) fn exec_unwind(
316        &self,
317        clause: &UnwindClause,
318        bindings: Vec<BindingRow>,
319    ) -> Result<Vec<BindingRow>, CypherError> {
320        let mut next = Vec::new();
321        for row in bindings {
322            let items = match self.eval(&clause.expr, &row)? {
323                Value::List(items) => items,
324                Value::Null => continue,
325                other => vec![other],
326            };
327            for item in items {
328                let mut new_row = row.clone();
329                new_row.insert(clause.variable.clone(), Binding::Value(item));
330                next.push(new_row);
331            }
332        }
333        Ok(next)
334    }
335
336    // ------------------------------------------------------------------
337    // MATCH
338    // ------------------------------------------------------------------
339}
340
341mod expression;
342mod functions;
343mod helpers;
344mod matching;
345mod projection;
346
347use helpers::{
348    aggregate_avg, aggregate_extreme, aggregate_sum, agtype_add, agtype_div, agtype_mod,
349    agtype_pow, domain_float_fn, float_fn, is_aggregate, is_aggregate_name, null_or_bool,
350    numeric_op, pattern_variables, regex_match, return_label, sort_keyed, str_predicate, string_fn,
351    unsupported_argument, validated_path_elements,
352};