1use super::{FloatMode, VALUE_WORK, f32_bits};
27use crate::typetree::{Kind, NodeId, NodeInfo, Shape, Tree};
28
29macro_rules! num {
30 ($big:expr, $t:ty, $b:expr) => {
31 if $big {
32 <$t>::from_be_bytes($b)
33 } else {
34 <$t>::from_le_bytes($b)
35 }
36 };
37}
38
39pub trait Sink {
43 type Obj;
45 fn scalar(&mut self, v: Scalar) -> Option<Self::Obj>;
47 fn str(&mut self, v: &[u8]) -> Option<Self::Obj>;
49 fn bytes(&mut self, v: &[u8]) -> Option<Self::Obj>;
51 fn tuple(&mut self, first: Self::Obj, second: Self::Obj) -> Option<Self::Obj>;
53 fn dict(&mut self, node: NodeId, children: usize) -> Option<Self::Obj>;
55 fn close(&mut self, node: NodeId, dict: Self::Obj) -> Option<Self::Obj> {
58 let _ = node;
59 Some(dict)
60 }
61 fn set(&mut self, dict: &Self::Obj, key: NodeId, value: Self::Obj) -> Option<()>;
63 fn list(&mut self, items: std::vec::Drain<'_, Self::Obj>) -> Option<Self::Obj>;
65 fn run(&mut self, run: Run<'_>) -> Option<Self::Obj>;
67 fn room(&mut self, items: usize) -> bool;
70}
71
72pub trait Elements {
74 fn element(&mut self, v: Scalar) -> Option<()>;
76}
77
78#[derive(Clone, Copy, Debug, PartialEq)]
80pub enum Scalar {
81 Bool(bool),
83 Int(i64),
85 UInt(u64),
87 Float(f64),
89}
90
91#[derive(Clone, Copy, Debug)]
94pub struct Run<'a> {
95 kind: Kind,
96 bytes: &'a [u8],
97 count: usize,
98 big: bool,
99 floats: FloatMode,
100}
101
102impl Run<'_> {
103 #[must_use]
105 pub fn len(&self) -> usize {
106 self.count
107 }
108
109 #[must_use]
111 pub fn is_empty(&self) -> bool {
112 self.count == 0
113 }
114
115 #[inline]
117 pub fn each(&self, f: impl FnMut(Scalar) -> Option<()>) -> Option<()> {
118 struct Each<F>(F);
119 impl<F: FnMut(Scalar) -> Option<()>> Elements for Each<F> {
120 #[inline]
121 fn element(&mut self, v: Scalar) -> Option<()> {
122 (self.0)(v)
123 }
124 }
125 self.each_into(&mut Each(f))
126 }
127
128 #[inline]
132 pub fn each_into<E: Elements>(&self, to: &mut E) -> Option<()> {
133 let mut f = |v| to.element(v);
134 let (big, floats) = (self.big, self.floats);
135 macro_rules! each {
136 ($n:literal, |$b:ident, $big:ident| $conv:expr) => {{
139 let chunks = self.bytes.as_chunks::<$n>().0;
140 if big {
141 for $b in chunks {
142 let ($b, $big) = (*$b, true);
143 let _ = $big;
144 f($conv)?;
145 }
146 } else {
147 for $b in chunks {
148 let ($b, $big) = (*$b, false);
149 let _ = $big;
150 f($conv)?;
151 }
152 }
153 }};
154 }
155 match self.kind {
156 Kind::U8 => each!(1, |b, big| Scalar::Int(i64::from(b[0]))),
157 Kind::Bool => each!(1, |b, big| Scalar::Bool(b[0] != 0)),
158 Kind::S8 => each!(1, |b, big| Scalar::Int(i64::from(i8::from_le_bytes(b)))),
159 Kind::U16 => each!(2, |b, big| Scalar::Int(i64::from(num!(big, u16, b)))),
160 Kind::S16 => each!(2, |b, big| Scalar::Int(i64::from(num!(big, i16, b)))),
161 Kind::U32 => each!(4, |b, big| Scalar::Int(i64::from(num!(big, u32, b)))),
162 Kind::S32 => each!(4, |b, big| Scalar::Int(i64::from(num!(big, i32, b)))),
163 Kind::U64 => each!(8, |b, big| Scalar::UInt(num!(big, u64, b))),
164 Kind::S64 => each!(8, |b, big| Scalar::Int(num!(big, i64, b))),
165 Kind::F32 => each!(4, |b, big| Scalar::Float(f64::from(f32::from_bits(
166 f32_bits(num!(big, u32, b), floats)
167 )))),
168 Kind::F64 => each!(8, |b, big| Scalar::Float(f64::from_bits(num!(big, u64, b)))),
169 _ => return None,
170 }
171 Some(())
172 }
173}
174
175#[must_use]
179pub fn supported(tree: &Tree) -> bool {
180 let mut i = 0_u32;
181 while let Some(info) = tree.info(NodeId(i)) {
182 if info.shape == Shape::RefObject
183 || info.kind == Kind::ManagedReferencesRegistry
184 || info.dup_names
185 {
186 return false;
187 }
188 i += 1;
189 }
190 true
191}
192
193pub struct Emitted<O> {
197 pub value: O,
199 pub bytes_read: usize,
201 pub work: u64,
203}
204
205pub fn emit<S: Sink>(
212 data: &[u8],
213 tree: &Tree,
214 big: bool,
215 floats: FloatMode,
216 max_depth: u32,
217 max_work: u64,
218 sink: &mut S,
219) -> Result<Emitted<S::Obj>, u64> {
220 let mut r = Emit {
221 cur: Cur {
222 bytes: data,
223 pos: 0,
224 big,
225 floats,
226 work: 0,
227 max_work,
228 },
229 tree,
230 max_depth: max_depth as usize,
231 frames: Vec::with_capacity(16),
232 stack: Vec::with_capacity(64),
233 sink,
234 };
235 let Some(value) = r.read(tree.root()) else {
236 return Err(r.cur.work);
237 };
238 Ok(Emitted {
239 value,
240 bytes_read: r.cur.pos,
241 work: r.cur.work,
242 })
243}
244
245enum Frame<'a, O> {
247 Class {
250 node: NodeId,
251 kids: &'a [NodeId],
252 next: usize,
253 dict: O,
254 align: bool,
255 },
256 List {
259 elem: NodeId,
260 left: usize,
261 base: usize,
262 align: bool,
263 },
264 Pairs {
268 a: NodeId,
269 b: NodeId,
270 left: usize,
271 base: usize,
272 first: Option<O>,
273 align: bool,
274 },
275 Pair {
277 a: NodeId,
278 b: NodeId,
279 items: (Option<O>, Option<O>),
280 align: bool,
281 },
282}
283
284enum Entered<O> {
286 Read(O),
287 Opened,
288}
289
290#[derive(Clone, Copy)]
293enum Open {
294 Pair {
295 align: bool,
296 },
297 Array {
298 elem: NodeId,
299 ei: NodeInfo,
300 run: bool,
301 count: usize,
302 align: bool,
303 },
304 Class {
305 align: bool,
306 },
307}
308
309enum Step<O> {
311 Read(NodeId),
313 Done(O),
315}
316
317struct Cur<'a> {
320 bytes: &'a [u8],
321 pos: usize,
323 big: bool,
324 floats: FloatMode,
325 work: u64,
326 max_work: u64,
328}
329
330struct Emit<'a, 's, S: Sink> {
331 cur: Cur<'a>,
332 tree: &'a Tree,
333 max_depth: usize,
334 frames: Vec<Frame<'a, S::Obj>>,
336 stack: Vec<S::Obj>,
338 sink: &'s mut S,
339}
340
341impl Cur<'_> {
342 #[inline]
344 fn bound(&self, n: usize) -> Option<usize> {
345 self.pos
346 .checked_add(n)
347 .filter(|end| *end <= self.bytes.len())
348 }
349
350 #[inline]
351 fn fixed<const N: usize>(&mut self) -> Option<[u8; N]> {
352 let end = self.bound(N)?;
353 let b = <[u8; N]>::try_from(self.bytes.get(self.pos..end)?).ok()?;
354 self.pos = end;
355 Some(b)
356 }
357
358 #[inline]
360 fn take(&mut self, n: usize) -> Option<&[u8]> {
361 let end = self.bound(n)?;
362 let b = self.bytes.get(self.pos..end)?;
363 self.pos = end;
364 Some(b)
365 }
366
367 #[inline]
369 fn align4(&mut self) {
370 self.pos = self.pos.checked_add(3).map_or(usize::MAX & !3, |p| p & !3);
371 }
372
373 #[inline]
375 fn length(&mut self) -> Option<usize> {
376 let n = num!(self.big, i32, self.fixed::<4>()?);
377 usize::try_from(n).ok()
378 }
379
380 #[inline(always)]
381 #[allow(
382 clippy::inline_always,
383 reason = "once per primitive value: outlined, it costs a call per value (callgrind)"
384 )]
385 fn prim(&mut self, kind: Kind) -> Option<Scalar> {
386 let big = self.big;
387 let int = Scalar::Int;
388 Some(match kind {
389 Kind::U8 => int(i64::from(self.fixed::<1>()?[0])),
390 Kind::S8 => int(i64::from(i8::from_le_bytes(self.fixed()?))),
391 Kind::Bool => Scalar::Bool(self.fixed::<1>()?[0] != 0),
392 Kind::U16 => int(i64::from(num!(big, u16, self.fixed()?))),
393 Kind::S16 => int(i64::from(num!(big, i16, self.fixed()?))),
394 Kind::U32 => int(i64::from(num!(big, u32, self.fixed()?))),
395 Kind::S32 => int(i64::from(num!(big, i32, self.fixed()?))),
396 Kind::U64 => Scalar::UInt(num!(big, u64, self.fixed()?)),
397 Kind::S64 => int(num!(big, i64, self.fixed()?)),
398 Kind::F32 => {
399 let bits = f32_bits(num!(big, u32, self.fixed()?), self.floats);
400 Scalar::Float(f64::from(f32::from_bits(bits)))
401 }
402 Kind::F64 => Scalar::Float(f64::from_bits(num!(big, u64, self.fixed()?))),
403 _ => return None,
404 })
405 }
406
407 fn run<S: Sink>(
409 &mut self,
410 sink: &mut S,
411 kind: Kind,
412 width: u32,
413 count: usize,
414 ) -> Option<S::Obj> {
415 let total = count.checked_mul(width as usize)?;
416 let end = self.bound(total)?;
417 let work = self.work.saturating_add(total as u64);
420 if work > self.max_work {
421 return None;
422 }
423 let run = Run {
424 kind,
425 bytes: self.bytes.get(self.pos..end)?,
426 count,
427 big: self.big,
428 floats: self.floats,
429 };
430 self.pos = end;
431 let out = sink.run(run)?;
432 self.work = work;
433 Some(out)
434 }
435
436 #[inline(always)]
440 #[allow(
441 clippy::inline_always,
442 reason = "once per value: inlined into the class loop it saves a call per value (callgrind)"
443 )]
444 fn look<S: Sink>(
445 &mut self,
446 tree: &Tree,
447 me: &NodeInfo,
448 sink: &mut S,
449 ) -> Option<Result<S::Obj, Open>> {
450 self.work = self.work.saturating_add(VALUE_WORK);
451 if self.work > self.max_work {
452 return None;
453 }
454 let mut align = me.align;
456 let out = match me.shape {
457 Shape::Prim => sink.scalar(self.prim(me.kind)?)?,
458 Shape::Str => {
460 let len = self.length()?;
461 let end = self.bound(len)?;
462 let s = self.bytes.get(self.pos..end)?;
463 self.pos = end;
464 self.align4();
465 sink.str(s)?
466 }
467 Shape::Bytes => {
469 let len = self.length()?;
470 sink.bytes(self.take(len)?)?
471 }
472 Shape::Pair => return Some(Err(Open::Pair { align })),
473 Shape::Vector {
474 elem,
475 run,
476 array_align,
477 } => {
478 align |= array_align;
479 let count = self.length()?;
480 let ei = tree.info(elem).copied().unwrap_or(*me);
481 align |= run && ei.align;
483 if run && let Some(width) = ei.kind.prim_size() {
484 self.run(sink, ei.kind, width, count)?
485 } else {
486 return Some(Err(Open::Array {
487 elem,
488 ei,
489 run,
490 count,
491 align,
492 }));
493 }
494 }
495 Shape::Class => return Some(Err(Open::Class { align })),
496 Shape::BadPair | Shape::BadVector | Shape::RefObject => return None,
497 };
498 if align {
499 self.align4();
500 }
501 Some(Ok(out))
502 }
503
504 fn fits(&self, count: usize, min_size: u32) -> bool {
507 let left = self.bytes.len().saturating_sub(self.pos);
508 min_size == 0 || count <= left / min_size as usize
509 }
510}
511
512impl<'a, S: Sink> Emit<'a, '_, S> {
513 fn read(&mut self, root: NodeId) -> Option<S::Obj> {
519 let mut value = match self.enter(root)? {
520 Entered::Read(v) => return Some(v),
521 Entered::Opened => None,
522 };
523 loop {
524 if let Some(v) = value.take() {
525 if self.frames.is_empty() {
526 return Some(v);
527 }
528 self.accept(v)?;
529 }
530 if self.class_children()? {
531 continue;
532 }
533 match self.step()? {
534 Step::Read(n) => {
535 if let Entered::Read(v) = self.enter(n)? {
536 value = Some(v);
537 }
538 }
539 Step::Done(v) => value = Some(v),
540 }
541 }
542 }
543
544 #[inline]
549 fn class_children(&mut self) -> Option<bool> {
550 let depth = self.frames.len();
551 let Self {
552 cur,
553 tree,
554 frames,
555 sink,
556 max_depth,
557 ..
558 } = self;
559 let Some(Frame::Class {
560 kids, next, dict, ..
561 }) = frames.last_mut()
562 else {
563 return Some(false);
564 };
565 let tree: &'a Tree = tree;
566 while let Some(&c) = kids.get(*next) {
567 let me = tree.info(c)?;
568 if me.kind == Kind::ManagedReferencesRegistry || depth >= *max_depth {
569 return None;
570 }
571 match cur.look(tree, me, &mut **sink)? {
572 Ok(v) => {
573 *next += 1;
574 sink.set(dict, me.key, v)?;
575 }
576 Err(open) => {
577 let me = *me;
578 self.open(c, &me, open)?;
579 return Some(true);
580 }
581 }
582 }
583 Some(false)
584 }
585
586 fn enter(&mut self, node: NodeId) -> Option<Entered<S::Obj>> {
589 if self.frames.len() >= self.max_depth {
590 return None;
591 }
592 let me = *self.tree.info(node)?;
593 match self.cur.look(self.tree, &me, &mut *self.sink)? {
594 Ok(v) => Some(Entered::Read(v)),
595 Err(open) => {
596 self.open(node, &me, open)?;
597 Some(Entered::Opened)
598 }
599 }
600 }
601
602 fn open(&mut self, node: NodeId, me: &NodeInfo, open: Open) -> Option<()> {
604 match open {
605 Open::Pair { align } => {
606 let (a, b) = two(self.tree, node);
607 self.frames.push(Frame::Pair {
608 a,
609 b,
610 items: (None, None),
611 align,
612 });
613 }
614 Open::Array {
615 elem,
616 ei,
617 run,
618 count,
619 align,
620 } => self.array(elem, ei, run, count, align)?,
621 Open::Class { align } => {
622 if me.dup_names {
623 return None;
624 }
625 let kids = self.tree.list().children(node);
626 let dict = self.sink.dict(node, kids.len())?;
627 self.frames.push(Frame::Class {
628 node,
629 kids,
630 next: 0,
631 dict,
632 align,
633 });
634 }
635 }
636 Some(())
637 }
638
639 fn array(
642 &mut self,
643 elem: NodeId,
644 ei: NodeInfo,
645 run: bool,
646 count: usize,
647 align: bool,
648 ) -> Option<()> {
649 if (run && ei.shape != Shape::Pair)
650 || !self.cur.fits(count, ei.min_size)
651 || !self.sink.room(count)
652 {
653 return None;
654 }
655 let base = self.stack.len();
656 self.frames.push(if run {
657 let (a, b) = two(self.tree, elem);
658 Frame::Pairs {
659 a,
660 b,
661 left: count,
662 base,
663 first: None,
664 align,
665 }
666 } else {
667 Frame::List {
668 elem,
669 left: count,
670 base,
671 align,
672 }
673 });
674 Some(())
675 }
676
677 fn accept(&mut self, v: S::Obj) -> Option<()> {
679 match self.frames.last_mut()? {
680 Frame::Class {
681 kids, next, dict, ..
682 } => {
683 let c = *kids.get(*next)?;
684 let key = self.tree.info(c)?.key;
685 *next += 1;
686 self.sink.set(dict, key, v)
687 }
688 Frame::List { left, .. } => {
689 *left -= 1;
690 self.stack.push(v);
691 Some(())
692 }
693 Frame::Pairs { left, first, .. } => {
694 if let Some(first) = first.take() {
695 *left -= 1;
696 let pair = self.sink.tuple(first, v)?;
697 self.stack.push(pair);
698 } else {
699 *first = Some(v);
700 }
701 Some(())
702 }
703 Frame::Pair { items, .. } => {
704 if items.0.is_none() {
705 items.0 = Some(v);
706 } else {
707 items.1 = Some(v);
708 }
709 Some(())
710 }
711 }
712 }
713
714 fn step(&mut self) -> Option<Step<S::Obj>> {
717 let read = match self.frames.last_mut()? {
718 Frame::Class { kids, next, .. } => kids.get(*next).copied(),
719 Frame::List { elem, left, .. } => (*left > 0).then_some(*elem),
720 Frame::Pairs {
721 a, b, left, first, ..
722 } => match first {
723 Some(_) => Some(*b),
724 None if *left > 0 => {
725 self.cur.work = self.cur.work.saturating_add(VALUE_WORK);
727 if self.cur.work > self.cur.max_work {
728 return None;
729 }
730 Some(*a)
731 }
732 None => None,
733 },
734 Frame::Pair { a, b, items, .. } => match items {
735 (None, _) => Some(*a),
736 (Some(_), None) => Some(*b),
737 (Some(_), Some(_)) => None,
738 },
739 };
740 if let Some(n) = read {
741 if let Frame::Class { .. } = self.frames.last()? {
742 let kind = self.tree.info(n)?.kind;
743 if kind == Kind::ManagedReferencesRegistry {
744 return None;
745 }
746 }
747 return Some(Step::Read(n));
748 }
749 let (value, align) = match self.frames.pop()? {
750 Frame::Class {
751 node, dict, align, ..
752 } => (self.sink.close(node, dict)?, align),
753 Frame::List { base, align, .. } | Frame::Pairs { base, align, .. } => {
754 (self.sink.list(self.stack.drain(base..))?, align)
755 }
756 Frame::Pair {
757 items: (first, second),
758 align,
759 ..
760 } => (self.sink.tuple(first?, second?)?, align),
761 };
762 if align {
763 self.cur.align4();
764 }
765 Some(Step::Done(value))
766 }
767}
768
769fn two(t: &Tree, node: NodeId) -> (NodeId, NodeId) {
771 match t.list().children(node) {
772 [a, b, ..] => (*a, *b),
773 [a] => (*a, *a),
774 [] => (node, node),
775 }
776}