diff options
Diffstat (limited to 'src')
3 files changed, 206 insertions, 81 deletions
diff --git a/src/buildtool/execution_engine/tree_operations/TARGETS b/src/buildtool/execution_engine/tree_operations/TARGETS index 0dd9e602..72b9eb23 100644 --- a/src/buildtool/execution_engine/tree_operations/TARGETS +++ b/src/buildtool/execution_engine/tree_operations/TARGETS @@ -7,11 +7,12 @@ [ ["src/buildtool/common", "common"] , ["src/buildtool/crypto", "hash_function"] , ["src/buildtool/execution_api/common", "common"] + , ["src/buildtool/multithreading", "async_map_consumer"] , ["src/utils/cpp", "expected"] + , ["src/utils/cpp", "hash_combine"] ] , "private-deps": [ ["@", "fmt", "", "fmt"] - , ["@", "gsl", "", "gsl"] , ["@", "json", "", "json"] , ["@", "protoc", "", "libprotobuf"] , ["src/buildtool/common", "artifact_blob"] @@ -21,6 +22,7 @@ , ["src/buildtool/file_system", "object_type"] , ["src/buildtool/logging", "log_level"] , ["src/buildtool/logging", "logging"] + , ["src/buildtool/multithreading", "task_system"] , ["src/utils/cpp", "hex_string"] ] , "stage": ["src", "buildtool", "execution_engine", "tree_operations"] diff --git a/src/buildtool/execution_engine/tree_operations/tree_operations_utils.cpp b/src/buildtool/execution_engine/tree_operations/tree_operations_utils.cpp index 88e828bd..a650d88f 100644 --- a/src/buildtool/execution_engine/tree_operations/tree_operations_utils.cpp +++ b/src/buildtool/execution_engine/tree_operations/tree_operations_utils.cpp @@ -16,13 +16,13 @@ #include <cstddef> #include <functional> +#include <memory> +#include <type_traits> // for remove_reference #include <unordered_set> -#include <utility> #include <vector> #include "fmt/core.h" #include "google/protobuf/repeated_ptr_field.h" -#include "gsl/gsl" #include "nlohmann/json.hpp" #include "src/buildtool/common/artifact_blob.hpp" #include "src/buildtool/common/artifact_digest_factory.hpp" @@ -32,6 +32,7 @@ #include "src/buildtool/file_system/object_type.hpp" #include "src/buildtool/logging/log_level.hpp" #include "src/buildtool/logging/logger.hpp" +#include "src/buildtool/multithreading/task_system.hpp" #include "src/utils/cpp/hex_string.hpp" auto TreeOperationsUtils::ParseBazelDirectory( @@ -248,91 +249,170 @@ auto TreeOperationsUtils::WriteTree(IExecutionApi const& api, return unexpected{fmt::format("Failed to upload tree blob")}; } -auto TreeOperationsUtils::ComputeTreeOverlay( - IExecutionApi const& api, - Artifact::ObjectInfo const& base_tree_info, - Artifact::ObjectInfo const& other_tree_info, - bool disjoint, - std::filesystem::path const& where) noexcept - -> expected<Artifact::ObjectInfo, std::string> { - // Ensure that both objects are actually trees. - Ensures(IsTreeObject(base_tree_info.type) and - IsTreeObject(other_tree_info.type)); - - Logger::Log(LogLevel::Trace, - "Tree overlay {} vs {}", - base_tree_info.ToString(), - other_tree_info.ToString()); - - // Early return if both trees are the same. - if (base_tree_info == other_tree_info) { - return base_tree_info; - } +auto TreeOperationsUtils::CreateTreeOverlayMap(IExecutionApi const& api, + bool disjoint) noexcept + -> AsyncMapConsumer<TreePair, Artifact::ObjectInfo> { + auto value_creator = [&api, disjoint](auto /*unused*/, + auto const& setter, + auto const& logger, + auto const& subcaller, + auto const& key) { + auto const& base_tree_info = key.trees.first; + auto const& other_tree_info = key.trees.second; - // Read base tree. - auto base_tree = ReadTree(api, base_tree_info); - if (not base_tree) { - return unexpected{base_tree.error()}; - } + Logger::Log(LogLevel::Trace, + "Compute tree overlay:\n - {}\n - {}", + base_tree_info.ToString(), + other_tree_info.ToString()); - // Read other tree. - auto other_tree = ReadTree(api, other_tree_info); - if (not other_tree) { - return unexpected{other_tree.error()}; - } + // Wrap logger for this tree-overlay computation. + auto new_logger = std::make_shared<AsyncMapConsumerLogger>( + [logger, base_tree_info, other_tree_info](auto const& msg, + auto fatal) { + (*logger)(fmt::format("While merging the trees:\n - {}\n " + "- {}\n{}", + base_tree_info.ToString(), + other_tree_info.ToString(), + msg), + fatal); + }); - // Compute tree overlay. - TreeEntries overlay_tree{*other_tree}; // Make a copy of other tree. - for (auto const& [base_name, base_entry] : *base_tree) { - auto it = overlay_tree.find(base_name); - if (it == overlay_tree.end()) { - // No naming conflict detected, add entry to the other tree. - overlay_tree.insert({base_name, base_entry}); - continue; + // Ensure that both objects are actually trees. + if (not IsTreeObject(base_tree_info.type) or + not IsTreeObject(other_tree_info.type)) { + (*new_logger)(fmt::format("Both objects have to be trees."), + /*fatal=*/true); + return; } - if (it->second.info == base_entry.info) { - // Naming conflict detected, but names point to the same - // object, no conflict. - continue; + // Early return if both trees are the same. + if (base_tree_info == other_tree_info) { + (*setter)(Artifact::ObjectInfo{base_tree_info}); + return; } - // Naming conflict detected and names point to different - // objects. - if (IsTreeObject(base_entry.info.type) and - IsTreeObject(it->second.info.type)) { - // If both objects are trees, recursively compute tree overlay. - auto tree_info = ComputeTreeOverlay(api, - base_entry.info, - it->second.info, - disjoint, - where / base_name); - if (not tree_info) { - return unexpected{tree_info.error()}; - } - overlay_tree[base_name] = TreeEntry{.info = *std::move(tree_info)}; - continue; + // Read base tree. + auto base_tree = ReadTree(api, base_tree_info); + if (not base_tree) { + (*new_logger)(base_tree.error(), /*fatal=*/true); + return; } - // If both objects are not trees, actual conflict detected. - if (disjoint) { - return unexpected{ - fmt::format("Conflict at path {}:\ndifferent objects {} vs {}", - nlohmann::json((where / base_name).string()).dump(), - base_entry.info.ToString(), - it->second.info.ToString())}; + // Read other tree. + auto other_tree = ReadTree(api, other_tree_info); + if (not other_tree) { + (*new_logger)(other_tree.error(), /*fatal=*/true); + return; } - // Ignore conflict, keep entry from other tree. - } + // Compute tree overlay. If two trees conflict, collect them and + // process them in the subcaller. + TreeEntries overlay_tree{*other_tree}; // Make a copy of other tree. + std::vector<TreePair> keys{}; + std::vector<std::string> base_names{}; + auto min_size = std::min(base_tree->size(), other_tree->size()); + keys.reserve(min_size); + base_names.reserve(min_size); + for (auto& [base_name, base_entry] : *base_tree) { + auto it = overlay_tree.find(base_name); + if (it == overlay_tree.end()) { + // No naming conflict detected, add entry to the other + // tree. + overlay_tree[std::move(base_name)] = std::move(base_entry); + continue; + } + + if (it->second.info == base_entry.info) { + // Naming conflict detected, but names point to the same + // object, no conflict. + continue; + } + + // Naming conflict detected and names point to different + // objects. + if (IsTreeObject(base_entry.info.type) and + IsTreeObject(it->second.info.type)) { + // If both objects are trees, compute tree overlay in + // the subcaller. + keys.emplace_back(std::make_pair(std::move(base_entry.info), + std::move(it->second.info))); + base_names.emplace_back(std::move(base_name)); + continue; + } - // Write tree overlay. - auto overlay_tree_info = WriteTree(api, overlay_tree); - if (not overlay_tree_info) { - return unexpected{overlay_tree_info.error()}; + // If both objects are not trees, actual conflict detected. + if (disjoint) { + (*new_logger)(fmt::format("Naming conflict detected at path " + "{}:\n - {}\n - {}", + nlohmann::json(base_name).dump(), + base_entry.info.ToString(), + it->second.info.ToString()), + /*fatal=*/true); + return; + } + + // Ignore conflict, keep entry from other tree. + } + + (*subcaller)( + keys, + [setter, + new_logger, + &api, + base_names = std::move(base_names), + partial_overlay_tree = + std::move(overlay_tree)](auto const& values) { + // Insert computed tree overlays into tree-overlay + // entries. + TreeEntries overlay_tree{partial_overlay_tree}; + for (size_t i = 0; i < values.size(); ++i) { + // Create copy of the value. + overlay_tree[base_names[i]] = + TreeEntry{.info = *(values[i])}; + } + + // Write tree overlay. + auto overlay_tree_info = WriteTree(api, overlay_tree); + if (not overlay_tree_info) { + (*new_logger)(overlay_tree_info.error(), /*fatal=*/true); + return; + } + + Logger::Log(LogLevel::Trace, + "Tree-overlay result: {}", + overlay_tree_info->ToString()); + + (*setter)(*std::move(overlay_tree_info)); + }, + new_logger); + }; + + return AsyncMapConsumer<TreePair, Artifact::ObjectInfo>{value_creator}; +} + +auto TreeOperationsUtils::ComputeTreeOverlay( + IExecutionApi const& api, + Artifact::ObjectInfo const& base_tree_info, + Artifact::ObjectInfo const& other_tree_info, + bool disjoint) noexcept -> expected<Artifact::ObjectInfo, std::string> { + + auto tree_overlay_map = CreateTreeOverlayMap(api, disjoint); + Artifact::ObjectInfo result{}; + std::string failed_msg{}; + bool failed{false}; + { + TaskSystem ts{1}; + tree_overlay_map.ConsumeAfterKeysReady( + &ts, + {TreePair{std::make_pair(base_tree_info, other_tree_info)}}, + [&result](auto const& values) { result = *values[0]; }, + [&failed_msg, &failed](auto const& msg, auto fatal) { + failed_msg = msg; + failed = fatal; + }); + } + if (failed) { + return unexpected{failed_msg}; } - Logger::Log(LogLevel::Trace, - "Tree overlay result: {}", - overlay_tree_info->ToString()); - return overlay_tree_info; + return result; } diff --git a/src/buildtool/execution_engine/tree_operations/tree_operations_utils.hpp b/src/buildtool/execution_engine/tree_operations/tree_operations_utils.hpp index 072ce8c8..52079d93 100644 --- a/src/buildtool/execution_engine/tree_operations/tree_operations_utils.hpp +++ b/src/buildtool/execution_engine/tree_operations/tree_operations_utils.hpp @@ -15,16 +15,25 @@ #ifndef INCLUDED_SRC_BUILDTOOL_EXECUTION_ENGINE_TREE_OPERATIONS_TREE_OPERATIONS_UTILS_HPP #define INCLUDED_SRC_BUILDTOOL_EXECUTION_ENGINE_TREE_OPERATIONS_TREE_OPERATIONS_UTILS_HPP -#include <filesystem> +#include <cstddef> +#include <functional> #include <optional> #include <string> #include <unordered_map> +#include <utility> #include "src/buildtool/common/artifact.hpp" #include "src/buildtool/common/artifact_digest.hpp" #include "src/buildtool/crypto/hash_function.hpp" #include "src/buildtool/execution_api/common/execution_api.hpp" +#include "src/buildtool/multithreading/async_map_consumer.hpp" #include "src/utils/cpp/expected.hpp" +#include "src/utils/cpp/hash_combine.hpp" + +namespace std { +template <typename> +struct hash; +} /// \brief Utility functions for tree operations. class TreeOperationsUtils final { @@ -51,9 +60,7 @@ class TreeOperationsUtils final { IExecutionApi const& api, Artifact::ObjectInfo const& base_tree_info, Artifact::ObjectInfo const& other_tree_info, - bool disjoint, - std::filesystem::path const& where = std::filesystem::path{}) noexcept - -> expected<Artifact::ObjectInfo, std::string>; + bool disjoint) noexcept -> expected<Artifact::ObjectInfo, std::string>; [[nodiscard]] static auto ReadTree( IExecutionApi const& api, @@ -66,6 +73,18 @@ class TreeOperationsUtils final { -> expected<Artifact::ObjectInfo, std::string>; private: + struct TreePair { + std::pair<Artifact::ObjectInfo, Artifact::ObjectInfo> trees; + explicit TreePair( + std::pair<Artifact::ObjectInfo, Artifact::ObjectInfo> trees) + : trees{std::move(trees)} {} + [[nodiscard]] auto operator==(TreePair const& other) const noexcept + -> bool { + return trees == other.trees; + } + }; + friend struct std::hash<TreePair>; + [[nodiscard]] static auto ParseBazelDirectory( std::string const& tree_data, HashFunction::Type hash_type) noexcept -> std::optional<TreeEntries>; @@ -80,6 +99,30 @@ class TreeOperationsUtils final { [[nodiscard]] static auto SerializeGitTree( TreeEntries const& tree_entries) noexcept -> std::optional<std::string>; + + /// \brief Creates an async map consumer that maps a pair of trees + /// to their corresponding overlay tree. + /// \param api The execution API to be used. + /// \param disjoint If true, abort the computation if a + /// conflict is encountered, otherwise the conflict is ignored and + /// the entry from the second tree wins. + /// \returns The async map consumer. + [[nodiscard]] static auto CreateTreeOverlayMap(IExecutionApi const& api, + bool disjoint) noexcept + -> AsyncMapConsumer<TreePair, Artifact::ObjectInfo>; +}; + +namespace std { +template <> +struct hash<TreeOperationsUtils::TreePair> { + [[nodiscard]] auto operator()(TreeOperationsUtils::TreePair const& pair) + const noexcept -> std::size_t { + std::size_t seed{}; + hash_combine(&seed, pair.trees.first); + hash_combine(&seed, pair.trees.second); + return seed; + } }; +} // namespace std #endif // INCLUDED_SRC_BUILDTOOL_EXECUTION_ENGINE_TREE_OPERATIONS_TREE_OPERATIONS_UTILS_HPP |