jsonld_core/object/
dismantle.rs

1//! Dropping nested JSON-LD objects without recursion.
2//!
3//! The derived drop of an expanded document recurses once per nesting level,
4//! and the Expansion algorithm, which runs on sufficient native stack, builds
5//! documents of any depth. [`Node`] and [`List`] are the two types that own
6//! JSON-LD objects, and every nesting level passes through one of them, so
7//! they drop through [`dismantle`]: every descendant node or list is moved
8//! onto a heap worklist and stripped there, so no drop ever sees a nested
9//! node or list.
10use super::{IndexedNode, List, Node, Object};
11use crate::IndexedObject;
12use std::mem;
13
14/// A descendant waiting to be dropped by [`dismantle`].
15pub(crate) enum Pending<T, B> {
16    /// An object bound to a property, in a graph or in a list.
17    Object(IndexedObject<T, B>),
18    /// An included node or a reverse property node.
19    Node(IndexedNode<T, B>),
20}
21
22/// Drops every descendant of `pending` without recursing.
23pub(crate) fn dismantle<T, B>(pending: &mut Vec<Pending<T, B>>) {
24    while let Some(descendant) = pending.pop() {
25        match descendant {
26            Pending::Object(mut object) => match object.inner_mut() {
27                Object::Node(node) => node.release_children(pending),
28                Object::List(list) => release_list(list, pending),
29                Object::Value(_) => {}
30            },
31            Pending::Node(mut node) => node.inner_mut().release_children(pending),
32        }
33    }
34}
35
36/// Moves the objects of `list` onto `pending`, keeping only those that own
37/// JSON-LD objects themselves.
38pub(crate) fn release_list<T, B>(list: &mut List<T, B>, pending: &mut Vec<Pending<T, B>>) {
39    pending.extend(list.take_entries().into_iter().filter(owns_objects).map(Pending::Object));
40}
41
42/// Whether dropping `object` could recurse: a node or a non-empty list.
43/// A value object holds no JSON-LD object, and a JSON literal inside one
44/// drops flat on its own.
45fn owns_objects<T, B>(object: &IndexedObject<T, B>) -> bool {
46    match object.inner() {
47        Object::Node(_) => true,
48        Object::List(list) => !list.is_empty(),
49        Object::Value(_) => false,
50    }
51}
52
53impl<T, B> Node<T, B> {
54    /// Moves every node and list object directly under this node onto
55    /// `pending`, leaving it without descendants. Value objects are dropped
56    /// in place.
57    pub(crate) fn release_children(&mut self, pending: &mut Vec<Pending<T, B>>) {
58        if let Some(graph) = self.graph.take() {
59            pending.extend(graph.into_iter().filter(owns_objects).map(Pending::Object));
60        }
61        if let Some(included) = self.included.take() {
62            pending.extend(included.into_iter().map(Pending::Node));
63        }
64        if !self.properties.is_empty() {
65            pending.extend(
66                mem::take(&mut self.properties)
67                    .into_iter()
68                    .flat_map(|(_, objects)| objects)
69                    .filter(owns_objects)
70                    .map(Pending::Object),
71            );
72        }
73        if let Some(reverse) = self.reverse_properties.take() {
74            pending.extend(reverse.into_iter().flat_map(|(_, nodes)| nodes).map(Pending::Node));
75        }
76    }
77}
78
79impl<T, B> Drop for Node<T, B> {
80    /// Drops the node's descendants iteratively: each one is stripped of its
81    /// own descendants before it is dropped, so no drop recurses and the
82    /// native stack stays flat whatever the nesting depth. A node whose
83    /// properties are all value objects allocates nothing.
84    fn drop(&mut self) {
85        let mut pending = Vec::new();
86        self.release_children(&mut pending);
87        dismantle(&mut pending);
88    }
89}
90
91impl<T, B> Drop for List<T, B> {
92    /// Drops the list's objects iteratively, as [`Node`] drops its own.
93    fn drop(&mut self) {
94        let mut pending = Vec::new();
95        release_list(self, &mut pending);
96        dismantle(&mut pending);
97    }
98}
jsonld_core/object/dismantle.rs

jsonld_core/object/
dismantle.rs
