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

78

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

358

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

361

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?

361

Maybe s/addHardlink/addHardLink?

473

Accidental whitespace change?

lib/Basic/VirtualFileSystem.cpp

502

s/buffer/Buffer

656

s/to_node/ToNode

unittests/Basic/VirtualFileSystemTest.cpp

1640

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

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

521

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

524

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?

524

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

530

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

632

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

775

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

unittests/Basic/VirtualFileSystemTest.cpp

1054

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

521

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

524

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)

530

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

• 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)?

358

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

359

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.

lib/Basic/VirtualFileSystem.cpp

485

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

524

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.

709

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

725

Why not pass the buffer unchanged?

811

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

846

NIT: add else?

848

NIT: add else?

unittests/Basic/VirtualFileSystemTest.cpp

701

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

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

524

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

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.

361

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

366

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.

367

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

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

525

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

654

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.

666

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

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.

805–812

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

806

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

811

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

844–849

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

717

s/IsHardLinktTo/IsHardLinkTo

720

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

654

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

unittests/Basic/VirtualFileSystemTest.cpp

720

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

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

482

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

509

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

572–573

NIT: .str() can be removed

653

The comment looks outdated

654

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

675

NIT: .str() seems redundant

796

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

unittests/Basic/VirtualFileSystemTest.cpp

979

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.

981

s/content/Content

992

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

1095

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

675

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

366

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

lib/Basic/VirtualFileSystem.cpp

484

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

615

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

654

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

669

NIT: end a comment with a full stop

675

You're right. Sorry for the confusion.

unittests/Basic/VirtualFileSystemTest.cpp

723

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!

include/clang/Basic/VirtualFileSystem.h

public:
   /// Get a copy of a Status with a different name.
   static Status copyWithNewName(const Status &In, StringRef NewName);
   static Status copyWithNewName(const llvm::sys::fs::file_status &In,
                                 StringRef NewName);
 
   /// Returns the name that should be used for this file or directory.
   StringRef getName() const { return Name; }
 
   /// @name Status interface from llvm::sys::fs
   /// @{
   llvm::sys::fs::file_type getType() const { return Type; }
   llvm::sys::fs::perms getPermissions() const { return Perms; }
   llvm::sys::TimePoint<> getLastModificationTime() const { return MTime; }
   llvm::sys::fs::UniqueID getUniqueID() const { return UID; }
   uint32_t getUser() const { return User; }
   uint32_t getGroup() const { return Group; }
   uint64_t getSize() const { return Size; }
public:
   /// system.
   iterator overlays_end() { return FSList.rend(); }
   const_iterator overlays_end() const { return FSList.rend(); }
 };
 
 namespace detail {
 
 class InMemoryDirectory;
+class InMemoryNode;
 
 } // namespace detail
 
 /// An in-memory file system.
 class InMemoryFileSystem : public FileSystem {
   std::unique_ptr<detail::InMemoryDirectory> Root;
   std::string WorkingDirectory;
   bool UseNormalizedPaths = true;
+  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,
+               detail::InMemoryNode *HardLink);
 
 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);
 
+  public:
+  /// Add a HardLink to a File.
+  /// The To path must be an existing file or a hardlink. The From file must not
+  /// have been added before. The From Node is added as an InMemoryHardLink
+  /// which points to the resolved file of To Node.
+  bool addHardLink(const Twine &From, const Twine &To,
+                   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 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,
public:
   }
 
   void write(llvm::raw_ostream &OS);
 };
 
 } // namespace vfs
 } // namespace clang
 
 #endif // LLVM_CLANG_BASIC_VIRTUALFILESYSTEM_H

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"
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; }
+  string FileName;
 
 public:
-  InMemoryNode(Status Stat, InMemoryNodeKind Kind)
-      : Stat(std::move(Stat)), Kind(Kind) {}
+  InMemoryNode(string FileName, InMemoryNodeKind Kind)
+      : Kind(Kind), FileName(std::move(FileName)) {}
   virtual ~InMemoryNode() = default;
 
