return exC;
}
-EventSet UdporChecker::compute_exC_by_enumeration(const Configuration& C, const std::shared_ptr<Transition> action)
-{
- // Here we're computing the following:
- //
- // U{<a, K> : K is maximal, `a` depends on all of K, `a` enabled at config(K) }
- //
- // where `a` is the `action` given to us. Note that `a` is presumed to be enabled
- EventSet incremental_exC;
-
- for (auto begin =
- maximal_subsets_iterator(C, {[&](const UnfoldingEvent* e) { return e->is_dependent_with(action.get()); }});
- begin != maximal_subsets_iterator(); ++begin) {
- const EventSet& maximal_subset = *begin;
-
- // Determining if `a` is enabled here might not be possible while looking at `a` opaquely
- // We leave the implementation as-is to ensure that any addition would be simple
- // if it were ever added
- const bool enabled_at_config_k = false;
-
- if (enabled_at_config_k) {
- auto event = std::make_unique<UnfoldingEvent>(maximal_subset, action);
- const auto handle = unfolding.insert(std::move(event));
- incremental_exC.insert(handle);
- }
- }
- return incremental_exC;
-}
-
EventSet UdporChecker::compute_enC(const Configuration& C, const EventSet& exC) const
{
EventSet enC;
const UnfoldingEvent* UdporChecker::select_next_unfolding_event(const EventSet& A, const EventSet& enC)
{
- if (!enC.empty()) {
+ if (enC.empty()) {
+ throw std::invalid_argument("There are no unfolding events to select. "
+ "Are you sure that you checked that en(C) was not "
+ "empty before attempting to select an event from it?");
+ }
+
+ if (A.empty()) {
return *(enC.begin());
}
{
EventSet exC;
- // TODO: if this is the first action by the actor, no such previous event exists.
- // How do we react here? Do we say we're dependent with the root event?
const auto send_action = std::static_pointer_cast<CommSendTransition>(std::move(action));
+ const auto pre_event_a_C = C.pre_event(send_action->aid_);
const unsigned sender_mailbox = send_action->get_mailbox();
- const auto pre_event_a_C = C.pre_event(send_action->aid_).value();
// 1. Create `e' := <a, config(preEvt(a, C))>` and add `e'` to `ex(C)`
- const auto e_prime = U->discover_event(EventSet({pre_event_a_C}), send_action);
- exC.insert(e_prime);
+ // NOTE: If `preEvt(a, C)` doesn't exist, we're effectively asking
+ // about `config({})`
+ if (pre_event_a_C.has_value()) {
+ const auto e_prime = U->discover_event(EventSet({pre_event_a_C.value()}), send_action);
+ exC.insert(e_prime);
+ } else {
+ const auto e_prime = U->discover_event(EventSet(), send_action);
+ exC.insert(e_prime);
+ }
// 2. foreach e ∈ C s.t. λ(e) ∈ {AsyncSend(m, _), TestAny(Com)} where
// Com contains a matching c' = AsyncReceive(m, _) with a
for (const auto e : C) {
const bool transition_type_check = [&]() {
if (const auto* async_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
- e != nullptr && async_send->get_mailbox() == sender_mailbox) {
- return true;
- } else if (const auto* e_test_any = dynamic_cast<const CommTestTransition*>(e->get_transition());
- e_test_any != nullptr) {
- // TODO: Check if there's a way to find a matching AsyncReceive -> matching when? in the history?
- return true;
+ async_send != nullptr) {
+ return async_send->get_mailbox() == sender_mailbox;
}
+ // TODO: Add `TestAny` dependency
return false;
}();
if (transition_type_check) {
- const EventSet K = EventSet({e, pre_event_a_C}).get_largest_maximal_subset();
+ const EventSet K = EventSet({e, pre_event_a_C.value_or(e)}).get_largest_maximal_subset();
- // TODO: How do we compute D_K(a, b)? There's a specialized
- // function for each case it appears, but I don't see where
- // `config(K)` comes in
- if (false) {
+ // TODO: Check D_K(a, lambda(e))
+ if (true) {
const auto e_prime = U->discover_event(std::move(K), send_action);
exC.insert(e_prime);
}
}
}
+ // TODO: Add `TestAny` dependency case
return exC;
}
EventSet ExtensionSetCalculator::partially_extend_CommRecv(const Configuration& C, Unfolding* U,
- const std::shared_ptr<Transition> recv_action)
+ const std::shared_ptr<Transition> action)
{
- return EventSet();
+ EventSet exC;
+
+ // TODO: if this is the first action by the actor, no such previous event exists.
+ // How do we react here? Do we say we're dependent with the root event?
+ const auto recv_action = std::static_pointer_cast<CommRecvTransition>(std::move(action));
+ const unsigned recv_mailbox = recv_action->get_mailbox();
+ const auto pre_event_a_C = C.pre_event(recv_action->aid_);
+
+ // 1. Create `e' := <a, config(preEvt(a, C))>` and add `e'` to `ex(C)`
+ if (pre_event_a_C.has_value()) {
+ const auto e_prime = U->discover_event(EventSet({pre_event_a_C.value()}), recv_action);
+ exC.insert(e_prime);
+ } else {
+ const auto e_prime = U->discover_event(EventSet(), recv_action);
+ exC.insert(e_prime);
+ }
+
+ // 2. foreach e ∈ C s.t. λ(e) ∈ {AsyncSend(m, _), TestAny(Com)} where
+ // Com contains a matching c' = AsyncReceive(m, _) with a
+ for (const auto e : C) {
+ const bool transition_type_check = [&]() {
+ if (const auto* async_recv = dynamic_cast<const CommSendTransition*>(e->get_transition());
+ async_recv != nullptr && async_recv->get_mailbox() == recv_mailbox) {
+ return true;
+ }
+ // TODO: Add `TestAny` dependency
+ return false;
+ }();
+
+ if (transition_type_check) {
+ const EventSet K = EventSet({e, pre_event_a_C.value_or(e)}).get_largest_maximal_subset();
+
+ // TODO: Check D_K(a, lambda(e))
+ if (true) {
+ const auto e_prime = U->discover_event(std::move(K), recv_action);
+ exC.insert(e_prime);
+ }
+ }
+ }
+
+ // TODO: Add `TestAny` dependency case
+ return exC;
}
-EventSet ExtensionSetCalculator::partially_extend_CommWait(const Configuration&, Unfolding* U,
- std::shared_ptr<Transition> wait_action)
+EventSet ExtensionSetCalculator::partially_extend_CommWait(const Configuration& C, Unfolding* U,
+ std::shared_ptr<Transition> action)
{
- return EventSet();
+ EventSet exC;
+
+ const auto wait_action = std::static_pointer_cast<CommWaitTransition>(std::move(action));
+ const auto pre_event_a_C = C.pre_event(wait_action->aid_);
+
+ // 1. if `a` is enabled at state(config({preEvt(a,C)})), then
+ // create `e' := <a, config({preEvt(a,C)})>` and add `e'` to `ex(C)`
+ //
+ // First, if `pre_event_a_C == std::nullopt`, then there is nothing to
+ // do: `CommWait` will never be enabled in the empty configuration (at
+ // least two actions must be executed before)
+ if (pre_event_a_C.has_value(); const auto unwrapped_pre_event = pre_event_a_C.value()) {
+
+ // Determine the _issuer_ of the communication of the `CommWait` event
+ // in `C`. The issuer of the `CommWait` in `C` is the event in `C`
+ // whose transition is the `CommRecv` or `CommSend` whose resutling
+ // communication this `CommWait` waits on
+ const auto issuer = std::find_if(C.begin(), C.end(), [=](const UnfoldingEvent* e) { return false; });
+ xbt_assert(issuer != C.end(),
+ "Invariant violation! A (supposedly) enabled `CommWait` transition "
+ "waiting on commiunication %lu should not be enabled: the receive/send "
+ "transition which generated the communication is not an action taken "
+ "to reach state(C) (the state of the configuration), which should "
+ "be an impossibility if `%s` is enabled. Please report this as "
+ "a bug in SimGrid's UDPOR implementation",
+ wait_action->get_comm(), wait_action->to_string(false).c_str());
+
+ // A necessary condition is that the issuer be present in
+ // config({preEvt(a, C)}); otherwise, the `CommWait` could not
+ // be enabled since the communication on which it waits would not
+ // have been created for it!
+ if (const auto config_pre_event = History(unwrapped_pre_event); config_pre_event.contains(*issuer)) {
+ // If the issuer is a `CommRecv` (resp. `CommSend`), then we check that there
+ // are at least as many `CommSend` (resp. `CommRecv`) transitions in `config_pre_event`
+ // as needed to reach the receive/send number that is `issuer`.
+ //...
+ //...
+ }
+ }
+
+ return exC;
}
-EventSet ExtensionSetCalculator::partially_extend_CommTest(const Configuration&, Unfolding* U,
+EventSet ExtensionSetCalculator::partially_extend_CommTest(const Configuration& C, Unfolding* U,
std::shared_ptr<Transition> test_action)
{
return EventSet();
