contrib/llvm/tools/clang/lib/Tooling/FileMatchTrie.cpp

   1 //===- FileMatchTrie.cpp --------------------------------------------------===//
   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 file contains the implementation of a FileMatchTrie.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Tooling/FileMatchTrie.h"
  15 #include "llvm/ADT/StringMap.h"
  16 #include "llvm/ADT/StringRef.h"
  17 #include "llvm/Support/FileSystem.h"
  18 #include "llvm/Support/Path.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <string>
  21 #include <vector>
  22
  23 using namespace clang;
  24 using namespace tooling;
  25
  26 namespace {
  27
  28 /// Default \c PathComparator using \c llvm::sys::fs::equivalent().
  29 struct DefaultPathComparator : public PathComparator {
  30   bool equivalent(StringRef FileA, StringRef FileB) const override {
  31     return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB);
  32   }
  33 };
  34
  35 } // namespace
  36
  37 namespace clang {
  38 namespace tooling {
  39
  40 /// A node of the \c FileMatchTrie.
  41 ///
  42 /// Each node has storage for up to one path and a map mapping a path segment to
  43 /// child nodes. The trie starts with an empty root node.
  44 class FileMatchTrieNode {
  45 public:
  46   /// Inserts 'NewPath' into this trie. \c ConsumedLength denotes
  47   /// the number of \c NewPath's trailing characters already consumed during
  48   /// recursion.
  49   ///
  50   /// An insert of a path
  51   /// 'p'starts at the root node and does the following:
  52   /// - If the node is empty, insert 'p' into its storage and abort.
  53   /// - If the node has a path 'p2' but no children, take the last path segment
  54   ///   's' of 'p2', put a new child into the map at 's' an insert the rest of
  55   ///   'p2' there.
  56   /// - Insert a new child for the last segment of 'p' and insert the rest of
  57   ///   'p' there.
  58   ///
  59   /// An insert operation is linear in the number of a path's segments.
  60   void insert(StringRef NewPath, unsigned ConsumedLength = 0) {
  61     // We cannot put relative paths into the FileMatchTrie as then a path can be
  62     // a postfix of another path, violating a core assumption of the trie.
  63     if (llvm::sys::path::is_relative(NewPath))
  64       return;
  65     if (Path.empty()) {
  66       // This is an empty leaf. Store NewPath and return.
  67       Path = NewPath;
  68       return;
  69     }
  70     if (Children.empty()) {
  71       // This is a leaf, ignore duplicate entry if 'Path' equals 'NewPath'.
  72       if (NewPath == Path)
  73           return;
  74       // Make this a node and create a child-leaf with 'Path'.
  75       StringRef Element(llvm::sys::path::filename(
  76           StringRef(Path).drop_back(ConsumedLength)));
  77       Children[Element].Path = Path;
  78     }
  79     StringRef Element(llvm::sys::path::filename(
  80           StringRef(NewPath).drop_back(ConsumedLength)));
  81     Children[Element].insert(NewPath, ConsumedLength + Element.size() + 1);
  82   }
  83
  84   /// Tries to find the node under this \c FileMatchTrieNode that best
  85   /// matches 'FileName'.
  86   ///
  87   /// If multiple paths fit 'FileName' equally well, \c IsAmbiguous is set to
  88   /// \c true and an empty string is returned. If no path fits 'FileName', an
  89   /// empty string is returned. \c ConsumedLength denotes the number of
  90   /// \c Filename's trailing characters already consumed during recursion.
  91   ///
  92   /// To find the best matching node for a given path 'p', the
  93   /// \c findEquivalent() function is called recursively for each path segment
  94   /// (back to front) of 'p' until a node 'n' is reached that does not ..
  95   /// - .. have children. In this case it is checked
  96   ///   whether the stored path is equivalent to 'p'. If yes, the best match is
  97   ///   found. Otherwise continue with the parent node as if this node did not
  98   ///   exist.
  99   /// - .. a child matching the next path segment. In this case, all children of
 100   ///   'n' are an equally good match for 'p'. All children are of 'n' are found
 101   ///   recursively and their equivalence to 'p' is determined. If none are
 102   ///   equivalent, continue with the parent node as if 'n' didn't exist. If one
 103   ///   is equivalent, the best match is found. Otherwise, report and ambigiuity
 104   ///   error.
 105   StringRef findEquivalent(const PathComparator& Comparator,
 106                            StringRef FileName,
 107                            bool &IsAmbiguous,
 108                            unsigned ConsumedLength = 0) const {
 109     if (Children.empty()) {
 110       if (Comparator.equivalent(StringRef(Path), FileName))
 111         return StringRef(Path);
 112       return {};
 113     }
 114     StringRef Element(llvm::sys::path::filename(FileName.drop_back(
 115         ConsumedLength)));
 116     llvm::StringMap<FileMatchTrieNode>::const_iterator MatchingChild =
 117         Children.find(Element);
 118     if (MatchingChild != Children.end()) {
 119       StringRef Result = MatchingChild->getValue().findEquivalent(
 120           Comparator, FileName, IsAmbiguous,
 121           ConsumedLength + Element.size() + 1);
 122       if (!Result.empty() || IsAmbiguous)
 123         return Result;
 124     }
 125     std::vector<StringRef> AllChildren;
 126     getAll(AllChildren, MatchingChild);
 127     StringRef Result;
 128     for (const auto &Child : AllChildren) {
 129       if (Comparator.equivalent(Child, FileName)) {
 130         if (Result.empty()) {
 131           Result = Child;
 132         } else {
 133           IsAmbiguous = true;
 134           return {};
 135         }
 136       }
 137     }
 138     return Result;
 139   }
 140
 141 private:
 142   /// Gets all paths under this FileMatchTrieNode.
 143   void getAll(std::vector<StringRef> &Results,
 144               llvm::StringMap<FileMatchTrieNode>::const_iterator Except) const {
 145     if (Path.empty())
 146       return;
 147     if (Children.empty()) {
 148       Results.push_back(StringRef(Path));
 149       return;
 150     }
 151     for (llvm::StringMap<FileMatchTrieNode>::const_iterator
 152          It = Children.begin(), E = Children.end();
 153          It != E; ++It) {
 154       if (It == Except)
 155         continue;
 156       It->getValue().getAll(Results, Children.end());
 157     }
 158   }
 159
 160   // The stored absolute path in this node. Only valid for leaf nodes, i.e.
 161   // nodes where Children.empty().
 162   std::string Path;
 163
 164   // The children of this node stored in a map based on the next path segment.
 165   llvm::StringMap<FileMatchTrieNode> Children;
 166 };
 167
 168 } // namespace tooling
 169 } // namespace clang
 170
 171 FileMatchTrie::FileMatchTrie()
 172     : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {}
 173
 174 FileMatchTrie::FileMatchTrie(PathComparator *Comparator)
 175     : Root(new FileMatchTrieNode), Comparator(Comparator) {}
 176
 177 FileMatchTrie::~FileMatchTrie() {
 178   delete Root;
 179 }
 180
 181 void FileMatchTrie::insert(StringRef NewPath) {
 182   Root->insert(NewPath);
 183 }
 184
 185 StringRef FileMatchTrie::findEquivalent(StringRef FileName,
 186                                         raw_ostream &Error) const {
 187   if (llvm::sys::path::is_relative(FileName)) {
 188     Error << "Cannot resolve relative paths";
 189     return {};
 190   }
 191   bool IsAmbiguous = false;
 192   StringRef Result = Root->findEquivalent(*Comparator, FileName, IsAmbiguous);
 193   if (IsAmbiguous)
 194     Error << "Path is ambiguous";
 195   return Result;
 196 }