[librsvg] (#393): Don't drop nodes recursively to avoid stack overflow

[Federico Mena Quintero <federico src gnome org>]

commit fef340ac418ca84ddd9443665cf788817f291a99
Author: Federico Mena Quintero <federico gnome org>
Date:   Fri Dec 14 17:00:08 2018 -0600

    (#393): Don't drop nodes recursively to avoid stack overflow
    
    We borrow a dropping technique from Kuchiki, to avoid deep recursion
    when there are thousands of sibling nodes.
    
    https://gitlab.gnome.org/GNOME/librsvg/issues/393

 rsvg_internals/src/tree_utils/mod.rs | 69 ++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)
---
diff --git a/rsvg_internals/src/tree_utils/mod.rs b/rsvg_internals/src/tree_utils/mod.rs
index 52627476..bada9087 100644
--- a/rsvg_internals/src/tree_utils/mod.rs
+++ b/rsvg_internals/src/tree_utils/mod.rs
@@ -79,6 +79,75 @@ impl<T> Node<T> {
     }
 }
 
+/// Prevent stack overflow when recursively dropping nodes
+///
+/// Dropping nodes is recursive, since a node owns strong references
+/// to its next sibling and its first child.  When there is an SVG
+/// with a flat hierarchy of a few hundred thousand elements,
+/// recursively dropping these siblings can cause stack overflow.
+///
+/// Here, we convert recursion to an explicit heap-allocated stack of
+/// nodes that need to be dropped.  This technique is borrowed from
+/// [kuchiki]'s tree implementation.
+///
+/// [kuchiki]: https://github.com/kuchiki-rs/kuchiki/blob/master/src/tree.rs
+impl<T> Drop for Node<T> {
+    fn drop(&mut self) {
+        let mut stack = Vec::new();
+
+        if let Some(rc) = take_if_unique_strong(&self.first_child) {
+            non_recursive_drop_unique_rc(rc, &mut stack);
+        }
+
+        if let Some(rc) = take_if_unique_strong(&self.next_sib) {
+            non_recursive_drop_unique_rc(rc, &mut stack);
+        }
+
+        fn non_recursive_drop_unique_rc<T>(mut rc: NodeRef<T>, stack: &mut Vec<NodeRef<T>>) {
+            loop {
+                if let Some(child) = take_if_unique_strong(&rc.first_child) {
+                    stack.push(rc);
+                    rc = child;
+                    continue;
+                }
+
+                if let Some(sibling) = take_if_unique_strong(&rc.next_sib) {
+                    rc = sibling;
+                    continue;
+                }
+
+                if let Some(parent) = stack.pop() {
+                    rc = parent;
+                    continue;
+                }
+
+                return;
+            }
+        }
+    }
+}
+
+/// Return `Some` if the `NodeRef` is the only strong reference count
+///
+/// Note that this leaves the tree in a partially inconsistent state, since
+/// the weak references to the node referenced by `r` will now point to
+/// an unlinked node.
+fn take_if_unique_strong<T>(r: &RefCell<Option<NodeRef<T>>>) -> Option<NodeRef<T>> {
+    let mut r = r.borrow_mut();
+
+    let has_single_ref = match *r {
+        None => false,
+        Some(ref rc) if Rc::strong_count(rc) > 1 => false,
+        Some(_) => true,
+    };
+
+    if has_single_ref {
+        r.take()
+    } else {
+        None
+    }
+}
+
 // An iterator over the Node's children
 pub struct Children<T> {
     next: Option<NodeRef<T>>,