1use 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
14pub(crate) const SYNTHETIC_RELATIONS: &[&str] = &[
16 "observed_as_candidate",
17 "observed_as_selected",
18 "observed_as_target",
19 "observed_as_signal",
20];
21
22pub const MAX_DEPTH: usize = 10;
24
25pub fn validate(query: &mut GqlQuery) -> Result<(), QueryError> {
33 validate_with_warnings(query).map(|_| ())
34}
35
36pub fn validate_pattern_shape(elements: &[PatternElement]) -> Result<(), QueryError> {
42 if elements.is_empty() {
43 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
66pub 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 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 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 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 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
253fn 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
354fn 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 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;