Skip to content

Commit d7cb5b8

Browse files
author
Eric Liu
committedFeb 6, 2019
[clangd] Add type boost to fuzzy find in Dex.
Summary: No noticeable impact on code completions overall except some improvement on cross-namespace completion. Reviewers: sammccall, ilya-biryukov Reviewed By: sammccall Subscribers: MaskRay, jkorous, arphaman, kadircet, cfe-commits Tags: #clang Differential Revision: https://reviews.llvm.org/D57815 llvm-svn: 353310
·
llvmorg-21-initllvmorg-9.0.0-rc1
1 parent ea27b59 commit d7cb5b8

File tree

7 files changed

+97
-50
lines changed

7 files changed

+97
-50
lines changed
 

‎clang-tools-extra/clangd/CodeComplete.cpp

+2
Original file line numberDiff line numberDiff line change
@@ -1333,6 +1333,8 @@ class CodeCompleteFlow {
13331333
Req.AnyScope = AllScopes;
13341334
// FIXME: we should send multiple weighted paths here.
13351335
Req.ProximityPaths.push_back(FileName);
1336+
if (PreferredType)
1337+
Req.PreferredTypes.push_back(PreferredType->raw());
13361338
vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
13371339

13381340
if (SpecFuzzyFind)

‎clang-tools-extra/clangd/index/Index.cpp

+3-1
Original file line numberDiff line numberDiff line change
@@ -179,7 +179,8 @@ bool fromJSON(const llvm::json::Value &Parameters, FuzzyFindRequest &Request) {
179179
O && O.map("Query", Request.Query) && O.map("Scopes", Request.Scopes) &&
180180
O.map("AnyScope", Request.AnyScope) && O.map("Limit", Limit) &&
181181
O.map("RestrictForCodeCompletion", Request.RestrictForCodeCompletion) &&
182-
O.map("ProximityPaths", Request.ProximityPaths);
182+
O.map("ProximityPaths", Request.ProximityPaths) &&
183+
O.map("PreferredTypes", Request.PreferredTypes);
183184
if (OK && Limit <= std::numeric_limits<uint32_t>::max())
184185
Request.Limit = Limit;
185186
return OK;
@@ -193,6 +194,7 @@ llvm::json::Value toJSON(const FuzzyFindRequest &Request) {
193194
{"Limit", Request.Limit},
194195
{"RestrictForCodeCompletion", Request.RestrictForCodeCompletion},
195196
{"ProximityPaths", llvm::json::Array{Request.ProximityPaths}},
197+
{"PreferredTypes", llvm::json::Array{Request.PreferredTypes}},
196198
};
197199
}
198200

‎clang-tools-extra/clangd/index/Index.h

+5-4
Original file line numberDiff line numberDiff line change
@@ -454,14 +454,15 @@ struct FuzzyFindRequest {
454454
/// Contextually relevant files (e.g. the file we're code-completing in).
455455
/// Paths should be absolute.
456456
std::vector<std::string> ProximityPaths;
457-
458-
// FIXME(ibiryukov): add expected type to the request.
457+
/// Preferred types of symbols. These are raw representation of `OpaqueType`.
458+
std::vector<std::string> PreferredTypes;
459459

460460
bool operator==(const FuzzyFindRequest &Req) const {
461461
return std::tie(Query, Scopes, Limit, RestrictForCodeCompletion,
462-
ProximityPaths) ==
462+
ProximityPaths, PreferredTypes) ==
463463
std::tie(Req.Query, Req.Scopes, Req.Limit,
464-
Req.RestrictForCodeCompletion, Req.ProximityPaths);
464+
Req.RestrictForCodeCompletion, Req.ProximityPaths,
465+
Req.PreferredTypes);
465466
}
466467
bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
467468
};

‎clang-tools-extra/clangd/index/dex/Dex.cpp

