Skip to main content

khive_query/
validate.rs

1//! AST validation and relation normalization.
2
3use std::collections::HashSet;
4use std::str::FromStr;
5
6use khive_types::EdgeRelation;
7
8use crate::ast::{
9    CompareOp, Condition, ConditionValue, GqlQuery, MatchPattern, PatternElement, PropertyRef,
10    WhereExpr,
11};
12use crate::error::QueryError;
13
14/// Closed synthetic relation set handled outside the canonical edge enum.
15pub(crate) const SYNTHETIC_RELATIONS: &[&str] = &[
16    "observed_as_candidate",
17    "observed_as_selected",
18    "observed_as_target",
19    "observed_as_signal",
20];
21
22/// Maximum accepted traversal depth, in hops.
23pub const MAX_DEPTH: usize = 10;
24
25/// Validates and normalizes `query` in place.
26///
27/// # Errors
28///
29/// Returns [`QueryError::Validation`] for structural or taxonomy violations and
30/// [`QueryError::InvalidInput`] for hop bounds above [`MAX_DEPTH`].
31/// See `crates/khive-query/docs/api/validation.md` for the full rule set.
32pub fn validate(query: &mut GqlQuery) -> Result<(), QueryError> {
33    validate_with_warnings(query).map(|_| ())
34}
35
36/// Validates that a non-empty pattern alternates node/edge/node.
37///
38/// # Errors
39///
40/// Returns [`QueryError::Validation`] for an even-length or misordered pattern.
41pub fn validate_pattern_shape(elements: &[PatternElement]) -> Result<(), QueryError> {
42    if elements.is_empty() {
43        // Compilation owns the more specific empty-pattern diagnostic.
44        return Ok(());
45    }
46    if elements.len().is_multiple_of(2) {
47        return Err(QueryError::Validation(
48            "pattern must alternate Node, Edge, Node, … (even element count is invalid)".into(),
49        ));
50    }
51    for (i, element) in elements.iter().enumerate() {
52        match (i % 2, element) {
53            (0, PatternElement::Node(_)) => {}
54            (1, PatternElement::Edge(_)) => {}
55            _ => {
56                return Err(QueryError::Validation(
57                    "pattern must alternate Node, Edge, Node, … (wrong element type at position)"
58                        .into(),
59                ))
60            }
61        }
62    }
63    Ok(())
64}
65
66/// Validates and normalizes `query`, returning non-fatal diagnostics.
67///
68/// # Errors
69///
70/// Returns the same errors as [`validate`].
71/// See `crates/khive-query/docs/api/validation.md` for mutation and warning behavior.
72pub fn validate_with_warnings(query: &mut GqlQuery) -> Result<Vec<String>, QueryError> {
73    let warnings: Vec<String> = Vec::new();
74
75    validate_bindings_and_connectivity(query)?;
76    let multiple_patterns = !query.additional_patterns.is_empty();
77
78    for element in query
79        .patterns_mut()
80        .flat_map(|pattern| &mut pattern.elements)
81    {
82        match element {
83            PatternElement::Node(node) => {
84                if node.properties.contains_key("namespace") {
85                    return Err(QueryError::Validation(
86                        "namespace is set by CompileOptions, not query text".into(),
87                    ));
88                }
89            }
90            PatternElement::Edge(edge) => {
91                for relation in edge.relations.iter_mut() {
92                    // Synthetic projections are closed but intentionally outside EdgeRelation.
93                    if relation.starts_with("observed_as_") {
94                        if !SYNTHETIC_RELATIONS.contains(&relation.as_str()) {
95                            return Err(QueryError::Validation(format!(
96                                "unknown synthetic relation '{relation}'; valid synthetic relations: {}",
97                                SYNTHETIC_RELATIONS.join(", ")
98                            )));
99                        }
100                        continue;
101                    }
102                    let parsed = EdgeRelation::from_str(relation)
103                        .map_err(|err| QueryError::Validation(err.to_string()))?;
104                    *relation = parsed.as_str().to_string();
105                }
106                // Never rewrite inverted ranges; doing so changes query semantics.
107                if edge.min_hops > edge.max_hops {
108                    return Err(QueryError::Validation(format!(
109                        "invalid hop range: min {} > max {}",
110                        edge.min_hops, edge.max_hops
111                    )));
112                }
113                if edge.min_hops > MAX_DEPTH {
114                    return Err(QueryError::Unsupported(format!(
115                        "minimum hop count {} exceeds depth cap {}",
116                        edge.min_hops, MAX_DEPTH
117                    )));
118                }
119                if edge.max_hops > MAX_DEPTH {
120                    return Err(QueryError::InvalidInput(format!(
121                        "max_hops {} exceeds the depth cap of {}; reduce the range or use a smaller bound",
122                        edge.max_hops, MAX_DEPTH
123                    )));
124                }
125                if multiple_patterns
126                    && (edge.min_hops != 1
127                        || edge.max_hops != 1
128                        || edge
129                            .relations
130                            .iter()
131                            .any(|r| SYNTHETIC_RELATIONS.contains(&r.as_str())))
132                {
133                    return Err(QueryError::Unsupported(
134                        "comma-separated MATCH requires canonical fixed one-hop edges".into(),
135                    ));
136                }
137            }
138        }
139    }
140
141    // Check the sum only after every edge's existing range/taxonomy checks, so
142    // their established diagnostics retain precedence. Normalized 1..1 is fixed.
143    let variable_maximum = query
144        .pattern
145        .edges()
146        .filter(|edge| edge.min_hops != 1 || edge.max_hops != 1)
147        .try_fold(0usize, |total, edge| total.checked_add(edge.max_hops))
148        .ok_or_else(|| {
149            QueryError::InvalidInput(format!(
150                "sum of variable-segment maximum hops exceeds the depth cap of {MAX_DEPTH}"
151            ))
152        })?;
153    if variable_maximum > MAX_DEPTH {
154        return Err(QueryError::InvalidInput(format!(
155            "sum of variable-segment maximum hops {variable_maximum} exceeds the depth cap of {MAX_DEPTH}; fixed steps do not count toward this sum"
156        )));
157    }
158    if query.pattern.has_variable_length()
159        && query.pattern.edges().count() > 1
160        && query.pattern.edges().any(|edge| {
161            edge.relations
162                .iter()
163                .any(|relation| SYNTHETIC_RELATIONS.contains(&relation.as_str()))
164        })
165    {
166        return Err(QueryError::Unsupported(
167            "mixed variable-length paths require canonical edges; synthetic observed_as_* edges are not supported".into(),
168        ));
169    }
170
171    // Taxonomy-sensitive property names apply only to their matching binding kind.
172    let mut var_kinds: std::collections::HashMap<String, VarKind> =
173        std::collections::HashMap::new();
174    for element in query.patterns().flat_map(|pattern| &pattern.elements) {
175        match element {
176            PatternElement::Node(n) => {
177                if let Some(v) = n.variable.as_deref() {
178                    var_kinds.insert(v.to_owned(), VarKind::Node);
179                }
180            }
181            PatternElement::Edge(e) => {
182                if let Some(v) = e.variable.as_deref() {
183                    let kind = if e
184                        .relations
185                        .iter()
186                        .any(|r| SYNTHETIC_RELATIONS.contains(&r.as_str()))
187                    {
188                        VarKind::SyntheticEdge
189                    } else {
190                        VarKind::Edge
191                    };
192                    var_kinds.insert(v.to_owned(), kind);
193                }
194            }
195        }
196    }
197
198    validate_absence_expr(&mut query.where_clause, &var_kinds)?;
199
200    let mut validate_err: Option<QueryError> = None;
201    query.where_clause.for_each_condition_mut(&mut |cond| {
202        if validate_err.is_some() {
203            return;
204        }
205        let kind = var_kinds
206            .get(cond.variable.as_str())
207            .copied()
208            .unwrap_or(VarKind::Node);
209        if let PropertyRef::MetadataPath(_) = &cond.property {
210            if kind != VarKind::Edge {
211                validate_err = Some(QueryError::Validation(
212                    "metadata paths require a canonical edge binding".into(),
213                ));
214                return;
215            }
216        }
217        let is_edge = matches!(kind, VarKind::Edge | VarKind::SyntheticEdge);
218        if let Err(e) = validate_condition(cond, is_edge) {
219            validate_err = Some(e);
220        }
221    });
222    if let Some(e) = validate_err {
223        return Err(e);
224    }
225
226    for item in &query.order_by {
227        let kind = var_kinds.get(item.variable.as_str()).ok_or_else(|| {
228            QueryError::Validation(format!("unknown variable '{}' in ORDER BY", item.variable))
229        })?;
230        match &item.property {
231            PropertyRef::Field(field) if field == "namespace" => {
232                return Err(QueryError::Validation(
233                    "namespace is set by CompileOptions, not query text".into(),
234                ));
235            }
236            PropertyRef::Field(field) if matches!(field.as_str(), "properties" | "metadata") => {
237                return Err(QueryError::Validation(
238                    "ORDER BY requires a JSON path, not a properties or metadata container".into(),
239                ));
240            }
241            PropertyRef::MetadataPath(_) if *kind != VarKind::Edge => {
242                return Err(QueryError::Validation(
243                    "metadata paths require a canonical edge binding".into(),
244                ));
245            }
246            _ => {}
247        }
248    }
249
250    Ok(warnings)
251}
252
253/// Validate local path bindings without exposing them to the outer scalar walkers.
254fn validate_absence_expr(
255    expr: &mut WhereExpr,
256    outer: &std::collections::HashMap<String, VarKind>,
257) -> Result<(), QueryError> {
258    match expr {
259        WhereExpr::NotExists(pattern) => validate_absence_pattern(pattern, outer),
260        WhereExpr::And(left, right) | WhereExpr::Or(left, right) => {
261            validate_absence_expr(left, outer)?;
262            validate_absence_expr(right, outer)
263        }
264        WhereExpr::True | WhereExpr::Condition(_) => Ok(()),
265    }
266}
267
268fn validate_absence_pattern(
269    pattern: &mut MatchPattern,
270    outer: &std::collections::HashMap<String, VarKind>,
271) -> Result<(), QueryError> {
272    if pattern.elements.is_empty() {
273        return Err(QueryError::Validation(
274            "NOT EXISTS requires a nonempty path".into(),
275        ));
276    }
277    validate_pattern_shape(&pattern.elements)?;
278    let mut nodes = HashSet::new();
279    let mut edges = HashSet::new();
280    let mut correlated = false;
281    for element in &mut pattern.elements {
282        match element {
283            PatternElement::Node(node) => {
284                if node.properties.contains_key("namespace") {
285                    return Err(QueryError::Validation(
286                        "namespace is set by CompileOptions, not query text".into(),
287                    ));
288                }
289                if let Some(var) = node.variable.as_deref() {
290                    if edges.contains(var)
291                        || outer.get(var).is_some_and(|kind| *kind != VarKind::Node)
292                    {
293                        return Err(QueryError::Validation(format!(
294                            "variable '{var}' cannot bind both a node and an edge in NOT EXISTS"
295                        )));
296                    }
297                    if !nodes.insert(var.to_owned()) {
298                        return Err(QueryError::Unsupported(format!(
299                            "repeated node variable '{var}' in NOT EXISTS is not supported"
300                        )));
301                    }
302                    correlated |= outer.get(var) == Some(&VarKind::Node);
303                }
304            }
305            PatternElement::Edge(edge) => {
306                if let Some(var) = edge.variable.as_deref() {
307                    if let Some(kind) = outer.get(var) {
308                        if *kind != VarKind::Node {
309                            return Err(QueryError::Validation(format!(
310                                "edge variable '{var}' is already bound outside; edge variables are not correlated into NOT EXISTS"
311                            )));
312                        }
313                        return Err(QueryError::Validation(format!(
314                            "variable '{var}' cannot bind both a node and an edge in NOT EXISTS"
315                        )));
316                    }
317                    if nodes.contains(var) {
318                        return Err(QueryError::Validation(format!(
319                            "variable '{var}' cannot bind both a node and an edge in NOT EXISTS"
320                        )));
321                    }
322                    if !edges.insert(var.to_owned()) {
323                        return Err(QueryError::Unsupported(format!(
324                            "repeated edge variable '{var}' in NOT EXISTS is not supported"
325                        )));
326                    }
327                }
328                if edge.min_hops != 1 || edge.max_hops != 1 {
329                    return Err(QueryError::Unsupported(
330                        "NOT EXISTS requires canonical fixed one-hop edges".into(),
331                    ));
332                }
333                for relation in &mut edge.relations {
334                    if relation.starts_with("observed_as_") {
335                        return Err(QueryError::Unsupported(
336                            "synthetic edges are not supported inside NOT EXISTS".into(),
337                        ));
338                    }
339                    let parsed = EdgeRelation::from_str(relation)
340                        .map_err(|err| QueryError::Validation(err.to_string()))?;
341                    *relation = parsed.as_str().to_owned();
342                }
343            }
344        }
345    }
346    if !correlated {
347        return Err(QueryError::Validation(
348            "NOT EXISTS requires a correlated outer node variable".into(),
349        ));
350    }
351    Ok(())
352}
353
354/// Preserve within-path binding rules and connect all comma components by named nodes.
355fn validate_bindings_and_connectivity(query: &GqlQuery) -> Result<(), QueryError> {
356    let mut seen_node_vars: HashSet<&str> = HashSet::new();
357    let mut seen_edge_vars: HashSet<&str> = HashSet::new();
358    let mut path_vars = Vec::new();
359    for (path_index, pattern) in query.patterns().enumerate() {
360        if path_index > 0 && pattern.elements.is_empty() {
361            return Err(QueryError::Validation(
362                "empty additional MATCH pattern".into(),
363            ));
364        }
365        validate_pattern_shape(&pattern.elements)?;
366        let mut local_node_vars = HashSet::new();
367        for element in &pattern.elements {
368            match element {
369                PatternElement::Node(node) => {
370                    if let Some(var) = node.variable.as_deref() {
371                        if seen_edge_vars.contains(var) {
372                            return Err(QueryError::Validation(format!(
373                                "variable '{var}' cannot bind both a node and an edge"
374                            )));
375                        }
376                        if !local_node_vars.insert(var) {
377                            return Err(QueryError::Unsupported(format!(
378                                "repeated node variable '{var}' (cycle / self-reachability \
379                                 requires alias-equality predicates not yet implemented)"
380                            )));
381                        }
382                        seen_node_vars.insert(var);
383                    }
384                }
385                PatternElement::Edge(edge) => {
386                    if let Some(var) = edge.variable.as_deref() {
387                        if seen_node_vars.contains(var) {
388                            return Err(QueryError::Validation(format!(
389                                "variable '{var}' cannot bind both a node and an edge"
390                            )));
391                        }
392                        if !seen_edge_vars.insert(var) {
393                            return Err(QueryError::Unsupported(format!(
394                                "repeated edge variable '{var}' not supported"
395                            )));
396                        }
397                    }
398                }
399            }
400        }
401        path_vars.push(local_node_vars);
402    }
403
404    if path_vars.len() > 1 {
405        // A later path can bridge earlier components; textual adjacency is not required.
406        let mut reached = vec![false; path_vars.len()];
407        reached[0] = true;
408        let mut names = path_vars[0].clone();
409        loop {
410            let mut changed = false;
411            for (index, vars) in path_vars.iter().enumerate() {
412                if !reached[index] && !names.is_disjoint(vars) {
413                    reached[index] = true;
414                    names.extend(vars.iter().copied());
415                    changed = true;
416                }
417            }
418            if !changed {
419                break;
420            }
421        }
422        if reached.iter().any(|connected| !connected) {
423            return Err(QueryError::Unsupported(
424                "comma-separated MATCH patterns must be connected through shared named nodes"
425                    .into(),
426            ));
427        }
428    }
429    Ok(())
430}
431
432#[derive(Clone, Copy, PartialEq, Eq)]
433enum VarKind {
434    Node,
435    Edge,
436    SyntheticEdge,
437}
438
439fn validate_condition(cond: &mut Condition, is_edge: bool) -> Result<(), QueryError> {
440    match &cond.property {
441        PropertyRef::Field(property) if property == "namespace" => Err(QueryError::Validation(
442            "namespace is set by CompileOptions, not query text".into(),
443        )),
444        PropertyRef::Field(property) if property == "kind" && !is_edge => Ok(()),
445        PropertyRef::Field(property) if property == "relation" && is_edge => {
446            let normalize = |s: &mut String| -> Result<(), QueryError> {
447                let parsed = EdgeRelation::from_str(s)
448                    .map_err(|err| QueryError::Validation(err.to_string()))?;
449                *s = parsed.as_str().to_string();
450                Ok(())
451            };
452            if matches!(
453                cond.op,
454                CompareOp::Contains
455                    | CompareOp::StartsWith
456                    | CompareOp::IsNotNull
457                    | CompareOp::IsNull
458            ) {
459                return Ok(());
460            }
461            match &mut cond.value {
462                ConditionValue::String(s) => normalize(s)?,
463                ConditionValue::List(values) => {
464                    for value in values {
465                        match value {
466                            ConditionValue::String(s) => normalize(s)?,
467                            _ => {
468                                return Err(QueryError::Validation(
469                                    "relation IN list values must be strings".into(),
470                                ));
471                            }
472                        }
473                    }
474                }
475                _ => {}
476            }
477            Ok(())
478        }
479        _ => Ok(()),
480    }
481}
482
483#[cfg(test)]
484#[path = "validate_tests.rs"]
485mod tests;