Oh shit. You are right, and it's my fault.

Created attachment 333286 [details] [review]
patch: Gtk::TreeNodeChildren: Fix the reverse iterator

This patch is a solution along track 1 in comment 0:

> 1) make your own reverse_iterator that somehow avoids this kind of thing
>   - doesn't solve the real problem, since a similar thing can creep up in
>     other situations

I don't think it breaks ABI. Since the modified part of the code consists of
templates, it's not in the ABI.

I haven't tried to fix the iterators for the GLIBMM_HAVE_SUN_REVERSE_ITERATOR
case. I don't know how Sun's iterators work, and I don't know if this bug
applies to them.

I agree that track 2 (make a _real_ iterator) would be a better solution, but it
would require a much more extensive modification that would break ABI and API.
Unless it was added as new classes, and the present TreeIter and TreeRow were
kept, but deprecated.

Do you think my patch is a good enough fix?

(In reply to Kjell Ahlstedt from comment #2)
> Created attachment 333286 [details] [review] [review]
> patch: Gtk::TreeNodeChildren: Fix the reverse iterator
> 
> This patch is a solution along track 1 in comment 0:
> 
> > 1) make your own reverse_iterator that somehow avoids this kind of thing
> >   - doesn't solve the real problem, since a similar thing can creep up in
> >     other situations
> 
> I don't think it breaks ABI. Since the modified part of the code consists of
> templates, it's not in the ABI.
I disagree. Imagine a shared library A compiled against the old version of the headers, which exposes some interface (e.g. a function) taking the reverse iterator. Then, let's have a library B, which calls that function, but is compiled with a newer version of the headers. There will be a mismatch between the interface of the function when compiled as a part of libA and libB.

That said, I don't think this is a very important issue, as the original class was so broken that probably noone used it, and if he did, ABI mismatch would be the least of his problems.

> 
> I haven't tried to fix the iterators for the GLIBMM_HAVE_SUN_REVERSE_ITERATOR
> case. I don't know how Sun's iterators work, and I don't know if this bug
> applies to them.
> 
> I agree that track 2 (make a _real_ iterator) would be a better solution,
> but it
> would require a much more extensive modification that would break ABI and
> API.
> Unless it was added as new classes, and the present TreeIter and TreeRow were
> kept, but deprecated.
> 
> Do you think my patch is a good enough fix?

It's a step in the right direction. However, I am not too fond of the fact that you have a mutable field there. For one, it breaks thread-safety of the class (normally doing an iterator dereference from multiple threads would be perfectly safe, but now it isn't, since both will be writing to the field. I don't really have a good suggestion how to fix that, short of putting a mutex around that.

>> I don't think it breaks ABI.
>I disagree. Imagine a shared library A .....

