[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

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

1 files changed, 81 insertions, 21 deletions

diff --git a/tools/libclang/CXCursor.cpp b/tools/libclang/CXCursor.cpp
index 22a841f4f5..c344b41cec 100644
--- a/tools/libclang/CXCursor.cpp
+++ b/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) {