Make CompilationDatabase work with symlinks and relative paths

[djasper]

Summary

This is a first version of my patch to properly support symlinks in the compilation database design, hopefully following the algorithm we discussed on IRC (see class comment of FileNameMatchTrie).

[djasper]

Ping.

[chandlerc]

Some high-level comments. My brain couldn't get wrapped around the trie structure yet though...

include/clang/Tooling/CompilationDatabase.h

193–198

Why expose this and require it to be passed into findEquivalent? It would simplify things to sink this into the implementation details of findEquivalent. and hide its existence from the users.

200–201

You explain in nice detail why this exists and its purpose, but no where do you really explain the datastructure technique you are using to build the trie efficiently. What are the expected storage requirements? what's the strategy used? I feel left a bit in the dark regarding the actual algorithms.

208–209

<project-root> is missing the '>' above.

236–239

Rather than a "std::string *" output parameter, I would suggest passing in a reference to a raw_ostream. You can then build a raw_ostream around a std::string or whatever other string object you like when calling this, and the function can avail itself of all the streamed output conveniences.

lib/Tooling/JSONCompilationDatabase.cpp

288

is this line over 80 columns, or is phab just being confusing?

[djasper]

include/clang/Tooling/CompilationDatabase.h

193–198

Injecting this is important for testing and I did not want to store anything in the Trie nodes. I have now split findEquivalent into two methods, the public one requiring fewer arguments. I'll put more effort into hiding PathComparator once you okayed the design in general.

200–201

How about this?

208–209

Added.

236–239

Done.

lib/Tooling/JSONCompilationDatabase.cpp

288

No, it was 81 columns.

[klimek]

include/clang/Tooling/CompilationDatabase.h

193

I think the MatchTrie and PathComparator should go into a different header file - they are implementation details of the compilation databases.

216–224

Here and below: the repetition of implementation details in the comment strikes me as odd. Why is a user of this at all interested in how exactly the implementation works? (I'm also not sure that's really what Chandler was after...)

256

What's ConsumedLength?

266

Now might be the time to start using Diagnostics instead of spreading the use of other error mechanisms...

275

I'd want to put the PathComparator in as a template parameter, and try to get rid of the friend test.

lib/Tooling/CompilationDatabase.cpp

136

Why do we need this? (as in: a comment might help :)

[djasper]

include/clang/Tooling/CompilationDatabase.h

193

Moved into a separate .h and .cpp file. I think a header file in clang/include/Tooling might still be useful as this is reusable for custom compilation databases.

216–224

I agree. What can I do?

256

Explained in comment now.

266

AFAICT, this implies a somewhat significant refactoring of other parts of libTooling (outside of the CompilationDatabase). I am happy to start working on that, but I would prefer to do that as a separate patch.

275

The test can now inject it into the FileNameTrie.

lib/Tooling/CompilationDatabase.cpp

136

Added comment.

[klimek]

Apart from:

• my nits
• my disagreement about where to put the comments
• a hunch that we'll want more tests ;)

looks good.

include/clang/Tooling/FileMatchTrie.h

104 ↗

