export targets: Enforce the invariant when writing target cache entries

We ensure that for each export target to be written to the target
cache all its implied export targets are written to the target
cache first. This ensures that the target cache maintains its
consistency at all times with respect to export target
dependencies.

5 files changed, 177 insertions, 19 deletions

diff --git a/src/buildtool/main/TARGETS b/src/buildtool/main/TARGETS
index af2998f1..0f30619c 100644
--- a/src/buildtool/main/TARGETS
+++ b/src/buildtool/main/TARGETS
@@ -221,6 +221,8 @@
     , ["src/buildtool/common", "common"]
     , ["src/buildtool/common", "config"]
     , ["src/buildtool/execution_api/common", "common"]
+    , ["src/buildtool/multithreading", "async_map_consumer"]
+    , ["src/buildtool/multithreading", "async_map_utils"]
     , ["src/buildtool/storage", "storage"]
     ]
   , "stage": ["src", "buildtool", "main"]
diff --git a/src/buildtool/main/build_utils.cpp b/src/buildtool/main/build_utils.cpp
index 2453e5e6..ff0bbf93 100644
--- a/src/buildtool/main/build_utils.cpp
+++ b/src/buildtool/main/build_utils.cpp
@@ -15,6 +15,7 @@
 #include "src/buildtool/main/build_utils.hpp"
 #ifndef BOOTSTRAP_BUILD_TOOL
 #include "src/buildtool/logging/logger.hpp"
+#include "src/buildtool/multithreading/async_map_utils.hpp"
 #include "src/buildtool/storage/storage.hpp"
 #include "src/buildtool/storage/target_cache_entry.hpp"
 #endif  // BOOTSTRAP_BUILD_TOOL
@@ -63,6 +64,95 @@ auto ToTargetCacheWriteStrategy(std::string const& strategy)
 }
 
 #ifndef BOOTSTRAP_BUILD_TOOL
+auto CreateTargetCacheWriterMap(
+    std::unordered_map<TargetCacheKey, AnalysedTargetPtr> const& cache_targets,
+    std::unordered_map<ArtifactDescription, Artifact::ObjectInfo> const&
+        extra_infos,
+    std::size_t jobs,
+    gsl::not_null<IExecutionApi*> const& local_api,
+    gsl::not_null<IExecutionApi*> const& remote_api,
+    TargetCacheWriteStrategy strategy,
+    TargetCache<true> const& tc) -> TargetCacheWriterMap {
+    auto write_tc_entry =
+        [cache_targets, extra_infos, jobs, local_api, remote_api, strategy, tc](
+            auto /*ts*/,
+            auto setter,
+            auto logger,
+            auto subcaller,
+            auto const& key) {
+            // get the TaretCacheKey corresponding to this Id
+            TargetCacheKey tc_key{key};
+            // check if entry actually needs storing
+            if (not cache_targets.contains(tc_key)) {
+                // sanity check: if not in the map, then it must be in cache
+                if (not tc.Read(tc_key)) {
+                    (*logger)(
+                        fmt::format("Target-cache key {} is neither stored "
+                                    "nor marked for storing",
+                                    key.ToString()),
+                        /*fatal=*/true);
+                    return;
+                }
+                // entry already in target-cache, so nothing to be done
+                (*setter)(nullptr);
+                return;
+            }
+            auto const& target = cache_targets.at(tc_key);
+            auto entry = TargetCacheEntry::FromTarget(target, extra_infos);
+            if (not entry) {
+                (*logger)(
+                    fmt::format("Failed creating target cache entry for key {}",
+                                key.ToString()),
+                    /*fatal=*/true);
+                return;
+            }
+            // only store current entry once all implied targets are stored
+            if (auto implied_targets = entry->ToImpliedIds(key.digest.hash())) {
+                (*subcaller)(
+                    *implied_targets,
+                    [tc_key,
+                     entry,
+                     jobs,
+                     local_api,
+                     remote_api,
+                     strategy,
+                     tc,
+                     setter,
+                     logger]([[maybe_unused]] auto const& values) {
+                        // create parallel artifacts downloader
+                        auto downloader = [&local_api,
+                                           &remote_api,
+                                           &jobs,
+                                           strategy](auto infos) {
+                            return remote_api->ParallelRetrieveToCas(
+                                infos,
+                                local_api,
+                                jobs,
+                                strategy == TargetCacheWriteStrategy::Split);
+                        };
+                        if (not tc.Store(tc_key, *entry, downloader)) {
+                            (*logger)(fmt::format("Failed writing target cache "
+                                                  "entry for {}",
+                                                  tc_key.Id().ToString()),
+                                      /*fatal=*/true);
+                            return;
+                        }
+                        // success!
+                        (*setter)(nullptr);
+                    },
+                    logger);
+            }
+            else {
+                (*logger)(fmt::format("Failed retrieving implied targets for "
+                                      "key {}",
+                                      key.ToString()),
+                          /*fatal=*/true);
+            }
+        };
+    return AsyncMapConsumer<Artifact::ObjectInfo, std::nullptr_t>(
+        write_tc_entry, jobs);
+}
+
 void WriteTargetCacheEntries(
     std::unordered_map<TargetCacheKey, AnalysedTargetPtr> const& cache_targets,
     std::unordered_map<ArtifactDescription, Artifact::ObjectInfo> const&
@@ -80,27 +170,39 @@ void WriteTargetCacheEntries(
                     "Backing up artifacts of {} export targets",
                     cache_targets.size());
     }
