[clangd] Compute scopes eagerly in IncludeFixer

[ilya-biryukov]

Summary

Computing lazily leads to crashes. In particular, computing scopes may
produce diagnostics (from inside template instantiations) and we
currently do it when processing another diagnostic, which leads to
crashes.

Moreover, we remember and access 'Scope*' when computing scopes. This
might lead to invalid memory access if the Scope is deleted by the time
we run the delayed computation. We did not actually construct an example
when this happens, though.

From the VCS and review history, it seems the optimization was
introduced in the initial version without a mention of any performance
benchmarks justifying the performance gains. This led me to a
conclusion that the optimization was premature, so removing it to avoid
crashes seems like the right trade-off at that point.

[ilya-biryukov]

• Make sure the test actually runs IncludeFixer.cpp

clang-tools-extra/clangd/IncludeFixer.h

private:
   std::vector<Fix> fixIncompleteType(const Type &T) const;
 
   /// Generates header insertion fixes for all symbols. Fixes are deduplicated.
   std::vector<Fix> fixesForSymbols(const SymbolSlab &Syms) const;
 
   struct UnresolvedName {
     std::string Name;   // E.g. "X" in foo::X.
     SourceLocation Loc; // Start location of the unresolved name.
-    // Lazily get the possible scopes of the unresolved name. `Sema` must be
-    // alive when this is called.
-    std::function<std::vector<std::string>()> GetScopes;
+    std::vector<std::string> Scopes; // Namespace scopes we should search in.
   };
 
   /// Records the last unresolved name seen by Sema.
   class UnresolvedNameRecorder;
 
   /// Attempts to fix the unresolved name associated with the current
   /// diagnostic. We assume a diagnostic is caused by a unresolved name when
   /// they have the same source location and the unresolved name is the last

clang-tools-extra/clangd/IncludeFixer.cpp

 #include "Diagnostics.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "index/Index.h"
 #include "index/Symbol.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
+#include "clang/AST/DeclarationName.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticSema.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/Scope.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Sema/TypoCorrection.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
if (auto QualifiedByUnresolved =
       // to the extra scope.
       Result.UnresolvedScope->append((Result.Name + Split.first).str());
       Result.Name = Split.second;
     }
   }
   return Result;
 }
 
