GSOC 2020: Tree Model - Week 1
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é. :-)
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
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:
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
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!
Pull request on GitHub: https://github.com/musescore/MuseScore/pull/6174