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(),
'/');
58 llvm::hash_value(llvm::StringRef(
"/"));
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;
72 llvm::hash_code Hash = llvm::hash_value(Rest);
73 for (
unsigned I = 0; !Rest.empty(); ++I) {
74 Rest = parent_path(Rest, llvm::sys::path::Style::posix);
75 auto NextHash = llvm::hash_value(Rest);
76 auto &Down = DownEdges[NextHash];
77 if (!llvm::is_contained(Down, Hash))
80 if (I > S.getValue().MaxUpTraversals) {
81 if (Cache.contains(Hash))
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;
101 for (
auto Child : DownEdges.lookup(llvm::hash_value(llvm::StringRef(
""))))
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)) {
126 auto Hash = llvm::hash_value(Rest);
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;
163FileDistance &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));
180static 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 =
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);
std::vector< std::string > QueryScopes
static constexpr unsigned Unreachable
FileDistance(llvm::StringMap< SourceParams > Sources, const FileDistanceOptions &Opts={})
unsigned distance(llvm::StringRef Path)
static const llvm::hash_code RootHash
unsigned distance(llvm::StringRef SymbolScope)
ScopeDistance(llvm::ArrayRef< std::string > QueryScopes)
QueryScopes[0] is the preferred scope.
unsigned distance(llvm::StringRef URI)
A URI describes the location of a source file.
static llvm::Expected< URI > create(llvm::StringRef AbsolutePath, llvm::StringRef Scheme)
Creates a URI for a file in the given scheme.
llvm::StringRef body() const
Returns decoded body e.g. "/D41946".
static llvm::Expected< URI > parse(llvm::StringRef Uri)
Parse a URI string "<scheme>:[//<authority>/]<path>".
static FileDistance createScopeFileDistance(llvm::ArrayRef< std::string > QueryScopes)
std::string Path
A typedef to represent a file path.
void log(const char *Fmt, Ts &&... Vals)
static llvm::SmallString< 128 > canonicalize(llvm::StringRef Path)
static std::pair< std::string, int > scopeToPath(llvm::StringRef Scope)
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
bool AllowDownTraversalFromRoot