[cfe-dev] Proposed: change tracking for RegionStore

[Ted Kremenek]

On Aug 4, 2010, at 11:01 PM, Jordy Rose wrote:

> OK, here's a first pass at ProcessRegionChange.
> 
> The first note is that I didn't choose to call it for every change to the
> store.
> 
> Included: bindLoc, bindDefault, InvalidateRegions

Note that InvalidateRegions touches a lot more than the regions specified.  It computes a transitive closure, including looking at regions whose addresses are bound to other regions.  Should those be included in the callback?

> Excluded: bindCompoundLiteral, bindDecl, bindDeclWithNoInit, unbindLoc,
> EnterStackFrame
> 
> The reason for this is that the excluded calls only /add/ regions to the
> store; they do not change existing bindings. It follows that a checker
> cannot already be tracking a region that has not existed until this point.
> (Arguably, bindDefault should be here too, since it's currently only used
> for new regions.) unbindLoc is a special case since it's not used for
> regions at all.

Makes lots of sense.

> 
> The second note is that it requires a ridiculous cross-indexing sort of
> search to be useful: if I'm tracking the strlen of region X, that length is
> invalid if any of X's subregions /or/ super-regions change. This results in
> the code seen in the attached txt snippet. Is there a better way to set
> this up that would make this neater?

This looks very similar to the region "cluster" analysis done in RegionStore that is used for InvalidateRegions and RemoveDeadBindings.  When I changed RegionStore to use the cluster analysis it wiped out a ton of old code.  We could expose that algorithm/API at a higher level, and possibly eliminate most of the boilerplate in your code.  Exposing APIs to do this kind of cross-indexing gives us the opportunity to do clever optimizations later that benefits all clients.

One nit: In your code, it's probably good to check that EntryMap is non-empty before building this index (which could be expensive).

> 
> Finally, the bind* covers in GRState are getting a little bulky for inline
> functions. At what point would we give up on the efficiency gain and move
> them to GRState.cpp?

Agreed.  I think all of these should be moved out-of-line at this point.  We should keep GRState.h defining a clean, readable interface.  These methods aren't hotspots anyway, so keeping them inline buys us nothing.