FileMatchTrie.cpp revision 61a50adfd9a095cfa017751d41af409c5bc26edf 
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#include "llvm/Support/raw_ostream.h"
20
21namespace clang {
22namespace tooling {
23
24/// \brief Default \c PathComparator using \c llvm::sys::fs::equivalent().
25struct DefaultPathComparator : public PathComparator {
26  virtual ~DefaultPathComparator() {}
27  virtual bool equivalent(StringRef FileA, StringRef FileB) const {
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.
36class FileMatchTrieNode {
37public:
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
133private:
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
160FileMatchTrie::FileMatchTrie()
161  : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {}
162
163FileMatchTrie::FileMatchTrie(PathComparator *Comparator)
164  : Root(new FileMatchTrieNode), Comparator(Comparator) {}
165
166FileMatchTrie::~FileMatchTrie() {
167  delete Root;
168}
169
170void FileMatchTrie::insert(StringRef NewPath) {
171  Root->insert(NewPath);
172}
173
174StringRef 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
189