GSOC 2020: Tree Model - Week 1

Posted 4 years ago

Hello guys! Time for another blog ...

This week, I had an interesting talk with Marc Sabatella, MuseScore Director of Education. He had invited me to his weekly series on YouTube called MuseScore Café, in which I talked about my project. It was a nice experience for me, and I am quite thankful to Marc for inviting me to MuseScore Café. :-)

MuseScore Café

After this I had some discussion with my mentor, and we finally decided that we will be following the second method that I mentioned in my previous blog, i.e. adding a treeChild(int n) function to each class. I will also be adding an iterator class only to the ScoreElement class so that we can write the loops to iterate over the children in a more natural syntax.

We were mainly thinking about an iterator based approach vs. this one because of performance considerations in linked lists. An iterator based approach would traverse a linked list in O(n) time complexity while this one would be O(n^2). Peter had an idea that we could implement two functions getChild(n) and getNextChild(currentChild) and then we could decide which one to use for iteration based on a function bool isLinkedList(). However, there was another problem: even if we managed to do it this way, QT still internally uses indexes in the QAbstractItemModel and has a kind of random-access model. So we decided that I could just implement getChild(n) right now and I might refactor the linked-list based classes later on and to use vectors in their place.

This would trade one performance hit for another, i.e. randomly accessing any element would take O(1) time in a vector instead of O(n) in a linked list but insertion would take O(n) instead of O(1). But since accessing the element would be more common than insertion so it will probably be better if we used vectors everywhere instead of a linked list.

Work done last week

So, after this was decided, firstly I changed the previous branch on GitHub and labelled it "experimental" and created a new branch which had the relevant code for the tree debugger etc, and then I created a WIP pull request which you can find here: https://github.com/musescore/MuseScore/pull/6174.

Then I went ahead and added the iterator and the treeChild function to the following classes: Score, Measure, Segment, Rest, Chord, Note. I also modified the tree debugger to show the pointers too, because I wanted to see if any element was returning a null pointer in its children. At first, I had made the children of Segment the elements in its "elist" which were Rests and Chords but soon I realised that a Segment can also have other children like Fermatas and Chord Symbols which are stored as "annotations" so I added those too. Similarly, I added the remaining elements in Chord and Note too.

I have tried to write the code in such a way that it avoids creating the whole list of children each time treeChild(n) function is called, and only returns the required element directly so that it will lead to better performance.

This is what the tree looks like now:

Screenshot from 2020-06-08 14-44-32.png

There was also a failing test that I fixed. The reason it was failing was, I had changed the Element class to have a ScoreElement as its parent instead of an Element, and I had made it always return the ScoreElement in the treeParent() function. (Because in the new tree model, a measure might have the score or page as the parent, for example.) But the parent() function, which was already there, needed to return an Element instead. So I had used a dynamic_cast to check whether to return an Element or a nullptr. However, I didn't know that using dyanamic_cast on a deleted pointer can actually cause a crash! (I'm actually learning a lot about C++ too, thanks to this project! ;)

So this means that now you can only call parent() on an element if the parent actually exists or it is null. If the parent is deleted then you cannot call parent(). Now surprisingly this only broke the code in one place in some removeElement function, and I fixed it. But I now think this change was not really required and it might cause other crashes too, so I'll probably just revert it.

Work planned to do next

Currently, the tree contains

Score -> Measure -> Segment -> Rest / Chord -> Note -> Children of Note (dots, ties, spanners, etc)

and also the articulations and linked elements of Segments, Chords and Notes.

It currently doesn't include:

Generated elements like Stems, Beams and Hooks.
Spanner segments (slurs etc)
Pages and Systems
Lyrics

This week I will be adding more elements to the tree, like the ones I might have left out accidentally, and the generated elements, and Pages, Systems etc. I might add some boolean parameters to the function treeChild() like:

ScoreElement* treeChild(int n, bool includePages=false, bool includeGenerated=false)

So that the tree can go either from Score -> Page -> Systems -> Measures or directly Score -> Measures, as required.

That's all for today's blog, see you next week!

GSOC 2020: Tree Model - Week 1

Work done last week

Work planned to do next

Other links