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 namespace simgrid::mc::udpor {
  10
  11 UnfoldingEvent::UnfoldingEvent(std::initializer_list<const UnfoldingEvent*> init_list)
  12     : UnfoldingEvent(EventSet(std::move(init_list)))
  13 {
  14 }
  15
  16 UnfoldingEvent::UnfoldingEvent(EventSet immediate_causes, std::shared_ptr<Transition> transition)
  17     : associated_transition(std::move(transition)), immediate_causes(std::move(immediate_causes))
  18 {
  19 }
  20
  21 bool UnfoldingEvent::operator==(const UnfoldingEvent& other) const
  22 {
  23   // Two events are equivalent iff:
  24   // 1. they have the same action
  25   // 2. they have the same history
  26   //
  27   // NOTE: All unfolding event objects are created in reference to
  28   // an `Unfolding` object which owns them. Hence, the references
  29   // they contain to other events in the unfolding can
  30   // be used as intrinsic identities (i.e. we don't need to
  31   // recursively check if each of our causes has a `==` in
  32   // the other event's causes)
  33   return associated_transition->aid_ == other.associated_transition->aid_ &&
  34          associated_transition->type_ == other.associated_transition->type_ &&
  35          associated_transition->times_considered_ == other.associated_transition->times_considered_ &&
  36          this->immediate_causes == other.immediate_causes;
  37 }
  38
  39 EventSet UnfoldingEvent::get_history() const
  40 {
  41   return History(this).get_all_events();
  42 }
  43
  44 bool UnfoldingEvent::related_to(const UnfoldingEvent* other) const
  45 {
  46   return this->in_history_of(other) or other->in_history_of(this);
  47 }
  48
  49 bool UnfoldingEvent::in_history_of(const UnfoldingEvent* other) const
  50 {
  51   return History(other).contains(this);
  52 }
  53
  54 bool UnfoldingEvent::conflicts_with(const UnfoldingEvent* other) const
  55 {
  56   // Events that have a causal relation never are in conflict
  57   // in an unfolding structure. Two events in conflict must
  58   // not be contained in each other's histories
  59   if (related_to(other)) {
  60     return false;
  61   }
  62
  63   const EventSet my_history      = get_history();
  64   const EventSet other_history   = other->get_history();
  65   const EventSet unique_to_me    = my_history.subtracting(other_history);
  66   const EventSet unique_to_other = other_history.subtracting(my_history);
  67
  68   const bool conflicts_with_me    = std::any_of(unique_to_me.begin(), unique_to_me.end(),
  69                                                 [&](const UnfoldingEvent* e) { return e->is_dependent_with(other); });
  70   const bool conflicts_with_other = std::any_of(unique_to_other.begin(), unique_to_other.end(),
  71                                                 [&](const UnfoldingEvent* e) { return e->is_dependent_with(this); });
  72   return conflicts_with_me or conflicts_with_other;
  73 }
  74
  75 bool UnfoldingEvent::conflicts_with(const Configuration& config) const
  76 {
  77   // A configuration is itself already conflict-free. Thus, it is
  78   // simply a matter of testing whether or not the transition associated
  79   // with the event is dependent with any already in `config` that are
  80   // OUTSIDE this event's history (in an unfolding, events only conflict
  81   // if they are not related)
  82   const EventSet potential_conflicts = config.get_events().subtracting(get_history());
  83   return std::any_of(potential_conflicts.cbegin(), potential_conflicts.cend(),
  84                      [&](const UnfoldingEvent* e) { return this->is_dependent_with(e); });
  85 }
  86
  87 bool UnfoldingEvent::immediately_conflicts_with(const UnfoldingEvent* other) const
  88 {
  89   // They have to be in conflict at a minimum
  90   if (not conflicts_with(other)) {
  91     return false;
  92   }
  93
  94   auto combined_events = History(EventSet{this, other}).get_all_events();
  95
  96   // See the definition of immediate conflicts in the original paper on UDPOR
  97   {
  98     combined_events.remove(this);
  99     if (not combined_events.is_valid_configuration()) {
 100       return false;
 101     }
 102     combined_events.insert(this);
 103   }
 104
 105   {
 106     combined_events.remove(other);
 107     if (not combined_events.is_valid_configuration()) {
 108       return false;
 109     }
 110     combined_events.insert(other);
 111   }
 112
 113   return true;
 114 }
 115
 116 bool UnfoldingEvent::is_dependent_with(const Transition* t) const
 117 {
 118   return associated_transition->depends(t);
 119 }
 120
 121 bool UnfoldingEvent::is_dependent_with(const UnfoldingEvent* other) const
 122 {
 123   return is_dependent_with(other->associated_transition.get());
 124 }
 125
 126 } // namespace simgrid::mc::udpor