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 /// \brief 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 /// \brief 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   /// \brief 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   /// \brief 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 fron) 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   /// \brief 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 }
197