refactor FileRoot::DirectoryEntries

... to foster the implementation of the built-in target "TREE"

9 files changed, 339 insertions, 26 deletions

diff --git a/src/buildtool/build_engine/base_maps/source_map.cpp b/src/buildtool/build_engine/base_maps/source_map.cpp
index 39976016..5e18a3e5 100644
--- a/src/buildtool/build_engine/base_maps/source_map.cpp
+++ b/src/buildtool/build_engine/base_maps/source_map.cpp
@@ -72,7 +72,7 @@ auto CreateSourceTargetMap(const gsl::not_null<DirectoryEntriesMap*>& dirs,
             ts,
             {ModuleName{target.repository, dir.string()}},
             [key, src_file_reader](auto values) {
-                src_file_reader(values[0]->Contains(
+                src_file_reader(values[0]->ContainsFile(
                     path(key.GetNamedTarget().name).filename().string()));
             },
             [logger, dir](auto msg, auto fatal) {
diff --git a/src/buildtool/file_system/file_root.hpp b/src/buildtool/file_system/file_root.hpp
index 1df40588..58f521cd 100644
--- a/src/buildtool/file_system/file_root.hpp
+++ b/src/buildtool/file_system/file_root.hpp
@@ -2,15 +2,75 @@
 #define INCLUDED_SRC_BUILDTOOL_FILE_SYSTEM_FILE_ROOT_HPP
 
 #include <filesystem>
+#include <iterator>
 #include <memory>
 #include <string>
+#include <unordered_map>
 #include <unordered_set>
+#include <utility>
 #include <variant>
 
 #include "gsl-lite/gsl-lite.hpp"
 #include "src/buildtool/common/artifact_description.hpp"
 #include "src/buildtool/file_system/file_system_manager.hpp"
 #include "src/buildtool/file_system/git_tree.hpp"
+#include "src/utils/cpp/concepts.hpp"
+
+/// FilteredIterator is an helper class to allow for iteration over
+/// directory-only or file-only entries stored inside the class
+/// DirectoryEntries. Internally, DirectoryEntries holds a
+/// map<string,ObjectType> or map<string, GitTree*>. While iterating, we are
+/// just interested in the name of the entry (i.e., the string).
+/// To decide which entries retain, the FilteredIterator requires a predicate.
+template <StrMapConstForwardIterator I>
+// I is a forward iterator
+// I::value_type is a std::pair<const std::string, *>
+class FilteredIterator {
+  public:
+    using value_type = std::string const;
+    using pointer = value_type*;
+    using reference = value_type&;
+    using difference_type = std::ptrdiff_t;
+    using iteratori_category = std::forward_iterator_tag;
+    using predicate_t = std::function<bool(typename I::reference)>;
+
+    FilteredIterator() noexcept = default;
+    // [first, last) is a valid sequence
+    FilteredIterator(I first, I last, predicate_t p) noexcept
+        : iterator_{std::find_if(first, last, p)},
+          end_{std::move(last)},
+          p{std::move(p)} {}
+
+    auto operator*() const noexcept -> reference { return iterator_->first; }
+
+    auto operator++() noexcept -> FilteredIterator& {
+        ++iterator_;
+        iterator_ = std::find_if(iterator_, end_, p);
+        return *this;
+    }
+
+    [[nodiscard]] auto begin() noexcept -> FilteredIterator& { return *this; }
+    [[nodiscard]] auto end() const noexcept -> FilteredIterator {
+        return FilteredIterator{end_, end_, p};
+    }
+
+    [[nodiscard]] friend auto operator==(FilteredIterator const& x,
+                                         FilteredIterator const& y) noexcept
+        -> bool {
+        return x.iterator_ == y.iterator_;
+    }
+
+    [[nodiscard]] friend auto operator!=(FilteredIterator const& x,
+                                         FilteredIterator const& y) noexcept
+        -> bool {
+        return not(x == y);
+    }
+
+  private:
+    I iterator_{};
+    const I end_{};
+    predicate_t p{};
+};
 
 class FileRoot {
     using fs_root_t = std::filesystem::path;
@@ -22,27 +82,100 @@ class FileRoot {
 
   public:
     class DirectoryEntries {
-        using names_t = std::unordered_set<std::string>;
+        friend class FileRoot;
+        using pairs_t = std::unordered_map<std::string, ObjectType>;
         using tree_t = gsl::not_null<GitTree const*>;
-        using entries_t = std::variant<std::monostate, names_t, tree_t>;
+        using entries_t = std::variant<std::monostate, tree_t, pairs_t>;
+
+        using fs_iterator_type = typename pairs_t::const_iterator;
+        using fs_iterator = FilteredIterator<fs_iterator_type>;
+
+        using git_iterator_type = GitTree::entries_t::const_iterator;
+        using git_iterator = FilteredIterator<git_iterator_type>;
+
+        /// Iterator has two FilteredIterators, one for iterating over pairs_t
+        /// and one for tree_t. Each FilteredIterator is constructed with a
+        /// proper predicate, allowing for iteration on file-only or
+        /// directory-only entries
+        class Iterator {
+          public:
+            using value_type = std::string const;
+            using pointer = value_type*;
+            using reference = value_type&;
+            using difference_type = std::ptrdiff_t;
+            using iteratori_category = std::forward_iterator_tag;
+            explicit Iterator(fs_iterator fs_it) : it_{std::move(fs_it)} {}
+            explicit Iterator(git_iterator git_it) : it_{std::move(git_it)} {}
+
+            auto operator*() const noexcept -> reference {
+                if (std::holds_alternative<fs_iterator>(it_)) {
+                    return *std::get<fs_iterator>(it_);
+                }
+                return *std::get<git_iterator>(it_);
+            }
+
+            [[nodiscard]] auto begin() noexcept -> Iterator& { return *this; }
+            [[nodiscard]] auto end() const noexcept -> Iterator {
+                if (std::holds_alternative<fs_iterator>(it_)) {
+                    return Iterator{std::get<fs_iterator>(it_).end()};
+                }
+                return Iterator{std::get<git_iterator>(it_).end()};
+            }
+            auto operator++() noexcept -> Iterator& {
+                if (std::holds_alternative<fs_iterator>(it_)) {
+                    ++(std::get<fs_iterator>(it_));
+                }
+                else {
+                    ++(std::get<git_iterator>(it_));
+                }
+                return *this;
+            }
+
+            friend auto operator==(Iterator const& x,
+                                   Iterator const& y) noexcept -> bool {
+                return x.it_ == y.it_;
+            }
+            friend auto operator!=(Iterator const& x,
+                                   Iterator const& y) noexcept -> bool {
+                return not(x == y);
+            }
+
+          private:
+            std::variant<fs_iterator, git_iterator> it_;
+        };
 
       public:
         DirectoryEntries() noexcept = default;
-        explicit DirectoryEntries(names_t names) noexcept
-            : data_{std::move(names)} {}
+
+        explicit DirectoryEntries(pairs_t pairs) noexcept
+            : data_{std::move(pairs)} {}
+
         explicit DirectoryEntries(tree_t git_tree) noexcept
             : data_{std::move(git_tree)} {}
-        [[nodiscard]] auto Contains(std::string const& name) const noexcept
+
+        [[nodiscard]] auto ContainsFile(std::string const& name) const noexcept
             -> bool {
-            if (std::holds_alternative<tree_t>(data_)) {
-                return static_cast<bool>(
-                    std::get<tree_t>(data_)->LookupEntryByName(name));
-            }
-            if (std::holds_alternative<names_t>(data_)) {
-                return std::get<names_t>(data_).contains(name);
+            try {
+                if (std::holds_alternative<tree_t>(data_)) {
+                    auto const& data = std::get<tree_t>(data_);
+                    auto ptr = data->LookupEntryByName(name);
+                    if (static_cast<bool>(ptr)) {
+                        return ptr->IsBlob();
+                    }
+                    return false;
+                }
+                if (std::holds_alternative<pairs_t>(data_)) {
+                    auto const& data = std::get<pairs_t>(data_);
+                    auto it = data.find(name);
+                    return (it != data.end() and
+                            it->second == ObjectType::File);
+                }
+            } catch (...) {
             }
+
             return false;
         }
+
         [[nodiscard]] auto Empty() const noexcept -> bool {
             if (std::holds_alternative<tree_t>(data_)) {
                 try {
@@ -52,12 +185,45 @@ class FileRoot {
                     return false;
                 }
             }
-            if (std::holds_alternative<names_t>(data_)) {
-                return std::get<names_t>(data_).empty();
+            if (std::holds_alternative<pairs_t>(data_)) {
+                return std::get<pairs_t>(data_).empty();
             }
             return true;
         }
 
+        [[nodiscard]] auto FilesIterator() const -> Iterator {
+            if (std::holds_alternative<pairs_t>(data_)) {
+                auto const& data = std::get<pairs_t>(data_);
+                return Iterator{FilteredIterator{
+                    data.begin(), data.end(), [](auto const& x) {
+                        return x.second == ObjectType::File;
+                    }}};
+            }
+            // std::holds_alternative<tree_t>(data_) == true
+            auto const& data = std::get<tree_t>(data_);
+            return Iterator{FilteredIterator{
+                data->begin(), data->end(), [](auto const& x) noexcept -> bool {
+                    return x.second->IsBlob();
+                }}};
+        }
+
+        [[nodiscard]] auto DirectoriesIterator() const -> Iterator {
+            if (std::holds_alternative<pairs_t>(data_)) {
+                auto const& data = std::get<pairs_t>(data_);
+                return Iterator{FilteredIterator{
+                    data.begin(), data.end(), [](auto const& x) {
+                        return x.second == ObjectType::Tree;
+                    }}};
+            }
+
+            // std::holds_alternative<tree_t>(data_) == true
+            auto const& data = std::get<tree_t>(data_);
+            return Iterator{FilteredIterator{
+                data->begin(), data->end(), [](auto const& x) noexcept -> bool {
+                    return x.second->IsTree();
+                }}};
+        }
+
       private:
         entries_t data_{};
     };
@@ -163,14 +329,14 @@ class FileRoot {
                 }
             }
             else {
-                std::unordered_set<std::string> names{};
+                DirectoryEntries::pairs_t map{};
                 if (FileSystemManager::ReadDirectory(
                         std::get<fs_root_t>(root_) / dir_path,
-                        [&names](auto name, auto /*type*/) {
-                            names.emplace(name.string());
+                        [&map](const auto& name, auto type) {
+                            map.emplace(name.string(), type);
                             return true;
                         })) {
-                    return DirectoryEntries{std::move(names)};
+                    return DirectoryEntries{std::move(map)};
                 }
             }
         } catch (std::exception const& ex) {
diff --git a/src/buildtool/file_system/object_type.hpp b/src/buildtool/file_system/object_type.hpp
index 6209f05d..79aaa96b 100644
--- a/src/buildtool/file_system/object_type.hpp
+++ b/src/buildtool/file_system/object_type.hpp
@@ -1,7 +1,8 @@
 #ifndef INCLUDED_SRC_BUILDTOOL_FILE_SYSTEM_OBJECT_TYPE_HPP
 #define INCLUDED_SRC_BUILDTOOL_FILE_SYSTEM_OBJECT_TYPE_HPP
+#include <cstdint>
 
-enum class ObjectType {
+enum class ObjectType : std::int8_t {
     File,
     Executable,
     Tree,
diff --git a/src/utils/cpp/concepts.hpp b/src/utils/cpp/concepts.hpp
index 597179e1..04b2bfcc 100644
--- a/src/utils/cpp/concepts.hpp
+++ b/src/utils/cpp/concepts.hpp
@@ -66,4 +66,10 @@ concept ClockHasFromTime = requires(std::time_t const t) {
     T::from_time_t(t);
 };
 
+template <typename T>
+concept StrMapConstForwardIterator = requires(T const c) {
+    { (*c).first }
+    ->same_as<std::string const>;
+};
+
 #endif  // INCLUDED_SRC_UTILS_CPP_CONCEPTS_HPP
diff --git a/test/buildtool/build_engine/base_maps/directory_map.test.cpp b/test/buildtool/build_engine/base_maps/directory_map.test.cpp
index 20ddae06..3eac9a4c 100644
--- a/test/buildtool/build_engine/base_maps/directory_map.test.cpp
+++ b/test/buildtool/build_engine/base_maps/directory_map.test.cpp
@@ -49,8 +49,8 @@ TEST_CASE("simple usage") {
     bool as_expected{false};
     auto name = ModuleName{"", "."};
     auto consumer = [&as_expected](auto values) {
-        if (values[0]->Contains("file") &&
-            not values[0]->Contains("does_not_exist")) {
+        if (values[0]->ContainsFile("file") &&
+            not values[0]->ContainsFile("does_not_exist")) {
             as_expected = true;
         };
     };
diff --git a/test/buildtool/file_system/TARGETS b/test/buildtool/file_system/TARGETS
index c7fe3bda..25189a5c 100644
--- a/test/buildtool/file_system/TARGETS
+++ b/test/buildtool/file_system/TARGETS
@@ -37,10 +37,28 @@
     ]
   , "stage": ["test", "buildtool", "file_system"]
   }
+, "directory_entries":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["directory_entries"]
+  , "srcs": ["directory_entries.test.cpp"]
+  , "data": ["test_data"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["test/utils", "container_matchers"]
+    , ["src/buildtool/common", "artifact_description"]
+    , ["src/buildtool/file_system", "file_root"]
+    ]
+  , "stage": ["test", "buildtool", "file_system"]
+  }
 , "test_data":
   { "type": ["@", "rules", "data", "staged"]
   , "srcs":
-    ["data/empty_executable", "data/example_file", "data/test_repo.bundle"]
+    [ "data/empty_executable"
+    , "data/example_file"
+    , "data/test_repo.bundle"
+    , "data/subdir/nested_file"
+    ]
   , "stage": ["test", "buildtool", "file_system"]
   }
 , "TESTS":
diff --git a/test/buildtool/file_system/data/subdir/nested_file b/test/buildtool/file_system/data/subdir/nested_file
new file mode 100644
index 00000000..b1a17ba1
--- /dev/null
+++ b/test/buildtool/file_system/data/subdir/nested_file
@@ -0,0 +1 @@
+zzz
diff --git a/test/buildtool/file_system/directory_entries.test.cpp b/test/buildtool/file_system/directory_entries.test.cpp
new file mode 100644
index 00000000..ed32ff65
--- /dev/null
+++ b/test/buildtool/file_system/directory_entries.test.cpp
@@ -0,0 +1,121 @@
+#include <atomic>
+#include <thread>
+
+#include "catch2/catch.hpp"
+#include "src/buildtool/common/artifact_description.hpp"
+#include "src/buildtool/file_system/file_root.hpp"
+#include "test/utils/container_matchers.hpp"
+
+namespace {
+
+auto const kBundlePath =
+    std::string{"test/buildtool/file_system/data/test_repo.bundle"};
+auto const kTreeId = std::string{"e51a219a27b672ccf17abec7d61eb4d6e0424140"};
+auto const kFooId = std::string{"19102815663d23f8b75a47e7a01965dcdc96468c"};
+auto const kBarId = std::string{"ba0e162e1c47469e3fe4b393a8bf8c569f302116"};
+
+[[nodiscard]] auto GetTestDir() -> std::filesystem::path {
+    auto* tmp_dir = std::getenv("TEST_TMPDIR");
+    if (tmp_dir != nullptr) {
+        return tmp_dir;
+    }
+    return FileSystemManager::GetCurrentDirectory() /
+           "test/buildtool/file_system";
+}
+
+[[nodiscard]] auto CreateTestRepo(bool do_checkout = false)
+    -> std::optional<std::filesystem::path> {
+    static std::atomic<int> counter{};
+    auto repo_path =
+        GetTestDir() / "test_repo" /
+        std::filesystem::path{std::to_string(counter++)}.filename();
+    auto cmd = fmt::format("git clone {}{} {}",
+                           do_checkout ? "--branch master " : "",
+                           kBundlePath,
+                           repo_path.string());
+    if (std::system(cmd.c_str()) == 0) {
+        return repo_path;
+    }
+    return std::nullopt;
+}
+
+}  // namespace
+
+TEST_CASE("Get entries of a directory", "[directory_entries]") {
+    const std::unordered_set<std::string> reference_entries{
+        "test_repo.bundle", "empty_executable", "subdir", "example_file"};
+
+    const auto dir = std::filesystem::path("test/buildtool/file_system/data");
+
+    auto fs_root = FileRoot();
+    auto dir_entries = fs_root.ReadDirectory(dir);
+    CHECK(dir_entries.ContainsFile("test_repo.bundle"));
+    CHECK(dir_entries.ContainsFile("empty_executable"));
+    CHECK(dir_entries.ContainsFile("example_file"));
+    {
+        // all the entries returned by FilesIterator are files,
+        // are contained in reference_entries,
+        // and are 3
+        auto counter = 0;
+        for (const auto& x : dir_entries.FilesIterator()) {
+            REQUIRE(reference_entries.contains(x));
+            CHECK(dir_entries.ContainsFile(x));
+            ++counter;
+        }
+
+        CHECK(counter == 3);
+    }
+    {
+        // all the entries returned by DirectoriesIterator are not files (e.g.,
+        // trees),
+        // are contained in reference_entries,
+        // and are 1
+
+        auto counter = 0;
+        for (const auto& x : dir_entries.DirectoriesIterator()) {
+            REQUIRE(reference_entries.contains(x));
+            CHECK_FALSE(dir_entries.ContainsFile(x));
+            ++counter;
+        }
+
+        CHECK(counter == 1);
+    }
+}
+
+TEST_CASE("Get entries of a git tree", "[directory_entries]") {
+    auto reference_entries =
+        std::unordered_set<std::string>{"foo", "bar", "baz", ".git"};
+    auto repo = *CreateTestRepo(true);
+    auto fs_root = FileRoot();
+    auto dir_entries = fs_root.ReadDirectory(repo);
+    CHECK(dir_entries.ContainsFile("bar"));
+    CHECK(dir_entries.ContainsFile("foo"));
+    CHECK_FALSE(dir_entries.ContainsFile("baz"));
+    {
+        // all the entries returned by FilesIterator are files,
+        // are contained in reference_entries,
+        // and are 2 (foo, and bar)
+        auto counter = 0;
+        for (const auto& x : dir_entries.FilesIterator()) {
+            REQUIRE(reference_entries.contains(x));
+            CHECK(dir_entries.ContainsFile(x));
+            ++counter;
+        }
+
+        CHECK(counter == 2);
+    }
+    {
+        // all the entries returned by DirectoriesIterator are not files (e.g.,
+        // trees),
+        // are contained in reference_entries,
+        // and are 2 (baz, and .git)
+        auto counter = 0;
+        for (const auto& x : dir_entries.DirectoriesIterator()) {
+            REQUIRE(reference_entries.contains(x));
+            CHECK_FALSE(dir_entries.ContainsFile(x));
+            ++counter;
+        }
+
+        CHECK(counter == 2);
+    }
+}
diff --git a/test/buildtool/file_system/file_root.test.cpp b/test/buildtool/file_system/file_root.test.cpp
index b0dad5d1..b776b5e3 100644
--- a/test/buildtool/file_system/file_root.test.cpp
+++ b/test/buildtool/file_system/file_root.test.cpp
@@ -64,12 +64,12 @@ void TestFileRootReadEntries(FileRoot const& root,
     auto entries = root.ReadDirectory(path);
 
     CHECK_FALSE(entries.Empty());
-    CHECK(entries.Contains("foo"));
-    CHECK(entries.Contains("bar"));
+    CHECK(entries.ContainsFile("foo"));
+    CHECK(entries.ContainsFile("bar"));
     if (has_baz) {
-        CHECK(entries.Contains("baz"));
+        CHECK_FALSE(entries.ContainsFile("baz"));
     }
-    CHECK_FALSE(entries.Contains("does_not_exist"));
+    CHECK_FALSE(entries.ContainsFile("does_not_exist"));
 }
 
 void TestFileRootReadDirectory(FileRoot const& root) {