kermit_algos/queries/
parser.rs

1use {
2    super::join_query::{Predicate, Term},
3    crate::JoinQuery,
4    winnow::{
5        ascii::multispace0,
6        combinator::{delimited, separated},
7        error::{ContextError, ErrMode},
8        token::take_while,
9        Parser,
10    },
11};
12
13type PResult<T> = Result<T, winnow::error::ErrMode<ContextError>>;
14
15fn ws(input: &mut &str) -> PResult<()> {
16    let _: &str = multispace0.parse_next(input)?;
17    Ok(())
18}
19
20fn ident(input: &mut &str) -> PResult<String> {
21    let start = *input;
22    take_while(1.., |c: char| c.is_ascii_alphabetic()).parse_next(input)?;
23    take_while(0.., |c: char| c.is_ascii_alphanumeric() || c == '_').parse_next(input)?;
24    let end = *input;
25    let len = start.len() - end.len();
26    Ok(start[..len].to_string())
27}
28
29fn comma(input: &mut &str) -> PResult<char> { delimited(ws, ',', ws).parse_next(input) }
30
31fn dot(input: &mut &str) -> PResult<char> { delimited(ws, '.', ws).parse_next(input) }
32
33// ---------- term / predicate ----------
34fn term(input: &mut &str) -> PResult<Term> {
35    if input.starts_with('_')
36        && (input.len() == 1 || !input.chars().nth(1).unwrap().is_ascii_alphanumeric())
37    {
38        let _ = '_'.parse_next(input)?;
39        return Ok(Term::Placeholder);
40    }
41
42    let name = ident.parse_next(input)?;
43
44    let is_var = name
45        .chars()
46        .next()
47        .map(|c| c.is_ascii_uppercase())
48        .unwrap_or(false);
49
50    Ok(if is_var {
51        Term::Var(name)
52    } else {
53        Term::Atom(name)
54    })
55}
56
57fn term_list(input: &mut &str) -> PResult<Vec<Term>> {
58    delimited(
59        delimited(ws, '(', ws),
60        separated(1.., term, comma),
61        delimited(ws, ')', ws),
62    )
63    .parse_next(input)
64}
65
66fn predicate(input: &mut &str) -> PResult<Predicate> {
67    ws.parse_next(input)?;
68    let name = ident.parse_next(input)?;
69    let terms = term_list.parse_next(input)?;
70    Ok(Predicate {
71        name,
72        terms,
73    })
74}
75
76fn query(input: &mut &str) -> PResult<JoinQuery> {
77    let head = predicate.parse_next(input)?;
78    // ":-" separates head from body
79    let _ = delimited(ws, ":-", ws).parse_next(input)?;
80    let body = separated(1.., predicate, comma).parse_next(input)?;
81    let _ = dot.parse_next(input)?;
82    Ok(JoinQuery {
83        head,
84        body,
85    })
86}
87
88impl std::str::FromStr for JoinQuery {
89    type Err = ErrMode<ContextError>;
90
91    fn from_str(s: &str) -> Result<Self, Self::Err> {
92        let mut input = s;
93        query.parse_next(&mut input)
94    }
95}
96
97// ---------- demo ----------
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_query_parser() {
105        let mut src = "P(A, C) :- Q(A, B), R(B, C).";
106        match query.parse_next(&mut src) {
107            | Ok(ast) => {
108                println!("{ast:#?}");
109                // Remaining input (should be empty or just whitespace)
110                let _ = ws.parse_next(&mut src);
111                if !src.is_empty() {
112                    eprintln!("Unparsed tail: {src:?}");
113                }
114                assert_eq!(ast.head.name, "P");
115                assert_eq!(ast.head.terms.len(), 2);
116                assert_eq!(ast.body.len(), 2);
117            },
118            | Err(e) => panic!("Parse error: {e:?}"),
119        }
120    }
121
122    #[test]
123    fn test_query_from_str_simple() {
124        let query_str = "P(X) :- Q(X).";
125        let query: JoinQuery = query_str.parse().expect("Failed to parse query");
126
127        assert_eq!(query.head.name, "P");
128        assert_eq!(query.head.terms.len(), 1);
129        assert_eq!(query.head.terms[0], Term::Var("X".to_string()));
130
131        assert_eq!(query.body.len(), 1);
132        assert_eq!(query.body[0].name, "Q");
133        assert_eq!(query.body[0].terms.len(), 1);
134        assert_eq!(query.body[0].terms[0], Term::Var("X".to_string()));
135    }
136
137    #[test]
138    fn test_query_from_str_multiple_body_predicates() {
139        let query_str = "ancestor(X, Z) :- parent(X, Y), parent(Y, Z).";
140        let query: JoinQuery = query_str.parse().expect("Failed to parse query");
141
142        assert_eq!(query.head.name, "ancestor");
143        assert_eq!(query.head.terms.len(), 2);
144        assert_eq!(query.head.terms[0], Term::Var("X".to_string()));
145        assert_eq!(query.head.terms[1], Term::Var("Z".to_string()));
146
147        assert_eq!(query.body.len(), 2);
148        assert_eq!(query.body[0].name, "parent");
149        assert_eq!(query.body[1].name, "parent");
150    }
151
152    #[test]
153    fn test_query_from_str_with_atoms() {
154        let query_str = "likes(alice, X):- food(X), healthy(X).";
155        let query: JoinQuery = query_str.parse().expect("Failed to parse query");
156
157        assert_eq!(query.head.name, "likes");
158        assert_eq!(query.head.terms[0], Term::Atom("alice".to_string()));
159        assert_eq!(query.head.terms[1], Term::Var("X".to_string()));
160
161        assert_eq!(query.body.len(), 2);
162    }
163
164    #[test]
165    fn test_query_from_str_with_whitespace() {
166        let query_str = "  P(X,Y)  :-  Q(X),R(Y)  .  ";
167        let query: JoinQuery = query_str
168            .parse()
169            .expect("Failed to parse query with whitespace");
170
171        assert_eq!(query.head.name, "P");
172        assert_eq!(query.head.terms.len(), 2);
173        assert_eq!(query.body.len(), 2);
174    }
175
176    #[test]
177    fn test_query_from_str_minimal_whitespace() {
178        let query_str = "P(X,Y):-Q(X),R(Y).";
179        let query: JoinQuery = query_str
180            .parse()
181            .expect("Failed to parse query with minimal whitespace");
182
183        assert_eq!(query.head.name, "P");
184        assert_eq!(query.head.terms.len(), 2);
185        assert_eq!(query.body.len(), 2);
186    }
187
188    #[test]
189    fn test_query_from_str_spaces_after_commas() {
190        let query_str = "result(X, Y, Z) :- relation1(X, Y), relation2(Y, Z).";
191        let query: JoinQuery = query_str
192            .parse()
193            .expect("Failed to parse query with spaces after commas");
194
195        assert_eq!(query.head.name, "result");
196        assert_eq!(query.head.terms.len(), 3);
197        assert_eq!(query.body.len(), 2);
198        assert_eq!(query.body[0].terms.len(), 2);
199        assert_eq!(query.body[1].terms.len(), 2);
200    }
201
202    #[test]
203    fn test_query_from_str_complex() {
204        let query_str = "path(X, Z) :- edge(X, Y), edge(Y, Z), vertex(X), vertex(Y), vertex(Z).";
205        let query: JoinQuery = query_str.parse().expect("Failed to parse complex query");
206
207        assert_eq!(query.head.name, "path");
208        assert_eq!(query.head.terms.len(), 2);
209        assert_eq!(query.body.len(), 5);
210
211        assert_eq!(query.body[0].name, "edge");
212        assert_eq!(query.body[1].name, "edge");
213        assert_eq!(query.body[2].name, "vertex");
214        assert_eq!(query.body[3].name, "vertex");
215        assert_eq!(query.body[4].name, "vertex");
216    }
217
218    #[test]
219    fn test_query_from_str_invalid_no_dot() {
220        let query_str = "P(X) :- Q(X)";
221        let result: Result<JoinQuery, _> = query_str.parse();
222        assert!(result.is_err());
223    }
224
225    #[test]
226    fn test_query_from_str_invalid_no_arrow() {
227        let query_str = "P(X) Q(X).";
228        let result: Result<JoinQuery, _> = query_str.parse();
229        assert!(result.is_err());
230    }
231
232    #[test]
233    fn test_query_from_str_invalid_empty_body() {
234        let query_str = "P(X) :- .";
235        let result: Result<JoinQuery, _> = query_str.parse();
236        assert!(result.is_err());
237    }
238
239    #[test]
240    fn test_query_from_str_with_placeholder() {
241        let query_str = "result(X, _) :- relation(X, _).";
242        let query: JoinQuery = query_str
243            .parse()
244            .expect("Failed to parse query with placeholder");
245
246        assert_eq!(query.head.name, "result");
247        assert_eq!(query.head.terms.len(), 2);
248        assert_eq!(query.head.terms[0], Term::Var("X".to_string()));
249        assert_eq!(query.head.terms[1], Term::Placeholder);
250
251        assert_eq!(query.body.len(), 1);
252        assert_eq!(query.body[0].terms[0], Term::Var("X".to_string()));
253        assert_eq!(query.body[0].terms[1], Term::Placeholder);
254    }
255
256    #[test]
257    fn test_query_from_str_multiple_placeholders() {
258        let query_str = "query(_, _, Z) :- data(_, _, Z).";
259        let query: JoinQuery = query_str
260            .parse()
261            .expect("Failed to parse query with multiple placeholders");
262
263        assert_eq!(query.head.terms[0], Term::Placeholder);
264        assert_eq!(query.head.terms[1], Term::Placeholder);
265        assert_eq!(query.head.terms[2], Term::Var("Z".to_string()));
266
267        assert_eq!(query.body[0].terms[0], Term::Placeholder);
268        assert_eq!(query.body[0].terms[1], Term::Placeholder);
269        assert_eq!(query.body[0].terms[2], Term::Var("Z".to_string()));
270    }
271
272    #[test]
273    fn test_query_from_str_placeholder_with_atoms() {
274        let query_str = "match(alice, _) :- person(alice, _), active(_).";
275        let query: JoinQuery = query_str
276            .parse()
277            .expect("Failed to parse query with placeholders and atoms");
278
279        assert_eq!(query.head.terms[0], Term::Atom("alice".to_string()));
280        assert_eq!(query.head.terms[1], Term::Placeholder);
281
282        assert_eq!(query.body[0].name, "person");
283        assert_eq!(query.body[0].terms[0], Term::Atom("alice".to_string()));
284        assert_eq!(query.body[0].terms[1], Term::Placeholder);
285
286        assert_eq!(query.body[1].name, "active");
287        assert_eq!(query.body[1].terms[0], Term::Placeholder);
288    }
289
290    #[test]
291    fn test_query_from_str_only_placeholders() {
292        let query_str = "any(_,_) :- data(_,_).";
293        let query: JoinQuery = query_str
294            .parse()
295            .expect("Failed to parse query with only placeholders");
296
297        assert_eq!(query.head.terms.len(), 2);
298        assert_eq!(query.head.terms[0], Term::Placeholder);
299        assert_eq!(query.head.terms[1], Term::Placeholder);
300
301        assert_eq!(query.body[0].terms.len(), 2);
302        assert_eq!(query.body[0].terms[0], Term::Placeholder);
303        assert_eq!(query.body[0].terms[1], Term::Placeholder);
304    }
305
306    #[test]
307    fn test_query_from_str_placeholder_mixed() {
308        let query_str = "filter(X, _, bob, Y) :- source(X, _, bob, Y), check(X, Y).";
309        let query: JoinQuery = query_str
310            .parse()
311            .expect("Failed to parse complex query with placeholders");
312
313        assert_eq!(query.head.terms.len(), 4);
314        assert_eq!(query.head.terms[0], Term::Var("X".to_string()));
315        assert_eq!(query.head.terms[1], Term::Placeholder);
316        assert_eq!(query.head.terms[2], Term::Atom("bob".to_string()));
317        assert_eq!(query.head.terms[3], Term::Var("Y".to_string()));
318
319        assert_eq!(query.body[0].terms.len(), 4);
320        assert_eq!(query.body[0].terms[1], Term::Placeholder);
321        assert_eq!(query.body[1].terms.len(), 2);
322    }
323}
kermit_algos/queries/parser.rs

kermit_algos/queries/
parser.rs
