src/mc/explo/udpor/UnfoldingEvent.cpp

   1 /* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
   7 #include "src/mc/explo/udpor/History.hpp"
   8
   9 #include <xbt/asserts.h>
  10 #include <xbt/log.h>
  11 #include <xbt/string.hpp>
  12
  13 namespace simgrid::mc::udpor {
  14
  15 UnfoldingEvent::UnfoldingEvent(std::initializer_list<const UnfoldingEvent*> init_list)
  16     : UnfoldingEvent(EventSet(std::move(init_list)))
  17 {
  18 }
  19
  20 UnfoldingEvent::UnfoldingEvent(EventSet immediate_causes, std::shared_ptr<Transition> transition)
  21     : associated_transition(std::move(transition)), immediate_causes(std::move(immediate_causes))
  22 {
  23   static uint64_t event_id = 0;
  24   this->id                 = ++event_id;
  25 }
  26
  27 bool UnfoldingEvent::operator==(const UnfoldingEvent& other) const
  28 {
  29   // Intrinsic identity check
  30   if (this == &other) {
  31     return true;
  32   }
  33   // Two events are equivalent iff:
  34   // 1. they have the same action
  35   // 2. they have the same history
  36   //
  37   // NOTE: All unfolding event objects are created in reference to
  38   // an `Unfolding` object which owns them. Hence, the references
  39   // they contain to other events in the unfolding can
  40   // be used as intrinsic identities (i.e. we don't need to
  41   // recursively check if each of our causes has a `==` in
  42   // the other event's causes)
  43   return associated_transition->aid_ == other.associated_transition->aid_ &&
  44          associated_transition->type_ == other.associated_transition->type_ &&
  45          associated_transition->times_considered_ == other.associated_transition->times_considered_ &&
  46          this->immediate_causes == other.immediate_causes;
  47 }
  48
  49 std::string UnfoldingEvent::to_string() const
  50 {
  51   std::string dependencies_string;
  52
  53   dependencies_string += "[";
  54   for (const auto* e : immediate_causes) {
  55     dependencies_string += " ";
  56     dependencies_string += e->to_string();
  57     dependencies_string += " and ";
  58   }
  59   dependencies_string += "]";
  60
  61   return xbt::string_printf("Event %lu, Actor %ld: %s (%lu dependencies: %s)", this->id, associated_transition->aid_,
  62                             associated_transition->to_string().c_str(), immediate_causes.size(),
  63                             dependencies_string.c_str());
  64 }
  65
  66 EventSet UnfoldingEvent::get_history() const
  67 {
  68   EventSet local_config = get_local_config();
  69   local_config.remove(this);
  70   return local_config;
  71 }
  72
  73 EventSet UnfoldingEvent::get_local_config() const
  74 {
  75   return History(this).get_all_events();
  76 }
  77
  78 bool UnfoldingEvent::related_to(const UnfoldingEvent* other) const
  79 {
  80   return this->in_history_of(other) || other->in_history_of(this);
  81 }
  82
  83 bool UnfoldingEvent::in_history_of(const UnfoldingEvent* other) const
  84 {
  85   return History(other).contains(this);
  86 }
  87
  88 bool UnfoldingEvent::conflicts_with(const UnfoldingEvent* other) const
  89 {
  90   // Events that have a causal relation never are in conflict
  91   // in an unfolding structure. Two events in conflict must
  92   // not be contained in each other's histories
  93   if (related_to(other)) {
  94     return false;
  95   }
  96
  97   const EventSet my_history      = get_local_config();
  98   const EventSet other_history   = other->get_local_config();
  99   const EventSet unique_to_me    = my_history.subtracting(other_history);
 100   const EventSet unique_to_other = other_history.subtracting(my_history);
 101
 102   const bool conflicts_with_me    = std::any_of(unique_to_me.begin(), unique_to_me.end(),
 103                                                 [&](const UnfoldingEvent* e) { return e->is_dependent_with(other); });
 104   const bool conflicts_with_other = std::any_of(unique_to_other.begin(), unique_to_other.end(),
 105                                                 [&](const UnfoldingEvent* e) { return e->is_dependent_with(this); });
 106   return conflicts_with_me || conflicts_with_other;
 107 }
 108
 109 bool UnfoldingEvent::conflicts_with_any(const EventSet& events) const
 110 {
 111   return std::any_of(events.begin(), events.end(), [&](const auto e) { return e->conflicts_with(this); });
 112 }
 113
 114 bool UnfoldingEvent::immediately_conflicts_with(const UnfoldingEvent* other) const
 115 {
 116   // They have to be in conflict at a minimum
 117   if (not conflicts_with(other)) {
 118     return false;
 119   }
 120
 121   auto combined_events = History(EventSet{this, other}).get_all_events();
 122
 123   // See the definition of immediate conflicts in the original paper on UDPOR
 124   combined_events.remove(this);
 125   if (not combined_events.is_valid_configuration())
 126     return false;
 127   combined_events.insert(this);
 128
 129   combined_events.remove(other);
 130   if (not combined_events.is_valid_configuration())
 131     return false;
 132   combined_events.insert(other);
 133
 134   return true;
 135 }
 136
 137 bool UnfoldingEvent::is_dependent_with(const Transition* t) const
 138 {
 139   return associated_transition->depends(t);
 140 }
 141
 142 bool UnfoldingEvent::is_dependent_with(const UnfoldingEvent* other) const
 143 {
 144   return is_dependent_with(other->associated_transition.get());
 145 }
 146
 147 } // namespace simgrid::mc::udpor