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 {
~DefaultPathComparatorclang::tooling::DefaultPathComparator26 virtual ~DefaultPathComparator() {}
equivalentclang::tooling::DefaultPathComparator27 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.
insert(StringRef NewPath,unsigned ConsumedLength=0)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.
findEquivalent(const PathComparator & Comparator,StringRef FileName,bool & IsAmbiguous,unsigned ConsumedLength=0) const97 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.
getAll(std::vector<StringRef> & Results,llvm::StringMap<FileMatchTrieNode>::const_iterator Except) const135 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
FileMatchTrie()160 FileMatchTrie::FileMatchTrie()
161 : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {}
162
FileMatchTrie(PathComparator * Comparator)163 FileMatchTrie::FileMatchTrie(PathComparator *Comparator)
164 : Root(new FileMatchTrieNode), Comparator(Comparator) {}
165
~FileMatchTrie()166 FileMatchTrie::~FileMatchTrie() {
167 delete Root;
168 }
169
insert(StringRef NewPath)170 void FileMatchTrie::insert(StringRef NewPath) {
171 Root->insert(NewPath);
172 }
173
findEquivalent(StringRef FileName,raw_ostream & Error) const174 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