Created attachment 275564 [details] [review]
Add GListModel

GListModel is an interface that represents a dynamic list of GObjects.
Also add GListStore, a simple implementation of GListModel that stores
all objects in memory.

Review of attachment 275564 [details] [review]:

::: gio/glistmodel.h
@@ +55,3 @@
+
+GLIB_AVAILABLE_IN_2_42
+guint                   g_list_model_get_n_items                       (GListModel *list);

So we assume it is always known how many items there are ?

@@ +58,3 @@
+
+GLIB_AVAILABLE_IN_2_42
+gpointer                g_list_model_get_item                          (GListModel *list,

If it is just meant to contain objects, why not return GObject* here ?

Also: no iters ? Sure it looks nice and simple now, but if you want to allow people to reimplement this in interesting ways...

(In reply to comment #2)
> So we assume it is always known how many items there are ?

Yes and no.

The exact answer depends on the exact interaction between model and view.

Consider that this API is non-blocking.  This restricts the sort of operations we can do.

We have the very simple case where the number of items is known and the view wants to know them (for showing a scrollbar say).

Then we have the easy case where the number of items is known but the view doesn't care (maybe listing out to stdout or something).  In this case, it is possible to skip the call to _get_n_items() and the view will return items until we get to the end.  When you request the nth item, you get NULL.

If we have a model based on a database cursor (ie: number of items not known in advance, but could be computed, but we prefer not to do the work "all at once") then we have a case where a view that doesn't call _get_n_items() is better.  It can call _get_item() for 0, 1, 2, 3, 4... etc. as the user scrolls and the cursor will be read a bit at a time.

Finally, we consider the case where fetching additional items is extremely expensive.  This is probably also the case where we may not know how many items there are, and the items available may change.  Think of a twitter client or something.  The best we can do here is to report the number of items that we know about and fetch more asynchronously when we get near the bottom (or the user hits a 'more' button).  Once we have more items we would emit a changed signal that new items are added at the end.

> @@ +58,3 @@
> +
> +GLIB_AVAILABLE_IN_2_42
> +gpointer                g_list_model_get_item                         
> (GListModel *list,
> 
> If it is just meant to contain objects, why not return GObject* here ?

Two reasons.  The first is that casts would be annoying here.  We have a fine tradition of using gpointer on GObject APIs where we may want to use the return value with pointers of specific object types [g_value_get_object(), _set_object(), even g_object_ref(), etc.].

Secondly: we explicitly consider that some day we may have things in here that are not objects.  The only reason we don't do that today is because it would be difficult to support with the current state of introspection.  It probably becomes possible to add other types later, however (and would work extremely nicely with Vala generics).

This probably seems scary from the standpoint of this being an object that always returns GObjects and is suddenly returning non-GObject but the user tends to get data from one place and put it into another -- it is their responsibility to know what is going on here.  Also: an API that today returns a GListModel with GObject-typed children is not suddenly going to start returning a model with non-GObject children.  Finally, there is the child type property that people can use to check for sanity...

(In reply to comment #3)
> Also: no iters ? Sure it looks nice and simple now, but if you want to allow
> people to reimplement this in interesting ways...

We considered this as well but concluded that we can just as well have a small 1-item cache on the get_item() call: we record the last-requested index and the GSequenceIter for it.  Changes invalidate.  If you ask for item i+1 then we can next() on the GSequenceIter to get O(1) instead of O(lgn) [or O(n) instead of O(nlgn) over all].

See also bug 560061 (GLib could use a collection API) and bug 639908 (Missing support for generic containers). (In particular, Matthias's question about iterators made me think of the collection API bug.)

(In reply to comment #4)

> This probably seems scary from the standpoint of this being an object that
> always returns GObjects and is suddenly returning non-GObject but the user
> tends to get data from one place and put it into another

that's not the only thing that's scary: you'd also break the introspected ABI if you decided to return something else.

right now, we'd have to annotate the returned value of this function with (type GObject) to let language bindings manage the memory appropriately; if this function suddenly started returning a boxed type, or any other random memory region, the annotation would not hold any more, which would mean bindings would break.

even if it's (transfer none), language bindings need to know the lifetime rules of the returned value, in case the user keeps a reference to it.

I know I'm terribly late, and it's my fault for not coalescing my gut feelings in this bug before, but I'm not sold on the "GListModel/GListStore" naming scheme. I know it's something that reminds us of the equivalent classes in GTK, but:

  - given the API scope of GListModel, something like GController would probably be more apt — a data type that notifies of changes *of* a collection of objects, as opposed of changes *in* a collection of objects
  - GListModel betrays the implementation detail; what if I wanted to have my own ArrayController that implemented GListModel? what if I wanted to have an HashController instead?

GListStore could probably be named GObjectList, but GListModel should probably be renamed.

(In reply to comment #4)
> Secondly: we explicitly consider that some day we may have things in here that
> are not objects.  The only reason we don't do that today is because it would be
> difficult to support with the current state of introspection.

It ought to work fine with boxed types? (And FTR, NetworkManager has several list-of-boxed properties/return-values in addition to its list-of-object ones.)

Review of attachment 275564 [details] [review]:

::: gio/gliststore.c
@@ +323,3 @@
+                     guint       position,
+                     guint       removed,
+                     guint       added,

Please change the order and rename these arguments to:

  removals, additions, n_additions

Created attachment 287807 [details] [review]
Add GListModel

Thanks for catching the unfortunate naming. I went with

  n_removals, additions, n_additions.

Comment on attachment 287807 [details] [review]
Add GListModel

Should this be in libgobject rather than libgio?

Also, it would be very very very easy to make GListModel support boxed types as well as GObjects:

  - * #GListModel is a dynamic list of #GObjects.
  + * #GListModel is a dynamic list of objects or boxed structures of a
  + * type registered with GLib.

  - * Returns: (transfer full) (allow-none) (type GObject): the item at
  + * Returns: (transfer full) (allow-none): the item at

I think that's the entire diff. I guess the down side of this would be that without the "(type GObject)" annotation, bindings would *require* explicit support for GListModel in order for it to be at all usable, whereas with that annotation, you get at least awkward support for it for free...

Or maybe we could just have a separate GBoxedListModel with the same API, but without the type guarantee? (In which case maybe this one should be GObjectListModel?)



>+ * Implementations may not emit this signal in response to a call to the
>+ * #GListModel API.

"May not" could mean either "possibly won't" or "aren't allowed to". "Must not" would be clearer.

>+struct _GListStore
>+{
>+  GObject parent;
>+
>+  GType item_type;
>+  GSequence *items;
>+};

GSequence seems like a strange choice for this...

Review of attachment 287807 [details] [review]:

::: docs/reference/gio/gio-sections.txt
@@ +4252,3 @@
+g_list_model_new
+<SUBSECTION>
+g_list_model_get_type

Shouldn’t this be in <SUBSECTION Private>?

@@ +4257,3 @@
+g_list_model_get_item
+g_list_model_items_changed
+<SUBSECTION>

<SUBSECTION Standard>?

@@ +4280,3 @@
+#define G_TYPE_LIST_STORE            (g_list_store_get_type ())
+#define G_LIST_STORE(o)              (G_TYPE_CHECK_INSTANCE_CAST ((o), G_TYPE_LIST_STORE, GListStore))
+#define G_IS_LIST_STORE(o)           (G_TYPE_CHECK_INSTANCE_TYPE ((o), G_TYPE_LIST_STORE))

Those #defines should not be there.

::: gio/glistmodel.c
@@ +30,3 @@
+ * @include: gio/gio.h
+ *
+ * #GListModel is a dynamic list of #GObjects.

This documentation should probably give some hints about what the interface is intended for, when it should be used, and what implementations of it are recommended.

@@ +41,3 @@
+ * The virtual function table for #GListModel.
+ *
+ * Since: 2.42

2.44 now.

@@ +52,3 @@
+   * GListModel::items-changed
+   * @list: the #GListModel that changed
+   * @position: the position at which @list changed

0-based index? Or is that stating the obvious?

@@ +115,3 @@
+ *
+ * Get the item at @position. If @position is greater than the number of
+ * items in @list, %NULL is returned.

0-based index?

@@ +121,3 @@
+ *
+ * Returns: (transfer full) (allow-none) (type GObject): the item at
+ * @position.

(allow-none) should now be (nullable).

::: gio/glistmodel.h
@@ +48,3 @@
+};
+
+GLIB_AVAILABLE_IN_2_42

GLIB_AVAILABLE_IN_2_44.

::: gio/gliststore.c
@@ +30,3 @@
+ *
+ * #GListStore is a simple implementation of #GListModel that stores all
+ * items in memory.

If you continue using GSequence, maybe make it clear in this documentation that G*List*Model does not actually use a linked list, and hence has different performance characteristics.

@@ +60,3 @@
+  GListStore *store = G_LIST_STORE (object);
+
+  g_sequence_free (store->items);

This needs to clear store->items, in case dispose() is called twice.

@@ +118,3 @@
+   * GListStore:item-type:
+   *
+   * The type of items contained in this list store.

You should mention that this must be GObject or a subtype of GObject.

@@ +174,3 @@
+/**
+ * g_list_store_new:
+ * @item_type: the #Gtype of the items that will be stored in the list

Mention that this must be a GObject or subtype, or link to the #GListStore:item-type documentation which mentions this.

@@ +201,3 @@
+ *
+ * Inserts @item into @store at @position. @item must be of type
+ * #GListStore:item-type.

What happens if @position is off the end of the store?

@@ +257,3 @@
+ * @position: the position of the item that is to be removed
+ *
+ * Removes the item from @store that is at @position.

What happens if no item exists at @position?

@@ +306,3 @@
+ * @position: the position at which to make the change
+ * @n_removals: the number of items to remove
+ * @additions: the items to add

Could do with a ‘(array length=n_additions)’ annotation.

@@ +310,3 @@
+ *
+ * Changes @store by removing @n_removals items and adding @n_additions
+ * items to store. @additions must contain @n_additions items of type

‘to store’ → ‘to the store’

@@ +311,3 @@
+ * Changes @store by removing @n_removals items and adding @n_additions
+ * items to store. @additions must contain @n_additions items of type
+ * #GListStore::item-type.

#GListStore:item-type.

Review of attachment 287807 [details] [review]:

::: gio/glistmodel.c
@@ +127,3 @@
+gpointer
+g_list_model_get_item (GListModel *list,
+                       guint       position)

As discussed, this should be g_list_model_dup_object() or g_list_model_get_object() (depending on your dup vs get preferences). It should return a gpointer which is always a GObject*. That way, when we add generic type support, we can deprecate g_list_model_dup_object() and add g_list_model_dup_item().

::: gio/gliststore.h
@@ +31,3 @@
+#define G_TYPE_LIST_STORE            (g_list_store_get_type ())
+#define G_LIST_STORE(o)              (G_TYPE_CHECK_INSTANCE_CAST ((o), G_TYPE_LIST_STORE, GListStore))
+#define G_IS_LIST_STORE(o)           (G_TYPE_CHECK_INSTANCE_TYPE ((o), G_TYPE_LIST_STORE))

Use G_DECLARE_FINAL_TYPE. \o/

What are the thread guarantees about this? What thread is the change signal emitted on?

I worry a bit about the using of offsets in the APIs. There is a lot of risk of accidentally creating O(n^2) code when iterating over such APIs.  On the other hand its very simple to use, easy to bind etc. But we should at least do the cache-of-one thing for the liststore so that forward and backwards iteration is efficient.

It also means whenever anything is inserted/removed you have to very carefully update all your existing widgetry so that they know the index of the item they refer to. Some kind of persistent row ids would make that a lot easier.

How is sorting supposed to work in this model? I can see having the list model itself sort the underlying data before exposing it, but what if you have sort operations in your list UI (say you click on a column to specify sort order). Are you supposed to then change the sort order of the model? What if some other view is also showing the model in a different order?

Also, wouldn't it be nice to have some kind of change event for a node being moved in the list, rather than having to fake that via remove+add.

I have a vague worry about the sync change signal. In order to properly keep a view in sync with changes to the model you have to update your ui directly in the callback, rather than coalescing such changes, or things get really tricky with the indexes in the list not matching the ones used in the view. On the other hand, I don't really have a better alternative.

(In reply to comment #11)
> (From update of attachment 287807 [details] [review])
> Should this be in libgobject rather than libgio?

Ryan made the same point, but we decided against it. libgobject feels like it should only contain the basics for a type system.

> Also, it would be very very very easy to make GListModel support boxed types as
> well as GObjects:
> 
>   - * #GListModel is a dynamic list of #GObjects.
>   + * #GListModel is a dynamic list of objects or boxed structures of a
>   + * type registered with GLib.
> 
>   - * Returns: (transfer full) (allow-none) (type GObject): the item at
>   + * Returns: (transfer full) (allow-none): the item at
> 
> I think that's the entire diff. I guess the down side of this would be that
> without the "(type GObject)" annotation, bindings would *require* explicit
> support for GListModel in order for it to be at all usable, whereas with that
> annotation, you get at least awkward support for it for free...

Boxed types is something we want to support eventually, but we don't want to add explicit support for GListModel to bindings. Probably won't happen until GType grows support for generics.

I'm about to rename g_list_model_get_item() to _get_object() for the time being. This way we have the object-based model now and keep the "good name" for when we support more types later.

> >+ * Implementations may not emit this signal in response to a call to the
> >+ * #GListModel API.
> 
> "May not" could mean either "possibly won't" or "aren't allowed to". "Must not"
> would be clearer.

Indeed, thanks.

> >+struct _GListStore
> >+{
> >+  GObject parent;
> >+
> >+  GType item_type;
> >+  GSequence *items;
> >+};
> 
> GSequence seems like a strange choice for this...

It was a GPtrArray initially. GSequence is a trade-off for the case I think is the most common: a smallish list that gets insertions and removals at random positions.

I'm about to add a cache of the last accessed GSequenceIter to the store so that iterating the model in-order is faster.

Created attachment 295687 [details] [review]
Add GListModel

Add a bit more documentation, fixup annotations and version macros, cache the
last used iter in GListStore, and use G_DECLARE_TYPE.

Thanks for the reviews!

Review of attachment 295687 [details] [review]:

Review round #2.

::: docs/reference/gio/gio-sections.txt
@@ +4284,3 @@
+g_list_store_new
+<SUBSECTION>
+g_list_store_get_type

This is listed here and in <SUBSECTION Private>. I guess it should just be in the latter.

@@ +4285,3 @@
+<SUBSECTION>
+g_list_store_get_type
+g_list_store_new

Same here; it’s listed above too. This occurrence should probably be removed.

::: gio/glistmodel.c
@@ +1,2 @@
+/*
+ * Copyright © 2014 Lars Uebernickel

It’s 2015 now!

@@ +41,3 @@
+ * g_list_model_get_length() returns the number of items in the list and
+ * g_list_model_get_item() returns an item at a (0-based) position. In
+ * order to allow implementations to calculate the length list lazily,

‘calculate the list length’

@@ +50,3 @@
+ *
+ * #GListModel emits the GListModel::items-changed signal when items are
+ * added or removed from the list. Use GObject::notify to find out about

‘#GObject::notify’.

@@ +71,3 @@
+{
+  /**
+   * GListModel::items-changed

Needs a trailing colon.

@@ +98,3 @@
+ *
+ * Gets the type of the items in @list. All items returned from
+ * g_list_model_get_type() are of that type.

‘are that type or a subtype’?

@@ +160,3 @@
+ *
+ * This function is the same as g_list_model_get_item(), except that it
+ * is annotated as returning a #GObject and throws an error if it isn't.

I would say ‘emits a critical warning’ instead of ‘throws an error’, which implies a GError to me.

@@ +163,3 @@
+ * It mainly exists for bindings.
+ *
+ * Returns: (transfer full) (allow-none) (type GObject): the object at

(allow-none) → (nullable)

::: gio/gliststore.c
@@ +235,3 @@
+ * Inserts @item into @store at @position. @item must be of type
+ * #GListStore:item-type and @position must be smaller than the length
+ * of the list.

‘@position must be smaller than the length of the list, or equal to it to append.’

@@ +281,3 @@
+
+  n_items = g_sequence_get_length (store->items);
+  g_sequence_append (store->items, g_object_ref (item));

This should invalidate the cache.

@@ +331,3 @@
+  n_items = g_sequence_get_length (store->items);
+  g_sequence_remove_range (g_sequence_get_begin_iter (store->items),
+                           g_sequence_get_end_iter (store->items));

This should invalidate the cache. And cache state vs. mutations of the GListStore should probably be added as unit tests.

::: gio/gliststore.h
@@ +29,3 @@
+G_BEGIN_DECLS
+
+G_DECLARE_FINAL_TYPE(GListStore, g_list_store, G, LIST_STORE, GObject)

Needs a GLIB_AVAILABLE_IN_2_44.

(In reply to comment #17)
> + * Copyright © 2014 Lars Uebernickel
> 
> It’s 2015 now!

Also, drop the "©". "©" is an abbreviation for "Copyright". Saying "Copyright © 2015" is equivalent to saying "Copyright Copyright 2015".</pet-peeve>

Created attachment 295755 [details] [review]
Add GListModel

Update with Philip's and Dan's suggestions and fixes. Thanks again for
reviewing.

Will this api let us define our own model like TreeModel let us?
(and provide a basic list based implementation)

Review of attachment 295755 [details] [review]:

::: gio/glistmodel.c
@@ +54,3 @@
+ * #GListModel emits the GListModel::items-changed signal when items are
+ * added or removed from the list. Use #GObject::notify to find out about
+ * changes in the list items itself.

I'd still like some thread related verbosity here. Something like:
Note: The notify signal will be emitted on the thread that maintains the list model, which means the consumer of the model must be on the same thread for everything to work properly.

::: gio/glistmodel.h
@@ +33,3 @@
+
+#define G_TYPE_LIST_MODEL         (g_list_model_get_type ())
+#define G_LIST_MODEL(o)           (G_TYPE_CHECK_INSTANCE_CAST ((o), G_TYPE_LIST_MODEL, GListModel))

Wish we had G_DECLARE_INTERFACE here.

::: gio/gliststore.c
@@ +70,3 @@
+{
+  store->last_iter = NULL;
+  store->last_position = -1;

Don't invalidate if position > last_position.
(For instance, if appending items)

::: gio/gliststore.h
@@ +43,3 @@
+void                    g_list_store_insert                             (GListStore *store,
+                                                                         guint       position,
+                                                                         gpointer    item);

It would be nice to have insert_stored (and the corresponding wrapper for g_sequence_sort_changed).

Maybe even g_list_store_sort().

(In reply to comment #20)
> Will this api let us define our own model like TreeModel let us?
> (and provide a basic list based implementation)

Yes. GListModel is a list interface (no trees yet) and GListStore is a simple implementation that stores objects in memory.

(In reply to comment #21)
> Review of attachment 295755 [details] [review]:
> 
> ::: gio/glistmodel.c
> @@ +54,3 @@
> + * #GListModel emits the GListModel::items-changed signal when items are
> + * added or removed from the list. Use #GObject::notify to find out about
> + * changes in the list items itself.
> 
> I'd still like some thread related verbosity here. Something like:
> Note: The notify signal will be emitted on the thread that maintains the list
> model, which means the consumer of the model must be on the same thread for
> everything to work properly.

The last version of the patch contains considerably more documentation (written under water). Ryan says he'll check if threading is covered and upload it in a bit.

> ::: gio/glistmodel.h
> @@ +33,3 @@
> +
> +#define G_TYPE_LIST_MODEL         (g_list_model_get_type ())
> +#define G_LIST_MODEL(o)           (G_TYPE_CHECK_INSTANCE_CAST ((o),
> G_TYPE_LIST_MODEL, GListModel))
> 
> Wish we had G_DECLARE_INTERFACE here.

Yes!

> ::: gio/gliststore.c
> @@ +70,3 @@
> +{
> +  store->last_iter = NULL;
> +  store->last_position = -1;
> 
> Don't invalidate if position > last_position.
> (For instance, if appending items)

Ok.

> It would be nice to have insert_stored (and the corresponding wrapper for
> g_sequence_sort_changed).
> 
> Maybe even g_list_store_sort().

Neat idea. Figuring out how to send change signals efficiently when calling g_list_store_sort() might be tricky.  I'll keep it in mind, but don't think this should block the first landing.

Attachment 295755 [details] pushed as b69beff - Add GListModel

Pushed a final version of the patch that larsu and I finished up on the
eurostar (plus a couple of Alex's suggestions incorporated).  Let's
discuss further improvements in other bugs.

(In reply to comment #23)
> (In reply to comment #21)
> 
> > It would be nice to have insert_stored (and the corresponding wrapper for
> > g_sequence_sort_changed).
> > 
> > Maybe even g_list_store_sort().
> 
> Neat idea. Figuring out how to send change signals efficiently when calling
> g_list_store_sort() might be tricky.  I'll keep it in mind, but don't think
> this should block the first landing.

g_list_store_sort() is a bit tricky, yes. But insert_sorted() should be basically trivial (and still quite useful).