1 /* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved. */
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. */
6 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
7 #include "src/mc/explo/udpor/History.hpp"
9 #include <xbt/asserts.h>
11 #include <xbt/string.hpp>
13 namespace simgrid::mc::udpor {
15 UnfoldingEvent::UnfoldingEvent(std::initializer_list<const UnfoldingEvent*> init_list)
16 : UnfoldingEvent(EventSet(std::move(init_list)))
20 UnfoldingEvent::UnfoldingEvent(EventSet immediate_causes, std::shared_ptr<Transition> transition)
21 : associated_transition(std::move(transition)), immediate_causes(std::move(immediate_causes))
25 bool UnfoldingEvent::operator==(const UnfoldingEvent& other) const
27 // Intrinsic identity check
31 // Two events are equivalent iff:
32 // 1. they have the same action
33 // 2. they have the same history
35 // NOTE: All unfolding event objects are created in reference to
36 // an `Unfolding` object which owns them. Hence, the references
37 // they contain to other events in the unfolding can
38 // be used as intrinsic identities (i.e. we don't need to
39 // recursively check if each of our causes has a `==` in
40 // the other event's causes)
41 return associated_transition->aid_ == other.associated_transition->aid_ &&
42 associated_transition->type_ == other.associated_transition->type_ &&
43 associated_transition->times_considered_ == other.associated_transition->times_considered_ &&
44 this->immediate_causes == other.immediate_causes;
47 std::string UnfoldingEvent::to_string() const
49 std::string dependencies_string;
51 dependencies_string += "[";
52 for (const auto* e : immediate_causes) {
53 dependencies_string += e->to_string();
55 dependencies_string += "]";
57 return xbt::string_printf("(%p) Actor %ld: %s (%zu dependencies: %s)", this, associated_transition->aid_,
58 associated_transition->to_string().c_str(), immediate_causes.size(),
59 dependencies_string.c_str());
62 EventSet UnfoldingEvent::get_history() const
64 EventSet local_config = get_local_config();
65 local_config.remove(this);
69 EventSet UnfoldingEvent::get_local_config() const
71 return History(this).get_all_events();
74 bool UnfoldingEvent::related_to(const UnfoldingEvent* other) const
76 return this->in_history_of(other) or other->in_history_of(this);
79 bool UnfoldingEvent::in_history_of(const UnfoldingEvent* other) const
81 return History(other).contains(this);
84 bool UnfoldingEvent::conflicts_with(const UnfoldingEvent* other) const
86 // Events that have a causal relation never are in conflict
87 // in an unfolding structure. Two events in conflict must
88 // not be contained in each other's histories
89 if (related_to(other)) {
93 const EventSet my_history = get_local_config();
94 const EventSet other_history = other->get_local_config();
95 const EventSet unique_to_me = my_history.subtracting(other_history);
96 const EventSet unique_to_other = other_history.subtracting(my_history);
98 const bool conflicts_with_me = std::any_of(unique_to_me.begin(), unique_to_me.end(),
99 [&](const UnfoldingEvent* e) { return e->is_dependent_with(other); });
100 const bool conflicts_with_other = std::any_of(unique_to_other.begin(), unique_to_other.end(),
101 [&](const UnfoldingEvent* e) { return e->is_dependent_with(this); });
102 return conflicts_with_me or conflicts_with_other;
105 bool UnfoldingEvent::conflicts_with_any(const EventSet& events) const
107 return std::any_of(events.begin(), events.end(), [&](const auto e) { return e->conflicts_with(this); });
110 bool UnfoldingEvent::immediately_conflicts_with(const UnfoldingEvent* other) const
112 // They have to be in conflict at a minimum
113 if (not conflicts_with(other)) {
117 auto combined_events = History(EventSet{this, other}).get_all_events();
119 // See the definition of immediate conflicts in the original paper on UDPOR
121 combined_events.remove(this);
122 if (not combined_events.is_valid_configuration()) {
125 combined_events.insert(this);
129 combined_events.remove(other);
130 if (not combined_events.is_valid_configuration()) {
133 combined_events.insert(other);
139 bool UnfoldingEvent::is_dependent_with(const Transition* t) const
141 return associated_transition->depends(t);
144 bool UnfoldingEvent::is_dependent_with(const UnfoldingEvent* other) const
146 return is_dependent_with(other->associated_transition.get());
149 } // namespace simgrid::mc::udpor