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