logicaffeine_kernel/dag/
json.rs

1//! A small, allocation-free JSON reader for one NDJSON record at a time.
2//!
3//! A record is parsed into a flat token tape that is reused across lines; containers record where
4//! they end so a lookup can skip a whole value in O(1). Strings stay borrowed from the line and are
5//! decoded only when a name or literal actually needs their text.
6
7#[derive(Clone, Copy, Debug)]
8pub enum Tok<'a> {
9    Obj { end: u32 },
10    Arr { end: u32 },
11    Key(&'a [u8], bool),
12    Str(&'a [u8], bool),
13    Num(&'a [u8]),
14    True,
15    False,
16    Null,
17}
18
19pub struct Tape<'a> {
20    pub toks: Vec<Tok<'a>>,
21}
22
23#[derive(Debug)]
24pub struct JsonError;
25
26struct P<'a> {
27    b: &'a [u8],
28    i: usize,
29}
30
31impl<'a> P<'a> {
32    #[inline]
33    fn ws(&mut self) {
34        while self.i < self.b.len() && matches!(self.b[self.i], b' ' | b'\t' | b'\r' | b'\n') {
35            self.i += 1;
36        }
37    }
38
39    fn string(&mut self) -> Result<(&'a [u8], bool), JsonError> {
40        // at opening quote
41        self.i += 1;
42        let start = self.i;
43        let mut escaped = false;
44        while self.i < self.b.len() {
45            match self.b[self.i] {
46                b'"' => {
47                    let s = &self.b[start..self.i];
48                    self.i += 1;
49                    return Ok((s, escaped));
50                }
51                b'\\' => {
52                    escaped = true;
53                    self.i += 2;
54                }
55                c if c < 0x20 => return Err(JsonError),
56                _ => self.i += 1,
57            }
58        }
59        Err(JsonError)
60    }
61
62    fn value(&mut self, toks: &mut Vec<Tok<'a>>, depth: u32) -> Result<(), JsonError> {
63        if depth > 64 {
64            return Err(JsonError);
65        }
66        self.ws();
67        let c = *self.b.get(self.i).ok_or(JsonError)?;
68        match c {
69            b'{' => {
70                let at = toks.len();
71                toks.push(Tok::Obj { end: 0 });
72                self.i += 1;
73                self.ws();
74                if self.b.get(self.i) == Some(&b'}') {
75                    self.i += 1;
76                } else {
77                    loop {
78                        self.ws();
79                        if self.b.get(self.i) != Some(&b'"') {
80                            return Err(JsonError);
81                        }
82                        let (k, e) = self.string()?;
83                        toks.push(Tok::Key(k, e));
84                        self.ws();
85                        if self.b.get(self.i) != Some(&b':') {
86                            return Err(JsonError);
87                        }
88                        self.i += 1;
89                        self.value(toks, depth + 1)?;
90                        self.ws();
91                        match self.b.get(self.i) {
92                            Some(b',') => self.i += 1,
93                            Some(b'}') => {
94                                self.i += 1;
95                                break;
96                            }
97                            _ => return Err(JsonError),
98                        }
99                    }
100                }
101                toks[at] = Tok::Obj {
102                    end: toks.len() as u32,
103                };
104            }
105            b'[' => {
106                let at = toks.len();
107                toks.push(Tok::Arr { end: 0 });
108                self.i += 1;
109                self.ws();
110                if self.b.get(self.i) == Some(&b']') {
111                    self.i += 1;
112                } else {
113                    loop {
114                        self.value(toks, depth + 1)?;
115                        self.ws();
116                        match self.b.get(self.i) {
117                            Some(b',') => self.i += 1,
118                            Some(b']') => {
119                                self.i += 1;
120                                break;
121                            }
122                            _ => return Err(JsonError),
123                        }
124                    }
125                }
126                toks[at] = Tok::Arr {
127                    end: toks.len() as u32,
128                };
129            }
130            b'"' => {
131                let (s, e) = self.string()?;
132                toks.push(Tok::Str(s, e));
133            }
134            b't' if self.b[self.i..].starts_with(b"true") => {
135                self.i += 4;
136                toks.push(Tok::True);
137            }
138            b'f' if self.b[self.i..].starts_with(b"false") => {
139                self.i += 5;
140                toks.push(Tok::False);
141            }
142            b'n' if self.b[self.i..].starts_with(b"null") => {
143                self.i += 4;
144                toks.push(Tok::Null);
145            }
146            b'-' | b'0'..=b'9' => {
147                let start = self.i;
148                self.i += 1;
149                while self.i < self.b.len()
150                    && matches!(
151                        self.b[self.i],
152                        b'0'..=b'9' | b'.' | b'e' | b'E' | b'+' | b'-'
153                    )
154                {
155                    self.i += 1;
156                }
157                toks.push(Tok::Num(&self.b[start..self.i]));
158            }
159            _ => return Err(JsonError),
160        }
161        Ok(())
162    }
163}
164
165impl<'a> Tape<'a> {
166    /// Parses one JSON document (the whole of `line`, trailing whitespace allowed).
167    pub fn parse(
168        line: &'a [u8],
169        mut toks: Vec<Tok<'a>>,
170    ) -> Result<Tape<'a>, (JsonError, Vec<Tok<'a>>)> {
171        toks.clear();
172        let mut p = P { b: line, i: 0 };
173        match p.value(&mut toks, 0) {
174            Ok(()) => {
175                p.ws();
176                if p.i != line.len() {
177                    return Err((JsonError, toks));
178                }
179                Ok(Tape { toks })
180            }
181            Err(e) => Err((e, toks)),
182        }
183    }
184
185    #[inline]
186    pub fn skip(&self, i: usize) -> usize {
187        match self.toks[i] {
188            Tok::Obj { end } | Tok::Arr { end } => end as usize,
189            _ => i + 1,
190        }
191    }
192
193    /// The members of the object at `i`, as (key, value index).
194    pub fn members(&self, i: usize) -> impl Iterator<Item = (&'a [u8], usize)> + '_ {
195        let end = match self.toks[i] {
196            Tok::Obj { end } => end as usize,
197            _ => i + 1,
198        };
199        let mut j = i + 1;
200        std::iter::from_fn(move || {
201            if j >= end {
202                return None;
203            }
204            let Tok::Key(k, _) = self.toks[j] else {
205                return None;
206            };
207            let v = j + 1;
208            j = self.skip(v);
209            Some((k, v))
210        })
211    }
212
213    pub fn get(&self, obj: usize, key: &str) -> Option<usize> {
214        self.members(obj)
215            .find(|(k, _)| *k == key.as_bytes())
216            .map(|(_, v)| v)
217    }
218
219    pub fn elems(&self, i: usize) -> impl Iterator<Item = usize> + '_ {
220        let end = match self.toks[i] {
221            Tok::Arr { end } => end as usize,
222            _ => i + 1,
223        };
224        let mut j = i + 1;
225        std::iter::from_fn(move || {
226            if j >= end {
227                return None;
228            }
229            let v = j;
230            j = self.skip(v);
231            Some(v)
232        })
233    }
234
235    /// A non-negative integer that fits `u64`; anything else (sign, fraction, exponent,
236    /// overflow) is `None`.
237    #[inline]
238    pub fn u64(&self, i: usize) -> Option<u64> {
239        let Tok::Num(s) = self.toks[i] else {
240            return None;
241        };
242        if s.is_empty() || s.len() > 20 {
243            return None;
244        }
245        let mut v: u64 = 0;
246        for &b in s {
247            let d = b.wrapping_sub(b'0');
248            if d > 9 {
249                return None;
250            }
251            v = v.checked_mul(10)?.checked_add(d as u64)?;
252        }
253        Some(v)
254    }
255
256    pub fn bool(&self, i: usize) -> Option<bool> {
257        match self.toks[i] {
258            Tok::True => Some(true),
259            Tok::False => Some(false),
260            _ => None,
261        }
262    }
263
264    pub fn str(&self, i: usize) -> Option<std::borrow::Cow<'a, str>> {
265        match self.toks[i] {
266            Tok::Str(s, false) => std::str::from_utf8(s).ok().map(std::borrow::Cow::Borrowed),
267            Tok::Str(s, true) => unescape(s).map(std::borrow::Cow::Owned),
268            _ => None,
269        }
270    }
271}
272
273fn hex4(b: &[u8]) -> Option<u32> {
274    if b.len() < 4 {
275        return None;
276    }
277    u32::from_str_radix(std::str::from_utf8(&b[..4]).ok()?, 16).ok()
278}
279
280fn unescape(s: &[u8]) -> Option<String> {
281    let mut out: Vec<u8> = Vec::with_capacity(s.len());
282    let mut i = 0;
283    while i < s.len() {
284        if s[i] != b'\\' {
285            out.push(s[i]);
286            i += 1;
287            continue;
288        }
289        let c = *s.get(i + 1)?;
290        i += 2;
291        let ch = match c {
292            b'"' => '"',
293            b'\\' => '\\',
294            b'/' => '/',
295            b'b' => '\u{8}',
296            b'f' => '\u{c}',
297            b'n' => '\n',
298            b'r' => '\r',
299            b't' => '\t',
300            b'u' => {
301                let hi = hex4(&s[i..])?;
302                i += 4;
303                if (0xD800..0xDC00).contains(&hi) {
304                    if s.get(i) != Some(&b'\\') || s.get(i + 1) != Some(&b'u') {
305                        return None;
306                    }
307                    let lo = hex4(&s[i + 2..])?;
308                    i += 6;
309                    if !(0xDC00..0xE000).contains(&lo) {
310                        return None;
311                    }
312                    char::from_u32(0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00))?
313                } else {
314                    char::from_u32(hi)?
315                }
316            }
317            _ => return None,
318        };
319        let mut buf = [0u8; 4];
320        out.extend_from_slice(ch.encode_utf8(&mut buf).as_bytes());
321    }
322    String::from_utf8(out).ok()
323}
324
325#[cfg(test)]
326#[path = "../../../logicaffeine_tests/unit/logicaffeine_kernel/dag/json/tests.rs"]
327mod tests;
logicaffeine_kernel/dag/json.rs

logicaffeine_kernel/dag/
json.rs
