Re: Proposal for a collection API in glib

[Jürg Billeter <j bitron ch>]

Hi Havoc,

On Thu, 2008-07-17 at 13:37 -0400, Havoc Pennington wrote:
> 2) Another idea would be an equivalent to registering boxed types:
> 
> g_iterator_type_register_static(const char *name, GBoxedCopyFunc
> boxed_copy, GBoxedFreeFunc boxed_free, GIteratorNextFunc
> iterator_next, GIteratorGetFunc iterator_get);
> 
> This would allow language bindings to generically manipulate custom
> iterator types like TextIter and TreeIter, without making things a
> pain in C and while keeping things lightweight. And without
> redoing/breaking TreeModelIter and TextIter and all the other existing
> examples you mention.

One issue I see with this approach is that new libraries in C still have
to invent their own interfaces for collections, as GList is certainly
not suitable for every situation, e.g. when using lazy loading.

They could register their collection interfaces, which helps for
language bindings, but we'd still not have a real collection API that
libraries can use.

However, I agree that we certainly should support iteration over GLists
with the new API, building such a bridge should be possible with almost
any approach we take, though.

> Why explore alternate ideas? Some downsides to GIterator-as-gobject:
> 
> * GObject is pretty heavyweight for something like this, and moreover
> right now libglib doesn't depend on libgobject

I certainly understand this point as for example valac spends most of
the compile time creating new GObjects. However, I think there is still
room for improvement without dropping the idea of using interfaces for
collections.

There are two objects involved when iterating over a collection: the
collection and the iterator. In libgee, both are GObjects, which might
really be an overkill.

One possibility would be to drop the GObject prerequisite in the
interfaces, i.e. allow types like GstMiniObject to implement the
collection interface. This would speed up object creation quite
significantly (by factor 5, iirc), and still have all the interface
features.

The major issue I see with this approach is that you can't just use the
usual g_object_ref/unref as that's only valid for GObjects. Possible
solutions for this problem:
      * add a new fundamental classed type to GLib, either something
        like GstMiniObject or a more concrete GCollection, however, this
        makes it impossible for full GObjects to implement the same
        interface
      * add virtual functions for ref/unref to the interface
      * move reference counting from GObject down to GTypeInstance, not
        possible for GLib 2.x, and might drag too much from GObject to
        GTypeInstance, not sure

If this is still not performing well enough, we could keep the interface
for the collection but use a stack-allocated struct like GtkTreeIter for
the iterator, so that we only need a heap object for the collection.

> * the need to unref the iterator is onerous for C programmers using iterators

Freeing a GList is certainly more complex and error-prone than unrefing
a GObject-based collection, as you have to take care of the elements
when freeing a GList. I consider this a major drawback of GList, not
only for language bindings, also when used in C.

For the iterator itself, we certainly could switch to a stack-allocated
struct, as noted above for performance reasons. However, for collections
unref makes it a lot easier, in my opinion.

> * the need to subclass a GObject is onerous for C programmers creating iterators

Not everyone needs to implement their own collection and iterator class.
Many libraries and applications will probably work fine with something
like GeeArraList if that'd be in GLib.

The main point is to enable developers to implement their own
collections if they have specific needs. The interface approach allows
this without breaking the interface, as it doesn't expose implementation
details as is the case when using GLists.

You also have to subclass a GObject in GTK+ if you write your own
widget, however, many applications don't need to.

> * as Owen mentioned long ago when this was already discussed, we'd end
> up duplicating bunches of APIs just to make them use iterators instead
> of whatever they use now - this is both bloat and confusing. It would
> not be realistic to ever deprecate walking GList etc. - the iterator
> replacement is much less convenient, and there's way, way, way too
> much code using GList already. You can't deprecate something that
> touches this much code.

I agree, however, there are already many libraries that don't use GList
for various reasons and implement their own iterator interfaces. Moving
such an iterator interface to GLib would at leasts prevent the ongoing
fragmentation in that area. Also, as I already wrote above, we certainly
want to build a bridge between GList and the new iterator interface.

Jürg