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::Integer(value) => Value::Integer(*value),
293        JsonValue::Number(value) => {
294            if value.fract().abs() < f64::EPSILON {
295                Value::Integer(*value as i64)
296            } else {
297                Value::Float(*value)
298            }
299        }
300        JsonValue::Decimal(value) => Value::DecimalText(value.clone()),
301        JsonValue::String(value) => Value::text(value.clone()),
302        JsonValue::Array(_) | JsonValue::Object(_) => {
303            Value::Json(reddb_types::json::to_vec(value).map_err(|err| {
304                ParseError::new(
305                    // F-05: defensively escape encoder error in case it
306                    // echoes a user fragment.
307                    format!("failed to encode nested JSON value: {:?}", err.to_string()),
308                    crate::lexer::Position::default(),
309                )
310            })?)
311        }
312    })
313}
314
315#[cfg(test)]
316mod tests {
317    use super::*;
318
319    fn parse_query(input: &str) -> Result<QueryExpr, ParseError> {
320        crate::parser::parse(input).map(|query| query.query)
321    }
322
323    fn entry_value<'a>(entries: &'a [(String, Value)], key: &str) -> &'a Value {
324        entries
325            .iter()
326            .find_map(|(entry_key, value)| (entry_key == key).then_some(value))
327            .unwrap_or_else(|| panic!("missing entry {key}"))
328    }
329
330    #[test]
331    fn create_tree_accepts_root_options_and_maxchildren_alias() {
332        let query = parse_query(
333            "CREATE TREE IF NOT EXISTS org IN forest ROOT LABEL 'Company' TYPE root \
334             METADATA {active: true, rank: 3, nested: {tier: 'gold'}} MAXCHILDREN 2",
335        )
336        .unwrap();
337
338        let QueryExpr::CreateTree(tree) = query else {
339            panic!("expected create tree");
340        };
341        assert_eq!(tree.collection, "forest");
342        assert_eq!(tree.name, "org");
343        assert!(tree.if_not_exists);
344        assert_eq!(tree.default_max_children, 2);
345        assert_eq!(tree.root.label, "Company");
346        assert_eq!(tree.root.node_type.as_deref(), Some("root"));
347        assert_eq!(tree.root.max_children, None);
348        assert_eq!(
349            entry_value(&tree.root.metadata, "active"),
350            &Value::Boolean(true)
351        );
352        assert_eq!(entry_value(&tree.root.metadata, "rank"), &Value::Integer(3));
353        assert!(matches!(
354            entry_value(&tree.root.metadata, "nested"),
355            Value::Json(_)
356        ));
357    }
358
359    #[test]
360    fn tree_insert_defaults_to_last_and_accepts_string_entity_ids() {
361        let query = parse_query(
362            "TREE INSERT INTO forest.org PARENT 'e42' LABEL child \
363             PROPERTIES {name: 'Platform'} MAX_CHILDREN 4",
364        )
365        .unwrap();
366
367        let QueryExpr::TreeCommand(TreeCommand::Insert {
368            collection,
369            tree_name,
370            parent_id,
371            node,
372            position,
373        }) = query
374        else {
375            panic!("expected tree insert");
376        };
377        assert_eq!(collection, "forest");
378        assert_eq!(tree_name, "org");
379        assert_eq!(parent_id, 42);
380        assert_eq!(node.label, "child");
381        assert_eq!(node.max_children, Some(4));
382        assert!(matches!(
383            entry_value(&node.properties, "name"),
384            Value::Text(value) if value.as_ref() == "Platform"
385        ));
386        assert_eq!(position, TreePosition::Last);
387    }
388
389    #[test]
390    fn tree_commands_cover_move_delete_validate_rebalance_and_drop() {
391        let query = parse_query("TREE MOVE forest.org NODE 'e9' TO PARENT 1 POSITION 3").unwrap();
392        let QueryExpr::TreeCommand(TreeCommand::Move {
393            collection,
394            tree_name,
395            node_id,
396            parent_id,
397            position,
398        }) = query
399        else {
400            panic!("expected tree move");
401        };
402        assert_eq!(collection, "forest");
403        assert_eq!(tree_name, "org");
404        assert_eq!(node_id, 9);
405        assert_eq!(parent_id, 1);
406        assert_eq!(position, TreePosition::Index(3));
407
408        let query = parse_query("TREE DELETE forest.org NODE 5").unwrap();
409        assert!(matches!(
410            query,
411            QueryExpr::TreeCommand(TreeCommand::Delete {
412                collection,
413                tree_name,
414                node_id,
415            }) if collection == "forest" && tree_name == "org" && node_id == 5
416        ));
417
418        let query = parse_query("TREE VALIDATE forest.org").unwrap();
419        assert!(matches!(
420            query,
421            QueryExpr::TreeCommand(TreeCommand::Validate {
422                collection,
423                tree_name,
424            }) if collection == "forest" && tree_name == "org"
425        ));
426
427        let query = parse_query("TREE REBALANCE forest.org").unwrap();
428        assert!(matches!(
429            query,
430            QueryExpr::TreeCommand(TreeCommand::Rebalance {
431                collection,
432                tree_name,
433                dry_run,
434            }) if collection == "forest" && tree_name == "org" && !dry_run
435        ));
436
437        let query = parse_query("DROP TREE IF EXISTS org IN forest").unwrap();
438        assert!(matches!(
439            query,
440            QueryExpr::DropTree(drop) if drop.name == "org"
441                && drop.collection == "forest"
442                && drop.if_exists
443        ));
444    }
445
446    #[test]
447    fn tree_parser_rejects_malformed_commands() {
448        for sql in [
449            "CREATE TREE org IN forest ROOT LABEL root",
450            "TREE INSERT INTO forest.org PARENT 0 LABEL child",
451            "TREE INSERT INTO forest.org PARENT 1 LABEL child POSITION 0",
452            "TREE INSERT INTO forest.org PARENT 1 LABEL child PROPERTIES 'not-object'",
453            "TREE UNKNOWN forest.org",
454        ] {
455            assert!(parse_query(sql).is_err(), "{sql} should not parse");
456        }
457    }
458}
reddb_rql/parser/tree.rs

reddb_rql/parser/
tree.rs
