src/mc/explo/udpor/History_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/History.hpp"
   8 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
   9
  10 using namespace simgrid::mc::udpor;
  11
  12 TEST_CASE("simgrid::mc::udpor::History: History generation")
  13 {
  14   // The following tests concern the given event tree
  15   //        e1
  16   //    /      /
  17   //  e2        e6
  18   //  | \  \  /   /
  19   // e3 e4 e5      e7
  20   UnfoldingEvent e1;
  21   UnfoldingEvent e2{&e1}, e6{&e1};
  22   UnfoldingEvent e3{&e2}, e4{&e2};
  23   UnfoldingEvent e5{&e2, &e6}, e7{&e6};
  24
  25   SECTION("History with no events")
  26   {
  27     History history;
  28     REQUIRE(history.get_all_events() == EventSet());
  29     REQUIRE_FALSE(history.contains(&e1));
  30     REQUIRE_FALSE(history.contains(&e2));
  31     REQUIRE_FALSE(history.contains(&e3));
  32     REQUIRE_FALSE(history.contains(&e4));
  33     REQUIRE_FALSE(history.contains(&e5));
  34     REQUIRE_FALSE(history.contains(&e6));
  35     REQUIRE_FALSE(history.contains(&e7));
  36   }
  37
  38   SECTION("Histories with a single event")
  39   {
  40     SECTION("Root event's history has a single event")
  41     {
  42       History history(&e1);
  43       REQUIRE(history.get_all_events() == EventSet({&e1}));
  44     }
  45
  46     SECTION("Check node e2")
  47     {
  48       History history(&e2);
  49       REQUIRE(history.get_all_events() == EventSet({&e1, &e2}));
  50       REQUIRE(history.contains(&e1));
  51       REQUIRE(history.contains(&e2));
  52       REQUIRE_FALSE(history.contains(&e3));
  53       REQUIRE_FALSE(history.contains(&e4));
  54       REQUIRE_FALSE(history.contains(&e5));
  55       REQUIRE_FALSE(history.contains(&e6));
  56       REQUIRE_FALSE(history.contains(&e7));
  57     }
  58
  59     SECTION("Check node e3")
  60     {
  61       History history(&e3);
  62       REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e3}));
  63       REQUIRE(history.contains(&e1));
  64       REQUIRE(history.contains(&e2));
  65       REQUIRE(history.contains(&e3));
  66       REQUIRE_FALSE(history.contains(&e4));
  67       REQUIRE_FALSE(history.contains(&e5));
  68       REQUIRE_FALSE(history.contains(&e6));
  69       REQUIRE_FALSE(history.contains(&e7));
  70     }
  71
  72     SECTION("Check node e4")
  73     {
  74       History history(&e4);
  75       REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e4}));
  76       REQUIRE(history.contains(&e1));
  77       REQUIRE(history.contains(&e2));
  78       REQUIRE_FALSE(history.contains(&e3));
  79       REQUIRE(history.contains(&e4));
  80       REQUIRE_FALSE(history.contains(&e5));
  81       REQUIRE_FALSE(history.contains(&e6));
  82       REQUIRE_FALSE(history.contains(&e7));
  83     }
  84
  85     SECTION("Check node e5")
  86     {
  87       History history(&e5);
  88       REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e6, &e5}));
  89       REQUIRE(history.contains(&e1));
  90       REQUIRE(history.contains(&e2));
  91       REQUIRE_FALSE(history.contains(&e3));
  92       REQUIRE_FALSE(history.contains(&e4));
  93       REQUIRE(history.contains(&e5));
  94       REQUIRE(history.contains(&e6));
  95       REQUIRE_FALSE(history.contains(&e7));
  96     }
  97
  98     SECTION("Check node e6")
  99     {
 100       History history(&e6);
 101       REQUIRE(history.get_all_events() == EventSet({&e1, &e6}));
 102       REQUIRE(history.contains(&e1));
 103       REQUIRE_FALSE(history.contains(&e2));
 104       REQUIRE_FALSE(history.contains(&e3));
 105       REQUIRE_FALSE(history.contains(&e4));
 106       REQUIRE_FALSE(history.contains(&e5));
 107       REQUIRE(history.contains(&e6));
 108       REQUIRE_FALSE(history.contains(&e7));
 109     }
 110
 111     SECTION("Check node e7")
 112     {
 113       History history(&e7);
 114       REQUIRE(history.get_all_events() == EventSet({&e1, &e6, &e7}));
 115       REQUIRE(history.contains(&e1));
 116       REQUIRE_FALSE(history.contains(&e2));
 117       REQUIRE_FALSE(history.contains(&e3));
 118       REQUIRE_FALSE(history.contains(&e4));
 119       REQUIRE_FALSE(history.contains(&e5));
 120       REQUIRE(history.contains(&e6));
 121       REQUIRE(history.contains(&e7));
 122     }
 123   }
 124
 125   SECTION("Histories with multiple nodes")
 126   {
 127     SECTION("Nodes contained in the same branch")
 128     {
 129       History history_e1e2(EventSet({&e1, &e2}));
 130       REQUIRE(history_e1e2.get_all_events() == EventSet({&e1, &e2}));
 131       REQUIRE(history_e1e2.contains(&e1));
 132       REQUIRE(history_e1e2.contains(&e2));
 133       REQUIRE_FALSE(history_e1e2.contains(&e3));
 134       REQUIRE_FALSE(history_e1e2.contains(&e4));
 135       REQUIRE_FALSE(history_e1e2.contains(&e5));
 136       REQUIRE_FALSE(history_e1e2.contains(&e6));
 137       REQUIRE_FALSE(history_e1e2.contains(&e7));
 138
 139       History history_e1e3(EventSet({&e1, &e3}));
 140       REQUIRE(history_e1e3.get_all_events() == EventSet({&e1, &e2, &e3}));
 141       REQUIRE(history_e1e3.contains(&e1));
 142       REQUIRE(history_e1e3.contains(&e2));
 143       REQUIRE(history_e1e3.contains(&e3));
 144       REQUIRE_FALSE(history_e1e3.contains(&e4));
 145       REQUIRE_FALSE(history_e1e3.contains(&e5));
 146       REQUIRE_FALSE(history_e1e3.contains(&e6));
 147       REQUIRE_FALSE(history_e1e3.contains(&e7));
 148
 149       History history_e6e7(EventSet({&e6, &e7}));
 150       REQUIRE(history_e6e7.get_all_events() == EventSet({&e1, &e6, &e7}));
 151       REQUIRE(history_e6e7.contains(&e1));
 152       REQUIRE_FALSE(history_e6e7.contains(&e2));
 153       REQUIRE_FALSE(history_e6e7.contains(&e3));
 154       REQUIRE_FALSE(history_e6e7.contains(&e4));
 155       REQUIRE_FALSE(history_e6e7.contains(&e5));
 156       REQUIRE(history_e6e7.contains(&e6));
 157       REQUIRE(history_e6e7.contains(&e7));
 158     }
 159
 160     SECTION("Nodes with the same ancestor")
 161     {
 162       History history_e3e5(EventSet({&e3, &e5}));
 163       REQUIRE(history_e3e5.get_all_events() == EventSet({&e1, &e2, &e3, &e5, &e6}));
 164       REQUIRE(history_e3e5.contains(&e1));
 165       REQUIRE(history_e3e5.contains(&e2));
 166       REQUIRE(history_e3e5.contains(&e3));
 167       REQUIRE_FALSE(history_e3e5.contains(&e4));
 168       REQUIRE(history_e3e5.contains(&e5));
 169       REQUIRE(history_e3e5.contains(&e6));
 170       REQUIRE_FALSE(history_e3e5.contains(&e7));
 171     }
 172
 173     SECTION("Nodes with different ancestors")
 174     {
 175       History history_e4e7(EventSet({&e4, &e7}));
 176       REQUIRE(history_e4e7.get_all_events() == EventSet({&e1, &e2, &e4, &e6, &e7}));
 177       REQUIRE(history_e4e7.contains(&e1));
 178       REQUIRE(history_e4e7.contains(&e2));
 179       REQUIRE_FALSE(history_e4e7.contains(&e3));
 180       REQUIRE(history_e4e7.contains(&e4));
 181       REQUIRE_FALSE(history_e4e7.contains(&e5));
 182       REQUIRE(history_e4e7.contains(&e6));
 183       REQUIRE(history_e4e7.contains(&e7));
 184     }
 185
 186     SECTION("Large number of nodes")
 187     {
 188       History history_e2356(EventSet({&e2, &e3, &e5, &e6}));
 189       REQUIRE(history_e2356.get_all_events() == EventSet({&e1, &e2, &e3, &e5, &e6}));
 190       REQUIRE(history_e2356.contains(&e1));
 191       REQUIRE(history_e2356.contains(&e2));
 192       REQUIRE(history_e2356.contains(&e3));
 193       REQUIRE_FALSE(history_e2356.contains(&e4));
 194       REQUIRE(history_e2356.contains(&e5));
 195       REQUIRE(history_e2356.contains(&e6));
 196       REQUIRE_FALSE(history_e2356.contains(&e7));
 197     }
 198
 199     SECTION("History of the entire graph yields the entire graph")
 200     {
 201       History history(EventSet({&e1, &e2, &e3, &e4, &e5, &e6, &e7}));
 202       REQUIRE(history.get_all_events() == EventSet({&e1, &e2, &e3, &e4, &e5, &e6, &e7}));
 203       REQUIRE(history.contains(&e1));
 204       REQUIRE(history.contains(&e2));
 205       REQUIRE(history.contains(&e3));
 206       REQUIRE(history.contains(&e4));
 207       REQUIRE(history.contains(&e5));
 208       REQUIRE(history.contains(&e6));
 209       REQUIRE(history.contains(&e7));
 210     }
 211   }
 212 }