[clangd] Fixed toHalfOpenFileRange

[SureYeaah]

Summary

• Fixed toHalfOpenFileRange to work for macros as well as template

instantiations

• Added unit tests

Breaking test case for older version of toHalfOpenFileRange:
\# define FOO(X) X++
int a = 1;
int b = FOO(a);
toHalfOpenFileRange for the sourceRange of VarDecl for b returned the
wrong Range.

[SureYeaah]

Minor fixes

[sammccall]

Thanks for fixing this, this stuff is such a tangled web.

Logic seems great, so just style/test nits.

clang-tools-extra/clangd/SourceCode.cpp

261 ↗

(On Diff #209193)

>>= too? That's legal with variable templates.

(If you're deliberately choosing different behavior that definitely deserves a comment)

303 ↗

(On Diff #209193)

Explain why we're implementing this from scratch?

Maybe something like

This is similar to getFileLocation in SourceManager, which chooses getExpansionRange or getSpellingLocation (for macro arguments).
However:
 - we need full range information, which getFileLocation discards
 - (there's something else wrong with getExpansionRange, right?)
 - we want to split `>>` tokens

338 ↗

(On Diff #209193)

maybe a comment "convert from closed token range to half-open range"

clang-tools-extra/clangd/SourceCode.h

69 ↗

(On Diff #209193)

This isn't well-defined without more information, because a SourceRange may be token/char range etc.
(And in fact this appears to treat it as a half-open range, which isn't the most common type).

Because this is ambiguous, fairly rare, and simple, can we just inline it into the test where it's used instead?

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

410 ↗

(On Diff #209193)

this is a function on ranges, so only using decls isn't a limitation per se.

Is there a type of range you're unable to test because you can't construct it as the source range of a decl? If so, please say which. If not I think we should just drop this comment.

412 ↗

(On Diff #209193)

Can you add an explanation of what's in the test?

e.g. "each marked range should be the file range of the decl with the same name"

421 ↗

(On Diff #209193)

some tests where the expansion range is a macro arg? e.g.

#define ECHO(X) X
ECHO($e[[ECHO(int) ECHO(e)]])

(if I'm understanding right)

432 ↗

(On Diff #209193)

I like the "factored out" test, but one trap is that if assertions fail then you can't tell which case it was.

You can use SCOPED_TRACE(Name) at the top of this block to make sure we print the range name.

[kadircet]

clang-tools-extra/clangd/SourceCode.cpp

252 ↗

(On Diff #209193)

maybe move the comment to just before if(thetok.is(greatergreater)) check?

260 ↗

(On Diff #209193)

re-arrange for less indentation:

if(Lexer::getRawToken(...))
  return 0;
if(TheTok.is(tok::greater...)
  return 1;
return TheTok...;

[SureYeaah]

Added comments and minor changes

[SureYeaah]

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

410 ↗

(On Diff #209193)

e.g. Nested template instantiation (TemplateSpecializationTypeLoc)

421 ↗

(On Diff #209193)

In this case, the FileRange would be

ECHO(ECHO($e[[int) ECHO(e]]));

So the code works correctly. But it's not how we want it to behave right?

[sammccall]

clang-tools-extra/clangd/SourceCode.cpp

261 ↗

(On Diff #209193)

nit: please don't just mark comments "done" if there's reason not to do them - a brief explanation in the review and/or the code is useful to keep track.

For the record, it turns out that it seems C++ doesn't actually allow >>= to be ambiguous - the user has to put a space before = if it's not a shift.

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

410 ↗

(On Diff #209193)

That's a type of decl, not a type of range.

This function inputs and outputs a range, so the type of decl used isn't relevant to its correctness.
Is there a particular type of range (e.g. certain macro expansion structure and pair of points) that you want to test but can't construct a decl to cover?

421 ↗

(On Diff #209193)

That looks OK to me. It's surprising, but I think defensible.

The most likely source of complaints is I guess if we use selection tree to implement structured selection expansion. Anyway, whatever the behavior is, thanks for adding the test :-)

clang-tools-extra/trunk/clangd/SourceCode.h

 #include "Context.h"
 #include "Protocol.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
 #include "clang/Tooling/Core/Replacement.h"
-#include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/SHA1.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
 // We tend to generate digests for source codes in a lot of different places.
 // This represents the type for those digests to prevent us hard coding details

clang-tools-extra/trunk/clangd/SourceCode.cpp

 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "SourceCode.h"
 
 #include "Context.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Protocol.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Format/Format.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
bool halfOpenRangeContains(const SourceManager &Mgr, SourceRange R,
   return BeginFID == LFid && BeginOffset <= LOffset && LOffset < EndOffset;
 }
 
 bool halfOpenRangeTouches(const SourceManager &Mgr, SourceRange R,
                           SourceLocation L) {
   return L == R.getEnd() || halfOpenRangeContains(Mgr, R, L);
 }
 
-llvm::Optional<SourceRange> toHalfOpenFileRange(const SourceManager &Mgr,
+static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
+                                    const LangOptions &LangOpts) {
+  Token TheTok;
+  if (Lexer::getRawToken(Loc, TheTok, SM, LangOpts))
+    return 0;
+  // FIXME: Here we check whether the token at the location is a greatergreater
+  // (>>) token and consider it as a single greater (>). This is to get it
+  // working for templates but it isn't correct for the right shift operator. We
+  // can avoid this by using half open char ranges in getFileRange() but getting
+  // token ending is not well supported in macroIDs.
+  if (TheTok.is(tok::greatergreater))
+    return 1;
+  return TheTok.getLength();
+}
+
+// Returns location of the last character of the token at a given loc
+static SourceLocation getLocForTokenEnd(SourceLocation BeginLoc,
+                                        const SourceManager &SM,
+                                        const LangOptions &LangOpts) {
+  unsigned Len = getTokenLengthAtLoc(BeginLoc, SM, LangOpts);
+  return BeginLoc.getLocWithOffset(Len ? Len - 1 : 0);
+}
+
+// Returns location of the starting of the token at a given EndLoc
+static SourceLocation getLocForTokenBegin(SourceLocation EndLoc,
+                                          const SourceManager &SM,
+                                          const LangOptions &LangOpts) {
+  return EndLoc.getLocWithOffset(
+      -(signed)getTokenLengthAtLoc(EndLoc, SM, LangOpts));
+}
+
+// Converts a char source range to a token range.
+static SourceRange toTokenRange(CharSourceRange Range, const SourceManager &SM,
+                                const LangOptions &LangOpts) {
+  if (!Range.isTokenRange())
+    Range.setEnd(getLocForTokenBegin(Range.getEnd(), SM, LangOpts));
+  return Range.getAsRange();
+}
+// Returns the union of two token ranges.
+// To find the maximum of the Ends of the ranges, we compare the location of the
+// last character of the token.
+static SourceRange unionTokenRange(SourceRange R1, SourceRange R2,
+                                   const SourceManager &SM,
+                                   const LangOptions &LangOpts) {
+  SourceLocation E1 = getLocForTokenEnd(R1.getEnd(), SM, LangOpts);
+  SourceLocation E2 = getLocForTokenEnd(R2.getEnd(), SM, LangOpts);
+  return SourceRange(std::min(R1.getBegin(), R2.getBegin()),
+                     E1 < E2 ? R2.getEnd() : R1.getEnd());
+}
+
+// Returns the tokenFileRange for a given Location as a Token Range
+// This is quite similar to getFileLoc in SourceManager as both use
+// getImmediateExpansionRange and getImmediateSpellingLoc (for macro IDs).
+// However:
+// - We want to maintain the full range information as we move from one file to
+//   the next. getFileLoc only uses the BeginLoc of getImmediateExpansionRange.
+// - We want to split '>>' tokens as the lexer parses the '>>' in template
+//   instantiations as a '>>' instead of a '>'.
+// There is also getExpansionRange but it simply calls
+// getImmediateExpansionRange on the begin and ends separately which is wrong.
+static SourceRange getTokenFileRange(SourceLocation Loc,
+                                     const SourceManager &SM,
+                                     const LangOptions &LangOpts) {
+  SourceRange FileRange = Loc;
+  while (!FileRange.getBegin().isFileID()) {
+    assert(!FileRange.getEnd().isFileID() &&
+           "Both Begin and End should be MacroIDs.");
+    if (SM.isMacroArgExpansion(FileRange.getBegin())) {
+      FileRange.setBegin(SM.getImmediateSpellingLoc(FileRange.getBegin()));
+      FileRange.setEnd(SM.getImmediateSpellingLoc(FileRange.getEnd()));
+    } else {
+      SourceRange ExpansionRangeForBegin = toTokenRange(
+          SM.getImmediateExpansionRange(FileRange.getBegin()), SM, LangOpts);
+      SourceRange ExpansionRangeForEnd = toTokenRange(
+          SM.getImmediateExpansionRange(FileRange.getEnd()), SM, LangOpts);
+      FileRange = unionTokenRange(ExpansionRangeForBegin, ExpansionRangeForEnd,
+                                  SM, LangOpts);
+    }
+  }
+  return FileRange;
+}
+
+llvm::Optional<SourceRange> toHalfOpenFileRange(const SourceManager &SM,
                                                 const LangOptions &LangOpts,
                                                 SourceRange R) {
-  auto Begin = Mgr.getFileLoc(R.getBegin());
-  if (Begin.isInvalid())
+  SourceRange R1 = getTokenFileRange(R.getBegin(), SM, LangOpts);
+  if (!isValidFileRange(SM, R1))
     return llvm::None;
-  auto End = Mgr.getFileLoc(R.getEnd());
-  if (End.isInvalid())
+
+  SourceRange R2 = getTokenFileRange(R.getEnd(), SM, LangOpts);
+  if (!isValidFileRange(SM, R2))
     return llvm::None;
-  End = Lexer::getLocForEndOfToken(End, 0, Mgr, LangOpts);
 
-  SourceRange Result(Begin, End);
-  if (!isValidFileRange(Mgr, Result))
+  SourceRange Result = unionTokenRange(R1, R2, SM, LangOpts);
+  unsigned TokLen = getTokenLengthAtLoc(Result.getEnd(), SM, LangOpts);
+  // Convert from closed token range to half-open (char) range
+  Result.setEnd(Result.getEnd().getLocWithOffset(TokLen));
+  if (!isValidFileRange(SM, Result))
     return llvm::None;
+
   return Result;
 }
 
 llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
   assert(isValidFileRange(SM, R));
   bool Invalid = false;
   auto *Buf = SM.getBuffer(SM.getFileID(R.getBegin()), &Invalid);
   assert(!Invalid);
std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
   for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
     Found.push_back(Enclosing);
     auto It = UsingDirectives.find(Enclosing);
     if (It != UsingDirectives.end())
       for (const auto& Used : It->second)
         Found.push_back(Used.getKey());
   }
 
-
   llvm::sort(Found, [&](const std::string &LHS, const std::string &RHS) {
     if (Current == RHS)
       return false;
     if (Current == LHS)
       return true;
     return LHS < RHS;
   });
   Found.erase(std::unique(Found.begin(), Found.end()), Found.end());

clang-tools-extra/trunk/clangd/unittests/SourceCodeTests.cpp

 //===-- SourceCodeTests.cpp  ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "Annotations.h"
 #include "Context.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "TestTU.h"
+#include "clang/Basic/LangOptions.h"
 #include "clang/Format/Format.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/raw_os_ostream.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
TEST(SourceCodeTests, GetMacros) {
   auto AST = TU.build();
   auto Loc = getBeginningOfIdentifier(AST, Code.point(),
                                       AST.getSourceManager().getMainFileID());
   auto Result = locateMacroAt(Loc, AST.getPreprocessor());
   ASSERT_TRUE(Result);
   EXPECT_THAT(*Result, MacroName("MACRO"));
 }
 
+// Test for functions toHalfOpenFileRange and getHalfOpenFileRange
+TEST(SourceCodeTests, HalfOpenFileRange) {
+  // Each marked range should be the file range of the decl with the same name
+  // and each name should be unique.
+  Annotations Test(R"cpp(
+    #define FOO(X, Y) int Y = ++X
+    #define BAR(X) X + 1
+    #define ECHO(X) X
+    template<typename T>
+    class P {};
+    void f() {
+      $a[[P<P<P<P<P<int>>>>> a]];
+      $b[[int b = 1]];
+      $c[[FOO(b, c)]]; 
+      $d[[FOO(BAR(BAR(b)), d)]];
+      // FIXME: We might want to select everything inside the outer ECHO.
+      ECHO(ECHO($e[[int) ECHO(e]]));
+    }
+  )cpp");
+
+  ParsedAST AST = TestTU::withCode(Test.code()).build();
+  llvm::errs() << Test.code();
+  const SourceManager &SM = AST.getSourceManager();
+  const LangOptions &LangOpts = AST.getASTContext().getLangOpts();
+  // Turn a SourceLocation into a pair of positions
+  auto SourceRangeToRange = [&SM](SourceRange SrcRange) {
+    return Range{sourceLocToPosition(SM, SrcRange.getBegin()),
+                 sourceLocToPosition(SM, SrcRange.getEnd())};
+  };
+  auto CheckRange = [&](llvm::StringRef Name) {
+    const NamedDecl &Decl = findUnqualifiedDecl(AST, Name);
+    auto FileRange = toHalfOpenFileRange(SM, LangOpts, Decl.getSourceRange());
+    SCOPED_TRACE("Checking range: " + Name);
+    ASSERT_NE(FileRange, llvm::None);
+    Range HalfOpenRange = SourceRangeToRange(*FileRange);
+    EXPECT_EQ(HalfOpenRange, Test.ranges(Name)[0]);
+  };
+
+  CheckRange("a");
+  CheckRange("b");
+  CheckRange("c");
+  CheckRange("d");
+  CheckRange("e");
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang