contrib/llvm-project/clang/lib/Tooling/FileMatchTrie.cpp

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