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