[clangd] Allow disble down traversals from root.

[ioeric]

Summary

This is useful for symbo scope proximity, where down traversals from
the global scope if not desired.

[sammccall]

Works for me! I think the code can be simplified slightly.

clangd/FileDistance.cpp

138

I think this is more power than it needs to be... and in fact messes up the caching.

if (KnownNode == RootHash && !Opts.AllowDownTraversalFromRoot && !Ancestors.empty())
 Cost = Unreachable;

should be enough.

Or maybe even clearer, after line 126:

if (Hash == RootHash && !Ancestors.empty() && !Opts.AllowDownTraversalFromRoot) {
  Cost = Unreachable;
  break;
}

then you never have to store KnownNode.

[ioeric]

• Simplify according to review suggestion.

clangd/FileDistance.h

 
 namespace clang {
 namespace clangd {
 
 struct FileDistanceOptions {
   unsigned UpCost = 2;      // |foo/bar.h -> foo|
   unsigned DownCost = 1;    // |foo -> foo/bar.h|
   unsigned IncludeCost = 2; // |foo.cc -> included_header.h|
+  bool AllowDownTraversalFromRoot = true; // | / -> /a |
 };
 
 struct SourceParams {
   // Base cost for paths starting at this source.
   unsigned Cost = 0;
   // Limits the number of upwards traversals allowed from this source.
   unsigned MaxUpTraversals = std::numeric_limits<unsigned>::max();
 };
 
 // Supports lookups to find the minimum distance to a file from any source.
 // This object should be reused, it memoizes intermediate computations.
 class FileDistance {
 public:
   static constexpr unsigned Unreachable = std::numeric_limits<unsigned>::max();
+  static const llvm::hash_code RootHash;
 
   FileDistance(llvm::StringMap<SourceParams> Sources,
                const FileDistanceOptions &Opts = {});
 
   // Computes the minimum distance from any source to the file path.
   unsigned distance(llvm::StringRef Path);
 
 private:

clangd/FileDistance.cpp

static SmallString<128> canonicalize(StringRef Path) {
   SmallString<128> Result = Path.rtrim('/');
   native(Result, sys::path::Style::posix);
   if (Result.empty() || Result.front() != '/')
     Result.insert(Result.begin(), '/');
   return Result;
 }
 
 constexpr const unsigned FileDistance::Unreachable;
+const llvm::hash_code FileDistance::RootHash = hash_value(StringRef("/"));
 
 FileDistance::FileDistance(StringMap<SourceParams> Sources,
                            const FileDistanceOptions &Opts)
     : Opts(Opts) {
   llvm::DenseMap<hash_code, SmallVector<hash_code, 4>> DownEdges;
   // Compute the best distance following only up edges.
   // Keep track of down edges, in case we can use them to improve on this.
   for (const auto &S : Sources) {
for (const auto &S : Sources) {
     }
   }
   // Now propagate scores parent -> child if that's an improvement.
   // BFS ensures we propagate down chains (must visit parents before children).
   std::queue<hash_code> Next;
   for (auto Child : DownEdges.lookup(hash_value(llvm::StringRef(""))))
     Next.push(Child);
   while (!Next.empty()) {
-    auto ParentCost = Cache.lookup(Next.front());
-    for (auto Child : DownEdges.lookup(Next.front())) {
+    auto Parent = Next.front();
+    Next.pop();
+    auto ParentCost = Cache.lookup(Parent);
+    for (auto Child : DownEdges.lookup(Parent)) {
+      if (Parent != RootHash || Opts.AllowDownTraversalFromRoot) {
         auto &ChildCost =
             Cache.try_emplace(Child, Unreachable).first->getSecond();
         if (ParentCost + Opts.DownCost < ChildCost)
           ChildCost = ParentCost + Opts.DownCost;
+      }
       Next.push(Child);
     }
-    Next.pop();
   }
 }
 
 unsigned FileDistance::distance(StringRef Path) {
   auto Canonical = canonicalize(Path);
   unsigned Cost = Unreachable;
   SmallVector<hash_code, 16> Ancestors;
   // Walk up ancestors until we find a path we know the distance for.
   for (StringRef Rest = Canonical; !Rest.empty();
        Rest = parent_path(Rest, sys::path::Style::posix)) {
     auto Hash = hash_value(Rest);
+    if (Hash == RootHash && !Ancestors.empty() &&
+        !Opts.AllowDownTraversalFromRoot) {
+      Cost = Unreachable;
+      break;
+    }
     auto It = Cache.find(Hash);
     if (It != Cache.end()) {
       Cost = It->second;
       break;
     }
     Ancestors.push_back(Hash);
   }
   // Now we know the costs for (known node, queried node].
   // Fill these in, walking down the directory tree.
   for (hash_code Hash : reverse(Ancestors)) {
     if (Cost != Unreachable)
       Cost += Opts.DownCost;
     Cache.try_emplace(Hash, Cost);
   }
   dlog("distance({0} = {1})", Path, Cost);
   return Cost;

unittests/clangd/FileDistanceTests.cpp

TEST(FileDistance, LimitUpTraversals) {
 
   FileDistance D({{"/", CostLots}, {"/a/b/c", CheapButLimited}}, Opts);
   EXPECT_EQ(D.distance("/a"), 101u);
   EXPECT_EQ(D.distance("/a/z"), 102u);
   EXPECT_EQ(D.distance("/a/b"), 1u);
   EXPECT_EQ(D.distance("/a/b/z"), 2u);
 }
 
+TEST(FileDistance, DisallowDownTraversalsFromRoot) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = Opts.DownCost = 1;
+  Opts.AllowDownTraversalFromRoot = false;
+  SourceParams CostLots;
+  CostLots.Cost = 100;
+
+  FileDistance D({{"/", SourceParams()}, {"/a/b/c", CostLots}}, Opts);
+  EXPECT_EQ(D.distance("/"), 0u);
+  EXPECT_EQ(D.distance("/a"), 102u);
+  EXPECT_EQ(D.distance("/a/b"), 101u);
+  EXPECT_EQ(D.distance("/x"), FileDistance::Unreachable);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang