[cfe-dev] [libc++] debug mode

[M.E. O'Neill]

I wrote:
>> let me outline how:
>> 
>> - For every container, associate a 64-bit tag (a.k.a. version stamp). 
>> 
>> - For every iterator, also associate a 64-bit tag.
>> 
>> - When you create a new container, just pick a random 64-bit value.
>> 
>> - When you create an iterator, copy the 64-bit tag from the associated container.  This represents the container/version the iterator belongs to.   Any access via the iterator checks that the tag of the iterator matches the tag of the container.  If it doesn't, BANG!
>> 
>> - When iterators are invalidated, generate a new tag for container. (For speed, you could just increment it, but the important point is that the value is a new and different one)

and Howard Hinnant replied:
> This is an interesting approach.  But one problem with it is that it only allows the system to invalidate all iterators referring to a container.  It can't invalidate a subset of them.  And we need to be able to invalidate subsets of iterators (e.g. during vector::erase).
> 
> Or have I missed something?

As outlined, yes, I was doing all-iterator invalidation, as happens in std::string, because that's simpler and quick to explain (and I've experience implementing it!).

But I think the method does generalize.  In situations where *some* of the iterators get invalidated, you need to do a little bit more work.  You need to maintain an invalidation log:

- For each (active) tag value, associate an optional record.  Initially there is no record for a tag.

- When an object updates in a way that invalidates iterators, add a record to its (now former) tag saying enough about what the operation was that you can know what got invalidated (e.g., for vector, the invalidated range, or possibly better, the range that remains valid).  Also, record the container's new tag.

Now when the tags don't match, instead of just blowing up, you use your tag to follow update chain through all the tags and see if you're still valid through the operations that have occurred.  You'll either find the new tag you need, or find you're invalid.

There are details, of course, such as reference counting things so that it all cleans up nicely (i.e., you only keep as much of the invalidation log as you actually need), and handling tag collisions for record information (because you really shouldn't *ever* fail for valid code, even if it is more likely that the user will be struck by lightning while in the bathroom).  But I think those details are pretty straightforward.

    M.E.O.