[AST/libclang] Speed up clang_getOverriddenCursors() considerably by reserving a bit

in ObjCMethodDecl to indicate whether the method does not override any other method,
which is the majority of cases.

That way we can avoid unnecessary work doing lookups, especially when PCH is involved.

rdar://11360082

llvm-svn: 156476

8 files changed, 252 insertions, 81 deletions

diff --git a/clang/include/clang/AST/DeclObjC.h b/clang/include/clang/AST/DeclObjC.h
index 4ae073ec4608..93441d2e8390 100644
--- a/clang/include/clang/AST/DeclObjC.h
+++ b/clang/include/clang/AST/DeclObjC.h
@@ -150,6 +150,15 @@ private:
   /// "standard" position, a enum SelectorLocationsKind.
   unsigned SelLocsKind : 2;
 
+  /// \brief Whether this method overrides any other in the class hierarchy.
+  ///
+  /// A method is said to override any method in the class's
+  /// base classes, its protocols, or its categories' protocols, that has
+  /// the same selector and is of the same kind (class or instance).
+  /// A method in an implementation is not considered as overriding the same
+  /// method in the interface or its categories.
+  unsigned IsOverriding : 1;
+
   // Result type of this method.
   QualType MethodDeclType;
 
@@ -230,7 +239,7 @@ private:
     IsDefined(isDefined), IsRedeclaration(0), HasRedeclaration(0),
     DeclImplementation(impControl), objcDeclQualifier(OBJC_TQ_None),
     RelatedResultType(HasRelatedResultType),
