diff options
author | Christian Kandeler <christian.kandeler@qt.io> | 2021-10-05 12:27:36 +0200 |
---|---|---|
committer | Christian Kandeler <christian.kandeler@qt.io> | 2021-10-11 08:46:52 +0000 |
commit | a40b7867f60e8823db20b2815ddf0336783ffd37 (patch) | |
tree | 9623d2df2876ea4001a731d3bac16c63569c6321 | |
parent | 9b6f60992cadf3835a9e6d752cfe860bf0da85bc (diff) |
ClangCodeModel: Optimize getAstPath()
Profiling has shown that this function is a hotspot. Luckily, it can be
easily sped up by taking advantage of the fact that the AST nodes are
(mostly) sorted by range, allowing us to employ a binary search when
looking for a given range.
Change-Id: I950c150543ff68b975d36c6fb652d366b93ea3b2
Reviewed-by: David Schulz <david.schulz@qt.io>
-rw-r--r-- | src/libs/languageserverprotocol/lsptypes.cpp | 10 | ||||
-rw-r--r-- | src/libs/languageserverprotocol/lsptypes.h | 9 | ||||
-rw-r--r-- | src/plugins/clangcodemodel/clangdclient.cpp | 50 | ||||
-rw-r--r-- | tests/auto/languageserverprotocol/tst_languageserverprotocol.cpp | 6 |
4 files changed, 61 insertions, 14 deletions
diff --git a/src/libs/languageserverprotocol/lsptypes.cpp b/src/libs/languageserverprotocol/lsptypes.cpp index 820f4b6c4b..65651366a3 100644 --- a/src/libs/languageserverprotocol/lsptypes.cpp +++ b/src/libs/languageserverprotocol/lsptypes.cpp @@ -293,6 +293,14 @@ QTextCursor Position::toTextCursor(QTextDocument *doc) const return cursor; } +Position Position::withOffset(int offset, const QTextDocument *doc) const +{ + int line; + int character; + Utils::Text::convertPosition(doc, toPositionInDocument(doc) + offset, &line, &character); + return Position(line - 1, character - 1); +} + Range::Range(const Position &start, const Position &end) { setStart(start); @@ -323,7 +331,7 @@ bool Range::contains(const Range &other) const bool Range::overlaps(const Range &range) const { - return end() > range.start() && start() < range.end(); + return !isLeftOf(range) && !range.isLeftOf(*this); } QString expressionForGlob(QString globPattern) diff --git a/src/libs/languageserverprotocol/lsptypes.h b/src/libs/languageserverprotocol/lsptypes.h index 7cbe045563..7bd004ca6c 100644 --- a/src/libs/languageserverprotocol/lsptypes.h +++ b/src/libs/languageserverprotocol/lsptypes.h @@ -90,6 +90,7 @@ public: int toPositionInDocument(const QTextDocument *doc) const; QTextCursor toTextCursor(QTextDocument *doc) const; + Position withOffset(int offset, const QTextDocument *doc) const; }; inline bool operator<(const Position &first, const Position &second) @@ -103,6 +104,11 @@ inline bool operator>(const Position &first, const Position &second) return second < first; } +inline bool operator>=(const Position &first, const Position &second) +{ + return !(first < second); +} + inline bool operator<=(const Position &first, const Position &second) { return !(first > second); @@ -124,9 +130,12 @@ public: Position end() const { return typedValue<Position>(endKey); } void setEnd(const Position &end) { insert(endKey, end); } + bool isEmpty() const { return start() == end(); } bool contains(const Position &pos) const { return start() <= pos && pos <= end(); } bool contains(const Range &other) const; bool overlaps(const Range &range) const; + bool isLeftOf(const Range &other) const + { return isEmpty() || other.isEmpty() ? end() < other.start() : end() <= other.start(); } bool isValid() const override { return JsonObject::contains(startKey) && JsonObject::contains(endKey); } diff --git a/src/plugins/clangcodemodel/clangdclient.cpp b/src/plugins/clangcodemodel/clangdclient.cpp index 5b3e76bee8..6d4dac1459 100644 --- a/src/plugins/clangcodemodel/clangdclient.cpp +++ b/src/plugins/clangcodemodel/clangdclient.cpp @@ -298,6 +298,7 @@ static QList<AstNode> getAstPath(const AstNode &root, const Range &range) QList<AstNode> path; QList<AstNode> queue{root}; bool isRoot = true; + while (!queue.isEmpty()) { AstNode curNode = queue.takeFirst(); if (!isRoot && !curNode.hasRange()) @@ -309,13 +310,39 @@ static QList<AstNode> getAstPath(const AstNode &root, const Range &range) const auto children = curNode.children(); if (!children) break; - queue = children.value(); + if (curNode.kind() == "Function" || curNode.role() == "expression") { + // Functions and expressions can contain implicit nodes that make the list unsorted. + // They cannot be ignored, as we need to consider them in certain contexts. + // Therefore, the binary search cannot be used here. + queue = *children; + } else { + queue.clear(); + + // Class and struct nodes can contain implicit constructors, destructors and + // operators, which appear at the end of the list, but whose range is the same + // as the class name. Therefore, we must force them not to compare less to + // anything else. + static const auto leftOfRange = [](const AstNode &node, const Range &range) { + return node.range().isLeftOf(range) && !node.arcanaContains(" implicit "); + }; + + for (auto it = std::lower_bound(children->cbegin(), children->cend(), range, + leftOfRange); + it != children->cend() && !range.isLeftOf(it->range()); ++it) { + queue << *it; + } + } } isRoot = false; } return path; } +static QList<AstNode> getAstPath(const AstNode &root, const Position &pos) +{ + return getAstPath(root, Range(pos, pos)); +} + static Usage::Type getUsageType(const QList<AstNode> &path) { bool potentialWrite = false; @@ -1643,7 +1670,7 @@ void ClangdClient::findLocalUsages(TextDocument *document, const QTextCursor &cu } const Position linkPos(link.targetLine - 1, link.targetColumn); - const QList<AstNode> astPath = getAstPath(ast, Range(linkPos, linkPos)); + const QList<AstNode> astPath = getAstPath(ast, linkPos); bool isVar = false; for (auto it = astPath.rbegin(); it != astPath.rend(); ++it) { if (it->role() == "declaration" && it->kind() == "Function") { @@ -2222,13 +2249,17 @@ static void semanticHighlighter(QFutureInterface<HighlightingResult> &future, } const QTextDocument doc(docContents); - const auto isOutputParameter = [&ast](const ExpandedSemanticToken &token) { + const auto tokenRange = [&doc](const ExpandedSemanticToken &token) { + const Position startPos(token.line - 1, token.column - 1); + const Position endPos = startPos.withOffset(token.length, &doc); + return Range(startPos, endPos); + }; + const auto isOutputParameter = [&ast, &doc, &tokenRange](const ExpandedSemanticToken &token) { if (token.modifiers.contains("usedAsMutableReference")) return true; if (token.type != "variable" && token.type != "property" && token.type != "parameter") return false; - const Position pos(token.line - 1, token.column - 1); - const QList<AstNode> path = getAstPath(ast, Range(pos, pos)); + const QList<AstNode> path = getAstPath(ast, tokenRange(token)); if (path.size() < 2) return false; if (path.last().hasConstType()) @@ -2249,7 +2280,8 @@ static void semanticHighlighter(QFutureInterface<HighlightingResult> &future, }; const std::function<HighlightingResult(const ExpandedSemanticToken &)> toResult - = [&ast, &isOutputParameter, &clangdVersion](const ExpandedSemanticToken &token) { + = [&ast, &isOutputParameter, &clangdVersion, &tokenRange] + (const ExpandedSemanticToken &token) { TextStyles styles; if (token.type == "variable") { if (token.modifiers.contains("functionScope")) { @@ -2263,8 +2295,7 @@ static void semanticHighlighter(QFutureInterface<HighlightingResult> &future, } else if (token.type == "function" || token.type == "method") { styles.mainStyle = token.modifiers.contains("virtual") ? C_VIRTUAL_METHOD : C_FUNCTION; if (ast.isValid()) { - const Position pos(token.line - 1, token.column - 1); - const QList<AstNode> path = getAstPath(ast, Range(pos, pos)); + const QList<AstNode> path = getAstPath(ast, tokenRange(token)); if (path.length() > 1) { const AstNode declNode = path.at(path.length() - 2); if (declNode.kind() == "Function" || declNode.kind() == "CXXMethod") { @@ -2283,8 +2314,7 @@ static void semanticHighlighter(QFutureInterface<HighlightingResult> &future, // clang hardly ever differentiates between constructors and the associated class, // whereas we highlight constructors as functions. if (ast.isValid()) { - const Position pos(token.line - 1, token.column - 1); - const QList<AstNode> path = getAstPath(ast, Range(pos, pos)); + const QList<AstNode> path = getAstPath(ast, tokenRange(token)); if (!path.isEmpty()) { if (path.last().kind() == "CXXConstructor") { if (!path.last().arcanaContains("implicit")) diff --git a/tests/auto/languageserverprotocol/tst_languageserverprotocol.cpp b/tests/auto/languageserverprotocol/tst_languageserverprotocol.cpp index db994a3c5b..20fb60cd53 100644 --- a/tests/auto/languageserverprotocol/tst_languageserverprotocol.cpp +++ b/tests/auto/languageserverprotocol/tst_languageserverprotocol.cpp @@ -552,7 +552,7 @@ void tst_LanguageServerProtocol::range_data() auto pos = [](int pos) { return Position(0, pos); }; QTest::newRow("both ranges empty") - << Range(pos(0), pos(0)) << Range(pos(0), pos(0)) << false << true << true; + << Range(pos(0), pos(0)) << Range(pos(0), pos(0)) << true << true << true; QTest::newRow("equal ranges") << Range(pos(0), pos(1)) << Range(pos(0), pos(1)) << true << true << true; QTest::newRow("r1 before r2") @@ -562,7 +562,7 @@ void tst_LanguageServerProtocol::range_data() QTest::newRow("r1 starts before r2 overlapping") << Range(pos(0), pos(2)) << Range(pos(1), pos(3)) << true << false << false; QTest::newRow("empty r1 on r2 start") - << Range(pos(0), pos(0)) << Range(pos(0), pos(1)) << false << false << true; + << Range(pos(0), pos(0)) << Range(pos(0), pos(1)) << true << false << true; QTest::newRow("r1 inside r2 equal start") << Range(pos(0), pos(1)) << Range(pos(0), pos(2)) << true << false << true; QTest::newRow("r1 inside r2 equal start") @@ -576,7 +576,7 @@ void tst_LanguageServerProtocol::range_data() QTest::newRow("r1 ends after r2 overlapping") << Range(pos(1), pos(3)) << Range(pos(0), pos(2)) << true << false << false; QTest::newRow("empty r1 on r2 end") - << Range(pos(1), pos(1)) << Range(pos(0), pos(1)) << false << false << true; + << Range(pos(1), pos(1)) << Range(pos(0), pos(1)) << true << false << true; QTest::newRow("r1 adjacent after r2") << Range(pos(1), pos(2)) << Range(pos(0), pos(1)) << false << false << false; QTest::newRow("r1 behind r2") |