You're right. I didn't think far enough. My patch doesn't seem to break ABI of
gtkmm (I've checked with the nm command), but it can break ABI of other
libraries. We've seen such things happen when someone changed the name of
struct nil in libsigc++. It didn't break ABI of libsigc++, but it did break ABI
of gtkmm and several other libraries. That name change had to be reverted.

I agree with you that an ABI break would probably be acceptable in this case.

> it breaks thread-safety of the class ..... putting a mutex around that.

You're right again. Usually you'd expect const methods (like operator*() and
operator->()) to be thread-safe. Perhaps a mutex is acceptable here. I suppose
reverse iterators are not heavily used, not even if they work as intended.

I got the idea of a mutable iterator deref_tmp from the C++ draft standard
N3242:

  24.5.1.3 reverse_iterator operations
  24.5.1.3.4 operator*

  reference operator*() const;

  deref_tmp = current;
  --deref_tmp;
  return *deref_tmp;

  [ Note: This operation must use an auxiliary member variable rather than a
  temporary variable to avoid returning a reference that persists beyond the
  lifetime of its associated iterator. (See 24.2.) — end note ]

I don't understand the note, but never mind. In later drafts (e.g. N4296),
std::reverse_iterator<> does not contain deref_tmp. The matter is also discussed
in the gcc bug http://gcc.gnu.org/PR51823.


Concerning your very reasonable suggestion to make TreeIter a _real_ iterator,
I think that's much more complicated than I expected before I looked closer into
the TreeIter and TreeModel classes.

In normal cases, such as std::vector<T> and std::vector<T>::iterator, there is
a container, std::vector<T>. The container contains elements of type T. An
iterator can provide a reference or a pointer to an element in the container.
The elements exist and are accessible regardless of the iterator. A pointer
returned from the iterator continues to be valid even if the iterator is
destroyed, provided the container is not (too much) changed.

The containers that implement GtkTreeModel, such as GtkTreeStore and
GtkListStore, don't behave quite like that. You might say that GtkTreeIter _is_
the pointer to the element in the GtkTreeModel. It's not very nice that
Gtk::TreeRow is a subclass of Gtk::TreeIter, but I think it's hard to avoid that
they have a common base class where a GtkTreeIter object and a GtkTreeModel*
pointer or Gtk::TreeModel* pointer are stored.

See also bug 134520, where the lack of a real const_iterator is discussed.
There is no const correctness in TreeIter and TreeRow.

I agree with your analysis. Unfortunately I do not see a reasonable way out right now.

Created attachment 334544 [details] [review]
patch: Gtk::TreeNodeChildren: Fix the reverse iterator

On second thought I've come to the conclusion that a mutex in ReverseTreeIter
would not make its operator*() and operator->() thread-safe.

Consider this case: Thread 1 calls operator*(). When it has finished, and the
mutex has been released, but before the returned reference has been used e.g. in
a call to gtk_tree_model_get_value(), thread 1 is interrupted by thread 2.
Thread 2 calls the same reverse iterator's operator*(). In the middle of
operator*(), e.g. between 
  deref_tmp = this->base();
and
  return *--deref_tmp;
thread 2 is interrupted, and thread 1 is resumed.

I think the solution in my latest patch is more thread-safe.

  Iterator local_deref_tmp = this->base();
  --local_deref_tmp;
  deref_tmp = local_deref_tmp;
  return *deref_tmp;

It's still possible that it will break ABI in modules that use gtkmm. Since the
present reverse iterator is totally useless, that's perhaps acceptable.
Murray's opinion would be appreciated.

(In reply to Kjell Ahlstedt from comment #6)
> Created attachment 334544 [details] [review] [review]
> patch: Gtk::TreeNodeChildren: Fix the reverse iterator
> 
> On second thought I've come to the conclusion that a mutex in ReverseTreeIter
> would not make its operator*() and operator->() thread-safe.
> 
> Consider this case: Thread 1 calls operator*(). When it has finished, and the
> mutex has been released, but before the returned reference has been used
> e.g. in
> a call to gtk_tree_model_get_value(), thread 1 is interrupted by thread 2.
> Thread 2 calls the same reverse iterator's operator*(). In the middle of
> operator*(), e.g. between 
>   deref_tmp = this->base();
> and
>   return *--deref_tmp;
> thread 2 is interrupted, and thread 1 is resumed.
Agreed. That is indeed a problem.

> 
> I think the solution in my latest patch is more thread-safe.
> 
>   Iterator local_deref_tmp = this->base();
>   --local_deref_tmp;
>   deref_tmp = local_deref_tmp;
>   return *deref_tmp;
This is probably *more* thread safe, but I most emphasize the "more" part, because it is still not 100% ok. You still have the issue that one thread is using the value *deref_tmp (which is the same as deref_tmp) and another thread is updating it (deref_tmp = local_deref_tmp). This *may* be mitigated by the fact that you are overwriting deref_tmp with the same value, but how safe is that depends on the details of the implementation of operator=() of the underlying iterator. However, in any case, you will still technically have a data race, as you have overlapping reads and writes to the same memory. How safe is that might depend on the hardware it is run on.

So, I'd still like to see something in the style of std::call_once there to make sure the variable is only updated once.


The other option I see is just making sure there are no mutating operations in operator*() by moving them to the preceding mutable operation. For example, it could be something along the lines of:

iterator iterator::operator++() {
  --this->base();
  if (! is_begin_iterator(this->base()))
    deref_tmp == std::prev(this->base());
  return *this;
}

reference iterator::opreator*() {
  return *deref_tmp; // the value is already ready
}

All other mutating operations would be implemented in a similar way. The tricky part there is the is_begin_iterator function. Right now I do not see any other way to implement it other than by keeping a copy the container's begin() iterator (*), which is a bit of a nuissance, but I think we're way past that point now..

(*) Could it be possible to extract that information somehow via C glib api ? I don't know.. it's been a long time since I've touched that...

Isn't this thread-safety issue becoming unreasonably complicated? How important
is it that the reverse iterator's operator*() is thread-safe? After all most
of gtk+ and gtkmm is not thread-safe. An alternative could be to document that
operator*() and operator->() are not 100% thread-safe.

Another "solution" could be to remove TreeNodeChildren::reverse_iterator.
It has never been useful, and probably very few people have even noticed that.
If you need to iterate in reverse, often you can do it with a normal (forward)
iterator and operator--() instead of a reverse_iterator and operator++(), even
though it might be a bit awkward. We could deprecate TreeNodeChildren::
reverse_iterator now, and remove it in gtkmm 4, to avoid an ABI break.

Created attachment 334912 [details] [review]
patch: Gtk::TreeNodeChildren: Deprecate the reverse iterator

This is what I recommend, deprecating the reverse iterator. I don't think it's
useful enough to justify a rather complicated fix.

Unless someone objects soon, I'll push this patch.

Sounds reasonable, although I am not even using gtkmm at the moment, so I don't think I get a vote. :)

TreeNodeChildren::reverse_iterator has been deprecated.