From d9c3bee2250c2f22dbabb765bd006e9a7c224627 Mon Sep 17 00:00:00 2001 From: Klaus Aehlig Date: Fri, 17 Jun 2022 12:13:34 +0200 Subject: Correctly serialize and deserialize results and nodes So far, our serialisation and deserialisation assumed that no node or result values are included contained in the given value. However, for nodes (and hence ressults, given our implementation of value nodes) there is a legitimate use case. An abstract interface specification, given by provided nodes, can well be a meaningful target to be exported. Implement serialisation for those values. Also, avoid tree-unfolding the value when deserialising the value by appropriately caching the corresponding expression pointers. Moreover, avoid the quadratic overhead through linearly searching through the list of artifacts. --- .../build_engine/expression/target_result.cpp | 205 ++++++++++++++++++--- 1 file changed, 178 insertions(+), 27 deletions(-) (limited to 'src/buildtool/build_engine/expression/target_result.cpp') diff --git a/src/buildtool/build_engine/expression/target_result.cpp b/src/buildtool/build_engine/expression/target_result.cpp index 9be45a5f..075a30fb 100644 --- a/src/buildtool/build_engine/expression/target_result.cpp +++ b/src/buildtool/build_engine/expression/target_result.cpp @@ -1,6 +1,7 @@ #include "src/buildtool/build_engine/expression/target_result.hpp" #include +#include #include #include "gsl-lite/gsl-lite.hpp" @@ -32,11 +33,18 @@ namespace { return expr->ToJson(); } +// forward declare as we have mutually recursive functions +auto SerializeTargetResultWithReplacement( + TargetResult const& result, + std::unordered_map const& + replacements = {}) -> nlohmann::json; + // Serialize arbitrary expression to JSON. This and any sub-expressions will be // collected in `nodes`. Any possible duplicate will be collected only once. As // pure JSON values can coincide with our JSON encoding of artifacts, the hash // of artifact expressions is recorded in `provided_artifacts` to differentiate -// them from non-artifacts. If replacements is set, replace any contained +// them from non-artifacts. Similarly for result and node values. +// If replacements is set, replace any contained // non-known artifact by known artifact from replacement. Throws runtime_error // if no replacement is found. // NOLINTNEXTLINE(misc-no-recursion) @@ -44,6 +52,8 @@ namespace { gsl::not_null*> const& nodes, gsl::not_null*> const& provided_artifacts, + gsl::not_null*> const& provided_nodes, + gsl::not_null*> const& provided_results, ExpressionPtr const& expr, std::unordered_map const& replacements) -> std::string { @@ -55,8 +65,12 @@ namespace { std::unordered_map hashes{}; hashes.reserve(map.size()); for (auto const& [key, val] : map) { - auto hash = SerializeExpression( - nodes, provided_artifacts, val, replacements); + auto hash = SerializeExpression(nodes, + provided_artifacts, + provided_nodes, + provided_results, + val, + replacements); hashes[key] = std::move(hash); } json = std::move(hashes); @@ -66,12 +80,53 @@ namespace { std::vector hashes{}; hashes.reserve(list.size()); for (auto const& val : list) { - auto hash = SerializeExpression( - nodes, provided_artifacts, val, replacements); + auto hash = SerializeExpression(nodes, + provided_artifacts, + provided_nodes, + provided_results, + val, + replacements); hashes.emplace_back(std::move(hash)); } json = std::move(hashes); } + else if (expr->IsNode()) { + auto const& node = expr->Node(); + provided_nodes->emplace_back(id); + if (node.IsValue()) { + auto hash = SerializeExpression(nodes, + provided_artifacts, + provided_nodes, + provided_results, + node.GetValue(), + replacements); + json = nlohmann::json{{"type", "VALUE_NODE"}, {"result", hash}}; + } + else { + auto const& data = node.GetAbstract(); + auto string_fields = SerializeExpression(nodes, + provided_artifacts, + provided_nodes, + provided_results, + data.string_fields, + replacements); + auto target_fields = SerializeExpression(nodes, + provided_artifacts, + provided_nodes, + provided_results, + data.target_fields, + replacements); + json = nlohmann::json{{"type", "ABSTRACT_NODE"}, + {"node_type", data.node_type}, + {"string_fields", string_fields}, + {"target_fields", target_fields}}; + } + } + else if (expr->IsResult()) { + provided_results->emplace_back(id); + json = SerializeTargetResultWithReplacement(expr->Result(), + replacements); + } else if (expr->IsArtifact()) { provided_artifacts->emplace_back(id); json = SerializeArtifactDescription(expr, replacements); @@ -89,52 +144,121 @@ namespace { [[nodiscard]] auto DeserializeExpression( nlohmann::json const& entry, nlohmann::json const& nodes, - nlohmann::json const& provided_artifacts) -> ExpressionPtr { - static auto contains = [](auto const& a, auto const& v) -> bool { - return std::find(a.begin(), a.end(), v) != a.end(); - }; + std::unordered_set const& provided_artifacts, + std::unordered_set const& provided_nodes, + std::unordered_set const& provided_results, + gsl::not_null*> const& sofar) + -> ExpressionPtr { + auto id = entry.get(); + + auto it = sofar->find(id); + if (it != sofar->end()) { + return it->second; + } + auto const& json = nodes.at(id); if (json.is_object()) { - if (contains(provided_artifacts, id)) { + if (provided_artifacts.contains(id)) { if (auto artifact = ArtifactDescription::FromJson(json)) { - return ExpressionPtr{*artifact}; + auto result = ExpressionPtr{*artifact}; + sofar->emplace(id, result); + return result; + } + return ExpressionPtr{nullptr}; + } + if (provided_nodes.contains(id)) { + if (json["type"] == "ABSTRACT_NODE") { + auto node_type = json["node_type"].get(); + auto target_fields = + DeserializeExpression(json["target_fields"], + nodes, + provided_artifacts, + provided_nodes, + provided_results, + sofar); + auto string_fields = + DeserializeExpression(json["string_fields"], + nodes, + provided_artifacts, + provided_nodes, + provided_results, + sofar); + auto result = ExpressionPtr{TargetNode{TargetNode::Abstract{ + node_type, string_fields, target_fields}}}; + sofar->emplace(id, result); + return result; + } + if (json["type"] == "VALUE_NODE") { + auto value = DeserializeExpression(json["result"], + nodes, + provided_artifacts, + provided_nodes, + provided_results, + sofar); + auto result = ExpressionPtr{TargetNode{value}}; + sofar->emplace(id, result); + return result; + } + return ExpressionPtr{nullptr}; + } + if (provided_results.contains(id)) { + auto result = TargetResult::FromJson(json); + if (result) { + auto result_exp = ExpressionPtr{*result}; + sofar->emplace(id, result_exp); + return result_exp; } return ExpressionPtr{nullptr}; } Expression::map_t::underlying_map_t map{}; for (auto const& [key, val] : json.items()) { - auto new_val = DeserializeExpression( - val.get(), nodes, provided_artifacts); + auto new_val = DeserializeExpression(val.get(), + nodes, + provided_artifacts, + provided_nodes, + provided_results, + sofar); if (not new_val) { return new_val; } map.emplace(key, std::move(new_val)); } - return ExpressionPtr{Expression::map_t{map}}; + auto result = ExpressionPtr{Expression::map_t{map}}; + sofar->emplace(id, result); + return result; } if (json.is_array()) { Expression::list_t list{}; list.reserve(json.size()); for (auto const& val : json) { - auto new_val = DeserializeExpression( - val.get(), nodes, provided_artifacts); + auto new_val = DeserializeExpression(val.get(), + nodes, + provided_artifacts, + provided_nodes, + provided_results, + sofar); if (not new_val) { return new_val; } list.emplace_back(std::move(new_val)); } - return ExpressionPtr{list}; + auto result = ExpressionPtr{list}; + sofar->emplace(id, result); + return result; } - return Expression::FromJson(json); + auto result = Expression::FromJson(json); + sofar->emplace(id, result); + return result; } // Serialize artifact map to JSON. If replacements is set, replace // non-known artifacts by known artifacts from replacement. Throws runtime_error // if no replacement is found. +// NOLINTNEXTLINE(misc-no-recursion) [[nodiscard]] auto SerializeArtifactMap( ExpressionPtr const& expr, std::unordered_map const& @@ -171,33 +295,59 @@ namespace { // Serialize provides map to JSON. If replacements is set, replace // non-known artifacts by known artifacts from replacement. Throws runtime_error // if no replacement is found. +// NOLINTNEXTLINE(misc-no-recursion) [[nodiscard]] auto SerializeProvidesMap( ExpressionPtr const& expr, std::unordered_map const& replacements) -> nlohmann::json { auto provided_artifacts = std::vector{}; + auto provided_nodes = std::vector{}; + auto provided_results = std::vector{}; auto nodes = std::unordered_map{}; - auto entry = - SerializeExpression(&nodes, &provided_artifacts, expr, replacements); - return nlohmann::json{ - {"entry", std::move(entry)}, - {"nodes", std::move(nodes)}, - {"provided_artifacts", std::move(provided_artifacts)}}; + auto entry = SerializeExpression(&nodes, + &provided_artifacts, + &provided_nodes, + &provided_results, + expr, + replacements); + return nlohmann::json{{"entry", std::move(entry)}, + {"nodes", std::move(nodes)}, + {"provided_artifacts", std::move(provided_artifacts)}, + {"provided_nodes", std::move(provided_nodes)}, + {"provided_results", std::move(provided_results)} + + }; +} + +auto JsonSet(nlohmann::json const& j) -> std::unordered_set { + std::unordered_set result{}; + result.reserve(j.size()); + for (auto const& it : j) { + result.emplace(it.get()); + } + return result; } +// NOLINTNEXTLINE(misc-no-recursion) [[nodiscard]] auto DeserializeProvidesMap(nlohmann::json const& json) -> ExpressionPtr { - return DeserializeExpression( - json["entry"], json["nodes"], json["provided_artifacts"]); + std::unordered_map sofar{}; + return DeserializeExpression(json["entry"], + json["nodes"], + JsonSet(json["provided_artifacts"]), + JsonSet(json["provided_nodes"]), + JsonSet(json["provided_results"]), + &sofar); } // Serialize TargetResult to JSON. If replacements is set, replace non-known // artifacts by known artifacts from replacement. Throws runtime_error if no // replacement is found. +// NOLINTNEXTLINE(misc-no-recursion) [[nodiscard]] auto SerializeTargetResultWithReplacement( TargetResult const& result, std::unordered_map const& - replacements = {}) -> nlohmann::json { + replacements) -> nlohmann::json { return nlohmann::json{ {"artifacts", SerializeArtifactMap(result.artifact_stage, replacements)}, @@ -224,6 +374,7 @@ auto TargetResult::ReplaceNonKnownAndToJson( return std::nullopt; } +// NOLINTNEXTLINE(misc-no-recursion) auto TargetResult::FromJson(nlohmann::json const& json) noexcept -> std::optional { try { -- cgit v1.2.3