+/// Returns all namespace scopes that the unqualified lookup would visit.
+std::vector<std::string>
+collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S,
+                        Sema::LookupNameKind LookupKind) {
+  std::vector<std::string> Scopes;
+  VisitedContextCollector Collector;
+  Sem.LookupVisibleDecls(S, LookupKind, Collector,
+                         /*IncludeGlobalScope=*/false,
+                         /*LoadExternal=*/false);
+
+  Scopes.push_back("");
+  for (const auto *Ctx : Collector.takeVisitedContexts()) {
+    if (isa<NamespaceDecl>(Ctx))
+      Scopes.push_back(printNamespaceScope(*Ctx));
+  }
+  return Scopes;
+}
+
 class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
 public:
   UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
       : LastUnresolvedName(LastUnresolvedName) {}
 
   void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
 
   // Captures the latest typo and treat it as an unresolved name that can
   // potentially be fixed by adding #includes.
   TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
                              Scope *S, CXXScopeSpec *SS,
                              CorrectionCandidateCallback &CCC,
                              DeclContext *MemberContext, bool EnteringContext,
                              const ObjCObjectPointerType *OPT) override {
     assert(SemaPtr && "Sema must have been set.");
     if (SemaPtr->isSFINAEContext())
       return TypoCorrection();
     if (!isInsideMainFile(Typo.getLoc(), SemaPtr->SourceMgr))
       return clang::TypoCorrection();
 
-    // This is not done lazily because `SS` can get out of scope and it's
-    // relatively cheap.
     auto Extracted = extractUnresolvedNameCheaply(
         SemaPtr->SourceMgr, Typo, SS, SemaPtr->LangOpts,
         static_cast<Sema::LookupNameKind>(LookupKind) ==
             Sema::LookupNameKind::LookupNestedNameSpecifierName);
     if (!Extracted)
       return TypoCorrection();
-    auto CheapUnresolved = std::move(*Extracted);
+
     UnresolvedName Unresolved;
-    Unresolved.Name = CheapUnresolved.Name;
+    Unresolved.Name = Extracted->Name;
     Unresolved.Loc = Typo.getBeginLoc();
-
-    if (!CheapUnresolved.ResolvedScope && !S) // Give up if no scope available.
+    if (!Extracted->ResolvedScope && !S) // Give up if no scope available.
       return TypoCorrection();
 
-    auto *Sem = SemaPtr; // Avoid capturing `this`.
-    Unresolved.GetScopes = [Sem, CheapUnresolved, S, LookupKind]() {
-      std::vector<std::string> Scopes;
-      if (CheapUnresolved.ResolvedScope) {
-        Scopes.push_back(*CheapUnresolved.ResolvedScope);
-      } else {
-        assert(S);
-        // No scope specifier is specified. Collect all accessible scopes in the
-        // context.
-        VisitedContextCollector Collector;
-        Sem->LookupVisibleDecls(
-            S, static_cast<Sema::LookupNameKind>(LookupKind), Collector,
-            /*IncludeGlobalScope=*/false,
-            /*LoadExternal=*/false);
-
-        Scopes.push_back("");
-        for (const auto *Ctx : Collector.takeVisitedContexts())
-          if (isa<NamespaceDecl>(Ctx))
-            Scopes.push_back(printNamespaceScope(*Ctx));
-      }
+    if (Extracted->ResolvedScope)
+      Unresolved.Scopes.push_back(*Extracted->ResolvedScope);
+    else // no qualifier or qualifier is unresolved.
+      Unresolved.Scopes = collectAccessibleScopes(
+          *SemaPtr, Typo, S, static_cast<Sema::LookupNameKind>(LookupKind));
+
+    if (Extracted->UnresolvedScope) {
+      for (std::string &Scope : Unresolved.Scopes)
+        Scope += *Extracted->UnresolvedScope;
 
-      if (CheapUnresolved.UnresolvedScope)
-        for (auto &Scope : Scopes)
-          Scope.append(*CheapUnresolved.UnresolvedScope);
-      return Scopes;
-    };
     LastUnresolvedName = std::move(Unresolved);
 
     // Never return a valid correction to try to recover. Our suggested fixes
     // always require a rebuild.
     return TypoCorrection();
   }
 
 private:
   Sema *SemaPtr = nullptr;
 
   llvm::Optional<UnresolvedName> &LastUnresolvedName;
 };
 
 llvm::IntrusiveRefCntPtr<ExternalSemaSource>
 IncludeFixer::unresolvedNameRecorder() {
   return new UnresolvedNameRecorder(LastUnresolvedName);
 }
 
 std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
   assert(LastUnresolvedName.hasValue());
   auto &Unresolved = *LastUnresolvedName;
-  std::vector<std::string> Scopes = Unresolved.GetScopes();
   vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
-       Unresolved.Name, llvm::join(Scopes.begin(), Scopes.end(), ", "));
+       Unresolved.Name, llvm::join(Unresolved.Scopes, ", "));
 
   FuzzyFindRequest Req;
   Req.AnyScope = false;
   Req.Query = Unresolved.Name;
-  Req.Scopes = Scopes;
+  Req.Scopes = Unresolved.Scopes;
   Req.RestrictForCodeCompletion = true;
   Req.Limit = 100;
 
   if (llvm::Optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
     return fixesForSymbols(**Syms);
 
   return {};
 }

clang-tools-extra/clangd/unittests/DiagnosticsTests.cpp

namespace c {
 
   EXPECT_THAT(TU.build().getDiagnostics(),
               UnorderedElementsAre(AllOf(
                   Diag(Test.range(), "no type named 'X' in namespace 'a'"),
                   WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
                               "Add include \"x.h\" for symbol a::X")))));
 }
 
+TEST(IncludeFixerTest, NoCrashOnTemplateInstantiations) {
+  Annotations Test(R"cpp(
+    template <typename T> struct Templ {
+      template <typename U>
+      typename U::type operator=(const U &);
+    };
+
+    struct A {
+      Templ<char> s;
+      A() { [[a]]; } // this caused crashes if we compute scopes lazily.
+    };
+  )cpp");
+
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol({});
+  TU.ExternalIndex = Index.get();
+
+  EXPECT_THAT(TU.build().getDiagnostics(),
+              ElementsAre(Diag(Test.range(), "use of undeclared identifier 'a'")));
+}
+
 TEST(DiagsInHeaders, DiagInsideHeader) {
   Annotations Main(R"cpp(
     #include [["a.h"]]
     void foo() {})cpp");
   Annotations Header("[[no_type_spec]];");
   TestTU TU = TestTU::withCode(Main.code());
   TU.AdditionalFiles = {{"a.h", Header.code()}};
   EXPECT_THAT(TU.build().getDiagnostics(),