GSoC 2020: Tree Model - Week 4 (scanElements refactoring)

Posted 11 months ago

Hello there! This is the latest blog in my series of GSoC blog posts.

Last week, I had planned that I will be working on refactoring the scanElements function using the score tree functions. I was able to nearly complete it but just near the end of the week, I found an interesting bug, because of which I'll have to make some changes either to the tree model or some code in Page or Measure classes. So it'll probably take a little longer to finish this refactoring.

You can see the latest changes I'm making on this PR on GitHub:

So here's a summary of what I did:

  1. I renamed the scanElements function to scanElementsOld and created a new scanElements function in its place.

    Earlier scanElements was decalred as a virtual function in the Element class but it was also implemented in Score class without overriding the virtual function. So apparantly it should have been declared in the ScoreElement class from the start? Maybe it wasn't done that way for historical reasons. Anyways I created the new scanElements in the ScoreElement class.

  2. I created a new test that will compare the elements scanned by scanElements and scanElementsOld. I created this test, so that when this test passes I will know that I have refactored scanElements correctly and it will not change any exisiting functionality. I will remove this test later, along with the old scanElements function once everything seems to work.

  3. I implemented the new scanElements function using a tree traversal. This is what the basic implementation looks like:


    This function needed to be overriden in a small number of classes. For example in class Rest we need to check the isGap() function, and also call the given function on this in the above mentioned classes, etc.

  4. After some testing, It turned out that I had missed two elements, Tuplets and Melisma lines in my original tree model, which I added in another commit..

  5. After a while I was able to make sure that scanElements is working same as before on the 4 scores I used for testing (two artificial ones, one was a copy of the Moonlight Sonata, and one was the Goldberg variations by Bach).

    After this I tested the application with the new scanElements and it seemed to be working completely okay, and I could find no obvious bugs yet.

  6. Now we come to the interesting part... One test (tst_unrollrepeats) was still failing on travis. I tested it locally and tried to find what was going wrong. I thought that it must be some trivial bug and this PR would also be finished soon. But it didn't turn out to be the case ;)

    It seemed like old and new scanElements were scanning different elements after repeats were unrolled in the test score. However when I checked the generated score with tst_scanElements I didn't get any difference. Then after some debugging I found out the reason for it. After unrolling the repeats, new measures were added to the score, but it seems like the Page and System classes aren't getting the updated list of measures until a layout is done.

    The original scanElements scans Measures, Pages and Systems separately, like in the left diagram (the measures are in a doubly-linked list, and the newly inserted measure is dashed), whereas the new one follows the tree structure like in the new one. So the original scanElements is able to see the newly inserted measures but the new implementation doesn't see those unless I call score->doLayout() first.


So I have a few ideas in my mind to fix this problem:

  1. Use the same logic as before in scanElements in the Score class.
  2. Change the score tree to match the scanElements function.
  3. Modify some code in Measure class so that as soon as a measure is constructed it is added to some page or system (possibly the same system as previous one), but the layout is not done yet.
  4. Call doLayout() after every Measure insert?

I'll try to test some of these options this week and I'll try to figure out what's the best way to fix this problem.

Other Links

PR on GitHub:
Previous Blog:…
Next Blog:…


This is coming from a non-technical person but I thought I'd ask:

I was chatting recently to the guys at Dorico about how they are able to provide free metered music and the ability for tuplets to cross barlines (which Sibelius can't do). Regarding tuplets, they suggested that a limitation of Sibelius was that it had a tree structure - of sorts. Since it classifies durations as 'belonging' to bars, it was an automatic limitation that meant they could never have tuplets crossing barlines.

Apart from that - the ability to turn off bars altogether and write free metered music is very powerful and eventually we'd like to be able to do this too (and would def like tuplets to be able to cross barlines). I'm bringing this up to find out whether it will be an issue for us? Again - I'm speaking conceptually here and I'm not sure if it is relevant to what you're doing. Thought I'd mention it.


In reply to by Tantacrul

Hi @tantacrul !

I think there is a simple way to make tuplets cross barlines already in the existing code, we can change the tuplet into a spanner element. In the tree model, it would be represented in the same way as slurs and beams are being handled currently in the model.
If we want to implement this it would probably require some refactoring in the playback and drawing code, and maybe we'll have to change the code that inserts the tuplets into the score.

What that means is, instead of a tuplet containing notes we can have a tuplet attached to the start note (and the tuplet itself has information about its end note).

So instead of this,

    Note A
      Note B
      Note C
      Note D

we have this:

    Note A
    Note B
       Tuplet (with end note: Note D)
    Note C
    Note D

What I mean to say is, the tree model wouldn't cause any limitations here, because the duration of the notes etc. are not being controlled by the tree. Right now the tree is only used as a "read-only" model.

I will probably also try to find some better way to represent spanners in the model later during my project, for example we could have a startSpanner and endSpanner element.

In fact, one of the motivations for doing this project was also to solve issues related to polymeter music. We could do that by modifying the tree so that each individual staff contains measures, instead of the measures containing vertical segments (like it is now). I'm not sure at the moment how far I would be able to go with that during GSoC, but I hope this project could serve as a beginning to improve the capabilities of MuseScore.