Re: rethinking GtkTreeModelSort

[jrb redhat com]

Havoc Pennington <hp redhat com> writes:

> >  In terms of space it requires 32
> > bytes per visible node (on IA32), though 8 of them could be cut down if
> > we decide to remove some unused pointers from GtkTreeIter (probably a
> > good idea.)  Not exactly trivial, but certainly a space-saver when
> > considring multiple models (see below).
> 
> The version in CVS looks a lot bigger than that to me... GtkTreeIter
> itself is 128 bytes, no?

Close.  128 bits (ia32 :-).  Though we could potentially cut it down to
12 bytes, as one of the pointers is just there as a precautionary
measure.

> >   Also, why is the ITERS_PERSIST
> > flag cheesy?  It's a performance saver, but GtkTreeModelSort should work
> > without it set (albeit less efficiently.)
> 
> Sufficiently less efficiently to be near-useless, right, otherwise we
> wouldn't have added that flag. ;-)

Depends on the size of the model, but to a certain extent, yeah.

> I think the flag is bad because it changes semantics substantially
> depending on what kind of model you have, when iterator semantics are
> already confusing, and after confusing iterator semantics it makes it
> hard for us to warn about misuse of iterators. So it's pretty
> suboptimal from that standpoint, IMHO.
> 
> Misusing iterators is quite easy, at least it is with the text
> widget. Once you start having signals and stuff, I've done it quite a
> few times just implementing the text widget itself.

Oh?  I think it's less of an issue (see below).  

> > I started working on a convenience function in gtktreemodelsort to do
> > this kind of thing.  Something like:
> >
> > static void
> > gtk_tree_view_set_sort_column (GtkSortView       *sort_view,
> >                                GtkTreeViewColumn *column,
> >                                GtkTreeModelSort  *sort,
> >                                GValueCompareFunc  func);
> >
> > Etc...
> >
> 
> Perhaps adding a set_sort_column method to the model is a bit nicer;
> even with TreeModelSort, the way we do sorting is to have one model
> per view. TreeModelSort just makes it easy to have a bunch of models
> that differ only in their sort, sharing a common model as the backend.
> So sort column is fundamentally a property of a single model. If it
> wasn't, you would need to pass a "view" argument to all the model
> methods, and get different order of iteration per-view. As it is, for
> a single model, there is only one ordering.
> 
> In principle you could have a model that shared the sort column
> between views, or you could have a bunch of custom GtkTreeModel that
> acted as views onto some application-specific child model. i.e. a sort
> model that chained to something other than another GtkTreeModel.
> 
> Ugh, confusing.

You wrote it that way. (-:

But you are right, there is a potential for complication here.  I think
that it is a product of the problem.

> Let's see: the summary is that the basic way you do sorting is to sort
> the model. The way you do a different sort for two different views is
> to create proxy models between the real data model and the views. The
> proxy models are themselves views for the real data
> model. TreeModelSort is a ready-made proxy model for the case where
> the real data model derives from GtkTreeModel. You could write your
> own custom proxy models for other kinds of real data model. These
> could conceivably use special knowledge about the real data model to
> be faster or use less memory.

Your model had better be a GtkTreeModel at some level, but I see your
point.

> Possible practical conclusions being:
> 
>  - TreeModelSort is not the only way to sort; ergo it doesn't have to
>    be efficient for all possible models, it just should be convenient
>    for the common cases. (e.g. I was thinking TreeModelSort eliminated
>    the ability to use an array for custom models with sorting; that's
>    not the case.)
> 
>  - we may as well have models support sorting directly via a
>    set_sort_column method, so we can set things up automatically,
>    because sort order is already a property of the model
> 
>    I guess "set things up automatically" just means that you can call:
>      gtk_tree_view_column_set_sort (column, 5, compare_func_can_be_null);
>    so that clicking that column sorts column 5 of the model. And
>    you could even default to something clever, maybe the
>    first column we're getting an attribute from.
> 
> This may have been obvious already, but I am just recently thinking
> about the issues.

Though I hadn't planned on letting you sort the basic models, that's
pretty much what I had in mind.  Sorting the basic models might be
useful.  I am a little wary of adding a "sort_column" function to
GtkTreeModel as it is optional, and only seems to buy us one less step
in setting up auto-sort.

> Another thought: it may well be useful to require explicit enabling of
> persistent iterators, and get safe iterators otherwise. Something
> like:
>   if (gtk_tree_model_request_persistent_iterators (model))
>     {
>      	/* can now use persistent iterators going forward */
> 
>     }
> 
> For the ListStore and TreeStore, basically this would turn off
> checking of the iterator stamps, and put the model in "persistent
> mode." In the non-sorted default case, you get safe iterators, but
> when you add TreeModelSort it automatically goes into unsafe mode for
> models that support it.

I don't understand this.  What's a safe iterator?  The whole point of
checking the stamps is to avoid looking at bogus memory, and it's
somewhat independent of whether or not the iters persist.  Having
ITERS_PERSIST simply means that an iterator is valid for the lifetime of
a node.  You won't be able to switch it on on the fly -- either the
model will use a format that can support it or it won't.  

> So we can maybe eliminate all the worries I had, namely we can allow
> efficient custom sorting, and we can keep safe iterators for unsorted
> tree/list store models. Also we should be able to set up
> clicking-causes-sort automatically. What do you think?

Sounds pretty sane, except for the part above.  Also, for what it's
worth, I think that we don't need to worry as much about the iterators
as with the text widget.  For most purposes, the iterators you need are
passed in the callbacks.  If you need to keep something around, there's
a good chance that keeping a path will be sufficient (and even
desireable.)  Additionally, all the models we provide should be
ITERS_PERSIST, so it's only a model that the user writes that requires
caution.

Thanks,
-Jonathan