[clangd] Added highlighting for tokens that are macro arguments.

[jvikstrom]

Summary

Adds semantic highlighting for tokens that are a macro argument.
Example:

#define D_V(X) int X = 1230
D_V(SomeVar);

The "SomeVar" inside the macro is highlighted as a variable now.

Tokens that are in a macro body expansion are ignored in this patch for three reasons.

• The spelling loc is inside the macro "definition" meaning it would highlight inside the macro definition (could probably easily be fixed by using getExpansionLoc instead of getSpellingLoc?)
• If wanting to highlight the macro definition this could create duplicate tokens. And if the tokens are of different types there would be conflicts (tokens in the same range but with different types). Say a macro defines some name and both a variable declaration and a function use this, there would be two tokens in the macro definition but one with Kind "Variable" and the other with Kind "Function".
• Thirdly, macro body expansions could come from a file that is not the main file (easily fixed, just check that the Loc is in the main file and not even a problem if we wanted to highlight the actual macro "invocation")

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

201

It'd be clearer for the comment to describe which cases we are going to highlight (rather than the cases we don't).

207

The Loc here maybe not in the main file, considering the case

// in .h
#define DEFINE(X) in X;
#define DEFINE_Y DEFINE(Y)

// in .cc

DEFINE_Y

[ilya-biryukov]

How should this behave when if the same token is used multiple times inside a macro and the uses are different? Could we add this to tests?
E.g.

#define W(a) class a { void test() { int a = 10; } }
W(foo); // <-- `foo` is a variable of a class?

[jvikstrom]

Address comments.

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

207

The spelling loc is still going to be in DEFINE_Y I think. And we only highlight arguments in macros. (Added a testcase though)

[jvikstrom]

Fixed edge case when removing conflicting tokens.

[jvikstrom]

clang-format

[jvikstrom]

In D64741#1587204, @ilya-biryukov wrote:

How should this behave when if the same token is used multiple times inside a macro and the uses are different? Could we add this to tests?
E.g.

#define W(a) class a { void test() { int a = 10; } }
W(foo); // <-- `foo` is a variable of a class?

I had completely missed that there could be conflicting tokens when only highlighting macro arguments as well. Added code to just remove conflicting tokens.

[ilya-biryukov]

I had completely missed that there could be conflicting tokens when only highlighting macro arguments as well. Added code to just remove conflicting tokens.

Picking one of the highlightings looks fine, but we probably want to make sure it's deterministic. Given that we use sort now, I bet it won't be. Maybe include kinds into comparison as well? That's not a perfect solution, but would at least make sure the user-visible behavior is not random.
Could you add tests for that case too?

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

207

ok, I don't have an exact case for macros now, but my gut feeling tells me we will encounter cases where the Loc is not in main file.

here is a test case for declarations, we will visit the foo() decl in test.h as well. This could be addressed in a separate patch.

// test.h
void foo();

// test.cc
#include "test.h"
void foo() {}

[jvikstrom]

In D64741#1588987, @ilya-biryukov wrote:

I had completely missed that there could be conflicting tokens when only highlighting macro arguments as well. Added code to just remove conflicting tokens.

Picking one of the highlightings looks fine, but we probably want to make sure it's deterministic. Given that we use sort now, I bet it won't be. Maybe include kinds into comparison as well? That's not a perfect solution, but would at least make sure the user-visible behavior is not random.
Could you add tests for that case too?

Already added the case you sent a comment on in the test case. (look at the top of it)
Don't understand what you mean with the sort though. Kinds are already included in the comparator for sort. After the call to unique the only tokens that will share ranges are the ones that have different kinds.

Could just have a custom comparator in the call to unique that only compares the tokens' ranges which would leave us with the token whose kind is the lowest when there are conflicting ones. But do we really want to highlight anything when there are conflicts?

Maybe we should add another kind of Kind for when a token is conflicting?

[ilya-biryukov]

Thanks for pointing out I missed stuff. The strategy for conflicting highlightings LG, just a few NITs left from my side.

In D64741#1589144, @jvikstrom wrote:

