contrib/llvm/tools/clang/include/clang/Tooling/FileMatchTrie.h

   1 //===--- FileMatchTrie.h - --------------------------------------*- C++ -*-===//
   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 implements a match trie to find the matching file in a compilation
  11 //  database based on a given path in the presence of symlinks.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
  16 #define LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
  17
  18 #include "clang/Basic/LLVM.h"
  19 #include "llvm/ADT/OwningPtr.h"
  20 #include "llvm/ADT/StringRef.h"
  21
  22 #include <string>
  23 #include <vector>
  24
  25 namespace clang {
  26 namespace tooling {
  27
  28 struct PathComparator {
  29   virtual ~PathComparator() {}
  30   virtual bool equivalent(StringRef FileA, StringRef FileB) const = 0;
  31 };
  32 class FileMatchTrieNode;
  33
  34 /// \brief A trie to efficiently match against the entries of the compilation
  35 /// database in order of matching suffix length.
  36 ///
  37 /// When a clang tool is supposed to operate on a specific file, we have to
  38 /// find the corresponding file in the compilation database. Although entries
  39 /// in the compilation database are keyed by filename, a simple string match
  40 /// is insufficient because of symlinks. Commonly, a project hierarchy looks
  41 /// like this:
  42 ///   /<project-root>/src/<path>/<somefile>.cc      (used as input for the tool)
  43 ///   /<project-root>/build/<symlink-to-src>/<path>/<somefile>.cc (stored in DB)
  44 ///
  45 /// Furthermore, there might be symlinks inside the source folder or inside the
  46 /// database, so that the same source file is translated with different build
  47 /// options.
  48 ///
  49 /// For a given input file, the \c FileMatchTrie finds its entries in order
  50 /// of matching suffix length. For each suffix length, there might be one or
  51 /// more entries in the database. For each of those entries, it calls
  52 /// \c llvm::sys::fs::equivalent() (injected as \c PathComparator). There might
  53 /// be zero or more entries with the same matching suffix length that are
  54 /// equivalent to the input file. Three cases are distinguished:
  55 /// 0  equivalent files: Continue with the next suffix length.
  56 /// 1  equivalent file:  Best match found, return it.
  57 /// >1 equivalent files: Match is ambiguous, return error.
  58 class FileMatchTrie {
  59 public:
  60   FileMatchTrie();
  61
  62   /// \brief Construct a new \c FileMatchTrie with the given \c PathComparator.
  63   ///
  64   /// The \c FileMatchTrie takes ownership of 'Comparator'. Used for testing.
  65   FileMatchTrie(PathComparator* Comparator);
  66
  67   ~FileMatchTrie();
  68
  69   /// \brief Insert a new absolute path. Relative paths are ignored.
  70   void insert(StringRef NewPath);
  71
  72   /// \brief Finds the corresponding file in this trie.
  73   ///
  74   /// Returns file name stored in this trie that is equivalent to 'FileName'
  75   /// according to 'Comparator', if it can be uniquely identified. If there
  76   /// are no matches an empty \c StringRef is returned. If there are ambigious
  77   /// matches, an empty \c StringRef is returned and a corresponding message
  78   /// written to 'Error'.
  79   StringRef findEquivalent(StringRef FileName,
  80                            llvm::raw_ostream &Error) const;
  81 private:
  82   FileMatchTrieNode *Root;
  83   OwningPtr<PathComparator> Comparator;
  84 };
  85
  86
  87 } // end namespace tooling
  88 } // end namespace clang
  89
  90 #endif // LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H