src/mc/explo/odpor/ClockVector_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/api/ClockVector.hpp"
   8
   9 using namespace simgrid::mc;
  10
  11 TEST_CASE("simgrid::mc::ClockVector: Constructing Vectors")
  12 {
  13   SECTION("Without values")
  14   {
  15     ClockVector cv;
  16     REQUIRE(cv.size() == 0);
  17
  18     // Verify `cv` doesn't map any values
  19     REQUIRE_FALSE(cv.get(0).has_value());
  20     REQUIRE_FALSE(cv.get(1).has_value());
  21     REQUIRE_FALSE(cv.get(2).has_value());
  22     REQUIRE_FALSE(cv.get(3).has_value());
  23   }
  24
  25   SECTION("With initial values")
  26   {
  27     ClockVector cv{
  28         {1, 5}, {3, 1}, {7, 10}, {6, 5}, {8, 1}, {10, 10},
  29     };
  30     REQUIRE(cv.size() == 6);
  31
  32     // Verify `cv` maps each value
  33     REQUIRE(cv.get(1).has_value());
  34     REQUIRE(cv.get(1).value() == 5);
  35     REQUIRE(cv[1] == 5);
  36     REQUIRE(cv.get(3).has_value());
  37     REQUIRE(cv.get(3).value() == 1);
  38     REQUIRE(cv[3] == 1);
  39     REQUIRE(cv.get(7).has_value());
  40     REQUIRE(cv.get(7).value() == 10);
  41     REQUIRE(cv[7] == 10);
  42     REQUIRE(cv.get(6).has_value());
  43     REQUIRE(cv.get(6).value() == 5);
  44     REQUIRE(cv[6] == 5);
  45     REQUIRE(cv.get(8).has_value());
  46     REQUIRE(cv.get(8).value() == 1);
  47     REQUIRE(cv[8] == 1);
  48     REQUIRE(cv.get(10).has_value());
  49     REQUIRE(cv.get(10).value() == 10);
  50     REQUIRE(cv[10] == 10);
  51   }
  52 }
  53
  54 TEST_CASE("simgrid::mc::ClockVector: Testing operator[]")
  55 {
  56   ClockVector cv;
  57   cv[0] = 1;
  58   REQUIRE(cv.size() == 1);
  59
  60   REQUIRE(cv.get(0).has_value());
  61   REQUIRE(cv.get(0).value() == 1);
  62
  63   // Verify `cv` doesn't map other values
  64   REQUIRE_FALSE(cv.get(2).has_value());
  65   REQUIRE_FALSE(cv.get(3).has_value());
  66
  67   cv[10] = 31;
  68   REQUIRE(cv.size() == 2);
  69
  70   // Old values are still mapped
  71   REQUIRE(cv.get(0).has_value());
  72   REQUIRE(cv.get(0).value() == 1);
  73   REQUIRE(cv[0] == 1);
  74   REQUIRE(cv.get(10).has_value());
  75   REQUIRE(cv.get(10).value() == 31);
  76   REQUIRE(cv[10] == 31);
  77
  78   // Verify `cv` doesn't map other values
  79   REQUIRE_FALSE(cv.get(2).has_value());
  80   REQUIRE_FALSE(cv.get(3).has_value());
  81 }
  82
  83 TEST_CASE("simgrid::mc::ClockVector: Testing Maximal Clock Vectors")
  84 {
  85   SECTION("Max with zero clock vector yields self")
  86   {
  87     ClockVector cv1{
  88         {1, 2},
  89         {2, 10},
  90         {3, 5},
  91     };
  92     ClockVector cv2;
  93     ClockVector maxCV = ClockVector::max(cv1, cv2);
  94
  95     REQUIRE(maxCV.size() == 3);
  96     REQUIRE(maxCV.get(1).has_value());
  97     REQUIRE(maxCV.get(1).value() == 2);
  98     REQUIRE(maxCV[1] == 2);
  99
 100     REQUIRE(maxCV.get(2).has_value());
 101     REQUIRE(maxCV.get(2).value() == 10);
 102     REQUIRE(maxCV[2] == 10);
 103
 104     REQUIRE(maxCV.get(3).has_value());
 105     REQUIRE(maxCV.get(3).value() == 5);
 106     REQUIRE(maxCV[3] == 5);
 107   }
 108
 109   SECTION("Max with self clock vector yields self")
 110   {
 111     ClockVector cv1{
 112         {1, 2},
 113         {2, 10},
 114         {3, 5},
 115     };
 116     ClockVector maxCV = ClockVector::max(cv1, cv1);
 117
 118     REQUIRE(maxCV.size() == 3);
 119     REQUIRE(maxCV.get(1).has_value());
 120     REQUIRE(maxCV.get(1).value() == 2);
 121     REQUIRE(maxCV[1] == 2);
 122
 123     REQUIRE(maxCV.get(2).has_value());
 124     REQUIRE(maxCV.get(2).value() == 10);
 125     REQUIRE(maxCV[2] == 10);
 126
 127     REQUIRE(maxCV.get(3).has_value());
 128     REQUIRE(maxCV.get(3).value() == 5);
 129     REQUIRE(maxCV[3] == 5);
 130   }
 131
 132   SECTION("Testing with partial overlaps")
 133   {
 134     SECTION("Example 1")
 135     {
 136       ClockVector cv1{
 137           {1, 2},
 138           {2, 10},
 139           {3, 5},
 140       };
 141       ClockVector cv2{
 142           {1, 5},
 143           {3, 1},
 144           {7, 10},
 145       };
 146       ClockVector maxCV = ClockVector::max(cv1, cv2);
 147
 148       REQUIRE(maxCV.size() == 4);
 149       REQUIRE(maxCV.get(1).has_value());
 150       REQUIRE(maxCV.get(1).value() == 5);
 151       REQUIRE(maxCV[1] == 5);
 152
 153       REQUIRE(maxCV.get(2).has_value());
 154       REQUIRE(maxCV.get(2).value() == 10);
 155       REQUIRE(maxCV[2] == 10);
 156
 157       REQUIRE(maxCV.get(3).has_value());
 158       REQUIRE(maxCV.get(3).value() == 5);
 159       REQUIRE(maxCV[3] == 5);
 160
 161       REQUIRE(maxCV.get(7).has_value());
 162       REQUIRE(maxCV.get(7).value() == 10);
 163       REQUIRE(maxCV[7] == 10);
 164     }
 165
 166     SECTION("Example 2")
 167     {
 168       ClockVector cv1{
 169           {1, 2}, {2, 10}, {3, 5}, {4, 40}, {11, 3}, {12, 8},
 170       };
 171       ClockVector cv2{
 172           {1, 18}, {2, 4}, {4, 41}, {10, 3}, {12, 8},
 173       };
 174       ClockVector maxCV = ClockVector::max(cv1, cv2);
 175
 176       REQUIRE(maxCV.size() == 7);
 177       REQUIRE(maxCV.get(1).has_value());
 178       REQUIRE(maxCV.get(1).value() == 18);
 179       REQUIRE(maxCV[1] == 18);
 180
 181       REQUIRE(maxCV.get(2).has_value());
 182       REQUIRE(maxCV.get(2).value() == 10);
 183       REQUIRE(maxCV[2] == 10);
 184
 185       REQUIRE(maxCV.get(3).has_value());
 186       REQUIRE(maxCV.get(3).value() == 5);
 187       REQUIRE(maxCV[3] == 5);
 188
 189       REQUIRE(maxCV.get(4).has_value());
 190       REQUIRE(maxCV.get(4).value() == 41);
 191       REQUIRE(maxCV[4] == 41);
 192
 193       REQUIRE(maxCV.get(10).has_value());
 194       REQUIRE(maxCV.get(10).value() == 3);
 195       REQUIRE(maxCV[10] == 3);
 196
 197       REQUIRE(maxCV.get(11).has_value());
 198       REQUIRE(maxCV.get(11).value() == 3);
 199       REQUIRE(maxCV[11] == 3);
 200
 201       REQUIRE(maxCV.get(12).has_value());
 202       REQUIRE(maxCV.get(12).value() == 8);
 203       REQUIRE(maxCV[12] == 8);
 204     }
 205
 206     SECTION("Example 3")
 207     {
 208       ClockVector cv1{{1, 2}, {4, 41}, {12, 0}, {100, 5}};
 209       ClockVector cv2{{2, 4}, {4, 10}, {10, 3}, {12, 8}, {19, 0}, {21, 6}, {22, 0}};
 210       ClockVector cv3{{21, 60}, {22, 6}, {100, 3}};
 211       ClockVector maxCV = ClockVector::max(cv1, cv2);
 212       maxCV             = ClockVector::max(maxCV, cv3);
 213
 214       REQUIRE(maxCV.size() == 9);
 215       REQUIRE(maxCV.get(1).has_value());
 216       REQUIRE(maxCV.get(1).value() == 2);
 217       REQUIRE(maxCV[1] == 2);
 218
 219       REQUIRE(maxCV.get(2).has_value());
 220       REQUIRE(maxCV.get(2).value() == 4);
 221       REQUIRE(maxCV[2] == 4);
 222
 223       REQUIRE(maxCV.get(4).has_value());
 224       REQUIRE(maxCV.get(4).value() == 41);
 225       REQUIRE(maxCV[4] == 41);
 226
 227       REQUIRE(maxCV.get(10).has_value());
 228       REQUIRE(maxCV.get(10).value() == 3);
 229       REQUIRE(maxCV[10] == 3);
 230
 231       REQUIRE(maxCV.get(12).has_value());
 232       REQUIRE(maxCV.get(12).value() == 8);
 233       REQUIRE(maxCV[12] == 8);
 234
 235       REQUIRE(maxCV.get(19).has_value());
 236       REQUIRE(maxCV.get(19).value() == 0);
 237       REQUIRE(maxCV[19] == 0);
 238
 239       REQUIRE(maxCV.get(21).has_value());
 240       REQUIRE(maxCV.get(21).value() == 60);
 241       REQUIRE(maxCV[21] == 60);
 242
 243       REQUIRE(maxCV.get(22).has_value());
 244       REQUIRE(maxCV.get(22).value() == 6);
 245       REQUIRE(maxCV[22] == 6);
 246
 247       REQUIRE(maxCV.get(100).has_value());
 248       REQUIRE(maxCV.get(100).value() == 5);
 249       REQUIRE(maxCV[100] == 5);
 250     }
 251   }
 252
 253   SECTION("Testing without overlaps")
 254   {
 255     SECTION("Example 1")
 256     {
 257       ClockVector cv1{{1, 2}};
 258       ClockVector cv2{
 259           {2, 4},
 260           {4, 41},
 261           {10, 3},
 262           {12, 8},
 263       };
 264       ClockVector maxCV = ClockVector::max(cv1, cv2);
 265
 266       REQUIRE(maxCV.size() == 5);
 267       REQUIRE(maxCV.get(1).has_value());
 268       REQUIRE(maxCV.get(1).value() == 2);
 269       REQUIRE(maxCV[1] == 2);
 270
 271       REQUIRE(maxCV.get(2).has_value());
 272       REQUIRE(maxCV.get(2).value() == 4);
 273       REQUIRE(maxCV[2] == 4);
 274
 275       REQUIRE(maxCV.get(4).has_value());
 276       REQUIRE(maxCV.get(4).value() == 41);
 277       REQUIRE(maxCV[4] == 41);
 278
 279       REQUIRE(maxCV.get(10).has_value());
 280       REQUIRE(maxCV.get(10).value() == 3);
 281       REQUIRE(maxCV[10] == 3);
 282
 283       REQUIRE(maxCV.get(12).has_value());
 284       REQUIRE(maxCV.get(12).value() == 8);
 285       REQUIRE(maxCV[12] == 8);
 286     }
 287
 288     SECTION("Example 2")
 289     {
 290       ClockVector cv1{{1, 2}, {4, 41}};
 291       ClockVector cv2{
 292           {2, 4},
 293           {10, 3},
 294           {12, 8},
 295       };
 296       ClockVector maxCV = ClockVector::max(cv1, cv2);
 297
 298       REQUIRE(maxCV.size() == 5);
 299       REQUIRE(maxCV.get(1).has_value());
 300       REQUIRE(maxCV.get(1).value() == 2);
 301       REQUIRE(maxCV[1] == 2);
 302
 303       REQUIRE(maxCV.get(2).has_value());
 304       REQUIRE(maxCV.get(2).value() == 4);
 305       REQUIRE(maxCV[2] == 4);
 306
 307       REQUIRE(maxCV.get(4).has_value());
 308       REQUIRE(maxCV.get(4).value() == 41);
 309       REQUIRE(maxCV[4] == 41);
 310
 311       REQUIRE(maxCV.get(10).has_value());
 312       REQUIRE(maxCV.get(10).value() == 3);
 313       REQUIRE(maxCV[10] == 3);
 314
 315       REQUIRE(maxCV.get(12).has_value());
 316       REQUIRE(maxCV.get(12).value() == 8);
 317       REQUIRE(maxCV[12] == 8);
 318     }
 319
 320     SECTION("Example 3")
 321     {
 322       ClockVector cv1{{1, 2}, {4, 41}};
 323       ClockVector cv2{{2, 4}, {10, 3}, {12, 8}, {19, 0}, {21, 6}};
 324       ClockVector cv3{{22, 6}, {100, 3}};
 325       ClockVector maxCV = ClockVector::max(cv1, cv2);
 326       maxCV             = ClockVector::max(maxCV, cv3);
 327
 328       REQUIRE(maxCV.size() == 9);
 329       REQUIRE(maxCV.get(1).has_value());
 330       REQUIRE(maxCV.get(1).value() == 2);
 331       REQUIRE(maxCV[1] == 2);
 332
 333       REQUIRE(maxCV.get(2).has_value());
 334       REQUIRE(maxCV.get(2).value() == 4);
 335       REQUIRE(maxCV[2] == 4);
 336
 337       REQUIRE(maxCV.get(4).has_value());
 338       REQUIRE(maxCV.get(4).value() == 41);
 339       REQUIRE(maxCV[4] == 41);
 340
 341       REQUIRE(maxCV.get(10).has_value());
 342       REQUIRE(maxCV.get(10).value() == 3);
 343       REQUIRE(maxCV[10] == 3);
 344
 345       REQUIRE(maxCV.get(12).has_value());
 346       REQUIRE(maxCV.get(12).value() == 8);
 347       REQUIRE(maxCV[12] == 8);
 348
 349       REQUIRE(maxCV.get(19).has_value());
 350       REQUIRE(maxCV.get(19).value() == 0);
 351       REQUIRE(maxCV[19] == 0);
 352
 353       REQUIRE(maxCV.get(21).has_value());
 354       REQUIRE(maxCV.get(21).value() == 6);
 355       REQUIRE(maxCV[21] == 6);
 356
 357       REQUIRE(maxCV.get(22).has_value());
 358       REQUIRE(maxCV.get(22).value() == 6);
 359       REQUIRE(maxCV[22] == 6);
 360
 361       REQUIRE(maxCV.get(100).has_value());
 362       REQUIRE(maxCV.get(100).value() == 3);
 363       REQUIRE(maxCV[100] == 3);
 364     }
 365   }
 366 }