+56-43
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,6 @@ const Token RestrictedForCodeCompletion =
4242
// Returns the tokens which are given symbols's characteristics. For example,
4343
// trigrams and scopes.
4444
// FIXME(kbobyrev): Support more token types:
45-
// * Types
4645
// * Namespace proximity
4746
std::vector<Token> generateSearchTokens(const Symbol &Sym) {
4847
std::vector<Token> Result = generateIdentifierTrigrams(Sym.Name);
@@ -54,49 +53,11 @@ std::vector<Token> generateSearchTokens(const Symbol &Sym) {
5453
Result.emplace_back(Token::Kind::ProximityURI, ProximityURI);
5554
if (Sym.Flags & Symbol::IndexedForCodeCompletion)
5655
Result.emplace_back(RestrictedForCodeCompletion);
56+
if (!Sym.Type.empty())
57+
Result.emplace_back(Token::Kind::Type, Sym.Type);
5758
return Result;
5859
}
5960

60-
// Constructs BOOST iterators for Path Proximities.
61-
std::unique_ptr<Iterator> createFileProximityIterator(
62-
llvm::ArrayRef<std::string> ProximityPaths,
63-
const llvm::DenseMap<Token, PostingList> &InvertedIndex,
64-
const Corpus &Corpus) {
65-
std::vector<std::unique_ptr<Iterator>> BoostingIterators;
66-
// Deduplicate parent URIs extracted from the ProximityPaths.
67-
llvm::StringSet<> ParentURIs;
68-
llvm::StringMap<SourceParams> Sources;
69-
for (const auto &Path : ProximityPaths) {
70-
Sources[Path] = SourceParams();
71-
auto PathURI = URI::create(Path);
72-
const auto PathProximityURIs = generateProximityURIs(PathURI.toString());
73-
for (const auto &ProximityURI : PathProximityURIs)
74-
ParentURIs.insert(ProximityURI);
75-
}
76-
// Use SymbolRelevanceSignals for symbol relevance evaluation: use defaults
77-
// for all parameters except for Proximity Path distance signal.
78-
SymbolRelevanceSignals PathProximitySignals;
79-
// DistanceCalculator will find the shortest distance from ProximityPaths to
80-
// any URI extracted from the ProximityPaths.
81-
URIDistance DistanceCalculator(Sources);
82-
PathProximitySignals.FileProximityMatch = &DistanceCalculator;
83-
// Try to build BOOST iterator for each Proximity Path provided by
84-
// ProximityPaths. Boosting factor should depend on the distance to the
85-
// Proximity Path: the closer processed path is, the higher boosting factor.
86-
for (const auto &ParentURI : ParentURIs.keys()) {
87-
Token Tok(Token::Kind::ProximityURI, ParentURI);
88-
const auto It = InvertedIndex.find(Tok);
89-
if (It != InvertedIndex.end()) {
90-
// FIXME(kbobyrev): Append LIMIT on top of every BOOST iterator.
91-
PathProximitySignals.SymbolURI = ParentURI;
92-
BoostingIterators.push_back(Corpus.boost(
93-
It->second.iterator(&It->first), PathProximitySignals.evaluate()));
94-
}
95-
}
96-
BoostingIterators.push_back(Corpus.all());
97-
return Corpus.unionOf(std::move(BoostingIterators));
98-
}
99-
10061
} // namespace
10162