-  /// 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);
-  }
-
   /// Get the filename of this node (the name without the directory part).
   StringRef getFileName() const {
-    return llvm::sys::path::filename(Stat.getName());
+    return llvm::sys::path::filename(FileName.data());
   }
   InMemoryNodeKind getKind() const { return Kind; }
   virtual std::string toString(unsigned Indent) const = 0;
 };
 
 namespace {
 
 class InMemoryFile : public InMemoryNode {
+  Status Stat;
   std::unique_ptr<llvm::MemoryBuffer> Buffer;
 
 public:
   InMemoryFile(Status Stat, std::unique_ptr<llvm::MemoryBuffer> Buffer)
-      : InMemoryNode(std::move(Stat), IME_File), Buffer(std::move(Buffer)) {}
+      : InMemoryNode(Stat.getName().str(), 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() { return Buffer.get(); }
 
   std::string toString(unsigned Indent) const override {
-    return (std::string(Indent, ' ') + getStatus().getName() + "\n").str();
+    return (std::string(Indent, ' ') + Stat.getName() + "\n").str();
   }
 
   static bool classof(const InMemoryNode *N) {
     return N->getKind() == IME_File;
   }
 };
 
+class InMemoryHardLink : public InMemoryNode {
+  InMemoryFile &ResolvedFile;
+
+public:
+  InMemoryHardLink(StringRef Path, InMemoryFile &ResolvedFile)
+      : InMemoryNode(Path.str(), IME_HardLink), ResolvedFile(ResolvedFile) {}
+  InMemoryFile *getResolvedFile() { return &ResolvedFile; }
+
+  std::string toString(unsigned Indent) const override {
+    return std::string(Indent, ' ') + "HardLink to -> " +
+           ResolvedFile.toString(0);
+  }
+
+  static bool classof(const InMemoryNode *N) {
+    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;
   /// The name to use when returning a Status for this file.
   std::string RequestedName;
 
public:
   }
 
   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().str(), 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 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,
+                                 detail::InMemoryNode *HardLink) {
   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);
+  // Cannot create HardLink from a directory.
+  if (HardLink && !isa<detail::InMemoryFile>(HardLink))
+    return false;
   // 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.
         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)));
+          if (HardLink)
+            Child.reset(new detail::InMemoryHardLink(
+                P.str(), *static_cast<detail::InMemoryFile *>(HardLink)));
+          else
+            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);
       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,
+                 llvm::MemoryBuffer::getMemBuffer(
+                     Buffer->getBuffer(), Buffer->getBufferIdentifier()),
+                 User, Group, Type, Perms, /*HardLink=*/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(
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 link.
+    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,
+                                     Optional<uint32_t> User,
+                                     Optional<uint32_t> Group,
+                                     Optional<llvm::sys::fs::file_type> Type,
+                                     Optional<llvm::sys::fs::perms> Perms) {
+  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, User,
+                       Group, Type, Perms,
+                       static_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());
+  if (Node) {
+    if (auto Dir = dyn_cast<detail::InMemoryDirectory>(*Node))
+      return Dir->getStatus(Path.str());
+    if (auto File = dyn_cast<detail::InMemoryFile>(*Node))
+      return File->getStatus(Path.str());
+    if (auto Link = dyn_cast<detail::InMemoryHardLink>(*Node))
+      return Link->getResolvedFile()->getStatus(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);
+      if (auto Dir = dyn_cast<detail::InMemoryDirectory>(I->second.get()))
+        CurrentEntry = Dir->getStatus(Path);
+      if (auto File = dyn_cast<detail::InMemoryFile>(I->second.get()))
+        CurrentEntry = File->getStatus(Path);
+      if (auto Link = dyn_cast<detail::InMemoryHardLink>(I->second.get()))
+        CurrentEntry = Link->getResolvedFile()->getStatus(Path);
     } else {
       // When we're at the end, make CurrentEntry invalid and DirIterImpl will
       // do the rest.
       CurrentEntry = Status();
     }
   }
 
 public:

