Checks for recursive element behavior (issue 6943072)

[mtsolo]

Reviewers: ,

Message:
Hey all,

I'm ok w/ this on the countdown but can someone check out David's
suspicion that this slows stuff down by O(n^3)?  I definitely won't push
this if it slows LilyPond down to a crawl.

Cheers,
MS

Description:
Checks for recursive element behavior

Please review this at https://codereview.appspot.com/6943072/

Affected files:
  M lily/engraver.cc
  M lily/include/pointer-group-interface.hh
  M lily/pointer-group-interface.cc


Index: lily/engraver.cc
diff --git a/lily/engraver.cc b/lily/engraver.cc
index  
db1303d63ce3b918f95e5d9f254c589a84bf89ea..11d080eb6e061a26c23356a825c89e4b8d434731  
100644
--- a/lily/engraver.cc
+++ b/lily/engraver.cc
@@ -123,7 +123,6 @@ Engraver::internal_make_grob (SCM symbol,

   SCM handle = scm_sloppy_assq (ly_symbol2scm ("meta"), props);
   SCM klass = scm_cdr (scm_sloppy_assq (ly_symbol2scm ("class"), scm_cdr  
(handle)));
-
   if (klass == ly_symbol2scm ("Item"))
     grob = new Item (props);
   else if (klass == ly_symbol2scm ("Spanner"))
Index: lily/include/pointer-group-interface.hh
diff --git a/lily/include/pointer-group-interface.hh  
b/lily/include/pointer-group-interface.hh
index  
e265bedc79d0cf29d72debc26af7c7eaa0d242b2..1970b1073fbddea5d63d6e02118bcd5ad0c906d2  
100644
--- a/lily/include/pointer-group-interface.hh
+++ b/lily/include/pointer-group-interface.hh
@@ -34,6 +34,7 @@ public:
   static void set_ordered (Grob *, SCM, bool);
   static Grob_array *get_grob_array (Grob *, SCM);
   static Grob *find_grob (Grob *, SCM, bool (*pred) (Grob *));
+  static bool has_in_element_chain (Grob *needle, Grob *hay);
 };

 vector<Grob *> const &internal_extract_grob_array (Grob const *elt, SCM  
symbol);
Index: lily/pointer-group-interface.cc
diff --git a/lily/pointer-group-interface.cc  
b/lily/pointer-group-interface.cc
index  
045563d457b9acd572a203788fb5dea3d4dab336..11deb42bee9f12e0d166b0db749d6d111d9cabb6  
100644
--- a/lily/pointer-group-interface.cc
+++ b/lily/pointer-group-interface.cc
@@ -21,6 +21,7 @@

 #include "grob-array.hh"
 #include "grob.hh"
+#include "international.hh"

 int
 Pointer_group_interface::count (Grob *me, SCM sym)
@@ -68,9 +69,32 @@ Pointer_group_interface::find_grob (Grob *me, SCM sym,  
bool (*pred) (Grob *))
   return 0;
 }

+bool
+Pointer_group_interface::has_in_element_chain (Grob *hay, Grob *needle)
+{
+  if (!needle || !hay)
+    return false;
+
+  if (needle == hay)
+    return true;
+  extract_grob_set(hay, "elements", haystack);
+  for (vsize i = 0; i < haystack.size (); i++)
+    {
+      if (has_in_element_chain (haystack[i], needle))
+        return true;
+    }
+  return false;
+}
+
 void
 Pointer_group_interface::add_grob (Grob *me, SCM sym, Grob *p)
 {
+  if (sym == ly_symbol2scm ("elements") && has_in_element_chain (p, me))
+    {
+      me->programming_error (_f ("Cowardly refusing to add %s to the  
elements list of %s, which would result in recursive behavior.", p->name  
().c_str (), me->name ().c_str ()));
+      return;
+    }
+
   Grob_array *arr = get_grob_array (me, sym);
   arr->add (p);
 }