src/mc/explo/udpor/UnfoldingEvent_test.cpp

   1 /* Copyright (c) 2017-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/3rd-party/catch.hpp"
   7 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
   8 #include "src/mc/explo/udpor/udpor_tests_private.hpp"
   9
  10 using namespace simgrid::mc::udpor;
  11
  12 TEST_CASE("simgrid::mc::udpor::UnfoldingEvent: Dependency/Conflict Tests")
  13 {
  14   SECTION("Properties of the relations")
  15   {
  16     // The following tests concern the given event structure:
  17     //                e1
  18     //              /   /
  19     //            e2    e6
  20     //           /  /    /
  21     //          e3   /   /
  22     //         /  /    /
  23     //        e4  e5   e7
  24     //
  25     // e5 and e6 are in conflict, e5 and e7 are in conflict, e2 and e6, and e2 ands e7 are in conflict
  26     UnfoldingEvent e1(EventSet(), std::make_shared<ConditionallyDependentAction>());
  27     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<DependentAction>());
  28     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
  29     UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
  30     UnfoldingEvent e5(EventSet({&e3}), std::make_shared<DependentAction>());
  31     UnfoldingEvent e6(EventSet({&e1}), std::make_shared<ConditionallyDependentAction>());
  32     UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<ConditionallyDependentAction>());
  33
  34     SECTION("Dependency relation properties")
  35     {
  36       SECTION("Dependency is reflexive")
  37       {
  38         REQUIRE(e2.is_dependent_with(&e2));
  39         REQUIRE(e5.is_dependent_with(&e5));
  40       }
  41
  42       SECTION("Dependency is symmetric")
  43       {
  44         REQUIRE(e2.is_dependent_with(&e6));
  45         REQUIRE(e6.is_dependent_with(&e2));
  46       }
  47
  48       SECTION("Dependency is NOT necessarily transitive")
  49       {
  50         REQUIRE(e1.is_dependent_with(&e5));
  51         REQUIRE(e5.is_dependent_with(&e7));
  52         REQUIRE_FALSE(e1.is_dependent_with(&e7));
  53       }
  54     }
  55
  56     SECTION("Conflict relation properties")
  57     {
  58       SECTION("Conflict relation is irreflexive")
  59       {
  60         REQUIRE_FALSE(e1.conflicts_with(&e1));
  61         REQUIRE_FALSE(e2.conflicts_with(&e2));
  62         REQUIRE_FALSE(e3.conflicts_with(&e3));
  63         REQUIRE_FALSE(e4.conflicts_with(&e4));
  64         REQUIRE_FALSE(e5.conflicts_with(&e5));
  65         REQUIRE_FALSE(e6.conflicts_with(&e6));
  66         REQUIRE_FALSE(e7.conflicts_with(&e7));
  67       }
  68
  69       SECTION("Conflict relation is symmetric")
  70       {
  71         REQUIRE(e5.conflicts_with(&e6));
  72         REQUIRE(e6.conflicts_with(&e5));
  73       }
  74     }
  75   }
  76
  77   SECTION("No conflicts whatsoever")
  78   {
  79     // The following tests concern the given event structure:
  80     //                e1
  81     //              /   /
  82     //            e2    e6
  83     //           /  /    /
  84     //          e3   /   /
  85     //         /  /    /
  86     //        e4  e5   e7
  87     UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
  88     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
  89     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
  90     UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
  91     UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
  92     UnfoldingEvent e6(EventSet({&e1}), std::make_shared<IndependentAction>());
  93     UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<IndependentAction>());
  94
  95     // Since everyone's actions are independent of one another, we expect
  96     // that there are no conflicts between each pair of events
  97     SECTION("Mutual dependencies")
  98     {
  99       CHECK_FALSE(e1.is_dependent_with(&e1));
 100       CHECK_FALSE(e1.is_dependent_with(&e2));
 101       CHECK_FALSE(e1.is_dependent_with(&e3));
 102       CHECK_FALSE(e1.is_dependent_with(&e4));
 103       CHECK_FALSE(e1.is_dependent_with(&e5));
 104       CHECK_FALSE(e1.is_dependent_with(&e6));
 105       CHECK_FALSE(e1.is_dependent_with(&e7));
 106
 107       CHECK_FALSE(e2.is_dependent_with(&e2));
 108       CHECK_FALSE(e2.is_dependent_with(&e3));
 109       CHECK_FALSE(e2.is_dependent_with(&e4));
 110       CHECK_FALSE(e2.is_dependent_with(&e5));
 111       CHECK_FALSE(e2.is_dependent_with(&e6));
 112       CHECK_FALSE(e2.is_dependent_with(&e7));
 113
 114       CHECK_FALSE(e3.is_dependent_with(&e3));
 115       CHECK_FALSE(e3.is_dependent_with(&e4));
 116       CHECK_FALSE(e3.is_dependent_with(&e5));
 117       CHECK_FALSE(e3.is_dependent_with(&e6));
 118       CHECK_FALSE(e3.is_dependent_with(&e7));
 119
 120       CHECK_FALSE(e4.is_dependent_with(&e4));
 121       CHECK_FALSE(e4.is_dependent_with(&e5));
 122       CHECK_FALSE(e4.is_dependent_with(&e6));
 123       CHECK_FALSE(e4.is_dependent_with(&e7));
 124
 125       CHECK_FALSE(e5.is_dependent_with(&e5));
 126       CHECK_FALSE(e5.is_dependent_with(&e6));
 127       CHECK_FALSE(e5.is_dependent_with(&e7));
 128
 129       CHECK_FALSE(e6.is_dependent_with(&e6));
 130       CHECK_FALSE(e6.is_dependent_with(&e7));
 131
 132       CHECK_FALSE(e7.is_dependent_with(&e7));
 133     }
 134
 135     SECTION("Mutual conflicts")
 136     {
 137       CHECK_FALSE(e1.conflicts_with(&e1));
 138       CHECK_FALSE(e1.conflicts_with(&e2));
 139       CHECK_FALSE(e1.conflicts_with(&e3));
 140       CHECK_FALSE(e1.conflicts_with(&e4));
 141       CHECK_FALSE(e1.conflicts_with(&e5));
 142       CHECK_FALSE(e1.conflicts_with(&e6));
 143       CHECK_FALSE(e1.conflicts_with(&e7));
 144
 145       CHECK_FALSE(e2.conflicts_with(&e1));
 146       CHECK_FALSE(e2.conflicts_with(&e2));
 147       CHECK_FALSE(e2.conflicts_with(&e3));
 148       CHECK_FALSE(e2.conflicts_with(&e4));
 149       CHECK_FALSE(e2.conflicts_with(&e5));
 150       CHECK_FALSE(e2.conflicts_with(&e6));
 151       CHECK_FALSE(e2.conflicts_with(&e7));
 152
 153       CHECK_FALSE(e3.conflicts_with(&e1));
 154       CHECK_FALSE(e3.conflicts_with(&e2));
 155       CHECK_FALSE(e3.conflicts_with(&e3));
 156       CHECK_FALSE(e3.conflicts_with(&e4));
 157       CHECK_FALSE(e3.conflicts_with(&e5));
 158       CHECK_FALSE(e3.conflicts_with(&e6));
 159       CHECK_FALSE(e3.conflicts_with(&e7));
 160
 161       CHECK_FALSE(e4.conflicts_with(&e1));
 162       CHECK_FALSE(e4.conflicts_with(&e2));
 163       CHECK_FALSE(e4.conflicts_with(&e3));
 164       CHECK_FALSE(e4.conflicts_with(&e4));
 165       CHECK_FALSE(e4.conflicts_with(&e5));
 166       CHECK_FALSE(e4.conflicts_with(&e6));
 167       CHECK_FALSE(e4.conflicts_with(&e7));
 168
 169       CHECK_FALSE(e5.conflicts_with(&e1));
 170       CHECK_FALSE(e5.conflicts_with(&e2));
 171       CHECK_FALSE(e5.conflicts_with(&e3));
 172       CHECK_FALSE(e5.conflicts_with(&e4));
 173       CHECK_FALSE(e5.conflicts_with(&e5));
 174       CHECK_FALSE(e5.conflicts_with(&e6));
 175       CHECK_FALSE(e5.conflicts_with(&e7));
 176
 177       CHECK_FALSE(e6.conflicts_with(&e1));
 178       CHECK_FALSE(e6.conflicts_with(&e2));
 179       CHECK_FALSE(e6.conflicts_with(&e3));
 180       CHECK_FALSE(e6.conflicts_with(&e4));
 181       CHECK_FALSE(e6.conflicts_with(&e5));
 182       CHECK_FALSE(e6.conflicts_with(&e6));
 183       CHECK_FALSE(e6.conflicts_with(&e7));
 184
 185       CHECK_FALSE(e7.conflicts_with(&e1));
 186       CHECK_FALSE(e7.conflicts_with(&e2));
 187       CHECK_FALSE(e7.conflicts_with(&e3));
 188       CHECK_FALSE(e7.conflicts_with(&e4));
 189       CHECK_FALSE(e7.conflicts_with(&e5));
 190       CHECK_FALSE(e7.conflicts_with(&e6));
 191       CHECK_FALSE(e7.conflicts_with(&e7));
 192     }
 193   }
 194
 195   SECTION("General conflicts")
 196   {
 197     // The following tests concern the given event structure:
 198     //                e1
 199     //              /   /
 200     //            e2    e6
 201     //           /  /    /
 202     //          e3   /   /
 203     //         /  /    /
 204     //        e4  e5   e7
 205     UnfoldingEvent e1(EventSet(), std::make_shared<DependentAction>());
 206     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<DependentAction>());
 207     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 208     UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 209     UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
 210     UnfoldingEvent e6(EventSet({&e1}), std::make_shared<IndependentAction>());
 211     UnfoldingEvent e7(EventSet({&e6, &e2}), std::make_shared<ConditionallyDependentAction>());
 212
 213     // Since everyone's actions are independent of one another, we expect
 214     // that there are no conflicts between each pair of events
 215     SECTION("Mutual dependencies")
 216     {
 217       CHECK(e1.is_dependent_with(&e1));
 218       CHECK(e1.is_dependent_with(&e2));
 219       CHECK_FALSE(e1.is_dependent_with(&e3));
 220       CHECK_FALSE(e1.is_dependent_with(&e4));
 221       CHECK_FALSE(e1.is_dependent_with(&e5));
 222       CHECK_FALSE(e1.is_dependent_with(&e6));
 223       CHECK(e1.is_dependent_with(&e7));
 224
 225       CHECK(e2.is_dependent_with(&e2));
 226       CHECK_FALSE(e2.is_dependent_with(&e3));
 227       CHECK_FALSE(e2.is_dependent_with(&e4));
 228       CHECK_FALSE(e2.is_dependent_with(&e5));
 229       CHECK_FALSE(e2.is_dependent_with(&e6));
 230       CHECK(e2.is_dependent_with(&e7));
 231
 232       CHECK_FALSE(e3.is_dependent_with(&e3));
 233       CHECK_FALSE(e3.is_dependent_with(&e4));
 234       CHECK_FALSE(e3.is_dependent_with(&e5));
 235       CHECK_FALSE(e3.is_dependent_with(&e6));
 236       CHECK_FALSE(e3.is_dependent_with(&e7));
 237
 238       CHECK_FALSE(e4.is_dependent_with(&e4));
 239       CHECK_FALSE(e4.is_dependent_with(&e5));
 240       CHECK_FALSE(e4.is_dependent_with(&e6));
 241       CHECK_FALSE(e4.is_dependent_with(&e7));
 242
 243       CHECK_FALSE(e5.is_dependent_with(&e5));
 244       CHECK_FALSE(e5.is_dependent_with(&e6));
 245       CHECK_FALSE(e5.is_dependent_with(&e7));
 246
 247       CHECK_FALSE(e6.is_dependent_with(&e6));
 248       CHECK_FALSE(e6.is_dependent_with(&e7));
 249
 250       CHECK_FALSE(e7.is_dependent_with(&e7));
 251     }
 252
 253     SECTION("Mutual conflicts")
 254     {
 255       // Although e1 is dependent with e1, e2, and e7,
 256       // since they are related to one another, they are not
 257       // considered to be in conflict
 258       CHECK_FALSE(e1.conflicts_with(&e1));
 259       CHECK_FALSE(e1.conflicts_with(&e2));
 260       CHECK_FALSE(e1.conflicts_with(&e3));
 261       CHECK_FALSE(e1.conflicts_with(&e4));
 262       CHECK_FALSE(e1.conflicts_with(&e5));
 263       CHECK_FALSE(e1.conflicts_with(&e6));
 264       CHECK_FALSE(e1.conflicts_with(&e7));
 265
 266       // Same goes for e2 with e2 and e7
 267       CHECK_FALSE(e2.conflicts_with(&e1));
 268       CHECK_FALSE(e2.conflicts_with(&e2));
 269       CHECK_FALSE(e2.conflicts_with(&e3));
 270       CHECK_FALSE(e2.conflicts_with(&e4));
 271       CHECK_FALSE(e2.conflicts_with(&e5));
 272       CHECK_FALSE(e2.conflicts_with(&e6));
 273       CHECK_FALSE(e2.conflicts_with(&e7));
 274
 275       CHECK_FALSE(e3.conflicts_with(&e1));
 276       CHECK_FALSE(e3.conflicts_with(&e2));
 277       CHECK_FALSE(e3.conflicts_with(&e3));
 278       CHECK_FALSE(e3.conflicts_with(&e4));
 279       CHECK_FALSE(e3.conflicts_with(&e5));
 280       CHECK_FALSE(e3.conflicts_with(&e6));
 281       CHECK_FALSE(e3.conflicts_with(&e7));
 282
 283       CHECK_FALSE(e4.conflicts_with(&e1));
 284       CHECK_FALSE(e4.conflicts_with(&e2));
 285       CHECK_FALSE(e4.conflicts_with(&e3));
 286       CHECK_FALSE(e4.conflicts_with(&e4));
 287       CHECK_FALSE(e4.conflicts_with(&e5));
 288       CHECK_FALSE(e4.conflicts_with(&e6));
 289       CHECK_FALSE(e4.conflicts_with(&e7));
 290
 291       CHECK_FALSE(e5.conflicts_with(&e1));
 292       CHECK_FALSE(e5.conflicts_with(&e2));
 293       CHECK_FALSE(e5.conflicts_with(&e3));
 294       CHECK_FALSE(e5.conflicts_with(&e4));
 295       CHECK_FALSE(e5.conflicts_with(&e5));
 296       CHECK_FALSE(e5.conflicts_with(&e6));
 297       CHECK_FALSE(e5.conflicts_with(&e7));
 298
 299       CHECK_FALSE(e6.conflicts_with(&e1));
 300       CHECK_FALSE(e6.conflicts_with(&e2));
 301       CHECK_FALSE(e6.conflicts_with(&e3));
 302       CHECK_FALSE(e6.conflicts_with(&e4));
 303       CHECK_FALSE(e6.conflicts_with(&e5));
 304       CHECK_FALSE(e6.conflicts_with(&e6));
 305       CHECK_FALSE(e6.conflicts_with(&e7));
 306
 307       CHECK_FALSE(e7.conflicts_with(&e1));
 308       CHECK_FALSE(e7.conflicts_with(&e2));
 309       CHECK_FALSE(e7.conflicts_with(&e3));
 310       CHECK_FALSE(e7.conflicts_with(&e4));
 311       CHECK_FALSE(e7.conflicts_with(&e5));
 312       CHECK_FALSE(e7.conflicts_with(&e6));
 313       CHECK_FALSE(e7.conflicts_with(&e7));
 314     }
 315   }
 316
 317   SECTION("More complicated conflicts")
 318   {
 319     // The following tests concern the given event structure:
 320     //                e1
 321     //              /   /
 322     //            e2    e6
 323     //           /      /
 324     //          e3      /
 325     //         /  /    e7
 326     //        e4  e5
 327     UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 328     UnfoldingEvent e2(EventSet({&e1}), std::make_shared<ConditionallyDependentAction>());
 329     UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 330     UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 331     UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
 332     UnfoldingEvent e6(EventSet({&e1}), std::make_shared<DependentAction>());
 333     UnfoldingEvent e7(EventSet({&e6}), std::make_shared<IndependentAction>());
 334
 335     CHECK_FALSE(e1.conflicts_with(&e1));
 336     CHECK_FALSE(e1.conflicts_with(&e2));
 337     CHECK_FALSE(e1.conflicts_with(&e3));
 338     CHECK_FALSE(e1.conflicts_with(&e4));
 339     CHECK_FALSE(e1.conflicts_with(&e5));
 340     CHECK_FALSE(e1.conflicts_with(&e6));
 341     CHECK_FALSE(e1.conflicts_with(&e7));
 342
 343     // e2 conflicts with e6. Since e6 < e7,
 344     // e2 also conflicts with e7
 345     CHECK_FALSE(e2.conflicts_with(&e1));
 346     CHECK_FALSE(e2.conflicts_with(&e2));
 347     CHECK_FALSE(e2.conflicts_with(&e3));
 348     CHECK_FALSE(e2.conflicts_with(&e4));
 349     CHECK_FALSE(e2.conflicts_with(&e5));
 350     CHECK(e2.conflicts_with(&e6));
 351     REQUIRE(e2.conflicts_with(&e7));
 352
 353     // e3 and e6 are dependent and unrelated, so they conflict
 354     CHECK_FALSE(e3.conflicts_with(&e1));
 355     CHECK_FALSE(e3.conflicts_with(&e2));
 356     CHECK_FALSE(e3.conflicts_with(&e3));
 357     CHECK_FALSE(e3.conflicts_with(&e4));
 358     CHECK_FALSE(e3.conflicts_with(&e5));
 359     CHECK(e3.conflicts_with(&e6));
 360     CHECK_FALSE(e3.conflicts_with(&e7));
 361
 362     // Since e3 and e6 conflict and e3 < e4, e4 and e6 conflict
 363     CHECK_FALSE(e4.conflicts_with(&e1));
 364     CHECK_FALSE(e4.conflicts_with(&e2));
 365     CHECK_FALSE(e4.conflicts_with(&e3));
 366     CHECK_FALSE(e4.conflicts_with(&e4));
 367     CHECK_FALSE(e4.conflicts_with(&e5));
 368     CHECK(e4.conflicts_with(&e6));
 369     CHECK_FALSE(e4.conflicts_with(&e7));
 370
 371     // Likewise for e5
 372     CHECK_FALSE(e5.conflicts_with(&e1));
 373     CHECK_FALSE(e5.conflicts_with(&e2));
 374     CHECK_FALSE(e5.conflicts_with(&e3));
 375     CHECK_FALSE(e5.conflicts_with(&e4));
 376     CHECK_FALSE(e5.conflicts_with(&e5));
 377     CHECK(e5.conflicts_with(&e6));
 378     CHECK_FALSE(e5.conflicts_with(&e7));
 379
 380     // Conflicts are symmetric
 381     CHECK_FALSE(e6.conflicts_with(&e1));
 382     CHECK(e6.conflicts_with(&e2));
 383     CHECK(e6.conflicts_with(&e3));
 384     CHECK(e6.conflicts_with(&e4));
 385     CHECK(e6.conflicts_with(&e5));
 386     CHECK_FALSE(e6.conflicts_with(&e6));
 387     CHECK_FALSE(e6.conflicts_with(&e7));
 388
 389     CHECK_FALSE(e7.conflicts_with(&e1));
 390     CHECK(e7.conflicts_with(&e2));
 391     CHECK_FALSE(e7.conflicts_with(&e3));
 392     CHECK_FALSE(e7.conflicts_with(&e4));
 393     CHECK_FALSE(e7.conflicts_with(&e5));
 394     CHECK_FALSE(e7.conflicts_with(&e6));
 395     CHECK_FALSE(e7.conflicts_with(&e7));
 396   }
 397 }