oxirs_core/sparql/
query_locator.rs

1//! Locating the SPARQL `GroupGraphPattern` (the WHERE clause) inside a query string.
2//!
3//! Per the SPARQL 1.1 grammar, `WhereClause ::= 'WHERE'? GroupGraphPattern`, the
4//! `WHERE` keyword is **optional**. Legal queries frequently omit it, e.g.
5//! `ASK { ?s ?p ?o }`, `SELECT * { ?s ?p ?o }`, `SELECT ?x { ?x a <T> }`, or
6//! `CONSTRUCT { ... } { ... }`.
7//!
8//! The simplified executor historically located the pattern block by a naive
9//! `sparql.to_uppercase().find("WHERE")` substring search. That approach both
10//! failed on the omitted-`WHERE` forms (extracting zero patterns) and could
11//! match the substring `WHERE` inside an IRI (e.g. `.../somewhere#...`). This
12//! module provides scanner-based helpers that:
13//!
14//! 1. locate the `WHERE` keyword only when it appears as a stand-alone,
15//!    top-level word (never inside an IRI `<...>`, a string literal, or a `#`
16//!    line comment), and
17//! 2. fall back to the first top-level `{ ... }` group when `WHERE` is omitted,
18//!    honoring the fact that for a `CONSTRUCT` query the first group is the
19//!    template and the graph pattern is the group that follows it.
20//!
21//! All offsets returned are **byte** indices into the original `sparql` string
22//! and always fall on `char` boundaries (the markers scanned — `{`, `}`, `<`,
23//! `>`, `"`, `'`, `\`, `#`, the `\n` that ends a comment, and the ASCII keyword
24//! bytes — are all single-byte ASCII, and UTF-8 continuation bytes never collide
25//! with them).
26
27/// The top-level result form of a SPARQL query.
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29pub enum QueryForm {
30    /// `SELECT ...`
31    Select,
32    /// `ASK ...`
33    Ask,
34    /// `CONSTRUCT ...`
35    Construct,
36    /// `DESCRIBE ...`
37    Describe,
38    /// Query form could not be determined.
39    Unknown,
40}
41
42/// Return `true` if `b` is an ASCII identifier byte (used for word-boundary
43/// checks around keywords).
44#[inline]
45fn is_ident_byte(b: u8) -> bool {
46    b.is_ascii_alphanumeric() || b == b'_'
47}
48
49/// Find the byte offset of `keyword` occurring as a stand-alone, top-level word.
50///
51/// The match is ASCII case-insensitive. Occurrences inside an IRI (`<...>`), a
52/// string literal (`"..."` / `'...'`), or a `#` line comment are ignored, as are
53/// occurrences that are adjacent to other identifier characters (so `WHERE`
54/// never matches inside `somewhere`). Returns the byte index of the first
55/// qualifying match.
56pub fn find_keyword(sparql: &str, keyword: &str) -> Option<usize> {
57    let bytes = sparql.as_bytes();
58    let kw = keyword.as_bytes();
59    let klen = kw.len();
60    if klen == 0 {
61        return None;
62    }
63    let n = bytes.len();
64
65    let mut in_string: Option<u8> = None;
66    let mut in_iri = false;
67    let mut in_comment = false;
68    let mut escaped = false;
69    let mut i = 0usize;
70
71    while i < n {
72        let b = bytes[i];
73
74        if let Some(quote) = in_string {
75            if escaped {
76                escaped = false;
77            } else if b == b'\\' {
78                escaped = true;
79            } else if b == quote {
80                in_string = None;
81            }
82            i += 1;
83            continue;
84        }
85
86        if in_iri {
87            if b == b'>' {
88                in_iri = false;
89            }
90            i += 1;
91            continue;
92        }
93
94        if in_comment {
95            if b == b'\n' {
96                in_comment = false;
97            }
98            i += 1;
99            continue;
100        }
101
102        match b {
103            b'"' | b'\'' => {
104                in_string = Some(b);
105                i += 1;
106                continue;
107            }
108            b'<' => {
109                in_iri = true;
110                i += 1;
111                continue;
112            }
113            b'#' => {
114                in_comment = true;
115                i += 1;
116                continue;
117            }
118            _ => {}
119        }
120
121        if i + klen <= n && bytes[i..i + klen].eq_ignore_ascii_case(kw) {
122            let before_ok = i == 0 || !is_ident_byte(bytes[i - 1]);
123            let after_idx = i + klen;
124            let after_ok = after_idx >= n || !is_ident_byte(bytes[after_idx]);
125            if before_ok && after_ok {
126                return Some(i);
127            }
128        }
129
130        i += 1;
131    }
132
133    None
134}
135
136/// Find the byte index of the next top-level `{` at or after `from`, skipping
137/// any `{` that appears inside an IRI (`<...>`), a string literal, or a `#` line
138/// comment.
139pub fn next_group_open_brace(sparql: &str, from: usize) -> Option<usize> {
140    let bytes = sparql.as_bytes();
141    let n = bytes.len();
142    let mut i = from.min(n);
143
144    let mut in_string: Option<u8> = None;
145    let mut in_iri = false;
146    let mut in_comment = false;
147    let mut escaped = false;
148
149    while i < n {
150        let b = bytes[i];
151
152        if let Some(quote) = in_string {
153            if escaped {
154                escaped = false;
155            } else if b == b'\\' {
156                escaped = true;
157            } else if b == quote {
158                in_string = None;
159            }
160            i += 1;
161            continue;
162        }
163
164        if in_iri {
165            if b == b'>' {
166                in_iri = false;
167            }
168            i += 1;
169            continue;
170        }
171
172        if in_comment {
173            if b == b'\n' {
174                in_comment = false;
175            }
176            i += 1;
177            continue;
178        }
179
180        match b {
181            b'"' | b'\'' => in_string = Some(b),
182            b'<' => in_iri = true,
183            b'#' => in_comment = true,
184            b'{' => return Some(i),
185            _ => {}
186        }
187
188        i += 1;
189    }
190
191    None
192}
193
194/// Find the byte index of the `}` that matches the `{` located at byte index
195/// `open`, tracking nested braces and skipping braces inside IRIs, string
196/// literals, and `#` line comments. Returns `None` if `open` does not point at a
197/// `{` or the group is unbalanced.
198pub fn matching_close_brace(sparql: &str, open: usize) -> Option<usize> {
199    let bytes = sparql.as_bytes();
200    let n = bytes.len();
201    if open >= n || bytes[open] != b'{' {
202        return None;
203    }
204
205    let mut depth: i32 = 0;
206    let mut in_string: Option<u8> = None;
207    let mut in_iri = false;
208    let mut in_comment = false;
209    let mut escaped = false;
210    let mut i = open;
211
212    while i < n {
213        let b = bytes[i];
214
215        if let Some(quote) = in_string {
216            if escaped {
217                escaped = false;
218            } else if b == b'\\' {
219                escaped = true;
220            } else if b == quote {
221                in_string = None;
222            }
223            i += 1;
224            continue;
225        }
226
227        if in_iri {
228            if b == b'>' {
229                in_iri = false;
230            }
231            i += 1;
232            continue;
233        }
234
235        if in_comment {
236            if b == b'\n' {
237                in_comment = false;
238            }
239            i += 1;
240            continue;
241        }
242
243        match b {
244            b'"' | b'\'' => in_string = Some(b),
245            b'<' => in_iri = true,
246            b'#' => in_comment = true,
247            b'{' => depth += 1,
248            b'}' => {
249                depth -= 1;
250                if depth == 0 {
251                    return Some(i);
252                }
253            }
254            _ => {}
255        }
256
257        i += 1;
258    }
259
260    None
261}
262
263/// Detect the top-level query form by picking the earliest top-level form
264/// keyword (`SELECT` / `ASK` / `CONSTRUCT` / `DESCRIBE`). This naturally ignores
265/// `PREFIX`/`BASE` prologue and keywords that appear inside IRIs, literals, or
266/// nested sub-queries (which necessarily start later than the outer form).
267pub fn detect_query_form(sparql: &str) -> QueryForm {
268    let candidates = [
269        (QueryForm::Select, "SELECT"),
270        (QueryForm::Ask, "ASK"),
271        (QueryForm::Construct, "CONSTRUCT"),
272        (QueryForm::Describe, "DESCRIBE"),
273    ];
274
275    let mut best: Option<(usize, QueryForm)> = None;
276    for (form, kw) in candidates {
277        if let Some(pos) = find_keyword(sparql, kw) {
278            match best {
279                Some((best_pos, _)) if best_pos <= pos => {}
280                _ => best = Some((pos, form)),
281            }
282        }
283    }
284
285    best.map(|(_, form)| form).unwrap_or(QueryForm::Unknown)
286}
287
288/// Locate the byte index of the `{` that opens the WHERE `GroupGraphPattern`,
289/// honoring the optional `WHERE` keyword.
290///
291/// * When the `WHERE` keyword is present (as a top-level word), the opening
292///   brace of the group that follows it is returned. For
293///   `CONSTRUCT { template } WHERE { pattern }` this correctly yields the
294///   pattern group.
295/// * When `WHERE` is omitted, the group that would have followed it is used:
296///   the first top-level `{ ... }` group for `SELECT`/`ASK`/`DESCRIBE`, and the
297///   group *after* the template for `CONSTRUCT { template } { pattern }`.
298pub fn locate_where_brace(sparql: &str) -> Option<usize> {
299    if let Some(where_pos) = find_keyword(sparql, "WHERE") {
300        return next_group_open_brace(sparql, where_pos + "WHERE".len());
301    }
302
303    match detect_query_form(sparql) {
304        QueryForm::Construct => {
305            // The first top-level group is the CONSTRUCT template; the graph
306            // pattern is the group that follows it.
307            let template_open = next_group_open_brace(sparql, 0)?;
308            let template_close = matching_close_brace(sparql, template_open)?;
309            next_group_open_brace(sparql, template_close + 1)
310        }
311        _ => next_group_open_brace(sparql, 0),
312    }
313}
314
315/// Convenience helper returning the `(open, close)` byte indices (inclusive) of
316/// the WHERE `GroupGraphPattern` braces, or `None` when no group is present.
317pub fn locate_where_group(sparql: &str) -> Option<(usize, usize)> {
318    let open = locate_where_brace(sparql)?;
319    let close = matching_close_brace(sparql, open)?;
320    Some((open, close))
321}
322
323/// Return the byte offset at which the `SELECT` projection clause ends — i.e.
324/// the position of the top-level `WHERE` keyword when present, otherwise the
325/// opening brace of the `GroupGraphPattern`. `select_start` is the byte offset
326/// of the `SELECT` keyword. Returns `None` when no group pattern can be found.
327pub fn select_projection_end(sparql: &str, select_start: usize) -> Option<usize> {
328    if let Some(where_pos) = find_keyword(sparql, "WHERE") {
329        if where_pos > select_start {
330            return Some(where_pos);
331        }
332    }
333    next_group_open_brace(sparql, select_start)
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339
340    #[test]
341    fn find_keyword_ignores_iri_substring() {
342        // "SOMEWHERE" contains "WHERE" but only inside an IRI -> must be skipped.
343        let q = "SELECT * { ?s <http://example.org/somewhere> ?o }";
344        assert_eq!(find_keyword(q, "WHERE"), None);
345    }
346
347    #[test]
348    fn find_keyword_case_insensitive_word() {
349        let q = "SELECT * where { ?s ?p ?o }";
350        let pos = find_keyword(q, "WHERE").expect("keyword present");
351        assert_eq!(&q[pos..pos + 5], "where");
352    }
353
354    #[test]
355    fn locate_where_brace_with_keyword() {
356        let q = "SELECT * WHERE { ?s ?p ?o }";
357        let open = locate_where_brace(q).expect("group present");
358        assert_eq!(q.as_bytes()[open], b'{');
359        // Group content matches.
360        let (o, c) = locate_where_group(q).expect("group");
361        assert_eq!(&q[o + 1..c], " ?s ?p ?o ");
362    }
363
364    #[test]
365    fn locate_where_brace_without_keyword_select() {
366        let q = "SELECT * { ?s ?p ?o }";
367        let (o, c) = locate_where_group(q).expect("group");
368        assert_eq!(&q[o + 1..c], " ?s ?p ?o ");
369    }
370
371    #[test]
372    fn locate_where_brace_without_keyword_ask() {
373        let q = "ASK { ?s ?p ?o }";
374        let (o, c) = locate_where_group(q).expect("group");
375        assert_eq!(&q[o + 1..c], " ?s ?p ?o ");
376    }
377
378    #[test]
379    fn locate_where_brace_construct_with_where() {
380        let q = "CONSTRUCT { ?a ?b ?c } WHERE { ?s ?p ?o }";
381        let (o, c) = locate_where_group(q).expect("group");
382        assert_eq!(&q[o + 1..c], " ?s ?p ?o ");
383    }
384
385    #[test]
386    fn locate_where_brace_construct_without_where() {
387        let q = "CONSTRUCT { ?a ?b ?c } { ?s ?p ?o }";
388        let (o, c) = locate_where_group(q).expect("group");
389        assert_eq!(&q[o + 1..c], " ?s ?p ?o ");
390    }
391
392    #[test]
393    fn detect_query_form_basic() {
394        assert_eq!(detect_query_form("ASK { ?s ?p ?o }"), QueryForm::Ask);
395        assert_eq!(
396            detect_query_form("SELECT * { ?s ?p ?o }"),
397            QueryForm::Select
398        );
399        assert_eq!(
400            detect_query_form("CONSTRUCT { ?s ?p ?o } { ?s ?p ?o }"),
401            QueryForm::Construct
402        );
403        assert_eq!(
404            detect_query_form("DESCRIBE <http://example.org/x>"),
405            QueryForm::Describe
406        );
407    }
408
409    #[test]
410    fn matching_close_brace_nested() {
411        let q = "{ ?s ?p ?o OPTIONAL { ?a ?b ?c } }";
412        let close = matching_close_brace(q, 0).expect("balanced");
413        assert_eq!(close, q.len() - 1);
414    }
415
416    #[test]
417    fn select_projection_end_without_where() {
418        let q = "SELECT ?x ?y { ?x ?p ?y }";
419        let select_start = find_keyword(q, "SELECT").expect("select");
420        let end = select_projection_end(q, select_start).expect("end");
421        assert_eq!(q.as_bytes()[end], b'{');
422        assert_eq!(&q[select_start + 6..end], " ?x ?y ");
423    }
424
425    #[test]
426    fn find_keyword_ignores_keyword_in_comment() {
427        // The first "WHERE" sits inside a # line comment and must be skipped; the
428        // real keyword on the next line is the one located.
429        let q = "SELECT * # WHERE inside a comment\nWHERE { ?s ?p ?o }";
430        let pos = find_keyword(q, "WHERE").expect("real WHERE present");
431        assert_eq!(&q[pos..pos + 5], "WHERE");
432        let newline = q.find('\n').expect("newline present");
433        assert!(pos > newline, "matched the WHERE after the comment line");
434    }
435
436    #[test]
437    fn find_keyword_hash_in_string_is_not_comment() {
438        // A '#' inside a string literal must not start a comment, so the "WHERE"
439        // that follows the string on the same line is still located.
440        let q = "SELECT * \"# not a comment WHERE\" WHERE { ?s ?p ?o }";
441        let pos = find_keyword(q, "WHERE").expect("WHERE present");
442        let close_quote = q.rfind('"').expect("closing quote");
443        assert!(pos > close_quote, "matched the real WHERE after the string");
444    }
445
446    #[test]
447    fn find_keyword_hash_in_iri_is_not_comment() {
448        // '#' is a legal IRI fragment delimiter; it must not start a comment, so
449        // the "WHERE" after the IRI on the same line is still located.
450        let q = "SELECT * { ?s <http://example.org/x#frag> ?o } WHERE { ?a ?b ?c }";
451        let pos = find_keyword(q, "WHERE").expect("WHERE present");
452        let frag = q.find("frag").expect("frag present");
453        assert!(pos > frag, "matched the real WHERE after the IRI fragment");
454    }
455
456    #[test]
457    fn next_group_open_brace_skips_brace_in_comment() {
458        // A '{' inside a comment must not be taken as the group open.
459        let q = "SELECT * # { not this one\nWHERE { ?s ?p ?o }";
460        let open = next_group_open_brace(q, 0).expect("group present");
461        let newline = q.find('\n').expect("newline present");
462        assert!(open > newline, "skipped the fake brace inside the comment");
463        assert_eq!(q.as_bytes()[open], b'{');
464    }
465
466    #[test]
467    fn matching_close_brace_skips_brace_in_comment() {
468        // A '}' inside a comment must not close the group prematurely.
469        let q = "{ ?s ?p ?o # } fake close\n ?a ?b ?c }";
470        let close = matching_close_brace(q, 0).expect("balanced");
471        assert_eq!(close, q.len() - 1);
472    }
473}
oxirs_core/sparql/query_locator.rs

oxirs_core/sparql/
query_locator.rs
