[clangd] Handle unresolved scope specifier when fixing includes.

[ioeric]

Summary

In the following examples, "clangd" is unresolved, and the fixer will try to fix
include for clang::clangd; however, clang::clangd::X is usually intended. So
when handling a qualifier that is unresolved, we change the unresolved name and
scopes so that the fixer will fix "clang::clangd::X" in the following example.

  namespace clang {
  	clangd::X
	~~~~~~
  }
  // or
  clang::clangd::X
         ~~~~~~

[ioeric]

• Remove unintended change.

[sammccall]

clangd/IncludeFixer.cpp

320–321

We can be more precise about this now I think: IIUC this is the resolved specified scope.
in two senses: it's the part of what was typed that was resolved, and it's in its resolved form not its typed form (think namespace clang { clangd::x } --> clang::clangd::)

321

nit: I don't think this is an example, it's the only case right?

Consider calling this UnresolvedSpecifiedScope

322

nit: qualier -> qualifier
accissible -> accessible

324

No idea when this can be invalid, but we could just return here?

325

I'm a bit concerned about how this mixes extraction of scopes from the source code/AST (which is now *really* complicated) with building the query and assembling the correction.

Can we reasonably extract the former to a helper function? Not sure exactly what the signature would be, but it would be helpful to find out.

The other thing is I think this has a lot in common with the scope-wrangling code in CodeComplete, and could *maybe* be unified a bit once isolated.

334

hmm, won't this heuristic have false positives?

// indexed-header.h
namespace a { int X; }

// main-file.cc
namespace b = a;
namespace c { int Y = b::x; }

I worry spelling is going to be "b::" here, while SpecifiedNS is going to be "a::".

372

identifiers

377

this only depends on the params right?
This could be static or even moved out of the class.

[ioeric]

• address review comments

[ioeric]

clangd/IncludeFixer.cpp

334

Thanks for pointing this out! I completely missed the namespace alias case. Fixed and added a test.

[sammccall]

Thanks! The layering is *much* clearer now.
I can still suggest a couple of tweaks, but they're pretty much cosmetic.

clangd/IncludeFixer.cpp

190

you're showing a range here, it should be a point though?

191

this isn't wrong per se (conservative, bails out e.g. on unicode)
But is it much harder to call Lexer::findNextToken twice and expect a raw identifier and ::?

231

Unrsolved -> Unresolved

emphasis might be clearer as UnresolvedIsSpecifier - there's always an unresolved entity, the boolean is indicating that it's a specifier

256

I don't think this vlog is useful as-is (quite far down the stack with no context)
Did you intend to remove it?

322

Following up on our offline discussion :-)
I think that since extractSpecifiedScopes can want to modify the name, we should just expand that function's signature/responsibility to always determine the name.

So we'd pass the const DeclarationNameInfo& to extractSpecifiedScopes, and it would return a struct {optional<string> ResolvedScope; optional<string> UnresolvedScope; string Name}.
Maybe need to call them CheapUnresolvedName/extractUnresolvedNameCheaply or similar.
But I think the code change is small.

[jkorous]

Hi Eric, I have just couple details.

clangd/IncludeFixer.cpp

188

qualfied -> qualified

193

It seems to me that calling Lexer would be better indeed.

216

Maybe move the comment about work done eagerly to the function?

251

Does this work with anonymous namespaces?

263

I'd personally prefer to add parentheses here to have the if/else if/else consistent. Up to you though.

271

Is the term qualifier applicable here? (Honest question.)

It seems like C++ grammar uses specifier (same as you in IsUnrsolvedSpecifier )
http://www.nongnu.org/hcb/#nested-name-specifier

unittests/clangd/DiagnosticsTests.cpp

452

If (see above) we decide qualifier should be replaced by specifier or smth else please replace here as well, otherwise ignore this.

[ioeric]

• address review comment

clangd/IncludeFixer.cpp

191

Good idea. Lexer is a better option.

251

I'm not sure... how do you use an anonymous namespace as a scope specifier?

256

Indeed. Thanks for the catch!

271

You've raised a good point. We've been using specifier and qualifier interchangeably in the project. But specifier does seem to be a more appropriate name to use. I've fixed uses in this file. Uses in other files probably need a separate cleanup.

322

Sounds good. Thanks!

[ioeric]

• minor cleanup

clangd/IncludeFixer.cpp

 #include "Trace.h"
 #include "index/Index.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticSema.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.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/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
for (const auto &Inc : getRankedIncludes(Sym)) {
       } else {
         vlog("Failed to calculate include insertion for {0} into {1}: {2}",
              File, Inc, ToInclude.takeError());
       }
     }
   }
   return Fixes;
 }
