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
21namespace clang {
22namespace tooling {
23
24class FileMatchTrieNode;
25
26struct 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.
56class FileMatchTrie {
57public:
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
80private:
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

source code of clang/include/clang/Tooling/FileMatchTrie.h