Skip to main content

qualia_core_db/sparql_library/
sparql_parser.rs

1//! SPARQL Parser - Hand-Rolled Zero-Allocation Parser
2//!
3//! Simple SPARQL 1.1 subset parser that's zero-allocation by design.
4//! Uses byte string slicing and no heap allocation.
5
6use crate::sparql_ast::*;
7use std::collections::HashMap;
8
9/// Parse a SPARQL query into an AST (discarding the collected literal table).
10pub fn parse_sparql(query: &str) -> Result<(SparqlQuery, SparqlQueryContext), String> {
11    let (q, ctx, _lits) = parse_sparql_full(query)?;
12    Ok((q, ctx))
13}
14
15/// Parse a SPARQL query and also return the [`LiteralTable`] of string/geometry
16/// constants collected during the parse — needed by the executor to resolve
17/// literal text for `geof:*`/text extension functions.
18pub fn parse_sparql_full(
19    query: &str,
20) -> Result<(SparqlQuery, SparqlQueryContext, LiteralTable), String> {
21    crate::sparql_library::sparql_grammar::expr::reset_parse_literals();
22    let mut ctx = SparqlQueryContext::new();
23    let (query, prefixes) = strip_prefix_declarations(query.trim());
24    let query = query.as_str();
25
26    let parsed = if query.starts_with("SELECT") {
27        parse_select_query(query, &mut ctx, &prefixes).map(SparqlQuery::Select)
28    } else if query.starts_with("ASK") {
29        parse_ask_query(query, &mut ctx, &prefixes).map(SparqlQuery::Ask)
30    } else if query.starts_with("CONSTRUCT") {
31        parse_construct_query(query, &mut ctx, &prefixes).map(SparqlQuery::Construct)
32    } else if query.starts_with("DESCRIBE") {
33        parse_describe_query(query, &mut ctx, &prefixes).map(SparqlQuery::Describe)
34    } else {
35        Err("Unsupported query form".to_string())
36    }?;
37
38    let literals = crate::sparql_library::sparql_grammar::expr::take_parse_literals();
39    Ok((parsed, ctx, literals))
40}
41
42fn strip_prefix_declarations(query: &str) -> (String, HashMap<String, String>) {
43    let mut prefixes = HashMap::new();
44    let mut body = String::new();
45    for line in query.lines() {
46        let trimmed = line.trim();
47        let upper = trimmed.to_ascii_uppercase();
48        if upper.starts_with("PREFIX") {
49            if let Some((prefix, iri)) = parse_prefix_line(trimmed) {
50                prefixes.insert(prefix, iri);
51            }
52            continue;
53        }
54        if !body.is_empty() {
55            body.push(' ');
56        }
57        body.push_str(trimmed);
58    }
59    if body.is_empty() {
60        (query.to_string(), prefixes)
61    } else {
62        (body, prefixes)
63    }
64}
65
66fn parse_prefix_line(line: &str) -> Option<(String, String)> {
67    let rest = line
68        .trim_start_matches("PREFIX")
69        .trim_start_matches("prefix")
70        .trim();
71    let colon = rest.find(':')?;
72    let prefix = rest[..colon]
73        .trim()
74        .trim_start_matches("PREFIX")
75        .to_string();
76    let after = rest[colon + 1..].trim();
77    let iri = if after.starts_with('<') {
78        after
79            .trim_start_matches('<')
80            .trim_end_matches('>')
81            .to_string()
82    } else {
83        after.trim_matches('"').to_string()
84    };
85    Some((prefix, iri))
86}
87
88/// Parses `select-query`.
89pub(crate) fn parse_select_query(
90    query: &str,
91    ctx: &mut SparqlQueryContext,
92    prefixes: &HashMap<String, String>,
93) -> Result<SelectQuery, String> {
94    let mut query_struct = SelectQuery::default();
95
96    // Parse SELECT clause
97    let after_select = query.trim_start_matches("SELECT").trim();
98    let (distinct_reduced, after_distinct) = parse_distinct(after_select);
99    query_struct.distinct = distinct_reduced.0;
100    query_struct.reduced = distinct_reduced.1;
101
102    // Parse variables
103    let variables = parse_variables(after_distinct)?;
104    for var in variables {
105        let var_id = ctx.register_variable(var)?;
106        if query_struct.var_count < MAX_VARIABLES as u8 {
107            query_struct.variables[query_struct.var_count as usize] = var_id;
108            query_struct.var_count += 1;
109        }
110    }
111
112    // Parse WHERE clause - find WHERE in the original query
113    let where_start = query.find("WHERE").ok_or("WHERE clause not found")?;
114    let where_clause = &query[where_start..];
115    let pattern_id = parse_where_clause(where_clause, ctx, prefixes)?;
116    query_struct.root_pattern = pattern_id;
117
118    // Parse AS OF / AT TIME temporal modifier (Phase 4).
119    // Only search after the closing brace of the WHERE clause to avoid false positives.
120    let after_where = query.rfind('}').map(|i| &query[i..]).unwrap_or("");
121    if let Some(pos) = after_where.find("AS OF") {
122        let ts_ms = parse_temporal_literal(after_where[pos + 5..].trim_start());
123        let as_of_pat = Pattern::AsOf {
124            inner: query_struct.root_pattern,
125            timestamp_ms: ts_ms,
126            mode: TemporalMode::AsOf,
127        };
128        query_struct.root_pattern = ctx.alloc_pattern(as_of_pat)?;
129    } else if let Some(pos) = after_where.find("AT TIME") {
130        let ts_ms = parse_temporal_literal(after_where[pos + 7..].trim_start());
131        let at_time_pat = Pattern::AsOf {
132            inner: query_struct.root_pattern,
133            timestamp_ms: ts_ms,
134            mode: TemporalMode::AtTime,
135        };
136        query_struct.root_pattern = ctx.alloc_pattern(at_time_pat)?;
137    }
138
139    // Parse LIMIT/OFFSET if present
140    let limit_start = where_clause.find("LIMIT");
141    if let Some(start) = limit_start {
142        let limit_str = &where_clause[start + 5..];
143        query_struct.limit = parse_integer(limit_str);
144    }
145
146    let offset_start = where_clause.find("OFFSET");
147    if let Some(start) = offset_start {
148        let offset_str = &where_clause[start + 6..];
149        query_struct.offset = parse_integer(offset_str).unwrap_or(0);
150    }
151
152    Ok(query_struct)
153}
154
155fn parse_ask_query(
156    query: &str,
157    ctx: &mut SparqlQueryContext,
158    prefixes: &HashMap<String, String>,
159) -> Result<AskQuery, String> {
160    let after_ask = query.trim_start_matches("ASK").trim();
161    let where_start = after_ask.find("WHERE").ok_or("WHERE clause not found")?;
162    let where_clause = &after_ask[where_start..];
163    let pattern_id = parse_where_clause(where_clause, ctx, prefixes)?;
164
165    Ok(AskQuery {
166        root_pattern: pattern_id,
167    })
168}
169
170/// Index of the `}` that closes the `{` at `open` (balanced), or `None`.
171/// `{`/`}` are ASCII (0x7B/0x7D) and never appear as UTF-8 continuation bytes,
172/// so byte scanning is safe.
173fn find_matching_brace(s: &str, open: usize) -> Option<usize> {
174    let bytes = s.as_bytes();
175    if bytes.get(open) != Some(&b'{') {
176        return None;
177    }
178    let mut depth = 0usize;
179    for (i, &b) in bytes.iter().enumerate().skip(open) {
180        match b {
181            b'{' => depth += 1,
182            b'}' => {
183                depth -= 1;
184                if depth == 0 {
185                    return Some(i);
186                }
187            }
188            _ => {}
189        }
190    }
191    None
192}
193
194fn empty_construct(template_pattern: PatternId, root_pattern: PatternId) -> ConstructQuery {
195    ConstructQuery {
196        template_pattern,
197        root_pattern,
198        group_by: [0; MAX_VARIABLES],
199        group_by_count: 0,
200        having: None,
201        order_by: [OrderCondition::default(); MAX_ORDER_CONDITIONS],
202        order_by_count: 0,
203        limit: None,
204        offset: 0,
205    }
206}
207
208fn parse_construct_query(
209    query: &str,
210    ctx: &mut SparqlQueryContext,
211    prefixes: &HashMap<String, String>,
212) -> Result<ConstructQuery, String> {
213    let after_construct = query.trim_start_matches("CONSTRUCT").trim();
214
215    // `CONSTRUCT WHERE { … }` shorthand: the WHERE pattern is also the template.
216    if after_construct.to_ascii_uppercase().starts_with("WHERE") {
217        let pid = parse_where_clause(after_construct, ctx, prefixes)?;
218        return Ok(empty_construct(pid, pid));
219    }
220
221    // `CONSTRUCT { template } WHERE { … }`: parse the template group (reusing the
222    // WHERE-group grammar by prefixing the `WHERE` keyword) first — this also
223    // registers its variables, which the WHERE clause then reuses by hash.
224    let tmpl_open = after_construct
225        .find('{')
226        .ok_or("CONSTRUCT template '{' not found")?;
227    let tmpl_close = find_matching_brace(after_construct, tmpl_open)
228        .ok_or("Unbalanced CONSTRUCT template braces")?;
229    let template_group = &after_construct[tmpl_open..=tmpl_close];
230    let template_input = format!("WHERE {template_group}");
231    let template_pattern = parse_where_clause(&template_input, ctx, prefixes)?;
232
233    let rest = &after_construct[tmpl_close + 1..];
234    let where_start = rest
235        .to_ascii_uppercase()
236        .find("WHERE")
237        .ok_or("WHERE clause not found")?;
238    let root_pattern = parse_where_clause(&rest[where_start..], ctx, prefixes)?;
239
240    Ok(empty_construct(template_pattern, root_pattern))
241}
242
243fn parse_describe_query(
244    query: &str,
245    ctx: &mut SparqlQueryContext,
246    prefixes: &HashMap<String, String>,
247) -> Result<DescribeQuery, String> {
248    let after_describe = query.trim_start_matches("DESCRIBE").trim();
249    let where_pos = after_describe.to_ascii_uppercase().find("WHERE");
250    let targets_str = match where_pos {
251        Some(p) => &after_describe[..p],
252        None => after_describe,
253    };
254
255    // Parse WHERE first so any `?var` targets are already registered in `ctx`
256    // and resolve to the same VariableId the WHERE clause bound.
257    let root_pattern = match where_pos {
258        Some(p) => Some(parse_where_clause(&after_describe[p..], ctx, prefixes)?),
259        None => None,
260    };
261
262    // Resolve each target token to a constant IRI hash or a bound variable id.
263    // Terms are hashed with `generate_60bit_token` — identical to the WHERE
264    // grammar and to RDF ingest, so `DESCRIBE <iri>` matches stored subjects.
265    let mut vars_or_ids = [0u64; MAX_VARIABLES];
266    let mut var_count = 0usize;
267    for tok in targets_str.split_whitespace() {
268        if var_count >= MAX_VARIABLES {
269            break;
270        }
271        if tok == "*" {
272            // `DESCRIBE *` — resources come from every WHERE binding
273            // (var_count stays 0; the executor handles that case).
274            continue;
275        }
276        let value: Option<u64> = if let Some(name) = tok.strip_prefix('?') {
277            let h = crate::lexicon::generate_60bit_token(format!("?{name}").as_bytes());
278            ctx.variable_hashes
279                .iter()
280                .take(ctx.variable_count)
281                .position(|x| *x == h)
282                .map(|id| id as u64)
283        } else if let Some(iri) = tok.strip_prefix('<').and_then(|s| s.strip_suffix('>')) {
284            Some(crate::lexicon::generate_60bit_token(iri.as_bytes()))
285        } else if let Some((pfx, local)) = tok.split_once(':') {
286            let expanded = match prefixes.get(pfx) {
287                Some(base) => format!("{base}{local}"),
288                None => tok.to_string(),
289            };
290            Some(crate::lexicon::generate_60bit_token(expanded.as_bytes()))
291        } else {
292            None
293        };
294        if let Some(v) = value {
295            vars_or_ids[var_count] = v;
296            var_count += 1;
297        }
298    }
299
300    Ok(DescribeQuery {
301        vars_or_ids,
302        var_count: var_count as u8,
303        root_pattern,
304    })
305}
306
307fn parse_distinct(input: &str) -> ((bool, bool), &str) {
308    let input = input.trim();
309    if input.starts_with("DISTINCT") {
310        let after_distinct = input.trim_start_matches("DISTINCT").trim();
311        if after_distinct.starts_with("REDUCED") {
312            (
313                (true, true),
314                after_distinct.trim_start_matches("REDUCED").trim(),
315            )
316        } else {
317            ((true, false), after_distinct)
318        }
319    } else {
320        ((false, false), input)
321    }
322}
323
324fn parse_variables(input: &str) -> Result<Vec<&str>, String> {
325    let input = input.trim();
326    if input == "*" {
327        return Ok(vec![]);
328    }
329    let select_clause = if let Some(pos) = input.to_ascii_uppercase().find("WHERE") {
330        &input[..pos]
331    } else {
332        input
333    };
334    let vars: Vec<&str> = select_clause
335        .split_whitespace()
336        .filter(|s| !s.is_empty() && s.starts_with('?'))
337        .collect();
338    Ok(vars)
339}
340
341fn parse_where_clause(
342    input: &str,
343    ctx: &mut SparqlQueryContext,
344    prefixes: &HashMap<String, String>,
345) -> Result<PatternId, String> {
346    // Delegate to the recursive-descent group-graph-pattern parser in
347    // `sparql_grammar`: FILTER / OPTIONAL / UNION / MINUS / nested groups /
348    // quoted triples, producing the `Pattern` arena the planner + executor
349    // already run. (`input` begins with `WHERE { … }`; the grammar consumes the
350    // balanced braces and ignores any trailing solution modifiers, which the
351    // caller parses separately.)
352    crate::sparql_library::sparql_grammar::parse_where_group(input, ctx, prefixes)
353}
354
355fn parse_integer(input: &str) -> Option<u64> {
356    input.trim().parse().ok()
357}
358
359/// Parse a temporal literal (Phase 4 AS OF / AT TIME).
360///
361/// Accepts two forms:
362/// - Integer milliseconds since Unix epoch: `1717286400000`
363/// - Typed ISO 8601 date literal: `"2024-06-01"^^xsd:dateTime`
364///
365/// Falls back to `0` if parsing fails.
366fn parse_temporal_literal(input: &str) -> u64 {
367    let input = input.trim();
368    // Strip typed literal wrapper: "YYYY-MM-DD"^^xsd:dateTime
369    let bare = if let Some(inner) = input.strip_prefix('"') {
370        inner.split("\"^^").next().unwrap_or(inner)
371    } else {
372        input
373    };
374    // Try integer milliseconds first.
375    if let Ok(ms) = bare.parse::<u64>() {
376        return ms;
377    }
378    // Minimal ISO 8601 date: YYYY-MM-DD → milliseconds at midnight UTC.
379    if bare.len() >= 10 {
380        if let (Ok(y), Ok(m), Ok(d)) = (
381            bare[0..4].parse::<u64>(),
382            bare[5..7].parse::<u64>(),
383            bare[8..10].parse::<u64>(),
384        ) {
385            let days = temporal_days_since_epoch(y, m, d);
386            return days * 86_400_000;
387        }
388    }
389    0
390}
391
392fn temporal_days_since_epoch(year: u64, month: u64, day: u64) -> u64 {
393    let mut days = 0u64;
394    for y in 1970..year {
395        days += if temporal_is_leap(y) { 366 } else { 365 };
396    }
397    let month_days: [u64; 12] = [
398        31,
399        if temporal_is_leap(year) { 29 } else { 28 },
400        31,
401        30,
402        31,
403        30,
404        31,
405        31,
406        30,
407        31,
408        30,
409        31,
410    ];
411    for m in 1..month {
412        days += month_days[(m - 1) as usize];
413    }
414    days + day - 1
415}
416
417fn temporal_is_leap(y: u64) -> bool {
418    (y % 4 == 0 && y % 100 != 0) || y % 400 == 0
419}
420
421#[cfg(test)]
422mod tests {
423    use super::*;
424
425    /// Regression: dots *inside* a `<…>` IRI or a `"…"` literal must not be
426    /// treated as triple terminators. The tokenizer handles this structurally
427    /// (whole-IRI / whole-string tokens), so these now parse end-to-end.
428    #[test]
429    fn dotted_iris_and_literals_do_not_break_bgp() {
430        let two = "SELECT ?a WHERE { ?a <https://ns.webcivics.net/values/partOf> <https://ns.webcivics.net/values/x#Instrument> . \
431                   ?a <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <https://ns.webcivics.net/values/Undertaking> }";
432        assert!(
433            parse_sparql(two).is_ok(),
434            "two dotted-IRI triples must parse"
435        );
436
437        let lit = "SELECT ?a WHERE { ?a <https://ns.webcivics.net/values/originalText> \"Art. 3 applies.\" }";
438        assert!(
439            parse_sparql(lit).is_ok(),
440            "a dotted literal must not break the BGP"
441        );
442    }
443
444    /// End-to-end parse of a typed BGP with explicit dotted IRIs — must produce a
445    /// triple pattern, not error out.
446    #[test]
447    fn typed_iri_bgp_parses() {
448        let q = "SELECT ?a WHERE { ?a <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> \
449                 <https://ns.webcivics.net/values/Undertaking> }";
450        let (_, ctx) = parse_sparql(q).expect("typed IRI BGP must parse");
451        assert!(
452            ctx.pattern_count > 0,
453            "the typed triple pattern must be allocated"
454        );
455    }
456
457    #[test]
458    fn test_parse_simple_select() {
459        let query = "SELECT ?s WHERE { ?s knows Bob }";
460        let result = parse_sparql(query);
461        assert!(result.is_ok());
462
463        let (sparql_query, ctx) = result.unwrap();
464        if let SparqlQuery::Select(select) = sparql_query {
465            assert!(select.var_count > 0);
466            assert!(ctx.pattern_count > 0);
467        } else {
468            panic!("Expected SELECT query");
469        }
470    }
471
472    #[test]
473    fn test_parse_distinct() {
474        let query = "SELECT DISTINCT ?s WHERE { ?s knows Bob }";
475        let result = parse_sparql(query);
476        assert!(result.is_ok());
477
478        let (sparql_query, _) = result.unwrap();
479        if let SparqlQuery::Select(select) = sparql_query {
480            assert!(select.distinct);
481        } else {
482            panic!("Expected SELECT query");
483        }
484    }
485
486    #[test]
487    fn test_parse_limit() {
488        let query = "SELECT ?s WHERE { ?s knows Bob } LIMIT 10";
489        let result = parse_sparql(query);
490        assert!(result.is_ok());
491
492        let (sparql_query, _) = result.unwrap();
493        if let SparqlQuery::Select(select) = sparql_query {
494            assert_eq!(select.limit, Some(10));
495        } else {
496            panic!("Expected SELECT query");
497        }
498    }
499
500    #[test]
501    fn test_parse_ask() {
502        let query = "ASK WHERE { ?s knows Bob }";
503        let result = parse_sparql(query);
504        assert!(result.is_ok());
505    }
506
507    #[test]
508    fn test_parse_as_of_integer() {
509        let query = "SELECT ?s WHERE { ?s knows Bob } AS OF 1717286400000";
510        let (q, ctx) = parse_sparql(query).expect("parse failed");
511        if let SparqlQuery::Select(sel) = q {
512            let root = &ctx.patterns[sel.root_pattern as usize];
513            match root {
514                Pattern::AsOf {
515                    timestamp_ms, mode, ..
516                } => {
517                    assert_eq!(*timestamp_ms, 1_717_286_400_000);
518                    assert_eq!(*mode, TemporalMode::AsOf);
519                }
520                other => panic!("expected AsOf, got {:?}", other),
521            }
522        } else {
523            panic!("expected SELECT");
524        }
525    }
526
527    #[test]
528    fn test_parse_as_of_iso_date() {
529        // 2024-06-01 = days since epoch × 86_400_000
530        let query = r#"SELECT ?s WHERE { ?s knows Bob } AS OF "2024-06-01"^^xsd:dateTime"#;
531        let (q, ctx) = parse_sparql(query).expect("parse failed");
532        if let SparqlQuery::Select(sel) = q {
533            if let Pattern::AsOf {
534                timestamp_ms, mode, ..
535            } = ctx.patterns[sel.root_pattern as usize]
536            {
537                assert!(timestamp_ms > 0, "timestamp should be > 0");
538                assert_eq!(mode, TemporalMode::AsOf);
539            } else {
540                panic!("expected AsOf pattern");
541            }
542        }
543    }
544
545    #[test]
546    fn test_parse_at_time() {
547        let query = "SELECT ?s WHERE { ?s knows Bob } AT TIME 9999999";
548        let (q, ctx) = parse_sparql(query).expect("parse failed");
549        if let SparqlQuery::Select(sel) = q {
550            if let Pattern::AsOf {
551                timestamp_ms, mode, ..
552            } = ctx.patterns[sel.root_pattern as usize]
553            {
554                assert_eq!(timestamp_ms, 9_999_999);
555                assert_eq!(mode, TemporalMode::AtTime);
556            } else {
557                panic!("expected AsOf pattern");
558            }
559        }
560    }
561
562    #[test]
563    fn test_temporal_literal_epoch() {
564        // 1970-01-01 = day 0 = ms 0
565        assert_eq!(
566            super::parse_temporal_literal(r#""1970-01-01"^^xsd:dateTime"#),
567            0
568        );
569    }
570
571    #[test]
572    fn test_temporal_literal_integer_passthrough() {
573        assert_eq!(super::parse_temporal_literal("42000"), 42_000);
574    }
575
576    #[test]
577    fn test_parse_prefix_and_star() {
578        let query = r#"
579            PREFIX ex: <http://example.org/>
580            SELECT ?s WHERE { << ?s ex:knows ex:bob >> ex:certainty ?c }
581        "#;
582        let (q, ctx) = parse_sparql(query).expect("parse");
583        assert!(matches!(q, SparqlQuery::Select(_)));
584        assert!(ctx.pattern_count > 0);
585    }
586}