From 60a98d8af269e4d8bdcd3ccb346b5ea2342519dc Mon Sep 17 00:00:00 2001
From: SUTER Frederic <frederic.suter@cc.in2p3.fr>
Date: Fri, 24 Dec 2021 11:52:10 +0100
Subject: [PATCH] modernize cycle detection in DAGs

---
 include/simgrid/s4u/Activity.hpp |  3 +++
 src/simdag/sd_daxloader.cpp      | 36 ++++++++++++++++++++++++++++++++
 src/simdag/sd_dotloader.cpp      |  6 ++++++
 src/simdag/simdag_private.hpp    |  1 +
 4 files changed, 46 insertions(+)

diff --git a/include/simgrid/s4u/Activity.hpp b/include/simgrid/s4u/Activity.hpp
index 4ef19c2073..6b4ceaefcd 100644
--- a/include/simgrid/s4u/Activity.hpp
+++ b/include/simgrid/s4u/Activity.hpp
@@ -168,6 +168,8 @@ public:
 
   double get_start_time() const;
   double get_finish_time() const;
+  void mark() { marked_ = true; }
+  bool is_marked() const { return marked_; }
 
   /** Returns the internal implementation of this Activity */
   kernel::activity::ActivityImpl* get_impl() const { return pimpl_.get(); }
@@ -194,6 +196,7 @@ private:
   Activity::State state_                   = Activity::State::INITED;
   double remains_                          = 0;
   bool suspended_                          = false;
+  bool marked_                             = false;
   std::vector<ActivityPtr> successors_;
   std::set<ActivityPtr> dependencies_;
   std::atomic_int_fast32_t refcount_{0};
diff --git a/src/simdag/sd_daxloader.cpp b/src/simdag/sd_daxloader.cpp
index a3afbcbaeb..91ffa116e7 100644
--- a/src/simdag/sd_daxloader.cpp
+++ b/src/simdag/sd_daxloader.cpp
@@ -5,6 +5,8 @@
  * under the terms of the license (GNU LGPL) which comes with this package. */
 
 #include "simdag_private.hpp"
+#include "simgrid/s4u/Comm.hpp"
+#include "simgrid/s4u/Exec.hpp"
 #include "simgrid/simdag.h"
 #include "xbt/file.hpp"
 #include "xbt/log.h"
@@ -126,6 +128,40 @@ bool acyclic_graph_detail(const_xbt_dynar_t dag)
   return all_marked;
 }
 
+bool check_for_cycle(const std::vector<simgrid::s4u::ActivityPtr>& dag)
+{
+  std::vector<simgrid::s4u::ActivityPtr> current;
+
+  for (const auto& a : dag)
+    if (dynamic_cast<simgrid::s4u::Exec*>(a.get()) != nullptr && a->is_waited_by() == 0)
+      current.push_back(a);
+
+  while (not current.empty()) {
+    std::vector<simgrid::s4u::ActivityPtr> next;
+    for (auto const& a : current) {
+      a->mark();
+      for (auto const& pred : a->get_dependencies()) {
+        if (dynamic_cast<simgrid::s4u::Comm*>(pred.get()) != nullptr) {
+          pred->mark();
+          // Comms have only one predecessor
+          auto pred_pred = *(pred->get_dependencies().begin());
+          if (std::none_of(pred_pred->get_successors().begin(), pred_pred->get_successors().end(),
+                           [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); }))
+            next.push_back(pred_pred);
+        } else {
+          if (std::none_of(pred->get_successors().begin(), pred->get_successors().end(),
+                           [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); }))
+            next.push_back(pred);
+        }
+      }
+    }
+    current.clear();
+    current = next;
+  }
+
+  return not std::any_of(dag.begin(), dag.end(), [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); });
+}
+
 static YY_BUFFER_STATE input_buffer;
 
 static xbt_dynar_t result;
diff --git a/src/simdag/sd_dotloader.cpp b/src/simdag/sd_dotloader.cpp
index 860f4092d4..cfecfe6ecd 100644
--- a/src/simdag/sd_dotloader.cpp
+++ b/src/simdag/sd_dotloader.cpp
@@ -120,6 +120,12 @@ std::vector<ActivityPtr> create_DAG_from_dot(const std::string& filename)
   agclose(dag_dot);
   fclose(in_file);
 
+  if (not check_for_cycle(dag)) {
+    std::string base = simgrid::xbt::Path(filename).get_base_name();
+    XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.", base.c_str());
+    dag.clear();
+  }
+
   return dag;
 }
 
diff --git a/src/simdag/simdag_private.hpp b/src/simdag/simdag_private.hpp
index d373b7618f..ef9e87da54 100644
--- a/src/simdag/simdag_private.hpp
+++ b/src/simdag/simdag_private.hpp
@@ -172,6 +172,7 @@ public:
 extern XBT_PRIVATE std::unique_ptr<simgrid::sd::Global> sd_global;
 
 /* SimDag private functions */
+XBT_PRIVATE bool check_for_cycle(const std::vector<simgrid::s4u::ActivityPtr>& dag);
 XBT_PRIVATE bool acyclic_graph_detail(const_xbt_dynar_t dag);
 XBT_PRIVATE void uniq_transfer_task_name(SD_task_t task);
 XBT_PRIVATE const char *__get_state_name(e_SD_task_state_t state);
-- 
2.20.1