Daniel Jasper | d3420c9 | 2012-10-08 16:08:15 +0000 | [diff] [blame] | 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 | |
Daniel Jasper | d3420c9 | 2012-10-08 16:08:15 +0000 | [diff] [blame] | 14 | #include "clang/Tooling/FileMatchTrie.h" |
| 15 | #include "llvm/ADT/StringMap.h" |
| 16 | #include "llvm/Support/FileSystem.h" |
| 17 | #include "llvm/Support/PathV2.h" |
Daniel Jasper | 61a50ad | 2012-10-08 18:37:21 +0000 | [diff] [blame] | 18 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | 55fc873 | 2012-12-04 09:13:33 +0000 | [diff] [blame] | 19 | #include <sstream> |
Daniel Jasper | d3420c9 | 2012-10-08 16:08:15 +0000 | [diff] [blame] | 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() {} |
Daniel Jasper | 2dbe2fa | 2012-10-08 18:31:54 +0000 | [diff] [blame] | 27 | virtual bool equivalent(StringRef FileA, StringRef FileB) const { |
| 28 | return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB); |
Daniel Jasper | d3420c9 | 2012-10-08 16:08:15 +0000 | [diff] [blame] | 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 | llvm::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 |