reddb_rql/parser/
tree.rs

1//! Parser for TREE commands and CREATE/DROP TREE.
2
3use super::error::ParseError;
4use super::Parser;
5use crate::ast::{
6    CreateTreeQuery, DropTreeQuery, QueryExpr, TreeCommand, TreeNodeSpec, TreePosition,
7};
8use crate::lexer::Token;
9use reddb_types::json::Value as JsonValue;
10use reddb_types::types::Value;
11
12impl<'a> Parser<'a> {
13    pub fn parse_create_tree_body(&mut self) -> Result<QueryExpr, ParseError> {
14        let if_not_exists = self.match_if_not_exists()?;
15        let name = self.expect_ident()?;
16        self.expect(Token::In)?;
17        let collection = self.expect_ident()?;
18        self.expect_tree_ident("ROOT")?;
19        let root = self.parse_tree_node_spec(false)?;
20        let default_max_children = self.parse_tree_required_max_children()?;
21
22        Ok(QueryExpr::CreateTree(CreateTreeQuery {
23            collection,
24            name,
25            root,
26            default_max_children,
27            if_not_exists,
28        }))
29    }
30
31    pub fn parse_drop_tree_body(&mut self) -> Result<QueryExpr, ParseError> {
32        let if_exists = self.match_if_exists()?;
33        let name = self.expect_ident()?;
34        self.expect(Token::In)?;
35        let collection = self.expect_ident()?;
36        Ok(QueryExpr::DropTree(DropTreeQuery {
37            collection,
38            name,
39            if_exists,
40        }))
41    }
42
43    pub fn parse_tree_command(&mut self) -> Result<QueryExpr, ParseError> {
44        self.expect(Token::Tree)?;
45
46        if self.consume(&Token::Insert)? {
47            self.expect(Token::Into)?;
48            let (collection, tree_name) = self.parse_tree_target()?;
49            self.expect_tree_ident("PARENT")?;
50            let parent_id = self.parse_tree_entity_id()?;
51            let node = self.parse_tree_node_spec(true)?;
52            let position = self.parse_tree_position()?;
53            return Ok(QueryExpr::TreeCommand(TreeCommand::Insert {
54                collection,
55                tree_name,
56                parent_id,
57                node,
58                position,
59            }));
60        }
61
62        if self.consume_ident_ci("MOVE")? {
63            let (collection, tree_name) = self.parse_tree_target()?;
64            self.expect(Token::Node)?;
65            let node_id = self.parse_tree_entity_id()?;
66            self.expect(Token::To)?;
67            self.expect_tree_ident("PARENT")?;
68            let parent_id = self.parse_tree_entity_id()?;
69            let position = self.parse_tree_position()?;
70            return Ok(QueryExpr::TreeCommand(TreeCommand::Move {
71                collection,
72                tree_name,
73                node_id,
74                parent_id,
75                position,
76            }));
77        }
78
79        if self.consume(&Token::Delete)? {
80            let (collection, tree_name) = self.parse_tree_target()?;
81            self.expect(Token::Node)?;
82            let node_id = self.parse_tree_entity_id()?;
83            return Ok(QueryExpr::TreeCommand(TreeCommand::Delete {
84                collection,
85                tree_name,
86                node_id,
87            }));
88        }
89
90        if self.consume_ident_ci("VALIDATE")? {
91            let (collection, tree_name) = self.parse_tree_target()?;
92            return Ok(QueryExpr::TreeCommand(TreeCommand::Validate {
93                collection,
94                tree_name,
95            }));
96        }
97
98        if self.consume_ident_ci("REBALANCE")? {
99            let (collection, tree_name) = self.parse_tree_target()?;
100            let dry_run = if self.consume_ident_ci("DRY")? {
101                self.expect_tree_ident("RUN")?;
102                true
103            } else {
104                false
105            };
106            return Ok(QueryExpr::TreeCommand(TreeCommand::Rebalance {
107                collection,
108                tree_name,
109                dry_run,
110            }));
111        }
112
113        Err(ParseError::expected(
114            vec!["INSERT", "MOVE", "DELETE", "VALIDATE", "REBALANCE"],
115            self.peek(),
116            self.position(),
117        ))
118    }
119
120    fn parse_tree_target(&mut self) -> Result<(String, String), ParseError> {
121        let collection = self.expect_ident()?;
122        self.expect(Token::Dot)?;
123        let tree_name = self.expect_ident()?;
124        Ok((collection, tree_name))
125    }
126
127    fn parse_tree_node_spec(
128        &mut self,
129        allow_max_children: bool,
130    ) -> Result<TreeNodeSpec, ParseError> {
131        self.expect_tree_ident("LABEL")?;
132        let label = self.parse_tree_string_like()?;
133        let mut node_type = None;
134        let mut properties = Vec::new();
135        let mut metadata = Vec::new();
136        let mut max_children = None;
137
138        loop {
139            if self.consume_ident_ci("TYPE")? {
140                node_type = Some(self.parse_tree_string_like()?);
141            } else if self.consume(&Token::Properties)? {
142                properties = self.parse_tree_object_literal_entries()?;
143            } else if self.consume(&Token::Metadata)? {
144                metadata = self.parse_tree_object_literal_entries()?;
145            } else if allow_max_children
146                && (self.consume_ident_ci("MAX_CHILDREN")?
147                    || self.consume_ident_ci("MAXCHILDREN")?)
148            {
149                max_children = Some(self.parse_tree_positive_usize()?);
150            } else {
151                break;
152            }
153        }
154
155        Ok(TreeNodeSpec {
156            label,
157            node_type,
158            properties,
159            metadata,
160            max_children,
161        })
162    }
163
164    fn parse_tree_position(&mut self) -> Result<TreePosition, ParseError> {
165        if !(self.consume_ident_ci("POSITION")?) {
166            return Ok(TreePosition::Last);
167        }
168
169        if self.consume(&Token::First)? {
170            return Ok(TreePosition::First);
171        }
172        if self.consume(&Token::Last)? {
173            return Ok(TreePosition::Last);
174        }
175
176        Ok(TreePosition::Index(self.parse_tree_positive_usize()?))
177    }
178
179    fn parse_tree_required_max_children(&mut self) -> Result<usize, ParseError> {
180        if !(self.consume_ident_ci("MAX_CHILDREN")? || self.consume_ident_ci("MAXCHILDREN")?) {
181            return Err(ParseError::expected(
182                vec!["MAX_CHILDREN"],
183                self.peek(),
184                self.position(),
185            ));
186        }
187        self.parse_tree_positive_usize()
188    }
189
190    fn parse_tree_entity_id(&mut self) -> Result<u64, ParseError> {
191        match self.peek().clone() {
192            Token::Integer(value) if value > 0 => {
193                self.advance()?;
194                Ok(value as u64)
195            }
196            Token::String(value) => {
197                self.advance()?;
198                parse_tree_entity_id_text(&value).ok_or_else(|| {
199                    ParseError::new(
200                        // F-05: `value` is caller-controlled string-literal
201                        // bytes. Render via `{:?}` so embedded CR/LF/NUL/
202                        // quotes are escaped before the message reaches the
203                        // downstream JSON / audit / log / gRPC sinks.
204                        format!("invalid tree entity id {value:?}"),
205                        self.position(),
206                    )
207                })
208            }
209            other => Err(ParseError::expected(
210                vec!["entity id"],
211                &other,
212                self.position(),
213            )),
214        }
215    }
216
217    fn parse_tree_positive_usize(&mut self) -> Result<usize, ParseError> {
218        let value = self.parse_integer()?;
219        if value <= 0 {
220            return Err(ParseError::new(
221                "expected a positive integer".to_string(),
222                self.position(),
223            ));
224        }
225        Ok(value as usize)
226    }
227
228    fn parse_tree_string_like(&mut self) -> Result<String, ParseError> {
229        match self.peek().clone() {
230            Token::String(value) => {
231                self.advance()?;
232                Ok(value)
233            }
234            _ => self.expect_ident_or_keyword(),
235        }
236    }
237
238    fn expect_tree_ident(&mut self, expected: &str) -> Result<(), ParseError> {
239        if self.consume_ident_ci(expected)? {
240            return Ok(());
241        }
242        Err(ParseError::expected(
243            vec![expected],
244            self.peek(),
245            self.position(),
246        ))
247    }
248
249    fn parse_tree_object_literal_entries(&mut self) -> Result<Vec<(String, Value)>, ParseError> {
250        let literal = self.parse_literal_value()?;
251        let Value::Json(bytes) = literal else {
252            return Err(ParseError::new(
253                "expected object literal".to_string(),
254                self.position(),
255            ));
256        };
257        let decoded = reddb_types::json::from_slice::<JsonValue>(&bytes).map_err(|err| {
258            ParseError::new(
259                // F-05: serde's parse error string can echo a user fragment.
260                // Render via `{:?}` so embedded control bytes / quotes are
261                // escaped before the message reaches downstream sinks.
262                format!("failed to decode object literal: {:?}", err.to_string()),
263                self.position(),
264            )
265        })?;
266        let JsonValue::Object(object) = decoded else {
267            return Err(ParseError::new(
268                "expected object literal".to_string(),
269                self.position(),
270            ));
271        };
272        object
273            .into_iter()
274            .map(|(key, value)| Ok((key, tree_json_value_to_storage_value(&value)?)))
275            .collect()
276    }
277}
278
279fn parse_tree_entity_id_text(value: &str) -> Option<u64> {
280    value
281        .strip_prefix('e')
282        .unwrap_or(value)
283        .parse::<u64>()
284        .ok()
285        .filter(|value| *value > 0)
286}
287
288fn tree_json_value_to_storage_value(value: &JsonValue) -> Result<Value, ParseError> {
289    Ok(match value {
290        JsonValue::Null => Value::Null,
291        JsonValue::Bool(value) => Value::Boolean(*value),
292        JsonValue::Number(value) => {
293            if value.fract().abs() < f64::EPSILON {
294                Value::Integer(*value as i64)
295            } else {
296                Value::Float(*value)
297            }
298        }
299        JsonValue::String(value) => Value::text(value.clone()),
300        JsonValue::Array(_) | JsonValue::Object(_) => {
301            Value::Json(reddb_types::json::to_vec(value).map_err(|err| {
302                ParseError::new(
303                    // F-05: defensively escape encoder error in case it
304                    // echoes a user fragment.
305                    format!("failed to encode nested JSON value: {:?}", err.to_string()),
306                    crate::lexer::Position::default(),
307                )
308            })?)
309        }
310    })
311}
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316
317    fn parse_query(input: &str) -> Result<QueryExpr, ParseError> {
318        crate::parser::parse(input).map(|query| query.query)
319    }
320
321    fn entry_value<'a>(entries: &'a [(String, Value)], key: &str) -> &'a Value {
322        entries
323            .iter()
324            .find_map(|(entry_key, value)| (entry_key == key).then_some(value))
325            .unwrap_or_else(|| panic!("missing entry {key}"))
326    }
327
328    #[test]
329    fn create_tree_accepts_root_options_and_maxchildren_alias() {
330        let query = parse_query(
331            "CREATE TREE IF NOT EXISTS org IN forest ROOT LABEL 'Company' TYPE root \
332             METADATA {active: true, rank: 3, nested: {tier: 'gold'}} MAXCHILDREN 2",
333        )
334        .unwrap();
335
336        let QueryExpr::CreateTree(tree) = query else {
337            panic!("expected create tree");
338        };
339        assert_eq!(tree.collection, "forest");
340        assert_eq!(tree.name, "org");
341        assert!(tree.if_not_exists);
342        assert_eq!(tree.default_max_children, 2);
343        assert_eq!(tree.root.label, "Company");
344        assert_eq!(tree.root.node_type.as_deref(), Some("root"));
345        assert_eq!(tree.root.max_children, None);
346        assert_eq!(
347            entry_value(&tree.root.metadata, "active"),
348            &Value::Boolean(true)
349        );
350        assert_eq!(entry_value(&tree.root.metadata, "rank"), &Value::Integer(3));
351        assert!(matches!(
352            entry_value(&tree.root.metadata, "nested"),
353            Value::Json(_)
354        ));
355    }
356
357    #[test]
358    fn tree_insert_defaults_to_last_and_accepts_string_entity_ids() {
359        let query = parse_query(
360            "TREE INSERT INTO forest.org PARENT 'e42' LABEL child \
361             PROPERTIES {name: 'Platform'} MAX_CHILDREN 4",
362        )
363        .unwrap();
364
365        let QueryExpr::TreeCommand(TreeCommand::Insert {
366            collection,
367            tree_name,
368            parent_id,
369            node,
370            position,
371        }) = query
372        else {
373            panic!("expected tree insert");
374        };
375        assert_eq!(collection, "forest");
376        assert_eq!(tree_name, "org");
377        assert_eq!(parent_id, 42);
378        assert_eq!(node.label, "child");
379        assert_eq!(node.max_children, Some(4));
380        assert!(matches!(
381            entry_value(&node.properties, "name"),
382            Value::Text(value) if value.as_ref() == "Platform"
383        ));
384        assert_eq!(position, TreePosition::Last);
385    }
386
387    #[test]
388    fn tree_commands_cover_move_delete_validate_rebalance_and_drop() {
389        let query = parse_query("TREE MOVE forest.org NODE 'e9' TO PARENT 1 POSITION 3").unwrap();
390        let QueryExpr::TreeCommand(TreeCommand::Move {
391            collection,
392            tree_name,
393            node_id,
394            parent_id,
395            position,
396        }) = query
397        else {
398            panic!("expected tree move");
399        };
400        assert_eq!(collection, "forest");
401        assert_eq!(tree_name, "org");
402        assert_eq!(node_id, 9);
403        assert_eq!(parent_id, 1);
404        assert_eq!(position, TreePosition::Index(3));
405
406        let query = parse_query("TREE DELETE forest.org NODE 5").unwrap();
407        assert!(matches!(
408            query,
409            QueryExpr::TreeCommand(TreeCommand::Delete {
410                collection,
411                tree_name,
412                node_id,
413            }) if collection == "forest" && tree_name == "org" && node_id == 5
414        ));
415
416        let query = parse_query("TREE VALIDATE forest.org").unwrap();
417        assert!(matches!(
418            query,
419            QueryExpr::TreeCommand(TreeCommand::Validate {
420                collection,
421                tree_name,
422            }) if collection == "forest" && tree_name == "org"
423        ));
424
425        let query = parse_query("TREE REBALANCE forest.org").unwrap();
426        assert!(matches!(
427            query,
428            QueryExpr::TreeCommand(TreeCommand::Rebalance {
429                collection,
430                tree_name,
431                dry_run,
432            }) if collection == "forest" && tree_name == "org" && !dry_run
433        ));
434
435        let query = parse_query("DROP TREE IF EXISTS org IN forest").unwrap();
436        assert!(matches!(
437            query,
438            QueryExpr::DropTree(drop) if drop.name == "org"
439                && drop.collection == "forest"
440                && drop.if_exists
441        ));
442    }
443
444    #[test]
445    fn tree_parser_rejects_malformed_commands() {
446        for sql in [
447            "CREATE TREE org IN forest ROOT LABEL root",
448            "TREE INSERT INTO forest.org PARENT 0 LABEL child",
449            "TREE INSERT INTO forest.org PARENT 1 LABEL child POSITION 0",
450            "TREE INSERT INTO forest.org PARENT 1 LABEL child PROPERTIES 'not-object'",
451            "TREE UNKNOWN forest.org",
452        ] {
453            assert!(parse_query(sql).is_err(), "{sql} should not parse");
454        }
455    }
456}
reddb_rql/parser/tree.rs

reddb_rql/parser/
tree.rs
