[clangd] Compute the inactive code range for semantic highlighting.

[hokein]

Summary

A screenshot in VSCode (with the LSP's v3.16 semanticToken enabled)

[nridge]

Do you mean "inactive" (instead of "interactive") in the commit message?

[hokein]

In D85635#2208325, @nridge wrote:

Do you mean "inactive" (instead of "interactive") in the commit message?

oh, right. Fixed the typo.

[sammccall]

Yup, this is a nice improvement, though there are further things we could do.

As discussed offline, we could consider mapping "disabled" to an attribute but we can't really consume that well in VSCode (or any other editor yet) so let's leave it.

clang-tools-extra/clangd/SemanticHighlighting.cpp

238

A little more direct and avoiding the special case:

StringRef LineText = MainCode.drop_front(StartOfLine).take_until([](char C) { return C == '\n'; });
...
{Position{Line, 0}, Position{Line, lspLength(LineText)}}

242

this may overlap existing tokens.
The spec is silent on this, it may pose a challenge to clients and makes for a complex model for little benefit. I think we should avoid overlapping tokens.

For now this can actually happen, as we consider #ifndef FOO to be disabled if FOO is defined, but also a usage of the macro FOO.
I'd suggest erasing these (collect their indexes and delete them in a second pass).

In future, I think we probably want to reduce the scope of the disabled regions to not include the directive itself, then this can become an assert.

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

83

AIUI the extra complexity here is to accommodate overlapping ranges, which we can likely get rid of.

[hokein]

address review comments

[sammccall]

I think the code could be a bit clearer, but up to you. The tests are good so feel free to submit any version you're happy with.

clang-tools-extra/clangd/SemanticHighlighting.cpp

242

Hmm, the role of NonConflicting is pretty confusing here: it has an invariant preserved as we construct it, then we violate it by dumping a bunch of ranges into it, then try to restore it.
And the correctness of the restoring seems to rely on some pretty subtle facts (that the inactive region always fully contains and is sorted *before* the regions it overlaps).

What about:

// Merge token stream with "inactive line" markers.
vector WithInactiveLines;
auto It = NonConflicting.begin();
for (Range &R : Ranges) {
  for (int Line : R) {
    // Copy tokens before the inactive line
    for (; It != NonConflicting.end() && It->position.begin.line < Line)
      WithInactiveLines.push_back(std::move(*It));
    // Add a token for the inactive line itself.
    WithInactiveLines.push_back(createInactiveLineToken(MainCode, Line));
    // Skip any other tokens on the inactive line
    while (It != NonConflicting.end() && It->position.begin.line == Line)
      ++It;
  }
}
// Copy tokens after the last inactive line
for (; It != NonOverlapping.end(); ++It)
  WithInactiveLines.push_back(std::move(*It));

The only real assumption here is "a token is associated with a line", which is pretty fundamental anyway.

[hokein]

address comment.

clang-tools-extra/clangd/SemanticHighlighting.cpp

for (ArrayRef<HighlightingToken> TokRef = Tokens; !TokRef.empty();) {
             return T.R == TokRef.front().R;
           });
       if (auto Resolved = resolveConflict(Conflicting))
         NonConflicting.push_back(*Resolved);
       // TokRef[Conflicting.size()] is the next token with a different range (or
       // the end of the Tokens).
       TokRef = TokRef.drop_front(Conflicting.size());
     }
+    const auto &SM = AST.getSourceManager();
+    StringRef MainCode = SM.getBuffer(SM.getMainFileID())->getBuffer();
     // Add tokens indicating lines skipped by the preprocessor.
     for (const Range &R : AST.getMacros().SkippedRanges) {
       // Create one token for each line in the skipped range, so it works
       // with line-based diffing.
       assert(R.start.line <= R.end.line);
       for (int Line = R.start.line; Line <= R.end.line; ++Line) {
-        // Don't bother computing the offset for the end of the line, just use
-        // zero. The client will treat this highlighting kind specially, and
-        // highlight the entire line visually (i.e. not just to where the text
-        // on the line ends, but to the end of the screen).
-        NonConflicting.push_back({HighlightingKind::InactiveCode,
-                                  {Position{Line, 0}, Position{Line, 0}}});
+        auto StartOfLine = positionToOffset(MainCode, Position{Line, 0});
+        if (!StartOfLine) {
+          elog("Failed to convert position to offset: {0}",
+               StartOfLine.takeError());
+          continue;
+        }
+        size_t LineLength = MainCode.substr(*StartOfLine).find('\n');
+        size_t EndOfLine = LineLength == llvm::StringRef::npos
+                               ? MainCode.size() - 1 // EOF
+                               : *StartOfLine + LineLength;
+        NonConflicting.push_back(
+            {HighlightingKind::InactiveCode,
+             {Position{Line, 0}, offsetToPosition(MainCode, EndOfLine)}});
       }
     }
     // Re-sort the tokens because that's what the diffing expects.
     llvm::sort(NonConflicting);
     return NonConflicting;
   }
 
 private:

 }
 
 std::vector<SemanticToken>
 toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens) {
   assert(std::is_sorted(Tokens.begin(), Tokens.end()));
   std::vector<SemanticToken> Result;
   const HighlightingToken *Last = nullptr;
   for (const HighlightingToken &Tok : Tokens) {
-    // FIXME: support inactive code - we need to provide the actual bounds.
-    if (Tok.Kind == HighlightingKind::InactiveCode)
-      continue;
     Result.emplace_back();
     SemanticToken &Out = Result.back();
     // deltaStart/deltaLine are relative if possible.
     if (Last) {
       assert(Tok.R.start.line >= Last->R.start.line);
       Out.deltaLine = Tok.R.start.line - Last->R.start.line;
       if (Out.deltaLine == 0) {
         assert(Tok.R.start.character >= Last->R.start.character);

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

 }
 
 /// Annotates the input code with provided semantic highlightings. Results look
 /// something like:
 ///   class $Class[[X]] {
 ///     $Primitive[[int]] $Field[[a]] = 0;
 ///   };
 std::string annotate(llvm::StringRef Input,
-                     llvm::ArrayRef<HighlightingToken> Tokens) {
+                     llvm::ArrayRef<HighlightingToken> Tokens,
+                     size_t NextChar = 0) {
   assert(std::is_sorted(
       Tokens.begin(), Tokens.end(),
       [](const HighlightingToken &L, const HighlightingToken &R) {
         return L.R.start < R.R.start;
       }));
 
   std::string Result;
-  unsigned NextChar = 0;
-  for (auto &T : Tokens) {
-    unsigned StartOffset = llvm::cantFail(positionToOffset(Input, T.R.start));
-    unsigned EndOffset = llvm::cantFail(positionToOffset(Input, T.R.end));
+  for (size_t I = 0; I < Tokens.size(); ++I) {
+    const auto &Current = Tokens[I];
+    unsigned StartOffset =
+        llvm::cantFail(positionToOffset(Input, Current.R.start));
+    assert(NextChar <= StartOffset && "Highlighting tokens must not overlap!");
+    unsigned EndOffset = llvm::cantFail(positionToOffset(Input, Current.R.end));
     assert(StartOffset <= EndOffset);
-    assert(NextChar <= StartOffset);
-
+    const auto *End =
+        llvm::find_if(llvm::makeArrayRef(Tokens.begin() + I + 1, Tokens.end()),
+                      [&](const HighlightingToken &Next) {
+                        return Current.R.end <= Next.R.start;
+                      });
+    // Tokens whose ranges are contained by the Current range, we recursively
+    // annotate them.
+    auto ContainedTokens = llvm::makeArrayRef(Tokens.begin() + I + 1, End);
     Result += Input.substr(NextChar, StartOffset - NextChar);
-    Result += std::string(
-        llvm::formatv("${0}[[{1}]]", T.Kind,
-                      Input.substr(StartOffset, EndOffset - StartOffset)));
+    if (ContainedTokens.empty()) {
+      // No extra tokens contained by Current.
+      Result +=
+          llvm::formatv("${0}[[{1}]]", Current.Kind,
+                        Input.substr(StartOffset, EndOffset - StartOffset));
+      NextChar = EndOffset;
+      continue;
+    }
+
+    auto Annotated =
+        annotate(Input.substr(0, EndOffset), ContainedTokens, StartOffset);
+    Result += llvm::formatv("${0}[[{1}]]", Current.Kind, Annotated);
     NextChar = EndOffset;
+    I += ContainedTokens.size();
   }
   Result += Input.substr(NextChar);
   return Result;
 }
 
 void checkHighlightings(llvm::StringRef Code,
                         std::vector<std::pair</*FileName*/ llvm::StringRef,
                                               /*FileContent*/ llvm::StringRef>>
)cpp",
       // highlighting all macro references
       R"cpp(
       #ifndef $Macro[[name]]
       #define $Macro[[name]]
       #endif
 
       #define $Macro[[test]]
       #undef $Macro[[test]]
-$InactiveCode[[]]      #ifdef $Macro[[test]]
-$InactiveCode[[]]      #endif
+$InactiveCode[[#ifdef $Macro[[test]]]]
+$InactiveCode[[#endif]]
 
-$InactiveCode[[]]      #if defined($Macro[[test]])
-$InactiveCode[[]]      #endif
+$InactiveCode[[#if defined($Macro[[test]])]]
+$InactiveCode[[#endif]]
     )cpp",
       R"cpp(
       struct $Class[[S]] {
         float $Field[[Value]];
         $Class[[S]] *$Field[[Next]];
       };
       $Class[[S]] $Variable[[Global]][2] = {$Class[[S]](), $Class[[S]]()};
       auto [$Variable[[G1]], $Variable[[G2]]] = $Variable[[Global]];
)cpp",
         $Class[[Foo]]<$TemplateParameter[[TT]], $TemplateParameter[[TTs]]...>
           *$Field[[t]];
       };
     )cpp",
       // Inactive code highlighting
       R"cpp(
       // Code in the preamble.
       // Inactive lines get an empty InactiveCode token at the beginning.
-$InactiveCode[[]]      #ifdef $Macro[[test]]
-$InactiveCode[[]]      #endif
+$InactiveCode[[#ifdef $Macro[[test]]]]
+$InactiveCode[[#endif]]
 
       // A declaration to cause the preamble to end.
       int $Variable[[EndPreamble]];
 
       // Code after the preamble.
       // Code inside inactive blocks does not get regular highlightings
       // because it's not part of the AST.
-$InactiveCode[[]]      #ifdef $Macro[[test]]
-$InactiveCode[[]]      int Inactive2;
-$InactiveCode[[]]      #endif
+$InactiveCode[[#ifdef $Macro[[test]]]]
+$InactiveCode[[int Inactive2;]]
+$InactiveCode[[#endif]]
 
       #ifndef $Macro[[test]]
       int $Variable[[Active1]];
       #endif
 
-$InactiveCode[[]]      #ifdef $Macro[[test]]
-$InactiveCode[[]]      int Inactive3;
-$InactiveCode[[]]      #else
+$InactiveCode[[#ifdef $Macro[[test]]]]
+$InactiveCode[[int Inactive3;]]
+$InactiveCode[[#else]]
       int $Variable[[Active2]];
       #endif
     )cpp",
       // Argument to 'sizeof...'
       R"cpp(
       template <typename... $TemplateParameter[[Elements]]>
       struct $Class[[TupleSize]] {
         static const int $StaticField[[size]] =