1243791Sdim//===--- FileMatchTrie.h - --------------------------------------*- C++ -*-===// 2243791Sdim// 3243791Sdim// The LLVM Compiler Infrastructure 4243791Sdim// 5243791Sdim// This file is distributed under the University of Illinois Open Source 6243791Sdim// License. See LICENSE.TXT for details. 7243791Sdim// 8243791Sdim//===----------------------------------------------------------------------===// 9243791Sdim// 10243791Sdim// This file implements a match trie to find the matching file in a compilation 11243791Sdim// database based on a given path in the presence of symlinks. 12243791Sdim// 13243791Sdim//===----------------------------------------------------------------------===// 14243791Sdim 15243791Sdim#ifndef LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H 16243791Sdim#define LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H 17243791Sdim 18243791Sdim#include "clang/Basic/LLVM.h" 19243791Sdim#include "llvm/ADT/OwningPtr.h" 20243791Sdim#include "llvm/ADT/StringRef.h" 21243791Sdim#include <string> 22243791Sdim#include <vector> 23243791Sdim 24243791Sdimnamespace clang { 25243791Sdimnamespace tooling { 26243791Sdim 27243791Sdimstruct PathComparator { 28243791Sdim virtual ~PathComparator() {} 29243791Sdim virtual bool equivalent(StringRef FileA, StringRef FileB) const = 0; 30243791Sdim}; 31243791Sdimclass FileMatchTrieNode; 32243791Sdim 33243791Sdim/// \brief A trie to efficiently match against the entries of the compilation 34243791Sdim/// database in order of matching suffix length. 35243791Sdim/// 36243791Sdim/// When a clang tool is supposed to operate on a specific file, we have to 37243791Sdim/// find the corresponding file in the compilation database. Although entries 38243791Sdim/// in the compilation database are keyed by filename, a simple string match 39243791Sdim/// is insufficient because of symlinks. Commonly, a project hierarchy looks 40243791Sdim/// like this: 41243791Sdim/// /<project-root>/src/<path>/<somefile>.cc (used as input for the tool) 42243791Sdim/// /<project-root>/build/<symlink-to-src>/<path>/<somefile>.cc (stored in DB) 43243791Sdim/// 44243791Sdim/// Furthermore, there might be symlinks inside the source folder or inside the 45243791Sdim/// database, so that the same source file is translated with different build 46243791Sdim/// options. 47243791Sdim/// 48243791Sdim/// For a given input file, the \c FileMatchTrie finds its entries in order 49243791Sdim/// of matching suffix length. For each suffix length, there might be one or 50243791Sdim/// more entries in the database. For each of those entries, it calls 51243791Sdim/// \c llvm::sys::fs::equivalent() (injected as \c PathComparator). There might 52243791Sdim/// be zero or more entries with the same matching suffix length that are 53243791Sdim/// equivalent to the input file. Three cases are distinguished: 54243791Sdim/// 0 equivalent files: Continue with the next suffix length. 55243791Sdim/// 1 equivalent file: Best match found, return it. 56243791Sdim/// >1 equivalent files: Match is ambiguous, return error. 57243791Sdimclass FileMatchTrie { 58243791Sdimpublic: 59243791Sdim FileMatchTrie(); 60243791Sdim 61243791Sdim /// \brief Construct a new \c FileMatchTrie with the given \c PathComparator. 62243791Sdim /// 63243791Sdim /// The \c FileMatchTrie takes ownership of 'Comparator'. Used for testing. 64243791Sdim FileMatchTrie(PathComparator* Comparator); 65243791Sdim 66243791Sdim ~FileMatchTrie(); 67243791Sdim 68243791Sdim /// \brief Insert a new absolute path. Relative paths are ignored. 69243791Sdim void insert(StringRef NewPath); 70243791Sdim 71243791Sdim /// \brief Finds the corresponding file in this trie. 72243791Sdim /// 73243791Sdim /// Returns file name stored in this trie that is equivalent to 'FileName' 74243791Sdim /// according to 'Comparator', if it can be uniquely identified. If there 75243791Sdim /// are no matches an empty \c StringRef is returned. If there are ambigious 76243791Sdim /// matches, an empty \c StringRef is returned and a corresponding message 77243791Sdim /// written to 'Error'. 78243791Sdim StringRef findEquivalent(StringRef FileName, 79249423Sdim raw_ostream &Error) const; 80243791Sdimprivate: 81243791Sdim FileMatchTrieNode *Root; 82243791Sdim OwningPtr<PathComparator> Comparator; 83243791Sdim}; 84243791Sdim 85243791Sdim 86243791Sdim} // end namespace tooling 87243791Sdim} // end namespace clang 88243791Sdim 89243791Sdim#endif // LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H 90