substrate_data/forms/text/
parser.rs

1//! The parser: text to a value, with the spans of its parts when asked.
2
3use super::{Doc, LineCol, Span, Spans, SyntaxError};
4use crate::model::value::{Map, Value};
5
6/// `\\u` escapes are hexadecimal.
7const HEX_RADIX: u32 = 16;
8
9/// Deeper than this is an error, not a stack overflow.
10pub const MAX_DEPTH: usize = 256;
11
12/// Parses text.
13///
14/// # Errors
15///
16/// [`SyntaxError`] when the text doesn't parse.
17pub fn parse(text: &str) -> Result<Doc, SyntaxError> {
18    let (value, spans) = run::<true>(text)?;
19    Ok(Doc { value, spans })
20}
21
22/// Parses text, without the positions (faster).
23///
24/// # Errors
25///
26/// [`SyntaxError`] when the text doesn't parse.
27pub fn parse_value(text: &str) -> Result<Value, SyntaxError> {
28    run::<false>(text).map(|(v, _)| v)
29}
30
31fn run<const SPANS: bool>(text: &str) -> Result<(Value, Spans), SyntaxError> {
32    let mut p = Parser::<SPANS> {
33        src: text.as_bytes(),
34        text,
35        i: 0,
36        depth: 0,
37    };
38    if text.starts_with('\u{feff}') {
39        p.i = 3;
40    }
41    p.ws()?;
42    let (value, spans) = p.value()?;
43    p.ws()?;
44    if p.i < p.src.len() {
45        return Err(p.error("unexpected text after the value"));
46    }
47    Ok((value, spans))
48}
49
50/// `SPANS`: whether to record where each value is.
51#[derive(Debug)]
52struct Parser<'a, const SPANS: bool> {
53    src: &'a [u8],
54    text: &'a str,
55    i: usize,
56    depth: usize,
57}
58
59impl<const SPANS: bool> Parser<'_, SPANS> {
60    fn error(&self, message: impl Into<String>) -> SyntaxError {
61        self.error_at(self.i, message)
62    }
63
64    fn error_at(&self, offset: usize, message: impl Into<String>) -> SyntaxError {
65        let mut message = message.into();
66        if offset >= self.src.len() {
67            message.push_str(", found the end of the file");
68        }
69        SyntaxError {
70            message,
71            at: LineCol::of(self.text, offset),
72            offset,
73        }
74    }
75
76    fn peek(&self) -> Option<u8> {
77        self.src.get(self.i).copied()
78    }
79
80    /// Skips whitespace and comments.
81    fn ws(&mut self) -> Result<(), SyntaxError> {
82        loop {
83            let rest = &self.src[self.i..];
84            self.i += rest
85                .iter()
86                .position(|&b| !matches!(b, b' ' | b'\t' | b'\n' | b'\r'))
87                .unwrap_or(rest.len());
88            if self.peek() != Some(b'/') {
89                return Ok(());
90            }
91            match self.src.get(self.i + 1) {
92                Some(b'/') => {
93                    let line = &self.src[self.i..];
94                    self.i += line.iter().position(|&b| b == b'\n').unwrap_or(line.len());
95                }
96                Some(b'*') => {
97                    let start = self.i;
98                    match self.text[self.i + 2..].find("*/") {
99                        Some(end) => self.i += 2 + end + 2,
100                        None => return Err(self.error_at(start, "unclosed `/*` comment")),
101                    }
102                }
103                _ => return Ok(()),
104            }
105        }
106    }
107
108    fn value(&mut self) -> Result<(Value, Spans), SyntaxError> {
109        let start = self.i;
110        let (value, children) = match self.peek() {
111            Some(b'{') => self.nested(Parser::map)?,
112            Some(b'[') => self.nested(Parser::list)?,
113            Some(b'"') => (Value::Str(self.string()?), Vec::new()),
114            Some(b'-' | b'0'..=b'9') => (self.number()?, Vec::new()),
115            Some(b't') if self.src[self.i..].starts_with(b"true") => {
116                self.i += 4;
117                (Value::Bool(true), Vec::new())
118            }
119            Some(b'f') if self.src[self.i..].starts_with(b"false") => {
120                self.i += 5;
121                (Value::Bool(false), Vec::new())
122            }
123            Some(b'n') if self.src[self.i..].starts_with(b"null") => {
124                self.i += 4;
125                (Value::Null, Vec::new())
126            }
127            Some(b'\'') => return Err(self.error("strings use double quotes")),
128            _ => return Err(self.error("expected a value")),
129        };
130        let span = Span::new(start, self.i);
131        Ok((
132            value,
133            Spans {
134                span,
135                key: None,
136                children,
137            },
138        ))
139    }
140
141    fn nested(
142        &mut self,
143        f: impl FnOnce(&mut Self) -> Result<(Value, Vec<Spans>), SyntaxError>,
144    ) -> Result<(Value, Vec<Spans>), SyntaxError> {
145        self.depth += 1;
146        if self.depth > MAX_DEPTH {
147            return Err(self.error(format!("nested deeper than {MAX_DEPTH} levels")));
148        }
149        let r = f(self);
150        self.depth -= 1;
151        r
152    }
153
154    fn list(&mut self) -> Result<(Value, Vec<Spans>), SyntaxError> {
155        self.i += 1;
156        let mut items = Vec::new();
157        let mut spans = Vec::new();
158        loop {
159            self.ws()?;
160            if self.peek() == Some(b']') {
161                self.i += 1;
162                break;
163            }
164            let (v, s) = self.value()?;
165            items.push(v);
166            if SPANS {
167                spans.push(s);
168            }
169            self.ws()?;
170            match self.peek() {
171                Some(b',') => self.i += 1,
172                Some(b']') => {
173                    self.i += 1;
174                    break;
175                }
176                _ => return Err(self.error("expected `,` or `]`")),
177            }
178        }
179        Ok((Value::List(items), spans))
180    }
181
182    fn map(&mut self) -> Result<(Value, Vec<Spans>), SyntaxError> {
183        self.i += 1;
184        let mut map = Map::new();
185        let mut spans = Vec::new();
186        // Duplicate keys: a scan for small objects, a set once they grow.
187        let mut seen: Option<std::collections::HashSet<String>> = None;
188        loop {
189            self.ws()?;
190            if self.peek() == Some(b'}') {
191                self.i += 1;
192                break;
193            }
194            let key_start = self.i;
195            let key = self.key()?;
196            let key_span = Span::new(key_start, self.i);
197            if is_duplicate(&map, &mut seen, &key) {
198                return Err(
199                    self.error_at(key_start, format!("`{key}` is already set in this object"))
200                );
201            }
202            self.ws()?;
203            if self.peek() != Some(b':') {
204                return Err(self.error("expected `:` after the key"));
205            }
206            self.i += 1;
207            self.ws()?;
208            let (v, mut s) = self.value()?;
209            s.key = Some(key_span);
210            map.push_unchecked(key.into(), v);
211            if SPANS {
212                spans.push(s);
213            }
214            self.ws()?;
215            match self.peek() {
216                Some(b',') => self.i += 1,
217                Some(b'}') => {
218                    self.i += 1;
219                    break;
220                }
221                _ => return Err(self.error("expected `,` or `}`")),
222            }
223        }
224        Ok((Value::Map(map), spans))
225    }
226
227    /// An object's key: a string, or a bare name.
228    fn key(&mut self) -> Result<String, SyntaxError> {
229        let start = self.i;
230        match self.peek() {
231            Some(b'"') => self.string(),
232            Some(first) if first.is_ascii_alphabetic() || first == b'_' || first == b'$' => {
233                while self
234                    .peek()
235                    .is_some_and(|c| c.is_ascii_alphanumeric() || c == b'_' || c == b'$')
236                {
237                    self.i += 1;
238                }
239                Ok(self.text[start..self.i].to_string())
240            }
241            _ => Err(self.error("expected a key")),
242        }
243    }
244
245    fn string(&mut self) -> Result<String, SyntaxError> {
246        let open = self.i;
247        self.i += 1;
248        let mut out = String::new();
249        loop {
250            let rest = &self.src[self.i..];
251            let Some(n) = rest
252                .iter()
253                .position(|&b| b == b'"' || b == b'\\' || b < 0x20)
254            else {
255                return Err(self.error_at(open, "unclosed string"));
256            };
257            out.push_str(&self.text[self.i..self.i + n]);
258            self.i += n;
259            match self.src[self.i] {
260                b'"' => {
261                    self.i += 1;
262                    return Ok(out);
263                }
264                b'\\' => self.escape(&mut out)?,
265                b'\n' => return Err(self.error("line break in a string (write `\\n`)")),
266                _ => return Err(self.error("control character in a string")),
267            }
268        }
269    }
270
271    fn escape(&mut self, out: &mut String) -> Result<(), SyntaxError> {
272        let at = self.i;
273        self.i += 1;
274        let c = self.peek().ok_or_else(|| self.error("unclosed string"))?;
275        self.i += 1;
276        match c {
277            b'"' => out.push('"'),
278            b'\\' => out.push('\\'),
279            b'/' => out.push('/'),
280            b'b' => out.push('\u{8}'),
281            b'f' => out.push('\u{c}'),
282            b'n' => out.push('\n'),
283            b'r' => out.push('\r'),
284            b't' => out.push('\t'),
285            b'u' => {
286                let hi = self.hex4(at)?;
287                let ch = if (0xD800..0xDC00).contains(&hi) {
288                    if !self.src[self.i..].starts_with(b"\\u") {
289                        return Err(self.error_at(at, "unpaired surrogate in `\\u` escape"));
290                    }
291                    self.i += 2;
292                    let lo = self.hex4(at)?;
293                    if !(0xDC00..0xE000).contains(&lo) {
294                        return Err(self.error_at(at, "unpaired surrogate in `\\u` escape"));
295                    }
296                    char::from_u32(0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00))
297                } else {
298                    char::from_u32(hi)
299                };
300                out.push(
301                    ch.ok_or_else(|| self.error_at(at, "unpaired surrogate in `\\u` escape"))?,
302                );
303            }
304            _ => {
305                return Err(self.error_at(
306                    at,
307                    "unknown escape (`\\n`, `\\t`, `\\\"`, `\\\\`, `\\uXXXX`, ...)",
308                ));
309            }
310        }
311        Ok(())
312    }
313
314    fn hex4(&mut self, at: usize) -> Result<u32, SyntaxError> {
315        let digits = self
316            .text
317            .get(self.i..self.i + 4)
318            .filter(|d| d.bytes().all(|b| b.is_ascii_hexdigit()));
319        let d = digits.ok_or_else(|| self.error_at(at, "`\\u` needs four hex digits"))?;
320        let code = u32::from_str_radix(d, HEX_RADIX)
321            .map_err(|_| self.error_at(at, "`\\u` needs four hex digits"))?;
322        self.i += 4;
323        Ok(code)
324    }
325
326    fn number(&mut self) -> Result<Value, SyntaxError> {
327        let start = self.i;
328        if self.peek() == Some(b'-') {
329            self.i += 1;
330        }
331        let digits = |p: &mut Self| {
332            let s = p.i;
333            while p.peek().is_some_and(|c| c.is_ascii_digit()) {
334                p.i += 1;
335            }
336            p.i - s
337        };
338        let int_start = self.i;
339        if digits(self) == 0 {
340            return Err(self.error("expected digits"));
341        }
342        if self.src[int_start] == b'0' && self.i - int_start > 1 {
343            return Err(self.error_at(int_start, "numbers don't start with 0"));
344        }
345        let mut float = false;
346        if self.peek() == Some(b'.') {
347            self.i += 1;
348            float = true;
349            if digits(self) == 0 {
350                return Err(self.error("expected digits after `.`"));
351            }
352        }
353        if matches!(self.peek(), Some(b'e' | b'E')) {
354            self.i += 1;
355            float = true;
356            if matches!(self.peek(), Some(b'+' | b'-')) {
357                self.i += 1;
358            }
359            if digits(self) == 0 {
360                return Err(self.error("expected digits in the exponent"));
361            }
362        }
363        let s = &self.text[start..self.i];
364        if !float && let Ok(n) = s.parse::<i64>() {
365            return Ok(Value::Int(n));
366        }
367        Ok(Value::Float(
368            s.parse::<f64>()
369                .map_err(|_| self.error_at(start, "invalid number"))?,
370        ))
371    }
372}
373
374/// Whether `key` is already in `map`: a scan for small objects, a set
375/// (built in `seen` the first time) once they grow.
376fn is_duplicate(
377    map: &Map,
378    seen: &mut Option<std::collections::HashSet<String>>,
379    key: &str,
380) -> bool {
381    match seen {
382        Some(set) => !set.insert(key.to_string()),
383        None if map.len() < 16 => map.get(key).is_some(),
384        None => {
385            let mut set: std::collections::HashSet<String> =
386                map.keys().map(str::to_string).collect();
387            let dup = !set.insert(key.to_string());
388            *seen = Some(set);
389            dup
390        }
391    }
392}
substrate_data/forms/text/parser.rs

substrate_data/forms/text/
parser.rs
