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