clang/Tooling/FileMatchTrie.h

0001 //===- FileMatchTrie.h ------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file implements a match trie to find the matching file in a compilation
0010 //  database based on a given path in the presence of symlinks.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_TOOLING_FILEMATCHTRIE_H
0015 #define LLVM_CLANG_TOOLING_FILEMATCHTRIE_H
0016
0017 #include "clang/Basic/LLVM.h"
0018 #include "llvm/ADT/StringRef.h"
0019 #include <memory>
0020
0021 namespace clang {
0022 namespace tooling {
0023
0024 class FileMatchTrieNode;
0025
0026 struct PathComparator {
0027   virtual ~PathComparator() = default;
0028
0029   virtual bool equivalent(StringRef FileA, StringRef FileB) const = 0;
0030 };
0031
0032 /// A trie to efficiently match against the entries of the compilation
0033 /// database in order of matching suffix length.
0034 ///
0035 /// When a clang tool is supposed to operate on a specific file, we have to
0036 /// find the corresponding file in the compilation database. Although entries
0037 /// in the compilation database are keyed by filename, a simple string match
0038 /// is insufficient because of symlinks. Commonly, a project hierarchy looks
0039 /// like this:
0040 ///   /<project-root>/src/<path>/<somefile>.cc      (used as input for the tool)
0041 ///   /<project-root>/build/<symlink-to-src>/<path>/<somefile>.cc (stored in DB)
0042 ///
0043 /// Furthermore, there might be symlinks inside the source folder or inside the
0044 /// database, so that the same source file is translated with different build
0045 /// options.
0046 ///
0047 /// For a given input file, the \c FileMatchTrie finds its entries in order
0048 /// of matching suffix length. For each suffix length, there might be one or
0049 /// more entries in the database. For each of those entries, it calls
0050 /// \c llvm::sys::fs::equivalent() (injected as \c PathComparator). There might
0051 /// be zero or more entries with the same matching suffix length that are
0052 /// equivalent to the input file. Three cases are distinguished:
0053 /// 0  equivalent files: Continue with the next suffix length.
0054 /// 1  equivalent file:  Best match found, return it.
0055 /// >1 equivalent files: Match is ambiguous, return error.
0056 class FileMatchTrie {
0057 public:
0058   FileMatchTrie();
0059
0060   /// Construct a new \c FileMatchTrie with the given \c PathComparator.
0061   ///
0062   /// The \c FileMatchTrie takes ownership of 'Comparator'. Used for testing.
0063   FileMatchTrie(PathComparator* Comparator);
0064
0065   ~FileMatchTrie();
0066
0067   /// Insert a new absolute path. Relative paths are ignored.
0068   void insert(StringRef NewPath);
0069
0070   /// Finds the corresponding file in this trie.
0071   ///
0072   /// Returns file name stored in this trie that is equivalent to 'FileName'
0073   /// according to 'Comparator', if it can be uniquely identified. If there
0074   /// are no matches an empty \c StringRef is returned. If there are ambiguous
0075   /// matches, an empty \c StringRef is returned and a corresponding message
0076   /// written to 'Error'.
0077   StringRef findEquivalent(StringRef FileName,
0078                            raw_ostream &Error) const;
0079
0080 private:
0081   FileMatchTrieNode *Root;
0082   std::unique_ptr<PathComparator> Comparator;
0083 };
0084
0085 } // namespace tooling
0086 } // namespace clang
0087
0088 #endif // LLVM_CLANG_TOOLING_FILEMATCHTRIE_H