[Analysis] Fix for call graph to correctly handle nested call expressions

[baloghadamsoftware]

Summary

Take the following example:

class Int {
public:
  Int(int n = 0): num(n) {}
  Int(const Int& rhs): num(rhs.num) {}
  Int& operator=(const Int& rhs) { num = rhs.num; }
  operator int() { return num; }
private:
  int num;
};

Int h(Int n) {
  return n;
}

Int f(Int n) {
  Int i;
  i = h(n);
  return i;
}

Int g(Int n) {
  Int i = h(n);
  return i;
}

The call graph for this C++ compilation unit will omit the edge from f to h, but not from g to h. This is obviously an error. The reason is that when visiting the statements to build the call graph all call expressions are handled as leafs. In the example above f calls operator=, which is a call expression, but it also has a child call expression, a call to function h. However, this latter edge is not visited because operator= is handled as leaf and its child call expression is not visited.

[xazax.hun]

Great find! Could you transform your examole into a testcasr that fails before this patch? I think there should be already some tests for call graphs that you can take a look at.

[baloghadamsoftware]

In D29183#657669, @xazax.hun wrote:

Great find! Could you transform your examole into a testcasr that fails before this patch? I think there should be already some tests for call graphs that you can take a look at.

Yes, but I am not sure where exactly to put it.

[baloghadamsoftware]

Some comments how I found this bug. I got some strange false positives even after the fix for the iterator past end checker (D28771). I could reproduce it with the following code:

#include <list>

using std::list;
using std::prev;

namespace {

  class Strange {
  public:
    Strange(list<int> &l) : Back(prev(l.end())), Item(*Back) {}
    void reset(list<int> &l) { Back = prev(l.end()); Item = *Back; }
    int get1(list<int> &l) { Back = prev(l.end()); return *Back; }
    int get2(list<int> &l) { list<int>::iterator i; i = prev(l.end()); return *i; }
    
  private:
    list<int>::iterator Back;
    int Item;
  };

}

This example was analyzed without errors, but if I removed get2(), I got iterator past end errors for every other function. Even more strange was that I could not reproduce this with std::vector, just with std::list. I started a long debugging session (days) and it turned out, that if I delete get2(), std::prev() is analyzed as top-level. Since std::prev() calls std::advance(), which calls an <underscore><underscore>advance() overload for bidirectional operators which increments or decrements the iterator in a loop. Since the number of iterations is undefined, after 4 iterations on both branch (++ and --) the analysis stops and marks the function as non-inlinable. This, of course does not happen for std::vector because it contains no loop but a simple += operation. If <underscore><underscore>advance() is marked as non-inlinable, it does not change its argument, so prev(l.end()) is the same as l.end(), so dereferencing the iterator is indeed an error.

[NoQ]

Hmm, we should have done better work reviewing D28905.

[baloghadamsoftware]

I wonder if this could also be a problem for nested messages in Objective-C, since the call for VisitChildren() is also missing from VisitObjCMessageExpr()...

[baloghadamsoftware]

In D29183#657706, @NoQ wrote:

Hmm, we should have done better work reviewing D28905.

Oh, someone was quicker than me by one week...

lib/Analysis/CallGraph.cpp

if (G->includeInGraph(D)) {
       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
       CallerNode->addCallee(CalleeNode);
     }
   }
 
   void VisitCallExpr(CallExpr *CE) {
     if (Decl *D = getDeclFromCall(CE))
       addCalledDecl(D);
+    VisitChildren(CE);
   }
 
   // Adds may-call edges for the ObjC message sends.
   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
       Selector Sel = ME->getSelector();
       
       // Find the callee definition within the same translation unit.