#5345 Crash with specific combination of pitch and omitted note head

[Simon Albrecht]

Issue 5345: Stop crash while merging ledger lines

The old code (part of issue 4979) used quite broken code for merging
intervals that could crash eating all memory under certain conditions
and failed to account for merging certain interval combinations.

The incremental broken merge code has been thrown out and replaced by
using the non-incremental Interval_set::union which has been designed
for that purpose.

http://codereview.appspot.com/343270043

---

Reported by Lukas-Fabian Moser in this thread with the following minimal example:

WARNING: Only test with appropriate configuration of ulimit, see the e-mail exchange.

\version "2.19.80"

\new Staff <<
  {
    \clef bass
    e,4
  }
  {
    \omit NoteHead
    e,4
  }
>>

Lukas says:

Everything here (except the \version) seems to be necessary. I can reproduce the crash with some other configurations as well (another pitch in tenor clef, for instance), but removing any single command seems to resolve the problem. Also, putting each "voice" into a regular \new Voice (as in Harm's proposal) makes the problem disappear. Just as taking f, instead of e, for the pitch does (which could point to ledger lines).

David K. says the problem appears to be in the page builder.

[Thomas Morley]

First bad commit is:

commit 4f2abdb21ee6b6f2441276f8dc81507708654915
Author: Paul Morris paulwmorris@gmail.com
Date: Sun Oct 2 15:52:14 2016 -0400

Issue 4979/1: Don't merge non-overlapping ledger lines

[David Kastrup]

Oh wow. I did not think of bijecting, and "don't merge non-overkapping ledger lines" is a theme that might be related to omitted note heads. The pitch would require a ledger line as noted by Lukas, and its double occurence would warrant some sort of merging.

This helps a lot.

[David Kastrup]

Well, the patch contains this part:

+                      +                  // When the extents of two ledgers at the same
+                  // vertical position overlap horizontally, we merge
+                  // them together to produce a single stencil.  In rare
+                  // cases they do not overlap and we do not merge them.
+
               if (lr.ledger_extents_.find (lpos) == lr.ledger_extents_.end ())
-                    lr.ledger_extents_[lpos] = x_extent;
+                    // Found nothing for this lpos.
+                    lr.ledger_extents_[lpos].push_back(x_extent);
                   else
-                    lr.ledger_extents_[lpos].unite (x_extent);

I suspect that "do not merge" here translates to "eat all memory and crash". But I'll have to do more of an analysis to be sure.

[Carl Sorensen]

Looks to me like a problem with a missing pure-impure-container -- checking the extent has a side effect, so you create a new layout, and off you go. But I haven't checked out the exact code.

[David Kastrup]

Well, I haven't started serious analysis yet, but my hunch is that an array basically containing {a, b} is iteratively changed into {a, b, a}, {a, b, a, a}, {a, b, a, a, a} or similar. Basically it is extended all the while and the iteration never finishes.

[David Kastrup]

Issue 5345: Stop crash while merging ledger lines

The old code (part of issue 4979) used quite broken code for merging
intervals that could crash eating all memory under certain conditions
and failed to account for merging certain interval combinations.

The incremental broken merge code has been thrown out and replaced by
using the non-incremental Interval_set::union which has been designed
for that purpose.

http://codereview.appspot.com/343270043

[Anonymous]

Passes make, make check and a full make doc.

[Anonymous]

Patch on countdown for June 22.

[Anonymous]

Patch counted down, please push.

[Anonymous]

author  David Kastrup <dak@gnu.org> 
    Mon, 18 Jun 2018 01:21:13 +0100 (02:21 +0200)
committer   David Kastrup <dak@gnu.org> 
    Fri, 22 Jun 2018 08:06:45 +0100 (09:06 +0200)
commit  9e6724e1a69fc2af653751019ba7d0e5b3bb0f95