Kristian Rietveld

When concluding the discussion on reference counting rules for nodes in an earlier blog post, we noted that these rules put limits on what kind of visible functions will function properly. The filter model must follow changes in its child model to keep the internal data structure up to date. As we have seen, changes can only be expected to be received for levels in which the filter model has a reference on at least one node. By default any references obtained on filter model nodes are passed on to the child model. So, the filter model will receive signals for all nodes that are visible in the filter model’s observer.

This is not enough to support an often used use case. If we, for example, want to only show a parent node if one of its children is visible, we need to monitor signals received on the child nodes, also when the parent node is hidden. Once one of the children changes state such that it will become visible, we must make the parent visible as well. Clearly, when the parent is invisible, its children are not referenced by the filter model’s observer.

Because this use case is so often used, we have made GtkTreeModelFilter explicitly support it. This is done by building child levels in the internal data structure of each node that could be visible. When a child level is built, a reference is obtained on the first node in that level. A node could be visible if any node in the level it is contained in (so any sibling) has been referenced by the filter model’s observer. Note that we thus look at the reference count of a level here and not at the reference count of individual nodes. We must also build the child level for invisible nodes contained in a visible level. Such child levels are monitored for changes and for every signal received a check is done whether this changed the visibility state of the parent node.

This explicit support is limited to dependencies from a node on its child for the node’s visibility state. If you want a node’s visibility to depend on the children of the node’s immediate children, you are on your own. In such cases you can either rely on GtkTreeStore, which always emits signals for all nodes because it does not implement reference counting, or obtain references on the additional child levels yourself.

To wrap up, we can in general say that visible functions should only use data or properties from the node for which the visibility state must be determined, its siblings or its parents. Because of the explicit support for this, it may also use data or properties from its children. If any other data is used, the filter model may not work reliably.

With this post, we have come to the end of the blog post series on peculiarities learned when fixing up GtkTreeModelSort and GtkTreeModelFilter last Summer. If you have any questions about these posts, do feel free to
contact me.

GtkTreeModelSort and GtkTreeModelFilter basically proxy the shape of their child model, including modifications. Internally, the models proxy incoming requests from their observers to requests on the child model. A mapping is needed from nodes exposed by the sort and filter models to nodes in their child models. Since the models can “perform” modifications, the mapping must be able to deal with these modifications.

The mapping is internally implemented as a tree of nodes that are visible in the observer (i.e. the observer took references on these nodes). Each level is an array of nodes. When we hand out an iterator to the observer, the user data of the iterator is set to a pointer to the node in the array. When the iterator is used, we can very quickly access the node in the internal data structure. Using data in this node (for example index into the level in the child model) we can construct an iterator relative to the child model to forward the operation. Sometimes we can even cache these iterators. A node can have a “children” pointer set to point at a child level.

Using arrays works well — we have been using GArray for a long time — unless the internal data structure is subject to frequent changes. This either happens due to a lot of activity in the child model, or due to filtering activity. When adding and removing nodes in the GArray, memory has to be moved. When the array is large and this happens often, this becomes very costly.

Xavier Claessens noticed this and wrote a patch to replace the use of GArray with GSequence. This significantly sped up operation of the filter model in certain cases. We have committed this change as part of the “treemodel-fix” branch last year, but only after we got a lot more of the sort and filter model under unit test. This way, we could ensure that no regressions were introduced when migrating from GArray to GSequence.

A couple of rules must be played by when using reference counting of GtkTreeModel nodes. These rules very much make sense when you reason about them. Also, the rules are paramount to implementing something like GtkTreeModelFilter, as we will see later. Let us first discuss the rules:

