Merge branch 'tlater/CASdiff' into 'master'

storage/_casbaseddirectory.py: Implement `_apply_changes`

See merge request BuildStream/buildstream!1769

55 files changed, 335 insertions, 19 deletions

diff --git a/src/buildstream/storage/_casbaseddirectory.py b/src/buildstream/storage/_casbaseddirectory.py
index 624d071dd..e86dd100c 100644
--- a/src/buildstream/storage/_casbaseddirectory.py
+++ b/src/buildstream/storage/_casbaseddirectory.py
@@ -73,10 +73,40 @@ class IndexEntry:
         return self.buildstream_object
 
     def get_digest(self):
-        if self.digest:
-            return self.digest
-        else:
+        if self.buildstream_object:
+            # directory with buildstream object
             return self.buildstream_object._get_digest()
+        else:
+            # regular file, symlink or directory without buildstream object
+            return self.digest
+
+    # clone():
+    #
+    # Create a deep copy of this object. If this is a directory, a
+    # CasBasedDirectory can also be passed to assign an appropriate
+    # parent directory.
+    #
+    def clone(self) -> "IndexEntry":
+        return IndexEntry(
+            self.name,
+            self.type,
+            # If this is a directory, the digest will be converted
+            # later if necessary. For other non-file types, digests
+            # are always None.
+            digest=self.get_digest(),
+            target=self.target,
+            is_executable=self.is_executable,
+            node_properties=self.node_properties,
+        )
+
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, IndexEntry):
+            return NotImplemented
+
+        def get_equivalency_properties(e: IndexEntry):
+            return (e.name, e.type, e.target, e.is_executable, e.node_properties, e.get_digest())
+
+        return get_equivalency_properties(self) == get_equivalency_properties(other)
 
 
 # CasBasedDirectory intentionally doesn't call its superclass constuctor,
@@ -158,23 +188,109 @@ class CasBasedDirectory(Directory):
         return newdir
 
     def _add_file(self, basename, filename, modified=False, can_link=False, properties=None):
-        entry = IndexEntry(filename, _FileType.REGULAR_FILE, modified=modified or filename in self.index)
         path = os.path.join(basename, filename)
-        entry.digest = self.cas_cache.add_object(path=path, link_directly=can_link)
-        entry.is_executable = os.access(path, os.X_OK)
-        properties = properties or []
+        digest = self.cas_cache.add_object(path=path, link_directly=can_link)
+        is_executable = os.access(path, os.X_OK)
+        node_properties = []
         # see https://github.com/bazelbuild/remote-apis/blob/master/build/bazel/remote/execution/v2/nodeproperties.md
         # for supported node property specifications
-        entry.node_properties = []
-        if "MTime" in properties:
+        if properties and "MTime" in properties:
             node_property = remote_execution_pb2.NodeProperty()
             node_property.name = "MTime"
             node_property.value = _get_file_mtimestamp(path)
-            entry.node_properties.append(node_property)
+            node_properties.append(node_property)
+
+        entry = IndexEntry(
+            filename,
+            _FileType.REGULAR_FILE,
+            digest=digest,
+            is_executable=is_executable,
+            modified=modified or filename in self.index,
+            node_properties=node_properties,
+        )
         self.index[filename] = entry
 
         self.__invalidate_digest()
 
