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_FILEMATCHTRIE_H
16 #define LLVM_CLANG_TOOLING_FILEMATCHTRIE_H
17 
18 #include "clang/Basic/LLVM.h"
19 #include "llvm/ADT/StringRef.h"
20 #include <memory>
21 #include <string>
22 #include <vector>
23 
24 namespace clang {
25 namespace tooling {
26 
27 struct PathComparator {
~PathComparatorPathComparator28   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   std::unique_ptr<PathComparator> Comparator;
83 };
84 
85 
86 } // end namespace tooling
87 } // end namespace clang
88 
89 #endif
90