1. Never take a reference on a node, without owning a reference on its parent. This means that all parent nodes of a referenced node must be referenced as well. Looking at this from a GtkTreeView perspective, this rule will never be violated. GtkTreeView will always take a reference on every node that is present in GtkTreeView’s RB tree, which contains all children of expanded parents. Naturally, GtkTreeView cannot expand a parent which is not visible itself, so parent nodes are always referenced.

   When you are implementing your own GtkTreeModel, you are free to reference whatever you want. In this case, it becomes important to adhere to the rules. When GtkTreeModelSort or GtkTreeModelFilter is set as the child model of your custom model, things quickly go wrong if you do not play by the rules. The sort and filter models aggressively empty their internal data structures of nodes that are no longer needed. This process is based on the current reference counts of the nodes. So, when you reference child nodes without holding a reference on their parents, a parent might eventually end up at a reference count of zero while its children are still visible. A parent level might wrongly be pruned from the cache, corrupting the data structures. (Of course, the sort and filter models could enforce the rule for you by referencing all parents when a node is reference, but this significantly hampers performance because many more virtual ref/unref calls are done than necessary).

2. Outstanding references on a deleted node are not released. So, once you receive a row-deleted signal for a node in your model, do not expect any unref call for that node to follow. You can implicitly erase all references.

   If you are not the model implementor, but instead have a couple of references on nodes in this model, then do not release references of a node once you have received the signal that that node has been deleted. (This actually implies you will have to listen for row-deleted signals if you have references on nodes, or you use a GtkTreeRowReference which will be set to NULL once the node has been deleted).

   It is clear why this rule is there: by the time you receive a row-deleted signal for a node, the node no longer exists in the model so you cannot get an iter to this node to perform the unref call.

3. Models are not obligated to emit a signal on rows of which none of its siblings are referenced. To phrase this differently, signals are only required for levels in which nodes are referenced. For the root level however, signals must be emitted at all times (however the root level is always referenced when any view is attached).

   What is this rule trying to say at all? Imagine you have a ref-counted model, some node in the root level has a couple of child nodes and only the nodes in the root level are referenced. This means that none of the nodes is currently expanded. The rule says that, as a result, any signals for the child nodes (e.g. row-changed if a child nodes changes) do not have to be emitted.

   Makes sense — what view is interested in signals of nodes that are not displayed in the view anyway? In general, you are indeed not interested. But the for GtkTreeModelFilter this rule is very important in order to properly handle a sensible use case. Imagine that you have a filter on child nodes. You only want to show an expander arrow next to the parent node if any of the child nodes is visible. To handle the expander arrow correctly, we must receive events for the child nodes, also when these nodes are not referenced. GtkTreeModelFilter handles this by explicitly obtaining a reference on one of the child nodes if a parent is referenced. Due to this rule, a reference on a single node is sufficient to start receiving signals for this level.

In summary, we can say that good understanding of these rules, which seem so obvious, is crucial when implementing a model like GtkTreeModelFilter. The rules are used to determine when it is required to emit signals and when levels in the internal data structures can be cleaned up. I can go into more detail on what is involved in GtkTreeModelFilter, but that is probably not of that much interest. What is for example required is to for each node maintain two reference counts; it’s actual, real, reference count and it’s external reference count. The external reference count maintains the reference count based on the ref and unref calls received from the model’s observer. This determines a node’s visibility, so should not be mixed up with any reference on the node taken internally!

As we have seen, these rules also put limits on what can be done with a visible function in GtkTreeModelFilter. More on that in a later blog post.

Many people are confused by what exactly the reference counting methods ref_node() and unref_node() in the GtkTreeModel interface are intended for. These methods are a way for views (or more generically, model observers) to let models know when nodes are being displayed. For example, GtkTreeview will obtain a reference on a node when the node is visible and release the reference when the node becomes invisible. And this is immediately the main source of the confusion: the confusion typically centers around the exact definition of node visibility.

There are two definitions of visibility in use:

1. A node is visible when it is visible on the screen, that is, the user can currently see it. This is the most obvious definition of this term. For a node to be visible according to this definition, the node’s parent must be in expanded state, secondly, the coordinates of the node must be within the coordinates that are currently visible in the tree view’s scrollable viewport.
2. A node is visible when its parent node is in the expanded state (or the node is in the root level in which case you can say that it is always visible because its implicit parent is always in expanded state). Do note that when a node is visible according to this definition, it might not be immediately visible to the user! This definition does not say anything about the current position of the scrollbar.