Already added the case you sent a comment on in the test case. (look at the top of it)

Ah, sorry, I missed it. There are many there and the one you added slipped my mind.

Don't understand what you mean with the sort though. Kinds are already included in the comparator for sort. After the call to unique the only tokens that will share ranges are the ones that have different kinds.

Ah, right. Sorry, missed that as well, sort() LG, the results are deterministic.

Could just have a custom comparator in the call to unique that only compares the tokens' ranges which would leave us with the token whose kind is the lowest when there are conflicting ones. But do we really want to highlight anything when there are conflicts?
Maybe we should add another kind of Kind for when a token is conflicting?

Not highlighting for conflicting kinds LG (there is one interesting case that I think we should support at the end of my comment, other than it looks ok).
Conflicting would be hard to explain to users, so not having it look like a better option.

Now, one interesting case that we should probably support is assert. Schematically, it does something like:

#define assert(COND) if (!(cond)) { fail("assertion failed" #COND); }
assert(x != y);

Despite the argument being mentioned twice, we definitely only want highlightings from the first occurrence (that would give us kinds for expressions).
I would expect that this already works, in which case it's just a matter of adding a test case to guard against future regressions.

If this does not work, we should probably fix it in a separate change.

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

195

Could you add a comment explaining that we choose to not highlight the conflicting tokens?

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

207

ok, here is the case, the spelling loc is not in main file, it is in <scratch space>

// test.h
#DEFINE(X) class X {};
#DEFINE_Y(Y) DEFINE(x##Y)

// test.cc
DEFINE_Y(a);

[jvikstrom]

Ignore tokens outside of main file. Added testcase for assert.

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

207

You are correct. The other comment was actually correct as well, I just put the arguments for the header code in the place where the source code should be in.

Added a check in addToken that the Loc we are trying to add must be in the main file.

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

195

There is a comment in SemanticHighlighting.cpp at line 43. Want me to add a comment in the test case as well?

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

46

we don't care the Kind in HighlightingToken now, I think we could simplify the code by tweaking the deduplication logic above?

llvm::sort(Tokens, [](const HighlightingToken &L, const HighlightingToken &R) {
                 return L.R < R.R;
               });
std::unique(Tokens.begin(), Tokens.end(), [](const HighlightingToken &L, const HighlightingToken &R) {
                 return L.R == R.R;
               });

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

195

The comment in SemanticHighlighting.cpp file is too far away, there is no harm to add comment here, indeed, it somehow improves the test code readability .

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

46

This would still keep one entry of the conflicting token though. (If we have one Kind that is a variable and one that is a function. One of those tokens would still be in Tokens at the place they were conflicting as unique removes every element but one of duplicates)

If we have conflicting tokens we want to remove all of them because it doesn't really make sense to highlight them as anything.

[jvikstrom]

Added comment saying conflicting tokens are not highlighted in the test.

[jvikstrom]

Rebased to master.

[jvikstrom]

Moved comment.

[jvikstrom]

@ilya-biryukov @hokein pinging about this cl (I had completely forgotten about it somehow. Just updated it to the new master though)

[jvikstrom]

@ilya-biryukov @hokein ping

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

55

This is potentially O(n^2). Could we instead create a new vector and fill it with the new items?

The memory usage should not matter much - we have the AST stored in the background anyway. I bet we would be looking at it first if we wanted to minimize memory usage.

If we really wanted to not waste any memory, we could do it std::erase_if-style, i.e. move the items we want to remove to the end of the vector, call vector::erase once at the end.

[ilya-biryukov]

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

197

Unrelated to the change: do we plan to highlight macro names?
That seems very useful.

[jvikstrom]

Rewrote conflicting token removal code.

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

55

Completely forgot that erase is linear. Will go for the "allocate another vector" approach.

Rewrote the entire conflicting checking code to hopefully be simpler as well (it changed substantially, so you might want to take another look at it).

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

197

Yes

[ilya-biryukov]

LGTM from my side (and a few NIT, but up to you whether to apply them)

