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