1use self::Event::*;
2use crate::de::{Deserialize, Map, Seq, Visitor};
3use crate::error::{Error, Result};
4use crate::ptr::NonuniqueBox;
5use alloc::vec::Vec;
6use core::char;
7use core::ptr::NonNull;
8use core::str;
9
10pub fn from_str<T>(j: &str) -> Result<T>
31where
32 T: Deserialize,
33{
34 let mut out = None;
35 from_str_impl(j, T::begin(&mut out))?;
36 out.ok_or(Error)
37}
38
39struct Deserializer<'a, 'b> {
40 input: &'a [u8],
41 pos: usize,
42 buffer: Vec<u8>,
43 stack: Vec<(NonNull<dyn Visitor>, Layer<'b>)>,
44}
45
46enum Layer<'a> {
47 Seq(NonuniqueBox<dyn Seq + 'a>),
48 Map(NonuniqueBox<dyn Map + 'a>),
49}
50
51impl<'a, 'b> Drop for Deserializer<'a, 'b> {
52 fn drop(&mut self) {
53 while !self.stack.is_empty() {
55 self.stack.pop();
56 }
57 }
58}
59
60fn from_str_impl(j: &str, visitor: &mut dyn Visitor) -> Result<()> {
61 let visitor = NonNull::from(visitor);
62 let mut visitor = unsafe { extend_lifetime!(visitor as NonNull<dyn Visitor>) };
63 let mut de = Deserializer {
64 input: j.as_bytes(),
65 pos: 0,
66 buffer: Vec::new(),
67 stack: Vec::new(),
68 };
69
70 'outer: loop {
71 let visitor_mut = unsafe { &mut *visitor.as_ptr() };
72 let layer = match de.event()? {
73 Null => {
74 visitor_mut.null()?;
75 None
76 }
77 Bool(b) => {
78 visitor_mut.boolean(b)?;
79 None
80 }
81 Negative(n) => {
82 visitor_mut.negative(n)?;
83 None
84 }
85 Nonnegative(n) => {
86 visitor_mut.nonnegative(n)?;
87 None
88 }
89 Float(n) => {
90 visitor_mut.float(n)?;
91 None
92 }
93 Str(s) => {
94 visitor_mut.string(s)?;
95 None
96 }
97 SeqStart => {
98 let seq = visitor_mut.seq()?;
99 Some(Layer::Seq(NonuniqueBox::from(seq)))
100 }
101 MapStart => {
102 let map = visitor_mut.map()?;
103 Some(Layer::Map(NonuniqueBox::from(map)))
104 }
105 };
106
107 let mut accept_comma;
108 let mut layer = match layer {
109 Some(layer) => {
110 accept_comma = false;
111 layer
112 }
113 None => match de.stack.pop() {
114 Some(frame) => {
115 accept_comma = true;
116 visitor = frame.0;
117 frame.1
118 }
119 None => break 'outer,
120 },
121 };
122
123 loop {
124 match de.parse_whitespace().unwrap_or(b'\0') {
125 b',' if accept_comma => {
126 de.bump();
127 break;
128 }
129 close @ (b']' | b'}') => {
130 de.bump();
131 match &mut layer {
132 Layer::Seq(seq) if close == b']' => seq.finish()?,
133 Layer::Map(map) if close == b'}' => map.finish()?,
134 _ => return Err(Error),
135 }
136 let Some(frame) = de.stack.pop() else {
137 break 'outer;
138 };
139 accept_comma = true;
140 visitor = frame.0;
141 layer = frame.1;
142 }
143 _ => {
144 if accept_comma {
145 return Err(Error);
146 } else {
147 break;
148 }
149 }
150 }
151 }
152
153 let outer = visitor;
154 match layer {
155 Layer::Seq(mut seq) => {
156 let element = seq.element()?;
157 let next = NonNull::from(element);
158 visitor = unsafe { extend_lifetime!(next as NonNull<dyn Visitor>) };
159 de.stack.push((outer, Layer::Seq(seq)));
160 }
161 Layer::Map(mut map) => {
162 match de.parse_whitespace() {
163 Some(b'"') => de.bump(),
164 _ => return Err(Error),
165 }
166 let key = de.parse_str()?;
167 let entry = map.key(key)?;
168 let next = NonNull::from(entry);
169 visitor = unsafe { extend_lifetime!(next as NonNull<dyn Visitor>) };
170 match de.parse_whitespace() {
171 Some(b':') => de.bump(),
172 _ => return Err(Error),
173 }
174 de.stack.push((outer, Layer::Map(map)));
175 }
176 }
177 }
178
179 match de.parse_whitespace() {
180 Some(_) => Err(Error),
181 None => Ok(()),
182 }
183}
184
185enum Event<'a> {
186 Null,
187 Bool(bool),
188 Str(&'a str),
189 Negative(i64),
190 Nonnegative(u64),
191 Float(f64),
192 SeqStart,
193 MapStart,
194}
195
196macro_rules! overflow {
197 ($a:ident * 10 + $b:ident, $c:expr) => {
198 match $c {
199 c => $a >= c / 10 && ($a > c / 10 || $b > c % 10),
200 }
201 };
202}
203
204impl<'a, 'b> Deserializer<'a, 'b> {
205 fn next(&mut self) -> Option<u8> {
206 if self.pos < self.input.len() {
207 let ch = self.input[self.pos];
208 self.pos += 1;
209 Some(ch)
210 } else {
211 None
212 }
213 }
214
215 fn next_or_nul(&mut self) -> u8 {
216 self.next().unwrap_or(b'\0')
217 }
218
219 fn peek(&mut self) -> Option<u8> {
220 if self.pos < self.input.len() {
221 Some(self.input[self.pos])
222 } else {
223 None
224 }
225 }
226
227 fn peek_or_nul(&mut self) -> u8 {
228 self.peek().unwrap_or(b'\0')
229 }
230
231 fn bump(&mut self) {
232 self.pos += 1;
233 }
234
235 fn parse_str(&mut self) -> Result<&str> {
236 fn result(bytes: &[u8]) -> &str {
237 unsafe { str::from_utf8_unchecked(bytes) }
241 }
242
243 let mut start = self.pos;
245 self.buffer.clear();
246
247 loop {
248 while self.pos < self.input.len() && !ESCAPE[usize::from(self.input[self.pos])] {
249 self.pos += 1;
250 }
251 if self.pos == self.input.len() {
252 return Err(Error);
253 }
254 match self.input[self.pos] {
255 b'"' => {
256 if self.buffer.is_empty() {
257 let borrowed = &self.input[start..self.pos];
260 self.pos += 1;
261 return Ok(result(borrowed));
262 } else {
263 self.buffer.extend_from_slice(&self.input[start..self.pos]);
264 self.pos += 1;
265 return Ok(result(&self.buffer));
266 }
267 }
268 b'\\' => {
269 self.buffer.extend_from_slice(&self.input[start..self.pos]);
270 self.pos += 1;
271 self.parse_escape()?;
272 start = self.pos;
273 }
274 _ => {
275 return Err(Error);
276 }
277 }
278 }
279 }
280
281 fn next_or_eof(&mut self) -> Result<u8> {
282 self.next().ok_or(Error)
283 }
284
285 fn parse_escape(&mut self) -> Result<()> {
288 let ch = self.next_or_eof()?;
289
290 match ch {
291 b'"' => self.buffer.push(b'"'),
292 b'\\' => self.buffer.push(b'\\'),
293 b'/' => self.buffer.push(b'/'),
294 b'b' => self.buffer.push(b'\x08'),
295 b'f' => self.buffer.push(b'\x0c'),
296 b'n' => self.buffer.push(b'\n'),
297 b'r' => self.buffer.push(b'\r'),
298 b't' => self.buffer.push(b'\t'),
299 b'u' => {
300 let c = match self.decode_hex_escape()? {
301 0xDC00..=0xDFFF => {
302 return Err(Error);
303 }
304
305 n1 @ 0xD800..=0xDBFF => {
308 if self.next_or_eof()? != b'\\' {
309 return Err(Error);
310 }
311 if self.next_or_eof()? != b'u' {
312 return Err(Error);
313 }
314
315 let n2 = self.decode_hex_escape()?;
316
317 if n2 < 0xDC00 || n2 > 0xDFFF {
318 return Err(Error);
319 }
320
321 let n =
322 ((u32::from(n1 - 0xD800) << 10) | u32::from(n2 - 0xDC00)) + 0x1_0000;
323
324 match char::from_u32(n) {
325 Some(c) => c,
326 None => {
327 return Err(Error);
328 }
329 }
330 }
331
332 n => match char::from_u32(u32::from(n)) {
333 Some(c) => c,
334 None => {
335 return Err(Error);
336 }
337 },
338 };
339
340 self.buffer
341 .extend_from_slice(c.encode_utf8(&mut [0_u8; 4]).as_bytes());
342 }
343 _ => {
344 return Err(Error);
345 }
346 }
347
348 Ok(())
349 }
350
351 fn decode_hex_escape(&mut self) -> Result<u16> {
352 let mut n = 0;
353 for _ in 0..4 {
354 n = match self.next_or_eof()? {
355 c @ b'0'..=b'9' => n * 16_u16 + u16::from(c - b'0'),
356 b'a' | b'A' => n * 16_u16 + 10_u16,
357 b'b' | b'B' => n * 16_u16 + 11_u16,
358 b'c' | b'C' => n * 16_u16 + 12_u16,
359 b'd' | b'D' => n * 16_u16 + 13_u16,
360 b'e' | b'E' => n * 16_u16 + 14_u16,
361 b'f' | b'F' => n * 16_u16 + 15_u16,
362 _ => {
363 return Err(Error);
364 }
365 };
366 }
367 Ok(n)
368 }
369
370 fn parse_whitespace(&mut self) -> Option<u8> {
371 loop {
372 match self.peek() {
373 Some(b' ' | b'\n' | b'\t' | b'\r') => {
374 self.bump();
375 }
376 other => {
377 return other;
378 }
379 }
380 }
381 }
382
383 fn parse_ident(&mut self, ident: &[u8]) -> Result<()> {
384 for expected in ident {
385 match self.next() {
386 None => {
387 return Err(Error);
388 }
389 Some(next) => {
390 if next != *expected {
391 return Err(Error);
392 }
393 }
394 }
395 }
396 Ok(())
397 }
398
399 fn parse_integer(&mut self, nonnegative: bool, first_digit: u8) -> Result<Event> {
400 match first_digit {
401 b'0' => {
402 match self.peek_or_nul() {
404 b'0'..=b'9' => Err(Error),
405 _ => self.parse_number(nonnegative, 0),
406 }
407 }
408 c @ b'1'..=b'9' => {
409 let mut res = u64::from(c - b'0');
410
411 loop {
412 match self.peek_or_nul() {
413 c @ b'0'..=b'9' => {
414 self.bump();
415 let digit = u64::from(c - b'0');
416
417 if overflow!(res * 10 + digit, u64::MAX) {
421 return self
422 .parse_long_integer(
423 nonnegative,
424 res,
425 1, )
427 .map(Float);
428 }
429
430 res = res * 10 + digit;
431 }
432 _ => {
433 return self.parse_number(nonnegative, res);
434 }
435 }
436 }
437 }
438 _ => Err(Error),
439 }
440 }
441
442 fn parse_long_integer(
443 &mut self,
444 nonnegative: bool,
445 significand: u64,
446 mut exponent: i32,
447 ) -> Result<f64> {
448 loop {
449 match self.peek_or_nul() {
450 b'0'..=b'9' => {
451 self.bump();
452 exponent += 1;
455 }
456 b'.' => {
457 return self.parse_decimal(nonnegative, significand, exponent);
458 }
459 b'e' | b'E' => {
460 return self.parse_exponent(nonnegative, significand, exponent);
461 }
462 _ => {
463 return f64_from_parts(nonnegative, significand, exponent);
464 }
465 }
466 }
467 }
468
469 fn parse_number(&mut self, nonnegative: bool, significand: u64) -> Result<Event> {
470 match self.peek_or_nul() {
471 b'.' => self.parse_decimal(nonnegative, significand, 0).map(Float),
472 b'e' | b'E' => self.parse_exponent(nonnegative, significand, 0).map(Float),
473 _ => {
474 Ok(if nonnegative {
475 Nonnegative(significand)
476 } else {
477 let neg = (significand as i64).wrapping_neg();
478
479 if neg > 0 {
481 Float(-(significand as f64))
482 } else {
483 Negative(neg)
484 }
485 })
486 }
487 }
488 }
489
490 fn parse_decimal(
491 &mut self,
492 nonnegative: bool,
493 mut significand: u64,
494 mut exponent: i32,
495 ) -> Result<f64> {
496 self.bump();
497
498 let mut at_least_one_digit = false;
499 while let c @ b'0'..=b'9' = self.peek_or_nul() {
500 self.bump();
501 let digit = u64::from(c - b'0');
502 at_least_one_digit = true;
503
504 if overflow!(significand * 10 + digit, u64::MAX) {
505 while let b'0'..=b'9' = self.peek_or_nul() {
508 self.bump();
509 }
510 break;
511 }
512
513 significand = significand * 10 + digit;
514 exponent -= 1;
515 }
516
517 if !at_least_one_digit {
518 return Err(Error);
519 }
520
521 match self.peek_or_nul() {
522 b'e' | b'E' => self.parse_exponent(nonnegative, significand, exponent),
523 _ => f64_from_parts(nonnegative, significand, exponent),
524 }
525 }
526
527 fn parse_exponent(
528 &mut self,
529 nonnegative: bool,
530 significand: u64,
531 starting_exp: i32,
532 ) -> Result<f64> {
533 self.bump();
534
535 let positive_exp = match self.peek_or_nul() {
536 b'+' => {
537 self.bump();
538 true
539 }
540 b'-' => {
541 self.bump();
542 false
543 }
544 _ => true,
545 };
546
547 let mut exp = match self.next_or_nul() {
549 c @ b'0'..=b'9' => i32::from(c - b'0'),
550 _ => {
551 return Err(Error);
552 }
553 };
554
555 while let c @ b'0'..=b'9' = self.peek_or_nul() {
556 self.bump();
557 let digit = i32::from(c - b'0');
558
559 if overflow!(exp * 10 + digit, i32::MAX) {
560 return self.parse_exponent_overflow(nonnegative, significand, positive_exp);
561 }
562
563 exp = exp * 10 + digit;
564 }
565
566 let final_exp = if positive_exp {
567 starting_exp.saturating_add(exp)
568 } else {
569 starting_exp.saturating_sub(exp)
570 };
571
572 f64_from_parts(nonnegative, significand, final_exp)
573 }
574
575 #[cold]
578 #[inline(never)]
579 fn parse_exponent_overflow(
580 &mut self,
581 nonnegative: bool,
582 significand: u64,
583 positive_exp: bool,
584 ) -> Result<f64> {
585 if significand != 0 && positive_exp {
587 return Err(Error);
588 }
589
590 while let b'0'..=b'9' = self.peek_or_nul() {
591 self.bump();
592 }
593 Ok(if nonnegative { 0.0 } else { -0.0 })
594 }
595
596 fn event(&mut self) -> Result<Event> {
597 let Some(peek) = self.parse_whitespace() else {
598 return Err(Error);
599 };
600 self.bump();
601 match peek {
602 b'"' => self.parse_str().map(Str),
603 digit @ b'0'..=b'9' => self.parse_integer(true, digit),
604 b'-' => {
605 let first_digit = self.next_or_nul();
606 self.parse_integer(false, first_digit)
607 }
608 b'{' => Ok(MapStart),
609 b'[' => Ok(SeqStart),
610 b'n' => {
611 self.parse_ident(b"ull")?;
612 Ok(Null)
613 }
614 b't' => {
615 self.parse_ident(b"rue")?;
616 Ok(Bool(true))
617 }
618 b'f' => {
619 self.parse_ident(b"alse")?;
620 Ok(Bool(false))
621 }
622 _ => Err(Error),
623 }
624 }
625}
626
627fn f64_from_parts(nonnegative: bool, significand: u64, mut exponent: i32) -> Result<f64> {
628 let mut f = significand as f64;
629 loop {
630 match POW10.get(exponent.unsigned_abs() as usize) {
631 Some(&pow) => {
632 if exponent >= 0 {
633 f *= pow;
634 if f.is_infinite() {
635 return Err(Error);
636 }
637 } else {
638 f /= pow;
639 }
640 break;
641 }
642 None => {
643 if f == 0.0 {
644 break;
645 }
646 if exponent >= 0 {
647 return Err(Error);
648 }
649 f /= 1e308;
650 exponent += 308;
651 }
652 }
653 }
654 Ok(if nonnegative { f } else { -f })
655}
656
657#[allow(clippy::excessive_precision)]
659static POW10: [f64; 309] = [
660 1e000, 1e001, 1e002, 1e003, 1e004, 1e005, 1e006, 1e007, 1e008, 1e009, 1e010, 1e011, 1e012, 1e013, 1e014, 1e015, 1e016, 1e017, 1e018, 1e019, 1e020, 1e021, 1e022, 1e023, 1e024, 1e025, 1e026, 1e027, 1e028, 1e029, 1e030, 1e031, 1e032, 1e033, 1e034, 1e035, 1e036, 1e037, 1e038, 1e039, 1e040, 1e041, 1e042, 1e043, 1e044, 1e045, 1e046, 1e047, 1e048, 1e049, 1e050, 1e051, 1e052, 1e053, 1e054, 1e055, 1e056, 1e057, 1e058, 1e059, 1e060, 1e061, 1e062, 1e063, 1e064, 1e065, 1e066, 1e067, 1e068, 1e069, 1e070, 1e071, 1e072, 1e073, 1e074, 1e075, 1e076, 1e077, 1e078, 1e079, 1e080, 1e081, 1e082, 1e083, 1e084, 1e085, 1e086, 1e087, 1e088, 1e089, 1e090, 1e091, 1e092, 1e093, 1e094, 1e095, 1e096, 1e097, 1e098, 1e099, 1e100, 1e101, 1e102, 1e103, 1e104, 1e105, 1e106, 1e107, 1e108, 1e109, 1e110, 1e111, 1e112, 1e113, 1e114, 1e115, 1e116, 1e117, 1e118, 1e119, 1e120, 1e121, 1e122, 1e123, 1e124, 1e125, 1e126, 1e127, 1e128, 1e129, 1e130, 1e131, 1e132, 1e133, 1e134, 1e135, 1e136, 1e137, 1e138, 1e139, 1e140, 1e141, 1e142, 1e143, 1e144, 1e145, 1e146, 1e147, 1e148, 1e149, 1e150, 1e151, 1e152, 1e153, 1e154, 1e155, 1e156, 1e157, 1e158, 1e159, 1e160, 1e161, 1e162, 1e163, 1e164, 1e165, 1e166, 1e167, 1e168, 1e169, 1e170, 1e171, 1e172, 1e173, 1e174, 1e175, 1e176, 1e177, 1e178, 1e179, 1e180, 1e181, 1e182, 1e183, 1e184, 1e185, 1e186, 1e187, 1e188, 1e189, 1e190, 1e191, 1e192, 1e193, 1e194, 1e195, 1e196, 1e197, 1e198, 1e199, 1e200, 1e201, 1e202, 1e203, 1e204, 1e205, 1e206, 1e207, 1e208, 1e209, 1e210, 1e211, 1e212, 1e213, 1e214, 1e215, 1e216, 1e217, 1e218, 1e219, 1e220, 1e221, 1e222, 1e223, 1e224, 1e225, 1e226, 1e227, 1e228, 1e229, 1e230, 1e231, 1e232, 1e233, 1e234, 1e235, 1e236, 1e237, 1e238, 1e239, 1e240, 1e241, 1e242, 1e243, 1e244, 1e245, 1e246, 1e247, 1e248, 1e249, 1e250, 1e251, 1e252, 1e253, 1e254, 1e255, 1e256, 1e257, 1e258, 1e259, 1e260, 1e261, 1e262, 1e263, 1e264, 1e265, 1e266, 1e267, 1e268, 1e269, 1e270, 1e271, 1e272, 1e273, 1e274, 1e275, 1e276, 1e277, 1e278, 1e279, 1e280, 1e281, 1e282, 1e283, 1e284, 1e285, 1e286, 1e287, 1e288, 1e289, 1e290, 1e291, 1e292, 1e293, 1e294, 1e295, 1e296, 1e297, 1e298, 1e299, 1e300, 1e301, 1e302, 1e303, 1e304, 1e305, 1e306, 1e307, 1e308,
691];
692
693const CT: bool = true; const QU: bool = true; const BS: bool = true; const O: bool = false; #[rustfmt::skip]
701static ESCAPE: [bool; 256] = [
702 CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, O, O, QU, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, BS, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, ];