TreeModel ZERO, a taste of life as it should be

If bugmasters are allowed to blog wishlists, then developers should also be allowed to write them! Which is why I wrote my wishlist!

Gtk.TreeModel was in my humble opinion designed wrong. In API design should an interface be just one thing.

A little bit of history

Many framework designers have repeated this in the past. Two of the best framework designers that we have on this planet, Krysztof Cwalina and Brad Abrams from Microsoft, added the meme to one of their books. It would be unfair to only mention those two guys and not the other people at Microsoft, and before that at the Delphi team at Borland. Brian Pepin notes at page 83 of Framework Design Guidelines: “Another sign that you’ve got a well defined interface is that the interface does exactly one thing. If you have an interface that has a grab bag of functionality, that’s a warning sign.”

The problem

What are the things a Gtk.TreeModel are or represent?

  • It’s something that is iterable
  • It’s something that is an iterator
  • It’s apparently something that has columns, which should have been at the View’s side of the story
  • It’s something that can be a tree
  • It’s something that emits row changes

That’s not one thing, and therefore we have a warning sign. If I count it correctly that’s at least five things, so that’s a big warning sign.

I’m sure I can come up with a few other things that a Gtk.TreeModel actually represents. For example its unref_node and ref_node make me think that it’s a garbage collector or something, too.

This is absolutely not good. I believe it is what makes the interface shockingly complicated. Because none of those five things can be made reusable this way.

What I think would be the right way

A prerequisite for this, and presumably also the reason why Gtk+ developers decided to do Gtk.TreeModel the way they did it a few years ago, is a collection framework.

Sadly is this proposal being ~ignored by the current GLib maintainers. Understandable because everybody is overloaded and busy, but in my opinion it’s nonetheless blocking us from heading in the right direction.

There are by the way quite a lot of other reasons mentioned on the proposal. This is just one of them.

interface GLib.Iterable {
	Iterator iterator();
}

interface GLib.Iterator {
	bool next ();
	object current;
}

Next would be recursive iterators or trees. There are many ways to represent these, but I’ll just take a simple route. Remember that when picking an API design, the most simple idea is often the most right one. But yeah, you can probably improve this.

interface GLib.TreeIterable : GLib.Iterable {
	GLib.TreeIterable get_children ();
	int n_children;
	bool has_child (GLib.TreeIterable e);
	GLib.TreeIterable parent;
}

In Gtk+ we would have the view, of course. It would hold the columns, as it should be.

class Gtk.TreeView {
	int n_columns;
	GLib.Type get_column_type (int n);
	GLib.TreeModel model;
	Gtk.ColumnBinding binding;
	Gtk.TreeView (GLib.TreeModel m);
	GLib.ColumnBinding column_binding;
}

We don’t have guaranteed introspection in Gtk+. To do the binding between a column in the view and a property of an instance in the model we need some code. In Gtk.TreeModel this is the get_value function.

It shouldn’t be part of the Gtk.TreeModel: That way it ain’t reusable and will it require each person implementing a Gtk.TreeModel to reinvent the code.

abstract class GLib.ColumnBinding {
	abstract GLib.Value get_value (GLib.TreeModel model,
	                               GLib.TreeIterable e,
	                               int column);
}

Let’s have some concrete column bindings:

class Gtk.TreeStoreColumnBinding : GLib.ColumnBinding {
}

class Gtk.ListStoreColumnBinding : Gtk.TreeStoreColumnBinding {
}

If we do have introspection we can do the same thing .NET offers: Link up the column number with a property name that can be found in the type of the instances that the model holds.

class GI.IntrospectColumnBinding : GLib.ColumnBinding {
	void add_column (int column, string prop_name);
}

These wouldn’t change at all, except that they implement GLib.TreeModel instead of Gtk.TreeModel

class Gtk.TreeStore : GLib.TreeModel {
}

class Gtk.ListStore : GLib.TreeModel {
}

And then we are at Gtk.TreeModel, of course. Well just take everything that we don’t do yet. That’s the row change emissions, right? Personally I think rows are too specific. A model is something that can be iterated. Being iterable doesn’t mean that you have rows, it just means that you have things that the consumer, the view in a model’s case, can iterate to. Let’s call them nodes.

Gtk.TreePath sounds to me like serializing and deserializing a location. It’s nothing special, just a way to formulate pointing to a node in the tree. It’s the model that exposes this capability.

I’m not sure about flags. Maybe it should just be moved to Gtk.TreeView. I don’t get the point of the flags anyway. Both ITERS_PERSIST and LIST_ONLY sound like an implementation detail to me: not something you want to expose to the API anyway. But fine, for sake of completeness I’ll put it here.

interface GLib.TreeModel : GLib.TreeIterable {
	signal node_changed (GLib.TreeIterable e);
	signal node_inserted (GLib.TreeIterable e);
	signal node_deleted  (GLib.TreeIterable e);
	signal node_reordered (GLib.TreeIterable e);
	GLib.TreeModelFlags flags;
	GLib.TreePath get_path (GLib.TreeIterable e);
	GLib.TreeIterable get_node (GLib.TreePath p);
}

Who’ll start GLib 4.0? Let’s do this stuff while the desktop guys play with GNOME 3.0? Why not?

