| 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 |