[PATCH] D151051: [clang-tidy] Optimize misc-confusable-identifiers

[Piotr Zegar via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG2a84c635f2a1: [clang-tidy] Optimize 
misc-confusable-identifiers (authored by PiotrZSL).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D151051/new/

https://reviews.llvm.org/D151051

Files:
  clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
  clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h

Index: clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
===
--- clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
+++ clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
@@ -11,6 +11,7 @@
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_CONFUSABLE_IDENTIFIER_CHECK_H
 
 #include "../ClangTidyCheck.h"
+#include 
 
 namespace clang::tidy::misc {
 
@@ -26,9 +27,23 @@
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult ) override;
 
+  struct ContextInfo {
+const DeclContext *PrimaryContext;
+const DeclContext *NonTransparentContext;
+llvm::SmallVector PrimaryContexts;
+llvm::SmallVector Bases;
+  };
+
 private:
-  std::string skeleton(StringRef);
-  llvm::StringMap> Mapper;
+  struct Entry {
+const NamedDecl *Declaration;
+const ContextInfo *Info;
+  };
+
+  const ContextInfo *getContextInfo(const DeclContext *DC);
+
+  llvm::StringMap> Mapper;
+  std::unordered_map ContextInfos;
 };
 
 } // namespace clang::tidy::misc
Index: clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
===
--- clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
+++ clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
@@ -45,7 +45,7 @@
 // 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;
@@ -89,75 +89,107 @@
   return Skeleton;
 }
 
-static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
-  const DeclContext *DC0 = ND0->getDeclContext()->getPrimaryContext();
-  const DeclContext *DC1 = ND1->getDeclContext()->getPrimaryContext();
+static bool mayShadowImpl(const DeclContext *DC0, const DeclContext *DC1) {
+  return DC0 && DC0 == DC1;
+}
 
-  if (isa(ND0) || isa(ND0))
-return true;
+static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
+  return isa(ND0) || isa(ND1);
+}
 
-  while (DC0->isTransparentContext())
-DC0 = DC0->getParent();
-  while (DC1->isTransparentContext())
-DC1 = DC1->getParent();
+static bool isMemberOf(const ConfusableIdentifierCheck::ContextInfo *DC0,
+   const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->Bases.empty())
+return false;
+  return llvm::is_contained(DC1->Bases, DC0->PrimaryContext);
+}
 
-  if (DC0->Equals(DC1))
+static bool enclosesContext(const ConfusableIdentifierCheck::ContextInfo *DC0,
+const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->PrimaryContext == DC1->PrimaryContext)
 return true;
 
-  return false;
+  return llvm::is_contained(DC0->PrimaryContexts, DC1->PrimaryContext) ||
+ llvm::is_contained(DC1->PrimaryContexts, DC0->PrimaryContext);
 }
 
-static bool isMemberOf(const NamedDecl *ND, const CXXRecordDecl *RD) {
-  const DeclContext *NDParent = ND->getDeclContext();
-  if (!NDParent || !isa(NDParent))
-return false;
-  if (NDParent == RD)
+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))
 return true;
-  return !RD->forallBases(
-  [NDParent](const CXXRecordDecl *Base) { return NDParent != Base; });
+  if (!DC1->Bases.empty() && ND0->getAccess() != AS_private &&
+  isMemberOf(DC0, DC1))
+return true;
+
+  return enclosesContext(DC0, DC1) &&
+ (mayShadowImpl(ND0, ND1) || mayShadowImpl(DC0->NonTransparentContext,
+   DC1->NonTransparentContext));
 }
 
