Adding HardLink Support to VirtualFileSystem.

[usaxena95]

Summary

Added support of creating a hardlink from one file to another file.
After a hardlink is added between two files, both file will have the same:

1. UniqueID (inode)
2. Size
3. Buffer

This will bring replay of compilation closer to the actual compilation. There are instances where clang checks for the UniqueID of the file/header to be loaded which leads to a different behavior during replay as all files have different UniqueIDs.

[ilya-biryukov]

Thanks for the change. Having something like this makes total sense.

Mutating existing in-memory nodes looks shaky and requires making Status mutable, which also looks undesirable.
Maybe we could consider adding a new kind of InMemoryNode for hard links that would store the link target? We would have to "resolve" the link on each access, but that would probably allow to avoid changing Status interfaces and get rid of the `UniqueID -> set of files' map. WDYT?

Also some generic comments wrt to the coding style, naming, etc.

include/clang/Basic/VirtualFileSystem.h

80 ↗

(On Diff #162862)

It seems Status was designed to be immutable.
Can we copy or reassign the whole status at the points where we need it?

359 ↗

(On Diff #162862)

Maybe use the common spelling: "hard link"? Otherwise it feels like there is a HardLink class somewhere.

362 ↗

(On Diff #162862)

The links seem to only work for files at this point.
Maybe explicitly document what happens with directories?
Also, maybe document what happens with existing hard links and existing files?

362 ↗

(On Diff #162862)

Maybe s/addHardlink/addHardLink?

468 ↗

(On Diff #162862)

Accidental whitespace change?

lib/Basic/VirtualFileSystem.cpp

516 ↗

(On Diff #162862)

s/buffer/Buffer

645 ↗

(On Diff #162862)

s/to_node/ToNode

unittests/Basic/VirtualFileSystemTest.cpp

1608 ↗

(On Diff #162862)

Accidental whitespace change?

[usaxena95]

Created InMemoryHardLink Class which can handle the resolved InMemoryFile

[usaxena95]

Applied the suggested changes. Added InMemoryHardLink as a subclass of InMemoryNode. Modified the tests accordingly.

[ilya-biryukov]

Could we try removing Status from the base class and move it into InMemoryFile and InMemoryDir?
It shouldn't be too much work and would give safer interfaces for our new hierarchy.

lib/Basic/VirtualFileSystem.cpp

470 ↗

(On Diff #163128)

NIT: maybe use a name that follow the naming style for the other node kinds, i.e. IME_HardLink?

526 ↗

(On Diff #163128)

Can we get away without storing Name? toString() can just say "hard link to " + ResolveNode->toString()

529 ↗

(On Diff #163128)

Why do we need the Stat?
We can get it from ResolveNode if we want to store a copy. Any reason why it would be different?

529 ↗

(On Diff #163128)

ResolveNode can't be null, right? Maybe use a reference instead?
Also, maybe make it const?

535 ↗

(On Diff #163128)

Could we inline getBuffer and getStatus? Having the client code that's explicit about resolving the references seems like a good idea.

639 ↗

(On Diff #163128)

Why not just InMemoryNode*? Null would be the empty hardlink

782 ↗

(On Diff #163128)

NIT: maybe call the variable Link or HardLink?
Since it's not a file.

unittests/Basic/VirtualFileSystemTest.cpp

1054 ↗

(On Diff #163128)

Maybe also add a test that gets into hard links via directory iterators?
To make sure those give the same results as openFileForRead

[usaxena95]

Could we try removing Status from the base class and move it into InMemoryFile and InMemoryDir?

Moved the Stat and getStatus into the subclasses. User of getStatus now calls getStatus of individual subclasses.

lib/Basic/VirtualFileSystem.cpp

526 ↗

(On Diff #163128)

Yeah we can do that. It is just for debug purpose only.

529 ↗

(On Diff #163128)

Changed it to reference. Can't make it const as the there it is involved in methods that are non const (like getResolvedFile returns a pointer, getBuffer is not const)

535 ↗

(On Diff #163128)

Removed these methods. Moved the logic to client code.

[usaxena95]

• Moved Stat to the subclasses of InMemoryNode

[ilya-biryukov]

include/clang/Basic/VirtualFileSystem.h

340 ↗

(On Diff #163330)

• Maybe name it differently, e.g. ResolvedHardLink or HardLinkTarget?
• Maybe document that how this function behaves for non-null vs null values (i.e. creates dirs/files vs links to files)?

359 ↗

(On Diff #163330)

Maybe document that it does nothing for directories?
Also, any reason to not support directories at this point? The limitation seem artificial at this point.

359 ↗

(On Diff #162862)

There are still instances of HardLink. Maybe update them too?

lib/Basic/VirtualFileSystem.cpp

485 ↗

(On Diff #163330)

Maybe store the result of llvm::sys::path::filename() instead of the full name in the first place?

709 ↗

(On Diff #163330)

Why do we need to pass a buffer when creating a hard link?
Maybe just assert it's null?

725 ↗

(On Diff #163330)

Why not pass the buffer unchanged?

811 ↗

(On Diff #163330)

lookupInMemoryNode never returns link nodes, right? Maybe assert the link case is not possible?

846 ↗

(On Diff #163330)

NIT: add else?

848 ↗

(On Diff #163330)

NIT: add else?

529 ↗

(On Diff #163128)

Both methods could be made const, though, right?
It looks like the buffers are always copied when returned from the file system (because the VFS interface returns a unique_ptr<MemoryBuffer>).
getResolvedFile can also return a const node.

unittests/Basic/VirtualFileSystemTest.cpp

701 ↗

(On Diff #163330)

Since gtest only reports one level of locations for the failing assertion, debugging test failures would be hard here (we won't see the actual test locations, the errors will always point into ExpectHardLink function.

We probably want to write a matcher and use EXPECT_THAT, so we can write something like

EXPECT_THAT(File, IsHardLinkTo(LinkTarget))

To write a matcher, we could use the gmock macros:

MATCHER_P(IsHardLinkTo, To, "") {
  llvm::StringRef From = arg;
  llvm::StringRef To = arg;
  // return true when matches, false otherwise
}

[usaxena95]

• Made suggested changes.

[usaxena95]

Made the suggested changes.

include/clang/Basic/VirtualFileSystem.h

359 ↗

(On Diff #163330)

Links to directories cannot be added with the current logic. Resolving paths and iterating directories becomes non trivial. Current implementation supports the use case of "file with multiple names" which is mostly sufficient to mimic the compilation.

lib/Basic/VirtualFileSystem.cpp

529 ↗

(On Diff #163128)

Since a raw pointer to the resolved file is returned by getResolvedNode (used by for lookup) , I have also changed some other raw pointer type to const pointer tpye.

[ilya-biryukov]

Thanks, the interface and implementation look good!
Last drop of nits and suggestions for code simplification.

include/clang/Basic/VirtualFileSystem.h

359 ↗

(On Diff #163330)

You're right. E.g. one potential trouble is cycles in the directory tree.
Let's leave them out, directory links do seem like some hard work and we don't have a use-case for them.

364 ↗

(On Diff #163549)

InMemoryHardLink is a private implementation detail. Maybe remove it from the docs of the public API?

369 ↗

(On Diff #163549)

Maybe expand a little on what a "hard link" is in our implementation?
Specifically, the important bits seem to be:

They are not intended to be fully equivalent to hard links of the classical filesystems, despite the name.
Both the original file and a hard link have the same UniqueID returned in their stats, share the same buffer, etc.
There is no way to distinguish hard links and the original files after they were added.
(this is already in the docs) Only links to files are supported, directories cannot be linked.

370 ↗

(On Diff #163549)

Maybe remove these defaulted parameters? They're not used and we'll probably have confusing semantics even if we add support for them (since our hard links don't have their own status, and merely return the status of the original file).
WDYT?

lib/Basic/VirtualFileSystem.cpp

476 ↗

(On Diff #163549)

Please use std::string, we usually don't leave out the std:: namespace in LLVM.

523 ↗

(On Diff #163549)

Maybe return a reference here too? To indicate this can't be null.

653 ↗

(On Diff #163549)

HardLinkTarget can only be InMemoryFile, so maybe change the type of the parameter to const InMemoryFile*?
Clients will be responsible for making sure the target is actually a file, but that seems fine, they already have to resolve the path to the target file.

665 ↗

(On Diff #163549)

We don't use Status for links, maybe move creation of Status into the branch that handles files?
This would allow to assert Buffer is not null too

690 ↗

(On Diff #163549)

Oh, wow, this used to set the size of the created parent directories to the size of the buffer we're creating. I guess nobody looks at it anyway, so we were never hitting any problems because of this.
Good catch, thanks for fixing this.

803 ↗

(On Diff #163549)

NIT: maybe invert condition?
I.e. change to

if (!Node)
  return Node.getError();
//.. rest of the code

to keep the amount of code with higher nesting small. See somewhat related section in LLVM Style Guide

804 ↗

(On Diff #163549)

This line seems to have wrong indent.
Running git-clang-format before submitting the code is a convenient way to fix this.

809 ↗

(On Diff #163549)

NIT: add llvm_unreachable() to make it clear we don't have a 4th kind of node?

841 ↗

(On Diff #163549)

Maybe extract it into a small helper function?

It only pops up twice, but a helper should still give better readability for both cases.

unittests/Basic/VirtualFileSystemTest.cpp

702 ↗

(On Diff #163549)

s/IsHardLinktTo/IsHardLinkTo

705 ↗

(On Diff #163549)

This matcher is pretty complicated and tests multiple things.
If it fails, it might be hard to track down what exactly went wrong.

Given the name, it seems reasonable for it to simply test that both paths point to the same unique-id.
We don't have to test every other invariant (sizes are the same, buffers are the same) on all the links we create, one test assertion per invariant should be enough (sizes are the same, buffers are the same, etc)

[usaxena95]

Applied suggested changes.

lib/Basic/VirtualFileSystem.cpp

653 ↗

(On Diff #163549)

Moved InMemoryFile from detail:<anonymous> namespace to detail namespace in order to be visible in VirtualFileSystem.h

unittests/Basic/VirtualFileSystemTest.cpp

705 ↗

(On Diff #163549)

Removed the check for Buffer and size from the matcher. Added the test for size and buffer in the smaller AddHardLinkTest

[usaxena95]

• applied suggested changes

[usaxena95]

• Moved helper function into anonymous namespace

[ilya-biryukov]

lib/Basic/VirtualFileSystem.cpp

478 ↗

(On Diff #163720)

NIT: accept a parameter of type llvm::StringRef instead of const std::string&.

495 ↗

(On Diff #163720)

NIT: .str() is redundant (in fact, a pessimization) if parameter of InMemoryNode is a StringRef.

522 ↗

(On Diff #163720)

NIT: as noted in the other comment, .str() can be removed if parameter type is changed.

570 ↗

(On Diff #163720)

NIT: .str() can be removed

662 ↗

(On Diff #163720)

The comment looks outdated

663 ↗

(On Diff #163720)

Shouldn't we assert this instead? This is not an invalid input, this is actually breaking our program logic, right? I.e. one shouldn't call addFile with HardLinkTarget set and non-null buffer

677 ↗

(On Diff #163720)

NIT: .str() seems redundant

804 ↗

(On Diff #163720)

NIT: use llvm::cast<InMemoryFile> instead of static_cast.
It's essentially equivalent with added asserts.

unittests/Basic/VirtualFileSystemTest.cpp

974 ↗

(On Diff #163720)

Please use StringRefs everywhere. Twine should only be generally only be used as temporary objects, see the specific guidelines in Twine's docs.
Whenever a reference to an existing string is needed, a StringRef is the best choice.
If you need to create new strings (e.g. concatenation, etc.), use std::string.

976 ↗

(On Diff #163720)

s/content/Content

987 ↗

(On Diff #163720)

s/link0/Link0
.... and other lowerCamelCase vars --> UpperCamelCase

1090 ↗

(On Diff #163720)

This seems equivalent to EXPECT_THAT(Nodes, UnorderedElementsAre("/a", "/a/b", "/c", "/c/d"). Maybe simplify?

Note that iterators might give different file separators on windows. You might want to normalize, e.g. with llvm::sys::path::native(..., Style::posix).
And still watch out for windows buildbot failures, in case the root (/) is interpreted differently on Windows, possibly giving different results.

[usaxena95]

• applied changes

[usaxena95]

Applied the changes suggested.

lib/Basic/VirtualFileSystem.cpp

677 ↗

(On Diff #163720)

Here P is a Twine here which cannot be converted to StringRef

[ilya-biryukov]

Thanks! LGTM with a last drop of NITs.
Do you already have commit access or do you want me to submit this change for you?

include/clang/Basic/VirtualFileSystem.h

369 ↗

(On Diff #163739)

NIT: since From should not exist, a comment that it shouldn't be a directory is redundant.

lib/Basic/VirtualFileSystem.cpp

677 ↗

(On Diff #163720)

You're right. Sorry for the confusion.

485 ↗

(On Diff #163739)

NIT: .data() is redundant (in fact, a pessimization, since StringRef ctor will have to compute the length of the string), string can be implicitly converted to StringRef

613 ↗

(On Diff #163739)

NIT: else can be removed, same at the next statement. See the style guide

663 ↗

(On Diff #163739)

NIT: maybe put comment into an assertion message?
E.g. assert(!(HardLinkTarget && Buffer) && "HardLink cannot have a buffer")

673 ↗

(On Diff #163739)

NIT: end a comment with a full stop

unittests/Basic/VirtualFileSystemTest.cpp

708 ↗

(On Diff #163739)

This is effectively a double negation, which is a bit hard to read.
Maybe replace !(a || b != c) to !a && b == c to avoid it?

[usaxena95]

• fixed the style issues

[usaxena95]

I don't have commit access. Can you please submit this ?

[ilya-biryukov]

In D51359#1222823, @usaxena95 wrote:

I don't have commit access. Can you please submit this ?

Will do.

[ilya-biryukov]

Submitted. Thanks for the change!

cfe/trunk/include/clang/Basic/VirtualFileSystem.h

public:
   /// system.
   iterator overlays_end() { return FSList.rend(); }
   const_iterator overlays_end() const { return FSList.rend(); }
 };
 
 namespace detail {
 
 class InMemoryDirectory;
+class InMemoryFile;
 
 } // namespace detail
 
 /// An in-memory file system.
 class InMemoryFileSystem : public FileSystem {
   std::unique_ptr<detail::InMemoryDirectory> Root;
   std::string WorkingDirectory;
   bool UseNormalizedPaths = true;
 
+  /// If HardLinkTarget is non-null, a hardlink is created to the To path which
+  /// must be a file. If it is null then it adds the file as the public addFile.
+  bool addFile(const Twine &Path, time_t ModificationTime,
+               std::unique_ptr<llvm::MemoryBuffer> Buffer,
+               Optional<uint32_t> User, Optional<uint32_t> Group,
+               Optional<llvm::sys::fs::file_type> Type,
+               Optional<llvm::sys::fs::perms> Perms,
+               const detail::InMemoryFile *HardLinkTarget);
+
 public:
   explicit InMemoryFileSystem(bool UseNormalizedPaths = true);
   ~InMemoryFileSystem() override;
 
   /// Add a file containing a buffer or a directory to the VFS with a
   /// path. The VFS owns the buffer.  If present, User, Group, Type
   /// and Perms apply to the newly-created file or directory.
   /// \return true if the file or directory was successfully added,
   /// false if the file or directory already exists in the file system with
   /// different contents.
   bool addFile(const Twine &Path, time_t ModificationTime,
                std::unique_ptr<llvm::MemoryBuffer> Buffer,
                Optional<uint32_t> User = None, Optional<uint32_t> Group = None,
                Optional<llvm::sys::fs::file_type> Type = None,
                Optional<llvm::sys::fs::perms> Perms = None);
 
+  /// Add a hard link to a file.
+  /// Here hard links are not intended to be fully equivalent to the classical
+  /// filesystem. Both the hard link and the file share the same buffer and
+  /// status (and thus have the same UniqueID). Because of this there is no way
+  /// to distinguish between the link and the file after the link has been
+  /// added.
+  ///
+  /// The To path must be an existing file or a hardlink. The From file must not
+  /// have been added before. The To Path must not be a directory. The From Node
+  /// is added as a hard link which points to the resolved file of To Node.
+  /// \return true if the above condition is satisfied and hardlink was
+  /// successfully created, false otherwise.
+  bool addHardLink(const Twine &From, const Twine &To);
+
   /// Add a buffer to the VFS with a path. The VFS does not own the buffer.
   /// If present, User, Group, Type and Perms apply to the newly-created file
   /// or directory.
   /// \return true if the file or directory was successfully added,
   /// false if the file or directory already exists in the file system with
   /// different contents.
   bool addFileNoOwn(const Twine &Path, time_t ModificationTime,
                     llvm::MemoryBuffer *Buffer,

cfe/trunk/lib/Basic/VirtualFileSystem.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/llvm-config.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Chrono.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
return directory_iterator(
       std::make_shared<OverlayFSDirIterImpl>(Dir, *this, EC));
 }
 
 namespace clang {
 namespace vfs {
 
 namespace detail {
 
-enum InMemoryNodeKind { IME_File, IME_Directory };
+enum InMemoryNodeKind { IME_File, IME_Directory, IME_HardLink };
 
 /// The in memory file system is a tree of Nodes. Every node can either be a
-/// file or a directory.
+/// file , hardlink or a directory.
 class InMemoryNode {
-  Status Stat;
   InMemoryNodeKind Kind;
-
-protected:
-  /// Return Stat.  This should only be used for internal/debugging use.  When
-  /// clients wants the Status of this node, they should use
-  /// \p getStatus(StringRef).
-  const Status &getStatus() const { return Stat; }
+  std::string FileName;
 
 public:
-  InMemoryNode(Status Stat, InMemoryNodeKind Kind)
-      : Stat(std::move(Stat)), Kind(Kind) {}
+  InMemoryNode(llvm::StringRef FileName, InMemoryNodeKind Kind)
+      : Kind(Kind), FileName(llvm::sys::path::filename(FileName)) {}
   virtual ~InMemoryNode() = default;
 
+  /// Get the filename of this node (the name without the directory part).
+  StringRef getFileName() const { return FileName; }
+  InMemoryNodeKind getKind() const { return Kind; }
+  virtual std::string toString(unsigned Indent) const = 0;
+};
+
+class InMemoryFile : public InMemoryNode {
+  Status Stat;
+  std::unique_ptr<llvm::MemoryBuffer> Buffer;
+
+public:
+  InMemoryFile(Status Stat, std::unique_ptr<llvm::MemoryBuffer> Buffer)
+      : InMemoryNode(Stat.getName(), IME_File), Stat(std::move(Stat)),
+        Buffer(std::move(Buffer)) {}
+
   /// Return the \p Status for this node. \p RequestedName should be the name
   /// through which the caller referred to this node. It will override
   /// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
   Status getStatus(StringRef RequestedName) const {
     return Status::copyWithNewName(Stat, RequestedName);
   }
+  llvm::MemoryBuffer *getBuffer() const { return Buffer.get(); }
 
-  /// Get the filename of this node (the name without the directory part).
-  StringRef getFileName() const {
-    return llvm::sys::path::filename(Stat.getName());
+  std::string toString(unsigned Indent) const override {
+    return (std::string(Indent, ' ') + Stat.getName() + "\n").str();
+  }
+
+  static bool classof(const InMemoryNode *N) {
+    return N->getKind() == IME_File;
   }
-  InMemoryNodeKind getKind() const { return Kind; }
-  virtual std::string toString(unsigned Indent) const = 0;
 };
 
 namespace {
 
-class InMemoryFile : public InMemoryNode {
-  std::unique_ptr<llvm::MemoryBuffer> Buffer;
+class InMemoryHardLink : public InMemoryNode {
+  const InMemoryFile &ResolvedFile;
 
 public:
-  InMemoryFile(Status Stat, std::unique_ptr<llvm::MemoryBuffer> Buffer)
-      : InMemoryNode(std::move(Stat), IME_File), Buffer(std::move(Buffer)) {}
-
-  llvm::MemoryBuffer *getBuffer() { return Buffer.get(); }
+  InMemoryHardLink(StringRef Path, const InMemoryFile &ResolvedFile)
+      : InMemoryNode(Path, IME_HardLink), ResolvedFile(ResolvedFile) {}
+  const InMemoryFile &getResolvedFile() const { return ResolvedFile; }
 
   std::string toString(unsigned Indent) const override {
-    return (std::string(Indent, ' ') + getStatus().getName() + "\n").str();
+    return std::string(Indent, ' ') + "HardLink to -> " +
+           ResolvedFile.toString(0);
   }
 
   static bool classof(const InMemoryNode *N) {
-    return N->getKind() == IME_File;
+    return N->getKind() == IME_HardLink;
   }
 };
 
 /// Adapt a InMemoryFile for VFS' File interface.  The goal is to make
 /// \p InMemoryFileAdaptor mimic as much as possible the behavior of
 /// \p RealFile.
 class InMemoryFileAdaptor : public File {
-  InMemoryFile &Node;
+  const InMemoryFile &Node;
   /// The name to use when returning a Status for this file.
   std::string RequestedName;
 
 public:
-  explicit InMemoryFileAdaptor(InMemoryFile &Node, std::string RequestedName)
+  explicit InMemoryFileAdaptor(const InMemoryFile &Node,
+                               std::string RequestedName)
       : Node(Node), RequestedName(std::move(RequestedName)) {}
 
   llvm::ErrorOr<Status> status() override {
     return Node.getStatus(RequestedName);
   }
 
   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
   getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
             bool IsVolatile) override {
     llvm::MemoryBuffer *Buf = Node.getBuffer();
     return llvm::MemoryBuffer::getMemBuffer(
         Buf->getBuffer(), Buf->getBufferIdentifier(), RequiresNullTerminator);
   }
 
   std::error_code close() override { return {}; }
 };
-
 } // namespace
 
 class InMemoryDirectory : public InMemoryNode {
+  Status Stat;
   std::map<std::string, std::unique_ptr<InMemoryNode>> Entries;
 
 public:
   InMemoryDirectory(Status Stat)
-      : InMemoryNode(std::move(Stat), IME_Directory) {}
+      : InMemoryNode(Stat.getName(), IME_Directory), Stat(std::move(Stat)) {}
 
+  /// Return the \p Status for this node. \p RequestedName should be the name
+  /// through which the caller referred to this node. It will override
+  /// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
+  Status getStatus(StringRef RequestedName) const {
+    return Status::copyWithNewName(Stat, RequestedName);
+  }
   InMemoryNode *getChild(StringRef Name) {
     auto I = Entries.find(Name);
     if (I != Entries.end())
       return I->second.get();
     return nullptr;
   }
 
   InMemoryNode *addChild(StringRef Name, std::unique_ptr<InMemoryNode> Child) {
     return Entries.insert(make_pair(Name, std::move(Child)))
         .first->second.get();
   }
 
   using const_iterator = decltype(Entries)::const_iterator;
 
   const_iterator begin() const { return Entries.begin(); }
   const_iterator end() const { return Entries.end(); }
 
   std::string toString(unsigned Indent) const override {
     std::string Result =
-        (std::string(Indent, ' ') + getStatus().getName() + "\n").str();
+        (std::string(Indent, ' ') + Stat.getName() + "\n").str();
     for (const auto &Entry : Entries)
       Result += Entry.second->toString(Indent + 2);
     return Result;
   }
 
   static bool classof(const InMemoryNode *N) {
     return N->getKind() == IME_Directory;
   }
 };
 
+namespace {
+Status getNodeStatus(const InMemoryNode *Node, StringRef RequestedName) {
+  if (auto Dir = dyn_cast<detail::InMemoryDirectory>(Node))
+    return Dir->getStatus(RequestedName);
+  if (auto File = dyn_cast<detail::InMemoryFile>(Node))
+    return File->getStatus(RequestedName);
+  if (auto Link = dyn_cast<detail::InMemoryHardLink>(Node))
+    return Link->getResolvedFile().getStatus(RequestedName);
+  llvm_unreachable("Unknown node type");
+}
+} // namespace
 } // namespace detail
 
 InMemoryFileSystem::InMemoryFileSystem(bool UseNormalizedPaths)
     : Root(new detail::InMemoryDirectory(
           Status("", getNextVirtualUniqueID(), llvm::sys::TimePoint<>(), 0, 0,
                  0, llvm::sys::fs::file_type::directory_file,
                  llvm::sys::fs::perms::all_all))),
       UseNormalizedPaths(UseNormalizedPaths) {}
 
 InMemoryFileSystem::~InMemoryFileSystem() = default;
 
 std::string InMemoryFileSystem::toString() const {
   return Root->toString(/*Indent=*/0);
 }
 
 bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
                                  std::unique_ptr<llvm::MemoryBuffer> Buffer,
                                  Optional<uint32_t> User,
                                  Optional<uint32_t> Group,
                                  Optional<llvm::sys::fs::file_type> Type,
-                                 Optional<llvm::sys::fs::perms> Perms) {
+                                 Optional<llvm::sys::fs::perms> Perms,
+                                 const detail::InMemoryFile *HardLinkTarget) {
   SmallString<128> Path;
   P.toVector(Path);
 
   // Fix up relative paths. This just prepends the current working directory.
   std::error_code EC = makeAbsolute(Path);
   assert(!EC);
   (void)EC;
 
   if (useNormalizedPaths())
     llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
 
   if (Path.empty())
     return false;
 
   detail::InMemoryDirectory *Dir = Root.get();
   auto I = llvm::sys::path::begin(Path), E = sys::path::end(Path);
   const auto ResolvedUser = User.getValueOr(0);
   const auto ResolvedGroup = Group.getValueOr(0);
   const auto ResolvedType = Type.getValueOr(sys::fs::file_type::regular_file);
   const auto ResolvedPerms = Perms.getValueOr(sys::fs::all_all);
+  assert(!(HardLinkTarget && Buffer) && "HardLink cannot have a buffer");
   // Any intermediate directories we create should be accessible by
   // the owner, even if Perms says otherwise for the final path.
   const auto NewDirectoryPerms = ResolvedPerms | sys::fs::owner_all;
   while (true) {
     StringRef Name = *I;
     detail::InMemoryNode *Node = Dir->getChild(Name);
     ++I;
     if (!Node) {
       if (I == E) {
-        // End of the path, create a new file or directory.
+        // End of the path.
+        std::unique_ptr<detail::InMemoryNode> Child;
+        if (HardLinkTarget)
+          Child.reset(new detail::InMemoryHardLink(P.str(), *HardLinkTarget));
+        else {
+          // Create a new file or directory.
           Status Stat(P.str(), getNextVirtualUniqueID(),
                       llvm::sys::toTimePoint(ModificationTime), ResolvedUser,
                       ResolvedGroup, Buffer->getBufferSize(), ResolvedType,
                       ResolvedPerms);
-        std::unique_ptr<detail::InMemoryNode> Child;
           if (ResolvedType == sys::fs::file_type::directory_file) {
             Child.reset(new detail::InMemoryDirectory(std::move(Stat)));
           } else {
-          Child.reset(new detail::InMemoryFile(std::move(Stat),
-                                               std::move(Buffer)));
+            Child.reset(
+                new detail::InMemoryFile(std::move(Stat), std::move(Buffer)));
+          }
         }
         Dir->addChild(Name, std::move(Child));
         return true;
       }
 
       // Create a new directory. Use the path up to here.
       Status Stat(
           StringRef(Path.str().begin(), Name.end() - Path.str().begin()),
           getNextVirtualUniqueID(), llvm::sys::toTimePoint(ModificationTime),
-          ResolvedUser, ResolvedGroup, Buffer->getBufferSize(),
-          sys::fs::file_type::directory_file, NewDirectoryPerms);
+          ResolvedUser, ResolvedGroup, 0, sys::fs::file_type::directory_file,
+          NewDirectoryPerms);
       Dir = cast<detail::InMemoryDirectory>(Dir->addChild(
           Name, llvm::make_unique<detail::InMemoryDirectory>(std::move(Stat))));
       continue;
     }
 
     if (auto *NewDir = dyn_cast<detail::InMemoryDirectory>(Node)) {
       Dir = NewDir;
     } else {
-      assert(isa<detail::InMemoryFile>(Node) &&
-             "Must be either file or directory!");
+      assert((isa<detail::InMemoryFile>(Node) ||
+              isa<detail::InMemoryHardLink>(Node)) &&
+             "Must be either file, hardlink or directory!");
 
       // Trying to insert a directory in place of a file.
       if (I != E)
         return false;
 
       // Return false only if the new file is different from the existing one.
+      if (auto Link = dyn_cast<detail::InMemoryHardLink>(Node)) {
+        return Link->getResolvedFile().getBuffer()->getBuffer() ==
+               Buffer->getBuffer();
+      }
       return cast<detail::InMemoryFile>(Node)->getBuffer()->getBuffer() ==
              Buffer->getBuffer();
     }
   }
 }
 
+bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
+                                 std::unique_ptr<llvm::MemoryBuffer> Buffer,
+                                 Optional<uint32_t> User,
+                                 Optional<uint32_t> Group,
+                                 Optional<llvm::sys::fs::file_type> Type,
+                                 Optional<llvm::sys::fs::perms> Perms) {
+  return addFile(P, ModificationTime, std::move(Buffer), User, Group, Type,
+                 Perms, /*HardLinkTarget=*/nullptr);
+}
+
 bool InMemoryFileSystem::addFileNoOwn(const Twine &P, time_t ModificationTime,
                                       llvm::MemoryBuffer *Buffer,
                                       Optional<uint32_t> User,
                                       Optional<uint32_t> Group,
                                       Optional<llvm::sys::fs::file_type> Type,
                                       Optional<llvm::sys::fs::perms> Perms) {
   return addFile(P, ModificationTime,
                  llvm::MemoryBuffer::getMemBuffer(
                      Buffer->getBuffer(), Buffer->getBufferIdentifier()),
                  std::move(User), std::move(Group), std::move(Type),
                  std::move(Perms));
 }
 
-static ErrorOr<detail::InMemoryNode *>
+static ErrorOr<const detail::InMemoryNode *>
 lookupInMemoryNode(const InMemoryFileSystem &FS, detail::InMemoryDirectory *Dir,
                    const Twine &P) {
   SmallString<128> Path;
   P.toVector(Path);
 
   // Fix up relative paths. This just prepends the current working directory.
   std::error_code EC = FS.makeAbsolute(Path);
   assert(!EC);
while (true) {
 
     // Return the file if it's at the end of the path.
     if (auto File = dyn_cast<detail::InMemoryFile>(Node)) {
       if (I == E)
         return File;
       return errc::no_such_file_or_directory;
     }
 
+    // If Node is HardLink then return the resolved file.
+    if (auto File = dyn_cast<detail::InMemoryHardLink>(Node)) {
+      if (I == E)
+        return &File->getResolvedFile();
+      return errc::no_such_file_or_directory;
+    }
     // Traverse directories.
     Dir = cast<detail::InMemoryDirectory>(Node);
     if (I == E)
       return Dir;
   }
 }
 
+bool InMemoryFileSystem::addHardLink(const Twine &FromPath,
+                                     const Twine &ToPath) {
+  auto FromNode = lookupInMemoryNode(*this, Root.get(), FromPath);
+  auto ToNode = lookupInMemoryNode(*this, Root.get(), ToPath);
+  // FromPath must not have been added before. ToPath must have been added
+  // before. Resolved ToPath must be a File.
+  if (!ToNode || FromNode || !isa<detail::InMemoryFile>(*ToNode))
+    return false;
+  return this->addFile(FromPath, 0, nullptr, None, None, None, None,
+                       cast<detail::InMemoryFile>(*ToNode));
+}
+
 llvm::ErrorOr<Status> InMemoryFileSystem::status(const Twine &Path) {
   auto Node = lookupInMemoryNode(*this, Root.get(), Path);
   if (Node)
-    return (*Node)->getStatus(Path.str());
+    return detail::getNodeStatus(*Node, Path.str());
   return Node.getError();
 }
 
 llvm::ErrorOr<std::unique_ptr<File>>
 InMemoryFileSystem::openFileForRead(const Twine &Path) {
   auto Node = lookupInMemoryNode(*this, Root.get(), Path);
   if (!Node)
     return Node.getError();
class InMemoryDirIterator : public clang::vfs::detail::DirIterImpl {
   detail::InMemoryDirectory::const_iterator I;
   detail::InMemoryDirectory::const_iterator E;
   std::string RequestedDirName;
 
   void setCurrentEntry() {
     if (I != E) {
       SmallString<256> Path(RequestedDirName);
       llvm::sys::path::append(Path, I->second->getFileName());
-      CurrentEntry = I->second->getStatus(Path);
+      CurrentEntry = detail::getNodeStatus(I->second.get(), Path);
     } else {
       // When we're at the end, make CurrentEntry invalid and DirIterImpl will
       // do the rest.
       CurrentEntry = Status();
     }
   }
 
 public:
   InMemoryDirIterator() = default;
 
-  explicit InMemoryDirIterator(detail::InMemoryDirectory &Dir,
+  explicit InMemoryDirIterator(const detail::InMemoryDirectory &Dir,
                                std::string RequestedDirName)
       : I(Dir.begin()), E(Dir.end()),
         RequestedDirName(std::move(RequestedDirName)) {
     setCurrentEntry();
   }
 
   std::error_code increment() override {
     ++I;

cfe/trunk/unittests/Basic/VirtualFileSystemTest.cpp

 #include "clang/Basic/VirtualFileSystem.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SourceMgr.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <map>
+#include <string>
 
 using namespace clang;
 using namespace llvm;
 using llvm::sys::fs::UniqueID;
 
 namespace {
 struct DummyFile : public vfs::File {
   vfs::Status S;
protected:
   clang::vfs::InMemoryFileSystem FS;
   clang::vfs::InMemoryFileSystem NormalizedFS;
 
   InMemoryFileSystemTest()
       : FS(/*UseNormalizedPaths=*/false),
         NormalizedFS(/*UseNormalizedPaths=*/true) {}
 };
 
+MATCHER_P2(IsHardLinkTo, FS, Target, "") {
+  StringRef From = arg;
+  StringRef To = Target;
+  auto OpenedFrom = FS->openFileForRead(From);
+  auto OpenedTo = FS->openFileForRead(To);
+  return !OpenedFrom.getError() && !OpenedTo.getError() &&
+         (*OpenedFrom)->status()->getUniqueID() ==
+             (*OpenedTo)->status()->getUniqueID();
+}
+
 TEST_F(InMemoryFileSystemTest, IsEmpty) {
   auto Stat = FS.status("/a");
   ASSERT_EQ(Stat.getError(),errc::no_such_file_or_directory) << FS.toString();
   Stat = FS.status("/");
   ASSERT_EQ(Stat.getError(), errc::no_such_file_or_directory) << FS.toString();
 }
 
 TEST_F(InMemoryFileSystemTest, WindowsPath) {
TEST_F(InMemoryFileSystemTest, StatusName) {
   // Access using a directory iterator.
   std::error_code EC;
   clang::vfs::directory_iterator It = NormalizedFS.dir_begin("../b", EC);
   // When on Windows, we end up with "../b\\c" as the name.  Convert to Posix
   // path for the sake of the comparison.
   ASSERT_EQ("../b/c", getPosixPath(It->getName()));
 }
 
+TEST_F(InMemoryFileSystemTest, AddHardLinkToFile) {
+  StringRef FromLink = "/path/to/FROM/link";
+  StringRef Target = "/path/to/TO/file";
+  FS.addFile(Target, 0, MemoryBuffer::getMemBuffer("content of target"));
+  EXPECT_TRUE(FS.addHardLink(FromLink, Target));
+  EXPECT_THAT(FromLink, IsHardLinkTo(&FS, Target));
+  EXPECT_TRUE(FS.status(FromLink)->getSize() == FS.status(Target)->getSize());
+  EXPECT_TRUE(FS.getBufferForFile(FromLink)->get()->getBuffer() ==
+              FS.getBufferForFile(Target)->get()->getBuffer());
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkInChainPattern) {
+  StringRef Link0 = "/path/to/0/link";
+  StringRef Link1 = "/path/to/1/link";
+  StringRef Link2 = "/path/to/2/link";
+  StringRef Target = "/path/to/target";
+  FS.addFile(Target, 0, MemoryBuffer::getMemBuffer("content of target file"));
+  EXPECT_TRUE(FS.addHardLink(Link2, Target));
+  EXPECT_TRUE(FS.addHardLink(Link1, Link2));
+  EXPECT_TRUE(FS.addHardLink(Link0, Link1));
+  EXPECT_THAT(Link0, IsHardLinkTo(&FS, Target));
+  EXPECT_THAT(Link1, IsHardLinkTo(&FS, Target));
+  EXPECT_THAT(Link2, IsHardLinkTo(&FS, Target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkToAFileThatWasNotAddedBefore) {
+  EXPECT_FALSE(FS.addHardLink("/path/to/link", "/path/to/target"));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkFromAFileThatWasAddedBefore) {
+  StringRef Link = "/path/to/link";
+  StringRef Target = "/path/to/target";
+  FS.addFile(Target, 0, MemoryBuffer::getMemBuffer("content of target"));
+  FS.addFile(Link, 0, MemoryBuffer::getMemBuffer("content of link"));
+  EXPECT_FALSE(FS.addHardLink(Link, Target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddSameHardLinkMoreThanOnce) {
+  StringRef Link = "/path/to/link";
+  StringRef Target = "/path/to/target";
+  FS.addFile(Target, 0, MemoryBuffer::getMemBuffer("content of target"));
+  EXPECT_TRUE(FS.addHardLink(Link, Target));
+  EXPECT_FALSE(FS.addHardLink(Link, Target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddFileInPlaceOfAHardLinkWithSameContent) {
+  StringRef Link = "/path/to/link";
+  StringRef Target = "/path/to/target";
+  StringRef Content = "content of target";
+  EXPECT_TRUE(FS.addFile(Target, 0, MemoryBuffer::getMemBuffer(Content)));
+  EXPECT_TRUE(FS.addHardLink(Link, Target));
+  EXPECT_TRUE(FS.addFile(Link, 0, MemoryBuffer::getMemBuffer(Content)));
+}
+
+TEST_F(InMemoryFileSystemTest, AddFileInPlaceOfAHardLinkWithDifferentContent) {
+  StringRef Link = "/path/to/link";
+  StringRef Target = "/path/to/target";
+  StringRef Content = "content of target";
+  StringRef LinkContent = "different content of link";
+  EXPECT_TRUE(FS.addFile(Target, 0, MemoryBuffer::getMemBuffer(Content)));
+  EXPECT_TRUE(FS.addHardLink(Link, Target));
+  EXPECT_FALSE(FS.addFile(Link, 0, MemoryBuffer::getMemBuffer(LinkContent)));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkToADirectory) {
+  StringRef Dir = "path/to/dummy/dir";
+  StringRef Link = "/path/to/link";
+  StringRef File = "path/to/dummy/dir/target";
+  StringRef Content = "content of target";
+  EXPECT_TRUE(FS.addFile(File, 0, MemoryBuffer::getMemBuffer(Content)));
+  EXPECT_FALSE(FS.addHardLink(Link, Dir));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkFromADirectory) {
+  StringRef Dir = "path/to/dummy/dir";
+  StringRef Target = "path/to/dummy/dir/target";
+  StringRef Content = "content of target";
+  EXPECT_TRUE(FS.addFile(Target, 0, MemoryBuffer::getMemBuffer(Content)));
+  EXPECT_FALSE(FS.addHardLink(Dir, Target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkUnderAFile) {
+  StringRef CommonContent = "content string";
+  FS.addFile("/a/b", 0, MemoryBuffer::getMemBuffer(CommonContent));
+  FS.addFile("/c/d", 0, MemoryBuffer::getMemBuffer(CommonContent));
+  EXPECT_FALSE(FS.addHardLink("/c/d/e", "/a/b"));
+}
+
+TEST_F(InMemoryFileSystemTest, RecursiveIterationWithHardLink) {
+  std::error_code EC;
+  FS.addFile("/a/b", 0, MemoryBuffer::getMemBuffer("content string"));
+  EXPECT_TRUE(FS.addHardLink("/c/d", "/a/b"));
+  auto I = vfs::recursive_directory_iterator(FS, "/", EC);
+  ASSERT_FALSE(EC);
+  std::vector<std::string> Nodes;
+  for (auto E = vfs::recursive_directory_iterator(); !EC && I != E;
+       I.increment(EC)) {
+    Nodes.push_back(getPosixPath(I->getName()));
+  }
+  EXPECT_THAT(Nodes, testing::UnorderedElementsAre("/a", "/a/b", "/c", "/c/d"));
+}
+
 // NOTE: in the tests below, we use '//root/' as our root directory, since it is
 // a legal *absolute* path on Windows as well as *nix.
 class VFSFromYAMLTest : public ::testing::Test {
 public:
   int NumDiagnostics;
 
   void SetUp() override { NumDiagnostics = 0; }