8 files changed, 590 insertions, 349 deletions

diff --git a/lib/Tooling/CMakeLists.txt b/lib/Tooling/CMakeLists.txt
index 49d3101f0e99..d29e564e34fe 100644
--- a/lib/Tooling/CMakeLists.txt
+++ b/lib/Tooling/CMakeLists.txt
@@ -2,8 +2,10 @@ set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTooling
   ArgumentsAdjusters.cpp
-  CommandLineClangTool.cpp
+  CommonOptionsParser.cpp
   CompilationDatabase.cpp
+  FileMatchTrie.cpp
+  JSONCompilationDatabase.cpp
   Refactoring.cpp
   RefactoringCallbacks.cpp
   Tooling.cpp
@@ -23,5 +25,6 @@ target_link_libraries(clangTooling
   clangFrontend
   clangAST
   clangASTMatchers
-  clangRewrite
+  clangRewriteCore
+  clangRewriteFrontend
   )
diff --git a/lib/Tooling/CommandLineClangTool.cpp b/lib/Tooling/CommonOptionsParser.cpp
index 8da2a335a557..15091c7e901e 100644
--- a/lib/Tooling/CommandLineClangTool.cpp
+++ b/lib/Tooling/CommonOptionsParser.cpp
@@ -1,4 +1,4 @@
-//===--- CommandLineClangTool.cpp - command-line clang tools driver -------===//
+//===--- CommonOptionsParser.cpp - common options for clang tools ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,28 +7,31 @@
 //
 //===----------------------------------------------------------------------===//
 //
-//  This file implements the CommandLineClangTool class used to run clang
-//  tools as separate command-line applications with a consistent common
-//  interface for handling compilation database and input files.
+//  This file implements the CommonOptionsParser class used to parse common
+//  command-line options for clang tools, so that they can be run as separate
+//  command-line applications with a consistent common interface for handling
+//  compilation database and input files.
 //
 //  It provides a common subset of command-line options, common algorithm
 //  for locating a compilation database and source files, and help messages
 //  for the basic command-line interface.
 //
-//  It creates a CompilationDatabase, initializes a ClangTool and runs a
-//  user-specified FrontendAction over all TUs in which the given files are
-//  compiled.
+//  It creates a CompilationDatabase and reads common command-line options.
+//
+//  This class uses the Clang Tooling infrastructure, see
+//    http://clang.llvm.org/docs/HowToSetupToolingForLLVM.html
+//  for details on setting it up with LLVM source tree.
 //
 //===----------------------------------------------------------------------===//
 
-#include "clang/Frontend/FrontendActions.h"
-#include "clang/Tooling/CommandLineClangTool.h"
+#include "llvm/Support/CommandLine.h"
+#include "clang/Tooling/CommonOptionsParser.h"
 #include "clang/Tooling/Tooling.h"
 
 using namespace clang::tooling;
 using namespace llvm;
 
-static const char *MoreHelpText =
+const char *const CommonOptionsParser::HelpMessage =
     "\n"
     "-p <build-path> is used to read a compile command database.\n"
     "\n"
@@ -40,26 +43,27 @@ static const char *MoreHelpText =
     "\thttp://clang.llvm.org/docs/HowToSetupToolingForLLVM.html for an\n"
     "\texample of setting up Clang Tooling on a source tree.\n"
     "\n"
-    "<source0> ... specify the paths of source files. These paths are looked\n"
-    "\tup in the compile command database. If the path of a file is absolute,\n"
-    "\tit needs to point into CMake's source tree. If the path is relative,\n"
-    "\tthe current working directory needs to be in the CMake source tree and\n"
-    "\tthe file must be in a subdirectory of the current working directory.\n"
-    "\t\"./\" prefixes in the relative files will be automatically removed,\n"
-    "\tbut the rest of a relative path must be a suffix of a path in the\n"
-    "\tcompile command database.\n"
+    "<source0> ... specify the paths of source files. These paths are\n"
+    "\tlooked up in the compile command database. If the path of a file is\n"
+    "\tabsolute, it needs to point into CMake's source tree. If the path is\n"
+    "\trelative, the current working directory needs to be in the CMake\n"
+    "\tsource tree and the file must be in a subdirectory of the current\n"
+    "\tworking directory. \"./\" prefixes in the relative files will be\n"
+    "\tautomatically removed, but the rest of a relative path must be a\n"
+    "\tsuffix of a path in the compile command database.\n"
     "\n";
 
