[cfe-dev] Invalidated Iterator Project

[Ted Kremenek]

I realized I never commented on these points.  Comments inline.

On Sep 9, 2010, at 2:58 AM, Jim Goodnow II wrote:

> 1) Locate all STL container instance declarations. This is needed 
> because we need to associate each iterator with a particular 
> container instance. STL containers have well defined operations that 
> invalidate bound iterators.

One thing to keep in mind is that STL implementations may vary in how they implement features such as std::string.  In some STL implementations a container might be a typedef, while in others it might be a direct declared class.  In my conversations with engineers working on commercial C++ static analysis tools, I vaguely recall this being an issue.  I don't have any specific advice; just something to look out for.

> 2) Locate all iterator declarations.

I don't think this needs to be done up front.  I think it can be done lazily when an iterator is used.

> 3) Locate all iterator definitions (assignments) and bind to the 
> instance used to initialize.

I think (2) can be lazily done as part of (3), and would be far more efficient.

> 4) Do a modified reaching definition analysis on the iterators where 
> certain operations on an instance such as insert, clear, reserve, 
> etc. can invalidate the iterator. Use the binding of the instance to 
> the iterator to invalidate the iterator.

This can probably be done as a typestate analysis, where a typestate is associated with the iterator.  Examples would be "VALID" and "INVALID".

> 5) Flag with warnings uses of iterators that have been invalidated.

If a typestate analysis was in place, this could easily be done for monitoring accesses to the iterators and seeing if the typestate is INVALID.

> 6) Flag with warnings binary operations on iterators bound to 
> different instances.

I advice doing this after (5) is in place.  This is a little more tricky, as this isn't just about different instances, but also that the iterators were created at a consistent point for the same container.  e.g.:

iterator E = container.end();
...
/// modify the container
...
iterator I = container.begin();
...
if (I == E) // error

This example, which is probably really rare in practice (although it could conceptually happen, especially if 'begin' is something like 'find'), is still an error even though both iterators access the same container.