36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/Support/Path.h"
49 llvm::SmallString<128> Result =
Path.rtrim(
'/');
50 native(Result, llvm::sys::path::Style::posix);
51 if (Result.empty() || Result.front() !=
'/')
52 Result.insert(Result.begin(),
'/');
63 llvm::DenseMap<llvm::hash_code, llvm::SmallVector<llvm::hash_code>> DownEdges;
66 for (
const auto &S : Sources) {
68 dlog(
"Source {0} = {1}, MaxUp = {2}", Canonical, S.second.Cost,
69 S.second.MaxUpTraversals);
71 llvm::StringRef Rest = Canonical;
73 for (
unsigned I = 0; !Rest.empty(); ++I) {
74 Rest = parent_path(Rest, llvm::sys::path::Style::posix);
76 auto &Down = DownEdges[NextHash];
77 if (!llvm::is_contained(Down, Hash))
80 if (I > S.getValue().MaxUpTraversals) {
81 if (Cache.find(Hash) != Cache.end())
84 unsigned Cost = S.getValue().Cost + I * Opts.UpCost;
85 auto R = Cache.try_emplace(Hash, Cost);
87 if (Cost < R.first->second) {
88 R.first->second = Cost;
100 std::queue<llvm::hash_code> Next;
103 while (!Next.empty()) {
104 auto Parent = Next.front();
106 auto ParentCost = Cache.lookup(
Parent);
107 for (
auto Child : DownEdges.lookup(
Parent)) {
110 Cache.try_emplace(Child,
Unreachable).first->getSecond();
111 if (ParentCost + Opts.DownCost < ChildCost)
112 ChildCost = ParentCost + Opts.DownCost;
122 llvm::SmallVector<llvm::hash_code> Ancestors;
124 for (llvm::StringRef Rest = Canonical; !Rest.empty();
125 Rest = parent_path(Rest, llvm::sys::path::Style::posix)) {
127 if (Hash ==
RootHash && !Ancestors.empty() &&
132 auto It = Cache.find(Hash);
133 if (It != Cache.end()) {
137 Ancestors.push_back(Hash);
141 for (llvm::hash_code Hash : llvm::reverse(Ancestors)) {
144 Cache.try_emplace(Hash, Cost);
146 dlog(
"distance({0} = {1})",
Path, Cost);
153 return R.first->getSecond();
156 R.first->second = forScheme(U->scheme()).
distance(U->body());
158 log(
"URIDistance::distance() of unparseable {0}: {1}",
URI, U.takeError());
160 return R.first->second;
163 FileDistance &URIDistance::forScheme(llvm::StringRef Scheme) {
164 auto &Delegate = ByScheme[Scheme];
166 llvm::StringMap<SourceParams> SchemeSources;
167 for (
const auto &Source : Sources) {
169 SchemeSources.try_emplace(U->body(), Source.getValue());
171 llvm::consumeError(U.takeError());
173 dlog(
"FileDistance for scheme {0}: {1}/{2} sources", Scheme,
174 SchemeSources.size(), Sources.size());
175 Delegate.reset(
new FileDistance(std::move(SchemeSources), Opts));
180 static std::pair<std::string, int>
scopeToPath(llvm::StringRef Scope) {
181 llvm::SmallVector<llvm::StringRef> Split;
182 Scope.split(Split,
"::", -1,
false);
183 return {
"/" +
llvm::join(Split,
"/"), Split.size()};
191 Opts.AllowDownTraversalFromRoot =
false;
193 llvm::StringMap<SourceParams> Sources;
194 llvm::StringRef Preferred =
195 QueryScopes.empty() ?
"" : QueryScopes.front().c_str();
196 for (llvm::StringRef S : QueryScopes) {
202 Param.
Cost = S ==
"" ? 4 : 0;
203 else if (Preferred.startswith(S) && !S.empty())
206 Param.
Cost = S ==
"" ? 6 : 2;
210 Sources[
Path.first] = std::move(Param);