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/ExtensionSetCalculator.hpp"
7 #include "src/mc/explo/udpor/Configuration.hpp"
8 #include "src/mc/explo/udpor/History.hpp"
9 #include "src/mc/explo/udpor/Unfolding.hpp"
12 #include <unordered_map>
13 #include <xbt/asserts.h>
16 using namespace simgrid::mc;
18 namespace simgrid::mc::udpor {
20 EventSet ExtensionSetCalculator::partially_extend(const Configuration& C, Unfolding* U,
21 const std::shared_ptr<Transition> action)
23 using Action = Transition::Type;
24 using Handler = std::function<EventSet(const Configuration&, Unfolding*, const std::shared_ptr<Transition>)>;
25 using HandlerMap = std::unordered_map<Action, Handler>;
27 const static HandlerMap handlers =
28 HandlerMap{{Action::COMM_ASYNC_RECV, &ExtensionSetCalculator::partially_extend_CommRecv},
29 {Action::COMM_ASYNC_SEND, &ExtensionSetCalculator::partially_extend_CommSend},
30 {Action::COMM_WAIT, &ExtensionSetCalculator::partially_extend_CommWait},
31 {Action::COMM_TEST, &ExtensionSetCalculator::partially_extend_CommTest}};
33 if (const auto handler = handlers.find(action->type_); handler != handlers.end()) {
34 return handler->second(C, U, std::move(action));
37 "There is currently no specialized computation for the transition "
38 "'%s' for computing extension sets in UDPOR, so the model checker cannot "
39 "determine how to proceed. Please submit a bug report requesting "
40 "that the transition be supported in SimGrid using UDPOR and consider "
41 "using the other model-checking algorithms supported by SimGrid instead "
43 action->to_string().c_str());
48 EventSet ExtensionSetCalculator::partially_extend_CommSend(const Configuration& C, Unfolding* U,
49 const std::shared_ptr<Transition> action)
53 const auto send_action = std::static_pointer_cast<CommSendTransition>(std::move(action));
54 const auto pre_event_a_C = C.pre_event(send_action->aid_);
55 const unsigned sender_mailbox = send_action->get_mailbox();
57 // 1. Create `e' := <a, config(preEvt(a, C))>` and add `e'` to `ex(C)`
58 // NOTE: If `preEvt(a, C)` doesn't exist, we're effectively asking
60 if (pre_event_a_C.has_value()) {
61 const auto* e_prime = U->discover_event(EventSet({pre_event_a_C.value()}), send_action);
64 const auto* e_prime = U->discover_event(EventSet(), send_action);
68 // 2. foreach e ∈ C s.t. λ(e) ∈ {AsyncSend(m, _), TestAny(Com)} where
69 // Com contains a matching c' = AsyncReceive(m, _) with `action`
70 for (const auto e : C) {
71 const bool transition_type_check = [&]() {
72 if (const auto* async_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
73 async_send != nullptr) {
74 return async_send->get_mailbox() == sender_mailbox;
76 // TODO: Add `TestAny` dependency
80 if (transition_type_check) {
81 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)}).get_largest_maximal_subset();
83 // TODO: Check D_K(a, lambda(e))
85 const auto* e_prime = U->discover_event(std::move(K), send_action);
91 // TODO: Add `TestAny` dependency case
95 EventSet ExtensionSetCalculator::partially_extend_CommRecv(const Configuration& C, Unfolding* U,
96 const std::shared_ptr<Transition> action)
100 const auto recv_action = std::static_pointer_cast<CommRecvTransition>(std::move(action));
101 const unsigned recv_mailbox = recv_action->get_mailbox();
102 const auto pre_event_a_C = C.pre_event(recv_action->aid_);
104 // 1. Create `e' := <a, config(preEvt(a, C))>` and add `e'` to `ex(C)`
105 if (pre_event_a_C.has_value()) {
106 const auto* e_prime = U->discover_event(EventSet({pre_event_a_C.value()}), recv_action);
109 const auto* e_prime = U->discover_event(EventSet(), recv_action);
113 // 2. foreach e ∈ C s.t. λ(e) ∈ {AsyncSend(m, _), TestAny(Com)} where
114 // Com contains a matching c' = AsyncReceive(m, _) with a
115 for (const auto e : C) {
116 const bool transition_type_check = [&]() {
117 if (const auto* async_recv = dynamic_cast<const CommRecvTransition*>(e->get_transition());
118 async_recv != nullptr && async_recv->get_mailbox() == recv_mailbox) {
121 // TODO: Add `TestAny` dependency
125 if (transition_type_check) {
126 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)}).get_largest_maximal_subset();
128 // TODO: Check D_K(a, lambda(e)) (ony matters in the case of TestAny)
130 const auto* e_prime = U->discover_event(std::move(K), recv_action);
136 // TODO: Add `TestAny` dependency case
140 EventSet ExtensionSetCalculator::partially_extend_CommWait(const Configuration& C, Unfolding* U,
141 std::shared_ptr<Transition> action)
145 const auto wait_action = std::static_pointer_cast<CommWaitTransition>(std::move(action));
146 const auto wait_comm = wait_action->get_comm();
147 const auto pre_event_a_C = C.pre_event(wait_action->aid_);
149 // Determine the _issuer_ of the communication of the `CommWait` event
150 // in `C`. The issuer of the `CommWait` in `C` is the event in `C`
151 // whose transition is the `CommRecv` or `CommSend` whose resulting
152 // communication this `CommWait` waits on
153 const auto issuer = std::find_if(C.begin(), C.end(), [&](const UnfoldingEvent* e) {
154 if (const CommRecvTransition* e_issuer_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
155 e_issuer_receive != nullptr) {
156 return e_issuer_receive->aid_ == wait_action->aid_ && wait_comm == e_issuer_receive->get_comm();
159 if (const CommSendTransition* e_issuer_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
160 e_issuer_send != nullptr) {
161 return e_issuer_send->aid_ == wait_action->aid_ && wait_comm == e_issuer_send->get_comm();
166 xbt_assert(issuer != C.end(),
167 "Invariant violation! A (supposedly) enabled `CommWait` transition "
168 "waiting on communication %lu should not be enabled: the receive/send "
169 "transition which generated the communication is not an action taken "
170 "to reach state(C) (the state of the configuration), which should "
171 "be an impossibility if `%s` is enabled. Please report this as "
172 "a bug in SimGrid's UDPOR implementation",
173 wait_action->get_comm(), wait_action->to_string(false).c_str());
174 const UnfoldingEvent* e_issuer = *issuer;
175 const History e_issuer_history(e_issuer);
177 // 1. if `a` is enabled at state(config({preEvt(a,C)})), then
178 // create `e' := <a, config({preEvt(a,C)})>` and add `e'` to `ex(C)`
180 // First, if `pre_event_a_C == std::nullopt`, then there is nothing to
181 // do: `CommWait` will never be enabled in the empty configuration (at
182 // least two actions must be executed before)
183 if (pre_event_a_C.has_value(); const auto* unwrapped_pre_event = pre_event_a_C.value()) {
184 // A necessary condition is that the issuer be present in
185 // config({preEvt(a, C)}); otherwise, the `CommWait` could not
186 // be enabled since the communication on which it waits would not
187 // have been created for it!
188 if (const auto config_pre_event = History(unwrapped_pre_event); config_pre_event.contains(e_issuer)) {
189 // If the issuer is a `CommRecv` (resp. `CommSend`), then we check that there
190 // are at least as many `CommSend` (resp. `CommRecv`) transitions in `config_pre_event`
191 // as needed to reach the receive/send number that is `issuer`.
194 if (const CommRecvTransition* e_issuer_receive =
195 dynamic_cast<const CommRecvTransition*>(e_issuer->get_transition());
196 e_issuer_receive != nullptr) {
197 const unsigned issuer_mailbox = e_issuer_receive->get_mailbox();
199 // Check from the config -> how many sends have there been
200 const unsigned send_position =
201 std::count_if(config_pre_event.begin(), config_pre_event.end(), [=](const auto e) {
202 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
203 if (e_send != nullptr) {
204 return e_send->get_mailbox() == issuer_mailbox;
209 // Check from e_issuer -> what place is the issuer in?
210 const unsigned receive_position =
211 std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
212 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
213 if (e_receive != nullptr) {
214 return e_receive->get_mailbox() == issuer_mailbox;
219 if (send_position >= receive_position) {
220 exC.insert(U->discover_event(EventSet({unwrapped_pre_event}), wait_action));
223 } else if (const CommSendTransition* e_issuer_send =
224 dynamic_cast<const CommSendTransition*>(e_issuer->get_transition());
225 e_issuer_send != nullptr) {
226 const unsigned issuer_mailbox = e_issuer_send->get_mailbox();
228 // Check from e_issuer -> what place is the issuer in?
229 const unsigned send_position =
230 std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
231 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
232 if (e_send != nullptr) {
233 return e_send->get_mailbox() == issuer_mailbox;
238 // Check from the config -> how many sends have there been
239 const unsigned receive_position =
240 std::count_if(config_pre_event.begin(), config_pre_event.end(), [=](const auto e) {
241 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
242 if (e_receive != nullptr) {
243 return e_receive->get_mailbox() == issuer_mailbox;
248 if (send_position <= receive_position) {
249 exC.insert(U->discover_event(EventSet({unwrapped_pre_event}), wait_action));
253 xbt_die("The transition which created the communication on which `%s` waits "
254 "is neither an async send nor an async receive. The current UDPOR "
255 "implementation does not know how to check if `CommWait` is enabled in "
256 "this case. Was a new transition added?",
257 e_issuer->get_transition()->to_string().c_str());
262 // 3. foreach event e in C do
263 if (const CommSendTransition* e_issuer_send = dynamic_cast<const CommSendTransition*>(e_issuer->get_transition());
264 e_issuer_send != nullptr) {
265 for (const auto e : C) {
266 // If the provider of the communication for `CommWait` is a
267 // `CommSend(m)`, then we only care about `e` if `λ(e) == `CommRecv(m)`.
268 // All other actions would be independent with the wait action (including
269 // another `CommSend` to the same mailbox: `CommWait` is "waiting" for its
270 // corresponding receive action)
271 if (e->get_transition()->type_ != Transition::Type::COMM_ASYNC_RECV) {
275 const auto issuer_mailbox = e_issuer_send->get_mailbox();
276 const CommRecvTransition* e_recv = dynamic_cast<const CommRecvTransition*>(e->get_transition());
277 if (e_recv->get_mailbox() != issuer_mailbox) {
281 // If the `issuer` is not in `config(K)`, this implies that
282 // `WaitAny()` is always disabled in `config(K)`; hence, it
283 // is independent of any transition in `config(K)` (according
284 // to formal definition of independence)
285 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)});
286 const auto config_K = History(K);
287 if (not config_K.contains(e_issuer)) {
291 // What send # is the issuer
292 const unsigned send_position = std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
293 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
294 if (e_send != nullptr) {
295 return e_send->get_mailbox() == issuer_mailbox;
300 // What receive # is the event `e`?
301 const unsigned receive_position = std::count_if(config_K.begin(), config_K.end(), [=](const auto e) {
302 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
303 if (e_receive != nullptr) {
304 return e_receive->get_mailbox() == issuer_mailbox;
309 if (send_position == receive_position) {
310 exC.insert(U->discover_event(std::move(K), wait_action));
313 } else if (const CommRecvTransition* e_issuer_recv =
314 dynamic_cast<const CommRecvTransition*>(e_issuer->get_transition());
315 e_issuer_recv != nullptr) {
316 for (const auto e : C) {
317 // If the provider of the communication for `CommWait` is a
318 // `CommRecv(m)`, then we only care about `e` if `λ(e) == `CommSend(m)`.
319 // All other actions would be independent with the wait action (including
320 // another `CommRecv` to the same mailbox: `CommWait` is "waiting" for its
321 // corresponding send action)
322 if (e->get_transition()->type_ != Transition::Type::COMM_ASYNC_SEND) {
326 const auto issuer_mailbox = e_issuer_recv->get_mailbox();
327 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
328 if (e_send->get_mailbox() != issuer_mailbox) {
332 // If the `issuer` is not in `config(K)`, this implies that
333 // `WaitAny()` is always disabled in `config(K)`; hence, it
334 // is independent of any transition in `config(K)` (according
335 // to formal definition of independence)
336 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)});
337 const auto config_K = History(K);
338 if (not config_K.contains(e_issuer)) {
342 // What receive # is the event `e`?
343 const unsigned send_position = std::count_if(config_K.begin(), config_K.end(), [=](const auto e) {
344 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
345 if (e_send != nullptr) {
346 return e_send->get_mailbox() == issuer_mailbox;
351 // What send # is the issuer
352 const unsigned receive_position =
353 std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
354 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
355 if (e_receive != nullptr) {
356 return e_receive->get_mailbox() == issuer_mailbox;
361 if (send_position == receive_position) {
362 exC.insert(U->discover_event(std::move(K), wait_action));
366 xbt_die("The transition which created the communication on which `%s` waits "
367 "is neither an async send nor an async receive. The current UDPOR "
368 "implementation does not know how to check if `CommWait` is enabled in "
369 "this case. Was a new transition added?",
370 e_issuer->get_transition()->to_string().c_str());
376 EventSet ExtensionSetCalculator::partially_extend_CommTest(const Configuration& C, Unfolding* U,
377 std::shared_ptr<Transition> action)
381 const auto test_action = std::static_pointer_cast<CommTestTransition>(std::move(action));
382 const auto test_comm = test_action->get_comm();
383 const auto test_aid = test_action->aid_;
384 const auto pre_event_a_C = C.pre_event(test_action->aid_);
386 // Add the previous event as a dependency (if it's there)
387 if (pre_event_a_C.has_value()) {
388 const auto e_prime = U->discover_event(EventSet({pre_event_a_C.value()}), test_action);
392 // Determine the _issuer_ of the communication of the `CommTest` event
393 // in `C`. The issuer of the `CommTest` in `C` is the event in `C`
394 // whose transition is the `CommRecv` or `CommSend` whose resulting
395 // communication this `CommTest` tests on
396 const auto issuer = std::find_if(C.begin(), C.end(), [=](const UnfoldingEvent* e) {
397 if (const CommRecvTransition* e_issuer_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
398 e_issuer_receive != nullptr) {
399 return e_issuer_receive->aid_ == test_aid && test_comm == e_issuer_receive->get_comm();
402 if (const CommSendTransition* e_issuer_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
403 e_issuer_send != nullptr) {
404 return e_issuer_send->aid_ == test_aid && test_comm == e_issuer_send->get_comm();
409 xbt_assert(issuer != C.end(),
410 "An enabled `CommTest` transition (%s) is testing a communication"
411 "%lu not created by a receive/send "
412 "transition. SimGrid cannot currently handle test actions "
413 "under which a test is performed on a communication that was "
414 "not directly created by a receive/send operation of the same actor.",
415 test_action->to_string(false).c_str(), test_action->get_comm());
416 const UnfoldingEvent* e_issuer = *issuer;
417 const History e_issuer_history(e_issuer);
419 // 3. foreach event e in C do
420 if (const CommSendTransition* e_issuer_send = dynamic_cast<const CommSendTransition*>(e_issuer->get_transition());
421 e_issuer_send != nullptr) {
422 for (const auto e : C) {
423 // If the provider of the communication for `CommTest` is a
424 // `CommSend(m)`, then we only care about `e` if `λ(e) == `CommRecv(m)`.
425 // All other actions would be independent with the test action (including
426 // another `CommSend` to the same mailbox: `CommTest` is testing the
427 // corresponding receive action)
428 if (e->get_transition()->type_ != Transition::Type::COMM_ASYNC_RECV) {
432 const auto issuer_mailbox = e_issuer_send->get_mailbox();
434 if (const CommRecvTransition* e_recv = dynamic_cast<const CommRecvTransition*>(e->get_transition());
435 e_recv->get_mailbox() != issuer_mailbox) {
439 // If the `issuer` is not in `config(K)`, this implies that
440 // `CommTest()` is always disabled in `config(K)`; hence, it
441 // is independent of any transition in `config(K)` (according
442 // to formal definition of independence)
443 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)});
444 const auto config_K = History(K);
445 if (not config_K.contains(e_issuer)) {
449 // What send # is the issuer
450 const unsigned send_position = std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
451 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
452 if (e_send != nullptr) {
453 return e_send->get_mailbox() == issuer_mailbox;
458 // What receive # is the event `e`?
459 const unsigned receive_position = std::count_if(config_K.begin(), config_K.end(), [=](const auto e) {
460 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
461 if (e_receive != nullptr) {
462 return e_receive->get_mailbox() == issuer_mailbox;
467 if (send_position == receive_position) {
468 exC.insert(U->discover_event(std::move(K), test_action));
471 } else if (const CommRecvTransition* e_issuer_recv =
472 dynamic_cast<const CommRecvTransition*>(e_issuer->get_transition());
473 e_issuer_recv != nullptr) {
475 for (const auto e : C) {
476 // If the provider of the communication for `CommTest` is a
477 // `CommRecv(m)`, then we only care about `e` if `λ(e) == `CommSend(m)`.
478 // All other actions would be independent with the wait action (including
479 // another `CommRecv` to the same mailbox: `CommWait` is "waiting" for its
480 // corresponding send action)
481 if (e->get_transition()->type_ != Transition::Type::COMM_ASYNC_SEND) {
485 const auto issuer_mailbox = e_issuer_recv->get_mailbox();
486 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
487 if (e_send->get_mailbox() != issuer_mailbox) {
491 // If the `issuer` is not in `config(K)`, this implies that
492 // `WaitAny()` is always disabled in `config(K)`; hence, it
493 // is independent of any transition in `config(K)` (according
494 // to formal definition of independence)
495 const EventSet K = EventSet({e, pre_event_a_C.value_or(e)});
496 const auto config_K = History(K);
497 if (not config_K.contains(e_issuer)) {
501 // What receive # is the event `e`?
502 const unsigned send_position = std::count_if(config_K.begin(), config_K.end(), [=](const auto e) {
503 const CommSendTransition* e_send = dynamic_cast<const CommSendTransition*>(e->get_transition());
504 if (e_send != nullptr) {
505 return e_send->get_mailbox() == issuer_mailbox;
510 // What send # is the issuer
511 const unsigned receive_position =
512 std::count_if(e_issuer_history.begin(), e_issuer_history.end(), [=](const auto e) {
513 const CommRecvTransition* e_receive = dynamic_cast<const CommRecvTransition*>(e->get_transition());
514 if (e_receive != nullptr) {
515 return e_receive->get_mailbox() == issuer_mailbox;
520 if (send_position == receive_position) {
521 exC.insert(U->discover_event(std::move(K), test_action));
525 xbt_die("The transition which created the communication on which `%s` waits "
526 "is neither an async send nor an async receive. The current UDPOR "
527 "implementation does not know how to check if `CommWait` is enabled in "
528 "this case. Was a new transition added?",
529 e_issuer->get_transition()->to_string().c_str());
535 } // namespace simgrid::mc::udpor