-static bool mayShadow(const NamedDecl *ND0, const NamedDecl *ND1) {
+const ConfusableIdentifierCheck::ContextInfo *
+ConfusableIdentifierCheck::getContextInfo(const DeclContext *DC) {
+  const DeclContext *PrimaryContext = DC->getPrimaryContext();
+  auto It = ContextInfos.find(PrimaryContext);
+  if (It != ContextInfos.end())
+return >second;
+
+  ContextInfo  = ContextInfos[PrimaryContext];
+  Info.PrimaryContext = PrimaryContext;
+  Info.NonTransparentContext = 

[PATCH] D151051: [clang-tidy] Optimize misc-confusable-identifiers

[serge via Phabricator via cfe-commits]

serge-sans-paille accepted this revision.
serge-sans-paille added a comment.
This revision is now accepted and ready to land.

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D151051/new/

https://reviews.llvm.org/D151051

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D151051: [clang-tidy] Optimize misc-confusable-identifiers

[Piotr Zegar via Phabricator via cfe-commits]

PiotrZSL created this revision.
PiotrZSL added reviewers: njames93, carlosgalvezp.
Herald added a subscriber: xazax.hun.
Herald added a project: All.
PiotrZSL requested review of this revision.
Herald added a project: clang-tools-extra.
Herald added a subscriber: cfe-commits.

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.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D151051

Files:
  clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
  clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h

Index: clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
===
--- clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
+++ clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.h
@@ -11,6 +11,7 @@
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_CONFUSABLE_IDENTIFIER_CHECK_H
 
 #include "../ClangTidyCheck.h"
+#include 
 
 namespace clang::tidy::misc {
 
@@ -26,9 +27,23 @@
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult ) override;
 
+  struct ContextInfo {
+const DeclContext *PrimaryContext;
+const DeclContext *NonTransparentContext;
+llvm::SmallVector PrimaryContexts;
+llvm::SmallVector Bases;
+  };
+
 private:
-  std::string skeleton(StringRef);
-  llvm::StringMap> Mapper;
+  struct Entry {
+const NamedDecl *Declaration;
+const ContextInfo *Info;
+  };
+
+  const ContextInfo *getContextInfo(const DeclContext *DC);
+
+  llvm::StringMap> Mapper;
+  std::unordered_map ContextInfos;
 };
 
 } // namespace clang::tidy::misc
Index: clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
===
--- clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
+++ clang-tools-extra/clang-tidy/misc/ConfusableIdentifierCheck.cpp
@@ -45,7 +45,7 @@
 // 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;
@@ -89,75 +89,107 @@
   return Skeleton;
 }
 
-static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
-  const DeclContext *DC0 = ND0->getDeclContext()->getPrimaryContext();
-  const DeclContext *DC1 = ND1->getDeclContext()->getPrimaryContext();
+static bool mayShadowImpl(const DeclContext *DC0, const DeclContext *DC1) {
+  return DC0 && DC0 == DC1;
+}
 
-  if (isa(ND0) || isa(ND0))
-return true;
+static bool mayShadowImpl(const NamedDecl *ND0, const NamedDecl *ND1) {
+  return isa(ND0) || isa(ND1);
+}
 
-  while (DC0->isTransparentContext())
-DC0 = DC0->getParent();
-  while (DC1->isTransparentContext())
-DC1 = DC1->getParent();
+static bool isMemberOf(const ConfusableIdentifierCheck::ContextInfo *DC0,
+   const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->Bases.empty())
+return false;
+  return llvm::is_contained(DC1->Bases, DC0->PrimaryContext);
+}
 
-  if (DC0->Equals(DC1))
+static bool enclosesContext(const ConfusableIdentifierCheck::ContextInfo *DC0,
+const ConfusableIdentifierCheck::ContextInfo *DC1) {
+  if (DC0->PrimaryContext == DC1->PrimaryContext)
 return true;
 
-  return false;
+  return llvm::is_contained(DC0->PrimaryContexts, DC1->PrimaryContext) ||
+ llvm::is_contained(DC1->PrimaryContexts, DC0->PrimaryContext);
 }
 
-static bool isMemberOf(const NamedDecl *ND, const CXXRecordDecl *RD) {
-  const DeclContext *NDParent = ND->getDeclContext();
-  if (!NDParent || !isa(NDParent))
-return false;
-  if (NDParent == RD)
+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))
 return true;
-  return !RD->forallBases(
-  [NDParent](const CXXRecordDecl *Base) { return NDParent != Base; });
+  if (!DC1->Bases.empty() && ND0->getAccess() != AS_private &&
+  isMemberOf(DC0, DC1))
+return true;
+
+  return enclosesContext(DC0, DC1) &&
+ (mayShadowImpl(ND0, ND1) || mayShadowImpl(DC0->NonTransparentContext,
+   DC1->NonTransparentContext));
 }
 
-static bool mayShadow(const