[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

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

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

303

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

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

clang-tools-extra/clangd/SourceCode.h

69

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

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

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

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

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

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

260

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

e.g. Nested template instantiation (TemplateSpecializationTypeLoc)

421

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

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

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

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/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.

 /// Turn an offset in Code into a [line, column] pair.
 /// The offset must be in range [0, Code.size()].
 Position offsetToPosition(llvm::StringRef Code, size_t Offset);
 
 /// Turn a SourceLocation into a [line, column] pair.
 /// FIXME: This should return an error if the location is invalid.
 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc);
 
+/// Turn a SourceLocation into a pair of positions
+Range sourceRangeToRange(const SourceManager &SM, SourceRange SrcRange);
+
 /// Returns the taken range at \p TokLoc.
 llvm::Optional<Range> getTokenRange(const SourceManager &SM,
                                     const LangOptions &LangOpts,
                                     SourceLocation TokLoc);
 
 /// Return the file location, corresponding to \p P. Note that one should take
 /// care to avoid comparing the result with expansion locations.
 llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,

clang-tools-extra/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 "llvm/ADT/None.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
   if (!Invalid) {
     auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
     auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
     P.character = lspLength(LineSoFar);
   }
   return P;
 }
 
+Range sourceRangeToRange(const SourceManager &SM, SourceRange SrcRange) {
+  return Range{sourceLocToPosition(SM, SrcRange.getBegin()),
+               sourceLocToPosition(SM, SrcRange.getEnd())};
+}
+
 llvm::Optional<Range> getTokenRange(const SourceManager &SM,
                                     const LangOptions &LangOpts,
                                     SourceLocation TokLoc) {
   if (!TokLoc.isValid())
     return llvm::None;
   SourceLocation End = Lexer::getLocForEndOfToken(TokLoc, 0, SM, LangOpts);
   if (!End.isValid())
     return llvm::None;
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,
+// 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.
+static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
+                                    const LangOptions &LangOpts) {
+  Token TheTok;
+  if (!Lexer::getRawToken(Loc, TheTok, SM, LangOpts)) {
+    if (TheTok.is(tok::greatergreater))
+      return 1;
+    else
+      return TheTok.getLength();
+  }
+  return 0;
+}
+// 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
+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);
+  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/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, VisibleNamespaces) {
   };
   for (const auto& Case : Cases) {
     EXPECT_EQ(Case.second,
               visibleNamespaces(Case.first, format::getLLVMStyle()))
         << Case.first;
   }
 }
 
+// Test for functions toHalfOpenFileRange and getHalfOpenFileRange
+// FIXME: Need better testing support to be able to check more than just Decls.
+TEST(SourceCodeTests, HalfOpenFileRange) {
+  Annotations Test(R"cpp(
+    #define FOO(X, Y) int Y = ++X
+    #define BAR(X) X + 1
+    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)]];
+    }
+  )cpp");
+
+  ParsedAST AST = TestTU::withCode(Test.code()).build();
+  const SourceManager &SM = AST.getSourceManager();
+  const LangOptions &LangOpts = AST.getASTContext().getLangOpts();
+
+  auto CheckRange = [&](llvm::StringRef Name) {
+    const NamedDecl &Decl = findUnqualifiedDecl(AST, Name);
+    auto FileRange = toHalfOpenFileRange(SM, LangOpts, Decl.getSourceRange());
+    ASSERT_NE(FileRange, llvm::None);
+    Range HalfOpenRange = sourceRangeToRange(SM, *FileRange);
+    EXPECT_EQ(HalfOpenRange, Test.ranges(Name)[0]);
+  };
+
+  CheckRange("a");
+  CheckRange("b");
+  CheckRange("c");
+  CheckRange("d");
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang