Re: [Boost-users] [Multi-Index] crash on invariant_() violation

Subject: Re: [Boost-users] [Multi-Index] crash on invariant_() violation
From: joaquin_at_[hidden]
Date: 2009-04-03 08:21:34

Hi Neil,

I'm answering your two posts together.

Neil Hunt escribió:
> Just weighing in here with a related question.
>
> But first to say: I find multi-index to be invaluable. So thanks for a 
> great library.

Thank you! It's thrilling to know that one's work is helpful to others.

> In my code, the objects I am indexing against are altered elsewhere, and
> then my index owning code is notified. At this point, the index owning 
> code
> calls:
>
> index.modify( index_iterator, NoOperationFunctor() );
>
> That is, on the assumption that the modify function has no knowledge
> of what changes the functor are making, it must re-evaluate all indices.
> Therefore, it doesn't matter if the change is made inside the modify 
> function
> as long as modify is called.
>
> (So, this statement from above does not appear strictly true:
> "Key modification has to be done via modify() so as to give the 
> container a
> chance to reindex elements.")

You're basically relying on undefined behavior: once you've broken the
container's invariant there's no formal guarantee that you can restore it:
in this particular case you're lucky that modify() with a dummy functor does
the job, but the implementor could have decided to, say, check the invariant
inside modify() before applying the functor and trigger an assertion.
More convoluted scenarios are also conceivable --for instance, iterator
copying relying on invariant validity.

I'm not saying that what you're doing is risky --in fact it works and it'll
continue to do in the future, but it's non-documented behavior. More
on invariant breaking below.

> Because (in my case) the change is made elsewhere, I am calling modify 
> with
> a functor that does nothing.
>
> In my particular case, I can guarantee that change made elsewhere won't
> affect the index that I use to find the iterator to pass to modify.
>
> This may seem a weird scenario, but it also seems weird that I have to 
> call
> modify with a no-op functor. Is it possible/desirable to add a simple
> update_indices( itor ) function?

I'm reluctant to add this for the reasons explained below, but you can
have it yourself as a free function template (untested):

struct do_nothing
{
  template<typename T>
  void operator()(T&)const{}
};

template<typename Index>
bool update_indices(Index& i, typename Index::iterator it)
{
  return i.modify(it,do_nothing);
}

> I guess more generally, why is this paradigm implictly disallowed?
>
> index_itor->value++;
> index.update_indices( index_itor );

Because between the first line and the second the container invariants
are broken and it is up to the user to follow the appropriate protocol
to restore them. There is no way the class design itself can force
this. There is an implicit constraint here that some other user (for
instance, the person maintaining your code) might not be aware of.
It is all too easy to forget about it and, say, do something fatal between
these two lines in a future revision of the code.

The utility of invariants comes precisely from this: the user can
rely on any moment on them to hold, no matter what the state of
the object is. This is reminiscent of an old pre-exception pattern by
which objects are first constructed and then initialized:

// pre-exception C++
MyClass x;
// x is in "uninitialized state"
bool success=x.init(...);

This is not optimum in terms of maintenance and forces the user
to follow a protocol that is not statically forced by the class design
itself. See the problems? If someone forgets to initialize the object
what we have will not behave as the MyClass interface advertises.

> While I can see the benefit of tying the modification to the 
> multi-index object
> via modify, there is no explicit reason that I can see why the above 
> is invalid
> (as per my perfectly working code that uses this paradigm).
>
> And "forcing" the user to use a functor to modify can introduce
> annoying code overhead.
>
> Don't get me wrong, I think that using modify with a functor is very 
> clear and
> helps prevent invalid indices. But, at the same time, it can be a pain 
> to write
> a functor. (Here's to C++0x lambda's).
>
> But in my case, where the code that modifies the object is unaware of
> multi-indices on that object, it is not feasible to use modify() to make
> the change.

I agree that in some situations using modify() can be difficult or 
impossible,
in this case at least you can resort to doing things the way you are now.
But I hope you understand I wouldn't like to promote this as a first-class
interface.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo