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/StringRef.h"
20#include <memory>
21#include <string>
22#include <vector>
23
24namespace clang {
25namespace tooling {
26
27struct PathComparator {
28  virtual ~PathComparator() {}
29  virtual bool equivalent(StringRef FileA, StringRef FileB) const = 0;
30};
31class 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.
57class FileMatchTrie {
58public:
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;
80private:
81  FileMatchTrieNode *Root;
82  std::unique_ptr<PathComparator> Comparator;
83};
84
85
86} // end namespace tooling
87} // end namespace clang
88
89#endif // LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
90