[clangd] Make output order of allTargetDecls deterministic

[kadircet]

Summary

Makes use of insertion order to stabilize output for multiple decls.

Fixes https://bugs.llvm.org/show_bug.cgi?id=44564

[merge_guards_bot]

Unit tests: pass. 61895 tests passed, 0 failed and 782 were skipped.

clang-tidy: unknown.

clang-format: pass.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[sammccall]

clang-tools-extra/clangd/FindTarget.cpp

202

why two maps vs map to pair<size_t, RelSet> here? Seems a little inefficient/untidy

[kadircet]

• Address comments

[merge_guards_bot]

Unit tests: pass. 61912 tests passed, 0 failed and 783 were skipped.

clang-tidy: unknown.

clang-format: pass.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[sammccall]

clang-tools-extra/clangd/FindTarget.cpp

224

no need for lookups I think

Result.resize(Decls.size());
for (auto& Elem : Decls)
  Result[Elem.second.second] = {Elem.first, Elem.second.first};

[kadircet]

• Get rid of redundant sorting step

clang-tools-extra/clangd/FindTarget.cpp

224

ah right, sorry I was in a rush :/

[merge_guards_bot]

Unit tests: pass. 61912 tests passed, 0 failed and 783 were skipped.

clang-tidy: unknown.

clang-format: pass.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

clang-tools-extra/clangd/FindTarget.cpp

 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <utility>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 using ast_type_traits::DynTypedNode;
 
 LLVM_ATTRIBUTE_UNUSED std::string
 nodeToString(const ast_type_traits::DynTypedNode &N) {
const Type *getPointeeType(const Type *T) {
   if (TST->getNumArgs() == 0)
     return nullptr;
   const TemplateArgument &FirstArg = TST->getArg(0);
   if (FirstArg.getKind() != TemplateArgument::Type)
     return nullptr;
   return FirstArg.getAsType().getTypePtrOrNull();
 }
 
+const NamedDecl *getTemplatePattern(const NamedDecl *D) {
+  if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) {
+    return CRD->getTemplateInstantiationPattern();
+  } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
+    return FD->getTemplateInstantiationPattern();
+  } else if (auto *VD = dyn_cast<VarDecl>(D)) {
+    // Hmm: getTIP returns its arg if it's not an instantiation?!
+    VarDecl *T = VD->getTemplateInstantiationPattern();
+    return (T == D) ? nullptr : T;
+  } else if (const auto *ED = dyn_cast<EnumDecl>(D)) {
+    return ED->getInstantiatedFromMemberEnum();
+  } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) {
+    if (const auto *Parent = llvm::dyn_cast<NamedDecl>(D->getDeclContext()))
+      if (const DeclContext *ParentPat =
+              dyn_cast_or_null<DeclContext>(getTemplatePattern(Parent)))
+        for (const NamedDecl *BaseND : ParentPat->lookup(D->getDeclName()))
+          if (!BaseND->isImplicit() && BaseND->getKind() == D->getKind())
+            return BaseND;
+  } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) {
+    if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) {
+      if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) {
+        for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName()))
+          return BaseECD;
+      }
+    }
+  }
+  return nullptr;
+}
+
 // TargetFinder locates the entities that an AST node refers to.
 //
 // Typically this is (possibly) one declaration and (possibly) one type, but
 // may be more:
 //  - for ambiguous nodes like OverloadExpr
 //  - if we want to include e.g. both typedefs and the underlying type
 //
 // This is organized as a set of mutually recursive helpers for particular node

 // This affects:
 //  - DependentTemplateSpecializationType,
 //  - DependentNameType
 //  - UnresolvedUsingValueDecl
 //  - UnresolvedUsingTypenameDecl
 struct TargetFinder {
   using RelSet = DeclRelationSet;
   using Rel = DeclRelation;
-  llvm::SmallDenseMap<const NamedDecl *, RelSet> Decls;
-  RelSet Flags;
 
-  static const NamedDecl *getTemplatePattern(const NamedDecl *D) {
-    if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) {
-      return CRD->getTemplateInstantiationPattern();
-    } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
-      return FD->getTemplateInstantiationPattern();
-    } else if (auto *VD = dyn_cast<VarDecl>(D)) {
-      // Hmm: getTIP returns its arg if it's not an instantiation?!
-      VarDecl *T = VD->getTemplateInstantiationPattern();
-      return (T == D) ? nullptr : T;
-    } else if (const auto *ED = dyn_cast<EnumDecl>(D)) {
-      return ED->getInstantiatedFromMemberEnum();
-    } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) {
-      if (const auto *Parent = llvm::dyn_cast<NamedDecl>(D->getDeclContext()))
-        if (const DeclContext *ParentPat =
-                dyn_cast_or_null<DeclContext>(getTemplatePattern(Parent)))
-          for (const NamedDecl *BaseND : ParentPat->lookup(D->getDeclName()))
-            if (!BaseND->isImplicit() && BaseND->getKind() == D->getKind())
-              return BaseND;
-    } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) {
-      if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) {
-        if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) {
-          for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName()))
-            return BaseECD;
-        }
-      }
-    }
-    return nullptr;
-  }
+private:
+  llvm::SmallDenseMap<const NamedDecl *,
+                      std::pair<RelSet, /*InsertionOrder*/ size_t>>
+      Decls;
+  RelSet Flags;
 
   template <typename T> void debug(T &Node, RelSet Flags) {
     dlog("visit [{0}] {1}", Flags,
          nodeToString(ast_type_traits::DynTypedNode::create(Node)));
   }
 
   void report(const NamedDecl *D, RelSet Flags) {
     dlog("--> [{0}] {1}", Flags,
          nodeToString(ast_type_traits::DynTypedNode::create(*D)));
-    Decls[D] |= Flags;
+    auto It = Decls.try_emplace(D, std::make_pair(Flags, Decls.size()));
+    // If already exists, update the flags.
+    if (!It.second)
+      It.first->second.first |= Flags;
   }
 
 public:
+  llvm::SmallVector<std::pair<const NamedDecl *, RelSet>, 1> takeDecls() const {
+    using ValTy = std::pair<const NamedDecl *, RelSet>;
+    llvm::SmallVector<ValTy, 1> Result;
+    Result.resize(Decls.size());
+    for (const auto &Elem : Decls)
+      Result[Elem.second.second] = {Elem.first, Elem.second.first};
+    return Result;
+  }
+
   void add(const Decl *Dcl, RelSet Flags) {
     const NamedDecl *D = llvm::dyn_cast<NamedDecl>(Dcl);
     if (!D)
       return;
     debug(*D, Flags);
     if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
       D = UDD->getNominatedNamespaceAsWritten();
 
else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>())
     Finder.add(NNS, Flags);
   else if (const TypeLoc *TL = N.get<TypeLoc>())
     Finder.add(TL->getType(), Flags);
   else if (const QualType *QT = N.get<QualType>())
     Finder.add(*QT, Flags);
   else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>())
     Finder.add(CCI, Flags);
 
-  return {Finder.Decls.begin(), Finder.Decls.end()};
+  return Finder.takeDecls();
 }
 
 llvm::SmallVector<const NamedDecl *, 1>
 targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) {
   llvm::SmallVector<const NamedDecl *, 1> Result;
   for (const auto &Entry : allTargetDecls(N)) {
     if (!(Entry.second & ~Mask))
       Result.push_back(Entry.first);