[clang-tidy] Optimize misc-confusable-identifiers

[PiotrZSL]

Summary

Main performance issue in this check were caused by many
calls to getPrimaryContext and constant walk up to declaration
contexts using getParent. Also there were issue with forallBases
that is slow.

Profiled with perf and tested on open-source project Cataclysm-DDA.
Before changes check took 27320 seconds, after changes 3682 seconds.
That's 86.5% reduction. More optimizations are still possible in this
check.

[serge-sans-paille]

Memoizing the calls to getPrimaryContext()... LGTM!

clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h

 //===--- ConfusableIdentifierCheck.h - clang-tidy
 //-------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_CONFUSABLE_IDENTIFIER_CHECK_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_CONFUSABLE_IDENTIFIER_CHECK_H
 
 #include "../ClangTidyCheck.h"
+#include <unordered_map>
 
 namespace clang::tidy::misc {
 
 /// Finds symbol which have confusable identifiers, i.e. identifiers that look
 /// the same visually but have a different Unicode representation.
 /// If symbols are confusable but don't live in conflicting namespaces, they are
 /// not reported.
 class ConfusableIdentifierCheck : public ClangTidyCheck {
 public:
   ConfusableIdentifierCheck(StringRef Name, ClangTidyContext *Context);
   ~ConfusableIdentifierCheck();
 
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
 
+  struct ContextInfo {
+    const DeclContext *PrimaryContext;
+    const DeclContext *NonTransparentContext;
+    llvm::SmallVector<const DeclContext *> PrimaryContexts;
+    llvm::SmallVector<const CXXRecordDecl *> Bases;
+  };
+
 private:
-  std::string skeleton(StringRef);
-  llvm::StringMap<llvm::SmallVector<const NamedDecl *>> Mapper;
+  struct Entry {
+    const NamedDecl *Declaration;
+    const ContextInfo *Info;
+  };
+
+  const ContextInfo *getContextInfo(const DeclContext *DC);
+
+  llvm::StringMap<llvm::SmallVector<Entry>> Mapper;
+  std::unordered_map<const DeclContext *, ContextInfo> ContextInfos;
 };
 
 } // namespace clang::tidy::misc
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_CONFUSABLE_IDENTIFIER_CHECK_H

clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp

 // 1. Convert X to NFD format, as described in [UAX15].
 // 2. Concatenate the prototypes for each character in X according to the
 // specified data, producing a string of exemplar characters.
 // 3. Reapply NFD.
 //
 // We're skipping 1. and 3. for the sake of simplicity, but this can lead to
 // false positive.
 
-std::string ConfusableIdentifierCheck::skeleton(StringRef Name) {
+static std::string skeleton(StringRef Name) {
   using namespace llvm;
   std::string SName = Name.str();
   std::string Skeleton;
   Skeleton.reserve(1 + Name.size());
 
   const char *Curr = SName.c_str();
   const char *End = Curr + SName.size();
   while (Curr < End) {
if (Where == std::end(ConfusableEntries) || CodePoint != Where->codepoint) {
         break;
       }
       Skeleton.append((char *)BufferStart, (char *)IBuffer);
     }
   }
   return Skeleton;
 }
 
-static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
-  const DeclContext *DC0 = ND0->getDeclContext()->getPrimaryContext();
-  const DeclContext *DC1 = ND1->getDeclContext()->getPrimaryContext();
-
-  if (isa<TemplateTypeParmDecl>(ND0) || isa<TemplateTypeParmDecl>(ND0))
-    return true;
-
-  while (DC0->isTransparentContext())
-    DC0 = DC0->getParent();
-  while (DC1->isTransparentContext())
-    DC1 = DC1->getParent();
-
-  if (DC0->Equals(DC1))
-    return true;
+static bool mayShadowImpl(const DeclContext *DC0, const DeclContext *DC1) {
+  return DC0 && DC0 == DC1;
+}
 
-  return false;
+static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
+  return isa<TemplateTypeParmDecl>(ND0) || isa<TemplateTypeParmDecl>(ND1);
 }
 
-static bool isMemberOf(const NamedDecl *ND, const CXXRecordDecl *RD) {
-  const DeclContext *NDParent = ND->getDeclContext();
-  if (!NDParent || !isa<CXXRecordDecl>(NDParent))
+static bool isMemberOf(const ConfusableIdentifierCheck::ContextInfo *DC0,
+                       const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->Bases.empty())
     return false;
-  if (NDParent == RD)
-    return true;
-  return !RD->forallBases(
-      [NDParent](const CXXRecordDecl *Base) { return NDParent != Base; });
+  return llvm::is_contained(DC1->Bases, DC0->PrimaryContext);
 }
 
-static bool mayShadow(const NamedDecl *ND0, const NamedDecl *ND1) {
+static bool enclosesContext(const ConfusableIdentifierCheck::ContextInfo *DC0,
+                            const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->PrimaryContext == DC1->PrimaryContext)
+    return true;
 
-  const DeclContext *DC0 = ND0->getDeclContext()->getPrimaryContext();
-  const DeclContext *DC1 = ND1->getDeclContext()->getPrimaryContext();
+  return llvm::is_contained(DC0->PrimaryContexts, DC1->PrimaryContext) ||
+         llvm::is_contained(DC1->PrimaryContexts, DC0->PrimaryContext);
+}
 