(On Diff #153)

I have a small preference to overloading the constructor (because we don't need to ever call this multiple times).

lib/Tooling/FileMatchTrie.cpp

79 ↗

(On Diff #153)

80 columns.

144 ↗

(On Diff #153)

80 columns.

[djasper]

Nits and comments fixed.

include/clang/Tooling/FileMatchTrie.h

104 ↗

(On Diff #153)

Done.

lib/Tooling/FileMatchTrie.cpp

79 ↗

(On Diff #153)

Done.

144 ↗

(On Diff #153)

Done.

[klimek]

LG

[djasper]

Submitted as r165392.

include/clang/Tooling/CompilationDatabase.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_COMPILATION_DATABASE_H
 #define LLVM_CLANG_TOOLING_COMPILATION_DATABASE_H
 
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/PathV2.h"
+
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace tooling {
 
 /// \brief Specifies the working directory and command of a compilation.
 struct CompileCommand {
public:
   virtual std::vector<std::string> getAllFiles() const;
 
 private:
   /// This is built up to contain a single entry vector to be returned from
   /// getCompileCommands after adding the positional argument.
   std::vector<CompileCommand> CompileCommands;
 };
 
+struct PathComparator {
+  virtual bool equivalent(const Twine &FileA, const Twine &FileB) const {
+    return FileA.str() == FileB.str() ||
+        llvm::sys::fs::equivalent(FileA, FileB);
+  }
+};
+
+
+/// \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 FileNameMatchTrie 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.
+///
+/// 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. 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.
+///
+/// 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.
+///
+/// An insert operation is linear in the number of a path's segments. The
+/// \c findEquivalent() operation can will in worst case (when the Trie does not
+/// contain the input path) compare each store path against the input path.
+class FileNameMatchTrie {
+public:
+  /// \brief Inserts 'NewPath' into this trie.
+  void insert(StringRef NewPath, unsigned ConsumedLength = 0);
+
+  /// \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 StringRef is return. If there are ambigious
+  /// matches, an empty StringRef is return and a corresponding message written
+  /// to 'Error'.
+  StringRef findEquivalent(StringRef FileName,
+                           llvm::raw_ostream &Error) const;
+
+private:
+  friend class FileNameMatchTrieTest;
+
+  /// Internal version of \c findEquivalent(). If multiple paths fit 'FileName'
+  /// equally well, \c IsAmbiguous is set to \c true. \c ConsumedLength denotes
+  /// the number of \c Filename's trailing characters already consumed during
+  /// recursion.
+  StringRef findEquivalent(const PathComparator &Comparator,
+                           StringRef FileName,
+                           bool &IsAmbiguous,
+                           unsigned ConsumedLength) const;
+
+  /// \brief Gets all paths in this FileNameMatchTrie.
+  void getAll(std::vector<StringRef> &Results,
+              llvm::StringMap<FileNameMatchTrie>::const_iterator Except) const;
+
+  // 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<FileNameMatchTrie> Children;
+};
+
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_COMPILATION_DATABASE_H

include/clang/Tooling/JSONCompilationDatabase.h

private:
 
   // Tuple (directory, commandline) where 'commandline' pointing to the
   // corresponding nodes in the YAML stream.
   typedef std::pair<llvm::yaml::ScalarNode*,
                     llvm::yaml::ScalarNode*> CompileCommandRef;
 
   // Maps file paths to the compile command lines for that file.
   llvm::StringMap< std::vector<CompileCommandRef> > IndexByFile;
   
+  FileNameMatchTrie MatchTrie;
+
   llvm::OwningPtr<llvm::MemoryBuffer> Database;
   llvm::SourceMgr SM;
   llvm::yaml::Stream YAMLStream;
 };
 
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_JSON_COMPILATION_DATABASE_H

lib/Tooling/CompilationDatabase.cpp

FixedCompilationDatabase::getAllFiles() const {
   return std::vector<std::string>();
 }
 
 // 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;
 
+void FileNameMatchTrie::insert(StringRef NewPath, unsigned ConsumedLength) {
+  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);
+}
+
+StringRef FileNameMatchTrie::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;
+  PathComparator PathComp;
+  StringRef Result = findEquivalent(PathComp, FileName, IsAmbiguous, 0);
+  if (IsAmbiguous)
+    Error << "Path is ambiguous";
+  return Result;
+}
+
+StringRef FileNameMatchTrie::findEquivalent(const PathComparator &Comparator,
+                                            StringRef FileName,
+                                            bool &IsAmbiguous,
+                                            unsigned ConsumedLength) 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<FileNameMatchTrie>::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;
+}
+
+void FileNameMatchTrie::getAll(
+    std::vector<StringRef> &Results,
+    llvm::StringMap<FileNameMatchTrie>::const_iterator Except) const {
+  if (Path.empty())
+    return;
+  if (Children.empty()) {
+    Results.push_back(StringRef(Path));
+    return;
+  }
+  for (llvm::StringMap<FileNameMatchTrie>::const_iterator
+       It = Children.begin(), E = Children.end();
+       It != E; ++It) {
+    if (It == Except)
+      continue;
+    It->getValue().getAll(Results, Children.end());
+  }
+}
+
 } // end namespace tooling
 } // end namespace clang

lib/Tooling/JSONCompilationDatabase.cpp

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(NativeFilePath);
+    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(
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;
-    llvm::sys::path::native(File->getValue(FileStorage), 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

unittests/Tooling/CompilationDatabaseTest.cpp

 }
 
 TEST(JSONCompilationDatabase, GetAllFiles) {
   std::string ErrorMessage;
   EXPECT_EQ(std::vector<std::string>(),
             getAllFiles("[]", ErrorMessage)) << ErrorMessage;
 
   std::vector<std::string> expected_files;
-  expected_files.push_back("file1");
-  expected_files.push_back("file2");
+  expected_files.push_back("/dir/file1");
+  expected_files.push_back("/dir/file2");
   EXPECT_EQ(expected_files, getAllFiles(
-    "[{\"directory\":\"dir\","
+    "[{\"directory\":\"/dir\","
       "\"command\":\"command\","
       "\"file\":\"file1\"},"
-    " {\"directory\":\"dir\","
+    " {\"directory\":\"/dir\","
       "\"command\":\"command\","
       "\"file\":\"file2\"}]",
     ErrorMessage)) << ErrorMessage;
 }
 
 static CompileCommand findCompileArgsInJsonDatabase(StringRef FileName,
                                                     StringRef JSONDatabase,
                                                     std::string &ErrorMessage) {
   llvm::OwningPtr<CompilationDatabase> Database(
       JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage));
   if (!Database)
     return CompileCommand();
   std::vector<CompileCommand> Commands = Database->getCompileCommands(FileName);
   EXPECT_LE(Commands.size(), 1u);
   if (Commands.empty())
     return CompileCommand();
   return Commands[0];
 }
 
+struct FakeComparator : public PathComparator {
+  virtual bool equivalent(const Twine &FileA, const Twine &FileB) const {
+    return StringRef(FileA.str()).equals_lower(FileB.str());
+  }
+};
+
+class FileNameMatchTrieTest : public ::testing::Test {
+protected:
+  StringRef find(StringRef Path) {
+    IsAmbiguous = false;
+    return Trie.findEquivalent(Comparator, Path, IsAmbiguous, 0);
+  }
+
+  FileNameMatchTrie Trie;
+  FakeComparator Comparator;
+  bool IsAmbiguous;
+};
+
+TEST_F(FileNameMatchTrieTest, InsertingRelativePath) {
+  Trie.insert("/path/file.cc");
+  Trie.insert("file.cc");
+  EXPECT_EQ("/path/file.cc", find("/path/file.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, MatchingRelativePath) {
+  EXPECT_EQ("", find("file.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, ReturnsBestResults) {
+  Trie.insert("/d/c/b.cc");
+  Trie.insert("/d/b/b.cc");
+  EXPECT_EQ("/d/b/b.cc", find("/d/b/b.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, HandlesSymlinks) {
+  Trie.insert("/AA/file.cc");
+  EXPECT_EQ("/AA/file.cc", find("/aa/file.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, ReportsSymlinkAmbiguity) {
+  Trie.insert("/Aa/file.cc");
+  Trie.insert("/aA/file.cc");
+  EXPECT_TRUE(find("/aa/file.cc").empty());
+  EXPECT_TRUE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, LongerMatchingSuffixPreferred) {
+  Trie.insert("/src/Aa/file.cc");
+  Trie.insert("/src/aA/file.cc");
+  Trie.insert("/SRC/aa/file.cc");
+  EXPECT_EQ("/SRC/aa/file.cc", find("/src/aa/file.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, EmptyTrie) {
+  EXPECT_TRUE(find("/some/path").empty());
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, NoResult) {
+  Trie.insert("/somepath/otherfile.cc");
+  Trie.insert("/otherpath/somefile.cc");
+  EXPECT_EQ("", find("/somepath/somefile.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
+TEST_F(FileNameMatchTrieTest, RootElementDifferent) {
+  Trie.insert("/path/file.cc");
+  Trie.insert("/otherpath/file.cc");
+  EXPECT_EQ("/path/file.cc", find("/path/file.cc"));
+  EXPECT_FALSE(IsAmbiguous);
+}
+
 TEST(findCompileArgsInJsonDatabase, FindsNothingIfEmpty) {
   std::string ErrorMessage;
   CompileCommand NotFound = findCompileArgsInJsonDatabase(
     "a-file.cpp", "", ErrorMessage);
   EXPECT_TRUE(NotFound.CommandLine.empty()) << ErrorMessage;
   EXPECT_TRUE(NotFound.Directory.empty()) << ErrorMessage;
 }
 
CompileCommand FoundCommand = findCompileArgsInJsonDatabase(
     ("[{\"directory\":\"" + Directory + "\"," +
        "\"command\":\"" + Command + "\","
        "\"file\":\"" + FileName + "\"}]").str(),
     ErrorMessage);
   EXPECT_EQ(Directory, FoundCommand.Directory) << ErrorMessage;
 }
 
 TEST(findCompileArgsInJsonDatabase, FindsEntry) {
-  StringRef Directory("directory");
+  StringRef Directory("/directory");
   StringRef FileName("file");
   StringRef Command("command");
   std::string JsonDatabase = "[";
   for (int I = 0; I < 10; ++I) {
     if (I > 0) JsonDatabase += ",";
     JsonDatabase +=
       ("{\"directory\":\"" + Directory + Twine(I) + "\"," +
         "\"command\":\"" + Command + Twine(I) + "\","
         "\"file\":\"" + FileName + Twine(I) + "\"}").str();
   }
   JsonDatabase += "]";
   std::string ErrorMessage;
   CompileCommand FoundCommand = findCompileArgsInJsonDatabase(
-    "file4", JsonDatabase, ErrorMessage);
-  EXPECT_EQ("directory4", FoundCommand.Directory) << ErrorMessage;
+    "/directory4/file4", JsonDatabase, ErrorMessage);
+  EXPECT_EQ("/directory4", FoundCommand.Directory) << ErrorMessage;
   ASSERT_EQ(1u, FoundCommand.CommandLine.size()) << ErrorMessage;
   EXPECT_EQ("command4", FoundCommand.CommandLine[0]) << ErrorMessage;
 }
 
 static std::vector<std::string> unescapeJsonCommandLine(StringRef Command) {
   std::string JsonDatabase =
-    ("[{\"directory\":\"\", \"file\":\"test\", \"command\": \"" +
+    ("[{\"directory\":\"/root\", \"file\":\"test\", \"command\": \"" +
      Command + "\"}]").str();
   std::string ErrorMessage;
   CompileCommand FoundCommand = findCompileArgsInJsonDatabase(
-    "test", JsonDatabase, ErrorMessage);
+    "/root/test", JsonDatabase, ErrorMessage);
   EXPECT_TRUE(ErrorMessage.empty()) << ErrorMessage;
   return FoundCommand.CommandLine;
 }
 
 TEST(unescapeJsonCommandLine, ReturnsEmptyArrayOnEmptyString) {
   std::vector<std::string> Result = unescapeJsonCommandLine("");
   EXPECT_TRUE(Result.empty());
 }