+    def _add_entry(self, entry: IndexEntry):
+        self.index[entry.name] = entry.clone()
+        self.__invalidate_digest()
+
+    def _contains_entry(self, entry: IndexEntry) -> bool:
+        return entry == self.index.get(entry.name)
+
+    # _apply_changes():
+    #
+    # Apply changes from dir_a to dir_b to this directory. The use
+    # case for this is to merge changes between different workspace
+    # versions into a buildtree.
+    #
+    # If a change was made both to this directory, as well as between
+    # the given directories, it is applied, overwriting any changes to
+    # this directory. This is desirable because we want to keep user
+    # changes, however it may need to be re-considered for other use
+    # cases.
+    #
+    # We perform this computation this way, instead of with a _diff
+    # method and a subsequent _apply_diff, because it prevents leaking
+    # IndexEntry objects, which contain mutable references and may
+    # therefore cause problems if used outside of this class.
+    #
+    # Args:
+    #     dir_a: The directory from which to start computing differences.
+    #     dir_b: The directory whose changes to apply
+    #
+    def _apply_changes(self, dir_a: "CasBasedDirectory", dir_b: "CasBasedDirectory"):
+        # If the digests are the same, the directories are the same
+        # (child properties affect the digest). We can skip any work
+        # in such a case.
+        if dir_a._get_digest() == dir_b._get_digest():
+            return
+
+        def get_subdir(entry: IndexEntry, directory: CasBasedDirectory) -> CasBasedDirectory:
+            return directory.index[entry.name].get_directory(directory)
+
+        def is_dir_in(entry: IndexEntry, directory: CasBasedDirectory) -> bool:
+            return directory.index[entry.name].type == _FileType.DIRECTORY
+
+        # We first check which files were added, and add them to our
+        # directory.
+        for entry in dir_b.index.values():
+            if self._contains_entry(entry):
+                # We can short-circuit checking entries from b that
+                # already exist in our index.
+                continue
+
+            if not dir_a._contains_entry(entry):
+                if entry.name in self.index and is_dir_in(entry, self) and is_dir_in(entry, dir_b):
+                    # If the entry changed, and is a directory in both
+                    # the current and to-merge-into tree, we need to
+                    # merge recursively.
+
+                    # If the entry is not a directory in dir_a, we
+                    # want to overwrite the file, but we need an empty
+                    # directory for recursion.
+                    if entry.name in dir_a.index and is_dir_in(entry, dir_a):
+                        sub_a = get_subdir(entry, dir_a)
+                    else:
+                        sub_a = CasBasedDirectory(dir_a.cas_cache)
+
+                    subdir = get_subdir(entry, self)
+                    subdir._apply_changes(sub_a, get_subdir(entry, dir_b))
+                else:
+                    # In any other case, we just add/overwrite the file/directory
+                    self._add_entry(entry)
+
+        # We can't iterate and remove entries at the same time
+        to_remove = [entry for entry in dir_a.index.values() if entry.name not in dir_b.index]
+        for entry in to_remove:
+            self.delete_entry(entry.name)
+
+        self.__invalidate_digest()
+
+    def _copy_link_from_filesystem(self, basename, filename):
+        self._add_new_link_direct(filename, os.readlink(os.path.join(basename, filename)))
+
     def _add_new_link_direct(self, name, target):
         self.index[name] = IndexEntry(name, _FileType.SYMLINK, target=target, modified=name in self.index)
 
@@ -343,15 +459,8 @@ class CasBasedDirectory(Directory):
             if not is_dir:
                 if self._check_replacement(name, relative_pathname, result):
                     if entry.type == _FileType.REGULAR_FILE:
-                        self.index[name] = IndexEntry(
-                            name,
-                            _FileType.REGULAR_FILE,
-                            digest=entry.digest,
-                            is_executable=entry.is_executable,
-                            modified=True,
-                            node_properties=entry.node_properties,
-                        )
-                        self.__invalidate_digest()
+                        self._add_entry(entry)
+                        self.index[entry.name].modified = True
                     else:
                         assert entry.type == _FileType.SYMLINK
                         self._add_new_link_direct(name=name, target=entry.target)
diff --git a/tests/internals/storage.py b/tests/internals/storage.py
index 8aa7f4a17..89a198d98 100644
--- a/tests/internals/storage.py
+++ b/tests/internals/storage.py
@@ -1,11 +1,17 @@
 from contextlib import contextmanager
 import os
+import pprint
+import shutil
+import glob
+from pathlib import Path
+from typing import List, Optional
 
 import pytest
 
 from buildstream._cas import CASCache
 from buildstream.storage._casbaseddirectory import CasBasedDirectory
 from buildstream.storage._filebaseddirectory import FileBasedDirectory
+from buildstream.storage.directory import _FileType
 
 DATA_DIR = os.path.join(os.path.dirname(os.path.realpath(__file__)), "storage")
 
@@ -51,3 +57,195 @@ def test_modified_file_list(tmpdir, datafiles, backend):
         assert "bin/bash" in c.list_relative_paths()
         assert "bin/bash" in c.list_modified_paths()
         assert "bin/hello" not in c.list_modified_paths()
+
+
+@pytest.mark.parametrize(
+    "directories", [("merge-base", "merge-base"), ("empty", "empty"),],
+)
+@pytest.mark.datafiles(DATA_DIR)
+def test_merge_same_casdirs(tmpdir, datafiles, directories):
+    buildtree = os.path.join(str(datafiles), "merge-buildtree")
+    before = os.path.join(str(datafiles), directories[0])
+    after = os.path.join(str(datafiles), directories[1])
+
+    # Bring the directories into a canonical state
+    for directory in (buildtree, before, after):
+        clear_gitkeeps(directory)
+        utime_recursively(directory, (100, 100))
+
+    with setup_backend(CasBasedDirectory, str(tmpdir)) as c, setup_backend(
+        CasBasedDirectory, str(tmpdir)
+    ) as a, setup_backend(CasBasedDirectory, str(tmpdir)) as b:
+        a.import_files(before)
+        b.import_files(after)
+        c.import_files(buildtree)
+
+        assert a._get_digest() == b._get_digest(), "{}\n{}".format(
+            pprint.pformat(list_relative_paths(a)), pprint.pformat(list_relative_paths(b))
+        )
+        old_digest = c._get_digest()
+        c._apply_changes(a, b)
+        # Assert that the build tree stays the same (since there were
+        # no changes between a and b)
+        assert c._get_digest() == old_digest
+
+
+@pytest.mark.parametrize(
+    "directories",
+    [
+        ("merge-base", "merge-replace"),
+        ("merge-base", "merge-remove"),
+        ("merge-base", "merge-add"),
+        ("merge-base", "merge-link"),
+        ("merge-base", "merge-subdirectory-replace"),
+        ("merge-base", "merge-subdirectory-remove"),
+        ("merge-base", "merge-subdirectory-add"),
+        ("merge-base", "merge-subdirectory-link"),
+        ("merge-link", "merge-link-change"),
+        ("merge-subdirectory-link", "merge-link-change"),
+        ("merge-base", "merge-override-with-file"),
+        ("merge-base", "merge-override-with-directory"),
+        ("merge-base", "merge-override-in-subdir-with-file"),
+        ("merge-base", "merge-override-in-subdir-with-directory"),
+        ("merge-base", "merge-override-subdirectory"),
+        ("merge-override-with-new-subdirectory", "merge-subdirectory-add"),
+        ("empty", "merge-subdirectory-add"),
+    ],
+)
+@pytest.mark.datafiles(DATA_DIR)
+def test_merge_casdirs(tmpdir, datafiles, directories):
+    buildtree = os.path.join(str(datafiles), "merge-buildtree")
+    before = os.path.join(str(datafiles), directories[0])
+    after = os.path.join(str(datafiles), directories[1])
+
+    # Bring the directories into a canonical state
+    for directory in (buildtree, before, after):
+        clear_gitkeeps(directory)
+        utime_recursively(directory, (100, 100))
+
+    _test_merge_dirs(before, after, buildtree, str(tmpdir))
+
+
+@pytest.mark.datafiles(DATA_DIR)
+@pytest.mark.parametrize("modification", ["executable", "time"])
+def test_merge_casdir_properties(tmpdir, datafiles, modification):
+    buildtree = os.path.join(str(datafiles), "merge-buildtree")
+    before = os.path.join(str(datafiles), "merge-base")
+    after = os.path.join(str(tmpdir), "merge-modified")
+    shutil.copytree(before, after, symlinks=True)
+
+    # Bring the directories into a canonical state
+    for directory in (buildtree, before, after):
+        clear_gitkeeps(directory)
+        utime_recursively(directory, (100, 100))
+
+    if modification == "executable":
+        os.chmod(os.path.join(after, "root-file"), 0o755)
+    elif modification == "time":
+        os.utime(os.path.join(after, "root-file"), (200, 200))
+
+    _test_merge_dirs(before, after, buildtree, str(tmpdir), properties=["MTime"])
+
+
+def _test_merge_dirs(
+    before: str, after: str, buildtree: str, tmpdir: str, properties: Optional[List[str]] = None
+) -> bool:
+    with setup_backend(CasBasedDirectory, tmpdir) as c, setup_backend(
+        CasBasedDirectory, tmpdir
+    ) as copy, setup_backend(CasBasedDirectory, tmpdir) as a, setup_backend(CasBasedDirectory, tmpdir) as b:
+        a.import_files(before, properties=properties)
+        b.import_files(after, properties=properties)
+        c.import_files(buildtree, properties=properties)
+        copy.import_files(buildtree, properties=properties)
+
+        assert c._get_digest() == copy._get_digest()
+
+        assert a._get_digest() != b._get_digest(), "{}\n{}".format(
+            pprint.pformat(list_relative_paths(a)), pprint.pformat(list_relative_paths(b))
+        )
+        c._apply_changes(a, b)
+        # The files in c now should contain changes from b, so these
+        # shouldn't be the same anymore
+        assert c._get_digest() != copy._get_digest(), "{}\n{}".format(
+            pprint.pformat(list_relative_paths(c)), pprint.pformat(list_relative_paths(copy))
+        )
+
+        # This is the set of paths that should have been removed
+        removed = [path for path in list_paths_with_properties(a) if path not in list_paths_with_properties(b)]
+
+        # This is the set of paths that were added in the new set
+        added = [path for path in list_paths_with_properties(b) if path not in list_paths_with_properties(a)]
+
+        # We need to strip some types of values, since they're more
+        # than our little list comparisons can handle
+        def make_info(entry, list_props=None):
+            ret = {k: v for k, v in vars(entry).items() if k != "buildstream_object"}
+            if entry.type == _FileType.REGULAR_FILE:
+                # Only file digests make sense here (directory digests
+                # need to be re-calculated taking into account their
+                # contents).
+                ret["digest"] = entry.get_digest()
+            else:
+                ret["digest"] = None
+            return ret
+
+        combined = [path for path in list_paths_with_properties(copy) if path not in removed]
+        # Add the new list, overriding any old entries that already
+        # exist.
+        for path in added:
+            if path.name in (o.name for o in combined):
+                # Any paths that already exist must be removed
+                # first
+                combined = [o for o in combined if o.name != path.name]
+                combined.append(path)
+            else:
+                combined.append(path)
+
+        # If any paths don't have a parent directory, we need to
+        # remove them now
+        for e in combined:
+            path = Path(e.name)
+            for parent in list(path.parents)[:-1]:
+                if not str(parent) in (e.name for e in combined if e.type == _FileType.DIRECTORY):
+                    # If not all parent directories are existing
+                    # directories
+                    combined = [e for e in combined if e.name != str(path)]
+
+        assert sorted(list(make_info(e) for e in combined), key=lambda x: x["name"]) == sorted(
+            list(make_info(e) for e in list_paths_with_properties(c)), key=lambda x: x["name"]
+        )
+
+
+# This is purely for error output; lists relative paths and
+# their digests so differences are human-grokkable
+def list_relative_paths(directory):
+    def entry_output(entry):
+        if entry.type == _FileType.DIRECTORY:
+            return list_relative_paths(entry.get_directory(directory))
+        elif entry.type == _FileType.SYMLINK:
+            return "-> " + entry.target
+        else:
+            return entry.get_digest().hash
+
+    return {name: entry_output(entry) for name, entry in directory.index.items()}
+
+
+def list_paths_with_properties(directory, prefix=""):
+    for leaf in directory.index.keys():
+        entry = directory.index[leaf].clone()
+        if directory.filename:
+            entry.name = directory.filename + os.path.sep + entry.name
+        yield entry
+        if entry.type == _FileType.DIRECTORY:
+            subdir = entry.get_directory(directory)
+            yield from list_paths_with_properties(subdir)
+
+
+def utime_recursively(directory, time):
+    for f in glob.glob(os.path.join(directory, "**"), recursive=True):
+        os.utime(f, time)
+
+
+def clear_gitkeeps(directory):
+    for f in glob.glob(os.path.join(directory, "**", ".gitkeep"), recursive=True):
+        os.remove(f)
diff --git a/tests/internals/storage/empty/.gitkeep b/tests/internals/storage/empty/.gitkeep
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/empty/.gitkeep
diff --git a/tests/internals/storage/merge-add/added b/tests/internals/storage/merge-add/added
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-add/added
diff --git a/tests/internals/storage/merge-add/root-file b/tests/internals/storage/merge-add/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-add/root-file
diff --git a/tests/internals/storage/merge-add/subdirectory/subdir-file b/tests/internals/storage/merge-add/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-add/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-base/root-file b/tests/internals/storage/merge-base/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-base/root-file
diff --git a/tests/internals/storage/merge-base/subdirectory/subdir-file b/tests/internals/storage/merge-base/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-base/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-buildtree/root-file b/tests/internals/storage/merge-buildtree/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-buildtree/root-file
diff --git a/tests/internals/storage/merge-buildtree/root-file.o b/tests/internals/storage/merge-buildtree/root-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-buildtree/root-file.o
diff --git a/tests/internals/storage/merge-buildtree/subdirectory/subdir-file b/tests/internals/storage/merge-buildtree/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-buildtree/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-buildtree/subdirectory/subdir-file.o b/tests/internals/storage/merge-buildtree/subdirectory/subdir-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-buildtree/subdirectory/subdir-file.o
diff --git a/tests/internals/storage/merge-link-change/link b/tests/internals/storage/merge-link-change/link
new file mode 120000
index 000000000..9da48df08
--- /dev/null
+++ b/tests/internals/storage/merge-link-change/link
@@ -0,0 +1 @@
+subdirectory/subdir-file
\ No newline at end of file
diff --git a/tests/internals/storage/merge-link-change/root-file b/tests/internals/storage/merge-link-change/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-link-change/root-file
diff --git a/tests/internals/storage/merge-link-change/subdirectory/link b/tests/internals/storage/merge-link-change/subdirectory/link
new file mode 120000
index 000000000..04db3d236
--- /dev/null
+++ b/tests/internals/storage/merge-link-change/subdirectory/link
@@ -0,0 +1 @@
+../root-file
\ No newline at end of file
diff --git a/tests/internals/storage/merge-link-change/subdirectory/subdir-file b/tests/internals/storage/merge-link-change/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-link-change/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-link/link b/tests/internals/storage/merge-link/link
new file mode 120000
index 000000000..c4e282ef7
--- /dev/null
+++ b/tests/internals/storage/merge-link/link
@@ -0,0 +1 @@
+root-file
\ No newline at end of file
diff --git a/tests/internals/storage/merge-link/root-file b/tests/internals/storage/merge-link/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-link/root-file
diff --git a/tests/internals/storage/merge-link/subdirectory/subdir-file b/tests/internals/storage/merge-link/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-link/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-override-in-subdir-with-directory/root-file b/tests/internals/storage/merge-override-in-subdir-with-directory/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-directory/root-file
diff --git a/tests/internals/storage/merge-override-in-subdir-with-directory/root-file.o b/tests/internals/storage/merge-override-in-subdir-with-directory/root-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-directory/root-file.o
diff --git a/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file b/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file.o/test b/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file.o/test
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-directory/subdirectory/subdir-file.o/test
diff --git a/tests/internals/storage/merge-override-in-subdir-with-file/root-file b/tests/internals/storage/merge-override-in-subdir-with-file/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-file/root-file
diff --git a/tests/internals/storage/merge-override-in-subdir-with-file/root-file.o b/tests/internals/storage/merge-override-in-subdir-with-file/root-file.o
new file mode 100644
index 000000000..9daeafb98
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-file/root-file.o
@@ -0,0 +1 @@
+test
diff --git a/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file b/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file.o b/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-in-subdir-with-file/subdirectory/subdir-file.o
diff --git a/tests/internals/storage/merge-override-subdirectory/root-file b/tests/internals/storage/merge-override-subdirectory/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-subdirectory/root-file
diff --git a/tests/internals/storage/merge-override-subdirectory/root-file.o b/tests/internals/storage/merge-override-subdirectory/root-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-subdirectory/root-file.o
diff --git a/tests/internals/storage/merge-override-subdirectory/subdirectory b/tests/internals/storage/merge-override-subdirectory/subdirectory
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-subdirectory/subdirectory
diff --git a/tests/internals/storage/merge-override-with-directory/root-file b/tests/internals/storage/merge-override-with-directory/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-directory/root-file
diff --git a/tests/internals/storage/merge-override-with-directory/root-file.o/test b/tests/internals/storage/merge-override-with-directory/root-file.o/test
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-directory/root-file.o/test
diff --git a/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file b/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file.o b/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-directory/subdirectory/subdir-file.o
diff --git a/tests/internals/storage/merge-override-with-file/root-file b/tests/internals/storage/merge-override-with-file/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-file/root-file
diff --git a/tests/internals/storage/merge-override-with-file/root-file.o b/tests/internals/storage/merge-override-with-file/root-file.o
new file mode 100644
index 000000000..9daeafb98
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-file/root-file.o
@@ -0,0 +1 @@
+test
diff --git a/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file b/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file.o b/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file.o
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-file/subdirectory/subdir-file.o
diff --git a/tests/internals/storage/merge-override-with-new-subdirectory/root-file b/tests/internals/storage/merge-override-with-new-subdirectory/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-new-subdirectory/root-file
diff --git a/tests/internals/storage/merge-override-with-new-subdirectory/subdirectory b/tests/internals/storage/merge-override-with-new-subdirectory/subdirectory
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-override-with-new-subdirectory/subdirectory
diff --git a/tests/internals/storage/merge-properties/root-file b/tests/internals/storage/merge-properties/root-file
new file mode 100755
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-properties/root-file
diff --git a/tests/internals/storage/merge-properties/subdirectory/subdir-file b/tests/internals/storage/merge-properties/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-properties/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-remove/subdirectory/subdir-file b/tests/internals/storage/merge-remove/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-remove/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-replace/root-file b/tests/internals/storage/merge-replace/root-file
new file mode 100644
index 000000000..617807982
--- /dev/null
+++ b/tests/internals/storage/merge-replace/root-file
@@ -0,0 +1 @@
+b
diff --git a/tests/internals/storage/merge-replace/subdirectory/subdir-file b/tests/internals/storage/merge-replace/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-replace/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-subdirectory-add/root-file b/tests/internals/storage/merge-subdirectory-add/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-add/root-file
diff --git a/tests/internals/storage/merge-subdirectory-add/subdirectory/added b/tests/internals/storage/merge-subdirectory-add/subdirectory/added
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-add/subdirectory/added
diff --git a/tests/internals/storage/merge-subdirectory-add/subdirectory/subdir-file b/tests/internals/storage/merge-subdirectory-add/subdirectory/subdir-file
new file mode 100644
index 000000000..617807982
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-add/subdirectory/subdir-file
@@ -0,0 +1 @@
+b
diff --git a/tests/internals/storage/merge-subdirectory-link/root-file b/tests/internals/storage/merge-subdirectory-link/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-link/root-file
diff --git a/tests/internals/storage/merge-subdirectory-link/subdirectory/link b/tests/internals/storage/merge-subdirectory-link/subdirectory/link
new file mode 120000
index 000000000..787413cef
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-link/subdirectory/link
@@ -0,0 +1 @@
+subdir-file
\ No newline at end of file
diff --git a/tests/internals/storage/merge-subdirectory-link/subdirectory/subdir-file b/tests/internals/storage/merge-subdirectory-link/subdirectory/subdir-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-link/subdirectory/subdir-file
diff --git a/tests/internals/storage/merge-subdirectory-remove/root-file b/tests/internals/storage/merge-subdirectory-remove/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-remove/root-file
diff --git a/tests/internals/storage/merge-subdirectory-remove/subdirectory/.gitkeep b/tests/internals/storage/merge-subdirectory-remove/subdirectory/.gitkeep
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-remove/subdirectory/.gitkeep
diff --git a/tests/internals/storage/merge-subdirectory-replace/root-file b/tests/internals/storage/merge-subdirectory-replace/root-file
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-replace/root-file
diff --git a/tests/internals/storage/merge-subdirectory-replace/subdirectory/subdir-file b/tests/internals/storage/merge-subdirectory-replace/subdirectory/subdir-file
new file mode 100644
index 000000000..617807982
--- /dev/null
+++ b/tests/internals/storage/merge-subdirectory-replace/subdirectory/subdir-file
@@ -0,0 +1 @@
+b