nedb_engine/
nql.rs

1//! NQL (NEDB Query Language) parser and executor for v2 DAG storage.
2//!
3//! Grammar:
4//!   FROM coll
5//!     [AS OF seq]
6//!     [VALID AS OF "date"]
7//!     [WHERE field op value [AND field op value]*]
8//!     [SEARCH "text"]
9//!     [ORDER BY field [DESC]]
10//!     [LIMIT n]
11//!     [GROUP BY field COUNT|SUM|AVG|MIN|MAX]
12//!     [TRACE caused_by [REVERSE]]
13
14use std::collections::HashMap;
15use anyhow::{bail, Result};
16use serde_json::{json, Value};
17
18use crate::db::Db;
19use crate::index::OrderedValue;
20use crate::store::Node;
21
22// ── Token types ──────────────────────────────────────────────────────────────
23
24#[derive(Debug, Clone, PartialEq)]
25enum Tok {
26    Kw(String),     // uppercase keyword: FROM, WHERE, ORDER, BY, AS, OF, VALID, LIMIT, GROUP, TRACE, REVERSE, AND, DESC, COUNT, SUM, AVG, MIN, MAX, SEARCH
27    Ident(String),  // field name or collection name (lowercase/mixed)
28    Str(String),    // "quoted string"
29    Num(f64),       // numeric literal
30    Op(String),     // = != > < >= <=
31    Eof,
32}
33
34struct Lexer<'a> {
35    src:  &'a str,
36    pos:  usize,
37}
38
39impl<'a> Lexer<'a> {
40    fn new(src: &'a str) -> Self { Self { src, pos: 0 } }
41
42    fn peek_char(&self) -> Option<char> { self.src[self.pos..].chars().next() }
43
44    fn skip_ws(&mut self) {
45        while let Some(c) = self.peek_char() {
46            if c.is_whitespace() { self.pos += c.len_utf8(); } else { break; }
47        }
48    }
49
50    fn next_tok(&mut self) -> Tok {
51        self.skip_ws();
52        if self.pos >= self.src.len() { return Tok::Eof; }
53
54        let c = self.peek_char().unwrap();
55
56        // Quoted string.
57        //
58        // A backslash escapes a following double-quote (\" -> a literal " that
59        // does NOT end the string). This is purely additive: a literal quote
60        // was previously impossible to express — the first " always closed the
61        // string — so no existing query can rely on the old meaning of \" and
62        // nothing breaks. Every OTHER backslash stays literal, so raw-backslash
63        // values (e.g. a Windows path) keep matching exactly as before; a
64        // regression test pins that. (A fully C-style scheme where \\ -> \
65        // would instead change the meaning of every existing backslash query,
66        // so it is deliberately NOT done here.)
67        if c == '"' {
68            self.pos += 1;
69            let mut s = String::new();
70            while let Some(ch) = self.peek_char() {
71                if ch == '"' {
72                    break;
73                }
74                if ch == '\\' {
75                    // Look at the next char: only \" collapses to ". A trailing
76                    // backslash (nothing after it) or \x for any other x stays
77                    // a literal backslash, preserving prior behavior.
78                    let next = self.src[self.pos + 1..].chars().next();
79                    if next == Some('"') {
80                        s.push('"');
81                        self.pos += 1 + 1; // consume the backslash and the quote
82                        continue;
83                    }
84                }
85                s.push(ch);
86                self.pos += ch.len_utf8();
87            }
88            if self.peek_char() == Some('"') {
89                self.pos += 1;
90            }
91            return Tok::Str(s);
92        }
93
94        // Two-char operators
95        if self.pos + 1 < self.src.len() {
96            let two = &self.src[self.pos..self.pos+2];
97            if matches!(two, "!=" | ">=" | "<=") {
98                self.pos += 2;
99                return Tok::Op(two.to_string());
100            }
101        }
102
103        // One-char operators
104        if matches!(c, '=' | '>' | '<') {
105            self.pos += 1;
106            return Tok::Op(c.to_string());
107        }
108
109        // Number
110        if c.is_ascii_digit() || (c == '-' && self.src[self.pos+1..].starts_with(|d: char| d.is_ascii_digit())) {
111            let start = self.pos;
112            if c == '-' { self.pos += 1; }
113            while let Some(d) = self.peek_char() {
114                if d.is_ascii_digit() || d == '.' { self.pos += 1; } else { break; }
115            }
116            let n: f64 = self.src[start..self.pos].parse().unwrap_or(0.0);
117            return Tok::Num(n);
118        }
119
120        // Keyword or identifier
121        if c.is_alphabetic() || c == '_' {
122            let start = self.pos;
123            while let Some(ch) = self.peek_char() {
124                if ch.is_alphanumeric() || ch == '_' || ch == '.' || ch == ':' {
125                    self.pos += ch.len_utf8();
126                } else { break; }
127            }
128            let word = &self.src[start..self.pos];
129            let upper = word.to_uppercase();
130            let keywords = ["FROM","AS","OF","VALID","WHERE","AND","ORDER","BY",
131                            "DESC","LIMIT","GROUP","COUNT","SUM","AVG","MIN","MAX",
132                            "TRACE","TRAVERSE","REVERSE","SEARCH","NOT","NULL","TRUE","FALSE"];
133            if keywords.contains(&upper.as_str()) {
134                return Tok::Kw(upper);
135            }
136            return Tok::Ident(word.to_string());
137        }
138
139        // Skip unknown char
140        self.pos += c.len_utf8();
141        self.next_tok()
142    }
143
144    fn tokenize(&mut self) -> Vec<Tok> {
145        let mut toks = vec![];
146        loop {
147            let t = self.next_tok();
148            if t == Tok::Eof { break; }
149            toks.push(t);
150        }
151        toks
152    }
153}
154
155// ── AST ──────────────────────────────────────────────────────────────────────
156
157#[derive(Debug, Clone)]
158pub struct WhereClause {
159    pub field: String,
160    pub op:    String,
161    pub value: Value,
162}
163
164#[derive(Debug, Clone)]
165pub enum GroupAgg { Count, Sum, Avg, Min, Max }
166
167#[derive(Debug, Clone)]
168pub struct Query {
169    pub coll:       String,
170    pub as_of:      Option<u64>,
171    pub valid_as_of: Option<String>,
172    pub wheres:     Vec<WhereClause>,
173    pub search:     Option<String>,
174    pub order_by:   Option<String>,
175    pub order_desc: bool,
176    pub limit:      Option<usize>,
177    pub group_by:   Option<(String, GroupAgg)>,
178    pub trace:      Option<String>,     // edge type (usually "caused_by")
179    pub trace_rev:  bool,
180    pub traverse:   Option<String>,     // named relation for TRAVERSE rel
181}
182
183// ── Parser ────────────────────────────────────────────────────────────────────
184
185struct Parser { toks: Vec<Tok>, pos: usize }
186
187impl Parser {
188    fn new(toks: Vec<Tok>) -> Self { Self { toks, pos: 0 } }
189
190    fn peek(&self) -> &Tok { self.toks.get(self.pos).unwrap_or(&Tok::Eof) }
191    fn advance(&mut self) -> Tok { let t = self.peek().clone(); self.pos += 1; t }
192
193    fn expect_kw(&mut self, kw: &str) -> Result<()> {
194        match self.advance() {
195            Tok::Kw(k) if k == kw => Ok(()),
196            other => bail!("expected keyword {}, got {:?}", kw, other),
197        }
198    }
199
200    fn parse_value(&mut self) -> Value {
201        match self.advance() {
202            Tok::Str(s)  => Value::String(s),
203            Tok::Num(n)  => json!(n),
204            Tok::Kw(k) if k == "NULL"  => Value::Null,
205            Tok::Kw(k) if k == "TRUE"  => Value::Bool(true),
206            Tok::Kw(k) if k == "FALSE" => Value::Bool(false),
207            Tok::Ident(s) => Value::String(s),
208            _ => Value::Null,
209        }
210    }
211
212    fn parse(&mut self) -> Result<Query> {
213        self.expect_kw("FROM")?;
214        let coll = match self.advance() {
215            Tok::Ident(s) | Tok::Kw(s) => s,
216            other => bail!("expected collection name, got {:?}", other),
217        };
218
219        let mut q = Query {
220            coll, as_of: None, valid_as_of: None,
221            wheres: vec![], search: None,
222            order_by: None, order_desc: false,
223            limit: None, group_by: None,
224            trace: None, trace_rev: false,
225            traverse: None,
226        };
227
228        loop {
229            match self.peek() {
230                Tok::Eof => break,
231
232                Tok::Kw(k) if k == "AS" => {
233                    self.advance();
234                    self.expect_kw("OF")?;
235                    match self.advance() {
236                        Tok::Num(n) => q.as_of = Some(n as u64),
237                        other => bail!("AS OF expects sequence number, got {:?}", other),
238                    }
239                }
240
241                Tok::Kw(k) if k == "VALID" => {
242                    self.advance();
243                    self.expect_kw("AS")?;
244                    self.expect_kw("OF")?;
245                    match self.advance() {
246                        Tok::Str(s) => q.valid_as_of = Some(s),
247                        other => bail!("VALID AS OF expects date string, got {:?}", other),
248                    }
249                }
250
251                Tok::Kw(k) if k == "WHERE" => {
252                    self.advance();
253                    loop {
254                        let field = match self.advance() {
255                            Tok::Ident(s) | Tok::Kw(s) => s,
256                            other => bail!("WHERE: expected field name, got {:?}", other),
257                        };
258                        let op = match self.advance() {
259                            Tok::Op(s) => s,
260                            other => bail!("WHERE: expected operator, got {:?}", other),
261                        };
262                        let value = self.parse_value();
263                        q.wheres.push(WhereClause { field, op, value });
264                        if let Tok::Kw(k) = self.peek() {
265                            if k == "AND" { self.advance(); } else { break; }
266                        } else { break; }
267                    }
268                }
269
270                Tok::Kw(k) if k == "SEARCH" => {
271                    self.advance();
272                    match self.advance() {
273                        Tok::Str(s) => q.search = Some(s),
274                        other => bail!("SEARCH expects quoted string, got {:?}", other),
275                    }
276                }
277
278                Tok::Kw(k) if k == "ORDER" => {
279                    self.advance();
280                    self.expect_kw("BY")?;
281                    let field = match self.advance() {
282                        Tok::Ident(s) | Tok::Kw(s) => s,
283                        other => bail!("ORDER BY: expected field, got {:?}", other),
284                    };
285                    q.order_by = Some(field);
286                    if let Tok::Kw(k) = self.peek() {
287                        if k == "DESC" { self.advance(); q.order_desc = true; }
288                    }
289                }
290
291                Tok::Kw(k) if k == "LIMIT" => {
292                    self.advance();
293                    match self.advance() {
294                        Tok::Num(n) => q.limit = Some(n as usize),
295                        other => bail!("LIMIT expects number, got {:?}", other),
296                    }
297                }
298
299                Tok::Kw(k) if k == "GROUP" => {
300                    self.advance();
301                    self.expect_kw("BY")?;
302                    let field = match self.advance() {
303                        Tok::Ident(s) | Tok::Kw(s) => s,
304                        other => bail!("GROUP BY: expected field, got {:?}", other),
305                    };
306                    let agg = match self.advance() {
307                        Tok::Kw(a) if a == "COUNT" => GroupAgg::Count,
308                        Tok::Kw(a) if a == "SUM"   => GroupAgg::Sum,
309                        Tok::Kw(a) if a == "AVG"   => GroupAgg::Avg,
310                        Tok::Kw(a) if a == "MIN"   => GroupAgg::Min,
311                        Tok::Kw(a) if a == "MAX"   => GroupAgg::Max,
312                        other => bail!("GROUP BY: expected aggregation, got {:?}", other),
313                    };
314                    q.group_by = Some((field, agg));
315                }
316
317                Tok::Kw(k) if k == "TRACE" => {
318                    self.advance();
319                    let edge = match self.advance() {
320                        Tok::Ident(s) | Tok::Kw(s) => s,
321                        other => bail!("TRACE: expected edge type, got {:?}", other),
322                    };
323                    q.trace = Some(edge);
324                    if let Tok::Kw(k) = self.peek() {
325                        if k == "REVERSE" { self.advance(); q.trace_rev = true; }
326                    }
327                }
328
329                Tok::Kw(k) if k == "TRAVERSE" => {
330                    self.advance();
331                    let rel = match self.advance() {
332                        Tok::Ident(s) | Tok::Kw(s) => s,
333                        other => bail!("TRAVERSE: expected relation name, got {:?}", other),
334                    };
335                    q.traverse = Some(rel);
336                }
337
338                _ => { self.advance(); } // skip unrecognised
339            }
340        }
341
342        Ok(q)
343    }
344}
345
346// ── Executor ──────────────────────────────────────────────────────────────────
347
348fn matches_where(node: &Node, w: &WhereClause) -> bool {
349    let field_val = if w.field == "_id" {
350        Value::String(node.id.clone())
351    } else if w.field == "_coll" {
352        Value::String(node.coll.clone())
353    } else if w.field == "_hash" {
354        Value::String(node.hash.clone())
355    } else {
356        node.data.get(&w.field).cloned().unwrap_or(Value::Null)
357    };
358
359    let a = OrderedValue::from(&field_val);
360    let b = OrderedValue::from(&w.value);
361
362    match w.op.as_str() {
363        "="  => a == b,
364        "!=" => a != b,
365        ">"  => a >  b,
366        "<"  => a <  b,
367        ">=" => a >= b,
368        "<=" => a <= b,
369        _    => false,
370    }
371}
372
373fn matches_valid_as_of(node: &Node, date: &str) -> bool {
374    // A node is valid at `date` if:
375    //   valid_from is None OR valid_from <= date
376    //   AND (valid_to is None OR valid_to > date)
377    let from_ok = node.valid_from.as_deref().map(|f| f <= date).unwrap_or(true);
378    let to_ok   = node.valid_to.as_deref().map(|t| t > date).unwrap_or(true);
379    from_ok && to_ok
380}
381
382fn node_contains_text(node: &Node, text: &str) -> bool {
383    let s = node.data.to_string().to_lowercase();
384    s.contains(&text.to_lowercase())
385}
386
387fn node_to_json(node: &Node) -> Value {
388    let mut obj = if let Value::Object(m) = &node.data {
389        m.clone()
390    } else {
391        serde_json::Map::new()
392    };
393    obj.insert("_id".to_string(),   Value::String(node.id.clone()));
394    obj.insert("_hash".to_string(), Value::String(node.hash.clone()));
395    obj.insert("_seq".to_string(),  json!(node.seq));
396    obj.insert("_coll".to_string(), Value::String(node.coll.clone()));
397    if let Some(ref vf) = node.valid_from {
398        obj.insert("_valid_from".to_string(), Value::String(vf.clone()));
399    }
400    if let Some(ref vt) = node.valid_to {
401        obj.insert("_valid_to".to_string(), Value::String(vt.clone()));
402    }
403    if !node.caused_by.is_empty() {
404        obj.insert("_caused_by".to_string(), Value::Array(
405            node.caused_by.iter().map(|h| Value::String(h.clone())).collect()
406        ));
407    }
408    Value::Object(obj)
409}
410
411/// Execute a NQL query against the DAG database.
412/// Parse NQL into a `Query` WITHOUT touching the database.
413///
414/// `execute` already does exactly this as its first step; exposing it separately
415/// lets callers validate a query before deciding to run it. The natural-language
416/// planner (`/v1/databases/:name/cast`) uses it to answer "is this runnable?"
417/// without side effects — checking the text against the real grammar rather than
418/// pattern-matching it, because the parser is the only authority on that.
419pub fn parse(nql: &str) -> Result<Query> {
420    let mut lexer = Lexer::new(nql);
421    let toks = lexer.tokenize();
422    let mut parser = Parser::new(toks);
423    parser.parse()
424}
425
426pub fn execute(db: &Db, nql: &str) -> Result<Vec<Value>> {
427    // One parse path, shared with the public `parse()` above — so validation and
428    // execution can never disagree about what is well-formed.
429    let q = parse(nql)?;
430
431    // ── Candidate generation ──────────────────────────────────────────────────
432
433    // Fast path: single equality filter on _id with no AS OF.
434    // Skip the O(n) collection scan — go straight to the id index (O(1) file read).
435    // This turns `FROM coll WHERE _id = "x" LIMIT 1` from a full-table-scan into
436    // a single file read, giving orders-of-magnitude speedup for point lookups.
437    let id_eq_fast_path: Option<String> = if q.as_of.is_none() && q.trace.is_none() {
438        q.wheres.iter().find_map(|w| {
439            if w.field == "_id" && w.op == "=" {
440                if let Value::String(ref id) = w.value { Some(id.clone()) } else { None }
441            } else { None }
442        })
443    } else { None };
444
445    let candidates: Vec<Node> = if let Some(ref target_id) = id_eq_fast_path {
446        // O(1) direct id-index lookup — skip full collection scan entirely
447        db.get(&q.coll, target_id).into_iter().collect()
448    } else if let Some(seq_target) = q.as_of {
449        // AS OF: return each doc's version at or before target seq
450        db.id_index.list_ids(&q.coll).into_iter()
451            .filter_map(|id| db.get_as_of(&q.coll, &id, seq_target))
452            .collect()
453    } else if let Some(ref order_field) = q.order_by {
454        // ORDER BY with optional sorted index — get candidates in order.
455        //
456        // Push LIMIT down into the index scan ONLY when nothing filters rows
457        // after candidate generation. WHERE / SEARCH / VALID AS OF all run on
458        // the candidate set below, so truncating to the top-k FIRST returns
459        // incomplete results: `WHERE n_tx > 100 ORDER BY height LIMIT 10`
460        // would fetch the 10 lowest blocks by height and then filter — losing
461        // matches past the top-k window. The Python reference filters → sorts
462        // → limits (engine.py execute()); this keeps the engines in agreement.
463        let has_post_filters = !q.wheres.is_empty()
464            || q.search.is_some()
465            || q.valid_as_of.is_some();
466        let limit = if has_post_filters {
467            9_999_999
468        } else {
469            q.limit.unwrap_or(9_999_999)
470        };
471        if q.order_desc {
472            db.order_by_desc(&q.coll, order_field, limit)
473        } else {
474            db.order_by_asc(&q.coll, order_field, limit)
475        }
476    } else if let (Some(n), true) = (q.limit, q.wheres.is_empty()
477            && q.search.is_none() && q.trace.is_none()
478            && q.traverse.is_none() && q.group_by.is_none()
479            && q.valid_as_of.is_none()) {
480        // LIMIT-only fast path: no filters, no ordering, no trace.
481        // Take only the first N IDs from the id-index and fetch those docs.
482        // This makes `FROM coll LIMIT 1` O(N) not O(total) — critical for
483        // the Studio "Preparing…" phase which samples every collection.
484        db.id_index
485            .list_ids(&q.coll)
486            .into_iter()
487            .take(n)
488            .filter_map(|id| db.get(&q.coll, &id))
489            .collect()
490    } else {
491        // Default: all docs in collection
492        db.list(&q.coll)
493    };
494
495    // ── WHERE filter ──────────────────────────────────────────────────────────
496
497    let mut rows: Vec<Node> = candidates.into_iter()
498        .filter(|n| q.wheres.iter().all(|w| matches_where(n, w)))
499        .filter(|n| q.valid_as_of.as_deref()
500                       .map(|d| matches_valid_as_of(n, d))
501                       .unwrap_or(true))
502        .filter(|n| q.search.as_deref()
503                       .map(|t| node_contains_text(n, t))
504                       .unwrap_or(true))
505        .collect();
506
507    // ── TRACE ─────────────────────────────────────────────────────────────────
508
509    if let Some(ref _edge_type) = q.trace {
510        let limit = q.limit.unwrap_or(1000);
511        let mut traced: Vec<Node> = vec![];
512        for root in &rows {
513            let chain = db.trace(&root.hash, q.trace_rev, limit);
514            traced.extend(chain);
515        }
516        rows = traced;
517    }
518
519    // ── TRAVERSE rel — one-hop named-relation lookup ──────────────────────────
520
521    if let Some(ref rel) = q.traverse {
522        let mut traversed: Vec<Node> = vec![];
523        for root in &rows {
524            let frm = format!("{}:{}", root.coll, root.id);
525            let neighbors = db.neighbors(&frm, rel);
526            traversed.extend(neighbors);
527        }
528        rows = traversed;
529    }
530
531    // ── ORDER BY (post-filter sort if no sorted index was used) ───────────────
532
533    if let Some(ref field) = q.order_by {
534        if q.as_of.is_some() || !q.wheres.is_empty() || q.search.is_some() {
535            // Re-sort after filtering
536            rows.sort_by(|a, b| {
537                let av = a.data.get(field).map(OrderedValue::from).unwrap_or(OrderedValue::Null);
538                let bv = b.data.get(field).map(OrderedValue::from).unwrap_or(OrderedValue::Null);
539                if q.order_desc { bv.cmp(&av) } else { av.cmp(&bv) }
540            });
541        }
542    }
543
544    // ── LIMIT ─────────────────────────────────────────────────────────────────
545
546    if let Some(n) = q.limit {
547        rows.truncate(n);
548    }
549
550    // ── GROUP BY ─────────────────────────────────────────────────────────────
551
552    if let Some((ref group_field, ref agg)) = q.group_by {
553        let mut groups: HashMap<String, Vec<f64>> = HashMap::new();
554        for node in &rows {
555            let key = node.data.get(group_field)
556                .map(|v| v.to_string().trim_matches('"').to_string())
557                .unwrap_or_else(|| "null".to_string());
558            let val = node.data.get(group_field)
559                .and_then(|v| v.as_f64())
560                .unwrap_or(1.0);
561            groups.entry(key).or_default().push(val);
562        }
563        let result: Vec<Value> = groups.into_iter().map(|(k, vals)| {
564            let agg_val = match agg {
565                GroupAgg::Count => vals.len() as f64,
566                GroupAgg::Sum   => vals.iter().sum(),
567                GroupAgg::Avg   => vals.iter().sum::<f64>() / vals.len() as f64,
568                GroupAgg::Min   => vals.iter().cloned().fold(f64::INFINITY, f64::min),
569                GroupAgg::Max   => vals.iter().cloned().fold(f64::NEG_INFINITY, f64::max),
570            };
571            json!({group_field: k, "value": agg_val, "count": vals.len()})
572        }).collect();
573        return Ok(result);
574    }
575
576    // ── Serialize ─────────────────────────────────────────────────────────────
577
578    Ok(rows.into_iter().map(|n| node_to_json(&n)).collect())
579}
580
581/// Parse and execute NQL, returning (rows, count).
582pub fn query(db: &Db, nql: &str) -> Result<(Vec<Value>, usize)> {
583    let rows = execute(db, nql)?;
584    let count = rows.len();
585    Ok((rows, count))
586}
587
588#[cfg(test)]
589mod tests {
590    use super::*;
591    use tempfile::tempdir;
592    use crate::db::Db;
593
594    // Returns (TempDir, Db) — the TempDir guard MUST be kept alive by the caller
595    // (`let (_tmp, db) = setup();`). If it dropped here, its Drop would delete the
596    // database directory out from under the live Db, and every objects.read()
597    // (loose object files live on disk) would fail → queries return 0 rows.
598    fn setup() -> (tempfile::TempDir, Db) {
599        let dir = tempdir().unwrap();
600        let db = Db::open(dir.path(), None).unwrap();
601        db.create_sorted_index("blocks", "height");
602        for h in 1u64..=5 {
603            db.put("blocks", &h.to_string(),
604                serde_json::json!({"height": h, "hash": format!("000{}", h), "n_tx": h * 2}),
605                vec![], None, None).unwrap();
606        }
607        (dir, db)
608    }
609
610    #[test]
611    fn from_all() {
612        let (_tmp, db) = setup();
613        let (rows, count) = query(&db, "FROM blocks").unwrap();
614        assert_eq!(count, 5);
615        let _ = rows;
616    }
617
618    #[test]
619    fn where_eq() {
620        let (_tmp, db) = setup();
621        let (rows, count) = query(&db, r#"FROM blocks WHERE _id = "3""#).unwrap();
622        assert_eq!(count, 1);
623        assert_eq!(rows[0]["_id"], "3");
624    }
625
626    #[test]
627    fn order_by_limit() {
628        let (_tmp, db) = setup();
629        let (rows, count) = query(&db, "FROM blocks ORDER BY height ASC LIMIT 3").unwrap();
630        assert_eq!(count, 3);
631        assert_eq!(rows[0]["height"], 1);
632        assert_eq!(rows[2]["height"], 3);
633    }
634
635    #[test]
636    fn order_by_desc() {
637        let (_tmp, db) = setup();
638        let (rows, _) = query(&db, "FROM blocks ORDER BY height DESC LIMIT 2").unwrap();
639        assert_eq!(rows[0]["height"], 5);
640    }
641
642    #[test]
643    fn where_gt() {
644        let (_tmp, db) = setup();
645        let (rows, _) = query(&db, "FROM blocks WHERE height > 3").unwrap();
646        assert_eq!(rows.len(), 2);
647    }
648
649    /// Regression: WHERE + ORDER BY + LIMIT must not truncate candidates
650    /// before the filter runs. setup() gives heights 1..=5 with n_tx = h*2;
651    /// the predicate matches ONLY the two highest heights (4, 5). The old
652    /// code passed LIMIT into the sorted-index top-k first: it fetched
653    /// heights [1, 2], filtered on n_tx >= 8, and returned ZERO rows even
654    /// though two matches exist. Python reference returns [4, 5].
655    #[test]
656    fn where_order_limit_does_not_truncate_before_filter() {
657        let (_tmp, db) = setup();
658        let (rows, count) =
659            query(&db, "FROM blocks WHERE n_tx >= 8 ORDER BY height LIMIT 2").unwrap();
660        assert_eq!(count, 2, "both matching rows must survive the limit");
661        let heights: Vec<u64> = rows.iter()
662            .filter_map(|r| r["height"].as_u64())
663            .collect();
664        assert_eq!(heights, vec![4, 5]);
665        // And the same shape DESC — top match first.
666        let (rows_d, _) =
667            query(&db, "FROM blocks WHERE n_tx >= 8 ORDER BY height DESC LIMIT 1").unwrap();
668        assert_eq!(rows_d.len(), 1);
669        assert_eq!(rows_d[0]["height"], 5);
670    }
671
672    #[test]
673    fn group_by_count() {
674        let (_tmp, db) = setup();
675        let (rows, _) = query(&db, "FROM blocks GROUP BY n_tx COUNT").unwrap();
676        assert_eq!(rows.len(), 5); // all unique n_tx values
677    }
678
679    #[test]
680    fn search() {
681        let (_tmp, db) = setup();
682        let (rows, _) = query(&db, r#"FROM blocks SEARCH "0003""#).unwrap();
683        assert_eq!(rows.len(), 1);
684    }
685
686    #[test]
687    fn as_of() {
688        let dir = tempdir().unwrap();
689        let db = Db::open(dir.path(), None).unwrap();
690        let v1 = db.put("docs", "x", serde_json::json!({"v": 1}), vec![], None, None).unwrap();
691        db.put("docs", "x", serde_json::json!({"v": 2}), vec![], None, None).unwrap();
692        let (rows, _) = query(&db, &format!("FROM docs AS OF {}", v1.seq)).unwrap();
693        assert_eq!(rows[0]["v"], 1);
694    }
695
696    #[test]
697    fn valid_as_of() {
698        let dir = tempdir().unwrap();
699        let db = Db::open(dir.path(), None).unwrap();
700        db.put("events", "e1", serde_json::json!({"type": "a"}), vec![],
701               Some("2025-01-01".to_string()), Some("2025-06-01".to_string())).unwrap();
702        db.put("events", "e2", serde_json::json!({"type": "b"}), vec![],
703               Some("2026-01-01".to_string()), None).unwrap();
704        let (rows, _) = query(&db, r#"FROM events VALID AS OF "2025-03-01""#).unwrap();
705        assert_eq!(rows.len(), 1);
706        assert_eq!(rows[0]["type"], "a");
707    }
708
709    // ── String-literal escaping ──────────────────────────────────────────────
710
711    #[test]
712    fn escaped_quote_matches_a_value_containing_a_quote() {
713        let dir = tempdir().unwrap();
714        let db = Db::open(dir.path(), None).unwrap();
715        db.put("m", "q", serde_json::json!({ "name": "say \"hi\"" }), vec![], None, None)
716            .unwrap();
717        db.put("m", "p", serde_json::json!({ "name": "plain" }), vec![], None, None).unwrap();
718
719        // \" inside the literal is a literal quote; the string does not end there.
720        let (rows, count) = query(&db, r#"FROM m WHERE name = "say \"hi\"""#).unwrap();
721        assert_eq!(count, 1, "the escaped-quote literal matches exactly one row");
722        assert_eq!(rows[0]["_id"], "q");
723    }
724
725    #[test]
726    fn raw_backslash_still_matches_literally() {
727        // REGRESSION GUARD: a lone backslash stays literal, so pre-existing
728        // backslash queries (Windows paths etc.) keep matching. This is the
729        // property that makes the \" addition non-breaking.
730        let dir = tempdir().unwrap();
731        let db = Db::open(dir.path(), None).unwrap();
732        db.put("m", "b", serde_json::json!({ "p": "back\\slash" }), vec![], None, None).unwrap();
733
734        let (rows, count) = query(&db, r#"FROM m WHERE p = "back\slash""#).unwrap();
735        assert_eq!(count, 1, "a raw backslash literal matches as before");
736        assert_eq!(rows[0]["_id"], "b");
737    }
738
739    #[test]
740    fn a_quote_can_no_longer_inject_trailing_clauses() {
741        // The security motivation: previously a value of `x" LIMIT 1` would
742        // terminate the literal and inject `LIMIT 1`. With \" the caller can
743        // escape the quote so it stays part of the value and matches nothing
744        // rogue. Here the escaped form matches the literal value verbatim.
745        let dir = tempdir().unwrap();
746        let db = Db::open(dir.path(), None).unwrap();
747        db.put("m", "x", serde_json::json!({ "v": "a\"b" }), vec![], None, None).unwrap();
748        let (rows, count) = query(&db, r#"FROM m WHERE v = "a\"b""#).unwrap();
749        assert_eq!(count, 1);
750        assert_eq!(rows[0]["_id"], "x");
751    }
752}
753
754#[cfg(test)]
755mod tests_traverse {
756    use super::*;
757    use tempfile::tempdir;
758    use crate::db::Db;
759
760    #[test]
761    fn traverse_one_hop() {
762        let db = Db::in_memory();
763        db.put("driver", "d1", serde_json::json!({"name": "Bob"}),   vec![], None, None).unwrap();
764        db.put("driver", "d2", serde_json::json!({"name": "Carol"}), vec![], None, None).unwrap();
765        db.put("trip",   "t1", serde_json::json!({"status": "req"}), vec![], None, None).unwrap();
766        db.put("trip",   "t2", serde_json::json!({"status": "ok"}),  vec![], None, None).unwrap();
767
768        db.link("driver:d1", "handles", "trip:t1").unwrap();
769        db.link("driver:d1", "handles", "trip:t2").unwrap();
770
771        let (rows, count) = query(&db, r#"FROM driver WHERE _id = "d1" TRAVERSE handles"#).unwrap();
772        assert_eq!(count, 2);
773        let ids: std::collections::HashSet<&str> = rows.iter()
774            .filter_map(|r| r["_id"].as_str())
775            .collect();
776        assert!(ids.contains("t1") && ids.contains("t2"));
777    }
778
779    #[test]
780    fn traverse_returns_empty_when_no_links() {
781        let db = Db::in_memory();
782        db.put("driver", "d1", serde_json::json!({"name": "Bob"}), vec![], None, None).unwrap();
783        let (rows, count) = query(&db, r#"FROM driver WHERE _id = "d1" TRAVERSE handles"#).unwrap();
784        assert_eq!(count, 0);
785        assert!(rows.is_empty());
786    }
787
788    #[test]
789    fn traverse_multi_source() {
790        // When WHERE matches multiple rows, TRAVERSE unions all their neighbors
791        let db = Db::in_memory();
792        db.put("driver", "d1", serde_json::json!({"status": "active"}), vec![], None, None).unwrap();
793        db.put("driver", "d2", serde_json::json!({"status": "active"}), vec![], None, None).unwrap();
794        db.put("trip",   "t1", serde_json::json!({"n": 1}), vec![], None, None).unwrap();
795        db.put("trip",   "t2", serde_json::json!({"n": 2}), vec![], None, None).unwrap();
796        db.put("trip",   "t3", serde_json::json!({"n": 3}), vec![], None, None).unwrap();
797
798        db.link("driver:d1", "handles", "trip:t1").unwrap();
799        db.link("driver:d1", "handles", "trip:t2").unwrap();
800        db.link("driver:d2", "handles", "trip:t3").unwrap();
801
802        let (_rows, count) = query(&db, r#"FROM driver WHERE status = "active" TRAVERSE handles"#).unwrap();
803        assert_eq!(count, 3);
804    }
805
806    #[test]
807    fn traverse_nql_keyword_case_insensitive() {
808        // Parser normalises to uppercase — "traverse" and "TRAVERSE" both work
809        let db = Db::in_memory();
810        db.put("driver", "d1", serde_json::json!({}), vec![], None, None).unwrap();
811        db.put("trip",   "t1", serde_json::json!({}), vec![], None, None).unwrap();
812        db.link("driver:d1", "handles", "trip:t1").unwrap();
813        // uppercase
814        let (r1, c1) = query(&db, r#"FROM driver WHERE _id = "d1" TRAVERSE handles"#).unwrap();
815        assert_eq!(c1, 1);
816        // lowercase (lexer uppercases keywords)
817        let (r2, c2) = query(&db, r#"FROM driver WHERE _id = "d1" traverse handles"#).unwrap();
818        assert_eq!(c2, 1);
819        assert_eq!(r1[0]["_id"], r2[0]["_id"]);
820    }
821
822    #[test]
823    fn traverse_durable() {
824        let dir = tempdir().unwrap();
825        {
826            let db = Db::open(dir.path(), None).unwrap();
827            db.put("driver", "d1", serde_json::json!({"name": "Bob"}),   vec![], None, None).unwrap();
828            db.put("trip",   "t1", serde_json::json!({"status": "req"}), vec![], None, None).unwrap();
829            db.link("driver:d1", "handles", "trip:t1").unwrap();
830        }
831        let db2 = Db::open(dir.path(), None).unwrap();
832        db2.startup_ready.store(true, std::sync::atomic::Ordering::SeqCst);
833        let (rows, count) = query(&db2, r#"FROM driver WHERE _id = "d1" TRAVERSE handles"#).unwrap();
834        assert_eq!(count, 1);
835        assert_eq!(rows[0]["_id"], "t1");
836    }
837}
nedb_engine/nql.rs

nedb_engine/
nql.rs