-    auto downloader = [&local_api, &remote_api, &jobs, strategy](auto infos) {
-        return remote_api->ParallelRetrieveToCas(
-            infos,
-            local_api,
-            jobs,
-            strategy == TargetCacheWriteStrategy::Split);
-    };
-    for (auto const& [key, target] : cache_targets) {
-        if (auto entry = TargetCacheEntry::FromTarget(target, extra_infos)) {
-            if (not tc.Store(key, *entry, downloader)) {
+    // set up writer map
+    auto tc_writer_map = CreateTargetCacheWriterMap(
+        cache_targets, extra_infos, jobs, local_api, remote_api, strategy, tc);
+    std::vector<Artifact::ObjectInfo> cache_targets_ids;
+    cache_targets_ids.reserve(cache_targets.size());
+    for (auto const& [k, _] : cache_targets) {
+        cache_targets_ids.emplace_back(k.Id());
+    }
+    // write the target cache keys
+    bool failed{false};
+    {
+        TaskSystem ts{jobs};
+        tc_writer_map.ConsumeAfterKeysReady(
+            &ts,
+            cache_targets_ids,
+            []([[maybe_unused]] auto _) {},  // map doesn't set anything
+            [&failed](auto const& msg, bool fatal) {
                 Logger::Log(LogLevel::Warning,
-                            "Failed writing target cache entry for {}",
-                            key.Id().ToString());
-            }
-        }
-        else {
-            Logger::Log(LogLevel::Warning,
-                        "Failed creating target cache entry for {}",
-                        key.Id().ToString());
-        }
+                            "While writing target cache entries:\n{}",
+                            msg);
+                failed = failed or fatal;
+            });
     }
+    // check for failures and cycles
+    if (failed) {
+        return;
+    }
+    if (auto error = DetectAndReportCycle(
+            "writing cache targets", tc_writer_map, kObjectInfoPrinter)) {
+        Logger::Log(LogLevel::Warning, *error);
+        return;
+    }
+
     Logger::Log(LogLevel::Debug,
                 "Finished backing up artifacts of export targets");
 }
diff --git a/src/buildtool/main/build_utils.hpp b/src/buildtool/main/build_utils.hpp
index 116ef1a9..cf1c68ec 100644
--- a/src/buildtool/main/build_utils.hpp
+++ b/src/buildtool/main/build_utils.hpp
@@ -15,6 +15,7 @@
 #ifndef INCLUDED_SRC_BUILDOOL_MAIN_BUILD_UTILS_HPP
 #define INCLUDED_SRC_BUILDOOL_MAIN_BUILD_UTILS_HPP
 
+#include <functional>
 #include <map>
 #include <optional>
 #include <string>
@@ -27,7 +28,9 @@
 #ifndef BOOTSTRAP_BUILD_TOOL
 #include "gsl/gsl"
 #include "src/buildtool/common/artifact.hpp"
+#include "src/buildtool/common/artifact_digest.hpp"
 #include "src/buildtool/execution_api/common/execution_api.hpp"
+#include "src/buildtool/multithreading/async_map_consumer.hpp"
 #include "src/buildtool/storage/storage.hpp"
 #include "src/buildtool/storage/target_cache.hpp"
 #endif  // BOOTSTRAP_BUILD_TOOL