-  if (const CXXRecordDecl *RD0 = dyn_cast<CXXRecordDecl>(DC0)) {
-    RD0 = RD0->getDefinition();
-    if (RD0 && ND1->getAccess() != AS_private && isMemberOf(ND1, RD0))
-      return true;
-  }
-  if (const CXXRecordDecl *RD1 = dyn_cast<CXXRecordDecl>(DC1)) {
-    RD1 = RD1->getDefinition();
-    if (RD1 && ND0->getAccess() != AS_private && isMemberOf(ND0, RD1))
-      return true;
+static bool mayShadow(const NamedDecl *ND0,
+                      const ConfusableIdentifierCheck::ContextInfo *DC0,
+                      const NamedDecl *ND1,
+                      const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (!DC0->Bases.empty() && ND1->getAccess() != AS_private &&
+      isMemberOf(DC1, DC0))
+  if (!DC1->Bases.empty() && ND0->getAccess() != AS_private &&
+      isMemberOf(DC0, DC1))
+
+  return enclosesContext(DC0, DC1) &&
+         (mayShadowImpl(ND0, ND1) || mayShadowImpl(DC0->NonTransparentContext,
+                                                   DC1->NonTransparentContext));
+}
+
+const ConfusableIdentifierCheck::ContextInfo *
+ConfusableIdentifierCheck::getContextInfo(const DeclContext *DC) {
+  const DeclContext *PrimaryContext = DC->getPrimaryContext();
+  auto It = ContextInfos.find(PrimaryContext);
+  if (It != ContextInfos.end())
+    return &It->second;
+
+  ContextInfo &Info = ContextInfos[PrimaryContext];
+  Info.PrimaryContext = PrimaryContext;
+  Info.NonTransparentContext = PrimaryContext;
+
+  while (Info.NonTransparentContext->isTransparentContext()) {
+    Info.NonTransparentContext = Info.NonTransparentContext->getParent();
+    if (!Info.NonTransparentContext)
+      break;
   }
 
-  if (DC0->Encloses(DC1))
-    return mayShadowImpl(ND0, ND1);
-  if (DC1->Encloses(DC0))
-    return mayShadowImpl(ND1, ND0);
+  if (Info.NonTransparentContext)
+    Info.NonTransparentContext =
+        Info.NonTransparentContext->getPrimaryContext();
+
+  while (DC) {
+    if (!isa<LinkageSpecDecl>(DC) && !isa<ExportDecl>(DC))
+      Info.PrimaryContexts.push_back(DC->getPrimaryContext());
+    DC = DC->getParent();
+  }
+
+  if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(PrimaryContext)) {
+    RD = RD->getDefinition();
+    if (RD) {
+      Info.Bases.push_back(RD);
+      RD->forallBases([&](const CXXRecordDecl *Base) {
+        Info.Bases.push_back(Base);
         return false;
+      });
+    }
+  }
+
+  return &Info;
 }
 
 void ConfusableIdentifierCheck::check(
     const ast_matchers::MatchFinder::MatchResult &Result) {
   if (const auto *ND = Result.Nodes.getNodeAs<NamedDecl>("nameddecl")) {
     if (IdentifierInfo *NDII = ND->getIdentifier()) {
+      const ContextInfo *Info = getContextInfo(ND->getDeclContext());
       StringRef NDName = NDII->getName();
-      llvm::SmallVector<const NamedDecl *> &Mapped = Mapper[skeleton(NDName)];
-      for (const NamedDecl *OND : Mapped) {
-        const IdentifierInfo *ONDII = OND->getIdentifier();
-        if (mayShadow(ND, OND)) {
+      llvm::SmallVector<Entry> &Mapped = Mapper[skeleton(NDName)];
+      for (const Entry &E : Mapped) {
+        const IdentifierInfo *ONDII = E.Declaration->getIdentifier();
+        if (mayShadow(ND, Info, E.Declaration, E.Info)) {
           StringRef ONDName = ONDII->getName();
           if (ONDName != NDName) {
-            diag(ND->getLocation(), "%0 is confusable with %1") << ND << OND;
-            diag(OND->getLocation(), "other declaration found here",
+            diag(ND->getLocation(), "%0 is confusable with %1")
+                << ND << E.Declaration;
+            diag(E.Declaration->getLocation(), "other declaration found here",
                  DiagnosticIDs::Note);
           }
         }
       }
-      Mapped.push_back(ND);
+      Mapped.push_back({ND, Info});
     }
   }
 }
 
 void ConfusableIdentifierCheck::registerMatchers(
     ast_matchers::MatchFinder *Finder) {
   Finder->addMatcher(ast_matchers::namedDecl().bind("nameddecl"), this);
 }
 
 } // namespace clang::tidy::misc