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

uqa_sql/
fts_query.rs
