1 //===--- FileDistance.cpp - File contents container -------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // The FileDistance structure allows calculating the minimum distance to paths
11 // in a single tree.
12 // We simply walk up the path's ancestors until we find a node whose cost is
13 // known, and add the cost of walking back down. Initialization ensures this
14 // gives the correct path to the roots.
15 // We cache the results, so that the runtime is O(|A|), where A is the set of
16 // all distinct ancestors of visited paths.
17 //
18 // Example after initialization with /=2, /bar=0, DownCost = 1:
19 //  / = 2
20 //    /bar = 0
21 //
22 // After querying /foo/bar and /bar/foo:
23 //  / = 2
24 //    /bar = 0
25 //      /bar/foo = 1
26 //    /foo = 3
27 //      /foo/bar = 4
28 //
29 // URIDistance creates FileDistance lazily for each URI scheme encountered. In
30 // practice this is a small constant factor.
31 //
32 //===-------------------------------------------------------------------------//
33 
34 #include "FileDistance.h"
35 #include "Logger.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include <queue>
38 #define DEBUG_TYPE "FileDistance"
39 
40 namespace clang {
41 namespace clangd {
42 using namespace llvm;
43 
44 // Convert a path into the canonical form.
45 // Canonical form is either "/", or "/segment" * N:
46 //   C:\foo\bar --> /c:/foo/bar
47 //   /foo/      --> /foo
48 //   a/b/c      --> /a/b/c
49 static SmallString<128> canonicalize(StringRef Path) {
50   SmallString<128> Result = Path.rtrim('/');
51   native(Result, sys::path::Style::posix);
52   if (Result.empty() || Result.front() != '/')
53     Result.insert(Result.begin(), '/');
54   return Result;
55 }
56 
57 constexpr const unsigned FileDistance::kUnreachable;
58 
59 FileDistance::FileDistance(StringMap<SourceParams> Sources,
60                            const FileDistanceOptions &Opts)
61     : Opts(Opts) {
62   llvm::DenseMap<hash_code, SmallVector<hash_code, 4>> DownEdges;
63   // Compute the best distance following only up edges.
64   // Keep track of down edges, in case we can use them to improve on this.
65   for (const auto &S : Sources) {
66     auto Canonical = canonicalize(S.getKey());
67     LLVM_DEBUG(dbgs() << "Source " << Canonical << " = " << S.second.Cost
68                       << ", MaxUp=" << S.second.MaxUpTraversals << "\n");
69     // Walk up to ancestors of this source, assigning cost.
70     StringRef Rest = Canonical;
71     llvm::hash_code Hash = hash_value(Rest);
72     for (unsigned I = 0; !Rest.empty(); ++I) {
73       Rest = parent_path(Rest, sys::path::Style::posix);
74       auto NextHash = hash_value(Rest);
75       auto &Down = DownEdges[NextHash];
76       if (std::find(Down.begin(), Down.end(), Hash) == Down.end())
77         DownEdges[NextHash].push_back(Hash);
78       // We can't just break after MaxUpTraversals, must still set DownEdges.
79       if (I > S.getValue().MaxUpTraversals) {
80         if (Cache.find(Hash) != Cache.end())
81           break;
82       } else {
83         unsigned Cost = S.getValue().Cost + I * Opts.UpCost;
84         auto R = Cache.try_emplace(Hash, Cost);
85         if (!R.second) {
86           if (Cost < R.first->second) {
87             R.first->second = Cost;
88           } else {
89             // If we're not the best way to get to this path, stop assigning.
90             break;
91           }
92         }
93       }
94       Hash = NextHash;
95     }
96   }
97   // Now propagate scores parent -> child if that's an improvement.
98   // BFS ensures we propagate down chains (must visit parents before children).
99   std::queue<hash_code> Next;
100   for (auto Child : DownEdges.lookup(hash_value(llvm::StringRef(""))))
101     Next.push(Child);
102   while (!Next.empty()) {
103     auto ParentCost = Cache.lookup(Next.front());
104     for (auto Child : DownEdges.lookup(Next.front())) {
105       auto &ChildCost =
106           Cache.try_emplace(Child, kUnreachable).first->getSecond();
107       if (ParentCost + Opts.DownCost < ChildCost)
108         ChildCost = ParentCost + Opts.DownCost;
109       Next.push(Child);
110     }
111     Next.pop();
112   }
113 }
114 
115 unsigned FileDistance::distance(StringRef Path) {
116   auto Canonical = canonicalize(Path);
117   unsigned Cost = kUnreachable;
118   SmallVector<hash_code, 16> Ancestors;
119   // Walk up ancestors until we find a path we know the distance for.
120   for (StringRef Rest = Canonical; !Rest.empty();
121        Rest = parent_path(Rest, sys::path::Style::posix)) {
122     auto Hash = hash_value(Rest);
123     auto It = Cache.find(Hash);
124     if (It != Cache.end()) {
125       Cost = It->second;
126       break;
127     }
128     Ancestors.push_back(Hash);
129   }
130   // Now we know the costs for (known node, queried node].
131   // Fill these in, walking down the directory tree.
132   for (hash_code Hash : reverse(Ancestors)) {
133     if (Cost != kUnreachable)
134       Cost += Opts.DownCost;
135     Cache.try_emplace(Hash, Cost);
136   }
137   LLVM_DEBUG(dbgs() << "distance(" << Path << ") = " << Cost << "\n");
138   return Cost;
139 }
140 
141 unsigned URIDistance::distance(llvm::StringRef URI) {
142   auto R = Cache.try_emplace(llvm::hash_value(URI), FileDistance::kUnreachable);
143   if (!R.second)
144     return R.first->getSecond();
145   if (auto U = clangd::URI::parse(URI)) {
146     LLVM_DEBUG(dbgs() << "distance(" << URI << ") = distance(" << U->body()
147                       << ")\n");
148     R.first->second = forScheme(U->scheme()).distance(U->body());
149   } else {
150     log("URIDistance::distance() of unparseable " + URI + ": " +
151         llvm::toString(U.takeError()));
152   }
153   return R.first->second;
154 }
155 
156 FileDistance &URIDistance::forScheme(llvm::StringRef Scheme) {
157   auto &Delegate = ByScheme[Scheme];
158   if (!Delegate) {
159     llvm::StringMap<SourceParams> SchemeSources;
160     for (const auto &Source : Sources) {
161       if (auto U = clangd::URI::create(Source.getKey(), Scheme))
162         SchemeSources.try_emplace(U->body(), Source.getValue());
163       else
164         consumeError(U.takeError());
165     }
166     LLVM_DEBUG(dbgs() << "FileDistance for scheme " << Scheme << ": "
167                       << SchemeSources.size() << "/" << Sources.size()
168                       << " sources\n");
169     Delegate.reset(new FileDistance(std::move(SchemeSources), Opts));
170   }
171   return *Delegate;
172 }
173 
174 } // namespace clangd
175 } // namespace clang
176