6 thoughts on “TreeModel ZERO, a taste of life as it should be”

  1. I like it. The next treeview *must* be designed around holding millions of items with bound memory usage and speed. Iterating the entire model when attached is unacceptable (like it is now). Everything lazy!

    Thanks for the post.

  2. Yes, being able to store millions of items efficiently would be great for the rare occasions when that happens.

    What I care about though is the API for developers and how ridiculous it is currently. I don’t want to have to care about iterators or store objects, I just want to say “here is my data, make a list” and get back to having fun!

  3. Some nits have to pick:
    1) TreeIterable should return Iterable as children, and not TreeIterables. Or am I missing something?
    2) TreeIterable and TreeModel are distinct, so both of these interfaces should require Iterable, but not each other. That way you get the LIST_ONLY flag by querying if TreeIterable was implemented.
    3) ITERS_PERSIST should be a requirement. A lot of the complexity of tree views currently comes from the fact that code wants to reference particular rows in the model, but cannot do so, because both iters and paths are not persistent. That’s why GtkTreeRowReference was invented.
    4) Current code now has 3 ways to reference rows: GtkTreeIter, GtkTreePath and the just mentioned GtkTreeRowReference. Is that really necessary?
    5) Your TreeIterable has an n_children property. For a lot of data (like a Tracker query ;)) you don’t know the number of results in advance. I’m not sure how/if you want to support that usecase.
    6) How does GtkTreeSortable fit into your design?

    And that’s just the first few things I came up with. ;)

  4. @Philip:
    looks like a very good start, please keep rocking on this ! :-)
    your proposed Gtk.TreeModel has both these, which I find confusing:
    Gtk.ColumnBinding binding;
    GLib.ColumnBinding column_binding;
    probably you mean only GLib.ColumnBinding, and some support stuff for mapping CellRenderers to column names / numbers ?

    AFAIK GLib 2.90 has not even been opened, so theoretically there would be time enough to polish these interfaces a bit and get them into GLib 3.0.
    Then we could also ship GTK+ with a simplified Gtk.TreeView2 (maybe call it Gtk.NodeView or something ?), and deprecate Gtk.TreeView but carry it around for the whole 3.x timeline. Gtk.TreeModel could implement the new interfaces but be supplemented over time by simpler implementations.

    Your GLib.TreeIterable interface strikes me as something you would want on the concrete Iterator, not as a subclass of Iterable, because you want to iterate over the children of the currently iterated-to row. So maybe it would better be named TreeIterator.
    Also, maybe get_children should return TreeIterator directly, instead of TreeIterable ? (The former would return another iterator, which should be enough; the latter would return “the node” in an Iterable form, which wouldn’t necessarily have an equivalent gobject class.)

    Maybe demanding that the rows (nodes ?) returned by a GLib.TreeIterator implement a simple property interface in the spirit of your Glib.ColumnBinding would be ok ? I’m thinking something like this:

    interface GLib.ColumnAccessor {
    GLib.Value get_value (int column);
    }

    We have enough introspection to check at runtime if this interface is implemented, and skip over the row if it’s not. This check might be too costly in real-world treeviews, though.
    Then again, just reusing the (overriable) GObject.get_property() class method might be completely enough. (Just do the mapping of property name to per-class property number at a higher level in Gtk.TreeView.)

    @Benjamin:
    agreed that the different iterator representations are the most horrible part of the API (possibly only fighting for 1st place with the whole column API).
    About making ITERS_PERSIST the default: maybe a looser guarantee would be enough, where iterators gain a is_valid property, or emit a signal when the row below their butt disappears.
    Then the new TreeView could still cache them all day long, and trying sane fallbacks when they invalidate.

    From the TreeModel API I fuzzyly remember that at least one representation of the Iterators was designed to be stored in a fixed-size space within TreeView, probably in an array. This is not something we can easily fullfil with a simplified implement-your-own-iterator API approach, but maybe that particular design constraint is just not that important.
    Iterators might have to be cloneable, though.

    Sorry for my long ramblings. :-)

  5. @Benjamin and pixelpapst: Yeah, I think all of your observations (from the both of you) are valid. As I wrote there are many ways to represent a tree and did I just take a simple route. Perhaps it’s indeed better to simply immediately return iterator and not iterable for the get_children. Best way to know is to write some code and see what works and what is needed & where. Gtk.ColumnBinding is of course wrong, should be GLib.ColumnBinding everywhere and I think the ColumnBinding should be solely at the View’s side, never at the Model (models don’t care about presentation of the data, only about the data).

    II have not thought (enough) about Gtk.TreeSortable yet. When properly iterable I think sorting should (if possible) happen at the source model instead of in a decorator, but I can see the need for such a Gtk.TreeSortable of course (for non-sortable source models).

    I would probably make GLib.TreeSortable an interface that can be implemented. And then have a wrapping GLib.TreeSortableWrap that implements it, and that wraps (decorates) non-sortable GLib.TreeModels by keeping a mapping of all its sorted nodes to the non-sorted nodes in the wrapped source model.

    As for pixelpapst’s suggestion to try to get this in in early current versions of GLib and Gtk+: it all depends on the decision to accept the proposal to have a collection framework in GLib. If this ain’t accepted, this kind of “doing it right” ain’t possible in a practical way.

Comments are closed.