summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/buildtool/execution_engine/dag/dag.hpp67
-rw-r--r--test/buildtool/execution_engine/dag/TARGETS1
-rw-r--r--test/buildtool/execution_engine/dag/dag.test.cpp87
3 files changed, 82 insertions, 73 deletions
diff --git a/src/buildtool/execution_engine/dag/dag.hpp b/src/buildtool/execution_engine/dag/dag.hpp
index d5c96b2e..e5f81308 100644
--- a/src/buildtool/execution_engine/dag/dag.hpp
+++ b/src/buildtool/execution_engine/dag/dag.hpp
@@ -18,7 +18,6 @@
#include <algorithm>
#include <atomic>
#include <cstddef>
-#include <cstdint>
#include <map>
#include <memory>
#include <optional>
@@ -49,13 +48,11 @@ class DirectedAcyclicGraph {
/// \brief Abstract class for DAG nodes.
/// \tparam T_Content Type of content.
/// \tparam T_Other Type of neighboring nodes.
- /// Sub classes need to implement \ref IsValid method.
/// TODO: once we have hashes, require sub classes to implement generating
/// IDs depending on its unique content.
template <typename T_Content, typename T_Other>
class Node {
public:
- using Id = std::uintptr_t;
using OtherNode = T_Other;
using OtherNodePtr = gsl::not_null<OtherNode*>;
@@ -76,11 +73,7 @@ class DirectedAcyclicGraph {
Node(Node&&) = delete;
auto operator=(Node const&) -> Node& = delete;
auto operator=(Node&&) -> Node& = delete;
-
- [[nodiscard]] auto NodeId() const noexcept -> Id {
- // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
- return reinterpret_cast<Id>(this);
- }
+ ~Node() = default;
[[nodiscard]] auto Content() const& noexcept -> T_Content const& {
return content_;
@@ -120,9 +113,6 @@ class DirectedAcyclicGraph {
return true;
}
- [[nodiscard]] virtual auto IsValid() const noexcept -> bool = 0;
- virtual ~Node() noexcept = default;
-
private:
T_Content content_{};
std::vector<OtherNodePtr> parents_{};
@@ -179,37 +169,6 @@ class DirectedAcyclicGraph {
std::atomic<bool> is_queued_to_be_processed_{false};
std::atomic<bool> is_required_{false};
};
-
- protected:
- template <typename T_Node>
- // NOLINTNEXTLINE(misc-no-recursion)
- [[nodiscard]] static auto check_validity(
- gsl::not_null<T_Node*> node) noexcept -> bool {
- // Check node-specified validity (e.g. bipartiteness requirements)
- if (!node->IsValid()) {
- return false;
- }
-
- // Search for cycles
- thread_local std::vector<typename T_Node::Id> stack{};
- for (auto const& child : node->Children()) {
- auto node_id = child->NodeId();
-
- if (std::find(stack.begin(), stack.end(), node_id) != stack.end()) {
- return false;
- }
-
- stack.push_back(node_id);
- bool valid = check_validity(child);
- stack.pop_back();
-
- if (!valid) {
- return false;
- }
- }
-
- return true;
- }
};
class DependencyGraph : DirectedAcyclicGraph {
@@ -292,7 +251,7 @@ class DependencyGraph : DirectedAcyclicGraph {
};
/// \brief Action node (bipartite)
- /// Cannot be entry (see \ref IsValid).
+ /// Cannot be entry.
class ActionNode final : public Node<Action, ArtifactNode> {
using base = Node<Action, ArtifactNode>;
@@ -313,11 +272,6 @@ class DependencyGraph : DirectedAcyclicGraph {
return std::make_unique<ActionNode>(std::move(content));
}
- // only valid if it has parents
- [[nodiscard]] auto IsValid() const noexcept -> bool final {
- return (!base::Parents().empty());
- }
-
[[nodiscard]] auto AddOutputFile(
NamedOtherNodePtr const& output) noexcept -> bool {
base::AddParent(output.node);
@@ -474,8 +428,7 @@ class DependencyGraph : DirectedAcyclicGraph {
};
/// \brief Artifact node (bipartite)
- /// Can be entry or leaf (see \ref IsValid) and can only have single child
- /// (see \ref AddChild)
+ /// Can be entry or leaf and can only have single child (see \ref AddChild)
class ArtifactNode final : public Node<Artifact, ActionNode> {
using base = Node<Artifact, ActionNode>;
@@ -510,10 +463,6 @@ class DependencyGraph : DirectedAcyclicGraph {
return base::AddParent(action);
}
- [[nodiscard]] auto IsValid() const noexcept -> bool final {
- return base::Children().size() <= 1;
- }
-
[[nodiscard]] auto HasBuilderAction() const noexcept -> bool {
return !base::Children().empty();
}
@@ -572,16 +521,6 @@ class DependencyGraph : DirectedAcyclicGraph {
[[nodiscard]] auto ArtifactWithId(
ArtifactIdentifier const& id) const noexcept -> std::optional<Artifact>;
- [[nodiscard]] auto IsValid() const noexcept -> bool {
- return std::all_of(
- artifact_nodes_.begin(),
- artifact_nodes_.end(),
- [](auto const& node) {
- return DirectedAcyclicGraph::check_validity<
- std::remove_reference_t<decltype(*node)>>(&(*node));
- });
- }
-
private:
// List of action nodes we already created
std::vector<ActionNode::Ptr> action_nodes_{};
diff --git a/test/buildtool/execution_engine/dag/TARGETS b/test/buildtool/execution_engine/dag/TARGETS
index 31bc55cd..ea37af31 100644
--- a/test/buildtool/execution_engine/dag/TARGETS
+++ b/test/buildtool/execution_engine/dag/TARGETS
@@ -5,6 +5,7 @@
, "private-deps":
[ ["@", "catch2", "", "catch2"]
, ["", "catch-main"]
+ , ["@", "gsl", "", "gsl"]
, ["utils", "container_matchers"]
, ["@", "src", "src/buildtool/common", "action_description"]
, ["@", "src", "src/buildtool/common", "artifact_factory"]
diff --git a/test/buildtool/execution_engine/dag/dag.test.cpp b/test/buildtool/execution_engine/dag/dag.test.cpp
index ad819e43..279c0683 100644
--- a/test/buildtool/execution_engine/dag/dag.test.cpp
+++ b/test/buildtool/execution_engine/dag/dag.test.cpp
@@ -13,11 +13,14 @@
// limitations under the License.
#include <cstddef>
+#include <cstdint>
#include <map>
#include <string>
+#include <unordered_set>
#include <vector>
#include "catch2/catch_test_macros.hpp"
+#include "gsl/gsl"
#include "src/buildtool/common/action.hpp"
#include "src/buildtool/common/action_description.hpp"
#include "src/buildtool/common/artifact_factory.hpp"
@@ -25,6 +28,10 @@
#include "src/buildtool/execution_engine/dag/dag.hpp"
#include "test/utils/container_matchers.hpp"
+namespace {
+[[nodiscard]] auto IsValidGraph(DependencyGraph const& graph) noexcept -> bool;
+}
+
/// \brief Checks that each artifact with identifier in output_ids has been
/// added to the graph and that its builder action has id action_id, and that
/// all outputs of actions are those the ids of which are listed in output_ids
@@ -78,7 +85,7 @@ void CheckLocalArtifactsCorrectlyAdded(
TEST_CASE("Empty Dependency Graph", "[dag]") {
DependencyGraph g;
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
}
TEST_CASE("AddAction({single action, single output, no inputs})", "[dag]") {
@@ -88,7 +95,7 @@ TEST_CASE("AddAction({single action, single output, no inputs})", "[dag]") {
DependencyGraph g;
CHECK(g.AddAction(action_description));
CheckOutputNodesCorrectlyAdded(g, action_id, {"out"});
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
}
TEST_CASE("AddAction({single action, more outputs, no inputs})", "[dag]") {
@@ -102,7 +109,7 @@ TEST_CASE("AddAction({single action, more outputs, no inputs})", "[dag]") {
DependencyGraph g;
CHECK(g.AddAction(action_description));
CheckOutputNodesCorrectlyAdded(g, action_id, output_files);
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
}
TEST_CASE("AddAction({single action, single output, source file})", "[dag]") {
@@ -141,7 +148,7 @@ TEST_CASE("AddAction({single action, single output, source file})", "[dag]") {
ArtifactFactory::Identifier(
ArtifactFactory::DescribeActionArtifact(
action_id, "executable"))}));
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
}
TEST_CASE("AddAction({single action, single output, no inputs, env_variables})",
@@ -171,7 +178,7 @@ TEST_CASE("AddAction({single action, single output, no inputs, env_variables})",
{ArtifactFactory::Identifier(
ArtifactFactory::DescribeActionArtifact(action_id,
"greeting"))}));
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
}
TEST_CASE("Add executable and library", "[dag]") {
@@ -207,7 +214,7 @@ TEST_CASE("Add executable and library", "[dag]") {
DependencyGraph g;
auto check_exec = [&]() {
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
CheckOutputNodesCorrectlyAdded(g, make_exec_id, {"exec"});
CheckInputNodesCorrectlyAdded(g, make_exec_id, {main_id, lib_a_id});
CheckLocalArtifactsCorrectlyAdded(g, {main_id}, {"main.cpp"});
@@ -216,7 +223,7 @@ TEST_CASE("Add executable and library", "[dag]") {
};
auto check_lib = [&]() {
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
CheckOutputNodesCorrectlyAdded(g, make_lib_id, {"lib.a"});
CheckInputNodesCorrectlyAdded(g, make_lib_id, {lib_hpp_id, lib_cpp_id});
CheckLocalArtifactsCorrectlyAdded(
@@ -287,7 +294,7 @@ TEST_CASE("Adding cyclic dependencies produces invalid graph", "[dag]") {
DependencyGraph g;
CHECK(g.Add({action1_desc, action2_desc}));
- CHECK(not g.IsValid());
+ CHECK(not IsValidGraph(g));
}
TEST_CASE("Error when adding an action with an id already added", "[dag]") {
@@ -298,7 +305,7 @@ TEST_CASE("Error when adding an action with an id already added", "[dag]") {
DependencyGraph g;
CHECK(g.AddAction(action_desc));
CheckOutputNodesCorrectlyAdded(g, action_id, {"out"});
- CHECK(g.IsValid());
+ CHECK(IsValidGraph(g));
CHECK(not g.AddAction(action_desc));
}
@@ -311,3 +318,65 @@ TEST_CASE("Error when adding conflicting output files and directories",
DependencyGraph g;
CHECK_FALSE(g.AddAction(action_desc));
}
+
+namespace {
+[[nodiscard]] auto IsValidNode(
+ DependencyGraph::ArtifactNode const& node) noexcept -> bool {
+ return node.Children().size() <= 1;
+}
+
+[[nodiscard]] auto IsValidNode(DependencyGraph::ActionNode const& node) noexcept
+ -> bool {
+ return not node.Parents().empty();
+}
+
+template <typename TNode>
+// NOLINTNEXTLINE(misc-no-recursion)
+[[nodiscard]] auto IsValidNode(
+ TNode const& node,
+ gsl::not_null<std::unordered_set<std::uintptr_t>*> const& seen) -> bool {
+ // Check the node hasn't been met yet (cycles check):
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ auto const node_id = reinterpret_cast<std::uintptr_t>(&node);
+ auto [it, inserted] = seen->insert(node_id);
+ if (not inserted) {
+ return false;
+ }
+
+ // Check the validity of the node and all children:
+ if (not IsValidNode(node)) {
+ return false;
+ }
+ for (auto const& child : node.Children()) {
+ if (not IsValidNode(*child, seen)) {
+ return false;
+ }
+ }
+
+ seen->erase(it);
+ return true;
+}
+
+[[nodiscard]] auto IsValidGraph(DependencyGraph const& graph) noexcept -> bool {
+ std::unordered_set<std::uintptr_t> seen{};
+ for (auto const& id : graph.ArtifactIdentifiers()) {
+ DependencyGraph::ArtifactNode const* node =
+ graph.ArtifactNodeWithId(id);
+
+ try {
+ // Check the node exists and is valid:
+ if (node == nullptr or not IsValidNode(*node, &seen)) {
+ return false;
+ }
+ } catch (...) {
+ return false;
+ }
+
+ // There must be no pending nodes:
+ if (not seen.empty()) {
+ return false;
+ }
+ }
+ return true;
+}
+} // namespace
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-05 23:31:40 +0000