10263
void Dex::buildIndex() {
@@ -141,6 +102,57 @@ std::unique_ptr<Iterator> Dex::iterator(const Token &Tok) const {
141102
: It->second.iterator(&It->first);
142103
}
143104

105+
// Constructs BOOST iterators for Path Proximities.
106+
std::unique_ptr<Iterator> Dex::createFileProximityIterator(
107+
llvm::ArrayRef<std::string> ProximityPaths) const {
108+
std::vector<std::unique_ptr<Iterator>> BoostingIterators;
109+
// Deduplicate parent URIs extracted from the ProximityPaths.
110+
llvm::StringSet<> ParentURIs;
111+
llvm::StringMap<SourceParams> Sources;
112+
for (const auto &Path : ProximityPaths) {
113+
Sources[Path] = SourceParams();
114+
auto PathURI = URI::create(Path);
115+
const auto PathProximityURIs = generateProximityURIs(PathURI.toString());
116+
for (const auto &ProximityURI : PathProximityURIs)
117+
ParentURIs.insert(ProximityURI);
118+
}
119+
// Use SymbolRelevanceSignals for symbol relevance evaluation: use defaults
120+
// for all parameters except for Proximity Path distance signal.
121+
SymbolRelevanceSignals PathProximitySignals;
122+
// DistanceCalculator will find the shortest distance from ProximityPaths to
123+
// any URI extracted from the ProximityPaths.
124+
URIDistance DistanceCalculator(Sources);
125+
PathProximitySignals.FileProximityMatch = &DistanceCalculator;
126+
// Try to build BOOST iterator for each Proximity Path provided by
127+
// ProximityPaths. Boosting factor should depend on the distance to the
128+
// Proximity Path: the closer processed path is, the higher boosting factor.
129+
for (const auto &ParentURI : ParentURIs.keys()) {
130+
// FIXME(kbobyrev): Append LIMIT on top of every BOOST iterator.
131+
auto It = iterator(Token(Token::Kind::ProximityURI, ParentURI));
132+
if (It->kind() != Iterator::Kind::False) {
133+
PathProximitySignals.SymbolURI = ParentURI;
134+
BoostingIterators.push_back(
135+
Corpus.boost(std::move(It), PathProximitySignals.evaluate()));
136+
}
137+
}
138+
BoostingIterators.push_back(Corpus.all());
139+
return Corpus.unionOf(std::move(BoostingIterators));
140+
}
141+
142+
// Constructs BOOST iterators for preferred types.
143+
std::unique_ptr<Iterator>
144+
Dex::createTypeBoostingIterator(llvm::ArrayRef<std::string> Types) const {
145+
std::vector<std::unique_ptr<Iterator>> BoostingIterators;
146+
SymbolRelevanceSignals PreferredTypeSignals;
147+
PreferredTypeSignals.TypeMatchesPreferred = true;
148+
auto Boost = PreferredTypeSignals.evaluate();
149+
for (const auto &T : Types)
150+
BoostingIterators.push_back(
151+
Corpus.boost(iterator(Token(Token::Kind::Type, T)), Boost));
152+
BoostingIterators.push_back(Corpus.all());
153+
return Corpus.unionOf(std::move(BoostingIterators));
154+
}
155+
144156
/// Constructs iterators over tokens extracted from the query and exhausts it
145157
/// while applying Callback to each symbol in the order of decreasing quality
146158
/// of the matched symbols.
@@ -174,8 +186,9 @@ bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
174186
Criteria.push_back(Corpus.unionOf(move(ScopeIterators)));
175187

176188
// Add proximity paths boosting (all symbols, some boosted).
177-
Criteria.push_back(
178-
createFileProximityIterator(Req.ProximityPaths, InvertedIndex, Corpus));
189+
Criteria.push_back(createFileProximityIterator(Req.ProximityPaths));
190+
// Add boosting for preferred types.
191+
Criteria.push_back(createTypeBoostingIterator(Req.PreferredTypes));
179192

180193
if (Req.RestrictForCodeCompletion)
181194
Criteria.push_back(iterator(RestrictedForCodeCompletion));

‎clang-tools-extra/clangd/index/dex/Dex.h

+4
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,10 @@ class Dex : public SymbolIndex {
7777
private:
7878
void buildIndex();
7979
std::unique_ptr<Iterator> iterator(const Token &Tok) const;
80+
std::unique_ptr<Iterator>
81+
createFileProximityIterator(llvm::ArrayRef<std::string> ProximityPaths) const;
82+
std::unique_ptr<Iterator>
83+
createTypeBoostingIterator(llvm::ArrayRef<std::string> Types) const;
8084

8185
/// Stores symbols sorted in the descending order of symbol quality..
8286
std::vector<const Symbol *> Symbols;

‎clang-tools-extra/clangd/index/dex/Token.h

+5-2
Original file line numberDiff line numberDiff line change
@@ -62,11 +62,11 @@ struct Token {
6262
/// Example: "file:///path/to/clang-tools-extra/clangd/index/SymbolIndex.h"
6363
/// and some amount of its parents.
6464
ProximityURI,
65+
/// Type of symbol (see `Symbol::Type`).
66+
Type,
6567
/// Internal Token type for invalid/special tokens, e.g. empty tokens for
6668
/// llvm::DenseMap.
6769
Sentinel,
68-
/// FIXME(kbobyrev): Add other Token Kinds
69-
/// * Type with qualified type name or its USR
7070
};
7171

7272
Token(Kind TokenKind, llvm::StringRef Data)
@@ -91,6 +91,9 @@ struct Token {
9191
case Kind::ProximityURI:
9292
OS << "U=";
9393
break;
94+
case Kind::Type:
95+
OS << "Ty=";
96+
break;
9497
case Kind::Sentinel:
9598
OS << "?=";
9699
break;

‎clang-tools-extra/unittests/clangd/DexTests.cpp

+22
Original file line numberDiff line numberDiff line change
@@ -688,6 +688,28 @@ TEST(DexTests, Refs) {
688688
EXPECT_THAT(Files, ElementsAre(AnyOf("foo.h", "foo.cc")));
689689
}
690690

691+
TEST(DexTest, PreferredTypesBoosting) {
692+
auto Sym1 = symbol("t1");
693+
Sym1.Type = "T1";
694+
auto Sym2 = symbol("t2");
695+
Sym2.Type = "T2";
696+
697+
std::vector<Symbol> Symbols{Sym1, Sym2};
698+
Dex I(Symbols, RefSlab());
699+
700+
FuzzyFindRequest Req;
701+
Req.AnyScope = true;
702+
Req.Query = "t";
703+
// The best candidate can change depending on the preferred type.
704+
Req.Limit = 1;
705+
706+
Req.PreferredTypes = {Sym1.Type};
707+
EXPECT_THAT(match(I, Req), ElementsAre("t1"));
708+
709+
Req.PreferredTypes = {Sym2.Type};
710+
EXPECT_THAT(match(I, Req), ElementsAre("t2"));
711+
}
712+
691713
} // namespace
692714
} // namespace dex
693715
} // namespace clangd

0 commit comments

Comments
 (0)
Please sign in to comment.