[clangd] Fix duplicate highlighting tokens appearing in initializer lists

[jvikstrom]

Summary

The RecursiveASTVisitor sometimes visits exprs in initializer lists twice. Added deduplication to prevent duplicate highlighting tokens from appearing. Done by sorting and a linear search.

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

36

nit: we could write it like

llvm::sort(Tokens, [](const HighlightingToken &Lhs, const HighlightingToken &Rhs) {
   return std::tie(Lhs.Kind, Lhs.R) < std::tie(Rhs.Kind, Rhs.R);
});
auto Last = std::unique(Tokens.begin(), Tokens.end());
Tokens.erase(Last, Tokens.end());

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

36

About the comparator function though. I added an < operator because https://reviews.llvm.org/D64475 also sorts the tokens. However, could I just remove the sort in the main diffHighlightings method and just rely on the highlightings to be sorted in the first place from this patch?

Instead we'd do the sorting like:

llvm::sort(Tokens, [](const HighlightingToken &Lhs, const HighlightingToken &Rhs) {
   return std::tie(Lhs.R,Lhs.Kind) < std::tie(Rhs.R,Rhs.Kind);
});

so we get it sorted by their position first and Kind second.

[jvikstrom]

Remove operator< and use std::unique.

[jvikstrom]

Readded newline that was removed accidentaly.

[jvikstrom]

Removed return type hint for lambda.

[ilya-biryukov]

Have we tried figuring out why RecursiveASTVisitor visits the argument lists twice? Is that an expected behavior?

clang-tools-extra/clangd/SemanticHighlighting.cpp

37

NIT: in LLVM style, these should be called LHS and RHS as they are abbreviations.
However, in clangd we typically use L and R for that in those cases, I would suggest sticking to that.

(One-letter names are harder to confuse with each other)

[jvikstrom]

Address comment.

[jvikstrom]

In D64634#1585521, @ilya-biryukov wrote:

Have we tried figuring out why RecursiveASTVisitor visits the argument lists twice? Is that an expected behavior?

The comment for the function that traverses initialization lists says this:

This method is called once for each pair of syntactic and semantic
InitListExpr, and it traverses the subtrees defined by the two forms. This
may cause some of the children to be visited twice, if they appear both in
the syntactic and the semantic form.

So it seems to be expected. (and looking at the documentation for InitListExpr it seems to be difficult to change RecursiveASTVisitor to visit every sub expr once)

[ilya-biryukov]

LGTM (I think @hokein 's comments were addressed too)

So it seems to be expected. (and looking at the documentation for InitListExpr it seems to be difficult to change RecursiveASTVisitor to visit every sub expr once)

Ah, this particular piece of behavior seems really surprising to me.
We should definitely only traverse syntactic form if shouldVisitImplicitCode() == false, which should help us avoid this corner case here. But that's a topic for a separate patch, please land this to unbreak semantic highlighting.

clang-tools-extra/clangd/SemanticHighlighting.cpp

 
 public:
   HighlightingTokenCollector(ParsedAST &AST)
       : Ctx(AST.getASTContext()), SM(AST.getSourceManager()) {}
 
   std::vector<HighlightingToken> collectTokens() {
     Tokens.clear();
     TraverseAST(Ctx);
+    // Initializer lists can give duplicates of tokens, therefore all tokens
+    // must be deduplicated.
+    llvm::sort(Tokens,
+               [](const HighlightingToken &Lhs, const HighlightingToken &Rhs) {
+                 return std::tie(Lhs.R, Lhs.Kind) < std::tie(Rhs.R, Rhs.Kind);
+               });
+    auto Last = std::unique(Tokens.begin(), Tokens.end());
+    Tokens.erase(Last, Tokens.end());
     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;
   }

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

R"cpp(
       };
       void $Function[[foo]]() {
         $Class[[A]] $Variable[[AA]];
         $Variable[[AA]].$Field[[B]] += 2;
         $Variable[[AA]].$Method[[foo]]();
         $Variable[[AA]].$Field[[E]].$Field[[C]];
         $Class[[A]]::$Variable[[S]] = 90;
       }
+    )cpp",
+    R"cpp(
+      struct $Class[[AA]] {
+        int $Field[[A]];
+      }
+      int $Variable[[B]];
+      $Class[[AA]] $Variable[[A]]{$Variable[[B]]};
     )cpp"};
   for (const auto &TestCase : TestCases) {
     checkHighlightings(TestCase);
   }
 }
 
 TEST(SemanticHighlighting, GeneratesHighlightsWhenFileChange) {
   class HighlightingsCounterDiagConsumer : public DiagnosticsConsumer {