blockworx/schema/kdl/
imp.rs

1//! Lexer + recursive-descent parser backing [`super::parse`].
2//!
3//! A single byte cursor over the source. Structural characters (identifiers,
4//! numbers, punctuation) are ASCII so they are scanned by byte; string and
5//! comment *contents* are advanced a whole UTF-8 char at a time so byte offsets
6//! stay valid. Newlines and `;` are node separators; spaces, tabs, `//` and
7//! `/* … */` comments are trivia. Block comments are NOT nested (a simple scan to
8//! the first `*/`).
9
10use super::{Entry, Node, Prop, Span, SyntaxError, Value};
11
12pub fn parse(src: &str) -> Result<Vec<Node>, SyntaxError> {
13    let mut p = Parser {
14        src,
15        bytes: src.as_bytes(),
16        pos: 0,
17    };
18    let nodes = p.parse_nodes(Nesting::TopLevel)?;
19    Ok(nodes)
20}
21
22/// Where `parse_nodes` is reading: a `}` closes a block body but is a stray
23/// token at the top level.
24#[derive(Clone, Copy, PartialEq, Eq)]
25enum Nesting {
26    TopLevel,
27    InsideBlock,
28}
29
30struct Parser<'a> {
31    src: &'a str,
32    bytes: &'a [u8],
33    pos: usize,
34}
35
36fn is_ident_start(c: u8) -> bool {
37    c.is_ascii_alphabetic() || c == b'_'
38}
39fn is_ident_continue(c: u8) -> bool {
40    c.is_ascii_alphanumeric() || c == b'_' || c == b'-'
41}
42
43fn err(message: impl Into<String>, span: Span) -> SyntaxError {
44    SyntaxError {
45        message: message.into(),
46        span,
47    }
48}
49
50impl Parser<'_> {
51    fn peek(&self) -> Option<u8> {
52        self.bytes.get(self.pos).copied()
53    }
54    fn peek2(&self) -> Option<u8> {
55        self.bytes.get(self.pos + 1).copied()
56    }
57    fn byte_at(&self, i: usize) -> Option<u8> {
58        self.bytes.get(i).copied()
59    }
60    /// Advance one whole UTF-8 char, returning it.
61    fn bump_char(&mut self) -> Option<char> {
62        let c = self.src[self.pos..].chars().next()?;
63        self.pos += c.len_utf8();
64        Some(c)
65    }
66
67    // ── Trivia ──────────────────────────────────────────────────────────────
68
69    /// Skip spaces, tabs, and comments — but NOT newlines or `;` (separators).
70    fn skip_ws(&mut self) -> Result<(), SyntaxError> {
71        loop {
72            match self.peek() {
73                Some(b' ' | b'\t') => self.pos += 1,
74                Some(b'/') if self.peek2() == Some(b'/') => {
75                    self.pos += 2;
76                    while !matches!(self.peek(), None | Some(b'\n')) {
77                        self.bump_char();
78                    }
79                }
80                Some(b'/') if self.peek2() == Some(b'*') => {
81                    let start = self.pos;
82                    self.pos += 2;
83                    loop {
84                        match self.peek() {
85                            None => return Err(err("unterminated block comment", start..self.pos)),
86                            Some(b'*') if self.peek2() == Some(b'/') => {
87                                self.pos += 2;
88                                break;
89                            }
90                            _ => {
91                                self.bump_char();
92                            }
93                        }
94                    }
95                }
96                _ => return Ok(()),
97            }
98        }
99    }
100
101    /// Skip trivia *and* node separators (newlines, `;`).
102    fn skip_trivia(&mut self) -> Result<(), SyntaxError> {
103        loop {
104            self.skip_ws()?;
105            match self.peek() {
106                Some(b'\n' | b'\r' | b';') => self.pos += 1,
107                _ => return Ok(()),
108            }
109        }
110    }
111
112    // ── Nodes ───────────────────────────────────────────────────────────────
113
114    fn parse_nodes(&mut self, nesting: Nesting) -> Result<Vec<Node>, SyntaxError> {
115        let mut nodes = Vec::new();
116        loop {
117            self.skip_trivia()?;
118            match self.peek() {
119                None => return Ok(nodes),
120                Some(b'}') if nesting == Nesting::InsideBlock => return Ok(nodes),
121                Some(b'}') => return Err(err("unexpected `}`", self.pos..self.pos + 1)),
122                _ => {}
123            }
124            nodes.push(self.parse_node()?);
125        }
126    }
127
128    fn parse_node(&mut self) -> Result<Node, SyntaxError> {
129        let start = self.pos;
130        let (name, name_span) = self.parse_identifier("a node name")?;
131        let mut args = Vec::new();
132        let mut props = Vec::new();
133        loop {
134            self.skip_ws()?;
135            match self.peek() {
136                None | Some(b'\n' | b'\r' | b';' | b'}' | b'{') => break,
137                _ => self.parse_entry(&mut args, &mut props)?,
138            }
139        }
140        let mut children = Vec::new();
141        if self.peek() == Some(b'{') {
142            self.pos += 1;
143            children = self.parse_nodes(Nesting::InsideBlock)?;
144            self.skip_trivia()?;
145            if self.peek() != Some(b'}') {
146                return Err(err("unclosed `{` (expected `}`)", start..self.pos));
147            }
148            self.pos += 1;
149        }
150        Ok(Node {
151            name,
152            name_span,
153            args,
154            props,
155            children,
156            span: start..self.pos,
157        })
158    }
159
160    /// One entry after the node name: a `key=value` property or a bare value.
161    fn parse_entry(
162        &mut self,
163        args: &mut Vec<Entry>,
164        props: &mut Vec<Prop>,
165    ) -> Result<(), SyntaxError> {
166        let is_raw = self.peek() == Some(b'r') && matches!(self.peek2(), Some(b'"' | b'#'));
167        if !is_raw && matches!(self.peek(), Some(c) if is_ident_start(c)) {
168            let (ident, key_span) = self.parse_identifier("an identifier")?;
169            if self.peek() == Some(b'=') {
170                self.pos += 1;
171                let value = self.parse_value()?;
172                props.push(Prop {
173                    key: ident,
174                    key_span,
175                    value,
176                });
177            } else {
178                match ident.as_str() {
179                    "true" => args.push(Entry {
180                        value: Value::Bool(true),
181                        span: key_span,
182                    }),
183                    "false" => args.push(Entry {
184                        value: Value::Bool(false),
185                        span: key_span,
186                    }),
187                    _ => {
188                        return Err(err(
189                            format!(
190                                "`{ident}` is not a value — quote it as \"{ident}\", or add `=` to make it a property"
191                            ),
192                            key_span,
193                        ));
194                    }
195                }
196            }
197        } else {
198            let value = self.parse_value()?;
199            args.push(value);
200        }
201        Ok(())
202    }
203
204    fn parse_identifier(&mut self, what: &str) -> Result<(String, Span), SyntaxError> {
205        let start = self.pos;
206        if !matches!(self.peek(), Some(c) if is_ident_start(c)) {
207            return Err(err(
208                format!("expected {what}"),
209                start..(start + 1).min(self.bytes.len()),
210            ));
211        }
212        self.pos += 1;
213        while matches!(self.peek(), Some(c) if is_ident_continue(c)) {
214            self.pos += 1;
215        }
216        let span = start..self.pos;
217        Ok((self.src[span.clone()].to_string(), span))
218    }
219
220    // ── Values ──────────────────────────────────────────────────────────────
221
222    fn parse_value(&mut self) -> Result<Entry, SyntaxError> {
223        match self.peek() {
224            Some(b'r') if matches!(self.peek2(), Some(b'"' | b'#')) => self.parse_raw_string(),
225            Some(b'"') => self.parse_quoted_string(),
226            Some(c) if c == b'-' || c == b'+' || c.is_ascii_digit() => self.parse_number(),
227            Some(b'#') => self.parse_hash_keyword(),
228            Some(c) if is_ident_start(c) => {
229                let (ident, span) = self.parse_identifier("a value")?;
230                match ident.as_str() {
231                    "true" => Ok(Entry {
232                        value: Value::Bool(true),
233                        span,
234                    }),
235                    "false" => Ok(Entry {
236                        value: Value::Bool(false),
237                        span,
238                    }),
239                    _ => Err(err(
240                        format!("`{ident}` is not a value — quote it as \"{ident}\""),
241                        span,
242                    )),
243                }
244            }
245            _ => Err(err(
246                "expected a value",
247                self.pos..(self.pos + 1).min(self.bytes.len()),
248            )),
249        }
250    }
251
252    fn parse_hash_keyword(&mut self) -> Result<Entry, SyntaxError> {
253        let start = self.pos;
254        self.pos += 1; // #
255        let (kw, span) = self.parse_identifier("a keyword after `#`")?;
256        let full = start..span.end;
257        match kw.as_str() {
258            "true" => Ok(Entry {
259                value: Value::Bool(true),
260                span: full,
261            }),
262            "false" => Ok(Entry {
263                value: Value::Bool(false),
264                span: full,
265            }),
266            _ => Err(err(format!("unknown keyword `#{kw}`"), full)),
267        }
268    }
269
270    fn parse_number(&mut self) -> Result<Entry, SyntaxError> {
271        let start = self.pos;
272        if matches!(self.peek(), Some(b'-' | b'+')) {
273            self.pos += 1;
274        }
275        let digits_start = self.pos;
276        while matches!(self.peek(), Some(c) if c.is_ascii_digit() || c == b'_') {
277            self.pos += 1;
278        }
279        if self.pos == digits_start {
280            return Err(err("expected digits in a number", start..self.pos));
281        }
282        let mut is_float = false;
283        if self.peek() == Some(b'.') && matches!(self.peek2(), Some(c) if c.is_ascii_digit()) {
284            is_float = true;
285            self.pos += 1;
286            while matches!(self.peek(), Some(c) if c.is_ascii_digit() || c == b'_') {
287                self.pos += 1;
288            }
289        }
290        if matches!(self.peek(), Some(b'e' | b'E')) {
291            is_float = true;
292            self.pos += 1;
293            if matches!(self.peek(), Some(b'-' | b'+')) {
294                self.pos += 1;
295            }
296            while matches!(self.peek(), Some(c) if c.is_ascii_digit()) {
297                self.pos += 1;
298            }
299        }
300        let span = start..self.pos;
301        let text: String = self.src[span.clone()]
302            .chars()
303            .filter(|&c| c != '_')
304            .collect();
305        let value = if is_float {
306            Value::Float(
307                text.parse()
308                    .map_err(|_| err(format!("invalid number `{text}`"), span.clone()))?,
309            )
310        } else {
311            Value::Int(
312                text.parse()
313                    .map_err(|_| err(format!("invalid integer `{text}`"), span.clone()))?,
314            )
315        };
316        Ok(Entry { value, span })
317    }
318
319    fn parse_quoted_string(&mut self) -> Result<Entry, SyntaxError> {
320        let start = self.pos;
321        self.pos += 1; // opening "
322        let mut s = String::new();
323        loop {
324            let ch_start = self.pos;
325            match self.bump_char() {
326                None => return Err(err("unterminated string", start..self.pos)),
327                Some('"') => break,
328                Some('\\') => match self.bump_char() {
329                    Some('n') => s.push('\n'),
330                    Some('t') => s.push('\t'),
331                    Some('r') => s.push('\r'),
332                    Some('"') => s.push('"'),
333                    Some('\\') => s.push('\\'),
334                    Some('/') => s.push('/'),
335                    Some('b') => s.push('\u{08}'),
336                    Some('f') => s.push('\u{0C}'),
337                    Some('u') => s.push(self.parse_unicode_escape(ch_start)?),
338                    // KDL v2 whitespace escape: `\` folds away all whitespace
339                    // that follows it (including the newline), so long prose
340                    // can wrap without embedding the line break.
341                    Some(c) if c.is_whitespace() => {
342                        while self.src[self.pos..]
343                            .chars()
344                            .next()
345                            .is_some_and(char::is_whitespace)
346                        {
347                            self.bump_char();
348                        }
349                    }
350                    other => {
351                        return Err(err(
352                            format!("invalid escape `\\{}`", other.unwrap_or(' ')),
353                            ch_start..self.pos,
354                        ));
355                    }
356                },
357                Some(c) => s.push(c),
358            }
359        }
360        Ok(Entry {
361            value: Value::String(s),
362            span: start..self.pos,
363        })
364    }
365
366    fn parse_unicode_escape(&mut self, esc_start: usize) -> Result<char, SyntaxError> {
367        if self.bump_char() != Some('{') {
368            return Err(err("expected `{` after `\\u`", esc_start..self.pos));
369        }
370        let hex_start = self.pos;
371        while matches!(self.peek(), Some(c) if c.is_ascii_hexdigit()) {
372            self.pos += 1;
373        }
374        let hex = &self.src[hex_start..self.pos];
375        if self.bump_char() != Some('}') {
376            return Err(err("expected `}` to close `\\u{…}`", esc_start..self.pos));
377        }
378        if hex.is_empty() || hex.len() > 6 {
379            return Err(err("`\\u{…}` needs 1–6 hex digits", esc_start..self.pos));
380        }
381        let Ok(cp) = u32::from_str_radix(hex, 16) else {
382            return Err(err("`\\u{…}` needs 1–6 hex digits", esc_start..self.pos));
383        };
384        char::from_u32(cp)
385            .ok_or_else(|| err(format!("invalid code point U+{hex}"), esc_start..self.pos))
386    }
387
388    fn parse_raw_string(&mut self) -> Result<Entry, SyntaxError> {
389        let start = self.pos;
390        self.pos += 1; // r
391        let mut hashes = 0;
392        while self.peek() == Some(b'#') {
393            self.pos += 1;
394            hashes += 1;
395        }
396        if self.peek() != Some(b'"') {
397            return Err(err(
398                "expected `\"` after `r` in a raw string",
399                start..self.pos,
400            ));
401        }
402        self.pos += 1; // opening "
403        let content_start = self.pos;
404        loop {
405            match self.peek() {
406                None => return Err(err("unterminated raw string", start..self.pos)),
407                Some(b'"') => {
408                    let closes = (0..hashes).all(|i| self.byte_at(self.pos + 1 + i) == Some(b'#'));
409                    if closes {
410                        let content = self.src[content_start..self.pos].to_string();
411                        self.pos += 1 + hashes;
412                        return Ok(Entry {
413                            value: Value::String(content),
414                            span: start..self.pos,
415                        });
416                    }
417                    self.pos += 1;
418                }
419                Some(_) => {
420                    self.bump_char();
421                }
422            }
423        }
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use super::super::{Value, parse};
430
431    fn s(v: &Value) -> &str {
432        match v {
433            Value::String(s) => s,
434            _ => panic!("not a string: {v:?}"),
435        }
436    }
437
438    #[test]
439    fn simple_node_args_props() {
440        let nodes = parse(r#"block "b1" x=0 y=-30 w=40 h=30 role=2"#).unwrap();
441        assert_eq!(nodes.len(), 1);
442        let n = &nodes[0];
443        assert_eq!(n.name, "block");
444        assert_eq!(s(&n.args[0].value), "b1");
445        assert_eq!(n.prop("x").unwrap().value.value, Value::Int(0));
446        assert_eq!(n.prop("y").unwrap().value.value, Value::Int(-30));
447        assert_eq!(n.prop("role").unwrap().value.value, Value::Int(2));
448        // name span covers `block`
449        assert_eq!(&"block \"b1\""[n.name_span.clone()], "block");
450    }
451
452    #[test]
453    fn separators_and_nesting() {
454        let src = "a; b\nc {\n  d 1; e 2\n}\n";
455        let nodes = parse(src).unwrap();
456        assert_eq!(
457            nodes.iter().map(|n| n.name.as_str()).collect::<Vec<_>>(),
458            ["a", "b", "c"]
459        );
460        let c = &nodes[2];
461        assert_eq!(c.children.len(), 2);
462        assert_eq!(c.children[0].name, "d");
463        assert_eq!(c.children[1].args[0].value, Value::Int(2));
464    }
465
466    #[test]
467    fn string_escapes() {
468        let n = &parse(r#"x "a\nb\t\"c\u{1F600}""#).unwrap()[0];
469        assert_eq!(s(&n.args[0].value.clone()), "a\nb\t\"c\u{1F600}");
470    }
471
472    #[test]
473    fn whitespace_escape_folds_the_line_break_away() {
474        let n = &parse("x \"one \\\n     two\"").unwrap()[0];
475        assert_eq!(s(&n.args[0].value), "one two");
476    }
477
478    #[test]
479    fn raw_strings() {
480        let n = &parse("x r#\"<svg a=\"1\">\nline</svg>\"#").unwrap()[0];
481        assert_eq!(s(&n.args[0].value), "<svg a=\"1\">\nline</svg>");
482        let n2 = &parse("x r##\"has \"# inside\"##").unwrap()[0];
483        assert_eq!(s(&n2.args[0].value), "has \"# inside");
484        let n3 = &parse(r#"x r"plain""#).unwrap()[0];
485        assert_eq!(s(&n3.args[0].value), "plain");
486    }
487
488    #[test]
489    fn numbers_and_bools() {
490        let n = &parse("x -16 42 -45.0 82.3 true false").unwrap()[0];
491        assert_eq!(n.args[0].value, Value::Int(-16));
492        assert_eq!(n.args[1].value, Value::Int(42));
493        assert_eq!(n.args[2].value, Value::Float(-45.0));
494        assert_eq!(n.args[3].value, Value::Float(82.3));
495        assert_eq!(n.args[4].value, Value::Bool(true));
496        assert_eq!(n.args[5].value, Value::Bool(false));
497        assert_eq!(
498            parse("x fliplr=true").unwrap()[0]
499                .prop("fliplr")
500                .unwrap()
501                .value
502                .value,
503            Value::Bool(true)
504        );
505    }
506
507    #[test]
508    fn comments() {
509        let src = "// lead\na 1 // trail\n/* block\ncomment */ b 2\n";
510        let nodes = parse(src).unwrap();
511        assert_eq!(
512            nodes.iter().map(|n| n.name.as_str()).collect::<Vec<_>>(),
513            ["a", "b"]
514        );
515        assert_eq!(nodes[1].args[0].value, Value::Int(2));
516    }
517
518    #[test]
519    fn error_unterminated_string() {
520        let e = parse(r#"x "oops"#).unwrap_err();
521        assert!(e.message.contains("unterminated string"), "{}", e.message);
522        assert_eq!(e.span.start, 2); // opening quote
523    }
524
525    #[test]
526    fn error_bare_ident_value() {
527        let e = parse("x foo").unwrap_err();
528        assert!(e.message.contains("not a value"), "{}", e.message);
529        assert_eq!(&"x foo"[e.span.clone()], "foo");
530    }
531
532    #[test]
533    fn error_stray_brace() {
534        let e = parse("a\n}\n").unwrap_err();
535        assert!(e.message.contains("unexpected `}`"), "{}", e.message);
536        assert_eq!(e.span.start, 2);
537    }
538
539    #[test]
540    fn real_document() {
541        let src = r##"top "b1"
542
543block "b1" x=0 y=-30 w=40 h=30 role=2 {
544    title "Adder"
545    pin "p1" "clk" loc="w1" x=-11 y=28 w=4 h=2 fliplr=true
546    route "b2:p1" "b3:p1" name="n" {
547        wp 12 21
548        label 766
549    }
550    image x=64 y=38 size=82.3 {
551        svg r#"<svg viewBox="0 0 10 10"/>"#
552    }
553    children "b2" "b3"
554}
555"##;
556        let nodes = parse(src).unwrap();
557        assert_eq!(nodes.len(), 2);
558        assert_eq!(nodes[0].name, "top");
559        let block = &nodes[1];
560        assert_eq!(block.name, "block");
561        assert_eq!(s(&block.args[0].value), "b1");
562        assert_eq!(block.props.len(), 5);
563        assert_eq!(block.prop("y").unwrap().value.value, Value::Int(-30));
564
565        let route = block.child("route").unwrap();
566        assert_eq!(s(&route.args[0].value), "b2:p1");
567        assert_eq!(s(&route.args[1].value), "b3:p1");
568        assert_eq!(s(&route.prop("name").unwrap().value.value), "n");
569        assert_eq!(route.child("wp").unwrap().args[1].value, Value::Int(21));
570        assert_eq!(route.child("label").unwrap().args[0].value, Value::Int(766));
571
572        let sym = block.child("image").unwrap();
573        assert_eq!(
574            s(&sym.child("svg").unwrap().args[0].value),
575            r#"<svg viewBox="0 0 10 10"/>"#
576        );
577
578        let pin = block.child("pin").unwrap();
579        assert_eq!(pin.prop("fliplr").unwrap().value.value, Value::Bool(true));
580
581        let children = block.child("children").unwrap();
582        assert_eq!(children.args.len(), 2);
583        assert_eq!(s(&children.args[1].value), "b3");
584    }
585}
blockworx/schema/kdl/imp.rs

blockworx/schema/kdl/
imp.rs
