Checks for recursive element behavior

Checks for recursive element behavior

[MikeSol, 2012-12-21 07:59:02]

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

[dak, 2012-12-21 09:09:02]

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.

[Keith, 2012-12-22 06:23:06]

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.

[mike7, 2012-12-22 06:41:06]

On 21 déc. 2012, at 10:09, dak@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

[Keith, 2012-12-22 07:41:09]

http://en.wiktionary.org/wiki/irony

[dak, 2012-12-22 08:25:33]

On 2012/12/22 06:41:06, mike7 wrote:
> On 21 déc. 2012, at 10:09, mailto:dak@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.

[mike7, 2012-12-22 08:29:59]

On 22 déc. 2012, at 09:25, dak@gnu.org wrote:

> On 2012/12/22 06:41:06, mike7 wrote:
>> On 21 déc. 2012, at 10:09, mailto:dak@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

[dak, 2012-12-22 08:46:21]

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).

[mike7, 2012-12-22 10:51:21]

On 22 déc. 2012, at 09:46, dak@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

[Keith, 2012-12-22 20:46:43]

On Sat, 22 Dec 2012 00:46:21 -0800, <dak@gnu.org> 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 <<b1 b>>
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, mike@mikesolomon.org <mike@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.