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::{CompareOp, Condition, ConditionValue, GqlQuery, PatternElement, PropertyRef};
9use crate::error::QueryError;
10
11/// Closed synthetic relation set handled outside the canonical edge enum.
12pub(crate) const SYNTHETIC_RELATIONS: &[&str] = &[
13    "observed_as_candidate",
14    "observed_as_selected",
15    "observed_as_target",
16    "observed_as_signal",
17];
18
19/// Maximum accepted traversal depth, in hops.
20pub const MAX_DEPTH: usize = 10;
21
22/// Validates and normalizes `query` in place.
23///
24/// # Errors
25///
26/// Returns [`QueryError::Validation`] for structural or taxonomy violations and
27/// [`QueryError::InvalidInput`] for hop bounds above [`MAX_DEPTH`].
28/// See `crates/khive-query/docs/api/validation.md` for the full rule set.
29pub fn validate(query: &mut GqlQuery) -> Result<(), QueryError> {
30    validate_with_warnings(query).map(|_| ())
31}
32
33/// Validates that a non-empty pattern alternates node/edge/node.
34///
35/// # Errors
36///
37/// Returns [`QueryError::Validation`] for an even-length or misordered pattern.
38pub fn validate_pattern_shape(elements: &[PatternElement]) -> Result<(), QueryError> {
39    if elements.is_empty() {
40        // Compilation owns the more specific empty-pattern diagnostic.
41        return Ok(());
42    }
43    if elements.len().is_multiple_of(2) {
44        return Err(QueryError::Validation(
45            "pattern must alternate Node, Edge, Node, … (even element count is invalid)".into(),
46        ));
47    }
48    for (i, element) in elements.iter().enumerate() {
49        match (i % 2, element) {
50            (0, PatternElement::Node(_)) => {}
51            (1, PatternElement::Edge(_)) => {}
52            _ => {
53                return Err(QueryError::Validation(
54                    "pattern must alternate Node, Edge, Node, … (wrong element type at position)"
55                        .into(),
56                ))
57            }
58        }
59    }
60    Ok(())
61}
62
63/// Validates and normalizes `query`, returning non-fatal diagnostics.
64///
65/// # Errors
66///
67/// Returns the same errors as [`validate`].
68/// See `crates/khive-query/docs/api/validation.md` for mutation and warning behavior.
69pub fn validate_with_warnings(query: &mut GqlQuery) -> Result<Vec<String>, QueryError> {
70    let warnings: Vec<String> = Vec::new();
71
72    validate_bindings_and_connectivity(query)?;
73    let multiple_patterns = !query.additional_patterns.is_empty();
74
75    for element in query
76        .patterns_mut()
77        .flat_map(|pattern| &mut pattern.elements)
78    {
79        match element {
80            PatternElement::Node(node) => {
81                if node.properties.contains_key("namespace") {
82                    return Err(QueryError::Validation(
83                        "namespace is set by CompileOptions, not query text".into(),
84                    ));
85                }
86            }
87            PatternElement::Edge(edge) => {
88                for relation in edge.relations.iter_mut() {
89                    // Synthetic projections are closed but intentionally outside EdgeRelation.
90                    if relation.starts_with("observed_as_") {
91                        if !SYNTHETIC_RELATIONS.contains(&relation.as_str()) {
92                            return Err(QueryError::Validation(format!(
93                                "unknown synthetic relation '{relation}'; valid synthetic relations: {}",
94                                SYNTHETIC_RELATIONS.join(", ")
95                            )));
96                        }
97                        continue;
98                    }
99                    let parsed = EdgeRelation::from_str(relation)
100                        .map_err(|err| QueryError::Validation(err.to_string()))?;
101                    *relation = parsed.as_str().to_string();
102                }
103                if edge.min_hops == 0 {
104                    return Err(QueryError::Unsupported(
105                        "zero-hop ranges (min_hops = 0) not yet supported; \
106                         use a minimum of 1 hop"
107                            .into(),
108                    ));
109                }
110                // Never rewrite inverted ranges; doing so changes query semantics.
111                if edge.min_hops > edge.max_hops {
112                    return Err(QueryError::Validation(format!(
113                        "invalid hop range: min {} > max {}",
114                        edge.min_hops, edge.max_hops
115                    )));
116                }
117                if edge.min_hops > MAX_DEPTH {
118                    return Err(QueryError::Unsupported(format!(
119                        "minimum hop count {} exceeds depth cap {}",
120                        edge.min_hops, MAX_DEPTH
121                    )));
122                }
123                if edge.max_hops > MAX_DEPTH {
124                    return Err(QueryError::InvalidInput(format!(
125                        "max_hops {} exceeds the depth cap of {}; reduce the range or use a smaller bound",
126                        edge.max_hops, MAX_DEPTH
127                    )));
128                }
129                if multiple_patterns
130                    && (edge.min_hops != 1
131                        || edge.max_hops != 1
132                        || edge
133                            .relations
134                            .iter()
135                            .any(|r| SYNTHETIC_RELATIONS.contains(&r.as_str())))
136                {
137                    return Err(QueryError::Unsupported(
138                        "comma-separated MATCH requires canonical fixed one-hop edges".into(),
139                    ));
140                }
141            }
142        }
143    }
144
145    // Taxonomy-sensitive property names apply only to their matching binding kind.
146    let mut var_kinds: std::collections::HashMap<String, VarKind> =
147        std::collections::HashMap::new();
148    for element in query.patterns().flat_map(|pattern| &pattern.elements) {
149        match element {
150            PatternElement::Node(n) => {
151                if let Some(v) = n.variable.as_deref() {
152                    var_kinds.insert(v.to_owned(), VarKind::Node);
153                }
154            }
155            PatternElement::Edge(e) => {
156                if let Some(v) = e.variable.as_deref() {
157                    let kind = if e
158                        .relations
159                        .iter()
160                        .any(|r| SYNTHETIC_RELATIONS.contains(&r.as_str()))
161                    {
162                        VarKind::SyntheticEdge
163                    } else {
164                        VarKind::Edge
165                    };
166                    var_kinds.insert(v.to_owned(), kind);
167                }
168            }
169        }
170    }
171
172    let mut validate_err: Option<QueryError> = None;
173    query.where_clause.for_each_condition_mut(&mut |cond| {
174        if validate_err.is_some() {
175            return;
176        }
177        let kind = var_kinds
178            .get(cond.variable.as_str())
179            .copied()
180            .unwrap_or(VarKind::Node);
181        if let PropertyRef::MetadataPath(_) = &cond.property {
182            if kind != VarKind::Edge {
183                validate_err = Some(QueryError::Validation(
184                    "metadata paths require a canonical edge binding".into(),
185                ));
186                return;
187            }
188        }
189        let is_edge = matches!(kind, VarKind::Edge | VarKind::SyntheticEdge);
190        if let Err(e) = validate_condition(cond, is_edge) {
191            validate_err = Some(e);
192        }
193    });
194    if let Some(e) = validate_err {
195        return Err(e);
196    }
197
198    for item in &query.order_by {
199        let kind = var_kinds.get(item.variable.as_str()).ok_or_else(|| {
200            QueryError::Validation(format!("unknown variable '{}' in ORDER BY", item.variable))
201        })?;
202        match &item.property {
203            PropertyRef::Field(field) if field == "namespace" => {
204                return Err(QueryError::Validation(
205                    "namespace is set by CompileOptions, not query text".into(),
206                ));
207            }
208            PropertyRef::Field(field) if matches!(field.as_str(), "properties" | "metadata") => {
209                return Err(QueryError::Validation(
210                    "ORDER BY requires a JSON path, not a properties or metadata container".into(),
211                ));
212            }
213            PropertyRef::MetadataPath(_) if *kind != VarKind::Edge => {
214                return Err(QueryError::Validation(
215                    "metadata paths require a canonical edge binding".into(),
216                ));
217            }
218            _ => {}
219        }
220    }
221
222    Ok(warnings)
223}
224
225/// Preserve within-path binding rules and connect all comma components by named nodes.
226fn validate_bindings_and_connectivity(query: &GqlQuery) -> Result<(), QueryError> {
227    let mut seen_node_vars: HashSet<&str> = HashSet::new();
228    let mut seen_edge_vars: HashSet<&str> = HashSet::new();
229    let mut path_vars = Vec::new();
230    for (path_index, pattern) in query.patterns().enumerate() {
231        if path_index > 0 && pattern.elements.is_empty() {
232            return Err(QueryError::Validation(
233                "empty additional MATCH pattern".into(),
234            ));
235        }
236        validate_pattern_shape(&pattern.elements)?;
237        let mut local_node_vars = HashSet::new();
238        for element in &pattern.elements {
239            match element {
240                PatternElement::Node(node) => {
241                    if let Some(var) = node.variable.as_deref() {
242                        if seen_edge_vars.contains(var) {
243                            return Err(QueryError::Validation(format!(
244                                "variable '{var}' cannot bind both a node and an edge"
245                            )));
246                        }
247                        if !local_node_vars.insert(var) {
248                            return Err(QueryError::Unsupported(format!(
249                                "repeated node variable '{var}' (cycle / self-reachability \
250                                 requires alias-equality predicates not yet implemented)"
251                            )));
252                        }
253                        seen_node_vars.insert(var);
254                    }
255                }
256                PatternElement::Edge(edge) => {
257                    if let Some(var) = edge.variable.as_deref() {
258                        if seen_node_vars.contains(var) {
259                            return Err(QueryError::Validation(format!(
260                                "variable '{var}' cannot bind both a node and an edge"
261                            )));
262                        }
263                        if !seen_edge_vars.insert(var) {
264                            return Err(QueryError::Unsupported(format!(
265                                "repeated edge variable '{var}' not supported"
266                            )));
267                        }
268                    }
269                }
270            }
271        }
272        path_vars.push(local_node_vars);
273    }
274
275    if path_vars.len() > 1 {
276        // A later path can bridge earlier components; textual adjacency is not required.
277        let mut reached = vec![false; path_vars.len()];
278        reached[0] = true;
279        let mut names = path_vars[0].clone();
280        loop {
281            let mut changed = false;
282            for (index, vars) in path_vars.iter().enumerate() {
283                if !reached[index] && !names.is_disjoint(vars) {
284                    reached[index] = true;
285                    names.extend(vars.iter().copied());
286                    changed = true;
287                }
288            }
289            if !changed {
290                break;
291            }
292        }
293        if reached.iter().any(|connected| !connected) {
294            return Err(QueryError::Unsupported(
295                "comma-separated MATCH patterns must be connected through shared named nodes"
296                    .into(),
297            ));
298        }
299    }
300    Ok(())
301}
302
303#[derive(Clone, Copy, PartialEq, Eq)]
304enum VarKind {
305    Node,
306    Edge,
307    SyntheticEdge,
308}
309
310fn validate_condition(cond: &mut Condition, is_edge: bool) -> Result<(), QueryError> {
311    match &cond.property {
312        PropertyRef::Field(property) if property == "namespace" => Err(QueryError::Validation(
313            "namespace is set by CompileOptions, not query text".into(),
314        )),
315        PropertyRef::Field(property) if property == "kind" && !is_edge => Ok(()),
316        PropertyRef::Field(property) if property == "relation" && is_edge => {
317            let normalize = |s: &mut String| -> Result<(), QueryError> {
318                let parsed = EdgeRelation::from_str(s)
319                    .map_err(|err| QueryError::Validation(err.to_string()))?;
320                *s = parsed.as_str().to_string();
321                Ok(())
322            };
323            if matches!(
324                cond.op,
325                CompareOp::Contains
326                    | CompareOp::StartsWith
327                    | CompareOp::IsNotNull
328                    | CompareOp::IsNull
329            ) {
330                return Ok(());
331            }
332            match &mut cond.value {
333                ConditionValue::String(s) => normalize(s)?,
334                ConditionValue::List(values) => {
335                    for value in values {
336                        match value {
337                            ConditionValue::String(s) => normalize(s)?,
338                            _ => {
339                                return Err(QueryError::Validation(
340                                    "relation IN list values must be strings".into(),
341                                ));
342                            }
343                        }
344                    }
345                }
346                _ => {}
347            }
348            Ok(())
349        }
350        _ => Ok(()),
351    }
352}
353
354#[cfg(test)]
355#[path = "validate_tests.rs"]
356mod tests;