@@ -53,6 +56,29 @@ auto ToTargetCacheWriteStrategy(std::string const&)
     -> std::optional<TargetCacheWriteStrategy>;
 
 #ifndef BOOTSTRAP_BUILD_TOOL
+/// \brief Maps the Id of a TargetCacheKey to nullptr_t, as we only care if
+/// writing the tc entry succeeds or not.
+using TargetCacheWriterMap =
+    AsyncMapConsumer<Artifact::ObjectInfo, std::nullptr_t>;
+
+/// \brief Handles the writing of target cache keys after analysis concludes.
+[[nodiscard]] auto CreateTargetCacheWriterMap(
+    std::unordered_map<TargetCacheKey, AnalysedTargetPtr> const& cache_targets,
+    std::unordered_map<ArtifactDescription, Artifact::ObjectInfo> const&
+        extra_infos,
+    std::size_t jobs,
+    gsl::not_null<IExecutionApi*> const& local_api,
+    gsl::not_null<IExecutionApi*> const& remote_api,
+    TargetCacheWriteStrategy strategy = TargetCacheWriteStrategy::Sync,
+    TargetCache<true> const& tc = Storage::Instance().TargetCache())
+    -> TargetCacheWriterMap;
+
+// use explicit cast to std::function to allow template deduction when used
+static const std::function<std::string(Artifact::ObjectInfo const&)>
+    kObjectInfoPrinter = [](Artifact::ObjectInfo const& x) -> std::string {
+    return x.ToString();
+};
+
 void WriteTargetCacheEntries(
     std::unordered_map<TargetCacheKey, AnalysedTargetPtr> const& cache_targets,
     std::unordered_map<ArtifactDescription, Artifact::ObjectInfo> const&
diff --git a/src/buildtool/storage/target_cache_entry.cpp b/src/buildtool/storage/target_cache_entry.cpp
index 2f245624..becc6a13 100644
--- a/src/buildtool/storage/target_cache_entry.cpp
+++ b/src/buildtool/storage/target_cache_entry.cpp
@@ -71,6 +71,28 @@ auto TargetCacheEntry::ToImplied() const noexcept -> std::set<std::string> {
     return result;
 }
 
+auto TargetCacheEntry::ToImpliedIds(std::string const& entry_key_hash)
+    const noexcept -> std::optional<std::vector<Artifact::ObjectInfo>> {
+    std::vector<Artifact::ObjectInfo> result{};
+    if (desc_.contains("implied export targets")) {
+        try {
+            for (auto const& x : desc_["implied export targets"]) {
+                if (x != entry_key_hash) {
+                    result.emplace_back(Artifact::ObjectInfo{
+                        .digest = ArtifactDigest{x, 0, /*is_tree=*/false},
+                        .type = ObjectType::File});
+                }
+            }
+        } catch (std::exception const& ex) {
+            Logger::Log(LogLevel::Warning,
+                        "Exception reading implied export targets: {}",
+                        ex.what());
+            return std::nullopt;
+        }
+    }
+    return result;
+}
+
 [[nodiscard]] auto ToObjectInfo(nlohmann::json const& json)
     -> Artifact::ObjectInfo {
     auto const& desc = ArtifactDescription::FromJson(json);
diff --git a/src/buildtool/storage/target_cache_entry.hpp b/src/buildtool/storage/target_cache_entry.hpp
index a976dd8c..b0bd1020 100644
--- a/src/buildtool/storage/target_cache_entry.hpp
+++ b/src/buildtool/storage/target_cache_entry.hpp
@@ -50,6 +50,12 @@ class TargetCacheEntry {
     // Obtain the implied export targets
     [[nodiscard]] auto ToImplied() const noexcept -> std::set<std::string>;
 
+    // Obtain the implied export targets hashes as a vector of ObjectInfo,
+    // excluding the digest corresponding to this entry. As opposed to
+    // ToImplied, it returns nullopt on exception.
+    [[nodiscard]] auto ToImpliedIds(std::string const& entry_key_hash)
+        const noexcept -> std::optional<std::vector<Artifact::ObjectInfo>>;
+
     // Obtain all artifacts from cache entry (all should be known
     // artifacts).
     [[nodiscard]] auto ToArtifacts(