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

qualia_core_db/sparql_library/
sparql_parser.rs