+
+// Returns the identifiers qualified by an unresolved name. \p Offset is the
+// first character after the unresolved name in \p Code. For the example below,
+// this returns "::X::Y" that is qualfied by unresolved name "clangd":
+//     clang::clangd::X::Y
+//            ~~~~~~
+llvm::Optional<std::string> qualifiedByUnresolved(llvm::StringRef Code,
+                                                  size_t Offset) {
+  auto IsValidIdentifierChar = [](char C) {
+    return ((C >= 'a' && C <= 'z') || (C >= 'A' && C <= 'Z') ||
+            (C >= '0' && C <= '9') || (C == '_'));
+  };
+  auto Truncated = Code.substr(Offset);
+  size_t ResultLen = 0;
+  while (Truncated.consume_front("::")) {
+    size_t P = 0;
+    for (; P < Truncated.size() && IsValidIdentifierChar(Truncated[P]); ++P) {
+    }
+    if (P == 0) // Stop if there's nothing after ::
+      break;
+    ResultLen += P + 2; // include "::".
+    Truncated = Truncated.drop_front(P);
+  }
+  if (ResultLen == 0)
+    return llvm::None;
+  return Code.substr(Offset, ResultLen).str();
+}
+
+struct SpecifiedScopes {
+  // This is the part of what was typed that was resolved, and it's in its
+  // resolved form not its typed form (think `namespace clang { clangd::x }` -->
+  // `clang::clangd::`). This is not done lazily because `SS` can get out of
+  // scope and it's relatively cheap.
+  llvm::Optional<std::string> Resolved;
+
+  // Unresolved part of the scope. When the unresolved name is a qualifier, we
+  // use the name that comes after it as the alternative name to resolve and use
+  // the qualifier as the extra scope in the accessible scopes.
+  llvm::Optional<std::string> Unresolved;
+  llvm::Optional<std::string> AlternativeUnresolvedName;
+};
+
+// Extracts the specified scopes around an unresolved name.
+// FIXME: try to merge this with the scope-wrangling code in CodeComplete.
+llvm::Optional<SpecifiedScopes> extractSpecifiedScopes(
+    const SourceManager &SM, CXXScopeSpec *SS, llvm::StringRef UnresolvedName,
+    SourceLocation UnresolvedLoc, bool IsUnrsolvedSpecifier) {
+  bool Invalid = false;
+  llvm::StringRef Code =
+      SM.getBufferData(SM.getDecomposedLoc(UnresolvedLoc).first, &Invalid);
+  if (Invalid)
+    return llvm::None;
+  SpecifiedScopes Result;
+  if (SS && SS->isNotEmpty()) { // "::" or "ns::"
+    if (auto *Nested = SS->getScopeRep()) {
+      if (Nested->getKind() == NestedNameSpecifier::Global)
+        Result.Resolved = "";
+      else if (const auto *NS = Nested->getAsNamespace()) {
+        auto SpecifiedNS = printNamespaceScope(*NS);
+
+        // Check the qualifier spelled in the source.
+        // If the resolved scope doesn't end with the spelled scope. The
+        // resolved scope can come from a sema typo correction. For example,
+        // sema assumes that "clangd::" is a typo of "clang::" and uses
+        // "clang::" as the specified scope in:
+        //     namespace clang { clangd::X; }
+        // In this case, we use the "typo" qualifier as extra scope instead
+        // of using the scope assumed by sema.
+        auto B = SM.getFileOffset(SS->getBeginLoc());
+        auto E = SM.getFileOffset(SS->getEndLoc());
+        std::string Spelling = (Code.substr(B, E - B) + "::").str();
+        vlog("Spelling scope: {0}, SpecifiedNS: {1}", Spelling, SpecifiedNS);
+        if (llvm::StringRef(SpecifiedNS).endswith(Spelling))
+          Result.Resolved = SpecifiedNS;
+        else
+          Result.Unresolved = Spelling;
+      } else if (const auto *ANS = Nested->getAsNamespaceAlias())
+        Result.Resolved = printNamespaceScope(*ANS->getNamespace());
+      else
+        // We don't fix symbols in scopes that are not top-level e.g. class
+        // members, as we don't collect includes for them.
+        return llvm::None;
+    }
+  }
+
+  if (IsUnrsolvedSpecifier) {
+    // If the unresolved name is a qualifier e.g.
+    //      clang::clangd::X
+    //             ~~~~~~
+    // We try to resolve clang::clangd::X instead of clang::clangd.
+    // FIXME: We won't be able to fix include if the qualifier is what we
+    // should resolve (e.g. it's a class scope specifier). Collecting include
+    // headers for nested types could make this work.
+
+    // Not using the end location as it doesn't always point to the end of
+    // identifier.
+    if (auto QualifiedByUnresolved = qualifiedByUnresolved(
+            Code, SM.getFileOffset(UnresolvedLoc) + UnresolvedName.size())) {
+      auto Split = splitQualifiedName(*QualifiedByUnresolved);
+      if (!Result.Unresolved)
+        Result.Unresolved.emplace();
+      // If UnresolvedSpecifiedScope is already set, we simply append the
+      // extra scope. Suppose the unresolved name is "index" in the following
+      // example:
+      //   namespace clang {  clangd::index::X; }
+      //                      ~~~~~~  ~~~~~
+      // "clangd::" is assumed to be clang:: by Sema, and we would have used
+      // it as extra scope. With "index" being a qualifier, we append
+      // "index::" to the extra scope.
+      Result.Unresolved->append((UnresolvedName + Split.first).str());
+      Result.AlternativeUnresolvedName = Split.second;
+    }
+  }
+  return Result;
+}
+
 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 (!SemaPtr->SourceMgr.isWrittenInMainFile(Typo.getLoc()))
       return clang::TypoCorrection();
 
-    // FIXME: support invalid scope before a type name. In the following
-    // example, namespace "clang::tidy::" hasn't been declared/imported.
-    //    namespace clang {
-    //    void f() {
-    //      tidy::Check c;
-    //      ~~~~
-    //      // or
-    //      clang::tidy::Check c;
-    //             ~~~~
-    //    }
-    //    }
-    // For both cases, the typo and the diagnostic are both on "tidy", and no
-    // diagnostic is generated for "Check". However, what we want to fix is
-    // "clang::tidy::Check".
-
-    // Extract the typed scope. This is not done lazily because `SS` can get
-    // out of scope and it's relatively cheap.
-    llvm::Optional<std::string> SpecifiedScope;
-    if (SS && SS->isNotEmpty()) { // "::" or "ns::"
-      if (auto *Nested = SS->getScopeRep()) {
-        if (Nested->getKind() == NestedNameSpecifier::Global)
-          SpecifiedScope = "";
-        else if (const auto *NS = Nested->getAsNamespace())
-          SpecifiedScope = printNamespaceScope(*NS);
-        else
-          // We don't fix symbols in scopes that are not top-level e.g. class
-          // members, as we don't collect includes for them.
-          return TypoCorrection();
-      }
-    }
-    if (!SpecifiedScope && !S) // Give up if no scope available.
-      return TypoCorrection();
-
     UnresolvedName Unresolved;
     Unresolved.Name = Typo.getAsString();
     Unresolved.Loc = Typo.getBeginLoc();
 
+    auto ExtractedScopes = extractSpecifiedScopes(
+        SemaPtr->SourceMgr, SS, Unresolved.Name, Unresolved.Loc,
+        static_cast<Sema::LookupNameKind>(LookupKind) ==
+            Sema::LookupNameKind::LookupNestedNameSpecifierName);
+    if (!ExtractedScopes)
+      return TypoCorrection();
+    auto SpecifiedScopes = std::move(*ExtractedScopes);
+    if (SpecifiedScopes.AlternativeUnresolvedName)
+      Unresolved.Name = *SpecifiedScopes.AlternativeUnresolvedName;
+
+    if (!SpecifiedScopes.Resolved && !S) // Give up if no scope available.
+      return TypoCorrection();
+
     auto *Sem = SemaPtr; // Avoid capturing `this`.
-    Unresolved.GetScopes = [Sem, SpecifiedScope, S, LookupKind]() {
+    Unresolved.GetScopes = [Sem, SpecifiedScopes, S, LookupKind]() {
       std::vector<std::string> Scopes;
-      if (SpecifiedScope) {
-        Scopes.push_back(*SpecifiedScope);
+      if (SpecifiedScopes.Resolved) {
+        Scopes.push_back(*SpecifiedScopes.Resolved);
       } else {
         assert(S);
         // No scope qualifier 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 (SpecifiedScopes.Unresolved)
+        for (auto &Scope : Scopes)
+          Scope.append(*SpecifiedScopes.Unresolved);
       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();

unittests/clangd/DiagnosticsTests.cpp

 #include "llvm/Support/ScopedPrinter.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+using testing::_;
 using testing::ElementsAre;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
 testing::Matcher<const Diag &> WithFix(testing::Matcher<Fix> FixMatcher) {
   return Field(&Diag::Fixes, ElementsAre(FixMatcher));
EXPECT_THAT(TU.build().getDiagnostics(),
                        "member access into incomplete type 'ns::X'")));
 }
 
 TEST(IncludeFixerTest, Typo) {
   Annotations Test(R"cpp(
 $insert[[]]namespace ns {
 void foo() {
   $unqualified1[[X]] x;
+  // No fix if the unresolved type is used as qualifier. (ns::)X::Nested will be
+  // considered the unresolved type.
   $unqualified2[[X]]::Nested n;
 }
 }
 void bar() {
   ns::$qualified1[[X]] x; // ns:: is valid.
   ns::$qualified2[[X]](); // Error: no member in namespace
 
   ::$global[[Global]] glob;
 }
   )cpp");
   auto TU = TestTU::withCode(Test.code());
   auto Index = buildIndexWithSymbol(
       {SymbolWithHeader{"ns::X", "unittest:///x.h", "\"x.h\""},
        SymbolWithHeader{"Global", "unittest:///global.h", "\"global.h\""}});
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(
       TU.build().getDiagnostics(),
       UnorderedElementsAre(
           AllOf(Diag(Test.range("unqualified1"), "unknown type name 'X'"),
                 WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
                             "Add include \"x.h\" for symbol ns::X"))),
-          AllOf(Diag(Test.range("unqualified2"),
-                     "use of undeclared identifier 'X'"),
-                WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
-                            "Add include \"x.h\" for symbol ns::X"))),
+          Diag(Test.range("unqualified2"), "use of undeclared identifier 'X'"),
           AllOf(Diag(Test.range("qualified1"),
                      "no type named 'X' in namespace 'ns'"),
                 WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
                             "Add include \"x.h\" for symbol ns::X"))),
           AllOf(Diag(Test.range("qualified2"),
                      "no member named 'X' in namespace 'ns'"),
                 WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
                             "Add include \"x.h\" for symbol ns::X"))),