clang-tools-extra/clangd/SemanticHighlighting.cpp

66

NIT: Using a for-loop here could provide a little more structure and limit the scope of TokRef

for (ArrayRef<Token> Toks = Tokens; !Toks.empty(); ) {
  // ...
  Toks = Toks.drop_front(Conflicting.size());
}

80

NIT: the following version seems more readable: TokRef = TokRef.drop_front(Conflicting.size());

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

197

Awesome, can't wait for it to land!

clang-tools-extra/clangd/SemanticHighlighting.cpp

std::vector<HighlightingToken> collectTokens() {
     // Initializer lists can give duplicates of tokens, therefore all tokens
     // must be deduplicated.
     llvm::sort(Tokens,
                [](const HighlightingToken &L, const HighlightingToken &R) {
                  return std::tie(L.R, L.Kind) < std::tie(R.R, R.Kind);
                });
     auto Last = std::unique(Tokens.begin(), Tokens.end());
     Tokens.erase(Last, Tokens.end());
+
+    // Macros can give tokens that have the same source range but conflicting
+    // kinds. In this case all tokens sharing this source range should be
+    // removed.
+    for (unsigned I = 0; I < Tokens.size(); ++I) {
+      ArrayRef<HighlightingToken> TokRef(Tokens);
+      ArrayRef<HighlightingToken> Conflicting =
+          llvm::ArrayRef<HighlightingToken>(TokRef.begin() + I, TokRef.end())
+              .take_while([&](const HighlightingToken &T) {
+                return T.R == Tokens[I].R;
+              });
+
+      if (Conflicting.size() > 1) {
+        Tokens.erase(Tokens.begin() + I,
+                     Tokens.begin() + I + Conflicting.size());
+        --I;
+      }
+    }
+
     return Tokens;
   }
 
   bool VisitNamespaceAliasDecl(NamespaceAliasDecl *NAD) {
     // The target namespace of an alias can not be found in any other way.
     addToken(NAD->getTargetNameLoc(), HighlightingKind::Namespace);
     return true;
   }
 
   bool VisitMemberExpr(MemberExpr *ME) {
     const auto *MD = ME->getMemberDecl();
     if (isa<CXXDestructorDecl>(MD))
       // When calling the destructor manually like: AAA::~A(); The ~ is a
       // MemberExpr. Other methods should still be highlighted though.
       return true;
     addToken(ME->getMemberLoc(), MD);
     return true;
   }
 
   bool VisitNamedDecl(NamedDecl *ND) {
     // UsingDirectiveDecl's namespaces do not show up anywhere else in the
     // Visit/Traverse mehods. But they should also be highlighted as a
     // namespace.
     if (const auto *UD = dyn_cast<UsingDirectiveDecl>(ND)) {
       addToken(UD->getIdentLocation(), HighlightingKind::Namespace);
       return true;
     }
 
void addToken(SourceLocation Loc, const NamedDecl *D) {
     }
     if (isa<NamespaceAliasDecl>(D)) {
       addToken(Loc, HighlightingKind::Namespace);
       return;
     }
   }
 
   void addToken(SourceLocation Loc, HighlightingKind Kind) {
-    if (Loc.isMacroID())
-      // FIXME: skip tokens inside macros for now.
+    if(Loc.isMacroID()) {
+      // Only intereseted in highlighting arguments in macros (DEF_X(arg)).
+      if (!SM.isMacroArgExpansion(Loc))
         return;
+      Loc = SM.getSpellingLoc(Loc);
+    }
 
     auto R = getTokenRange(SM, Ctx.getLangOpts(), Loc);
     if (!R) {
       // R should always have a value, if it doesn't something is very wrong.
       elog("Tried to add semantic token with an invalid range");
       return;
     }
 
     Tokens.push_back({Kind, R.getValue()});
   }

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

makeHighlightingTokens(llvm::ArrayRef<Range> Ranges, HighlightingKind Kind) {
   for (int I = 0, End = Ranges.size(); I < End; ++I) {
     Tokens[I].R = Ranges[I];
     Tokens[I].Kind = Kind;
   }
 
   return Tokens;
 }
 
