linkrs_query/parser/parsing/
traversal_parser.rs

1//! Graph Traversal Statement Parsing Module
2//!
3//! Responsible for parsing statements related to graph traversal, including MATCH, GO, FIND PATH, GET SUBGRAPH, etc.
4
5use crate::parser::ast::hint::JoinHintAst;
6use crate::parser::ast::pattern::{
7    EdgePattern, EdgeRange, NodePattern, PathElement, PathPattern, Pattern, VariablePattern,
8};
9use crate::parser::ast::stmt::*;
10use crate::parser::core::error::{ParseError, ParseErrorKind};
11use crate::parser::parsing::expr_parser::parse_expression_with_context;
12use crate::parser::parsing::parse_context::ParseContext;
13use crate::parser::parsing::pattern_common;
14use crate::parser::TokenKind;
15use linkrs_core::types::expr::contextual::ContextualExpression;
16use linkrs_core::types::expr::Expression as CoreExpression;
17
18mod find_path;
19mod get_subgraph;
20mod go;
21mod r#match;
22
23/// Graph Traversal Parser
24pub struct TraversalParser;
25
26/// The body of one MATCH clause, used when merging consecutive MATCH clauses.
27pub(crate) struct ParsedMatchClause {
28    patterns: Vec<Pattern>,
29    join_hint: Option<JoinHintAst>,
30    where_clause: Option<ContextualExpression>,
31    where_explicit: bool,
32    return_clause: Option<ReturnClause>,
33    delete_clause: Option<MatchDeleteClause>,
34}
35
36impl TraversalParser {
37    pub fn new() -> Self {
38        Self
39    }
40
41    /// Analysis mode
42    pub fn parse_pattern(&mut self, ctx: &mut ParseContext) -> Result<Pattern, ParseError> {
43        let start_span = ctx.current_span();
44
45        if let TokenKind::Identifier(_) = ctx.current_token().kind {
46            let ckpt = ctx.checkpoint();
47            if let Ok(candidate) = ctx.expect_identifier() {
48                if ctx.match_token(TokenKind::Assign) {
49                    return self.parse_named_path(ctx, candidate, start_span);
50                }
51            }
52            ctx.restore(ckpt);
53        }
54
55        self.parse_unnamed_pattern(ctx, start_span)
56    }
57
58    /// Parse the remainder of a named path binding after `name =`.
59    fn parse_named_path(
60        &mut self,
61        ctx: &mut ParseContext,
62        name: String,
63        start_span: crate::parser::ast::types::Span,
64    ) -> Result<Pattern, ParseError> {
65        match self.parse_unnamed_pattern(ctx, ctx.current_span())? {
66            Pattern::Path(mut path) => {
67                if path.name.is_some() {
68                    return Err(ParseError::new(
69                        ParseErrorKind::SyntaxError,
70                        "Duplicate path name in named path binding".to_string(),
71                        ctx.current_position(),
72                    ));
73                }
74                path.name = Some(name);
75                Ok(Pattern::Path(path))
76            }
77            Pattern::Node(node) => {
78                let span = ctx.span_since(start_span.start);
79                Ok(Pattern::Path(PathPattern::with_name(
80                    vec![PathElement::Node(node)],
81                    span,
82                    name,
83                )))
84            }
85            _ => Err(ParseError::new(
86                ParseErrorKind::SyntaxError,
87                "Expected a node or path pattern after '=' in named path binding".to_string(),
88                ctx.current_position(),
89            )),
90        }
91    }
92
93    /// Parse a plain pattern without a leading path-name binding.
94    fn parse_unnamed_pattern(
95        &mut self,
96        ctx: &mut ParseContext,
97        start_span: crate::parser::ast::types::Span,
98    ) -> Result<Pattern, ParseError> {
99        if ctx.match_token(TokenKind::LParen) {
100            let node = self.parse_node_pattern(ctx, start_span)?;
101
102            if ctx.check_token(TokenKind::LeftArrow)
103                || ctx.check_token(TokenKind::RightArrow)
104                || ctx.check_token(TokenKind::Minus)
105                || ctx.check_token(TokenKind::Arrow)
106                || ctx.check_token(TokenKind::BackArrow)
107            {
108                return self.parse_path_pattern(ctx, node);
109            }
110
111            return Ok(Pattern::Node(node));
112        }
113
114        if let TokenKind::Identifier(ref name) = ctx.current_token().kind.clone() {
115            let name = name.clone();
116            let span = ctx.current_span();
117            ctx.next_token();
118            return Ok(Pattern::Variable(VariablePattern { span, name }));
119        }
120
121        Err(ParseError::new(
122            ParseErrorKind::SyntaxError,
123            "Expected pattern (node or path)".to_string(),
124            ctx.current_position(),
125        ))
126    }
127
128    /// Analyzing the node pattern
129    fn parse_node_pattern(
130        &mut self,
131        ctx: &mut ParseContext,
132        start_span: crate::parser::ast::types::Span,
133    ) -> Result<NodePattern, ParseError> {
134        let mut variable = None;
135        let mut labels = Vec::new();
136        let mut properties = None;
137
138        if let TokenKind::Identifier(ref name) = ctx.current_token().kind.clone() {
139            let name = name.clone();
140            ctx.next_token();
141            variable = Some(name);
142        }
143
144        if ctx.match_token(TokenKind::Colon) {
145            loop {
146                let label = ctx.expect_identifier()?;
147                pattern_common::reject_qualified_reference(ctx, &label)?;
148                labels.push(label);
149                if !ctx.check_token(TokenKind::Colon) {
150                    break;
151                }
152                ctx.next_token();
153            }
154        }
155
156        if ctx.match_token(TokenKind::LBrace) {
157            properties = Some(self.parse_properties_expr(ctx)?);
158            ctx.expect_token(TokenKind::RBrace)?;
159        }
160
161        ctx.expect_token(TokenKind::RParen)?;
162
163        let span = ctx.span_since(start_span.start);
164
165        Ok(NodePattern {
166            span,
167            variable,
168            labels,
169            properties,
170            predicates: Vec::new(),
171        })
172    }
173
174    /// Analyzing path patterns
175    fn parse_path_pattern(
176        &mut self,
177        ctx: &mut ParseContext,
178        start_node: NodePattern,
179    ) -> Result<Pattern, ParseError> {
180        let start_span = start_node.span;
181        let mut elements = vec![PathElement::Node(start_node)];
182
183        while ctx.check_token(TokenKind::LeftArrow)
184            || ctx.check_token(TokenKind::RightArrow)
185            || ctx.check_token(TokenKind::Minus)
186            || ctx.check_token(TokenKind::Arrow)
187            || ctx.check_token(TokenKind::BackArrow)
188        {
189            let edge = self.parse_edge_pattern(ctx)?;
190            elements.push(PathElement::Edge(edge));
191
192            if ctx.match_token(TokenKind::LParen) {
193                let node_span = ctx.current_span();
194                let node = self.parse_node_pattern(ctx, node_span)?;
195                elements.push(PathElement::Node(node));
196            } else {
197                break;
198            }
199        }
200
201        let span = ctx.span_since(start_span.start);
202
203        Ok(Pattern::Path(PathPattern {
204            span,
205            elements,
206            name: None,
207        }))
208    }
209
210    /// Analyzing the border mode
211    fn parse_edge_pattern(&mut self, ctx: &mut ParseContext) -> Result<EdgePattern, ParseError> {
212        let start_span = ctx.current_span();
213        let incoming =
214            ctx.match_token(TokenKind::BackArrow) || ctx.match_token(TokenKind::LeftArrow);
215
216        ctx.expect_token(TokenKind::Minus)?;
217
218        let mut variable = None;
219        let mut edge_types = Vec::new();
220        let mut properties = None;
221        let mut range = None;
222        let mut path_semantic = None;
223
224        if ctx.match_token(TokenKind::LBracket) {
225            if let TokenKind::Identifier(ref name) = ctx.current_token().kind.clone() {
226                let name = name.clone();
227                ctx.next_token();
228
229                if ctx.check_token(TokenKind::Colon) {
230                    variable = Some(name);
231                } else {
232                    pattern_common::reject_qualified_reference(ctx, &name)?;
233                    edge_types.push(name);
234                }
235            }
236
237            if ctx.match_token(TokenKind::Colon) {
238                loop {
239                    ctx.match_token(TokenKind::Colon);
240                    let edge_type = ctx.expect_identifier()?;
241                    pattern_common::reject_qualified_reference(ctx, &edge_type)?;
242                    edge_types.push(edge_type);
243                    if !ctx.match_token(TokenKind::Pipe) {
244                        break;
245                    }
246                }
247            }
248
249            if ctx.match_token(TokenKind::LBrace) {
250                properties = Some(self.parse_properties_expr(ctx)?);
251                ctx.expect_token(TokenKind::RBrace)?;
252            }
253
254            if ctx.match_token(TokenKind::Star) {
255                if ctx.match_token(TokenKind::Trail) {
256                    path_semantic = Some(PathSemantic::Trail);
257                    range = Some(EdgeRange::any());
258                } else if ctx.match_token(TokenKind::Acyclic) {
259                    path_semantic = Some(PathSemantic::Acyclic);
260                    range = Some(EdgeRange::any());
261                } else if ctx.match_token(TokenKind::Shortest) {
262                    path_semantic = Some(PathSemantic::Shortest);
263                    range = Some(EdgeRange::any());
264                } else if ctx.match_token(TokenKind::AllShortestPaths)
265                    || (ctx.match_token(TokenKind::All) && ctx.match_token(TokenKind::Shortest))
266                {
267                    path_semantic = Some(PathSemantic::AllShortest);
268                    range = Some(EdgeRange::any());
269                } else if ctx.match_token(TokenKind::Weighted) {
270                    ctx.expect_token(TokenKind::LParen)?;
271                    let weight_prop = ctx.expect_identifier()?;
272                    ctx.expect_token(TokenKind::RParen)?;
273                    path_semantic = Some(PathSemantic::WeightedShortest(weight_prop));
274                    range = Some(EdgeRange::any());
275                } else if ctx.match_token(TokenKind::LParen) {
276                    return Err(ParseError::new(
277                        ParseErrorKind::UnsupportedFeature,
278                        "Recursive comprehension patterns are not supported".to_string(),
279                        ctx.current_position(),
280                    ));
281                } else if ctx.match_token(TokenKind::LBracket) {
282                    let min = if matches!(ctx.current_token().kind, TokenKind::IntegerLiteral(_)) {
283                        let n = ctx.expect_integer_literal()? as usize;
284                        Some(n)
285                    } else {
286                        None
287                    };
288
289                    if ctx.match_token(TokenKind::DotDot) {
290                        let max =
291                            if matches!(ctx.current_token().kind, TokenKind::IntegerLiteral(_)) {
292                                let n = ctx.expect_integer_literal()? as usize;
293                                Some(n)
294                            } else {
295                                None
296                            };
297                        range = Some(EdgeRange::new(min, max));
298                    } else if let Some(min_val) = min {
299                        range = Some(EdgeRange::fixed(min_val));
300                    } else {
301                        range = Some(EdgeRange::any());
302                    }
303
304                    ctx.expect_token(TokenKind::RBracket)?;
305                } else if matches!(ctx.current_token().kind, TokenKind::IntegerLiteral(_)) {
306                    let min = ctx.expect_integer_literal()? as usize;
307                    if ctx.match_token(TokenKind::DotDot) {
308                        let max =
309                            if matches!(ctx.current_token().kind, TokenKind::IntegerLiteral(_)) {
310                                let n = ctx.expect_integer_literal()? as usize;
311                                Some(n)
312                            } else {
313                                None
314                            };
315                        range = Some(EdgeRange::new(Some(min), max));
316                    } else {
317                        range = Some(EdgeRange::fixed(min));
318                    }
319                } else {
320                    range = Some(EdgeRange::any());
321                }
322            }
323
324            ctx.expect_token(TokenKind::RBracket)?;
325        }
326
327        // The trailing direction closes the hop: `->` or `-`.
328        let closing = ctx.current_token().kind.clone();
329        let direction =
330            pattern_common::resolve_edge_direction(incoming, &closing).ok_or_else(|| {
331                ParseError::new(
332                    ParseErrorKind::SyntaxError,
333                    "Expected '-', '->', or '<-' after edge pattern".to_string(),
334                    ctx.current_position(),
335                )
336            })?;
337        ctx.next_token();
338
339        let span = ctx.span_since(start_span.start);
340
341        Ok(EdgePattern {
342            span,
343            variable,
344            edge_types,
345            properties,
346            predicates: Vec::new(),
347            direction,
348            range,
349            path_semantic,
350            recursive_comprehension: ctx.take_recursive_comprehension(),
351        })
352    }
353
354    /// Analysis steps
355    fn parse_steps(&mut self, ctx: &mut ParseContext) -> Result<Steps, ParseError> {
356        let token = ctx.current_token();
357        match token.kind {
358            TokenKind::IntegerLiteral(n) => {
359                ctx.next_token();
360                Ok(Steps::Fixed(n as usize))
361            }
362            TokenKind::Step | TokenKind::From => Ok(Steps::Fixed(1)),
363            _ => Err(ParseError::new(
364                ParseErrorKind::UnsupportedFeature,
365                "GO step count must be an integer literal".to_string(),
366                ctx.current_position(),
367            )),
368        }
369    }
370
371    /// Parse a list of expressions
372    fn parse_expression_list(
373        &mut self,
374        ctx: &mut ParseContext,
375    ) -> Result<Vec<ContextualExpression>, ParseError> {
376        let mut expressions = Vec::new();
377
378        loop {
379            expressions.push(self.parse_expression(ctx)?);
380            if !ctx.match_token(TokenKind::Comma) {
381                break;
382            }
383        }
384
385        Ok(expressions)
386    }
387
388    /// Analyzing attribute expressions
389    fn parse_properties_expr(
390        &mut self,
391        ctx: &mut ParseContext,
392    ) -> Result<ContextualExpression, ParseError> {
393        let mut properties = Vec::new();
394
395        while !ctx.check_token(TokenKind::RBrace) {
396            let key = ctx.expect_identifier()?;
397            ctx.expect_token(TokenKind::Colon)?;
398            let value = self.parse_expression(ctx)?;
399            properties.push((key, value));
400            if !ctx.match_token(TokenKind::Comma) {
401                break;
402            }
403        }
404
405        let mut mapped_properties = Vec::new();
406        for (k, v) in properties {
407            let v_expr = v
408                .expression()
409                .ok_or_else(|| {
410                    ParseError::new_simple(
411                        "Expression not registered in context".to_string(),
412                        ctx.current_position(),
413                    )
414                })?
415                .inner()
416                .clone();
417            mapped_properties.push((k, v_expr));
418        }
419
420        let expr = CoreExpression::map(mapped_properties);
421
422        let expr_meta = linkrs_core::types::expr::ExpressionMeta::new(expr);
423        let id = ctx.expression_context().register_expression(expr_meta);
424        Ok(ContextualExpression::new(
425            id,
426            ctx.expression_context_clone(),
427        ))
428    }
429
430    /// Create the default true expression.
431    fn create_true_expression(ctx: &mut ParseContext) -> Result<ContextualExpression, ParseError> {
432        let expr = CoreExpression::literal(true);
433        let expr_meta = linkrs_core::types::expr::ExpressionMeta::new(expr);
434        let id = ctx.expression_context().register_expression(expr_meta);
435        Ok(ContextualExpression::new(
436            id,
437            ctx.expression_context_clone(),
438        ))
439    }
440
441    /// Analyzing the expression
442    fn parse_expression(
443        &mut self,
444        ctx: &mut ParseContext,
445    ) -> Result<ContextualExpression, ParseError> {
446        parse_expression_with_context(ctx, ctx.expression_context_clone())
447    }
448}
449
450impl Default for TraversalParser {
451    fn default() -> Self {
452        Self::new()
453    }
454}
linkrs_query/parser/parsing/traversal_parser.rs

linkrs_query/parser/parsing/
traversal_parser.rs
