[cfe-dev] Check virtual calls in ctor or dtor

[章磊]

Hi Ted,

Thank you very much for your reply and all your advises.

Sorry for this late reply, i am busy on my job this period.

I think the last approach is a good choice, it's simple and clear.

But i have two minor problems.


   1. When we do (b)(ii), we may find many calls not already in the
   PreVisit or PostVisit state, then we will add them to the stack. So the
   complete stack is not a  call stack, right? Then we may need a iterator
   point to the "call stack" top?
   2. In your former mail, you mentioned that "For each
   constructor/destructor, only report calling a specific virtual function
   once." IMO, we may need to report all the calls to a specific virtual
   function, these information may help the users to find out where is the
   exact place in the call path to fix these problems. But it may seems to
   noisy, so we may need a new bug report mechanism to make this kind of
   report clear.

After all, I will re-implement this patch lately after this busy period.

在 2011年11月23日 下午2:41，Ted Kremenek <kremenek at apple.com>写道：

> On Nov 22, 2011, at 10:11 PM, Ted Kremenek wrote:
>
> Stepping back, I think it's worth re-evaluating the overall algorithm.
>  Here's an abstraction that I think will help.
>
> Essentially we are building a virtual function callgraph.  Once we have
> the callgraph, we can determine if any of the constructors/destructors can
> call a virtual function.  Here's a simple decoupling of the algorithm:
>
> (1) Do a DFS worklist algorithm to build the callgraph.  This is basically
> the walk you are doing now, but you don't have to do any error reporting.
>  You also don't need to keep track of the current call stack; all you care
> about is the current function you are analyzing, and the functions it
> calls.  The worklist just consists of enqueueing FunctionDecls, dequeing
> them and walking their bodies looking for calls.  When you see a call, you
> add the called function to the set of functions called by that function.
>  Of course we only want to restrict ourselves to calls on the 'this' object.
>
> (2) Once you have the (sparse) callgraph, you can iterate over all the
> constructors and destructors (you can cache a list of them on the side
> while doing step 1).  For each one, do a BFS over the callgraph, looking
> for virtual functions.  The BFS can be done as a worklist.  The advantage
> of using a BFS is you just report the shortest call chain from the
> constructor/destructor to the virtual function.  For each
> constructor/destructor, only report calling a specific virtual function
> once.
>
> (2a) As a refinement to (2), you can cache when certain functions *never*
> call a virtual function, thus pruning the search.  This is an optional step
> to improve performance.
>
> (2b) Error reporting comes down to just reporting a path through the
> callgraph.  Thus error reporting just becomes centralized in one place.  No
> code duplication.
>
> The nice thing about this approach is you get a really nice separation of
> concerns.  You decouple to problem of finding the call graph (which
> conceptually could be extended to incorporate path-sensitive information,
> etc.) from the process of finding a bug (a path through the callgraph from
> constructor to virtual function).  You also decouple the string generation
> from the logic of finding bugs.
>
> I hope my comments are not discouraging.  I think you are on the right
> track.  I think taking a step back and looking at how the algorithm could
> be restructured would be really beneficial to cleaning up the code and also
> potentially making the checker more powerful in the long run.  I also think
> you should pay a bit more attention to the accesses to containers.  While
> doing redundant hash table lookups on a error reporting case is not so bad,
> having redundant lookups in the fast path of the checker really adds
> unnecessary sluggishness to your code.
>
> I hope this helps.
>
>
> Thinking about this more, I think this strategy, while generally, is more
> complicated then you need for a first go around.
>
> Here is a much simpler approach, which basically matches what you are
> already doing:
>
> (1) Starting from each constructor/destructor, do a DFS, using a worklist.
>  The worklist just has a chain of FunctionDecls.
>
>   (a) Define 'Enqueue' to enqueue a method to the worklist.  This..
>
>     (i) adds the method to the stack (push_back())
>     (ii) adds the method to a DenseMap that records two states: "PreVisit"
> and "PostVisit".  Enqueue marks them as PreVisit.
>
>   (b) When processing a method from the worklist:
>
>      (i) dequeue the item from the end of the stack, but don't remove it
> yet from the stack
>
>      IF the function is in the PreVisit state:
>
>      (ii) walk its body:
>           - If we find a call to a virtual function, emit a warning by
> simply passing the complete stack + the virtual function called to our
> error reporting routine.
>           - If we find a call to a non-virtual function, add it to the
> worklist IFF it is not already in the PreVisit or PostVisit state.
>      (iii) mark the decl as being in the PostVisit state
>
>      (iv) continue processing the worklist
>
>     IF the function is in the PostVisit state:
>
>     (v) pop it off the worklist.
>
> The value of the PreVisit versus PostVisit is that we always keep a full
> call chain stack available.
>
> This should provide a nice decoupling between the search and the error
> reporting, while completely unrolling the recursion.  As a further
> optimization, we can potential recording as part of step (v) whether or not
> a function is never transitively calls a virtual method, and thus doesn't
> need to be considered as part of any further search.
>
> I think this should be a vast simplification of your existing logic, and
> also is much simpler than the algorithm I proposed.
>
> What do you think?
>



-- 
Best regards!

Lei Zhang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111202/945a6b18/attachment.html>