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,10 @@ // 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) + override; // LSP methods. Notifications have signature void(const Params&). // Calls have signature void(const Params&, Callback). 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 @@ -1090,7 +1090,8 @@ } void ClangdLSPServer::onHighlightingsReady( - PathRef File, std::vector Highlightings) { + PathRef File, + std::vector>> Highlightings) { publishSemanticHighlighting( {{URIForFile::canonicalize(File, /*TUPath=*/File)}, toSemanticHighlightingInformation(Highlightings)}); 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,9 @@ 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) {} }; /// When set, used by ClangdServer to get clang-tidy options for each particular @@ -315,7 +315,7 @@ // can be caused by missing includes (e.g. member access in incomplete type). bool SuggestMissingIncludes = false; bool EnableHiddenFeatures = false; - + std::function TweakFilter; // GUARDED_BY(CachedCompletionFuzzyFindRequestMutex) 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 @@ -64,7 +64,7 @@ if (FIndex) FIndex->updateMain(Path, AST); if (SemanticHighlighting) - DiagConsumer.onHighlightingsReady(Path, getSemanticHighlightings(AST)); + DiagConsumer.onHighlightingsReady(Path, Differ.diffHighlightings(AST, getSemanticHighlightings(AST))); } void onDiagnostics(PathRef File, std::vector Diags) override { @@ -79,6 +79,7 @@ FileIndex *FIndex; DiagnosticsConsumer &DiagConsumer; bool SemanticHighlighting; + HighlightingDiffer Differ; }; } // namespace 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 @@ -40,7 +40,8 @@ }; bool operator==(const HighlightingToken &Lhs, const HighlightingToken &Rhs); - +bool operator!=(const HighlightingToken &Lhs, const HighlightingToken &Rhs); +bool operator<(const HighlightingToken &Lhs, const HighlightingToken &Rhs); // Returns all HighlightingTokens from an AST. Only generates highlights for the // main AST. std::vector getSemanticHighlightings(ParsedAST &AST); @@ -50,8 +51,37 @@ llvm::StringRef toTextMateScope(HighlightingKind Kind); // Convert to LSP's semantic highlighting information. -std::vector -toSemanticHighlightingInformation(llvm::ArrayRef Tokens); +std::vector toSemanticHighlightingInformation( + llvm::ArrayRef>> Tokens); + +/// Class for getting the input highlighting lines that differ the previous +/// highlightings. +class HighlightingDiffer { + std::map> PrevHighlightingsMap; + std::mutex PrevMutex; + + ArrayRef takeLine(ArrayRef AllTokens, + ArrayRef OldLine, + int Line); + +public: + /// Removes every line where the \c Highlightings is the same as the + /// respective line in the previous highlightings this method was called with. + /// If the previous highlightings have a line that does not exist in \c + /// Highlightings an empty line is added. Returns the resulting + /// HighlightingTokens grouped by their line number. + std::vector>> + diffHighlightings(const ParsedAST &AST, + std::vector Highlightings); + + /// Removes every line where \c Highlightings is the same as \c + /// PrevHighlightings. If \c PrevHighlightings has lines that does not exist + /// in \c Highlightings an empty line is added. Returns the resulting + /// HighlightingTokens grouped by their line number. + std::vector>> + diffHighlightings(ArrayRef Highlightings, + ArrayRef PrevHighlightings); +}; } // 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,9 @@ #include "SourceCode.h" #include "clang/AST/ASTContext.h" #include "clang/AST/RecursiveASTVisitor.h" +#include "llvm/ADT/ArrayRef.h" +#include +#include namespace clang { namespace clangd { @@ -101,6 +104,8 @@ private: void addToken(SourceLocation Loc, const NamedDecl *D) { + if (D->isInvalidDecl()) + return; if (D->getDeclName().isIdentifier() && D->getName().empty()) // Don't add symbols that don't have any length. return; @@ -197,31 +202,96 @@ } } // namespace +ArrayRef HighlightingDiffer::takeLine(ArrayRef AllTokens, ArrayRef OldLine, int Line) { + return ArrayRef(OldLine.end(), AllTokens.end()).take_while([Line](const HighlightingToken &Token) -> bool{ + return Token.R.start.line == Line; + }); +} + +std::vector>> +HighlightingDiffer::diffHighlightings( + ArrayRef Highlightings, + ArrayRef PrevHighlightings) { + // 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. + std::vector>> LineTokens; + ArrayRef NewLine(Highlightings.data(), + Highlightings.data()), + OldLine = {PrevHighlightings.data(), PrevHighlightings.data()}, + Current = {Highlightings}, Prev = {PrevHighlightings}; + for (unsigned Line = 0; + NewLine.end() < Current.end() || OldLine.end() < Prev.end(); ++Line) { + NewLine = takeLine(Current, NewLine, Line); + OldLine = takeLine(Prev, OldLine, Line); + if (NewLine != OldLine) + LineTokens.push_back({Line, NewLine}); + } + + return LineTokens; +} + +std::vector>> +HighlightingDiffer::diffHighlightings( + const ParsedAST &AST, std::vector Highlightings) { + std::sort(Highlightings.begin(), Highlightings.end()); + + // FIXME: Want to put a cap on the number of files highlightings we save here + // otherwise this will start hogging memory after a while few files. + auto &SM = AST.getASTContext().getSourceManager(); + const FileEntry *CurrentFileEntry = SM.getFileEntryForID(SM.getMainFileID()); + std::string CurrentPath = CurrentFileEntry->tryGetRealPathName().str() + + CurrentFileEntry->getName().str(); + + // FIXME: This should be LIFO. + ArrayRef PrevHighlightings; + { + std::lock_guard Lock(PrevMutex); + PrevHighlightings = PrevHighlightingsMap[CurrentPath]; + } + auto LineTokens = diffHighlightings(Highlightings, PrevHighlightings); + { + std::lock_guard Lock(PrevMutex); + PrevHighlightingsMap[CurrentPath] = Highlightings; + } + + return LineTokens; +} + bool operator==(const HighlightingToken &Lhs, const HighlightingToken &Rhs) { return Lhs.Kind == Rhs.Kind && Lhs.R == Rhs.R; } +bool operator!=(const HighlightingToken &Lhs, const HighlightingToken &Rhs) { + return !(Lhs == Rhs); +} +bool operator<(const HighlightingToken &Lhs, const HighlightingToken &Rhs) { + return Lhs.R.start < Rhs.R.start; +} std::vector getSemanticHighlightings(ParsedAST &AST) { return HighlightingTokenCollector(AST).collectTokens(); } -std::vector -toSemanticHighlightingInformation(llvm::ArrayRef Tokens) { +std::vector 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 &LinePair : Tokens) { llvm::SmallVector LineByteTokens; llvm::raw_svector_ostream OS(LineByteTokens); - for (const auto &Token : Line.second) { + for (const auto &Token : LinePair.second) { // Writes the token to LineByteTokens in the byte format specified by the // LSP proposal. Described below. // |<---- 4 bytes ---->|<-- 2 bytes -->|<--- 2 bytes -->| @@ -232,7 +302,7 @@ write16be(static_cast(Token.Kind), OS); } - Lines.push_back({Line.first, encodeBase64(LineByteTokens)}); + Lines.push_back({LinePair.first, 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 @@ -37,6 +37,21 @@ # CHECK-NEXT: } # CHECK-NEXT:} --- +{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///foo.cpp","languageId":"cpp","version":1,"text":"int x = 2; int;\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","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,7 +29,9 @@ return Tokens; } -void checkHighlightings(llvm::StringRef Code) { +std::tuple, + std::vector> +getHighlightingsAnnotated(llvm::StringRef Code) { Annotations Test(Code); auto AST = TestTU::withCode(Test.code()).build(); static const std::map KindToString{ @@ -46,9 +48,43 @@ } auto ActualTokens = getSemanticHighlightings(AST); + return {std::move(AST), ActualTokens, ExpectedTokens}; +} + +void checkHighlightings(llvm::StringRef Code) { + std::vector ActualTokens; + std::vector ExpectedTokens; + std::tie(std::ignore, ActualTokens, ExpectedTokens) = + getHighlightingsAnnotated(Code); EXPECT_THAT(ActualTokens, testing::UnorderedElementsAreArray(ExpectedTokens)); } +void checkDiffedHighlights( + const std::vector &ExpectedTokens, + const std::vector &EmptyLines, + std::vector>> &ActualDiffed) { + std::map> ExpectedLines; + for (const HighlightingToken &Token : ExpectedTokens) + ExpectedLines[Token.R.start.line].push_back(Token); + std::vector>> + ExpectedLinePairHighlighting; + for (int Line : EmptyLines) + ExpectedLinePairHighlighting.push_back({Line, {}}); + for (auto LineTokens : ExpectedLines) { + std::sort(LineTokens.second.begin(), LineTokens.second.end()); + ExpectedLinePairHighlighting.push_back( + {LineTokens.first, LineTokens.second}); + } + + // The UnorderedElementsAreArray only checks that the top level vector + // is unordered. The vectors in the pair must be in the correct order. + for (unsigned I = 0, End = ActualDiffed.size(); I < End; ++I) + std::sort(ActualDiffed[I].second.begin(), ActualDiffed[I].second.end()); + + EXPECT_THAT(ActualDiffed, + testing::UnorderedElementsAreArray(ExpectedLinePairHighlighting)); +} + TEST(SemanticHighlighting, GetsCorrectTokens) { const char *TestCases[] = { R"cpp( @@ -145,7 +181,9 @@ void onDiagnosticsReady(PathRef, std::vector) override {} void onHighlightingsReady( - PathRef File, std::vector Highlightings) override { + PathRef File, + std::vector>> + Highlightings) override { ++Count; } }; @@ -170,21 +208,148 @@ 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) { + std::vector< + std::pair, std::pair>> + TestCases{{{}, + { + R"cpp( + int $Variable[[A]] + double $Variable[[B]]; + struct $Class[[C]] {}; + )cpp", + R"cpp( + int A; + double B; + struct C {}; + )cpp"}}, + {{5}, + { + R"cpp( + struct $Class[[Alpha]] { + double SomeVariable = 9483.301; + }; + struct $Class[[Beta]] {}; + int $Variable[[A]] = 121; + $Class[[Alpha]] $Variable[[Var]]; + )cpp", + R"cpp( + struct Alpha { + double SomeVariable = 9483.301; + }; + struct Beta {}; // Some comment + intA = 121; + $Class[[Beta]] $Variable[[Var]]; + )cpp"}}, + {{}, + { + R"cpp( + int $Variable[[A]] = 121; int $Variable[[B]]; + )cpp", + R"cpp( + intA = 121; int $Variable[[B]]; + )cpp"}}, + {{}, + { + R"cpp( + int $Variable[[A]]; + )cpp", + R"cpp( + struct $Class[[A]]; + )cpp"}}, + {{2}, + { + R"cpp( + int $Variable[[ABBA]] = 23; + double $Variable[[C]] = 123.3 * 5; + )cpp", + R"cpp( + int ABBA = 23; + //double C = 123.3 * 5; + float $Variable[[H]]; + )cpp"}}}; + + HighlightingDiffer Differ; + for (auto Test : TestCases) { + ParsedAST AST1 = + TestTU::withCode("").build(); // Can't default construct a ParsedAST. + ParsedAST AST2 = + TestTU::withCode("").build(); // Can't default construct a ParsedAST. + std::vector CompleteTokens1; + std::vector ExpectedTokens; + std::tie(AST1, CompleteTokens1, ExpectedTokens) = + getHighlightingsAnnotated(Test.second.first); + std::vector CompleteTokens2; + std::tie(AST1, CompleteTokens2, ExpectedTokens) = + getHighlightingsAnnotated(Test.second.second); + + std::vector>> DiffedTokens = + Differ.diffHighlightings(CompleteTokens2, CompleteTokens1); + + checkDiffedHighlights(ExpectedTokens, Test.first, DiffedTokens); + } +} + +TEST(SemanticHighlighting, HighlightingDifferState) { + std::vector, const char *>>> TestCases{ + {{{}, R"cpp( + int $Variable[[A]] = 213; + )cpp"}, + {{}, R"cpp( + int C = 312; + int $Variable[[B]] = 213; + )cpp"}, + {{}, R"cpp( + int C = 213; + int B = 412; + )cpp"}, + {{}, R"cpp( + struct $Class[[A]] { + void $Function[[foo]](); + + int A; + }; + )cpp"}, + {{2}, R"cpp( + struct A { + // void foo(); + }; + int $Variable[[B]]; + )cpp"}}}; + + for (auto Test : TestCases) { + HighlightingDiffer Differ; + for (const auto &MissingCodePair : Test) { + ParsedAST AST = + TestTU::withCode("").build(); // Can't default construct a ParsedAST. + std::vector CompleteTokens; + std::vector ExpectedTokens; + std::tie(AST, CompleteTokens, ExpectedTokens) = + getHighlightingsAnnotated(MissingCodePair.second); + std::vector>> DiffedTokens = + Differ.diffHighlightings(AST, CompleteTokens); + checkDiffedHighlights(ExpectedTokens, MissingCodePair.first, + DiffedTokens); + } + } +} + } // namespace } // namespace clangd } // namespace clang