linkrs_query/parser/ast/
pattern.rs

1//! AST Mode Definition (v2)
2//!
3//! AST (Abstract Syntax Tree) definitions related to pattern matching in graph contexts, supporting patterns for nodes, edges, and paths.
4
5use super::types::*;
6use linkrs_core::types::expr::analysis_utils::collect_variables_from_contextual;
7use linkrs_core::types::expr::contextual::ContextualExpression;
8
9/// Pattern Enumeration – Graph Pattern Matching
10#[derive(Debug, Clone, PartialEq)]
11pub enum Pattern {
12    Node(NodePattern),
13    Edge(EdgePattern),
14    Path(PathPattern),
15    Variable(VariablePattern),
16}
17
18impl Pattern {
19    /// Obtaining the location information of the mode
20    pub fn span(&self) -> Span {
21        match self {
22            Pattern::Node(p) => p.span,
23            Pattern::Edge(p) => p.span,
24            Pattern::Path(p) => p.span,
25            Pattern::Variable(p) => p.span,
26        }
27    }
28
29    /// Render a node or path pattern back to canonical source text.
30    ///
31    /// The output re-parses through the traversal parser, which lets callers
32    /// embed a parsed pattern into string-based subquery bodies (e.g. the
33    /// inline pattern predicate rewrite). Returns `None` for shapes without
34    /// a faithful textual form (bare variables, top-level edges,
35    /// alternatives, repetitions, recursive comprehensions).
36    pub fn to_pattern_string(&self) -> Option<String> {
37        match self {
38            Pattern::Node(node) => render_node(node),
39            Pattern::Path(path) => {
40                let mut out = String::new();
41                for element in &path.elements {
42                    match element {
43                        PathElement::Node(node) => out.push_str(&render_node(node)?),
44                        PathElement::Edge(edge) => out.push_str(&render_edge(edge)?),
45                        PathElement::CreateEdge(edge) => out.push_str(&render_create_edge(edge)?),
46                        _ => return None,
47                    }
48                }
49                Some(out)
50            }
51            _ => None,
52        }
53    }
54}
55
56/// Node mode
57#[derive(Debug, Clone, PartialEq)]
58pub struct NodePattern {
59    pub span: Span,
60    pub variable: Option<String>,
61    pub labels: Vec<String>,
62    pub properties: Option<ContextualExpression>,
63    pub predicates: Vec<ContextualExpression>,
64}
65
66impl NodePattern {
67    pub fn new(
68        variable: Option<String>,
69        labels: Vec<String>,
70        properties: Option<ContextualExpression>,
71        predicates: Vec<ContextualExpression>,
72        span: Span,
73    ) -> Self {
74        Self {
75            span,
76            variable,
77            labels,
78            properties,
79            predicates,
80        }
81    }
82}
83
84/// Edge Mode
85#[derive(Debug, Clone, PartialEq)]
86pub struct EdgePattern {
87    pub span: Span,
88    pub variable: Option<String>,
89    pub edge_types: Vec<String>,
90    pub properties: Option<ContextualExpression>,
91    pub predicates: Vec<ContextualExpression>,
92    pub direction: EdgeDirection,
93    pub range: Option<EdgeRange>,
94    pub path_semantic: Option<PathSemantic>,
95    /// Optional recursive comprehension for variable-length patterns with binding
96    pub recursive_comprehension: Option<RecursiveComprehension>,
97}
98
99/// Path semantic types for variable-length patterns
100#[derive(Debug, Clone, PartialEq)]
101pub enum PathSemantic {
102    Walk,                     // * (default, allows repeated nodes/edges)
103    Trail,                    // *TRAIL (no repeated edges)
104    Acyclic,                  // *ACYCLIC (no repeated vertices)
105    Shortest,                 // *SHORTEST
106    AllShortest,              // *ALL SHORTEST
107    WeightedShortest(String), // *WEIGHTED(weight_prop)
108}
109
110impl EdgePattern {
111    pub fn new(
112        variable: Option<String>,
113        edge_types: Vec<String>,
114        properties: Option<ContextualExpression>,
115        predicates: Vec<ContextualExpression>,
116        direction: EdgeDirection,
117        range: Option<EdgeRange>,
118        span: Span,
119    ) -> Self {
120        Self {
121            span,
122            variable,
123            edge_types,
124            properties,
125            predicates,
126            direction,
127            range,
128            path_semantic: None,
129            recursive_comprehension: None,
130        }
131    }
132}
133
134/// Edge hop inside a CREATE data pattern.
135///
136/// Variable-length traversal constructs (`*` ranges, path semantics,
137/// recursive comprehension, predicates) are MATCH-only; the CREATE parser
138/// cannot produce them, so they are absent from this struct by construction
139/// instead of sitting as always-empty placeholder fields.
140#[derive(Debug, Clone, PartialEq)]
141pub struct CreateEdgePattern {
142    pub span: Span,
143    pub variable: Option<String>,
144    pub edge_types: Vec<String>,
145    pub properties: Option<ContextualExpression>,
146    pub direction: EdgeDirection,
147}
148
149/// Border range
150#[derive(Debug, Clone, PartialEq)]
151pub struct EdgeRange {
152    pub min: Option<usize>,
153    pub max: Option<usize>,
154}
155
156impl EdgeRange {
157    pub fn new(min: Option<usize>, max: Option<usize>) -> Self {
158        Self { min, max }
159    }
160
161    pub fn fixed(steps: usize) -> Self {
162        Self {
163            min: Some(steps),
164            max: Some(steps),
165        }
166    }
167
168    pub fn range(min: usize, max: usize) -> Self {
169        Self {
170            min: Some(min),
171            max: Some(max),
172        }
173    }
174
175    pub fn at_least(min: usize) -> Self {
176        Self {
177            min: Some(min),
178            max: None,
179        }
180    }
181
182    pub fn at_most(max: usize) -> Self {
183        Self {
184            min: None,
185            max: Some(max),
186        }
187    }
188
189    pub fn any() -> Self {
190        Self {
191            min: None,
192            max: None,
193        }
194    }
195}
196
197/// Path pattern
198#[derive(Debug, Clone, PartialEq)]
199pub struct PathPattern {
200    pub span: Span,
201    pub elements: Vec<PathElement>,
202    /// Optional path name from `p = <pattern>` binding. Plain patterns
203    /// carry `None`; the planner ignores the name for scan planning and
204    /// the binder exposes it as a path alias in scope.
205    pub name: Option<String>,
206}
207
208impl PathPattern {
209    pub fn new(elements: Vec<PathElement>, span: Span) -> Self {
210        Self {
211            span,
212            elements,
213            name: None,
214        }
215    }
216
217    pub fn with_name(elements: Vec<PathElement>, span: Span, name: String) -> Self {
218        Self {
219            span,
220            elements,
221            name: Some(name),
222        }
223    }
224}
225
226/// Path element
227#[derive(Debug, Clone, PartialEq)]
228pub enum PathElement {
229    Node(NodePattern),
230    Edge(EdgePattern),
231    /// Edge hop produced only by the CREATE data parser.
232    CreateEdge(CreateEdgePattern),
233    Alternative(Vec<Pattern>),
234    Optional(Box<PathElement>),
235    Repeated(Box<PathElement>, RepetitionType),
236    Recursive(RecursiveComprehension),
237}
238
239/// Recursive comprehension for variable-length path queries
240#[derive(Debug, Clone, PartialEq)]
241pub struct RecursiveComprehension {
242    pub span: Span,
243    /// Node variable name (e.g., `v` in `-[e* (v, r | WHERE v.age > 20 | {v.name}, {r.weight})]->`)
244    pub variable: String,
245    /// Edge variable name (e.g., `r` in the same syntax)
246    pub edge_variable: Option<String>,
247    /// Optional filter predicate on each step (e.g., `WHERE v.age > 20`)
248    pub filter_predicate: Option<ContextualExpression>,
249    /// Optional node projection (e.g., `{v.name}`)
250    pub node_projection: Option<ContextualExpression>,
251    /// Optional edge projection (e.g., `{r.weight}`)
252    pub edge_projection: Option<ContextualExpression>,
253}
254
255/// Duplicate type
256#[derive(Debug, Clone, Copy, PartialEq)]
257pub enum RepetitionType {
258    ZeroOrMore,          // *
259    OneOrMore,           // +
260    ZeroOrOne,           // ?
261    Exactly(usize),      // {n}
262    Range(usize, usize), // {n,m}
263}
264
265/// Variable mode
266#[derive(Debug, Clone, PartialEq)]
267pub struct VariablePattern {
268    pub span: Span,
269    pub name: String,
270}
271
272impl VariablePattern {
273    pub fn new(name: String, span: Span) -> Self {
274        Self { span, name }
275    }
276}
277
278/// Render `(var:Label {k: v, ...})`. Property values reuse the core
279/// expression display so literals keep their quoting.
280fn render_node(node: &NodePattern) -> Option<String> {
281    let mut out = String::from("(");
282    if let Some(ref var) = node.variable {
283        out.push_str(var);
284    }
285    for label in &node.labels {
286        out.push(':');
287        out.push_str(label);
288    }
289    if let Some(ref props) = node.properties {
290        out.push_str(&render_properties(props)?);
291    }
292    out.push(')');
293    Some(out)
294}
295
296/// Render the edge segment including its direction arrows, e.g.
297/// `-[e:KNOWS {since: 2020}]->`. A present path semantic overrides the
298/// numeric range exactly like the parser does; an absent range renders no
299/// suffix. Recursive comprehensions have no textual round-trip.
300fn render_edge(edge: &EdgePattern) -> Option<String> {
301    if edge.recursive_comprehension.is_some() {
302        return None;
303    }
304    let mut out = String::new();
305    match edge.direction {
306        EdgeDirection::In => out.push_str("<-"),
307        EdgeDirection::Out | EdgeDirection::Both => out.push('-'),
308    }
309    out.push('[');
310    if let Some(ref var) = edge.variable {
311        out.push_str(var);
312    }
313    for (i, edge_type) in edge.edge_types.iter().enumerate() {
314        if i == 0 {
315            out.push(':');
316        } else {
317            out.push_str("|:");
318        }
319        out.push_str(edge_type);
320    }
321    if let Some(ref props) = edge.properties {
322        out.push_str(&render_properties(props)?);
323    }
324    if let Some(ref semantic) = edge.path_semantic {
325        match semantic {
326            PathSemantic::Walk => {
327                if edge.range.is_some() {
328                    out.push_str(&render_range(edge.range.as_ref())?);
329                }
330            }
331            PathSemantic::Trail => out.push_str("*TRAIL"),
332            PathSemantic::Acyclic => out.push_str("*ACYCLIC"),
333            PathSemantic::Shortest => out.push_str("*SHORTEST"),
334            PathSemantic::AllShortest => out.push_str("*ALL SHORTEST"),
335            PathSemantic::WeightedShortest(weight) => {
336                out.push_str("*WEIGHTED(");
337                out.push_str(weight);
338                out.push(')');
339            }
340        }
341    } else if let Some(ref range) = edge.range {
342        out.push_str(&render_range(Some(range))?);
343    }
344    out.push(']');
345    match edge.direction {
346        EdgeDirection::Out => out.push_str("->"),
347        EdgeDirection::In | EdgeDirection::Both => out.push('-'),
348    }
349    Some(out)
350}
351
352/// Render a CREATE edge hop back to Cypher syntax. Same bracket grammar as
353/// `render_edge` but without the MATCH-only range / path-semantic suffixes.
354fn render_create_edge(edge: &CreateEdgePattern) -> Option<String> {
355    let mut out = String::new();
356    match edge.direction {
357        EdgeDirection::In => out.push_str("<-"),
358        EdgeDirection::Out | EdgeDirection::Both => out.push('-'),
359    }
360    out.push('[');
361    if let Some(ref var) = edge.variable {
362        out.push_str(var);
363    }
364    for (i, edge_type) in edge.edge_types.iter().enumerate() {
365        if i == 0 {
366            out.push(':');
367        } else {
368            out.push_str("|:");
369        }
370        out.push_str(edge_type);
371    }
372    if let Some(ref props) = edge.properties {
373        out.push_str(&render_properties(props)?);
374    }
375    out.push(']');
376    match edge.direction {
377        EdgeDirection::Out => out.push_str("->"),
378        EdgeDirection::In | EdgeDirection::Both => out.push('-'),
379    }
380    Some(out)
381}
382
383/// Render `*`, `*n`, `*a..b`, `*a..`. An open-ended upper bound without a
384/// lower bound has no parser round-trip, so it renders as `*0..b`.
385fn render_range(range: Option<&EdgeRange>) -> Option<String> {
386    let range = range?;
387    let mut out = String::from("*");
388    match (range.min, range.max) {
389        (None, None) => {}
390        (Some(min), Some(max)) if min == max => out.push_str(&min.to_string()),
391        (Some(min), Some(max)) => {
392            out.push_str(&min.to_string());
393            out.push_str("..");
394            out.push_str(&max.to_string());
395        }
396        (Some(min), None) => {
397            out.push_str(&min.to_string());
398            out.push_str("..");
399        }
400        (None, Some(max)) => {
401            out.push_str("0..");
402            out.push_str(&max.to_string());
403        }
404    }
405    Some(out)
406}
407
408/// Render ` {k1: v1, k2: v2}` from a map property expression.
409fn render_properties(props: &ContextualExpression) -> Option<String> {
410    let expr = props.get_expression()?;
411    match expr {
412        linkrs_core::types::expr::Expression::Map(entries) => {
413            let mut out = String::from(" {");
414            for (i, (key, value)) in entries.iter().enumerate() {
415                if i > 0 {
416                    out.push_str(", ");
417                }
418                out.push_str(key);
419                out.push_str(": ");
420                out.push_str(&value.to_expression_string());
421            }
422            out.push('}');
423            Some(out)
424        }
425        _ => None,
426    }
427}
428
429// Pattern Tool Functions
430pub struct PatternUtils;
431impl PatternUtils {
432    /// All variables used in the search pattern
433    pub fn find_variables(pattern: &Pattern) -> Vec<String> {
434        let mut variables = Vec::new();
435        Self::find_variables_recursive(pattern, &mut variables);
436        variables
437    }
438
439    fn find_variables_recursive(pattern: &Pattern, variables: &mut Vec<String>) {
440        match pattern {
441            Pattern::Node(p) => {
442                if let Some(ref var) = p.variable {
443                    variables.push(var.clone());
444                }
445                if let Some(ref props) = p.properties {
446                    variables.extend(collect_variables_from_contextual(props));
447                }
448                for predicate in &p.predicates {
449                    variables.extend(collect_variables_from_contextual(predicate));
450                }
451            }
452            Pattern::Edge(p) => {
453                if let Some(ref var) = p.variable {
454                    variables.push(var.clone());
455                }
456                if let Some(ref props) = p.properties {
457                    variables.extend(collect_variables_from_contextual(props));
458                }
459                for predicate in &p.predicates {
460                    variables.extend(collect_variables_from_contextual(predicate));
461                }
462            }
463            Pattern::Path(p) => {
464                if let Some(ref path_name) = p.name {
465                    variables.push(path_name.clone());
466                }
467                for element in &p.elements {
468                    Self::find_variables_in_element(element, variables);
469                }
470            }
471            Pattern::Variable(p) => {
472                variables.push(p.name.clone());
473            }
474        }
475    }
476
477    fn find_variables_in_element(element: &PathElement, variables: &mut Vec<String>) {
478        match element {
479            PathElement::Node(p) => {
480                if let Some(ref var) = p.variable {
481                    variables.push(var.clone());
482                }
483                if let Some(ref props) = p.properties {
484                    variables.extend(collect_variables_from_contextual(props));
485                }
486                for predicate in &p.predicates {
487                    variables.extend(collect_variables_from_contextual(predicate));
488                }
489            }
490            PathElement::Edge(p) => {
491                if let Some(ref var) = p.variable {
492                    variables.push(var.clone());
493                }
494                if let Some(ref props) = p.properties {
495                    variables.extend(collect_variables_from_contextual(props));
496                }
497                for predicate in &p.predicates {
498                    variables.extend(collect_variables_from_contextual(predicate));
499                }
500            }
501            PathElement::CreateEdge(p) => {
502                if let Some(ref var) = p.variable {
503                    variables.push(var.clone());
504                }
505                if let Some(ref props) = p.properties {
506                    variables.extend(collect_variables_from_contextual(props));
507                }
508            }
509            PathElement::Alternative(patterns) => {
510                for pattern in patterns {
511                    Self::find_variables_recursive(pattern, variables);
512                }
513            }
514            PathElement::Optional(elem) => {
515                Self::find_variables_in_element(elem, variables);
516            }
517            PathElement::Repeated(elem, _) => {
518                Self::find_variables_in_element(elem, variables);
519            }
520            PathElement::Recursive(rc) => {
521                variables.push(rc.variable.clone());
522                if let Some(ref edge_var) = rc.edge_variable {
523                    variables.push(edge_var.clone());
524                }
525                if let Some(ref filter) = rc.filter_predicate {
526                    variables.extend(collect_variables_from_contextual(filter));
527                }
528                if let Some(ref node_proj) = rc.node_projection {
529                    variables.extend(collect_variables_from_contextual(node_proj));
530                }
531                if let Some(ref edge_proj) = rc.edge_projection {
532                    variables.extend(collect_variables_from_contextual(edge_proj));
533                }
534            }
535        }
536    }
537
538    /// Check whether the mode contains any variables.
539    pub fn has_variables(pattern: &Pattern) -> bool {
540        !Self::find_variables(pattern).is_empty()
541    }
542
543    /// Retrieve all tags from the mode.
544    pub fn get_labels(pattern: &Pattern) -> Vec<String> {
545        let mut labels = Vec::new();
546        Self::get_labels_recursive(pattern, &mut labels);
547        labels
548    }
549
550    fn get_labels_recursive(pattern: &Pattern, labels: &mut Vec<String>) {
551        match pattern {
552            Pattern::Node(p) => {
553                labels.extend(p.labels.clone());
554            }
555            Pattern::Path(p) => {
556                for element in &p.elements {
557                    Self::get_labels_in_element(element, labels);
558                }
559            }
560            _ => {}
561        }
562    }
563
564    fn get_labels_in_element(element: &PathElement, labels: &mut Vec<String>) {
565        match element {
566            PathElement::Node(p) => {
567                labels.extend(p.labels.clone());
568            }
569            PathElement::CreateEdge(_) => {
570                // Edge hops carry edge types, not node labels.
571            }
572            PathElement::Alternative(patterns) => {
573                for pattern in patterns {
574                    Self::get_labels_recursive(pattern, labels);
575                }
576            }
577            PathElement::Optional(elem) => {
578                Self::get_labels_in_element(elem, labels);
579            }
580            PathElement::Repeated(elem, _) => {
581                Self::get_labels_in_element(elem, labels);
582            }
583            PathElement::Recursive(_rc) => {
584                // Recursive comprehension doesn't have a path_pattern anymore;
585                // labels are inferred from the filter/projection expressions.
586            }
587            _ => {}
588        }
589    }
590}
591
592#[cfg(test)]
593mod tests {
594    use super::*;
595
596    #[test]
597    fn test_node_pattern() {
598        let pattern = Pattern::Node(NodePattern::new(
599            Some("n".to_string()),
600            vec!["Person".to_string()],
601            None,
602            vec![],
603            Span::default(),
604        ));
605
606        assert!(matches!(pattern, Pattern::Node(_)));
607        let vars = PatternUtils::find_variables(&pattern);
608        assert_eq!(vars, vec!["n"]);
609    }
610
611    #[test]
612    fn test_edge_pattern() {
613        let pattern = Pattern::Edge(EdgePattern::new(
614            Some("e".to_string()),
615            vec!["KNOWS".to_string()],
616            None,
617            vec![],
618            EdgeDirection::Out,
619            None,
620            Span::default(),
621        ));
622
623        assert!(matches!(pattern, Pattern::Edge(_)));
624        let vars = PatternUtils::find_variables(&pattern);
625        assert_eq!(vars, vec!["e"]);
626    }
627
628    #[test]
629    fn test_path_pattern() {
630        let elements = vec![
631            PathElement::Node(NodePattern::new(
632                Some("a".to_string()),
633                vec![],
634                None,
635                vec![],
636                Span::default(),
637            )),
638            PathElement::Edge(EdgePattern::new(
639                Some("e".to_string()),
640                vec![],
641                None,
642                vec![],
643                EdgeDirection::Out,
644                None,
645                Span::default(),
646            )),
647            PathElement::Node(NodePattern::new(
648                Some("b".to_string()),
649                vec![],
650                None,
651                vec![],
652                Span::default(),
653            )),
654        ];
655
656        let pattern = Pattern::Path(PathPattern::new(elements, Span::default()));
657        let vars = PatternUtils::find_variables(&pattern);
658        assert_eq!(vars, vec!["a", "e", "b"]);
659    }
660
661    #[test]
662    fn test_edge_range() {
663        let range1 = EdgeRange::fixed(2);
664        assert_eq!(range1.min, Some(2));
665        assert_eq!(range1.max, Some(2));
666
667        let range2 = EdgeRange::range(1, 3);
668        assert_eq!(range2.min, Some(1));
669        assert_eq!(range2.max, Some(3));
670
671        let range3 = EdgeRange::at_least(1);
672        assert_eq!(range3.min, Some(1));
673        assert_eq!(range3.max, None);
674
675        let range4 = EdgeRange::any();
676        assert_eq!(range4.min, None);
677        assert_eq!(range4.max, None);
678    }
679}
linkrs_query/parser/ast/pattern.rs

linkrs_query/parser/ast/
pattern.rs
