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