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