[clangd] Implement getBeginning for overloaded operators.

[hokein]

Summary

This will fix some bugs where navigation doesn't work on cases like
std::cout <^< "hello".

[hokein]

clang-tools-extra/clangd/SourceCode.cpp

279

the function name doesn't match what it does now, considering a new name for it, getBeginningOfIdentifierOrOverloadedOperator seems too verbose, maybe just getBeginning?

[hokein]

Rewrite the getBeignningOfIdentifier function.

[hokein]

Fix a typo.

[ilya-biryukov]

clang-tools-extra/clangd/SourceCode.cpp

320–339

If we use IgnoreWhitespace = false, I think we can simplify to:

// Location in the middle of some token.
if (BeforeLoc == CurrentLoc)
  return CurrentLoc;

// Whitespace is not interesting.
if (CurrentTok.Kind == tok::whitespace) 
  return BeforeTok;
if (BeforeTok.Kind == tok::whitespace)
  return CurrentTok;

// The cursor is at token boundary, i.e. `Before^Current`.
// Prefer identifiers to other tokens.
if (CurrentTok.Kind == tok::raw_identifier)
  return CurrentLoc;
if (BeforeTok.Kind == tok::raw_identifier)
  return BeforeLoc;
// And overloaded operators to other tokens.
if (isOperator(CurrentTok.Kind))
  return CurrentLoc;
if (isOperator(BeforeTok.Kind))
  return BeforeLoc;
return CurrentLoc;

That would have the same semantics, but is arguably simpler. WDYT?

[hokein]

Simplify the logic.

[hokein]

Upload correct diff.

clang-tools-extra/clangd/SourceCode.cpp

320–339

Good point, that would simplify the logic.

[ilya-biryukov]

Mostly NITs, except the naming of the new TokenKind enum.
I think it's better to pick something that's not clashing with clang::tok::TokenKind, even if the enum is in a different namespace.

clang-tools-extra/clangd/SourceCode.cpp

242

TokenKind has the same name as tok::TokenKind. Could we use a different name here to avoid possible confusions?
E.g. TokenGroup or TokenFlavor.

258

NIT: add static for consistency with the rest of the function.

261

NIT: can this just be tok::NUM_TOKENS? same for other kinds in the same function

311

NIT: Could you please duplicate what case 2 is to avoid the need to go back to the comment at the top.

326

could be at the token boundary should be is at the token boundary, right?
Whenever it's not the case we'll bail out on BeforeTokBeginning == CurrentTokBeginning.

[hokein]

address comments.

clang-tools-extra/clangd/SourceCode.cpp

242

renamed to TokenFlavor.

258

I think the static is redundant here, as the function is in the anonymous namespace, I removed the static on the function above.

326

yes, you are right. I was thinking of the single token case int ^foo;, which should be counted into the boundary case as we consider whitespace as a token kind.

[ilya-biryukov]

Mostly LGTM

clang-tools-extra/clangd/SourceCode.cpp

258

LG, that's also fine.

I suggested 'static' because other functions in this file are using it (in addition to being in the anonymous namespace, I believe).

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

330

Do we test ++^^abc anywhere?

[ilya-biryukov]

clang-tools-extra/clangd/SourceCode.cpp

279

getBeginning sounds too generic too me, would definitely avoid that. I think getBeginningOfIdentifier creates less confusion, albeit it definitely creates some.

No better alternative comes to mind, though. Maybe keep as is and update the comment to mention it also handles tokens for operators?

[hokein]

add one more testcase.

[hokein]

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

330

no, but we have a similar test ++/**/^abc, added it.

clang-tools-extra/clangd/SourceCode.cpp

llvm::Optional<Range> getTokenRange(const SourceManager &SM,
   if (!TokLoc.isValid())
     return llvm::None;
   SourceLocation End = Lexer::getLocForEndOfToken(TokLoc, 0, SM, LangOpts);
   if (!End.isValid())
     return llvm::None;
   return halfOpenToRange(SM, CharSourceRange::getCharRange(TokLoc, End));
 }
 