auto Index = buildIndexWithSymbol(
       SymbolWithHeader{"na::X", "unittest:///a.h", "\"a.h\""});
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(
       TU.build().getDiagnostics(),
       UnorderedElementsAre(Diag(Test.range(), "no member named 'xy' in 'X'")));
 }
 
+TEST(IncludeFixerTest, UnresolvedNameAsQualifier) {
+  Annotations Test(R"cpp(
+$insert[[]]namespace ns {
+}
+void g() {  ns::$[[scope]]::X_Y();  }
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol(
+      SymbolWithHeader{"ns::scope::X_Y", "unittest:///x.h", "\"x.h\""});
+  TU.ExternalIndex = Index.get();
+
+  EXPECT_THAT(
+      TU.build().getDiagnostics(),
+      UnorderedElementsAre(AllOf(
+          Diag(Test.range(), "no member named 'scope' in namespace 'ns'"),
+          WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
+                      "Add include \"x.h\" for symbol ns::scope::X_Y")))));
+}
+
+TEST(IncludeFixerTest, UnresolvedQualifierWithSemaCorrection) {
+  Annotations Test(R"cpp(
+$insert[[]]namespace clang {
+void f() {
+  // "clangd::" will be corrected to "clang::" by Sema.
+  $q1[[clangd]]::$x[[X]] x;
+  $q2[[clangd]]::$ns[[ns]]::Y y;
+}
+}
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol(
+      {SymbolWithHeader{"clang::clangd::X", "unittest:///x.h", "\"x.h\""},
+       SymbolWithHeader{"clang::clangd::ns::Y", "unittest:///y.h", "\"y.h\""}});
+  TU.ExternalIndex = Index.get();
+
+  EXPECT_THAT(
+      TU.build().getDiagnostics(),
+      UnorderedElementsAre(
+          AllOf(
+              Diag(Test.range("q1"), "use of undeclared identifier 'clangd'; "
+                                     "did you mean 'clang'?"),
+              WithFix(_, // change clangd to clang
+                      Fix(Test.range("insert"), "#include \"x.h\"\n",
+                          "Add include \"x.h\" for symbol clang::clangd::X"))),
+          AllOf(
+              Diag(Test.range("x"), "no type named 'X' in namespace 'clang'"),
+              WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
+                          "Add include \"x.h\" for symbol clang::clangd::X"))),
+          AllOf(
+              Diag(Test.range("q2"), "use of undeclared identifier 'clangd'; "
+                                     "did you mean 'clang'?"),
+              WithFix(
+                  _, // change clangd to clangd
+                  Fix(Test.range("insert"), "#include \"y.h\"\n",
+                      "Add include \"y.h\" for symbol clang::clangd::ns::Y"))),
+          AllOf(Diag(Test.range("ns"),
+                     "no member named 'ns' in namespace 'clang'"),
+                WithFix(Fix(
+                    Test.range("insert"), "#include \"y.h\"\n",
+                    "Add include \"y.h\" for symbol clang::clangd::ns::Y")))));
+}
+TEST(IncludeFixerTest, SpecifiedScopeIsNamespaceAlias) {
+  Annotations Test(R"cpp(
+$insert[[]]namespace a {}
+namespace b = a;
+namespace c {
+  b::$[[X]] x;
+}
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol(
+      SymbolWithHeader{"a::X", "unittest:///x.h", "\"x.h\""});
+  TU.ExternalIndex = Index.get();
+
+  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")))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang