[librsvg] (#341): Don't infinite-loop with cyclic pattern references

[Federico Mena Quintero <federico src gnome org>]

commit 011dca9a1bee125a7765d8be9f09806169369c05
Author: Federico Mena Quintero <federico gnome org>
Date:   Tue Sep 18 19:18:08 2018 -0500

    (#341): Don't infinite-loop with cyclic pattern references
    
    In each loop iteration in resolve_pattern() we drop the AcquiredNode,
    and so we can't use the implicit stack of acquired nodes to test for
    cycles.
    
    This commit introduces a NodeStack helper, which code can use to catch
    reference cycles explicitly.
    
    We also have new test program for files that cause infinite loops.
    
    https://gitlab.gnome.org/GNOME/librsvg/issues/341

 rsvg_internals/src/drawing_ctx.rs                  | 26 +++++++-
 rsvg_internals/src/pattern.rs                      | 17 ++++--
 tests/Makefile.am                                  |  8 ++-
 .../infinite-loop/341-recursive-pattern.svg        |  5 ++
 tests/infinite-loop.c                              | 70 ++++++++++++++++++++++
 5 files changed, 120 insertions(+), 6 deletions(-)
---
diff --git a/rsvg_internals/src/drawing_ctx.rs b/rsvg_internals/src/drawing_ctx.rs
index 076c047c..c34b2490 100644
--- a/rsvg_internals/src/drawing_ctx.rs
+++ b/rsvg_internals/src/drawing_ctx.rs
@@ -290,7 +290,9 @@ impl<'a> DrawingCtx<'a> {
         if let Some(node) = self.defs.borrow_mut().lookup(url) {
             if !self.acquired_nodes_contains(node) {
                 self.acquired_nodes.borrow_mut().push(node.clone());
-                return Some(AcquiredNode(self.acquired_nodes.clone(), node.clone()));
+                let acq = AcquiredNode(self.acquired_nodes.clone(), node.clone());
+                println!("acquired {}: node={:?}", url, node.as_ref() as *const _);
+                return Some(acq);
             }
         }
 
@@ -1101,6 +1103,7 @@ pub struct AcquiredNode(Rc<RefCell<Vec<RsvgNode>>>, RsvgNode);
 
 impl Drop for AcquiredNode {
     fn drop(&mut self) {
+        println!("dropping node={:?}", self.1.as_ref() as *const _);
         let mut v = self.0.borrow_mut();
         assert!(Rc::ptr_eq(v.last().unwrap(), &self.1));
         v.pop();
@@ -1113,6 +1116,27 @@ impl AcquiredNode {
     }
 }
 
+/// Keeps a stack of nodes and can check if a certain node is contained in the stack
+///
+/// Sometimes parts of the code cannot plainly use the implicit stack of acquired
+/// nodes as maintained by DrawingCtx::get_acquired_node(), and they must keep their
+/// own stack of nodes to test for reference cycles.  NodeStack can be used to do that.
+pub struct NodeStack(Vec<RsvgNode>);
+
+impl NodeStack {
+    pub fn new() -> NodeStack {
+        NodeStack(Vec::new())
+    }
+
+    pub fn push(&mut self, node: &RsvgNode) {
+        self.0.push(node.clone());
+    }
+
+    pub fn contains(&self, node: &RsvgNode) -> bool {
+        self.0.iter().find(|n| Rc::ptr_eq(n, node)).is_some()
+    }
+}
+
 #[no_mangle]
 pub extern "C" fn rsvg_drawing_ctx_new(
     cr: *mut cairo_sys::cairo_t,
diff --git a/rsvg_internals/src/pattern.rs b/rsvg_internals/src/pattern.rs
index 7db7924d..46104c1d 100644
--- a/rsvg_internals/src/pattern.rs
+++ b/rsvg_internals/src/pattern.rs
@@ -9,7 +9,7 @@ use aspect_ratio::*;
 use attributes::Attribute;
 use bbox::*;
 use coord_units::CoordUnits;
-use drawing_ctx::DrawingCtx;
+use drawing_ctx::{DrawingCtx, NodeStack};
 use error::RenderingError;
 use float_eq_cairo::ApproxEqCairo;
 use handle::RsvgHandle;
@@ -237,14 +237,23 @@ impl NodeTrait for NodePattern {
 fn resolve_pattern(pattern: &Pattern, draw_ctx: &mut DrawingCtx<'_>) -> Pattern {
     let mut result = pattern.clone();
 
+    let mut stack = NodeStack::new();
+
     while !result.is_resolved() {
         if let Some(acquired) = draw_ctx.get_acquired_node_of_type(
             result.fallback.as_ref().map(String::as_ref),
             NodeType::Pattern,
         ) {
-            acquired
-                .get()
-                .with_impl(|i: &NodePattern| result.resolve_from_fallback(&*i.pattern.borrow()));
+            let node = acquired.get();
+
+            if stack.contains(node) {
+                result.resolve_from_defaults();
+                break; // reference cycle; bail out
+            }
+
+            node.with_impl(|i: &NodePattern| result.resolve_from_fallback(&*i.pattern.borrow()));
+
+            stack.push(node);
         } else {
             result.resolve_from_defaults();
         }
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 45687448..fa8c650a 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -11,7 +11,8 @@ test_programs =               \
        crash           \
        render-crash    \
        dimensions      \
-       errors
+       errors          \
+       infinite-loop
 
 # Removed "styles" from the above; it is broken right now
 
@@ -27,6 +28,10 @@ errors_SOURCES =     \
        errors.c        \
        $(test_utils_common_sources)
 
+infinite_loop_SOURCES =        \
+       infinite-loop.c         \
+       $(test_utils_common_sources)
+
 rsvg_test_SOURCES = \
        rsvg-test.c     \
        $(test_utils_common_sources)
@@ -70,6 +75,7 @@ dist_installed_test_data =                                            \
        $(wildcard $(srcdir)/fixtures/crash/*.svg)                      \
        $(wildcard $(srcdir)/fixtures/crash/*.png)                      \
        $(wildcard $(srcdir)/fixtures/errors/*)                         \
+       $(wildcard $(srcdir)/fixtures/infinite-loop/*)                  \
        $(wildcard $(srcdir)/fixtures/loading/*)                        \
        $(wildcard $(srcdir)/fixtures/reftests/*.svg)                   \
        $(wildcard $(srcdir)/fixtures/reftests/*.png)                   \
diff --git a/tests/fixtures/infinite-loop/341-recursive-pattern.svg 
b/tests/fixtures/infinite-loop/341-recursive-pattern.svg
new file mode 100644
index 00000000..66cb07e5
--- /dev/null
+++ b/tests/fixtures/infinite-loop/341-recursive-pattern.svg
@@ -0,0 +1,5 @@
+<svg>
+  <pattern id="p1" xlink:href="#p1"/>
+  <pattern id="p2" xlink:href="#p1"/>
+  <rect fill="url(#p2)" width="100" height="100"/>
+</svg>
diff --git a/tests/infinite-loop.c b/tests/infinite-loop.c
new file mode 100644
index 00000000..978c97dc
--- /dev/null
+++ b/tests/infinite-loop.c
@@ -0,0 +1,70 @@
+/* -*- Mode: C; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* vim: set ts=4 nowrap ai expandtab sw=4: */
+
+#include <glib.h>
+#include "librsvg/rsvg.h"
+#include "test-utils.h"
+
+static void
+test_infinite_loop (gconstpointer data)
+{
+    if (g_test_subprocess ()) {
+        GFile *file = G_FILE (data);
+        RsvgHandle *handle;
+        GError *error = NULL;
+        cairo_surface_t *surface;
+        cairo_t *cr;
+
+        handle = rsvg_handle_new_from_gfile_sync (file, RSVG_HANDLE_FLAGS_NONE, NULL, &error);
+        g_assert_no_error (error);
+        g_assert (handle != NULL);
+
+        surface = cairo_image_surface_create (CAIRO_FORMAT_ARGB32, 10, 10);
+        cr = cairo_create (surface);
+        g_assert (rsvg_handle_render_cairo (handle, cr));
+
+        cairo_surface_destroy (surface);
+        cairo_destroy (cr);
+
+        g_object_unref (handle);
+
+        return;
+    }
+
+    g_test_trap_subprocess (NULL, 5000000, 0);
+    g_assert (!g_test_trap_reached_timeout ());
+    g_assert (g_test_trap_has_passed ());
+}
+
+int
+main (int argc, char *argv[])
+{
+    GFile *base, *crash;
+    int result;
+
+    g_test_init (&argc, &argv, NULL);
+
+    if (argc < 2) {
+        base = g_file_new_for_path (test_utils_get_test_data_path ());
+        crash = g_file_get_child (base, "infinite-loop");
+        test_utils_add_test_for_all_files ("/infinite-loop", crash, crash, test_infinite_loop, NULL);
+        g_object_unref (base);
+        g_object_unref (crash);
+    } else {
+        guint i;
+
+        for (i = 1; i < argc; i++) {
+            GFile *file = g_file_new_for_commandline_arg (argv[i]);
+
+            test_utils_add_test_for_all_files ("/infinite-loop", NULL, file, test_infinite_loop, NULL);
+
+            g_object_unref (file);
+        }
+    }
+
+    result = g_test_run ();
+
+    rsvg_cleanup ();
+
+    return result;
+}