Support symlinks and relative paths in complilation databases.

Review: http://llvm-reviews.chandlerc.com/D30

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@165392 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 95 insertions, 0 deletions

diff --git a/include/clang/Tooling/CompilationDatabase.h b/include/clang/Tooling/CompilationDatabase.h
index b054b85e40..a40bffec78 100644
--- a/include/clang/Tooling/CompilationDatabase.h
+++ b/include/clang/Tooling/CompilationDatabase.h
@@ -33,6 +33,7 @@
 #include "llvm/ADT/OwningPtr.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
+
 #include <string>
 #include <vector>
 
diff --git a/include/clang/Tooling/FileMatchTrie.h b/include/clang/Tooling/FileMatchTrie.h
new file mode 100644
index 0000000000..14c823ba5e
--- /dev/null
+++ b/include/clang/Tooling/FileMatchTrie.h
@@ -0,0 +1,91 @@
+//===--- FileMatchTrie.h - --------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file implements a match trie to find the matching file in a compilation
+//  database based on a given path in the presence of symlinks.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
+#define LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
+
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace tooling {
+
+struct PathComparator {
+  virtual ~PathComparator() {}
+  virtual bool equivalent(const Twine &FileA, const Twine &FileB) const = 0;
+};
+class FileMatchTrieNode;
+
+/// \brief A trie to efficiently match against the entries of the compilation
+/// database in order of matching suffix length.
+///
+/// When a clang tool is supposed to operate on a specific file, we have to
+/// find the corresponding file in the compilation database. Although entries
+/// in the compilation database are keyed by filename, a simple string match
+/// is insufficient because of symlinks. Commonly, a project hierarchy looks
+/// like this:
+///   /<project-root>/src/<path>/<somefile>.cc      (used as input for the tool)
+///   /<project-root>/build/<symlink-to-src>/<path>/<somefile>.cc (stored in DB)
+///
+/// Furthermore, there might be symlinks inside the source folder or inside the
+/// database, so that the same source file is translated with different build
+/// options.
+///
+/// For a given input file, the \c FileMatchTrie finds its entries in order
+/// of matching suffix length. For each suffix length, there might be one or
+/// more entries in the database. For each of those entries, it calls
+/// \c llvm::sys::fs::equivalent() (injected as \c PathComparator). There might
+/// be zero or more entries with the same matching suffix length that are
+/// equivalent to the input file. Three cases are distinguished:
+/// 0  equivalent files: Continue with the next suffix length.
+/// 1  equivalent file:  Best match found, return it.
+/// >1 equivalent files: Match is ambiguous, return error.
+class FileMatchTrie {
+public:
+  FileMatchTrie();
+
+  /// \brief Construct a new \c FileMatchTrie with the given \c PathComparator.
+  ///
+  /// The \c FileMatchTrie takes ownership of 'Comparator'. Used for testing.
+  FileMatchTrie(PathComparator* Comparator);
+
+  ~FileMatchTrie();
+
+  /// \brief Insert a new absolute path. Relative paths are ignored.
+  void insert(StringRef NewPath);
+
+  /// \brief Finds the corresponding file in this trie.
+  ///
+  /// Returns file name stored in this trie that is equivalent to 'FileName'
+  /// according to 'Comparator', if it can be uniquely identified. If there
+  /// are no matches an empty \c StringRef is returned. If there are ambigious
+  /// matches, an empty \c StringRef is returned and a corresponding message
+  /// written to 'Error'.
+  StringRef findEquivalent(StringRef FileName,
+                           llvm::raw_ostream &Error) const;
+private:
+  FileMatchTrieNode *Root;
+  OwningPtr<PathComparator> Comparator;
+};
+
+
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_FILE_MATCH_TRIE_H
diff --git a/include/clang/Tooling/JSONCompilationDatabase.h b/include/clang/Tooling/JSONCompilationDatabase.h
index 2ff2ba5a11..d62ab5c503 100644
--- a/include/clang/Tooling/JSONCompilationDatabase.h
+++ b/include/clang/Tooling/JSONCompilationDatabase.h
@@ -17,6 +17,7 @@
 
 #include "clang/Basic/LLVM.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "clang/Tooling/FileMatchTrie.h"
 #include "llvm/ADT/OwningPtr.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
@@ -93,6 +94,8 @@ private:
   // Maps file paths to the compile command lines for that file.
   llvm::StringMap< std::vector<CompileCommandRef> > IndexByFile;
 
+  FileMatchTrie MatchTrie;
+
   llvm::OwningPtr<llvm::MemoryBuffer> Database;
   llvm::SourceMgr SM;
   llvm::yaml::Stream YAMLStream;