LCOV - code coverage report
Current view: top level - clang/tools/extra/clangd - FileDistance.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 5 0.0 %
Date: 2018-10-20 13:21:21 Functions: 0 1 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- FileDistance.h - File proximity scoring -----------------*- 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             : // This library measures the distance between file paths.
      11             : // It's used for ranking symbols, e.g. in code completion.
      12             : //  |foo/bar.h -> foo/bar.h| = 0.
      13             : //  |foo/bar.h -> foo/baz.h| < |foo/bar.h -> baz.h|.
      14             : // This is an edit-distance, where edits go up or down the directory tree.
      15             : // It's not symmetrical, the costs of going up and down may not match.
      16             : //
      17             : // Dealing with multiple sources:
      18             : // In practice we care about the distance from a source file, but files near
      19             : // its main-header and #included files are considered "close".
      20             : // So we start with a set of (anchor, cost) pairs, and call the distance to a
      21             : // path the minimum of `cost + |source -> path|`.
      22             : //
      23             : // We allow each source to limit the number of up-traversals paths may start
      24             : // with. Up-traversals may reach things that are not "semantically near".
      25             : //
      26             : // Symbol URI schemes:
      27             : // Symbol locations may be represented by URIs rather than file paths directly.
      28             : // In this case we want to perform distance computations in URI space rather
      29             : // than in file-space, without performing redundant conversions.
      30             : // Therefore we have a lookup structure that accepts URIs, so that intermediate
      31             : // calculations for the same scheme can be reused.
      32             : //
      33             : // Caveats:
      34             : // Assuming up and down traversals each have uniform costs is simplistic.
      35             : // Often there are "semantic roots" whose children are almost unrelated.
      36             : // (e.g. /usr/include/, or / in an umbrella repository). We ignore this.
      37             : //
      38             : //===----------------------------------------------------------------------===//
      39             : 
      40             : #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FILEDISTANCE_H
      41             : #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FILEDISTANCE_H
      42             : 
      43             : #include "URI.h"
      44             : #include "llvm/ADT/DenseMap.h"
      45             : #include "llvm/ADT/DenseMapInfo.h"
      46             : #include "llvm/ADT/SmallString.h"
      47             : #include "llvm/ADT/StringRef.h"
      48             : #include "llvm/Support/Allocator.h"
      49             : #include "llvm/Support/Path.h"
      50             : #include "llvm/Support/StringSaver.h"
      51             : #include <memory>
      52             : 
      53             : namespace clang {
      54             : namespace clangd {
      55             : 
      56           0 : struct FileDistanceOptions {
      57             :   unsigned UpCost = 2;      // |foo/bar.h -> foo|
      58             :   unsigned DownCost = 1;    // |foo -> foo/bar.h|
      59             :   unsigned IncludeCost = 2; // |foo.cc -> included_header.h|
      60             :   bool AllowDownTraversalFromRoot = true; // | / -> /a |
      61             : };
      62             : 
      63           0 : struct SourceParams {
      64             :   // Base cost for paths starting at this source.
      65             :   unsigned Cost = 0;
      66             :   // Limits the number of upwards traversals allowed from this source.
      67             :   unsigned MaxUpTraversals = std::numeric_limits<unsigned>::max();
      68             : };
      69             : 
      70             : // Supports lookups to find the minimum distance to a file from any source.
      71             : // This object should be reused, it memoizes intermediate computations.
      72           0 : class FileDistance {
      73             : public:
      74             :   static constexpr unsigned Unreachable = std::numeric_limits<unsigned>::max();
      75             :   static const llvm::hash_code RootHash;
      76             : 
      77             :   FileDistance(llvm::StringMap<SourceParams> Sources,
      78             :                const FileDistanceOptions &Opts = {});
      79             : 
      80             :   // Computes the minimum distance from any source to the file path.
      81             :   unsigned distance(llvm::StringRef Path);
      82             : 
      83             : private:
      84             :   // Costs computed so far. Always contains sources and their ancestors.
      85             :   // We store hash codes only. Collisions are rare and consequences aren't dire.
      86             :   llvm::DenseMap<llvm::hash_code, unsigned> Cache;
      87             :   FileDistanceOptions Opts;
      88             : };
      89             : 
      90             : // Supports lookups like FileDistance, but the lookup keys are URIs.
      91             : // We convert each of the sources to the scheme of the URI and do a FileDistance
      92             : // comparison on the bodies.
      93             : class URIDistance {
      94             : public:
      95             :   // \p Sources must contain absolute paths, not URIs.
      96           0 :   URIDistance(llvm::StringMap<SourceParams> Sources,
      97             :               const FileDistanceOptions &Opts = {})
      98           0 :       : Sources(Sources), Opts(Opts) {}
      99             : 
     100             :   // Computes the minimum distance from any source to the URI.
     101             :   // Only sources that can be mapped into the URI's scheme are considered.
     102             :   unsigned distance(llvm::StringRef URI);
     103             : 
     104             : private:
     105             :   // Returns the FileDistance for a URI scheme, creating it if needed.
     106             :   FileDistance &forScheme(llvm::StringRef Scheme);
     107             : 
     108             :   // We cache the results using the original strings so we can skip URI parsing.
     109             :   llvm::DenseMap<llvm::hash_code, unsigned> Cache;
     110             :   llvm::StringMap<SourceParams> Sources;
     111             :   llvm::StringMap<std::unique_ptr<FileDistance>> ByScheme;
     112             :   FileDistanceOptions Opts;
     113             : };
     114             : 
     115             : /// Support lookups like FileDistance, but the lookup keys are symbol scopes.
     116             : /// For example, a scope "na::nb::" is converted to "/na/nb".
     117             : class ScopeDistance {
     118             : public:
     119             :   /// QueryScopes[0] is the preferred scope.
     120             :   ScopeDistance(llvm::ArrayRef<std::string> QueryScopes);
     121             : 
     122             :   unsigned distance(llvm::StringRef SymbolScope);
     123             : 
     124             : private:
     125             :   FileDistance Distance;
     126             : };
     127             : 
     128             : } // namespace clangd
     129             : } // namespace clang
     130             : 
     131             : #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_FILEDISTANCE_H

Generated by: LCOV version 1.13