diff --git a/clang-tools-extra/clangd/ClangdLSPServer.h b/clang-tools-extra/clangd/ClangdLSPServer.h --- a/clang-tools-extra/clangd/ClangdLSPServer.h +++ b/clang-tools-extra/clangd/ClangdLSPServer.h @@ -55,9 +55,9 @@ // Implement DiagnosticsConsumer. void onDiagnosticsReady(PathRef File, std::vector Diagnostics) override; void onFileUpdated(PathRef File, const TUStatus &Status) override; - void - onHighlightingsReady(PathRef File, - std::vector Highlightings) override; + void onHighlightingsReady(PathRef File, + std::vector Highlightings, + int NLines) override; // LSP methods. Notifications have signature void(const Params&). // Calls have signature void(const Params&, Callback). @@ -136,6 +136,8 @@ DiagnosticToReplacementMap; /// Caches FixIts per file and diagnostics llvm::StringMap FixItsMap; + std::mutex HighlightingsMutex; + llvm::StringMap> FileToHighlightings; // Most code should not deal with Transport directly. // MessageHandler deals with incoming messages, use call() etc for outgoing. diff --git a/clang-tools-extra/clangd/ClangdLSPServer.cpp b/clang-tools-extra/clangd/ClangdLSPServer.cpp --- a/clang-tools-extra/clangd/ClangdLSPServer.cpp +++ b/clang-tools-extra/clangd/ClangdLSPServer.cpp @@ -452,6 +452,12 @@ void ClangdLSPServer::onDocumentDidOpen( const DidOpenTextDocumentParams &Params) { PathRef File = Params.textDocument.uri.file(); + { + // If a file was closed before highlightings were generated for the last + // edit there are stale previous highlightings. + std::lock_guard Lock(HighlightingsMutex); + FileToHighlightings.erase(File); + } const std::string &Contents = Params.textDocument.text; @@ -601,6 +607,10 @@ std::lock_guard Lock(FixItsMutex); FixItsMap.erase(File); } + { + std::lock_guard HLock(HighlightingsMutex); + FileToHighlightings.erase(File); + } // clangd will not send updates for this file anymore, so we empty out the // list of diagnostics shown on the client (e.g. in the "Problems" pane of // VSCode). Note that this cannot race with actual diagnostics responses @@ -1098,10 +1108,20 @@ } void ClangdLSPServer::onHighlightingsReady( - PathRef File, std::vector Highlightings) { + PathRef File, std::vector Highlightings, int NLines) { + std::vector Old; + { + std::lock_guard Lock(HighlightingsMutex); + Old = std::move(FileToHighlightings[File]); + FileToHighlightings[File] = Highlightings; + } + // LSP allows us to send incremental edits of highlightings. Also need to diff + // to remove highlightings from tokens that should no longer have them. + std::vector Diffed = + diffHighlightings(Highlightings, Old, NLines); publishSemanticHighlighting( {{URIForFile::canonicalize(File, /*TUPath=*/File)}, - toSemanticHighlightingInformation(Highlightings)}); + toSemanticHighlightingInformation(Diffed)}); } void ClangdLSPServer::onDiagnosticsReady(PathRef File, diff --git a/clang-tools-extra/clangd/ClangdServer.h b/clang-tools-extra/clangd/ClangdServer.h --- a/clang-tools-extra/clangd/ClangdServer.h +++ b/clang-tools-extra/clangd/ClangdServer.h @@ -52,9 +52,8 @@ virtual void onFileUpdated(PathRef File, const TUStatus &Status){}; /// Called by ClangdServer when some \p Highlightings for \p File are ready. - virtual void - onHighlightingsReady(PathRef File, - std::vector Highlightings) {} + virtual void onHighlightingsReady( + PathRef File, std::vector Highlightings, int NLines) {} }; /// When set, used by ClangdServer to get clang-tidy options for each particular diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp --- a/clang-tools-extra/clangd/ClangdServer.cpp +++ b/clang-tools-extra/clangd/ClangdServer.cpp @@ -63,8 +63,18 @@ void onMainAST(PathRef Path, ParsedAST &AST) override { if (FIndex) FIndex->updateMain(Path, AST); - if (SemanticHighlighting) - DiagConsumer.onHighlightingsReady(Path, getSemanticHighlightings(AST)); + if (SemanticHighlighting) { + // FIXME: We need a better way to send the maximum line number to the + // differ. + // The differ needs the information about the max number of lines + // to not send diffs that are outside the file. + const SourceManager &SM = AST.getSourceManager(); + FileID MainFileID = SM.getMainFileID(); + unsigned int FileSize = SM.getFileEntryForID(MainFileID)->getSize(); + int NLines = AST.getSourceManager().getLineNumber(MainFileID, FileSize); + DiagConsumer.onHighlightingsReady(Path, getSemanticHighlightings(AST), + NLines); + } } void onDiagnostics(PathRef File, std::vector Diags) override { diff --git a/clang-tools-extra/clangd/SemanticHighlighting.h b/clang-tools-extra/clangd/SemanticHighlighting.h --- a/clang-tools-extra/clangd/SemanticHighlighting.h +++ b/clang-tools-extra/clangd/SemanticHighlighting.h @@ -43,7 +43,16 @@ Range R; }; -bool operator==(const HighlightingToken &Lhs, const HighlightingToken &Rhs); +bool operator==(const HighlightingToken &L, const HighlightingToken &R); +bool operator<(const HighlightingToken &L, const HighlightingToken &R); + +/// Contains all information about highlightings on a single line. +struct LineHighlightings { + int Line; + std::vector Tokens; +}; + +bool operator==(const LineHighlightings &L, const LineHighlightings &R); // Returns all HighlightingTokens from an AST. Only generates highlights for the // main AST. @@ -53,9 +62,22 @@ /// (https://manual.macromates.com/en/language_grammars). llvm::StringRef toTextMateScope(HighlightingKind Kind); -// Convert to LSP's semantic highlighting information. +/// Convert to LSP's semantic highlighting information. std::vector -toSemanticHighlightingInformation(llvm::ArrayRef Tokens); +toSemanticHighlightingInformation(llvm::ArrayRef Tokens); + +// Return a line-by-line diff between two highlightings. +// - if the tokens on a line are the same in both hightlightings this line is +// omitted. +// - if a line exists in New but not in Old the tokens +// on this line is emitted., we emit the tokens on this line +// - if a line not exists in New but in Old an empty +// line is emitted (to tell client to clear the previous highlightings on this +// line) +/// REQUIRED: Old and New are sorted. +std::vector +diffHighlightings(ArrayRef New, + ArrayRef Old, int NLines); } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/SemanticHighlighting.cpp b/clang-tools-extra/clangd/SemanticHighlighting.cpp --- a/clang-tools-extra/clangd/SemanticHighlighting.cpp +++ b/clang-tools-extra/clangd/SemanticHighlighting.cpp @@ -12,6 +12,7 @@ #include "SourceCode.h" #include "clang/AST/ASTContext.h" #include "clang/AST/RecursiveASTVisitor.h" +#include namespace clang { namespace clangd { @@ -33,10 +34,7 @@ TraverseAST(Ctx); // 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); - }); + llvm::sort(Tokens); auto Last = std::unique(Tokens.begin(), Tokens.end()); Tokens.erase(Last, Tokens.end()); return Tokens; @@ -260,10 +258,74 @@ llvm::support::endian::write16be(Buf.data(), I); OS.write(Buf.data(), Buf.size()); } + +// Get the highlightings on \c Line where the first entry of line is at \c +// StartLineIt. If it is not at \c StartLineIt an empty vector is returned. +ArrayRef +takeLine(ArrayRef AllTokens, + ArrayRef::iterator StartLineIt, int Line) { + return ArrayRef(StartLineIt, AllTokens.end()) + .take_while([Line](const HighlightingToken &Token) { + return Token.R.start.line == Line; + }); +} } // namespace -bool operator==(const HighlightingToken &Lhs, const HighlightingToken &Rhs) { - return Lhs.Kind == Rhs.Kind && Lhs.R == Rhs.R; +std::vector +diffHighlightings(ArrayRef New, + ArrayRef Old, int NLines) { + assert(std::is_sorted(New.begin(), New.end()) && "New must be a sorted vector"); + assert(std::is_sorted(Old.begin(), Old.end()) && "Old must be a sorted vector"); + + // FIXME: There's an edge case when tokens span multiple lines. If the first + // token on the line started on a line above the current one and the rest of + // the line is the equal to the previous one than we will remove all + // highlights but the ones for the token spanning multiple lines. This means + // that when we get into the LSP layer the only highlights that will be + // visible are the ones for the token spanning multiple lines. + // Example: + // EndOfMultilineToken Token Token Token + // If "Token Token Token" don't differ from previously the line is + // incorrectly removed. Suggestion to fix is to separate any multiline tokens + // into one token for every line it covers. This requires reading from the + // file buffer to figure out the length of each line though. + std::vector DiffedLines; + // ArrayRefs to the current line in the highlights. + ArrayRef NewLine(New.begin(), + /*length*/0UL); + ArrayRef OldLine(Old.begin(), + /*length*/ 0UL); + auto NewEnd = New.end(); + auto OldEnd = Old.end(); + auto NextLine = [&]() { + int NextNew = NewLine.end() != NewEnd ? NewLine.end()->R.start.line + : std::numeric_limits::max(); + int NextOld = OldLine.end() != OldEnd ? OldLine.end()->R.start.line + : std::numeric_limits::max(); + return std::min(NextNew, NextOld); + }; + + // If the New file has fewer lines than the Old file we don't want to send + // highlightings beyond the end of the file. That might crash the client. + for (int Line = 0; Line != std::numeric_limits::max() && Line < NLines; + Line = NextLine()) { + NewLine = takeLine(New, NewLine.end(), Line); + OldLine = takeLine(Old, OldLine.end(), Line); + if (NewLine != OldLine) + DiffedLines.push_back({Line, NewLine}); + } + + return DiffedLines; +} + +bool operator==(const HighlightingToken &L, const HighlightingToken &R) { + return std::tie(L.R, L.Kind) == std::tie(R.R, R.Kind); +} +bool operator<(const HighlightingToken &L, const HighlightingToken &R) { + return std::tie(L.R, L.Kind) < std::tie(R.R, R.Kind); +} +bool operator==(const LineHighlightings &L, const LineHighlightings &R) { + return std::tie(L.Line, L.Tokens) == std::tie(R.Line, R.Tokens); } std::vector getSemanticHighlightings(ParsedAST &AST) { @@ -271,22 +333,18 @@ } std::vector -toSemanticHighlightingInformation(llvm::ArrayRef Tokens) { +toSemanticHighlightingInformation(llvm::ArrayRef Tokens) { if (Tokens.size() == 0) return {}; // FIXME: Tokens might be multiple lines long (block comments) in this case // this needs to add multiple lines for those tokens. - std::map> TokenLines; - for (const HighlightingToken &Token : Tokens) - TokenLines[Token.R.start.line].push_back(Token); - std::vector Lines; - Lines.reserve(TokenLines.size()); - for (const auto &Line : TokenLines) { + Lines.reserve(Tokens.size()); + for (const auto &Line : Tokens) { llvm::SmallVector LineByteTokens; llvm::raw_svector_ostream OS(LineByteTokens); - for (const auto &Token : Line.second) { + for (const auto &Token : Line.Tokens) { // Writes the token to LineByteTokens in the byte format specified by the // LSP proposal. Described below. // |<---- 4 bytes ---->|<-- 2 bytes -->|<--- 2 bytes -->| @@ -297,7 +355,7 @@ write16be(static_cast(Token.Kind), OS); } - Lines.push_back({Line.first, encodeBase64(LineByteTokens)}); + Lines.push_back({Line.Line, encodeBase64(LineByteTokens)}); } return Lines; diff --git a/clang-tools-extra/clangd/test/semantic-highlighting.test b/clang-tools-extra/clangd/test/semantic-highlighting.test --- a/clang-tools-extra/clangd/test/semantic-highlighting.test +++ b/clang-tools-extra/clangd/test/semantic-highlighting.test @@ -49,6 +49,50 @@ # CHECK-NEXT: } # CHECK-NEXT:} --- +{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///foo2.cpp","languageId":"cpp","version":1,"text":"int x = 2;\nint y = 2;"}}} +# CHECK: "method": "textDocument/semanticHighlighting", +# CHECK-NEXT: "params": { +# CHECK-NEXT: "lines": [ +# CHECK-NEXT: { +# CHECK-NEXT: "line": 0, +# CHECK-NEXT: "tokens": "AAAABAABAAA=" +# CHECK-NEXT: } +# CHECK-NEXT: { +# CHECK-NEXT: "line": 1, +# CHECK-NEXT: "tokens": "AAAABAABAAA=" +# CHECK-NEXT: } +# CHECK-NEXT: ], +# CHECK-NEXT: "textDocument": { +# CHECK-NEXT: "uri": "file:///clangd-test/foo2.cpp" +# CHECK-NEXT: } +# CHECK-NEXT: } +# CHECK-NEXT:} +--- +{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.cpp","version":2},"contentChanges": [{"range":{"start": {"line": 0,"character": 10},"end": {"line": 0,"character": 10}},"rangeLength": 0,"text": "\nint y = 2;"}]}} +# CHECK: "method": "textDocument/semanticHighlighting", +# CHECK-NEXT: "params": { +# CHECK-NEXT: "lines": [ +# CHECK-NEXT: { +# CHECK-NEXT: "line": 1, +# CHECK-NEXT: "tokens": "AAAABAABAAA=" +# CHECK-NEXT: } +# CHECK-NEXT: ], +# CHECK-NEXT: "textDocument": { +# CHECK-NEXT: "uri": "file:///clangd-test/foo.cpp" +# CHECK-NEXT: } +# CHECK-NEXT: } +# CHECK-NEXT:} +--- +{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.cpp","version":2},"contentChanges": [{"range":{"start": {"line": 0,"character": 10},"end": {"line": 1,"character": 10}},"rangeLength": 11,"text": ""}]}} +# CHECK: "method": "textDocument/semanticHighlighting", +# CHECK-NEXT: "params": { +# CHECK-NEXT: "lines": [], +# CHECK-NEXT: "textDocument": { +# CHECK-NEXT: "uri": "file:///clangd-test/foo.cpp" +# CHECK-NEXT: } +# CHECK-NEXT: } +# CHECK-NEXT:} +--- {"jsonrpc":"2.0","id":3,"method":"shutdown"} --- {"jsonrpc":"2.0","method":"exit"} diff --git a/clang-tools-extra/clangd/unittests/SemanticHighlightingTests.cpp b/clang-tools-extra/clangd/unittests/SemanticHighlightingTests.cpp --- a/clang-tools-extra/clangd/unittests/SemanticHighlightingTests.cpp +++ b/clang-tools-extra/clangd/unittests/SemanticHighlightingTests.cpp @@ -29,9 +29,7 @@ return Tokens; } -void checkHighlightings(llvm::StringRef Code) { - Annotations Test(Code); - auto AST = TestTU::withCode(Test.code()).build(); +std::vector getExpectedTokens(Annotations &Test) { static const std::map KindToString{ {HighlightingKind::Variable, "Variable"}, {HighlightingKind::Function, "Function"}, @@ -48,9 +46,43 @@ Test.ranges(KindString.second), KindString.first); ExpectedTokens.insert(ExpectedTokens.end(), Toks.begin(), Toks.end()); } + llvm::sort(ExpectedTokens); + return ExpectedTokens; +} + +void checkHighlightings(llvm::StringRef Code) { + Annotations Test(Code); + auto AST = TestTU::withCode(Test.code()).build(); + std::vector ActualTokens = getSemanticHighlightings(AST); + EXPECT_THAT(ActualTokens, getExpectedTokens(Test)); +} + +void checkDiffedHighlights(llvm::StringRef OldCode, llvm::StringRef NewCode, + llvm::ArrayRef DiffedLines) { + Annotations OldTest(OldCode); + Annotations NewTest(NewCode); + std::vector OldTokens = getExpectedTokens(OldTest); + std::vector NewTokens = getExpectedTokens(NewTest); + + std::map> ExpectedLines; + for (int Line : DiffedLines) { + ExpectedLines[Line]; // Default initialize to an empty line. Tokens are + // inserted on these lines later. + } + std::vector ExpectedLinePairHighlighting; + for (const HighlightingToken &Token : NewTokens) { + auto It = ExpectedLines.find(Token.R.start.line); + if (It != ExpectedLines.end()) + It->second.push_back(Token); + } + for (auto &LineTokens : ExpectedLines) + ExpectedLinePairHighlighting.push_back( + {LineTokens.first, LineTokens.second}); - auto ActualTokens = getSemanticHighlightings(AST); - EXPECT_THAT(ActualTokens, testing::UnorderedElementsAreArray(ExpectedTokens)); + std::vector ActualDiffed = + diffHighlightings(NewTokens, OldTokens, NewCode.count('\n')); + EXPECT_THAT(ActualDiffed, + testing::UnorderedElementsAreArray(ExpectedLinePairHighlighting)); } TEST(SemanticHighlighting, GetsCorrectTokens) { @@ -225,8 +257,9 @@ std::atomic Count = {0}; void onDiagnosticsReady(PathRef, std::vector) override {} - void onHighlightingsReady( - PathRef File, std::vector Highlightings) override { + void onHighlightingsReady(PathRef File, + std::vector Highlightings, + int NLines) override { ++Count; } }; @@ -251,21 +284,135 @@ return Pos; }; - std::vector Tokens{ - {HighlightingKind::Variable, - Range{CreatePosition(3, 8), CreatePosition(3, 12)}}, - {HighlightingKind::Function, - Range{CreatePosition(3, 4), CreatePosition(3, 7)}}, - {HighlightingKind::Variable, - Range{CreatePosition(1, 1), CreatePosition(1, 5)}}}; + std::vector Tokens{ + {3, + {{HighlightingKind::Variable, + Range{CreatePosition(3, 8), CreatePosition(3, 12)}}, + {HighlightingKind::Function, + Range{CreatePosition(3, 4), CreatePosition(3, 7)}}}}, + {1, + {{HighlightingKind::Variable, + Range{CreatePosition(1, 1), CreatePosition(1, 5)}}}}}; std::vector ActualResults = toSemanticHighlightingInformation(Tokens); std::vector ExpectedResults = { - {1, "AAAAAQAEAAA="}, - {3, "AAAACAAEAAAAAAAEAAMAAQ=="}}; + {3, "AAAACAAEAAAAAAAEAAMAAQ=="}, {1, "AAAAAQAEAAA="}}; EXPECT_EQ(ActualResults, ExpectedResults); } +TEST(SemanticHighlighting, HighlightingDiffer) { + struct { + llvm::StringRef OldCode; + llvm::StringRef NewCode; + std::vector DiffedLines; + } TestCases[]{ + { + R"cpp( + $Variable[[A]] + $Class[[B]] + $Function[[C]] + )cpp", + R"cpp( + $Variable[[A]] + $Class[[D]] + $Function[[C]] + )cpp", + {}}, + { + R"cpp( + $Class[[C]] + $Field[[F]] + $Variable[[V]] + $Class[[C]] $Variable[[V]] $Field[[F]] + )cpp", + R"cpp( + $Class[[C]] + $Field[[F]] + $Function[[F]] + $Class[[C]] $Variable[[V]] $Field[[F]] + )cpp", + {3}}, + { + R"cpp( + + $Class[[A]] + $Variable[[A]] + )cpp", + R"cpp( + + + $Class[[A]] + $Variable[[A]] + )cpp", + {2, 3, 4}}, + { + R"cpp( + $Class[[C]] + $Field[[F]] + $Variable[[V]] + $Class[[C]] $Variable[[V]] $Field[[F]] + )cpp", + R"cpp( + $Class[[C]] + + + $Class[[C]] $Variable[[V]] $Field[[F]] + )cpp", + {2, 3}}, + { + R"cpp( + $Class[[A]] + $Variable[[A]] + $Variable[[A]] + )cpp", + R"cpp( + $Class[[A]] + $Variable[[AA]] + $Variable[[A]] + )cpp", + {2}}, + { + R"cpp( + $Class[[A]] + $Variable[[A]] + $Class[[A]] + $Variable[[A]] + )cpp", + R"cpp( + $Class[[A]] + $Variable[[A]] + )cpp", + {}}, + { + R"cpp( + $Class[[A]] + $Variable[[A]] + )cpp", + R"cpp( + $Class[[A]] + $Variable[[A]] + $Class[[A]] + $Variable[[A]] + )cpp", + {3, 4}}, + { + R"cpp( + $Variable[[A]] + $Variable[[A]] + $Variable[[A]] + )cpp", + R"cpp( + $Class[[A]] + $Class[[A]] + $Class[[A]] + )cpp", + {1, 2, 3}} + }; + + for (const auto &Test : TestCases) + checkDiffedHighlights(Test.OldCode, Test.NewCode, Test.DiffedLines); +} + } // namespace } // namespace clangd } // namespace clang