unittests/Basic/VirtualFileSystemTest.cpp

 #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 "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;

 class InMemoryFileSystemTest : public ::testing::Test {
 protected:
   clang::vfs::InMemoryFileSystem FS;
   clang::vfs::InMemoryFileSystem NormalizedFS;
 
   InMemoryFileSystemTest()
       : FS(/*UseNormalizedPaths=*/false),
         NormalizedFS(/*UseNormalizedPaths=*/true) {}
+
+public:
+  void ExpectHardLink(Twine From, Twine To, const string &ExpectedBuffer) {
+    auto OpenedFrom = FS.openFileForRead(From);
+    ASSERT_FALSE(OpenedFrom.getError());
+    auto OpenedTo = FS.openFileForRead(To);
+    ASSERT_FALSE(OpenedTo.getError());
+    ASSERT_EQ((*OpenedFrom)->status()->getSize(),
+              (*OpenedTo)->status()->getSize());
+    ASSERT_EQ((*OpenedFrom)->status()->getUniqueID(),
+              (*OpenedTo)->status()->getUniqueID());
+    ASSERT_EQ((*OpenedFrom)->getBuffer(From)->get()->getBuffer().data(),
+              (*OpenedTo)->getBuffer(To)->get()->getBuffer().data());
+    ASSERT_EQ((*OpenedFrom)->getBuffer(From)->get()->getBuffer().data(),
+              ExpectedBuffer);
+  }
 };
 
 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) {
   FS.addFile("c:/windows/system128/foo.cpp", 0, MemoryBuffer::getMemBuffer(""));
   auto Stat = FS.status("c:");
 #if !defined(_WIN32)
   ASSERT_FALSE(Stat.getError()) << Stat.getError() << FS.toString();
 #endif
   Stat = FS.status("c:/windows/system128/foo.cpp");
   ASSERT_FALSE(Stat.getError()) << Stat.getError() << FS.toString();
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) {
+  std::pair<llvm::Twine, StringRef> From = {"/path/to/FROM/file",
+                                            "content of FROM file"};
+  std::pair<llvm::Twine, StringRef> To = {"/path/to/TO/file",
+                                          "content of TO file"};
+  FS.addFile(To.first, 0, MemoryBuffer::getMemBuffer(To.second));
+  EXPECT_TRUE(FS.addHardLink(From.first, To.first));
+  ExpectHardLink(From.first, To.first, To.second.data());
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkInChainPattern) {
+  StringRef content = "content of target file";
+  Twine link0 = "/path/to/0/link";
+  Twine link1 = "/path/to/1/link";
+  Twine link2 = "/path/to/2/link";
+  Twine target = "/path/to/target";
+  FS.addFile(target, 0, MemoryBuffer::getMemBuffer(content));
+  EXPECT_TRUE(FS.addHardLink(link2, target));
+  EXPECT_TRUE(FS.addHardLink(link1, link2));
+  EXPECT_TRUE(FS.addHardLink(link0, link1));
+  ExpectHardLink(link0, target, content.data());
+  ExpectHardLink(link1, target, content.data());
+  ExpectHardLink(link2, target, content.data());
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkToAFileThatWasNotAddedBefore) {
+  Twine link = "/path/to/link";
+  Twine target = "/path/to/target";
+  EXPECT_FALSE(FS.addHardLink(link, target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkFromAFileThatWasAddedBefore) {
+  Twine link = "/path/to/link";
+  StringRef content_link = "content of link";
+  Twine target = "/path/to/target";
+  StringRef content = "content of target";
+  FS.addFile(target, 0, MemoryBuffer::getMemBuffer(content));
+  FS.addFile(link, 0, MemoryBuffer::getMemBuffer(content_link));
+  EXPECT_FALSE(FS.addHardLink(link, target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddSameHardLinkMoreThanOnce) {
+  Twine link = "/path/to/link";
+  Twine target = "/path/to/target";
+  StringRef content = "content of target";
+  FS.addFile(target, 0, MemoryBuffer::getMemBuffer(content));
+  EXPECT_TRUE(FS.addHardLink(link, target));
+  EXPECT_FALSE(FS.addHardLink(link, target));
+}
+
+TEST_F(InMemoryFileSystemTest, AddFileInPlaceOfAHardLinkWithSameContent) {
+  Twine link = "/path/to/link";
+  Twine 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) {
+  Twine link = "/path/to/link";
+  Twine target = "/path/to/target";
+  StringRef content = "content of target";
+  StringRef link_content = "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(link_content)));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkToADirectory) {
+  Twine dir = "path/to/dummy/dir";
+  Twine link = "/path/to/link";
+  Twine dummy_file = dir + "/target";
+  StringRef content = "content of target";
+  EXPECT_TRUE(FS.addFile(dummy_file, 0, MemoryBuffer::getMemBuffer(content)));
+  EXPECT_FALSE(FS.addHardLink(link, dir));
+}
+
+TEST_F(InMemoryFileSystemTest, AddHardLinkFromADirectory) {
+  Twine dir = "path/to/dummy/dir";
+  Twine target = 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 common_content = "content string";
+  FS.addFile("/a/b", 0, MemoryBuffer::getMemBuffer(common_content));
+  FS.addFile("/c/d", 0, MemoryBuffer::getMemBuffer(common_content));
+  EXPECT_FALSE(FS.addHardLink("/c/d/e", "/a/b"));
+}
+
+TEST_F(InMemoryFileSystemTest, RecursiveIterationWithHardLink) {
+  std::error_code EC;
+  StringRef common_content = "content string";
+  FS.addFile("/a/b", 0, MemoryBuffer::getMemBuffer(common_content));
+  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(I->getName());
+  }
+
+  // Check contents, which may be in any order
+  EXPECT_EQ(4U, Nodes.size());
+  int Counts[4] = {0, 0, 0, 0};
+  for (const std::string &Name : Nodes) {
+    ASSERT_FALSE(Name.empty());
+    int Index = Name[Name.size() - 1] - 'a';
+    ASSERT_TRUE(Index >= 0 && Index < 4);
+    Counts[Index]++;
+  }
+  EXPECT_EQ(1, Counts[0]);  // a
+  EXPECT_EQ(1, Counts[1]);  // b
+  EXPECT_EQ(1, Counts[2]);  // c
+  EXPECT_EQ(1, Counts[3]);  // 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; }
 
FS = getFromYAMLString(
        "{ 'roots': [\n"
        "  { 'type': 'directory', 'name': 'relative/directory/path.h',\n"
        "    'contents': []\n"
        "  }\n"
        "] }", Lower);
   EXPECT_EQ(nullptr, FS.get());
 
   EXPECT_EQ(3, NumDiagnostics);
 }