+std::vector<std::string> get_textual_trace(const PartialExecution& w)
+{
+ std::vector<std::string> trace;
+ for (const auto& t : w) {
+ auto a = xbt::string_printf("Actor %ld: %s", t->aid_, t->to_string(true).c_str());
+ trace.emplace_back(std::move(a));
+ }
+ return trace;
+}
+
+Execution::Execution(const PartialExecution& w)
+{
+ push_partial_execution(w);
+}
+
+void Execution::push_transition(std::shared_ptr<Transition> t)
+{
+ if (t == nullptr) {
+ throw std::invalid_argument("Unexpectedly received `nullptr`");
+ }
+ ClockVector max_clock_vector;
+ for (const Event& e : this->contents_) {
+ if (e.get_transition()->depends(t.get())) {
+ max_clock_vector = ClockVector::max(max_clock_vector, e.get_clock_vector());
+ }
+ }
+ max_clock_vector[t->aid_] = this->size();
+ contents_.push_back(Event({std::move(t), max_clock_vector}));
+}
+
+void Execution::push_partial_execution(const PartialExecution& w)
+{
+ for (const auto& t : w) {
+ push_transition(t);
+ }
+}
+
+std::vector<std::string> Execution::get_textual_trace() const
+{
+ std::vector<std::string> trace;
+ for (const auto& t : this->contents_) {
+ auto a = xbt::string_printf("Actor %ld: %s", t.get_transition()->aid_, t.get_transition()->to_string(true).c_str());
+ trace.emplace_back(std::move(a));
+ }
+ return trace;
+}
+
+std::unordered_set<Execution::EventHandle> Execution::get_racing_events_of(Execution::EventHandle target) const
+{
+ std::unordered_set<Execution::EventHandle> racing_events;
+ // This keep tracks of events that happens-before the target
+ std::unordered_set<Execution::EventHandle> disqualified_events;
+
+ // For each event of the execution
+ for (auto e_i = target; e_i != std::numeric_limits<Execution::EventHandle>::max(); e_i--) {
+ // We need `e_i -->_E target` as a necessary condition
+ if (not happens_before(e_i, target)) {
+ XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` discarded because `%u` --\\-->_E `%u`", target, e_i, e_i, target);
+ continue;
+ }
+
+ // Further, `proc(e_i) != proc(target)`
+ if (get_actor_with_handle(e_i) == get_actor_with_handle(target)) {
+ disqualified_events.insert(e_i);
+ XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` disqualified because proc(`%u`)=proc(`%u`)", target, e_i, e_i,
+ target);
+ continue;
+ }
+
+ // There could an event that "happens-between" the two events which would discount `e_i` as a race
+ for (auto e_j = e_i; e_j < target; e_j++) {
+ // If both:
+ // 1. e_i --->_E e_j; and
+ // 2. disqualified_events.count(e_j) > 0
+ // then e_i --->_E target indirectly (either through
+ // e_j directly, or transitively through e_j)
+ if (disqualified_events.count(e_j) > 0 && happens_before(e_i, e_j)) {
+ XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` disqualified because `%u` happens-between `%u`-->`%u`-->`%u`)",
+ target, e_i, e_j, e_i, e_j, target);
+ disqualified_events.insert(e_i);
+ break;
+ }
+ }
+
+ // If `e_i` wasn't disqualified in the last round,
+ // it's in a race with `target`. After marking it
+ // as such, we ensure no other event `e` can happen-before
+ // it (since this would transitively make it the event
+ // which "happens-between" `target` and `e`)
+ if (disqualified_events.count(e_i) == 0) {
+ XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` is a valid racing event",
+ target, e_i);
+ racing_events.insert(e_i);
+ disqualified_events.insert(e_i);
+ }
+ }
+
+ return racing_events;
+}
+
+std::unordered_set<Execution::EventHandle> Execution::get_reversible_races_of(EventHandle handle) const
+{
+ std::unordered_set<EventHandle> reversible_races;
+ for (EventHandle race : get_racing_events_of(handle)) {
+ if (ReversibleRaceCalculator::is_race_reversible(*this, race, handle)) {
+ reversible_races.insert(race);
+ }
+ }
+ return reversible_races;
+}
+
+Execution Execution::get_prefix_before(Execution::EventHandle handle) const
+{
+ return Execution(std::vector<Event>{contents_.begin(), contents_.begin() + handle});
+}
+
+std::unordered_set<aid_t>
+Execution::get_missing_source_set_actors_from(EventHandle e, const std::unordered_set<aid_t>& backtrack_set) const
+{
+ // If this execution is empty, there are no initials
+ // relative to the last transition added to the execution
+ // since such a transition does not exist
+ if (empty()) {
+ return std::unordered_set<aid_t>{};
+ }
+
+ // To actually compute `I_[E'](v) ∩ backtrack(E')`, we must
+ // first compute `E'` and "move" in the direction of `v`.
+ // We perform a scan over `E` (this execution) and make
+ // note of any events which occur after `e` but don't
+ // "happen-after" `e` by pushing them onto `E'`. Note that
+ // correctness is still preserved in computing `v` "on-the-fly"
+ // to determine if an event `e` by actor `q` is an initial for `E'`
+ // after `v`: only those events that "occur-before" `e` in `v` could
+ // "happen-before" `ve for any valid "happens-before" relation
+ // (see property 1 in the ODPOR paper, viz. "is included in <_E")
+
+ // First, grab `E' := pre(e, E)` and determine what actor `p` is
+ const auto next_E_p = get_latest_event_handle().value();
+ xbt_assert(e != next_E_p,
+ "This method assumes that the event `e` (%u) and `next_[E](p)` (%u)"
+ "are in a reversible race, yet we claim to have such a race between the"
+ "same event. This indicates the the SDPOR pseudocode implementation is broken "
+ "as it supplies these values.",
+ e, next_E_p);
+ Execution E_prime_v = get_prefix_before(e);
+ std::vector<sdpor::Execution::EventHandle> v;
+ std::unordered_set<aid_t> I_E_prime_v;
+ std::unordered_set<aid_t> disqualified_actors;
+
+ // Note `e + 1` here: `notdep(e, E)` is defined as the
+ // set of events that *occur-after* but don't *happen-after* `e`
+ for (auto e_prime = e + 1; e_prime <= next_E_p; ++e_prime) {
+ // Any event `e*` which occurs after `e` but which does not
+ // happen after `e` is a member of `v`. In addition to marking
+ // the event in `v`, we also "simulate" running the action `v`
+ // from E'
+ if (not happens_before(e, e_prime) || e_prime == next_E_p) {
+ // First, push the transition onto the hypothetical execution
+ E_prime_v.push_transition(get_event_with_handle(e_prime).get_transition());
+ const EventHandle e_prime_in_E_prime_v = E_prime_v.get_latest_event_handle().value();
+
+ // When checking whether any event in `dom_[E'](v)` happens before
+ // `next_[E'](q)` below for thread `q`, we must consider that the
+ // events relative to `E` (this execution) are different than those
+ // relative to `E'.v`. Thus e.g. event `7` in `E` may be event `4`
+ // in `E'.v`. Since we are asking about "happens-before"
+ // `-->_[E'.v]` about `E'.v`, we must build `v` relative to `E'`.
+ //
+ // Note that we add `q` to v regardless of whether `q` itself has been
+ // disqualified since we've determined that `e_prime` "occurs-after" but
+ // does not "happen-after" `e`
+ v.push_back(e_prime_in_E_prime_v);
+
+ const aid_t q = E_prime_v.get_actor_with_handle(e_prime_in_E_prime_v);
+ if (disqualified_actors.count(q) > 0) { // Did we already note that `q` is not an initial?
+ continue;
+ }
+ const bool is_initial = std::none_of(v.begin(), v.end(), [&](const auto& e_star) {
+ return E_prime_v.happens_before(e_star, e_prime_in_E_prime_v);
+ });
+ if (is_initial) {
+ // If the backtrack set already contains `q`, we're done:
+ // they've made note to search for (or have already searched for)
+ // this initial
+ if (backtrack_set.count(q) > 0) {
+ return std::unordered_set<aid_t>{};
+ } else {
+ I_E_prime_v.insert(q);
+ }
+ } else {
+ // If `q` is disqualified as a candidate, clearly
+ // no event occurring after `e_prime` in `E` executed
+ // by actor `q` will qualify since any (valid) happens-before
+ // relation orders actions taken by each actor
+ disqualified_actors.insert(q);
+ }
+ }
+ }
+ xbt_assert(not I_E_prime_v.empty(),
+ "For any non-empty execution, we know that "
+ "at minimum one actor is an initial since "
+ "some execution is possible with respect to a "
+ "prefix before event `%u`, yet we didn't find anyone. "
+ "This implies the implementation of this function is broken.",
+ e);
+ return I_E_prime_v;
+}
+
+std::optional<PartialExecution> Execution::get_odpor_extension_from(EventHandle e, EventHandle e_prime,
+ const State& state_at_e) const