+namespace {
+
+enum TokenKind { Identifier, Operator, Whitespace, Other };
+
+static bool isOverloadedOperator(const Token &Tok) {
+  switch (Tok.getKind()) {
+#define OVERLOADED_OPERATOR(Name, Spelling, Token, Unary, Binary, MemOnly)     \
+  case tok::Token:
+#define OVERLOADED_OPERATOR_MULTI(Name, Spelling, Unary, Binary, MemOnly)
+#include "clang/Basic/OperatorKinds.def"
+    return true;
+
+  default:
+    break;
+  }
+  return false;
+}
+
+TokenKind getTokenKind(SourceLocation Loc, const SourceManager &SM,
+                       const LangOptions &LangOpts) {
+  Token Tok;
+  Tok.setKind(tok::TokenKind::NUM_TOKENS);
+  if (Lexer::getRawToken(Loc, Tok, SM, LangOpts,
+                         /*IgnoreWhiteSpace*/ false))
+    return Other;
+
+  // getRawToken will return false without setting Tok when the token is
+  // whitespace, so if the flag is not set, we are sure this is a whitespace.
+  if (Tok.is(tok::TokenKind::NUM_TOKENS))
+    return Whitespace;
+  if (Tok.is(tok::TokenKind::raw_identifier))
+    return Identifier;
+  if (isOverloadedOperator(Tok))
+    return Operator;
+  return Other;
+}
+
+} // namespace
+
 SourceLocation getBeginningOfIdentifier(const Position &Pos,
                                         const SourceManager &SM,
                                         const LangOptions &LangOpts) {
   FileID FID = SM.getMainFileID();
   auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
   if (!Offset) {
     log("getBeginningOfIdentifier: {0}", Offset.takeError());
     return SourceLocation();
   }
 
-  // GetBeginningOfToken(pos) is almost what we want, but does the wrong thing
-  // if the cursor is at the end of the identifier.
-  // Instead, we lex at GetBeginningOfToken(pos - 1). The cases are:
-  //  1) at the beginning of an identifier, we'll be looking at something
-  //  that isn't an identifier.
-  //  2) at the middle or end of an identifier, we get the identifier.
-  //  3) anywhere outside an identifier, we'll get some non-identifier thing.
-  // We can't actually distinguish cases 1 and 3, but returning the original
-  // location is correct for both!
+  // GetBeginningOfToken(InputLoc) is almost what we want, but does the wrong
+  // thing if the cursor is at the end of the token (identifier or operator).
+  // The cases are:
+  //   1) at the beginning of the token
+  //   2) at the middle of the token
+  //   3) at the end of the token
+  //   4) anywhere outside the identifier or operator
+  // To distinguish all cases, we lex both at the
+  // GetBeginningOfToken(InputLoc-1) and GetBeginningOfToken(InputLoc), for
+  // cases 1 and 4, we just return the original location.
   SourceLocation InputLoc = SM.getComposedLoc(FID, *Offset);
-  if (*Offset == 0) // Case 1 or 3.
+  if (*Offset == 0) // Case 1 or 4.
     return InputLoc;
   SourceLocation Before = SM.getComposedLoc(FID, *Offset - 1);
+  SourceLocation BeforeTokBeginning =
+      Lexer::GetBeginningOfToken(Before, SM, LangOpts);
+  TokenKind BeforeKind = getTokenKind(BeforeTokBeginning, SM, LangOpts);
+
+  SourceLocation CurrentTokBeginning =
+      Lexer::GetBeginningOfToken(InputLoc, SM, LangOpts);
+  TokenKind CurrentKind = getTokenKind(CurrentTokBeginning, SM, LangOpts);
+
+  // Case 2.
+  if (BeforeTokBeginning == CurrentTokBeginning) {
+    // For interesting token, we return the beginning of the token.
+    if (CurrentKind == Identifier || CurrentKind == Operator)
+      return CurrentTokBeginning;
+    // otherwise, we return the original loc.
+    return InputLoc;
+  }
 
-  Before = Lexer::GetBeginningOfToken(Before, SM, LangOpts);
-  Token Tok;
-  if (Before.isValid() &&
-      !Lexer::getRawToken(Before, Tok, SM, LangOpts, false) &&
-      Tok.is(tok::raw_identifier))
-    return Before; // Case 2.
-  return InputLoc; // Case 1 or 3.
+  // Whitespace is not interesting.
+  if (BeforeKind == Whitespace)
+    return CurrentTokBeginning;
+  if (CurrentKind == Whitespace)
+    return BeforeTokBeginning;
+
+  // Handle case 1 and 3. Note that the cursor could be at the token boundary,
+  // e.g. "Before^Current", we prefer identifiers to other tokens.
+  if (CurrentKind == Identifier)
+    return CurrentTokBeginning;
+  if (BeforeKind == Identifier)
+    return BeforeTokBeginning;
+  // Then prefer overloaded operators to other tokens.
+  if (CurrentKind == Operator)
+    return CurrentTokBeginning;
+  if (BeforeKind == Operator)
+    return BeforeTokBeginning;
+
+  // Case 4, we just return the original location.
+  return InputLoc;
 }
 
 bool isValidFileRange(const SourceManager &Mgr, SourceRange R) {
   if (!R.getBegin().isValid() || !R.getEnd().isValid())
     return false;
 
   FileID BeginFID;
   size_t BeginOffset = 0;

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

 
 TEST(SourceCodeTests, GetBeginningOfIdentifier) {
   std::string Preamble = R"cpp(
 struct Bar { int func(); };
 #define MACRO(X) void f() { X; }
 Bar* bar;
   )cpp";
   // First ^ is the expected beginning, last is the search position.
-  for (std::string Text : std::vector<std::string>{
+  for (const std::string &Text : std::vector<std::string>{
            "int ^f^oo();", // inside identifier
            "int ^foo();",  // beginning of identifier
            "int ^foo^();", // end of identifier
            "int foo(^);",  // non-identifier
            "^int foo();",  // beginning of file (can't back up)
            "int ^f0^0();", // after a digit (lexing at N-1 is wrong)
-           "int ^λλ^λ();", // UTF-8 handled properly when backing up
+           "/^/ comments", // non-interesting token
+           "void f(int abc) { abc ^ ++; }",    // whitespace
+           "void f(int abc) { ^abc^++; }",     // range of identifier
+           "void f(int abc) { ++^abc^; }",     // range of identifier
+           "void f(int abc) { ^+^+abc; }",     // range of operator
+           "void f(int abc) { ^abc^ ++; }",    // range of identifier
+           "void f(int abc) { abc ^++^; }",    // range of operator
+           "void f(int abc) { ^++^ abc; }",    // range of operator
+           "void f(int abc) { ++ ^abc^; }",    // range of identifier
+           "void f(int abc) { ^++^/**/abc; }", // range of operator
+           "void f(int abc) { ++/**/^abc; }",  // range of identifier
+           "void f(int abc) { ^abc^/**/++; }", // range of identifier
+           "void f(int abc) { abc/**/^++; }",  // range of operator
+           "void f() {^ }", // outside of identifier and operator
+           "int ^λλ^λ();",  // UTF-8 handled properly when backing up
 
            // identifier in macro arg
            "MACRO(bar->^func())",  // beginning of identifier
            "MACRO(bar->^fun^c())", // inside identifier
            "MACRO(bar->^func^())", // end of identifier
            "MACRO(^bar->func())",  // begin identifier
            "MACRO(^bar^->func())", // end identifier
            "^MACRO(bar->func())",  // beginning of macro name

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

const char *Tests[] = {
         class X {
           X(X&& x) = default;
         };
         X [[makeX]]() {}
         void foo() {
           auto x = m^akeX();
         }
       )cpp",
+
+      R"cpp(
+        struct X {
+          X& [[operator]]++() {}
+        };
+        void foo(X& x) {
+          +^+x;
+        }
+      )cpp",
   };
   for (const char *Test : Tests) {
     Annotations T(Test);
     llvm::Optional<Range> WantDecl;
     llvm::Optional<Range> WantDef;
     if (!T.ranges().empty())
       WantDecl = WantDef = T.range();
     if (!T.ranges("decl").empty())