-void checkHighlightings(llvm::StringRef Code) {
+void checkHighlightings(llvm::StringRef Code, llvm::StringRef HeaderCode = "") {
   Annotations Test(Code);
-  auto AST = TestTU::withCode(Test.code()).build();
+  TestTU TU = TestTU::withCode(Test.code());
+  TU.HeaderCode = HeaderCode;
+  auto AST = TU.build();
   static const std::map<HighlightingKind, std::string> KindToString{
       {HighlightingKind::Variable, "Variable"},
       {HighlightingKind::Function, "Function"},
       {HighlightingKind::Class, "Class"},
       {HighlightingKind::Enum, "Enum"},
       {HighlightingKind::Namespace, "Namespace"},
       {HighlightingKind::EnumConstant, "EnumConstant"},
       {HighlightingKind::Field, "Field"},
R"cpp(
       typedef $Namespace[[a]]::$Class[[A]] $Class[[B]];
       using $Class[[BB]] = $Namespace[[a]]::$Class[[A]];
       enum class $Enum[[E]] {};
       typedef $Enum[[E]] $Enum[[C]];
       typedef $Enum[[C]] $Enum[[CC]];
       using $Enum[[CD]] = $Enum[[CC]];
       $Enum[[CC]] $Function[[f]]($Class[[B]]);
       $Enum[[CD]] $Function[[f]]($Class[[BB]]);
+    )cpp",
+    R"cpp(
+      #define DEF_MULTIPLE(X) namespace X { class X { int X; }; }
+      #define DEF_CLASS(T) class T {};
+      DEF_MULTIPLE(XYZ);
+      DEF_MULTIPLE(XYZW);
+      DEF_CLASS($Class[[A]])
+      #define MACRO_CONCAT(X, V, T) T foo##X = V
+      #define DEF_VAR(X, V) int X = V
+      #define DEF_VAR_T(T, X, V) T X = V
+      #define DEF_VAR_REV(V, X) DEF_VAR(X, V)
+      #define CPY(X) X
+      #define DEF_VAR_TYPE(X, Y) X Y
+      #define SOME_NAME variable
+      #define SOME_NAME_SET variable2 = 123
+      #define INC_VAR(X) X += 2
+      void $Function[[foo]]() {
+        DEF_VAR($Variable[[X]],  123);
+        DEF_VAR_REV(908, $Variable[[XY]]);
+        int CPY( $Variable[[XX]] );
+        DEF_VAR_TYPE($Class[[A]], $Variable[[AA]]);
+        double SOME_NAME;
+        int SOME_NAME_SET;
+        $Variable[[variable]] = 20.1;
+        MACRO_CONCAT(var, 2, float);
+        DEF_VAR_T($Class[[A]], CPY(CPY($Variable[[Nested]])),
+              CPY($Class[[A]]()));
+        INC_VAR($Variable[[variable]]);
+      }
+      void SOME_NAME();
+      DEF_VAR($Variable[[XYZ]], 567);
+      DEF_VAR_REV(756, $Variable[[AB]]);
+
+      #define CALL_FN(F) F();
+      #define DEF_FN(F) void F ()
+      DEF_FN($Function[[g]]) {
+        CALL_FN($Function[[foo]]);
+      }
     )cpp"};
   for (const auto &TestCase : TestCases) {
     checkHighlightings(TestCase);
   }
+
+  // A separate test for macros in headers.
+  checkHighlightings(R"cpp(
+    #define DEFINE(X) int X;
+    #define DEFINE_Y DEFINE(Y)
+  )cpp",
+                     R"cpp(
+    DEFINE_Y
+    DEFINE($Variable[[XYZ]]);
+  )cpp");
 }
 
 TEST(SemanticHighlighting, GeneratesHighlightsWhenFileChange) {
   class HighlightingsCounterDiagConsumer : public DiagnosticsConsumer {
   public:
     std::atomic<int> Count = {0};
 
     void onDiagnosticsReady(PathRef, std::vector<Diag>) override {}