-    SelLocsKind(SelLoc_StandardNoSpace),
+    SelLocsKind(SelLoc_StandardNoSpace), IsOverriding(0),
     MethodDeclType(T), ResultTInfo(ResultTInfo),
     ParamsAndSelLocs(0), NumParams(0),
     EndLoc(endLoc), Body(0), SelfDecl(0), CmdDecl(0) {
@@ -396,6 +405,16 @@ public:
   bool isDefined() const { return IsDefined; }
   void setDefined(bool isDefined) { IsDefined = isDefined; }
 
+  /// \brief Whether this method overrides any other in the class hierarchy.
+  ///
+  /// A method is said to override any method in the class's
+  /// base classes, its protocols, or its categories' protocols, that has
+  /// the same selector and is of the same kind (class or instance).
+  /// A method in an implementation is not considered as overriding the same
+  /// method in the interface or its categories.
+  bool isOverriding() const { return IsOverriding; }
+  void setOverriding(bool isOverriding) { IsOverriding = isOverriding; }
+  
   // Related to protocols declared in  @protocol
   void setDeclImplementation(ImplementationControl ic) {
     DeclImplementation = ic;
diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h
index 4518fe901bc2..0c0b3ead3b12 100644
--- a/clang/include/clang/Sema/Sema.h
+++ b/clang/include/clang/Sema/Sema.h
@@ -6174,9 +6174,16 @@ public:
                                const ObjCMethodDecl *Overridden,
                                bool IsImplementation);
 
-  /// \brief Check whether the given method overrides any methods in its class,
-  /// calling \c CheckObjCMethodOverride for each overridden method.
-  bool CheckObjCMethodOverrides(ObjCMethodDecl *NewMethod, DeclContext *DC);
+  /// \brief Describes the compatibility of a result type with its method.
+  enum ResultTypeCompatibilityKind {
+    RTC_Compatible,
+    RTC_Incompatible,
+    RTC_Unknown
+  };
+
+  void CheckObjCMethodOverrides(ObjCMethodDecl *ObjCMethod,
+                                ObjCInterfaceDecl *CurrentClass,
+                                ResultTypeCompatibilityKind RTC);
 
   enum PragmaOptionsAlignKind {
     POAK_Native,  // #pragma options align=native
diff --git a/clang/lib/Sema/SemaDeclObjC.cpp b/clang/lib/Sema/SemaDeclObjC.cpp
index d2fdd4fec662..02430e6da54f 100644
--- a/clang/lib/Sema/SemaDeclObjC.cpp
+++ b/clang/lib/Sema/SemaDeclObjC.cpp
@@ -2444,19 +2444,10 @@ bool containsInvalidMethodImplAttribute(ObjCMethodDecl *IMD,
   return false;
 }
 
-namespace  {
-  /// \brief Describes the compatibility of a result type with its method.
-  enum ResultTypeCompatibilityKind {
-    RTC_Compatible,
-    RTC_Incompatible,
-    RTC_Unknown
-  };
-}
-
 /// \brief Check whether the declared result type of the given Objective-C
 /// method declaration is compatible with the method's class.
 ///
-static ResultTypeCompatibilityKind 
+static Sema::ResultTypeCompatibilityKind 
 CheckRelatedResultTypeCompatibility(Sema &S, ObjCMethodDecl *Method,
                                     ObjCInterfaceDecl *CurrentClass) {
   QualType ResultType = Method->getResultType();
@@ -2469,27 +2460,27 @@ CheckRelatedResultTypeCompatibility(Sema &S, ObjCMethodDecl *Method,
     //   - it is id or qualified id, or
     if (ResultObjectType->isObjCIdType() ||
         ResultObjectType->isObjCQualifiedIdType())
-      return RTC_Compatible;
+      return Sema::RTC_Compatible;
   
     if (CurrentClass) {
       if (ObjCInterfaceDecl *ResultClass 
                                       = ResultObjectType->getInterfaceDecl()) {
         //   - it is the same as the method's class type, or
         if (declaresSameEntity(CurrentClass, ResultClass))
-          return RTC_Compatible;
+          return Sema::RTC_Compatible;
         
         //   - it is a superclass of the method's class type
         if (ResultClass->isSuperClassOf(CurrentClass))
-          return RTC_Compatible;
+          return Sema::RTC_Compatible;
       }      
     } else {
       // Any Objective-C pointer type might be acceptable for a protocol
       // method; we just don't know.
-      return RTC_Unknown;
+      return Sema::RTC_Unknown;
     }
   }
   
-  return RTC_Incompatible;
+  return Sema::RTC_Incompatible;
 }
 
 namespace {
@@ -2639,6 +2630,67 @@ private:
 };
 }
 
+void Sema::CheckObjCMethodOverrides(ObjCMethodDecl *ObjCMethod,
+                                    ObjCInterfaceDecl *CurrentClass,
+                                    ResultTypeCompatibilityKind RTC) {
+  // Search for overridden methods and merge information down from them.
+  OverrideSearch overrides(*this, ObjCMethod);
+  // Keep track if the method overrides any method in the class's base classes,
+  // its protocols, or its categories' protocols; we will keep that info
+  // in the ObjCMethodDecl.
+  // For this info, a method in an implementation is not considered as
+  // overriding the same method in the interface or its categories.
+  bool hasOverriddenMethodsInBaseOrProtocol = false;
+  for (OverrideSearch::iterator
+         i = overrides.begin(), e = overrides.end(); i != e; ++i) {
+    ObjCMethodDecl *overridden = *i;
+
+    if (isa<ObjCProtocolDecl>(overridden->getDeclContext()) ||
+        CurrentClass != overridden->getClassInterface() ||
+        overridden->isOverriding())
+      hasOverriddenMethodsInBaseOrProtocol = true;
+
+    // Propagate down the 'related result type' bit from overridden methods.
+    if (RTC != Sema::RTC_Incompatible && overridden->hasRelatedResultType())
+      ObjCMethod->SetRelatedResultType();
+
+    // Then merge the declarations.
+    mergeObjCMethodDecls(ObjCMethod, overridden);
+
+    if (ObjCMethod->isImplicit() && overridden->isImplicit())
+      continue; // Conflicting properties are detected elsewhere.
+
+    // Check for overriding methods
+    if (isa<ObjCInterfaceDecl>(ObjCMethod->getDeclContext()) || 
+        isa<ObjCImplementationDecl>(ObjCMethod->getDeclContext()))
+      CheckConflictingOverridingMethod(ObjCMethod, overridden,
+              isa<ObjCProtocolDecl>(overridden->getDeclContext()));
+    
+    if (CurrentClass && overridden->getDeclContext() != CurrentClass &&
+        isa<ObjCInterfaceDecl>(overridden->getDeclContext())) {
+      ObjCMethodDecl::param_iterator ParamI = ObjCMethod->param_begin(),
+                                          E = ObjCMethod->param_end();
+      ObjCMethodDecl::param_iterator PrevI = overridden->param_begin();
+      for (; ParamI != E; ++ParamI, ++PrevI) {
+        // Number of parameters are the same and is guaranteed by selector match.
+        assert(PrevI != overridden->param_end() && "Param mismatch");
+        QualType T1 = Context.getCanonicalType((*ParamI)->getType());
+        QualType T2 = Context.getCanonicalType((*PrevI)->getType());
+        // If type of argument of method in this class does not match its
+        // respective argument type in the super class method, issue warning;
+        if (!Context.typesAreCompatible(T1, T2)) {
+          Diag((*ParamI)->getLocation(), diag::ext_typecheck_base_super)
+            << T1 << T2;
+          Diag(overridden->getLocation(), diag::note_previous_declaration);
+          break;
+        }
+      }
+    }
+  }
+
+  ObjCMethod->setOverriding(hasOverriddenMethodsInBaseOrProtocol);
+}
+
 Decl *Sema::ActOnMethodDeclaration(
     Scope *S,
     SourceLocation MethodLoc, SourceLocation EndLoc,
@@ -2828,53 +2880,14 @@ Decl *Sema::ActOnMethodDeclaration(
   ResultTypeCompatibilityKind RTC
     = CheckRelatedResultTypeCompatibility(*this, ObjCMethod, CurrentClass);
 
-  // Search for overridden methods and merge information down from them.
-  OverrideSearch overrides(*this, ObjCMethod);
-  for (OverrideSearch::iterator
-         i = overrides.begin(), e = overrides.end(); i != e; ++i) {
-    ObjCMethodDecl *overridden = *i;
-
-    // Propagate down the 'related result type' bit from overridden methods.
-    if (RTC != RTC_Incompatible && overridden->hasRelatedResultType())
-      ObjCMethod->SetRelatedResultType();
+  CheckObjCMethodOverrides(ObjCMethod, CurrentClass, RTC);
 
-    // Then merge the declarations.
-    mergeObjCMethodDecls(ObjCMethod, overridden);
-    
-    // Check for overriding methods
-    if (isa<ObjCInterfaceDecl>(ObjCMethod->getDeclContext()) || 
-        isa<ObjCImplementationDecl>(ObjCMethod->getDeclContext()))
-      CheckConflictingOverridingMethod(ObjCMethod, overridden,
-              isa<ObjCProtocolDecl>(overridden->getDeclContext()));
-    
-    if (CurrentClass && overridden->getDeclContext() != CurrentClass &&
-        isa<ObjCInterfaceDecl>(overridden->getDeclContext())) {
-      ObjCMethodDecl::param_iterator ParamI = ObjCMethod->param_begin(),
-                                          E = ObjCMethod->param_end();
-      ObjCMethodDecl::param_iterator PrevI = overridden->param_begin();
-      for (; ParamI != E; ++ParamI, ++PrevI) {
-        // Number of parameters are the same and is guaranteed by selector match.
-        assert(PrevI != overridden->param_end() && "Param mismatch");
-        QualType T1 = Context.getCanonicalType((*ParamI)->getType());
-        QualType T2 = Context.getCanonicalType((*PrevI)->getType());
-        // If type of argument of method in this class does not match its
-        // respective argument type in the super class method, issue warning;
-        if (!Context.typesAreCompatible(T1, T2)) {
-          Diag((*ParamI)->getLocation(), diag::ext_typecheck_base_super)
-            << T1 << T2;
-          Diag(overridden->getLocation(), diag::note_previous_declaration);
-          break;
-        }
-      }
-    }
-  }
-  
   bool ARCError = false;
   if (getLangOpts().ObjCAutoRefCount)
     ARCError = CheckARCMethodDecl(*this, ObjCMethod);
 
   // Infer the related result type when possible.
-  if (!ARCError && RTC == RTC_Compatible &&
+  if (!ARCError && RTC == Sema::RTC_Compatible &&
       !ObjCMethod->hasRelatedResultType() &&
       LangOpts.ObjCInferRelatedResultType) {
     bool InferRelatedResultType = false;
diff --git a/clang/lib/Sema/SemaObjCProperty.cpp b/clang/lib/Sema/SemaObjCProperty.cpp
index 8e767e21bd10..5a98077bd7f3 100644
--- a/clang/lib/Sema/SemaObjCProperty.cpp
+++ b/clang/lib/Sema/SemaObjCProperty.cpp
@@ -1776,6 +1776,18 @@ void Sema::ProcessPropertyDecl(ObjCPropertyDecl *property,
     AddInstanceMethodToGlobalPool(GetterMethod);
   if (SetterMethod)
     AddInstanceMethodToGlobalPool(SetterMethod);
+
+  ObjCInterfaceDecl *CurrentClass = dyn_cast<ObjCInterfaceDecl>(CD);
+  if (!CurrentClass) {
+    if (ObjCCategoryDecl *Cat = dyn_cast<ObjCCategoryDecl>(CD))
+      CurrentClass = Cat->getClassInterface();
+    else if (ObjCImplDecl *Impl = dyn_cast<ObjCImplDecl>(CD))
+      CurrentClass = Impl->getClassInterface();
+  }
+  if (GetterMethod)
+    CheckObjCMethodOverrides(GetterMethod, CurrentClass, Sema::RTC_Unknown);
+  if (SetterMethod)
+    CheckObjCMethodOverrides(SetterMethod, CurrentClass, Sema::RTC_Unknown);
 }
 
 void Sema::CheckObjCPropertyAttributes(Decl *PDecl,
diff --git a/clang/lib/Serialization/ASTReaderDecl.cpp b/clang/lib/Serialization/ASTReaderDecl.cpp
index 9ead7947acd1..512b070620ac 100644
--- a/clang/lib/Serialization/ASTReaderDecl.cpp
+++ b/clang/lib/Serialization/ASTReaderDecl.cpp
@@ -642,6 +642,7 @@ void ASTDeclReader::VisitObjCMethodDecl(ObjCMethodDecl *MD) {
   MD->setVariadic(Record[Idx++]);
   MD->setSynthesized(Record[Idx++]);
   MD->setDefined(Record[Idx++]);
+  MD->IsOverriding = Record[Idx++];
 
   MD->IsRedeclaration = Record[Idx++];
   MD->HasRedeclaration = Record[Idx++];
diff --git a/clang/lib/Serialization/ASTWriterDecl.cpp b/clang/lib/Serialization/ASTWriterDecl.cpp
index ee30dd8ea9a4..86b667ad719e 100644
--- a/clang/lib/Serialization/ASTWriterDecl.cpp
+++ b/clang/lib/Serialization/ASTWriterDecl.cpp
@@ -417,6 +417,7 @@ void ASTDeclWriter::VisitObjCMethodDecl(ObjCMethodDecl *D) {
   Record.push_back(D->isVariadic());
   Record.push_back(D->isSynthesized());
   Record.push_back(D->isDefined());
+  Record.push_back(D->IsOverriding);
 
   Record.push_back(D->IsRedeclaration);
   Record.push_back(D->HasRedeclaration);
diff --git a/clang/test/Index/overrides.m b/clang/test/Index/overrides.m
index 690875456371..f0f3e5fedbf6 100644
--- a/clang/test/Index/overrides.m
+++ b/clang/test/Index/overrides.m
@@ -50,6 +50,52 @@
 -(void)meth { }
 @end
 
+@protocol P5
+-(void)kol;
+-(void)kol;
+@end
+
+@protocol P6
+@property (readonly) id prop1;
+@property (readonly) id prop2;
+-(void)meth;
+@end
+
+@interface I3 <P6>
+@property (readwrite) id prop1;
+@property (readonly) id bar;
+@end
+
+@interface I3()
+@property (readwrite) id prop2;
+@property (readwrite) id bar;
+-(void)meth;
+@end
+
+@interface B4
+-(id)prop;
+-(void)setProp:(id)prop;
+@end
+
+@interface I4 : B4
+@property (assign) id prop;
+@end
+
+@interface B5
+@end
+
+@interface I5 : B5
+-(void)meth;
+@end
+
+@interface B5(cat)
+-(void)meth;
+@end
+
+@implementation I5
+-(void)meth{}
+@end
+
 // RUN: c-index-test -test-load-source local %s | FileCheck %s
 // CHECK: overrides.m:12:9: ObjCInstanceMethodDecl=protoMethod:12:9 [Overrides @3:9]
 // CHECK: overrides.m:22:9: ObjCInstanceMethodDecl=method:22:9 [Overrides @16:9]
@@ -59,3 +105,15 @@
 // CHECK: overrides.m:32:9: ObjCInstanceMethodDecl=protoMethod:32:9 [Overrides @8:9]
 // CHECK: overrides.m:36:9: ObjCInstanceMethodDecl=protoMethod:36:9 [Overrides @12:9, @8:9, @32:9, @17:9]
 // CHECK: overrides.m:50:8: ObjCInstanceMethodDecl=meth:50:8 (Definition) [Overrides @43:8]
+// CHECK: overrides.m:55:8: ObjCInstanceMethodDecl=kol:55:8 Extent=[55:1 - 55:12]
+// CHECK: overrides.m:65:26: ObjCInstanceMethodDecl=prop1:65:26 [Overrides @59:25] Extent=[65:26 - 65:31]
+// CHECK: overrides.m:65:26: ObjCInstanceMethodDecl=setProp1::65:26 Extent=[65:26 - 65:31]
+// CHECK: overrides.m:70:26: ObjCInstanceMethodDecl=prop2:70:26 [Overrides @60:25] Extent=[70:26 - 70:31]
+// CHECK: overrides.m:70:26: ObjCInstanceMethodDecl=setProp2::70:26 Extent=[70:26 - 70:31]
+// CHECK: overrides.m:71:26: ObjCInstanceMethodDecl=setBar::71:26 Extent=[71:26 - 71:29]
+// CHECK: overrides.m:72:8: ObjCInstanceMethodDecl=meth:72:8 [Overrides @61:8] Extent=[72:1 - 72:13]
+// CHECK: overrides.m:81:23: ObjCInstanceMethodDecl=prop:81:23 [Overrides @76:6] Extent=[81:23 - 81:27]
+// CHECK: overrides.m:81:23: ObjCInstanceMethodDecl=setProp::81:23 [Overrides @77:8] Extent=[81:23 - 81:27]
+// CHECK: overrides.m:92:8: ObjCInstanceMethodDecl=meth:92:8 Extent=[92:1 - 92:13]
+// CHECK: overrides.m:95:17: ObjCImplementationDecl=I5:95:17 (Definition) Extent=[95:1 - 97:2]
+// CHECK: overrides.m:96:9: ObjCInstanceMethodDecl=meth:96:9 (Definition) [Overrides @92:8] Extent=[96:1 - 96:14]
diff --git a/clang/tools/libclang/CXCursor.cpp b/clang/tools/libclang/CXCursor.cpp
index 22a841f4f54c..c344b41cecc1 100644
--- a/clang/tools/libclang/CXCursor.cpp
+++ b/clang/tools/libclang/CXCursor.cpp
@@ -864,27 +864,10 @@ static inline void CollectOverriddenMethods(CXTranslationUnit TU,
                                   /*MovedToSuper=*/false);
 }
 
-void cxcursor::getOverriddenCursors(CXCursor cursor,
-                                    SmallVectorImpl<CXCursor> &overridden) { 
-  assert(clang_isDeclaration(cursor.kind));
-  Decl *D = getCursorDecl(cursor);
-  if (!D)
-    return;
-
-  // Handle C++ member functions.
-  CXTranslationUnit TU = getCursorTU(cursor);
-  if (CXXMethodDecl *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
-    for (CXXMethodDecl::method_iterator
-              M = CXXMethod->begin_overridden_methods(),
-           MEnd = CXXMethod->end_overridden_methods();
-         M != MEnd; ++M)
-      overridden.push_back(MakeCXCursor(const_cast<CXXMethodDecl*>(*M), TU));
-    return;
-  }
-
-  ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(D);
-  if (!Method)
-    return;
+static void collectOverriddenMethodsSlow(CXTranslationUnit TU,
+                                         ObjCMethodDecl *Method,
+                                        SmallVectorImpl<CXCursor> &overridden) {
+  assert(Method->isOverriding());
 
   if (ObjCProtocolDecl *
         ProtD = dyn_cast<ObjCProtocolDecl>(Method->getDeclContext())) {
@@ -921,6 +904,83 @@ void cxcursor::getOverriddenCursors(CXCursor cursor,
   }
 }
 
+static void collectOnCategoriesAfterLocation(SourceLocation Loc,
+                                             ObjCInterfaceDecl *Class,
+                                             CXTranslationUnit TU,
+                                             ObjCMethodDecl *Method,
+                                           SmallVectorImpl<CXCursor> &Methods) {
+  if (!Class)
+    return;
+
+  SourceManager &SM = static_cast<ASTUnit *>(TU->TUData)->getSourceManager();
+  for (ObjCCategoryDecl *Category = Class->getCategoryList();
+       Category; Category = Category->getNextClassCategory())
+    if (SM.isBeforeInTranslationUnit(Loc, Category->getLocation()))
+      CollectOverriddenMethodsRecurse(TU, Category, Method, Methods, true);
+
+  collectOnCategoriesAfterLocation(Loc, Class->getSuperClass(), TU,
+                                   Method, Methods);
+}
+
+/// \brief Faster collection that is enabled when ObjCMethodDecl::isOverriding()
+/// returns false.
+/// You'd think that in that case there are no overrides but categories can
+/// "introduce" new overridden methods that are missed by Sema because the
+/// overrides lookup that it does for methods, inside implementations, will
+/// stop at the interface level (if there is a method there) and not look
+/// further in super classes.
+static void collectOverriddenMethodsFast(CXTranslationUnit TU,
+                                         ObjCMethodDecl *Method,
+                                         SmallVectorImpl<CXCursor> &Methods) {
+  assert(!Method->isOverriding());
+
+  ObjCContainerDecl *ContD = cast<ObjCContainerDecl>(Method->getDeclContext());
+  if (isa<ObjCInterfaceDecl>(ContD) || isa<ObjCProtocolDecl>(ContD))
+    return;
+  ObjCInterfaceDecl *Class = Method->getClassInterface();
+  if (!Class)
+    return;
+
+  collectOnCategoriesAfterLocation(Class->getLocation(), Class->getSuperClass(),
+                                   TU, Method, Methods);
+}
+
+void cxcursor::getOverriddenCursors(CXCursor cursor,
+                                    SmallVectorImpl<CXCursor> &overridden) { 
+  assert(clang_isDeclaration(cursor.kind));
+  Decl *D = getCursorDecl(cursor);
+  if (!D)
+    return;
+
+  // Handle C++ member functions.
+  CXTranslationUnit TU = getCursorTU(cursor);
+  if (CXXMethodDecl *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
+    for (CXXMethodDecl::method_iterator
+              M = CXXMethod->begin_overridden_methods(),
+           MEnd = CXXMethod->end_overridden_methods();
+         M != MEnd; ++M)
+      overridden.push_back(MakeCXCursor(const_cast<CXXMethodDecl*>(*M), TU));
+    return;
+  }
+
+  ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(D);
+  if (!Method)
+    return;
+
+  if (Method->isRedeclaration()) {
+    Method = cast<ObjCContainerDecl>(Method->getDeclContext())->
+                   getMethod(Method->getSelector(), Method->isInstanceMethod());
+  }
+
+  if (!Method->isOverriding()) {
+    collectOverriddenMethodsFast(TU, Method, overridden);
+  } else {
+    collectOverriddenMethodsSlow(TU, Method, overridden);
+    assert(!overridden.empty() &&
+           "ObjCMethodDecl's overriding bit is not as expected");
+  }
+}
+
 std::pair<int, SourceLocation>
 cxcursor::getSelectorIdentifierIndexAndLoc(CXCursor cursor) {
   if (cursor.kind == CXCursor_ObjCMessageExpr) {