Re: Checks for recursive element behavior (issue 6943072)
On Sat, 22 Dec 2012 00:46:21 -0800, wrote: In this particular case, however, the problem is adding an axis group to an axis group. _Any_ old axis group to _any_ old axis group. No no. The reported problem \new StaffGroup \RemoveEmptyStaves <> causes a StaffGrouper to be added to the VerticalAxisGroup created in the StaffGroup context. That by itself seems fine, as I would expect that StaffGrouper's elements to be the VAGs from the two grouped staves. For some reason, though, that StaffGrouper gets the VAG from the enclosing StaffGroup context added to its list. StaffGroups nest, which adds StaffGroupers to the elements of the outer StaffGroupers with no problem, so we are accustomed to letting grouping-objects have elements that are themselves objects of the same type. On Sat, 22 Dec 2012 02:01:25 -0800, m...@mikesolomon.org wrote: My patch is intended to avoid this segfault by not allowing recursive nesting of elements in theelements list. Yes, but usually we look for the cause of a situation that triggers such an error-trap, when the situation itself seems incorrect. Does it not seem incorrect that the same VAG both contains and is an element of a StaffGrouper ? What correct processing of objects would make either of these inclusions ? Also, you still get segfault as soon as you add a second staff and complete at least one bar. (Try the example above as-is and substituting ChoirStaff.) If we use the Hara_kiri_engraver by default, and define removeEmptyStaves as \override VerticalAxisGroup #'remove-empty = ##t then it could be set at any level like the other options. I've just made this change on my Windows installation, and now my LilyPond works, and yours doesn't, nyah. ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 22 déc. 2012, at 09:46, d...@gnu.org wrote: > On 2012/12/22 08:29:59, mike7 wrote: >> Where in the new code are things being allocated and thrown away > temporarily on >> the heap? > > What do you think extract_grob_set does? Got it. > >> If there is a more efficient way to implement this patch, let me know. > It >> seems, though, that the only way to prevent grobs being elements of > other grobs >> is to prevent grobs from being added to elements lists à la this > patch. > > That is rubbish. We can't add checks for any hypothetical programming > error that can't come about as user error. True. > Here we have one situation, > namely axis groups, where there is a possibility of user error. So I > proposed setting a context property when having an axis group engraver. It sounds like you're mixing together "axis-groups" and "Axis group engraver." The axis group engraver creates VerticalAxisGroups, which implement the axis-group-interface. There are, however, numerous grobs that implement the axis-group-interface that are not created in the Axis_group_engraver. To avoid future confusion, it may be worth renaming the engraver with a convert-ly rule. My patch treats all grobs with an element array (meaning that they implement axis-group-interface). > > If you think that adding something to an existing set twice is a > fundamental problem, you can easily enough create a hashtable for each > set and check before adding to it that the element is not a member of > this set. This is one manifestation of the problem. The deeper problem is that if we have grobs A, B, C, and D and the following happens : A adds B as an element. B adds C C adds D D adds A A hash structure cannot avoid this. > > In this particular case, however, the problem is adding an axis group to > an axis group. _Any_ old axis group to _any_ old axis group. The check > for that is trivial: in the code adding a grob to an axis group, check > that what you add is not an axis group (assuming that axis groups are > top-level containers). It seems like you're mixing up axis-group-interface with Axis_group_engraver. When you say _any_ old axis group, note that NoteColumn, Ambitus, and DynamicLineSpanner are all axis groups with element lists. A user can make an Ambitus the element of a NoteColumn which is the element of a DynamicLineSpanner which is then the element of the Ambitus if she so chooses. This will result in a segfault when the elements lists are recursively iterated through. My patch is intended to avoid this segfault by not allowing recursive nesting of elements in the elements list. I am positive that your proposal would work in this specific case, but I also know that you advocate general, holistic, simple and "boring" solutions that cover many things. I feel that my solution is that. It seems that the only issue, as expressed before, is the efficiency one. I will do benchmarks later today. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 2012/12/22 08:29:59, mike7 wrote: Where in the new code are things being allocated and thrown away temporarily on the heap? What do you think extract_grob_set does? If there is a more efficient way to implement this patch, let me know. It seems, though, that the only way to prevent grobs being elements of other grobs is to prevent grobs from being added to elements lists à la this patch. That is rubbish. We can't add checks for any hypothetical programming error that can't come about as user error. Here we have one situation, namely axis groups, where there is a possibility of user error. So I proposed setting a context property when having an axis group engraver. You keep ignoring that proposal as if I never said anything. It is simple, efficient, and addresses the problem we see here. If you think that adding something to an existing set twice is a fundamental problem, you can easily enough create a hashtable for each set and check before adding to it that the element is not a member of this set. In this particular case, however, the problem is adding an axis group to an axis group. _Any_ old axis group to _any_ old axis group. The check for that is trivial: in the code adding a grob to an axis group, check that what you add is not an axis group (assuming that axis groups are top-level containers). https://codereview.appspot.com/6943072/ ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 22 déc. 2012, at 09:25, d...@gnu.org wrote: > On 2012/12/22 06:41:06, mike7 wrote: >> On 21 déc. 2012, at 10:09, mailto:d...@gnu.org wrote: > >> > On 2012/12/21 07:59:02, MikeSol wrote: >> >> 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. >> > >> > I am not ok with that. It looks really, really, really expensive. > I >> > don't see what would be wrong with just setting a context property > flag >> > axis-group-active in the engraver and refuse to maintain an axis > group >> > if the flag is already set. > >> In general, elements should never recursively be elements of > themselves. > > Either grobs being elements of other grobs are a frequent occurence, in > which case going through _all_ elements recursively each time in that > particularly expensive way of unpacking them into a throw-away array is > really wasteful, or they aren't, in which case we should just bother > with those cases which actually act as grob containers. All grobs that have an element list are, by definition, implementing axis-group-interface and are thus grob containers. The recursion through the elements list happens at the time of adding, not each time the element list is accessed. > > If we are talking about a general recursion-blocking mechanism, there > are much, much, much, much more efficient ways than going recursively > through the whole data base in an inefficient way (allocating and > throwing away arrays temporarily on the heap) for every new element. Where in the new code are things being allocated and thrown away temporarily on the heap? If there is a more efficient way to implement this patch, let me know. It seems, though, that the only way to prevent grobs being elements of other grobs is to prevent grobs from being added to elements lists à la this patch. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 2012/12/22 06:41:06, mike7 wrote: On 21 déc. 2012, at 10:09, mailto:d...@gnu.org wrote: > On 2012/12/21 07:59:02, MikeSol wrote: >> 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. > > I am not ok with that. It looks really, really, really expensive. I > don't see what would be wrong with just setting a context property flag > axis-group-active in the engraver and refuse to maintain an axis group > if the flag is already set. In general, elements should never recursively be elements of themselves. Either grobs being elements of other grobs are a frequent occurence, in which case going through _all_ elements recursively each time in that particularly expensive way of unpacking them into a throw-away array is really wasteful, or they aren't, in which case we should just bother with those cases which actually act as grob containers. If we are talking about a general recursion-blocking mechanism, there are much, much, much, much more efficient ways than going recursively through the whole data base in an inefficient way (allocating and throwing away arrays temporarily on the heap) for every new element. https://codereview.appspot.com/6943072/ ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
http://en.wiktionary.org/wiki/irony https://codereview.appspot.com/6943072/ ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 21 déc. 2012, at 10:09, d...@gnu.org wrote: > On 2012/12/21 07:59:02, MikeSol wrote: >> 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. > > I am not ok with that. It looks really, really, really expensive. I > don't see what would be wrong with just setting a context property flag > axis-group-active in the engraver and refuse to maintain an axis group > if the flag is already set. In general, elements should never recursively be elements of themselves. This seems like a safe assumption for LilyPond programming, especially as recursion through elements lists becomes more prevalent in the code base. This is an implicit assumption with which we've been programming all along, but the advantage of making it explicit via a check in the Pointer_group_interface is that it alerts users of this. We could maybe create a flag -recursive-element-leniency to allow for this if people really want it. Keith thinks that it's worth it to put this in. I do too, but I'd like unanimity, so if you still think this should not be part of LilyPond then I'll scrap the patch. Note that I'm not adverse to any of your suggestions about the engravers, but I think that this is a healthy patch for LilyPond that will fix potential segfaults down the road (inadvertent user mistakes w/ element lists) in addition to the one reported. Of course, if it slows LilyPond down too much then it's not worth it, but I'm ok with it being in a development version and then reverting it if people complain too much about speed issues. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 2012/12/21 07:59:02, MikeSol wrote:
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.
Don't worry; I'm sure we'll hear about it in lilypond-user if there is a
problem.
I still get a segfault with
\new StaffGroup \with {\RemoveEmptyStaves } << c'1 c' >>
but the example in the tracker works, so I guess this it good to go.
https://codereview.appspot.com/6943072/
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Checks for recursive element behavior (issue 6943072)
On 2012/12/21 07:59:02, MikeSol wrote: 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. I am not ok with that. It looks really, really, really expensive. I don't see what would be wrong with just setting a context property flag axis-group-active in the engraver and refuse to maintain an axis group if the flag is already set. Another reasonable course would be to merge Hara_kiri_engraver and Axis_group_engraver and let the difference just be determined by setting flags. Then we can get rid of the error-prone parts of \RemoveEmptyStaves, the meddling with engravers. However, it would not help against nesting Staffs or similar things causing multiple axis groups. https://codereview.appspot.com/6943072/ ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Checks for recursive element behavior (issue 6943072)
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 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);
}
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
