Deduplicate replacements by FileEntry instead of file names.

[ioeric]

Summary

The current version does not deduplicate equivalent file paths correctly.
For example, a relative path and an absolute path are considered inequivalent.
Comparing FileEnry addresses these issues.

[alexander-shaposhnikov]

lib/Tooling/Core/Replacement.cpp

578 ↗

(On Diff #76881)

(saves 2 lines of code) (although not particularly important)

if (ProcessedFileEntries.insert(FE).second)
   Result[Entry.first] = std::move(Entry.second);

[ioeric]

• Kill a few lines.

lib/Tooling/Core/Replacement.cpp

578 ↗

(On Diff #76881)

Always nice to save a few lines :) Thanks!

[klimek]

If the files do not exist, how does this work? Won't that potentially give different results if the files exist locally vs if they don't?

[ioeric]

In D26288#586902, @klimek wrote:

If the files do not exist, how does this work? Won't that potentially give different results if the files exist locally vs if they don't?

This would be problematic. Thanks for the catch!

[ioeric]

• Addressed comments: handle non-existing files.

[klimek]

In D26288#586932, @ioeric wrote:

• Addressed comments: handle non-existing files.

We're not really handling them now though? We're just printing an error?

My point is that we might run the replacement generation on a distributed system, and then group/deduplicate/apply them somewhere where the files might not actually exist (think the reduce stage of a mapreduce). If possible, I'd like to not rely on the existence of the file when we deal with Replacements. I'd find it especially problematic if the existence or non-existence of files changes the semantics of those operations.

[ioeric]

In D26288#587513, @klimek wrote:

In D26288#586932, @ioeric wrote:

• Addressed comments: handle non-existing files.

We're not really handling them now though? We're just printing an error?

My point is that we might run the replacement generation on a distributed system, and then group/deduplicate/apply them somewhere where the files might not actually exist (think the reduce stage of a mapreduce). If possible, I'd like to not rely on the existence of the file when we deal with Replacements. I'd find it especially problematic if the existence or non-existence of files changes the semantics of those operations.

This function is only used in replacements application phase, and I think this is the most easiest if not the best way to ensure that two sets of replacements for the same file are applied without needing to handle dots and relative/absolute paths.

For distributed replacements generation, I think it makes more sense to duplications on the replacements application phase since this needs to be done when combining all replacements anyway.

It might make more sense to make this function local in tooling/Refactoring.cpp. But in that case, I can't unit test it :(

[klimek]

Ok, makes sense. Can you add a comment to the function that explains what happens with replacements for files that do not exist (we ignore them, unless I'm mistaken). Otherwise LG.

[ioeric]

• addressed comments.

[ioeric]

Since Manuel's comment has been addressed, I'd like to land this if there is no objection.

[ioeric]

• Merge with origin/master

cfe/trunk/include/clang/Tooling/Core/Replacement.h

 //  all changes must be applied at once at the end of the refactoring so that
 //  the code is always parseable.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_CORE_REPLACEMENT_H
 #define LLVM_CLANG_TOOLING_CORE_REPLACEMENT_H
 
+#include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include <map>
 #include <set>
 #include <string>
 #include <vector>

 ///
 /// \return The new ranges after \p Replaces are applied. The new ranges will be
 /// sorted and non-overlapping.
 std::vector<Range>
 calculateRangesAfterReplacements(const Replacements &Replaces,
                                  const std::vector<Range> &Ranges);
 
 /// \brief If there are multiple <File, Replacements> pairs with the same file
-/// path after removing dots, we only keep one pair (with path after dots being
-/// removed) and discard the rest.
+/// entry, we only keep one pair and discard the rest.
+/// If a file does not exist, its corresponding replacements will be ignored.
 std::map<std::string, Replacements> groupReplacementsByFile(
+    FileManager &FileMgr,
     const std::map<std::string, Replacements> &FileToReplaces);
 
 template <typename Node>
 Replacement::Replacement(const SourceManager &Sources,
                          const Node &NodeToReplace, StringRef ReplacementText,
                          const LangOptions &LangOpts) {
   const CharSourceRange Range =
       CharSourceRange::getTokenRange(NodeToReplace->getSourceRange());
   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
 }
 
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_CORE_REPLACEMENT_H

cfe/trunk/lib/Tooling/Core/Replacement.cpp

 
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticIDs.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Rewrite/Core/Rewriter.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_os_ostream.h"
 
 namespace clang {
 namespace tooling {
 
 static const char * const InvalidLocation = "";
llvm::Expected<std::string> applyAllReplacements(StringRef Code,
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   Rewrite.getEditBuffer(ID).write(OS);
   OS.flush();
   return Result;
 }
 
 std::map<std::string, Replacements> groupReplacementsByFile(
+    FileManager &FileMgr,
     const std::map<std::string, Replacements> &FileToReplaces) {
   std::map<std::string, Replacements> Result;
+  llvm::SmallPtrSet<const FileEntry *, 16> ProcessedFileEntries;
   for (const auto &Entry : FileToReplaces) {
-    llvm::SmallString<256> CleanPath(Entry.first);
-    llvm::sys::path::remove_dots(CleanPath, /*remove_dot_dot=*/true);
-    Result[CleanPath.str()] = std::move(Entry.second);
+    const FileEntry *FE = FileMgr.getFile(Entry.first);
+    if (!FE)
+      llvm::errs() << "File path " << Entry.first << " is invalid.\n";
+    else if (ProcessedFileEntries.insert(FE).second)
+      Result[Entry.first] = std::move(Entry.second);
   }
   return Result;
 }
 
 } // end namespace tooling
 } // end namespace clang

cfe/trunk/lib/Tooling/Refactoring.cpp

if (!applyAllReplacements(Rewrite)) {
     llvm::errs() << "Skipped some replacements.\n";
   }
 
   return saveRewrittenFiles(Rewrite);
 }
 
 bool RefactoringTool::applyAllReplacements(Rewriter &Rewrite) {
   bool Result = true;
-  for (const auto &Entry : groupReplacementsByFile(FileToReplaces))
+  for (const auto &Entry : groupReplacementsByFile(
+           Rewrite.getSourceMgr().getFileManager(), FileToReplaces))
     Result = tooling::applyAllReplacements(Entry.second, Rewrite) && Result;
   return Result;
 }
 
 int RefactoringTool::saveRewrittenFiles(Rewriter &Rewrite) {
   return Rewrite.overwriteChangedFiles() ? 1 : 0;
 }
 
 bool formatAndApplyAllReplacements(
     const std::map<std::string, Replacements> &FileToReplaces, Rewriter &Rewrite,
     StringRef Style) {
   SourceManager &SM = Rewrite.getSourceMgr();
   FileManager &Files = SM.getFileManager();
 
   bool Result = true;
-  for (const auto &FileAndReplaces : groupReplacementsByFile(FileToReplaces)) {
+  for (const auto &FileAndReplaces : groupReplacementsByFile(
+           Rewrite.getSourceMgr().getFileManager(), FileToReplaces)) {
     const std::string &FilePath = FileAndReplaces.first;
     auto &CurReplaces = FileAndReplaces.second;
 
     const FileEntry *Entry = Files.getFile(FilePath);
     FileID ID = SM.getOrCreateFileID(Entry, SrcMgr::C_User);
     StringRef Code = SM.getBufferData(ID);
 
     format::FormatStyle CurStyle = format::getStyle(Style, FilePath, "LLVM");

cfe/trunk/unittests/Tooling/RefactoringTest.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Frontend/TextDiagnosticPrinter.h"
 #include "clang/Rewrite/Core/Rewriter.h"
 #include "clang/Tooling/Refactoring.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/SmallString.h"
mergeAndTestRewrite(
       toReplacements({{"", 0, 1, ""}, {"", 2, 0, "bb"}, {"", 3, 0, "b"}}),
       toReplacements({{"", 0, 2, "cc"}, {"", 2, 3, "dd"}}));
   mergeAndTestRewrite(
       "aa", "babbab", "ccdd",
       toReplacements({{"", 0, 0, "b"}, {"", 1, 0, "bb"}, {"", 2, 0, "b"}}),
       toReplacements({{"", 0, 3, "cc"}, {"", 3, 3, "dd"}}));
 }
 
-TEST(DeduplicateByFileTest, LeaveLeadingDotDot) {
+TEST(DeduplicateByFileTest, PathsWithDots) {
   std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager *FileMgr = new FileManager(FileSystemOptions(), VFS);
 #if !defined(LLVM_ON_WIN32)
-  FileToReplaces["../../a/b/.././c.h"] = Replacements();
-  FileToReplaces["../../a/c.h"] = Replacements();
+  StringRef Path1 = "a/b/.././c.h";
+  StringRef Path2 = "a/c.h";
 #else
-  FileToReplaces["..\\..\\a\\b\\..\\.\\c.h"] = Replacements();
-  FileToReplaces["..\\..\\a\\c.h"] = Replacements();
+  StringRef Path1 = "a\\b\\..\\.\\c.h";
+  StringRef Path2 = "a\\c.h";
 #endif
-  FileToReplaces = groupReplacementsByFile(FileToReplaces);
+  EXPECT_TRUE(VFS->addFile(Path1, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  EXPECT_TRUE(VFS->addFile(Path2, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(*FileMgr, FileToReplaces);
   EXPECT_EQ(1u, FileToReplaces.size());
-#if !defined(LLVM_ON_WIN32)
-  EXPECT_EQ("../../a/c.h", FileToReplaces.begin()->first);
-#else
-  EXPECT_EQ("..\\..\\a\\c.h", FileToReplaces.begin()->first);
-#endif
+  EXPECT_EQ(Path1, FileToReplaces.begin()->first);
 }
 
-TEST(DeduplicateByFileTest, RemoveDotSlash) {
+TEST(DeduplicateByFileTest, PathWithDotSlash) {
   std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager *FileMgr = new FileManager(FileSystemOptions(), VFS);
 #if !defined(LLVM_ON_WIN32)
-  FileToReplaces["./a/b/.././c.h"] = Replacements();
-  FileToReplaces["a/c.h"] = Replacements();
+  StringRef Path1 = "./a/b/c.h";
+  StringRef Path2 = "a/b/c.h";
 #else
-  FileToReplaces[".\\a\\b\\..\\.\\c.h"] = Replacements();
-  FileToReplaces["a\\c.h"] = Replacements();
+  StringRef Path1 = ".\\a\\b\\c.h";
+  StringRef Path2 = "a\\b\\c.h";
 #endif
-  FileToReplaces = groupReplacementsByFile(FileToReplaces);
+  EXPECT_TRUE(VFS->addFile(Path1, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  EXPECT_TRUE(VFS->addFile(Path2, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(*FileMgr, FileToReplaces);
   EXPECT_EQ(1u, FileToReplaces.size());
+  EXPECT_EQ(Path1, FileToReplaces.begin()->first);
+}
+
+TEST(DeduplicateByFileTest, NonExistingFilePath) {
+  std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager *FileMgr = new FileManager(FileSystemOptions(), VFS);
 #if !defined(LLVM_ON_WIN32)
-  EXPECT_EQ("a/c.h", FileToReplaces.begin()->first);
+  StringRef Path1 = "./a/b/c.h";
+  StringRef Path2 = "a/b/c.h";
 #else
-  EXPECT_EQ("a\\c.h", FileToReplaces.begin()->first);
+  StringRef Path1 = ".\\a\\b\\c.h";
+  StringRef Path2 = "a\\b\\c.h";
 #endif
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(*FileMgr, FileToReplaces);
+  EXPECT_TRUE(FileToReplaces.empty());
 }
 
 } // end namespace tooling
 } // end namespace clang