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`), and `WITH`. 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, 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}
110
111impl From<crate::cypher::parser::ParseError> for CypherError {
112    fn from(err: crate::cypher::parser::ParseError) -> Self {
113        CypherError::Parse(err.to_string())
114    }
115}
116
117impl From<agtype::AgtypeConversionError> for CypherError {
118    fn from(err: agtype::AgtypeConversionError) -> Self {
119        CypherError::Storage(err.to_string())
120    }
121}
122
123impl From<crate::store::GraphStoreError> for CypherError {
124    fn from(err: crate::store::GraphStoreError) -> Self {
125        CypherError::Storage(err.to_string())
126    }
127}
128
129fn boolean_cast_error(value: &Value) -> CypherError {
130    CypherError::TypeError(format!(
131        "cannot cast agtype {} to type boolean",
132        agtype::agtype_type_name(value)
133    ))
134}
135
136/// Strict boolean coercion (AGE): booleans pass through, null is
137/// three-valued unknown, anything else raises a cast error.
138fn strict_bool(value: &Value) -> Result<Option<bool>, CypherError> {
139    match value {
140        Value::Bool(b) => Ok(Some(*b)),
141        Value::Null => Ok(None),
142        other => Err(boolean_cast_error(other)),
143    }
144}
145
146const MAX_EXACT_F64_INTEGER: i64 = 9_007_199_254_740_992;
147
148fn usize_to_i64(value: usize, context: &str) -> Result<i64, CypherError> {
149    i64::try_from(value).map_err(|_| {
150        CypherError::TypeError(format!(
151            "{context} {value} exceeds the agtype integer range"
152        ))
153    })
154}
155
156fn nonnegative_i64_to_usize(value: i64, context: &str) -> Result<usize, CypherError> {
157    if value < 0 {
158        return Err(CypherError::TypeError(format!(
159            "{context} must not be negative, got {value}"
160        )));
161    }
162    usize::try_from(value).map_err(|_| {
163        CypherError::TypeError(format!(
164            "{context} {value} exceeds the platform index range"
165        ))
166    })
167}
168
169fn nonnegative_i64_to_u64(value: i64, context: &str) -> Result<u64, CypherError> {
170    u64::try_from(value)
171        .map_err(|_| CypherError::TypeError(format!("{context} must not be negative, got {value}")))
172}
173
174fn exact_i64_to_f64(value: i64, context: &str) -> Result<f64, CypherError> {
175    if (-MAX_EXACT_F64_INTEGER..=MAX_EXACT_F64_INTEGER).contains(&value) {
176        Ok(value as f64)
177    } else {
178        Err(CypherError::TypeError(format!(
179            "{context} {value} cannot be represented exactly as a float"
180        )))
181    }
182}
183
184fn trunc_f64_to_i64(value: f64, context: &str) -> Result<i64, CypherError> {
185    if !value.is_finite() {
186        return Err(CypherError::TypeError(format!(
187            "{context} must be finite, got {value}"
188        )));
189    }
190    let truncated = value.trunc();
191    if !(-9_223_372_036_854_775_808.0..9_223_372_036_854_775_808.0).contains(&truncated) {
192        return Err(CypherError::TypeError(format!(
193            "{context} {value} is outside the agtype integer range"
194        )));
195    }
196    Ok(truncated as i64)
197}
198
199/// Read-only execution context.
200pub struct CypherExecutor<'a, G: GraphStore> {
201    pub store: &'a G,
202    pub graph: &'a str,
203    pub params: BTreeMap<String, Value>,
204}
205
206/// Intermediate state while a path pattern binds: the row so far, the
207/// vertex the pattern currently stands on (anonymous nodes have no
208/// variable to look up), and the ordered vertex / edge trail (for
209/// `p = (...)` path variables).
210#[derive(Debug, Clone)]
211struct MatchState {
212    row: BindingRow,
213    position: Option<Vertex>,
214    trail: Vec<Value>,
215}
216
217impl<'a, G: GraphStore> CypherExecutor<'a, G> {
218    pub fn new(store: &'a G, graph: &'a str) -> Self {
219        Self {
220            store,
221            graph,
222            params: BTreeMap::new(),
223        }
224    }
225
226    pub fn with_params(mut self, params: BTreeMap<String, Value>) -> Self {
227        self.params = params;
228        self
229    }
230
231    pub fn execute(
232        &self,
233        query: &CypherQuery,
234    ) -> Result<(Vec<String>, Vec<ResultRow>), CypherError> {
235        let mut bindings: Vec<BindingRow> = vec![BTreeMap::new()];
236        let mut columns: Vec<String> = Vec::new();
237        let mut rows: Vec<ResultRow> = Vec::new();
238        for clause in &query.clauses {
239            match clause {
240                CypherClause::Match(m) => {
241                    bindings = self.exec_match(m, &bindings)?;
242                }
243                CypherClause::With(w) => {
244                    let (cols, projected) = self.exec_return_like(
245                        &w.items,
246                        w.distinct,
247                        w.order_by.as_deref(),
248                        w.skip.as_ref(),
249                        w.limit.as_ref(),
250                        &bindings,
251                    )?;
252                    let mut next = Vec::with_capacity(projected.len());
253                    for row in projected {
254                        if let Some(filter) = &w.r#where {
255                            if !self.where_passes(filter, &row)? {
256                                continue;
257                            }
258                        }
259                        next.push(Self::row_to_bindings(&cols, &row));
260                    }
261                    bindings = next;
262                }
263                CypherClause::Return(r) => {
264                    let (cols, ret_rows) = self.exec_return_like(
265                        &r.items,
266                        r.distinct,
267                        r.order_by.as_deref(),
268                        r.skip.as_ref(),
269                        r.limit.as_ref(),
270                        &bindings,
271                    )?;
272                    columns = cols;
273                    rows = ret_rows;
274                }
275                CypherClause::Create(_)
276                | CypherClause::Merge(_)
277                | CypherClause::Set(_)
278                | CypherClause::Delete(_)
279                | CypherClause::Unwind(_) => {
280                    return Err(CypherError::Unsupported(format!("{clause:?}")));
281                }
282            }
283        }
284        Ok((columns, rows))
285    }
286
287    pub(crate) fn row_to_bindings(cols: &[String], row: &ResultRow) -> BindingRow {
288        let mut out = BindingRow::new();
289        for col in cols {
290            if let Some(v) = row.get(col) {
291                out.insert(col.clone(), Binding::Value(v.clone()));
292            }
293        }
294        out
295    }
296
297    // ------------------------------------------------------------------
298    // MATCH
299    // ------------------------------------------------------------------
300}
301
302mod expression;
303mod functions;
304mod helpers;
305mod matching;
306mod projection;
307
308use helpers::{
309    aggregate_avg, aggregate_extreme, aggregate_sum, agtype_add, agtype_div, agtype_mod,
310    agtype_pow, domain_float_fn, float_fn, is_aggregate, is_aggregate_name, null_or_bool,
311    numeric_op, pattern_variables, regex_match, return_label, sort_keyed, str_predicate, string_fn,
312    unsupported_argument, validated_path_elements,
313};
uqa_graph/cypher/executor.rs

uqa_graph/cypher/
executor.rs
