[analyzer] Optimize dynamic dispatch bifurcation by detecting the cases

when we don't need to split.

In some cases we know that a method cannot have a different
implementation in a subclass:
 - the class is declared in the main file (private)
 - all the method declarations (including the ones coming from super
classes) are in the main file.

This can be improved further, but might be enough for the heuristic.
(When we are too aggressive splitting the state, efficiency suffers.
When we fail to split the state coverage might suffer.)

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@161681 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 144 insertions, 25 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
index 5e008bd976..0a9590f640 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
@@ -754,6 +754,10 @@ protected:
 
   virtual QualType getDeclaredResultType() const;
 
+  /// Check if the selector may have multiple definitions (may have overrides).
+  virtual bool canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
+                                        Selector Sel) const;
+
 public:
   virtual const ObjCMessageExpr *getOriginExpr() const {
     return cast<ObjCMessageExpr>(CallEvent::getOriginExpr());
diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp
index 13bdaa729b..773600b096 100644
--- a/lib/StaticAnalyzer/Core/CallEvent.cpp
+++ b/lib/StaticAnalyzer/Core/CallEvent.cpp
@@ -659,6 +659,59 @@ ObjCMessageKind ObjCMethodCall::getMessageKind() const {
   return static_cast<ObjCMessageKind>(Info.getInt());
 }
 
+
+bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
+                                             Selector Sel) const {
+  assert(IDecl);
+  const SourceManager &SM =
+    getState()->getStateManager().getContext().getSourceManager();
+
+  // If the class interface is declared inside the main file, assume it is not
+  // subcassed. 
+  // TODO: It could actually be subclassed if the subclass is private as well.
+  // This is probably very rare.
+  SourceLocation InterfLoc = IDecl->getEndOfDefinitionLoc();
+  if (InterfLoc.isValid() && SM.isFromMainFile(InterfLoc))
+    return false;
+
+
+  // We assume that if the method is public (declared outside of main file) or
+  // has a parent which publicly declares the method, the method could be
+  // overridden in a subclass.
+
+  // Find the first declaration in the class hierarchy that declares
+  // the selector.
+  ObjCMethodDecl *D = 0;
+  while (true) {
+    D = IDecl->lookupMethod(Sel, true);
+
+    // Cannot find a public definition.
+    if (!D)
+      return false;
+
+    // If outside the main file,
+    if (D->getLocation().isValid() && !SM.isFromMainFile(D->getLocation()))
+      return true;
+
+    if (D->isOverriding()) {
+      // Search in the superclass on the next iteration.
+      IDecl = D->getClassInterface();
+      if (!IDecl)
+        return false;
+
+      IDecl = IDecl->getSuperClass();
+      if (!IDecl)
+        return false;
+
+      continue;
+    }
+
+    return false;
+  };
+
+  llvm_unreachable("The while loop should always terminate.");
+}
+
 RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
   const ObjCMessageExpr *E = getOriginExpr();
   assert(E);
@@ -686,8 +739,12 @@ RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
 
     // Lookup the method implementation.
     if (ReceiverT)
