uqa_sql/
fts_query.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Full-text search query-string parser.
8//!
9//! Grammar
10//! -------
11//! ```text
12//!     query      = or_expr
13//!     or_expr    = and_expr ( 'OR' and_expr )*
14//!     and_expr   = unary ( ('AND' | <implicit>) unary )*
15//!     unary      = 'NOT' unary | primary
16//!     primary    = '(' or_expr ')'
17//!                | TERM ':' PHRASE          -- field:"phrase"
18//!                | TERM ':' VECTOR          -- field:[0.1, 0.2]
19//!                | TERM ':' TERM            -- field:term
20//!                | PHRASE                   -- "phrase"
21//!                | TERM                     -- bare term
22//! ```
23//!
24//! Operators AND / OR / NOT are case-insensitive keywords. Adjacent
25//! terms without an explicit operator are treated as implicit AND.
26//! Precedence: NOT > AND > OR.
27//!
28//! This module stops at the syntax AST. Physical retrieval lowering belongs
29//! to the engine/planner boundary, so the SQL crate remains independent of
30//! storage, scoring, fusion, and operator implementations.
31
32use crate::error::{Result, SQLError};
33
34// ---------------------------------------------------------------------
35// Token
36// ---------------------------------------------------------------------
37
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39pub enum FTSTokenType {
40    Term,
41    Phrase,
42    Vector,
43    And,
44    Or,
45    Not,
46    LParen,
47    RParen,
48    Colon,
49    Eof,
50}
51
52#[derive(Debug, Clone)]
53pub struct FTSToken {
54    pub kind: FTSTokenType,
55    pub value: String,
56    pub pos: usize,
57}
58
59#[expect(
60    clippy::too_many_lines,
61    reason = "FTS parser keeps token precedence in one state machine"
62)]
63pub fn tokenize(source: &str) -> Result<Vec<FTSToken>> {
64    let mut tokens: Vec<FTSToken> = Vec::new();
65    let bytes: Vec<char> = source.chars().collect();
66    let n = bytes.len();
67    let mut i = 0_usize;
68
69    while i < n {
70        let ch = bytes[i];
71        if ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' {
72            i += 1;
73            continue;
74        }
75        match ch {
76            '(' => {
77                tokens.push(FTSToken {
78                    kind: FTSTokenType::LParen,
79                    value: "(".into(),
80                    pos: i,
81                });
82                i += 1;
83                continue;
84            }
85            ')' => {
86                tokens.push(FTSToken {
87                    kind: FTSTokenType::RParen,
88                    value: ")".into(),
89                    pos: i,
90                });
91                i += 1;
92                continue;
93            }
94            ':' => {
95                tokens.push(FTSToken {
96                    kind: FTSTokenType::Colon,
97                    value: ":".into(),
98                    pos: i,
99                });
100                i += 1;
101                continue;
102            }
103            '"' => {
104                let start = i;
105                i += 1;
106                let body_start = i;
107                while i < n && bytes[i] != '"' {
108                    i += 1;
109                }
110                if i >= n {
111                    return Err(SQLError::TypeMismatch(format!(
112                        "Unterminated quoted phrase starting at position {start}"
113                    )));
114                }
115                let phrase: String = bytes[body_start..i].iter().collect();
116                tokens.push(FTSToken {
117                    kind: FTSTokenType::Phrase,
118                    value: phrase,
119                    pos: start,
120                });
121                i += 1;
122                continue;
123            }
124            '[' => {
125                let start = i;
126                i += 1;
127                let body_start = i;
128                while i < n && bytes[i] != ']' {
129                    i += 1;
130                }
131                if i >= n {
132                    return Err(SQLError::TypeMismatch(format!(
133                        "Unterminated vector literal starting at position {start}"
134                    )));
135                }
136                let content: String = bytes[body_start..i].iter().collect();
137                tokens.push(FTSToken {
138                    kind: FTSTokenType::Vector,
139                    value: content,
140                    pos: start,
141                });
142                i += 1;
143                continue;
144            }
145            _ => {}
146        }
147        if is_word_char(ch) {
148            let start = i;
149            while i < n && is_word_char(bytes[i]) {
150                i += 1;
151            }
152            let word: String = bytes[start..i].iter().collect();
153            let lower = word.to_ascii_lowercase();
154            let kind = match lower.as_str() {
155                "and" => FTSTokenType::And,
156                "or" => FTSTokenType::Or,
157                "not" => FTSTokenType::Not,
158                _ => FTSTokenType::Term,
159            };
160            tokens.push(FTSToken {
161                kind,
162                value: word,
163                pos: start,
164            });
165            continue;
166        }
167        return Err(SQLError::TypeMismatch(format!(
168            "Unexpected character {ch:?} at position {i}"
169        )));
170    }
171
172    tokens.push(FTSToken {
173        kind: FTSTokenType::Eof,
174        value: String::new(),
175        pos: n,
176    });
177    Ok(tokens)
178}
179
180fn is_word_char(ch: char) -> bool {
181    !matches!(
182        ch,
183        ' ' | '\t' | '\n' | '\r' | '(' | ')' | ':' | '"' | '[' | ']'
184    )
185}
186
187// ---------------------------------------------------------------------
188// AST
189// ---------------------------------------------------------------------
190
191#[derive(Debug, Clone)]
192pub enum FTSNode {
193    Term {
194        field: Option<String>,
195        term: String,
196    },
197    Phrase {
198        field: Option<String>,
199        phrase: String,
200    },
201    Vector {
202        field: Option<String>,
203        values: Vec<f32>,
204    },
205    And(Box<FTSNode>, Box<FTSNode>),
206    Or(Box<FTSNode>, Box<FTSNode>),
207    Not(Box<FTSNode>),
208}
209
210// ---------------------------------------------------------------------
211// Parser
212// ---------------------------------------------------------------------
213
214pub struct FTSParser {
215    tokens: Vec<FTSToken>,
216    pos: usize,
217}
218
219impl FTSParser {
220    pub fn new(tokens: Vec<FTSToken>) -> Self {
221        Self { tokens, pos: 0 }
222    }
223
224    pub fn parse(mut self) -> Result<FTSNode> {
225        if self.peek().kind == FTSTokenType::Eof {
226            return Err(SQLError::TypeMismatch("Empty query".into()));
227        }
228        let node = self.or_expr()?;
229        if self.peek().kind != FTSTokenType::Eof {
230            let tok = self.peek();
231            return Err(SQLError::TypeMismatch(format!(
232                "Unexpected token {:?} at position {}",
233                tok.value, tok.pos
234            )));
235        }
236        Ok(node)
237    }
238
239    fn peek(&self) -> &FTSToken {
240        &self.tokens[self.pos]
241    }
242
243    fn advance(&mut self) -> FTSToken {
244        let tok = self.tokens[self.pos].clone();
245        self.pos += 1;
246        tok
247    }
248
249    fn expect(&mut self, kind: FTSTokenType) -> Result<FTSToken> {
250        let tok = self.advance();
251        if tok.kind != kind {
252            return Err(SQLError::TypeMismatch(format!(
253                "Expected {:?}, got {:?} ({:?}) at position {}",
254                kind, tok.kind, tok.value, tok.pos
255            )));
256        }
257        Ok(tok)
258    }
259
260    fn or_expr(&mut self) -> Result<FTSNode> {
261        let mut left = self.and_expr()?;
262        while self.peek().kind == FTSTokenType::Or {
263            self.advance();
264            let right = self.and_expr()?;
265            left = FTSNode::Or(Box::new(left), Box::new(right));
266        }
267        Ok(left)
268    }
269
270    fn and_expr(&mut self) -> Result<FTSNode> {
271        let mut left = self.unary()?;
272        loop {
273            let kind = self.peek().kind;
274            if kind == FTSTokenType::And {
275                self.advance();
276                let right = self.unary()?;
277                left = FTSNode::And(Box::new(left), Box::new(right));
278            } else if matches!(
279                kind,
280                FTSTokenType::Term
281                    | FTSTokenType::Phrase
282                    | FTSTokenType::Vector
283                    | FTSTokenType::LParen
284                    | FTSTokenType::Not
285            ) {
286                let right = self.unary()?;
287                left = FTSNode::And(Box::new(left), Box::new(right));
288            } else {
289                break;
290            }
291        }
292        Ok(left)
293    }
294
295    fn unary(&mut self) -> Result<FTSNode> {
296        if self.peek().kind == FTSTokenType::Not {
297            self.advance();
298            let operand = self.unary()?;
299            return Ok(FTSNode::Not(Box::new(operand)));
300        }
301        self.primary()
302    }
303
304    fn primary(&mut self) -> Result<FTSNode> {
305        let kind = self.peek().kind;
306        if kind == FTSTokenType::LParen {
307            self.advance();
308            let node = self.or_expr()?;
309            self.expect(FTSTokenType::RParen)?;
310            return Ok(node);
311        }
312        if kind == FTSTokenType::Phrase {
313            let tok = self.advance();
314            return Ok(FTSNode::Phrase {
315                field: None,
316                phrase: tok.value,
317            });
318        }
319        if kind == FTSTokenType::Vector {
320            let tok = self.advance();
321            return Ok(FTSNode::Vector {
322                field: None,
323                values: parse_vector_literal(&tok.value)?,
324            });
325        }
326        if kind == FTSTokenType::Term {
327            let tok = self.advance();
328            if self.peek().kind == FTSTokenType::Colon {
329                self.advance();
330                let next = self.peek().clone();
331                match next.kind {
332                    FTSTokenType::Phrase => {
333                        self.advance();
334                        return Ok(FTSNode::Phrase {
335                            field: Some(tok.value),
336                            phrase: next.value,
337                        });
338                    }
339                    FTSTokenType::Vector => {
340                        self.advance();
341                        return Ok(FTSNode::Vector {
342                            field: Some(tok.value),
343                            values: parse_vector_literal(&next.value)?,
344                        });
345                    }
346                    FTSTokenType::Term => {
347                        self.advance();
348                        return Ok(FTSNode::Term {
349                            field: Some(tok.value),
350                            term: next.value,
351                        });
352                    }
353                    other => {
354                        return Err(SQLError::TypeMismatch(format!(
355                            "Expected term, phrase, or vector after ':', got {other:?} at position {}",
356                            next.pos
357                        )));
358                    }
359                }
360            }
361            return Ok(FTSNode::Term {
362                field: None,
363                term: tok.value,
364            });
365        }
366        let tok = self.peek().clone();
367        Err(SQLError::TypeMismatch(format!(
368            "Unexpected token {:?} ({:?}) at position {}",
369            tok.kind, tok.value, tok.pos
370        )))
371    }
372}
373
374fn parse_vector_literal(content: &str) -> Result<Vec<f32>> {
375    let trimmed = content.trim();
376    if trimmed.is_empty() {
377        return Err(SQLError::TypeMismatch("Empty vector literal".into()));
378    }
379    trimmed
380        .split(',')
381        .map(|s| {
382            s.trim()
383                .parse::<f32>()
384                .map_err(|e| SQLError::TypeMismatch(format!("Malformed vector literal: {e}")))
385        })
386        .collect()
387}
388
389/// Tokenize and parse a full-text query string without choosing a physical
390/// retrieval representation.
391pub fn parse_query_string(query_string: &str) -> Result<FTSNode> {
392    let tokens = tokenize(query_string)?;
393    FTSParser::new(tokens).parse()
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399
400    #[test]
401    fn tokenize_terms_and_phrase() {
402        let tokens = tokenize(r#"hello "world today" foo"#).unwrap();
403        let kinds: Vec<_> = tokens.iter().map(|t| t.kind).collect();
404        assert_eq!(
405            kinds,
406            vec![
407                FTSTokenType::Term,
408                FTSTokenType::Phrase,
409                FTSTokenType::Term,
410                FTSTokenType::Eof,
411            ]
412        );
413        assert_eq!(tokens[1].value, "world today");
414    }
415
416    #[test]
417    fn tokenize_vector() {
418        let tokens = tokenize("[0.1, 0.2, 0.3]").unwrap();
419        assert_eq!(tokens[0].kind, FTSTokenType::Vector);
420        assert_eq!(tokens[0].value, "0.1, 0.2, 0.3");
421    }
422
423    #[test]
424    fn parse_implicit_and() {
425        let tokens = tokenize("rust ferris").unwrap();
426        let ast = FTSParser::new(tokens).parse().unwrap();
427        assert!(matches!(ast, FTSNode::And(_, _)));
428    }
429
430    #[test]
431    fn parse_field_qualified_term() {
432        let tokens = tokenize("title:rust").unwrap();
433        let ast = FTSParser::new(tokens).parse().unwrap();
434        match ast {
435            FTSNode::Term { field, term } => {
436                assert_eq!(field.as_deref(), Some("title"));
437                assert_eq!(term, "rust");
438            }
439            _ => panic!("expected Term"),
440        }
441    }
442
443    #[test]
444    fn parse_not_precedence() {
445        let tokens = tokenize("NOT foo OR bar").unwrap();
446        let ast = FTSParser::new(tokens).parse().unwrap();
447        // Should parse as (NOT foo) OR bar.
448        match ast {
449            FTSNode::Or(left, _) => match *left {
450                FTSNode::Not(_) => {}
451                _ => panic!("expected NOT on left"),
452            },
453            _ => panic!("expected OR"),
454        }
455    }
456
457    #[test]
458    fn parse_query_string_stops_at_syntax_ast() {
459        let ast = parse_query_string("body:rust OR embedding:[1, 0]").unwrap();
460        assert!(matches!(ast, FTSNode::Or(_, _)));
461    }
462}
uqa_sql/fts_query.rs

uqa_sql/
fts_query.rs