For the reference counting mechanism of GtkTreeModel, the second definition is in use. So, what is the point exactly in knowing whether a node’s parent is expanded? The design rationale of the reference counting mechanism is to be able to delay loading content of child nodes until it is really necessary. A useful use case is a file system model. You do not want to load in an entire file system tree when the model is being instantiated. Instead, only the root level is loaded. All nodes in the root level will be referenced when the model is attached to a view. In response to this, one could decide to load ahead the child nodes of the root level nodes. Once a root level node is expanded, the children of this node get referenced, and so on. Similarly, when nodes are collapsed, nodes are unreferenced. This information can be used to possibly prune nodes from the tree which are no longer necessary to keep in memory.

Rather unfortunate is that usually you want to avoid loading child nodes if the parent node has not yet been expanded. Especially when you are for example operating on a remote file system. A preferred approach is often to delay loading the nodes until the parent is expanded, displaying a “Loading …” node in the level until the real child nodes are retrieved. The reference counting mechanism does not really aid you to implement that, except that you can re-use it for cache pruning.

The reference counting scheme is not of much use for lists either. Generally, for lists, developers are mostly interested in the first definition of visible. When dealing with lists with large numbers of nodes, you want to avoid loading all data from the data source if this is expensive. Alas, because all nodes in the root level get referenced as soon as the model is attached to a view and there is no relation between the reference count and whether a node is visible on the screen, other methods have to be used to implement this. The fact that models are separated from views and that there is no mechanism to relay information about which nodes are visible on the screen to a model, makes it hard to implement this. What is really needed is a proper “lazy loading model interface”, such that views and models can exchange information on this.

The scheme does work very well for GtkTreeModelSort and GtkTreeModelFilter. These models actually must load child nodes as soon their parent is referenced. GtkTreeModelFilter must process the child nodes (i.e. performing the filter function on these nodes) in order to determine whether the child nodes are visible at all and thus whether the parent node actually has children. Recall that as soon as a node is visible, it is queried whether it has any children such that an expander can be drawn next to the node.

I have a confession to make. Years ago, I told people who wrote GtkTreeModels that implemented reference counting to emit GtkTreeModel:row-deleted before actually removing the node from the model’s internal data structures, contrary to after like the documentation suggested. GtkTreeModelFilter and GtkTreeModelSort have worked like this for years. It turns out I have been wrong, and I now finally understand why — I failed to correlate two commits which fixed related bugs back in 2002.

Back in February 2002, emitting row-deleted after deleting the node from the internal data structure was indeed a problem and caused warnings/errors to be spewed to the console. I (wrongly) reasoned that the nodes had to be available during the row-deleted phase to receive the unref calls, and added a comment:

  /* we _need_ to emit ::row_deleted before we start unreffing the node
   * itself. This is because of the row refs, which start unreffing nodes
   * when we emit ::row_deleted
   */

I continued to refer to this comment even in 2007.

During that e-mail thread, I did notice a single line in gtktreemodel.c mentioning that “Please note that nodes that are deleted are not unreffed.”. But clearly, the contrary was happening in February 2002? Deleted nodes were being unreffed.

It turns out that these faulty unrefs were caused by another bug which was fixed in April 2002! Unfortunately, I failed to correlate these commits and continued to be wrongly convinced that emitting row-deleted after really removing the node could be troublesome.

The good thing is that this is now documented together with other rules to take into account when dealing with reference counting (blog post on this will follow) and it is now unit tested, so it cannot happen again.

So last August (ahem) I announced the merge of the treemodel-fix branch and a blog post series on interesting things that I’ve learned while working on treemodel-fix. By the end of the Summer, I got carried away with other things. To make sure things do not go wrong this time, I have already written all posts and will be publishing them in the coming two weeks. It is a bit late, but since the code is still the same and the details are quite interesting, I thought it was still useful to do.