llvm/clang-tools-extra/clangd/FileDistance.cpp

//===--- FileDistance.cpp - File contents container -------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The FileDistance structure allows calculating the minimum distance to paths
// in a single tree.
// We simply walk up the path's ancestors until we find a node whose cost is
// known, and add the cost of walking back down. Initialization ensures this
// gives the correct path to the roots.
// We cache the results, so that the runtime is O(|A|), where A is the set of
// all distinct ancestors of visited paths.
//
// Example after initialization with /=2, /bar=0, DownCost = 1:
//  / = 2
//    /bar = 0
//
// After querying /foo/bar and /bar/foo:
//  / = 2
//    /bar = 0
//      /bar/foo = 1
//    /foo = 3
//      /foo/bar = 4
//
// URIDistance creates FileDistance lazily for each URI scheme encountered. In
// practice this is a small constant factor.
//
//===-------------------------------------------------------------------------//

#include "FileDistance.h"
#include "URI.h"
#include "support/Logger.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Path.h"
#include <queue>

namespace clang {
namespace clangd {

// Convert a path into the canonical form.
// Canonical form is either "/", or "/segment" * N:
//   C:\foo\bar --> /c:/foo/bar
//   /foo/      --> /foo
//   a/b/c      --> /a/b/c
static llvm::SmallString<128> canonicalize(llvm::StringRef Path) { … }

constexpr const unsigned FileDistance::Unreachable;
const llvm::hash_code FileDistance::RootHash = …;

FileDistance::FileDistance(llvm::StringMap<SourceParams> Sources,
                           const FileDistanceOptions &Opts)
    : … { … }

unsigned FileDistance::distance(llvm::StringRef Path) { … }

unsigned URIDistance::distance(llvm::StringRef URI) { … }

FileDistance &URIDistance::forScheme(llvm::StringRef Scheme) { … }

static std::pair<std::string, int> scopeToPath(llvm::StringRef Scope) { … }

static FileDistance
createScopeFileDistance(llvm::ArrayRef<std::string> QueryScopes) { … }

ScopeDistance::ScopeDistance(llvm::ArrayRef<std::string> QueryScopes)
    : … { … }

unsigned ScopeDistance::distance(llvm::StringRef SymbolScope) { … }

} // namespace clangd
} // namespace clang