-      if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl())
-        return RuntimeDefinition(IDecl->lookupPrivateMethod(Sel), Receiver);
+      if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl()) {
+        if (canBeOverridenInSubclass(IDecl, Sel))
+          return RuntimeDefinition(IDecl->lookupPrivateMethod(Sel), Receiver);
+        else
+          return RuntimeDefinition(IDecl->lookupPrivateMethod(Sel), 0);
+      }
 
   } else {
     // This is a class method.
diff --git a/test/Analysis/inlining/DynDispatchBifurcate.m b/test/Analysis/inlining/DynDispatchBifurcate.m
index 7616c1136b..2a690a5e62 100644
--- a/test/Analysis/inlining/DynDispatchBifurcate.m
+++ b/test/Analysis/inlining/DynDispatchBifurcate.m
@@ -1,19 +1,6 @@
 // RUN: %clang_cc1 -analyze -analyzer-checker=core -analyzer-ipa=dynamic-bifurcate -verify %s
 
-typedef signed char BOOL;
-typedef struct objc_class *Class;
-typedef struct objc_object {
-    Class isa;
-} *id;
-@protocol NSObject  - (BOOL)isEqual:(id)object; @end
-@interface NSObject <NSObject> {}
-+(id)alloc;
--(id)init;
--(id)autorelease;
--(id)copy;
-- (Class)class;
--(id)retain;
-@end
+#include "InlineObjCInstanceMethod.h"
 
 @interface MyParent : NSObject
 - (int)getZero;
@@ -24,28 +11,92 @@ typedef struct objc_object {
 }
 @end
 
+@implementation PublicClass
+- (int)getZeroPublic {
+    return 0;
+}
+@end
+
+@interface MyClassWithPublicParent : PublicClass
+- (int)getZeroPublic;
+@end
+@implementation MyClassWithPublicParent
+- (int)getZeroPublic {
+    return 0;
+}
+@end
+
+// Category overrides a public method.
+@interface PublicSubClass (PrvateCat)
+  - (int) getZeroPublic;
+@end
+@implementation PublicSubClass (PrvateCat)
+- (int)getZeroPublic {
+    return 0;
+}
+@end
+
+
 @interface MyClass : MyParent
 - (int)getZero;
 @end
 
-MyClass *getObj();
-
-// Check that we explore both paths - on one the calla are inlined and they are 
-// not inlined on the other.
-// In this case, p can be either the object of type MyParent* or MyClass*:
-// - If it's MyParent*, getZero returns 0.
-// - If it's MyClass*, getZero returns 1 and 'return 5/m' is reachable.
+// Since class is private, we assume that it cannot be subclassed.
+// False negative: this class is "privately subclassed". this is very rare 
+// in practice.
 @implementation MyClass
 + (int) testTypeFromParam:(MyParent*) p {
   int m = 0;
   int z = [p getZero];
   if (z)
-    return 5/m; // expected-warning {{Division by zero}}
+    return 5/m; // false negative
   return 5/[p getZero];// expected-warning {{Division by zero}}
 }
 
+// Here only one definition is possible, since the declaration is not visible 
+// from outside. 
++ (int) testTypeFromParamPrivateChild:(MyClass*) c {
+  int m = 0;
+  int z = [c getZero]; // MyClass overrides getZero to return '1'.
+  if (z)
+    return 5/m; // expected-warning {{Division by zero}}
+  return 5/[c getZero];//no warning
+}
+
 - (int)getZero {
     return 1;
 }
+@end
 
-@end
\ No newline at end of file
+// The class is prvate and is not subclassed.
+int testCallToPublicAPIInParent(MyClassWithPublicParent *p) {
+  int m = 0;
+  int z = [p getZeroPublic];
+  if (z)
+    return 5/m; // no warning
+  return 5/[p getZeroPublic];// expected-warning {{Division by zero}}  
+}
+
+// When the called method is public (due to it being defined outside of main file),
+// split the path and analyze both branches.
+// In this case, p can be either the object of type MyParent* or MyClass*:
+// - If it's MyParent*, getZero returns 0.
+// - If it's MyClass*, getZero returns 1 and 'return 5/m' is reachable.
+// Declaration is provate, but p can be a subclass (MyClass*).
+int testCallToPublicAPI(PublicClass *p) {
+  int m = 0;
+  int z = [p getZeroPublic];
+  if (z)
+    return 5/m; // expected-warning {{Division by zero}}
+  return 5/[p getZeroPublic];// expected-warning {{Division by zero}}  
+}
+
+// Even though the method is privately declared in the category, the parent 
+// declares the method as public. Assume the instance can be subclassed.
+int testCallToPublicAPICat(PublicSubClass *p) {
+  int m = 0;
+  int z = [p getZeroPublic];
+  if (z)
+    return 5/m; // expected-warning {{Division by zero}}
+  return 5/[p getZeroPublic];// expected-warning {{Division by zero}}  
+}
diff --git a/test/Analysis/inlining/InlineObjCInstanceMethod.h b/test/Analysis/inlining/InlineObjCInstanceMethod.h
index 18131c8673..bae80c60ec 100644
--- a/test/Analysis/inlining/InlineObjCInstanceMethod.h
+++ b/test/Analysis/inlining/InlineObjCInstanceMethod.h
@@ -17,3 +17,10 @@ typedef struct objc_object {
 - (Class)class;
 -(id)retain;
 @end
+
+@interface PublicClass : NSObject
+- (int)getZeroPublic;
+@end
+
+@interface PublicSubClass : PublicClass
+@end