[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 ↗

(On Diff #186674)

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

211 ↗

(On Diff #186674)

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 ↗

(On Diff #186674)

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

Consider calling this UnresolvedSpecifiedScope

213 ↗

(On Diff #186674)

nit: qualier -> qualifier
accissible -> accessible

216 ↗

(On Diff #186674)

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 ↗

(On Diff #186674)

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 ↗

(On Diff #186674)

identifiers

320 ↗

(On Diff #186674)

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 ↗

(On Diff #186674)

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 ↗

(On Diff #187222)

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

191 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

Unrsolved -> Unresolved

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

256 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

qualfied -> qualified

193 ↗

(On Diff #187222)

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

216 ↗

(On Diff #187222)

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

251 ↗

(On Diff #187222)

Does this work with anonymous namespaces?

263 ↗

(On Diff #187222)

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

271 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

Good idea. Lexer is a better option.

251 ↗

(On Diff #187222)

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

256 ↗

(On Diff #187222)

Indeed. Thanks for the catch!

271 ↗

(On Diff #187222)

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 ↗

(On Diff #187222)

Sounds good. Thanks!

[ioeric]

• minor cleanup

clang-tools-extra/trunk/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/LangOptions.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TokenKinds.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 Loc is the
+// start location of the unresolved name. For the example below, this returns
+// "::X::Y" that is qualified by unresolved name "clangd":
+//     clang::clangd::X::Y
+//            ~
+llvm::Optional<std::string> qualifiedByUnresolved(const SourceManager &SM,
+                                                  SourceLocation Loc,
+                                                  const LangOptions &LangOpts) {
+  std::string Result;
+
+  SourceLocation NextLoc = Loc;
+  while (auto CCTok = Lexer::findNextToken(NextLoc, SM, LangOpts)) {
+    if (!CCTok->is(tok::coloncolon))
+      break;
+    auto IDTok = Lexer::findNextToken(CCTok->getLocation(), SM, LangOpts);
+    if (!IDTok || !IDTok->is(tok::raw_identifier))
+      break;
+    Result.append(("::" + IDTok->getRawIdentifier()).str());
+    NextLoc = IDTok->getLocation();
+  }
+  if (Result.empty())
+    return llvm::None;
+  return Result;
+}
+
+// An unresolved name and its scope information that can be extracted cheaply.
+struct CheapUnresolvedName {
+  std::string Name;
+  // 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::`).
+  llvm::Optional<std::string> ResolvedScope;
+
+  // Unresolved part of the scope. When the unresolved name is a specifier, we
+  // use the name that comes after it as the alternative name to resolve and use
+  // the specifier as the extra scope in the accessible scopes.
+  llvm::Optional<std::string> UnresolvedScope;
+};
+
+// Extracts unresolved name and scope information around \p Unresolved.
+// FIXME: try to merge this with the scope-wrangling code in CodeComplete.
+llvm::Optional<CheapUnresolvedName> extractUnresolvedNameCheaply(
+    const SourceManager &SM, const DeclarationNameInfo &Unresolved,
+    CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier) {
+  bool Invalid = false;
+  llvm::StringRef Code = SM.getBufferData(
+      SM.getDecomposedLoc(Unresolved.getBeginLoc()).first, &Invalid);
+  if (Invalid)
+    return llvm::None;
+  CheapUnresolvedName Result;
+  Result.Name = Unresolved.getAsString();
+  if (SS && SS->isNotEmpty()) { // "::" or "ns::"
+    if (auto *Nested = SS->getScopeRep()) {
+      if (Nested->getKind() == NestedNameSpecifier::Global)
+        Result.ResolvedScope = "";
+      else if (const auto *NS = Nested->getAsNamespace()) {
+        auto SpecifiedNS = printNamespaceScope(*NS);
+
+        // Check the specifier 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" specifier 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))
+          Result.ResolvedScope = SpecifiedNS;
+        else
+          Result.UnresolvedScope = Spelling;
+      } else if (const auto *ANS = Nested->getAsNamespaceAlias()) {
+        Result.ResolvedScope = 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 (UnresolvedIsSpecifier) {
+    // If the unresolved name is a specifier 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 specifier 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(SM, Unresolved.getBeginLoc(), LangOpts)) {
+      auto Split = splitQualifiedName(*QualifiedByUnresolved);
+      if (!Result.UnresolvedScope)
+        Result.UnresolvedScope.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 specifier, we append "index::"
+      // to the extra scope.
+      Result.UnresolvedScope->append((Result.Name + Split.first).str());
+      Result.Name = 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.
+    // 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 = Typo.getAsString();
+    Unresolved.Name = CheapUnresolved.Name;
     Unresolved.Loc = Typo.getBeginLoc();
 
+    if (!CheapUnresolved.ResolvedScope && !S) // Give up if no scope available.
+      return TypoCorrection();
+
     auto *Sem = SemaPtr; // Avoid capturing `this`.
-    Unresolved.GetScopes = [Sem, SpecifiedScope, S, LookupKind]() {
+    Unresolved.GetScopes = [Sem, CheapUnresolved, S, LookupKind]() {
       std::vector<std::string> Scopes;
-      if (SpecifiedScope) {
-        Scopes.push_back(*SpecifiedScope);
+      if (CheapUnresolved.ResolvedScope) {
+        Scopes.push_back(*CheapUnresolved.ResolvedScope);
       } else {
         assert(S);
-        // No scope qualifier is specified. Collect all accessible scopes in the
+        // 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 (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();
   }

clang-tools-extra/trunk/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 specifier. (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"))),
void bar(X *x) {
   auto Parsed = TU.build();
   for (const auto &D : Parsed.getDiagnostics()) {
     EXPECT_EQ(D.Fixes.size(), 1u);
     EXPECT_EQ(D.Fixes[0].Message,
               std::string("Add include \"a.h\" for symbol X"));
   }
 }
 
+TEST(IncludeFixerTest, UnresolvedNameAsSpecifier) {
+  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, UnresolvedSpecifierWithSemaCorrection) {
+  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