-CommandLineClangTool::CommandLineClangTool() :
-    BuildPath("p", cl::desc("Build path"), cl::Optional),
-    SourcePaths(cl::Positional, cl::desc("<source0> [... <sourceN>]"),
-                cl::OneOrMore),
-    MoreHelp(MoreHelpText) {
-}
+CommonOptionsParser::CommonOptionsParser(int &argc, const char **argv) {
+  static cl::opt<std::string> BuildPath(
+      "p", cl::desc("Build path"), cl::Optional);
+
+  static cl::list<std::string> SourcePaths(
+      cl::Positional, cl::desc("<source0> [... <sourceN>]"), cl::OneOrMore);
 
-void CommandLineClangTool::initialize(int argc, const char **argv) {
-  Compilations.reset(FixedCompilationDatabase::loadFromCommandLine(argc, argv));
+  Compilations.reset(FixedCompilationDatabase::loadFromCommandLine(argc,
+                                                                   argv));
   cl::ParseCommandLineOptions(argc, argv);
+  SourcePathList = SourcePaths;
   if (!Compilations) {
     std::string ErrorMessage;
     if (!BuildPath.empty()) {
@@ -73,8 +77,3 @@ void CommandLineClangTool::initialize(int argc, const char **argv) {
       llvm::report_fatal_error(ErrorMessage);
   }
 }
-
-int CommandLineClangTool::run(FrontendActionFactory *ActionFactory) {
-  ClangTool Tool(*Compilations, SourcePaths);
-  return Tool.run(ActionFactory);
-}
diff --git a/lib/Tooling/CompilationDatabase.cpp b/lib/Tooling/CompilationDatabase.cpp
index 3139cc21bb8d..4149cda3787c 100644
--- a/lib/Tooling/CompilationDatabase.cpp
+++ b/lib/Tooling/CompilationDatabase.cpp
@@ -7,132 +7,49 @@
 //
 //===----------------------------------------------------------------------===//
 //
-//  This file contains multiple implementations for CompilationDatabases.
+//  This file contains implementations of the CompilationDatabase base class
+//  and the FixedCompilationDatabase.
 //
 //===----------------------------------------------------------------------===//
 
+#include <sstream>
 #include "clang/Tooling/CompilationDatabase.h"
+#include "clang/Tooling/CompilationDatabasePluginRegistry.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/SmallString.h"
-#include "llvm/Support/YAMLParser.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/system_error.h"
 
-#ifdef USE_CUSTOM_COMPILATION_DATABASE
-#include "CustomCompilationDatabase.h"
-#endif
-
 namespace clang {
 namespace tooling {
 
-namespace {
-
-/// \brief A parser for escaped strings of command line arguments.
-///
-/// Assumes \-escaping for quoted arguments (see the documentation of
-/// unescapeCommandLine(...)).
-class CommandLineArgumentParser {
- public:
-  CommandLineArgumentParser(StringRef CommandLine)
-      : Input(CommandLine), Position(Input.begin()-1) {}
-
-  std::vector<std::string> parse() {
-    bool HasMoreInput = true;
-    while (HasMoreInput && nextNonWhitespace()) {
-      std::string Argument;
-      HasMoreInput = parseStringInto(Argument);
-      CommandLine.push_back(Argument);
-    }
-    return CommandLine;
-  }
-
- private:
-  // All private methods return true if there is more input available.
-
-  bool parseStringInto(std::string &String) {
-    do {
-      if (*Position == '"') {
-        if (!parseQuotedStringInto(String)) return false;
-      } else {
-        if (!parseFreeStringInto(String)) return false;
-      }
-    } while (*Position != ' ');
-    return true;
-  }
-
-  bool parseQuotedStringInto(std::string &String) {
-    if (!next()) return false;
-    while (*Position != '"') {
-      if (!skipEscapeCharacter()) return false;
-      String.push_back(*Position);
-      if (!next()) return false;
-    }
-    return next();
-  }
-
-  bool parseFreeStringInto(std::string &String) {
-    do {
-      if (!skipEscapeCharacter()) return false;
-      String.push_back(*Position);
-      if (!next()) return false;
-    } while (*Position != ' ' && *Position != '"');
-    return true;
-  }
-
-  bool skipEscapeCharacter() {
-    if (*Position == '\\') {
-      return next();
-    }
-    return true;
-  }
-
-  bool nextNonWhitespace() {
-    do {
-      if (!next()) return false;
-    } while (*Position == ' ');
-    return true;
-  }
-
-  bool next() {
-    ++Position;
-    return Position != Input.end();
-  }
-
-  const StringRef Input;
-  StringRef::iterator Position;
-  std::vector<std::string> CommandLine;
-};
-
-std::vector<std::string> unescapeCommandLine(
-    StringRef EscapedCommandLine) {
-  CommandLineArgumentParser parser(EscapedCommandLine);
-  return parser.parse();
-}
-
-} // end namespace
-
 CompilationDatabase::~CompilationDatabase() {}
 
 CompilationDatabase *
 CompilationDatabase::loadFromDirectory(StringRef BuildDirectory,
                                        std::string &ErrorMessage) {
-  llvm::SmallString<1024> JSONDatabasePath(BuildDirectory);
-  llvm::sys::path::append(JSONDatabasePath, "compile_commands.json");
-  llvm::OwningPtr<CompilationDatabase> Database(
-    JSONCompilationDatabase::loadFromFile(JSONDatabasePath, ErrorMessage));
-  if (!Database) {
-    return NULL;
+  std::stringstream ErrorStream;
+  for (CompilationDatabasePluginRegistry::iterator
+       It = CompilationDatabasePluginRegistry::begin(),
+       Ie = CompilationDatabasePluginRegistry::end();
+       It != Ie; ++It) {
+    std::string DatabaseErrorMessage;
+    OwningPtr<CompilationDatabasePlugin> Plugin(It->instantiate());
+    if (CompilationDatabase *DB =
+        Plugin->loadFromDirectory(BuildDirectory, DatabaseErrorMessage))
+      return DB;
+    else
+      ErrorStream << It->getName() << ": " << DatabaseErrorMessage << "\n";
   }
-  return Database.take();
+  ErrorMessage = ErrorStream.str();
+  return NULL;
 }
 
 static CompilationDatabase *
-findCompilationDatabaseFromDirectory(StringRef Directory) {
-#ifdef USE_CUSTOM_COMPILATION_DATABASE
-  if (CompilationDatabase *DB =
-      ::clang::tooling::findCompilationDatabaseForDirectory(Directory))
-    return DB;
-#endif
+findCompilationDatabaseFromDirectory(StringRef Directory,
+                                     std::string &ErrorMessage) {
+  std::stringstream ErrorStream;
+  bool HasErrorMessage = false;
   while (!Directory.empty()) {
     std::string LoadErrorMessage;
 
@@ -140,8 +57,15 @@ findCompilationDatabaseFromDirectory(StringRef Directory) {
            CompilationDatabase::loadFromDirectory(Directory, LoadErrorMessage))
       return DB;
 
+    if (!HasErrorMessage) {
+      ErrorStream << "No compilation database found in " << Directory.str()
+                  << " or any parent directory\n" << LoadErrorMessage;
+      HasErrorMessage = true;
+    }
+
     Directory = llvm::sys::path::parent_path(Directory);
   }
+  ErrorMessage = ErrorStream.str();
   return NULL;
 }
 
@@ -151,11 +75,12 @@ CompilationDatabase::autoDetectFromSource(StringRef SourceFile,
   llvm::SmallString<1024> AbsolutePath(getAbsolutePath(SourceFile));
   StringRef Directory = llvm::sys::path::parent_path(AbsolutePath);
 
-  CompilationDatabase *DB = findCompilationDatabaseFromDirectory(Directory);
+  CompilationDatabase *DB = findCompilationDatabaseFromDirectory(Directory,
+                                                                 ErrorMessage);
 
   if (!DB)
     ErrorMessage = ("Could not auto-detect compilation database for file \"" +
-                   SourceFile + "\"").str();
+                   SourceFile + "\"\n" + ErrorMessage).str();
   return DB;
 }
 
@@ -164,14 +89,17 @@ CompilationDatabase::autoDetectFromDirectory(StringRef SourceDir,
                                              std::string &ErrorMessage) {
   llvm::SmallString<1024> AbsolutePath(getAbsolutePath(SourceDir));
 
-  CompilationDatabase *DB = findCompilationDatabaseFromDirectory(AbsolutePath);
+  CompilationDatabase *DB = findCompilationDatabaseFromDirectory(AbsolutePath,
+                                                                 ErrorMessage);
 
   if (!DB)
     ErrorMessage = ("Could not auto-detect compilation database from directory \"" +
-                   SourceDir + "\"").str();
+                   SourceDir + "\"\n" + ErrorMessage).str();
   return DB;
 }
 
+CompilationDatabasePlugin::~CompilationDatabasePlugin() {}
+
 FixedCompilationDatabase *
 FixedCompilationDatabase::loadFromCommandLine(int &Argc,
                                               const char **Argv,
@@ -204,153 +132,10 @@ FixedCompilationDatabase::getAllFiles() const {
   return std::vector<std::string>();
 }
 
-JSONCompilationDatabase *
-JSONCompilationDatabase::loadFromFile(StringRef FilePath,
-                                      std::string &ErrorMessage) {
-  llvm::OwningPtr<llvm::MemoryBuffer> DatabaseBuffer;
-  llvm::error_code Result =
-    llvm::MemoryBuffer::getFile(FilePath, DatabaseBuffer);
-  if (Result != 0) {
-    ErrorMessage = "Error while opening JSON database: " + Result.message();
-    return NULL;
-  }
-  llvm::OwningPtr<JSONCompilationDatabase> Database(
-    new JSONCompilationDatabase(DatabaseBuffer.take()));
-  if (!Database->parse(ErrorMessage))
-    return NULL;
-  return Database.take();
-}
-
-JSONCompilationDatabase *
-JSONCompilationDatabase::loadFromBuffer(StringRef DatabaseString,
-                                        std::string &ErrorMessage) {
-  llvm::OwningPtr<llvm::MemoryBuffer> DatabaseBuffer(
-      llvm::MemoryBuffer::getMemBuffer(DatabaseString));
-  llvm::OwningPtr<JSONCompilationDatabase> Database(
-    new JSONCompilationDatabase(DatabaseBuffer.take()));
-  if (!Database->parse(ErrorMessage))
-    return NULL;
-  return Database.take();
-}
-
-std::vector<CompileCommand>
-JSONCompilationDatabase::getCompileCommands(StringRef FilePath) const {
-  llvm::SmallString<128> NativeFilePath;
-  llvm::sys::path::native(FilePath, NativeFilePath);
-  llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
-    CommandsRefI = IndexByFile.find(NativeFilePath);
-  if (CommandsRefI == IndexByFile.end())
-    return std::vector<CompileCommand>();
-  const std::vector<CompileCommandRef> &CommandsRef = CommandsRefI->getValue();
-  std::vector<CompileCommand> Commands;
-  for (int I = 0, E = CommandsRef.size(); I != E; ++I) {
-    llvm::SmallString<8> DirectoryStorage;
-    llvm::SmallString<1024> CommandStorage;
-    Commands.push_back(CompileCommand(
-      // FIXME: Escape correctly:
-      CommandsRef[I].first->getValue(DirectoryStorage),
-      unescapeCommandLine(CommandsRef[I].second->getValue(CommandStorage))));
-  }
-  return Commands;
-}
-
-std::vector<std::string>
-JSONCompilationDatabase::getAllFiles() const {
-  std::vector<std::string> Result;
-
-  llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
-    CommandsRefI = IndexByFile.begin();
-  const llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
-    CommandsRefEnd = IndexByFile.end();
-  for (; CommandsRefI != CommandsRefEnd; ++CommandsRefI) {
-    Result.push_back(CommandsRefI->first().str());
-  }
-
-  return Result;
-}
-
-bool JSONCompilationDatabase::parse(std::string &ErrorMessage) {
-  llvm::yaml::document_iterator I = YAMLStream.begin();
-  if (I == YAMLStream.end()) {
-    ErrorMessage = "Error while parsing YAML.";
-    return false;
-  }
-  llvm::yaml::Node *Root = I->getRoot();
-  if (Root == NULL) {
-    ErrorMessage = "Error while parsing YAML.";
-    return false;
-  }
-  llvm::yaml::SequenceNode *Array =
-    llvm::dyn_cast<llvm::yaml::SequenceNode>(Root);
-  if (Array == NULL) {
-    ErrorMessage = "Expected array.";
-    return false;
-  }
-  for (llvm::yaml::SequenceNode::iterator AI = Array->begin(),
-                                          AE = Array->end();
-       AI != AE; ++AI) {
-    llvm::yaml::MappingNode *Object =
-      llvm::dyn_cast<llvm::yaml::MappingNode>(&*AI);
-    if (Object == NULL) {
-      ErrorMessage = "Expected object.";
-      return false;
-    }
-    llvm::yaml::ScalarNode *Directory = NULL;
-    llvm::yaml::ScalarNode *Command = NULL;
-    llvm::yaml::ScalarNode *File = NULL;
-    for (llvm::yaml::MappingNode::iterator KVI = Object->begin(),
-                                           KVE = Object->end();
-         KVI != KVE; ++KVI) {
-      llvm::yaml::Node *Value = (*KVI).getValue();
-      if (Value == NULL) {
-        ErrorMessage = "Expected value.";
-        return false;
-      }
-      llvm::yaml::ScalarNode *ValueString =
-        llvm::dyn_cast<llvm::yaml::ScalarNode>(Value);
-      if (ValueString == NULL) {
-        ErrorMessage = "Expected string as value.";
-        return false;
-      }
-      llvm::yaml::ScalarNode *KeyString =
-        llvm::dyn_cast<llvm::yaml::ScalarNode>((*KVI).getKey());
-      if (KeyString == NULL) {
-        ErrorMessage = "Expected strings as key.";
-        return false;
-      }
-      llvm::SmallString<8> KeyStorage;
-      if (KeyString->getValue(KeyStorage) == "directory") {
-        Directory = ValueString;
-      } else if (KeyString->getValue(KeyStorage) == "command") {
-        Command = ValueString;
-      } else if (KeyString->getValue(KeyStorage) == "file") {
-        File = ValueString;
-      } else {
-        ErrorMessage = ("Unknown key: \"" +
-                        KeyString->getRawValue() + "\"").str();
-        return false;
-      }
-    }
-    if (!File) {
-      ErrorMessage = "Missing key: \"file\".";
-      return false;
-    }
-    if (!Command) {
-      ErrorMessage = "Missing key: \"command\".";
-      return false;
-    }
-    if (!Directory) {
-      ErrorMessage = "Missing key: \"directory\".";
-      return false;
-    }
-    llvm::SmallString<8> FileStorage;
-    llvm::SmallString<128> NativeFilePath;
-    llvm::sys::path::native(File->getValue(FileStorage), NativeFilePath);
-    IndexByFile[NativeFilePath].push_back(
-      CompileCommandRef(Directory, Command));
-  }
-  return true;
-}
+// This anchor is used to force the linker to link in the generated object file
+// and thus register the JSONCompilationDatabasePlugin.
+extern volatile int JSONAnchorSource;
+static int JSONAnchorDest = JSONAnchorSource;
 
 } // end namespace tooling
 } // end namespace clang
diff --git a/lib/Tooling/CustomCompilationDatabase.h b/lib/Tooling/CustomCompilationDatabase.h
deleted file mode 100644
index b375f8d25634..000000000000
--- a/lib/Tooling/CustomCompilationDatabase.h
+++ /dev/null
@@ -1,42 +0,0 @@
-//===--- CustomCompilationDatabase.h --------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-//  This file contains a hook to supply a custom \c CompilationDatabase
-//  implementation.
-//
-//  The mechanism can be used by IDEs or non-public code bases to integrate with
-//  their build system. Currently we support statically linking in an
-//  implementation of \c findCompilationDatabaseForDirectory and enabling it
-//  with -DUSE_CUSTOM_COMPILATION_DATABASE when compiling the Tooling library.
-//
-//  FIXME: The strategy forward is to provide a plugin system that can load
-//  custom compilation databases and make enabling that a build option.
-//
-//===----------------------------------------------------------------------===//
-#ifndef LLVM_CLANG_TOOLING_CUSTOM_COMPILATION_DATABASE_H
-#define LLVM_CLANG_TOOLING_CUSTOM_COMPILATION_DATABASE_H
-
-#include "llvm/ADT/StringRef.h"
-
-namespace clang {
-namespace tooling {
-class CompilationDatabase;
-
-/// \brief Returns a CompilationDatabase for the given \c Directory.
-///
-/// \c Directory can be any directory within a project. This methods will
-/// then try to find compilation database files in \c Directory or any of its
-/// parents. If a compilation database cannot be found or loaded, returns NULL.
-clang::tooling::CompilationDatabase *findCompilationDatabaseForDirectory(
-  llvm::StringRef Directory);
-
-} // namespace tooling
-} // namespace clang
-
-#endif // LLVM_CLANG_TOOLING_CUSTOM_COMPILATION_DATABASE_H
diff --git a/lib/Tooling/FileMatchTrie.cpp b/lib/Tooling/FileMatchTrie.cpp
new file mode 100644
index 000000000000..8f25a8c2bcfb
--- /dev/null
+++ b/lib/Tooling/FileMatchTrie.cpp
@@ -0,0 +1,188 @@
+//===--- FileMatchTrie.cpp - ----------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file contains the implementation of a FileMatchTrie.
+//
+//===----------------------------------------------------------------------===//
+
+#include <sstream>
+#include "clang/Tooling/FileMatchTrie.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/PathV2.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace tooling {
+
+/// \brief Default \c PathComparator using \c llvm::sys::fs::equivalent().
+struct DefaultPathComparator : public PathComparator {
+  virtual ~DefaultPathComparator() {}
+  virtual bool equivalent(StringRef FileA, StringRef FileB) const {
+    return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB);
+  }
+};
+
+/// \brief A node of the \c FileMatchTrie.
+///
+/// Each node has storage for up to one path and a map mapping a path segment to
+/// child nodes. The trie starts with an empty root node.
+class FileMatchTrieNode {
+public:
+  /// \brief Inserts 'NewPath' into this trie. \c ConsumedLength denotes
+  /// the number of \c NewPath's trailing characters already consumed during
+  /// recursion.
+  ///
+  /// An insert of a path
+  /// 'p'starts at the root node and does the following:
+  /// - If the node is empty, insert 'p' into its storage and abort.
+  /// - If the node has a path 'p2' but no children, take the last path segment
+  ///   's' of 'p2', put a new child into the map at 's' an insert the rest of
+  ///   'p2' there.
+  /// - Insert a new child for the last segment of 'p' and insert the rest of
+  ///   'p' there.
+  ///
+  /// An insert operation is linear in the number of a path's segments.
+  void insert(StringRef NewPath, unsigned ConsumedLength = 0) {
+    // We cannot put relative paths into the FileMatchTrie as then a path can be
+    // a postfix of another path, violating a core assumption of the trie.
+    if (llvm::sys::path::is_relative(NewPath))
+      return;
+    if (Path.empty()) {
+      // This is an empty leaf. Store NewPath and return.
+      Path = NewPath;
+      return;
+    }
+    if (Children.empty()) {
+      // This is a leaf, ignore duplicate entry if 'Path' equals 'NewPath'.
+      if (NewPath == Path)
+          return;
+      // Make this a node and create a child-leaf with 'Path'.
+      StringRef Element(llvm::sys::path::filename(
+          StringRef(Path).drop_back(ConsumedLength)));
+      Children[Element].Path = Path;
+    }
+    StringRef Element(llvm::sys::path::filename(
+          StringRef(NewPath).drop_back(ConsumedLength)));
+    Children[Element].insert(NewPath, ConsumedLength + Element.size() + 1);
+  }
+
+  /// \brief Tries to find the node under this \c FileMatchTrieNode that best
+  /// matches 'FileName'.
+  ///
+  /// If multiple paths fit 'FileName' equally well, \c IsAmbiguous is set to
+  /// \c true and an empty string is returned. If no path fits 'FileName', an
+  /// empty string is returned. \c ConsumedLength denotes the number of
+  /// \c Filename's trailing characters already consumed during recursion.
+  ///
+  /// To find the best matching node for a given path 'p', the
+  /// \c findEquivalent() function is called recursively for each path segment
+  /// (back to fron) of 'p' until a node 'n' is reached that does not ..
+  /// - .. have children. In this case it is checked
+  ///   whether the stored path is equivalent to 'p'. If yes, the best match is
+  ///   found. Otherwise continue with the parent node as if this node did not
+  ///   exist.
+  /// - .. a child matching the next path segment. In this case, all children of
+  ///   'n' are an equally good match for 'p'. All children are of 'n' are found
+  ///   recursively and their equivalence to 'p' is determined. If none are
+  ///   equivalent, continue with the parent node as if 'n' didn't exist. If one
+  ///   is equivalent, the best match is found. Otherwise, report and ambigiuity
+  ///   error.
+  StringRef findEquivalent(const PathComparator& Comparator,
+                           StringRef FileName,
+                           bool &IsAmbiguous,
+                           unsigned ConsumedLength = 0) const {
+    if (Children.empty()) {
+      if (Comparator.equivalent(StringRef(Path), FileName))
+        return StringRef(Path);
+      return StringRef();
+    }
+    StringRef Element(llvm::sys::path::filename(FileName.drop_back(
+        ConsumedLength)));
+    llvm::StringMap<FileMatchTrieNode>::const_iterator MatchingChild =
+        Children.find(Element);
+    if (MatchingChild != Children.end()) {
+      StringRef Result = MatchingChild->getValue().findEquivalent(
+          Comparator, FileName, IsAmbiguous,
+          ConsumedLength + Element.size() + 1);
+      if (!Result.empty() || IsAmbiguous)
+        return Result;
+    }
+    std::vector<StringRef> AllChildren;
+    getAll(AllChildren, MatchingChild);
+    StringRef Result;
+    for (unsigned i = 0; i < AllChildren.size(); i++) {
+      if (Comparator.equivalent(AllChildren[i], FileName)) {
+        if (Result.empty()) {
+          Result = AllChildren[i];
+        } else {
+          IsAmbiguous = true;
+          return StringRef();
+        }
+      }
+    }
+    return Result;
+  }
+
+private:
+  /// \brief Gets all paths under this FileMatchTrieNode.
+  void getAll(std::vector<StringRef> &Results,
+              llvm::StringMap<FileMatchTrieNode>::const_iterator Except) const {
+    if (Path.empty())
+      return;
+    if (Children.empty()) {
+      Results.push_back(StringRef(Path));
+      return;
+    }
+    for (llvm::StringMap<FileMatchTrieNode>::const_iterator
+         It = Children.begin(), E = Children.end();
+         It != E; ++It) {
+      if (It == Except)
+        continue;
+      It->getValue().getAll(Results, Children.end());
+    }
+  }
+
+  // The stored absolute path in this node. Only valid for leaf nodes, i.e.
+  // nodes where Children.empty().
+  std::string Path;
+
+  // The children of this node stored in a map based on the next path segment.
+  llvm::StringMap<FileMatchTrieNode> Children;
+};
+
+FileMatchTrie::FileMatchTrie()
+  : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {}
+
+FileMatchTrie::FileMatchTrie(PathComparator *Comparator)
+  : Root(new FileMatchTrieNode), Comparator(Comparator) {}
+
+FileMatchTrie::~FileMatchTrie() {
+  delete Root;
+}
+
+void FileMatchTrie::insert(StringRef NewPath) {
+  Root->insert(NewPath);
+}
+
+StringRef FileMatchTrie::findEquivalent(StringRef FileName,
+                                        llvm::raw_ostream &Error) const {
+  if (llvm::sys::path::is_relative(FileName)) {
+    Error << "Cannot resolve relative paths";
+    return StringRef();
+  }
+  bool IsAmbiguous = false;
+  StringRef Result = Root->findEquivalent(*Comparator, FileName, IsAmbiguous);
+  if (IsAmbiguous)
+    Error << "Path is ambiguous";
+  return Result;
+}
+
+} // end namespace tooling
+} // end namespace clang
diff --git a/lib/Tooling/JSONCompilationDatabase.cpp b/lib/Tooling/JSONCompilationDatabase.cpp
new file mode 100644
index 000000000000..cf35a2566637
--- /dev/null
+++ b/lib/Tooling/JSONCompilationDatabase.cpp
@@ -0,0 +1,303 @@
+//===--- JSONCompilationDatabase.cpp - ------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file contains the implementation of the JSONCompilationDatabase.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/JSONCompilationDatabase.h"
+
+#include "clang/Tooling/CompilationDatabase.h"
+#include "clang/Tooling/CompilationDatabasePluginRegistry.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/system_error.h"
+
+namespace clang {
+namespace tooling {
+
+namespace {
+
+/// \brief A parser for escaped strings of command line arguments.
+///
+/// Assumes \-escaping for quoted arguments (see the documentation of
+/// unescapeCommandLine(...)).
+class CommandLineArgumentParser {
+ public:
+  CommandLineArgumentParser(StringRef CommandLine)
+      : Input(CommandLine), Position(Input.begin()-1) {}
+
+  std::vector<std::string> parse() {
+    bool HasMoreInput = true;
+    while (HasMoreInput && nextNonWhitespace()) {
+      std::string Argument;
+      HasMoreInput = parseStringInto(Argument);
+      CommandLine.push_back(Argument);
+    }
+    return CommandLine;
+  }
+
+ private:
+  // All private methods return true if there is more input available.
+
+  bool parseStringInto(std::string &String) {
+    do {
+      if (*Position == '"') {
+        if (!parseQuotedStringInto(String)) return false;
+      } else {
+        if (!parseFreeStringInto(String)) return false;
+      }
+    } while (*Position != ' ');
+    return true;
+  }
+
+  bool parseQuotedStringInto(std::string &String) {
+    if (!next()) return false;
+    while (*Position != '"') {
+      if (!skipEscapeCharacter()) return false;
+      String.push_back(*Position);
+      if (!next()) return false;
+    }
+    return next();
+  }
+
+  bool parseFreeStringInto(std::string &String) {
+    do {
+      if (!skipEscapeCharacter()) return false;
+      String.push_back(*Position);
+      if (!next()) return false;
+    } while (*Position != ' ' && *Position != '"');
+    return true;
+  }
+
+  bool skipEscapeCharacter() {
+    if (*Position == '\\') {
+      return next();
+    }
+    return true;
+  }
+
+  bool nextNonWhitespace() {
+    do {
+      if (!next()) return false;
+    } while (*Position == ' ');
+    return true;
+  }
+
+  bool next() {
+    ++Position;
+    return Position != Input.end();
+  }
+
+  const StringRef Input;
+  StringRef::iterator Position;
+  std::vector<std::string> CommandLine;
+};
+
+std::vector<std::string> unescapeCommandLine(
+    StringRef EscapedCommandLine) {
+  CommandLineArgumentParser parser(EscapedCommandLine);
+  return parser.parse();
+}
+
+} // end namespace
+
+class JSONCompilationDatabasePlugin : public CompilationDatabasePlugin {
+  virtual CompilationDatabase *loadFromDirectory(
+      StringRef Directory, std::string &ErrorMessage) {
+    llvm::SmallString<1024> JSONDatabasePath(Directory);
+    llvm::sys::path::append(JSONDatabasePath, "compile_commands.json");
+    llvm::OwningPtr<CompilationDatabase> Database(
+        JSONCompilationDatabase::loadFromFile(JSONDatabasePath, ErrorMessage));
+    if (!Database)
+      return NULL;
+    return Database.take();
+  }
+};
+
+// Register the JSONCompilationDatabasePlugin with the
+// CompilationDatabasePluginRegistry using this statically initialized variable.
+static CompilationDatabasePluginRegistry::Add<JSONCompilationDatabasePlugin>
+X("json-compilation-database", "Reads JSON formatted compilation databases");
+
+// This anchor is used to force the linker to link in the generated object file
+// and thus register the JSONCompilationDatabasePlugin.
+volatile int JSONAnchorSource = 0;
+
+JSONCompilationDatabase *
+JSONCompilationDatabase::loadFromFile(StringRef FilePath,
+                                      std::string &ErrorMessage) {
+  llvm::OwningPtr<llvm::MemoryBuffer> DatabaseBuffer;
+  llvm::error_code Result =
+    llvm::MemoryBuffer::getFile(FilePath, DatabaseBuffer);
+  if (Result != 0) {
+    ErrorMessage = "Error while opening JSON database: " + Result.message();
+    return NULL;
+  }
+  llvm::OwningPtr<JSONCompilationDatabase> Database(
+    new JSONCompilationDatabase(DatabaseBuffer.take()));
+  if (!Database->parse(ErrorMessage))
+    return NULL;
+  return Database.take();
+}
+
+JSONCompilationDatabase *
+JSONCompilationDatabase::loadFromBuffer(StringRef DatabaseString,
+                                        std::string &ErrorMessage) {
+  llvm::OwningPtr<llvm::MemoryBuffer> DatabaseBuffer(
+      llvm::MemoryBuffer::getMemBuffer(DatabaseString));
+  llvm::OwningPtr<JSONCompilationDatabase> Database(
+    new JSONCompilationDatabase(DatabaseBuffer.take()));
+  if (!Database->parse(ErrorMessage))
+    return NULL;
+  return Database.take();
+}
+
+std::vector<CompileCommand>
+JSONCompilationDatabase::getCompileCommands(StringRef FilePath) const {
+  llvm::SmallString<128> NativeFilePath;
+  llvm::sys::path::native(FilePath, NativeFilePath);
+  std::vector<StringRef> PossibleMatches;
+  std::string Error;
+  llvm::raw_string_ostream ES(Error);
+  StringRef Match = MatchTrie.findEquivalent(NativeFilePath.str(), ES);
+  if (Match.empty()) {
+    if (Error.empty())
+      Error = "No match found.";
+    llvm::outs() << Error << "\n";
+    return std::vector<CompileCommand>();
+  }
+  llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
+    CommandsRefI = IndexByFile.find(Match);
+  if (CommandsRefI == IndexByFile.end())
+    return std::vector<CompileCommand>();
+  const std::vector<CompileCommandRef> &CommandsRef = CommandsRefI->getValue();
+  std::vector<CompileCommand> Commands;
+  for (int I = 0, E = CommandsRef.size(); I != E; ++I) {
+    llvm::SmallString<8> DirectoryStorage;
+    llvm::SmallString<1024> CommandStorage;
+    Commands.push_back(CompileCommand(
+      // FIXME: Escape correctly:
+      CommandsRef[I].first->getValue(DirectoryStorage),
+      unescapeCommandLine(CommandsRef[I].second->getValue(CommandStorage))));
+  }
+  return Commands;
+}
+
+std::vector<std::string>
+JSONCompilationDatabase::getAllFiles() const {
+  std::vector<std::string> Result;
+
+  llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
+    CommandsRefI = IndexByFile.begin();
+  const llvm::StringMap< std::vector<CompileCommandRef> >::const_iterator
+    CommandsRefEnd = IndexByFile.end();
+  for (; CommandsRefI != CommandsRefEnd; ++CommandsRefI) {
+    Result.push_back(CommandsRefI->first().str());
+  }
+
+  return Result;
+}
+
+bool JSONCompilationDatabase::parse(std::string &ErrorMessage) {
+  llvm::yaml::document_iterator I = YAMLStream.begin();
+  if (I == YAMLStream.end()) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+  llvm::yaml::Node *Root = I->getRoot();
+  if (Root == NULL) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+  llvm::yaml::SequenceNode *Array =
+    llvm::dyn_cast<llvm::yaml::SequenceNode>(Root);
+  if (Array == NULL) {
+    ErrorMessage = "Expected array.";
+    return false;
+  }
+  for (llvm::yaml::SequenceNode::iterator AI = Array->begin(),
+                                          AE = Array->end();
+       AI != AE; ++AI) {
+    llvm::yaml::MappingNode *Object =
+      llvm::dyn_cast<llvm::yaml::MappingNode>(&*AI);
+    if (Object == NULL) {
+      ErrorMessage = "Expected object.";
+      return false;
+    }
+    llvm::yaml::ScalarNode *Directory = NULL;
+    llvm::yaml::ScalarNode *Command = NULL;
+    llvm::yaml::ScalarNode *File = NULL;
+    for (llvm::yaml::MappingNode::iterator KVI = Object->begin(),
+                                           KVE = Object->end();
+         KVI != KVE; ++KVI) {
+      llvm::yaml::Node *Value = (*KVI).getValue();
+      if (Value == NULL) {
+        ErrorMessage = "Expected value.";
+        return false;
+      }
+      llvm::yaml::ScalarNode *ValueString =
+        llvm::dyn_cast<llvm::yaml::ScalarNode>(Value);
+      if (ValueString == NULL) {
+        ErrorMessage = "Expected string as value.";
+        return false;
+      }
+      llvm::yaml::ScalarNode *KeyString =
+        llvm::dyn_cast<llvm::yaml::ScalarNode>((*KVI).getKey());
+      if (KeyString == NULL) {
+        ErrorMessage = "Expected strings as key.";
+        return false;
+      }
+      llvm::SmallString<8> KeyStorage;
+      if (KeyString->getValue(KeyStorage) == "directory") {
+        Directory = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "command") {
+        Command = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "file") {
+        File = ValueString;
+      } else {
+        ErrorMessage = ("Unknown key: \"" +
+                        KeyString->getRawValue() + "\"").str();
+        return false;
+      }
+    }
+    if (!File) {
+      ErrorMessage = "Missing key: \"file\".";
+      return false;
+    }
+    if (!Command) {
+      ErrorMessage = "Missing key: \"command\".";
+      return false;
+    }
+    if (!Directory) {
+      ErrorMessage = "Missing key: \"directory\".";
+      return false;
+    }
+    llvm::SmallString<8> FileStorage;
+    StringRef FileName = File->getValue(FileStorage);
+    llvm::SmallString<128> NativeFilePath;
+    if (llvm::sys::path::is_relative(FileName)) {
+      llvm::SmallString<8> DirectoryStorage;
+      llvm::SmallString<128> AbsolutePath(
+          Directory->getValue(DirectoryStorage));
+      llvm::sys::path::append(AbsolutePath, FileName);
+      llvm::sys::path::native(AbsolutePath.str(), NativeFilePath);
+    } else {
+      llvm::sys::path::native(FileName, NativeFilePath);
+    }
+    IndexByFile[NativeFilePath].push_back(
+        CompileCommandRef(Directory, Command));
+    MatchTrie.insert(NativeFilePath.str());
+  }
+  return true;
+}
+
+} // end namespace tooling
+} // end namespace clang
diff --git a/lib/Tooling/Refactoring.cpp b/lib/Tooling/Refactoring.cpp
index 628435307c0b..c5002ef9fcfc 100644
--- a/lib/Tooling/Refactoring.cpp
+++ b/lib/Tooling/Refactoring.cpp
@@ -11,12 +11,12 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
-#include "clang/Frontend/DiagnosticOptions.h"
 #include "clang/Frontend/TextDiagnosticPrinter.h"
 #include "clang/Lex/Lexer.h"
-#include "clang/Rewrite/Rewriter.h"
+#include "clang/Rewrite/Core/Rewriter.h"
 #include "clang/Tooling/Refactoring.h"
 #include "llvm/Support/raw_os_ostream.h"
 
@@ -164,12 +164,11 @@ Replacements &RefactoringTool::getReplacements() { return Replace; }
 int RefactoringTool::run(FrontendActionFactory *ActionFactory) {
   int Result = Tool.run(ActionFactory);
   LangOptions DefaultLangOptions;
-  DiagnosticOptions DefaultDiagnosticOptions;
-  TextDiagnosticPrinter DiagnosticPrinter(llvm::errs(),
-                                          DefaultDiagnosticOptions);
+  IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
+  TextDiagnosticPrinter DiagnosticPrinter(llvm::errs(), &*DiagOpts);
   DiagnosticsEngine Diagnostics(
       llvm::IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()),
-      &DiagnosticPrinter, false);
+      &*DiagOpts, &DiagnosticPrinter, false);
   SourceManager Sources(Diagnostics, Tool.getFiles());
   Rewriter Rewrite(Sources, DefaultLangOptions);
   if (!applyAllReplacements(Replace, Rewrite)) {
diff --git a/lib/Tooling/Tooling.cpp b/lib/Tooling/Tooling.cpp
index e93e0c97f710..af20254811aa 100644
--- a/lib/Tooling/Tooling.cpp
+++ b/lib/Tooling/Tooling.cpp
@@ -97,17 +97,22 @@ static clang::CompilerInvocation *newInvocation(
 
 bool runToolOnCode(clang::FrontendAction *ToolAction, const Twine &Code,
                    const Twine &FileName) {
+  return runToolOnCodeWithArgs(
+      ToolAction, Code, std::vector<std::string>(), FileName);
+}
+
+bool runToolOnCodeWithArgs(clang::FrontendAction *ToolAction, const Twine &Code,
+                           const std::vector<std::string> &Args,
+                           const Twine &FileName) {
   SmallString<16> FileNameStorage;
   StringRef FileNameRef = FileName.toNullTerminatedStringRef(FileNameStorage);
-  const char *const CommandLine[] = {
-      "clang-tool", "-fsyntax-only", FileNameRef.data()
-  };
+  std::vector<std::string> Commands;
+  Commands.push_back("clang-tool");
+  Commands.push_back("-fsyntax-only");
+  Commands.insert(Commands.end(), Args.begin(), Args.end());
+  Commands.push_back(FileNameRef.data());
   FileManager Files((FileSystemOptions()));
-  ToolInvocation Invocation(
-      std::vector<std::string>(
-          CommandLine,
-          CommandLine + llvm::array_lengthof(CommandLine)),
-      ToolAction, &Files);
+  ToolInvocation Invocation(Commands, ToolAction, &Files);
 
   SmallString<1024> CodeStorage;
   Invocation.mapVirtualFile(FileNameRef,
@@ -154,11 +159,12 @@ bool ToolInvocation::run() {
   for (int I = 0, E = CommandLine.size(); I != E; ++I)
     Argv.push_back(CommandLine[I].c_str());
   const char *const BinaryName = Argv[0];
-  DiagnosticOptions DefaultDiagnosticOptions;
+  IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
   TextDiagnosticPrinter DiagnosticPrinter(
-      llvm::errs(), DefaultDiagnosticOptions);
-  DiagnosticsEngine Diagnostics(llvm::IntrusiveRefCntPtr<clang::DiagnosticIDs>(
-      new DiagnosticIDs()), &DiagnosticPrinter, false);
+      llvm::errs(), &*DiagOpts);
+  DiagnosticsEngine Diagnostics(
+    llvm::IntrusiveRefCntPtr<clang::DiagnosticIDs>(new DiagnosticIDs()),
+    &*DiagOpts, &DiagnosticPrinter, false);
 
   const llvm::OwningPtr<clang::driver::Driver> Driver(
       newDriver(&Diagnostics, BinaryName));