[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

208

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

211–216

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::)

212

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

Consider calling this UnresolvedSpecifiedScope

213

nit: qualier -> qualifier
accissible -> accessible

216

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.

235

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::".

315

identifiers

320

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

235

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

189

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

190

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 ::?

230

Unrsolved -> Unresolved

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

249

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.

255

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

[jkorous]

Hi Eric, I have just couple details.

clangd/IncludeFixer.cpp

187

qualfied -> qualified

192

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

215

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

250

Does this work with anonymous namespaces?

262

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

270

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

190

Good idea. Lexer is a better option.

249

Sounds good. Thanks!

250

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

255

Indeed. Thanks for the catch!

270

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.

[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/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)) {
       }
     }
   }
   return Fixes;
 }
 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".
-
+    auto &SM = SemaPtr->SourceMgr;
+    bool Invalid = false;
+    llvm::StringRef Code =
+        SM.getBufferData(SM.getDecomposedLoc(Typo.getLoc()).first, &Invalid);
+    assert(!Invalid);
     // 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;
+    // Extra scope to append to the query scopes. This is useful, for example,
+    // when the unresolved name is a qualier, in which case we use the name that
+    // comes after it as the name to resolve and use the qualifier as the extra
+    // scope in the accissible scopes.
+    llvm::Optional<std::string> ExtraScope;
     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 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();
+          if (llvm::StringRef(SpecifiedNS).endswith(Spelling))
+            SpecifiedScope = SpecifiedNS;
           else
+            ExtraScope = Spelling;
+        } 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();
 
+    if (static_cast<Sema::LookupNameKind>(LookupKind) ==
+        Sema::LookupNameKind::LookupNestedNameSpecifierName) {
+      // 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(Unresolved.Loc) +
+                                              Unresolved.Name.size())) {
+        auto Split = splitQualifiedName(*QualifiedByUnresolved);
+        if (!ExtraScope)
+          ExtraScope.emplace();
+        // If ExtraScope 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.
+        ExtraScope->append((Unresolved.Name + Split.first).str());
+        Unresolved.Name = Split.second;
+      }
+    }
     auto *Sem = SemaPtr; // Avoid capturing `this`.
-    Unresolved.GetScopes = [Sem, SpecifiedScope, S, LookupKind]() {
+    Unresolved.GetScopes = [Sem, SpecifiedScope, S, LookupKind, ExtraScope]() {
       std::vector<std::string> Scopes;
       if (SpecifiedScope) {
         Scopes.push_back(*SpecifiedScope);
       } 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 (ExtraScope)
+        for (auto &Scope : Scopes)
+          Scope.append(*ExtraScope);
       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:
+  // Returns the idenfiers 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) const {
+    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();
+  }
   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(), ", "));
+  vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}] (loc={2})",
+       Unresolved.Name, llvm::join(Scopes.begin(), Scopes.end(), ", "),
+       Unresolved.Loc.getRawEncoding());
 
   FuzzyFindRequest Req;
   Req.AnyScope = false;
   Req.Query = Unresolved.Name;
   Req.Scopes = Scopes;
   Req.RestrictForCodeCompletion = true;
   Req.Limit = 100;
 

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")))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang