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