hphp/runtime/test/id-set.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/vm/jit/id-set.h"
  18
  19 #include <folly/Lazy.h>
  20 #include <folly/portability/GTest.h>
  21
  22 namespace HPHP::jit {
  23
  24 namespace {
  25
  26 struct Foo {
  27   explicit Foo(uint32_t id) : m_id{id} {}
  28   uint32_t id() const { return m_id; }
  29   uint32_t m_id;
  30
  31   bool operator<(const Foo& o) const {
  32     return m_id < o.m_id;
  33   }
  34   bool operator==(const Foo& o) const {
  35     return m_id == o.m_id;
  36   }
  37 };
  38
  39 using FooVector = std::vector<Foo>;
  40 using FooSet = IdSet<Foo>;
  41
  42 void PrintTo(const Foo& f, std::ostream* os) {
  43   *os << f.id();
  44 }
  45
  46 void PrintTo(const FooVector& v, std::ostream* os) {
  47   *os << '{';
  48   auto first = true;
  49   for (auto const& foo : v) {
  50     if (!first) *os << ", ";
  51     first = false;
  52     *os << foo.id();
  53   }
  54   *os << '}';
  55 }
  56
  57 FooVector toFooVector(const FooSet& s) {
  58   FooVector ret;
  59   s.forEach([&] (uint32_t id) { ret.emplace_back(Foo{id}); });
  60   return ret;
  61 }
  62
  63 bool inFooVector(const FooVector& v, const Foo& f) {
  64   return std::find(v.begin(), v.end(), f) != v.end();
  65 }
  66
  67 void removeFromFooVector(FooVector& v, const Foo& f) {
  68   v.erase(std::remove(v.begin(), v.end(), f), v.end());
  69 }
  70
  71 FooVector unionFooVector(const FooVector& v1, const FooVector& v2) {
  72   auto out = v1;
  73   out.insert(out.end(), v2.begin(), v2.end());
  74   std::sort(out.begin(), out.end());
  75   out.erase(std::unique(out.begin(), out.end()), out.end());
  76   return out;
  77 }
  78
  79 auto const foos = folly::lazy(
  80   [] {
  81     return FooVector{
  82       Foo{0},
  83       Foo{1},
  84       Foo{FooSet::kBlockSize - 1},
  85       Foo{FooSet::kBlockSize},
  86       Foo{FooSet::kBlockSize + 1},
  87       Foo{FooSet::kBlockSize * 2 - 1},
  88       Foo{FooSet::kBlockSize * 2},
  89       Foo{FooSet::kBlockSize * 2 + 1},
  90       Foo{FooSet::kBlockSize * 5 + 27}
  91     };
  92   }
  93 );
  94
  95 auto const membershipFoos = folly::lazy(
  96   [] {
  97     auto out = foos();
  98     out.emplace_back(Foo{2});
  99     out.emplace_back(FooSet::kBlockSize + 5);
 100     out.emplace_back(FooSet::kBlockSize * 4 - 7);
 101     out.emplace_back(1000001);
 102     return out;
 103   }
 104 );
 105
 106 auto const eraseOpFoos = folly::lazy(
 107   [] {
 108     return FooVector{
 109       Foo{1},
 110       Foo{FooSet::kBlockSize + 1},
 111       Foo{FooSet::kBlockSize * 2 + 1},
 112       Foo{FooSet::kBlockSize * 3 + 1},
 113       Foo{FooSet::kBlockSize * 4 + 1}
 114     };
 115   }
 116 );
 117
 118 auto const eraseOpFoosWithZero = folly::lazy(
 119   [] {
 120     auto out = eraseOpFoos();
 121     out.emplace_back(Foo{0});
 122     return out;
 123   }
 124 );
 125
 126 auto const eraseOpFoosWithZeroPairs = folly::lazy(
 127   [] {
 128     std::vector<std::pair<Foo, Foo>> out;
 129     for (auto const& f1 : eraseOpFoosWithZero()) {
 130       for (auto const& f2 : eraseOpFoosWithZero()) {
 131         out.emplace_back(f1, f2);
 132       }
 133     }
 134     return out;
 135   }
 136 );
 137
 138 std::vector<FooVector> makeSubsets(const FooVector& v) {
 139   std::vector<FooVector> out;
 140
 141   uint64_t selected = 0;
 142   while (selected < (1ULL << v.size())) {
 143     FooVector current;
 144     for (size_t i = 0; i < v.size(); ++i) {
 145       if (selected & (1ULL << i)) current.emplace_back(v[i]);
 146     }
 147     out.emplace_back(std::move(current));
 148     ++selected;
 149   }
 150
 151   return out;
 152 }
 153
 154 void sortSubsets(std::vector<FooVector>& subsets) {
 155   for (auto& subset : subsets) std::sort(subset.begin(), subset.end());
 156 }
 157
 158 std::vector<FooVector> permutations(const std::vector<FooVector>& sorted) {
 159   std::vector<FooVector> out;
 160   for (auto subset : sorted) {
 161     do {
 162       out.emplace_back(subset);
 163     } while (std::next_permutation(subset.begin(), subset.end()));
 164   }
 165   return out;
 166 }
 167
 168 auto const subsets =
 169   folly::lazy([] { return makeSubsets(foos()); });
 170 auto const eraseOpSubsets =
 171   folly::lazy([] { return makeSubsets(eraseOpFoos()); });
 172
 173 auto const sortedSubsets = folly::lazy(
 174   [] {
 175     auto s = subsets();
 176     sortSubsets(s);
 177     return s;
 178   }
 179 );
 180
 181 auto const sortedEraseOpSubsets = folly::lazy(
 182   [] {
 183     auto s = eraseOpSubsets();
 184     sortSubsets(s);
 185     return s;
 186   }
 187 );
 188
 189 auto const all =
 190   folly::lazy([] { return permutations(sortedSubsets()); });
 191 auto const eraseOpAll =
 192   folly::lazy([] { return permutations(sortedEraseOpSubsets()); });
 193
 194 }
 195
 196 TEST(IdSet, Add) {
 197   for (auto values : all()) {
 198     FooSet s;
 199     for (auto const& value : values) s.add(value);
 200
 201     EXPECT_EQ(s.none(), values.empty());
 202     for (auto const& foo : membershipFoos()) {
 203       EXPECT_EQ(s[foo], inFooVector(values, foo));
 204     }
 205     std::sort(values.begin(), values.end());
 206     EXPECT_EQ(toFooVector(s), values);
 207   }
 208 }
 209
 210 TEST(IdSet, Erase) {
 211   for (auto values : sortedSubsets()) {
 212     FooSet s;
 213     for (auto const& value : values) s.add(value);
 214
 215     for (auto const& foo : membershipFoos()) {
 216       s.erase(foo);
 217       removeFromFooVector(values, foo);
 218       EXPECT_FALSE(s[foo]);
 219       EXPECT_EQ(toFooVector(s), values);
 220       for (auto const& foo : membershipFoos()) {
 221         EXPECT_EQ(s[foo], inFooVector(values, foo));
 222       }
 223     }
 224
 225     EXPECT_TRUE(s.none());
 226   }
 227 }
 228
 229 TEST(IdSet, Clear) {
 230   for (auto const& values : sortedSubsets()) {
 231     FooSet s;
 232     for (auto const& value : values) s.add(value);
 233     s.clear();
 234
 235     EXPECT_TRUE(s.none());
 236     for (auto const& foo : membershipFoos()) EXPECT_FALSE(s[foo]);
 237     EXPECT_EQ(toFooVector(s), FooVector{});
 238   }
 239 }
 240
 241 TEST(IdSet, AddDuplicate) {
 242   for (auto const& values : sortedSubsets()) {
 243     FooSet s;
 244     for (auto const& value : values) s.add(value);
 245
 246     for (auto const& foo : foos()) {
 247       if (!inFooVector(values, foo)) continue;
 248       EXPECT_TRUE(s[foo]);
 249       s.add(foo);
 250       EXPECT_TRUE(s[foo]);
 251       EXPECT_EQ(toFooVector(s), values);
 252       for (auto const& foo : membershipFoos()) {
 253         EXPECT_EQ(s[foo], inFooVector(values, foo));
 254       }
 255     }
 256   }
 257 }
 258
 259 TEST(IdSet, Copy) {
 260   for (auto const& values : sortedSubsets()) {
 261     FooSet s;
 262     for (auto const& value : values) s.add(value);
 263
 264     auto const s2 = s;
 265     EXPECT_EQ(toFooVector(s), toFooVector(s2));
 266     EXPECT_EQ(toFooVector(s2), values);
 267     for (auto const& foo : membershipFoos()) {
 268       EXPECT_EQ(s[foo], s2[foo]);
 269       EXPECT_EQ(s2[foo], inFooVector(values, foo));
 270     }
 271     EXPECT_EQ(s.none(), s2.none());
 272     EXPECT_EQ(values.empty(), s2.none());
 273   }
 274 }
 275
 276 TEST(IdSet, MoveCopy) {
 277   for (auto const& values : sortedSubsets()) {
 278     FooSet s;
 279     for (auto const& value : values) s.add(value);
 280
 281     auto const orig = s;
 282     auto const s2 = std::move(s);
 283     EXPECT_EQ(toFooVector(orig), toFooVector(s2));
 284     EXPECT_EQ(toFooVector(s2), values);
 285     for (auto const& foo : membershipFoos()) {
 286       EXPECT_EQ(orig[foo], s2[foo]);
 287       EXPECT_EQ(s2[foo], inFooVector(values, foo));
 288     }
 289     EXPECT_EQ(orig.none(), s2.none());
 290     EXPECT_EQ(values.empty(), s2.none());
 291   }
 292 }
 293
 294 TEST(IdSet, Assign) {
 295   for (auto const& values1 : sortedSubsets()) {
 296     for (auto const& values2 : sortedSubsets()) {
 297       FooSet s1, s2;
 298       for (auto const& value : values1) s1.add(value);
 299       for (auto const& value : values2) s2.add(value);
 300       s1 = s2;
 301
 302       EXPECT_EQ(toFooVector(s1), toFooVector(s2));
 303       EXPECT_EQ(toFooVector(s1), values2);
 304       for (auto const& foo : membershipFoos()) {
 305         EXPECT_EQ(s1[foo], s2[foo]);
 306         EXPECT_EQ(s1[foo], inFooVector(values2, foo));
 307       }
 308       EXPECT_EQ(s1.none(), s2.none());
 309       EXPECT_EQ(values2.empty(), s1.none());
 310     }
 311   }
 312 }
 313
 314 TEST(IdSet, MoveAssign) {
 315   for (auto const& values1 : sortedSubsets()) {
 316     for (auto const& values2 : sortedSubsets()) {
 317       FooSet s1, s2;
 318       for (auto const& value : values1) s1.add(value);
 319       for (auto const& value : values2) s2.add(value);
 320       auto const s3 = s2;
 321       s1 = std::move(s2);
 322
 323       EXPECT_EQ(toFooVector(s1), toFooVector(s3));
 324       EXPECT_EQ(toFooVector(s1), values2);
 325       for (auto const& foo : membershipFoos()) {
 326         EXPECT_EQ(s1[foo], s3[foo]);
 327         EXPECT_EQ(s1[foo], inFooVector(values2, foo));
 328       }
 329       EXPECT_EQ(s1.none(), s3.none());
 330       EXPECT_EQ(values2.empty(), s1.none());
 331     }
 332   }
 333 }
 334
 335 TEST(IdSet, Swap) {
 336   for (auto const& values1 : sortedSubsets()) {
 337     for (auto const& values2 : sortedSubsets()) {
 338       FooSet s1, s2;
 339       for (auto const& value : values1) s1.add(value);
 340       for (auto const& value : values2) s2.add(value);
 341       s1.swap(s2);
 342
 343       EXPECT_EQ(toFooVector(s1), values2);
 344       EXPECT_EQ(toFooVector(s2), values1);
 345       for (auto const& foo : membershipFoos()) {
 346         EXPECT_EQ(s1[foo], inFooVector(values2, foo));
 347         EXPECT_EQ(s2[foo], inFooVector(values1, foo));
 348       }
 349       EXPECT_EQ(values2.empty(), s1.none());
 350       EXPECT_EQ(values1.empty(), s2.none());
 351     }
 352   }
 353 }
 354
 355 TEST(IdSet, Union) {
 356   for (auto const& values1 : sortedSubsets()) {
 357     for (auto const& values2 : sortedSubsets()) {
 358       FooSet s1, s2;
 359       for (auto const& value : values1) s1.add(value);
 360       for (auto const& value : values2) s2.add(value);
 361       auto s3 = s1;
 362       s3 |= s2;
 363       auto const values3 = unionFooVector(values1, values2);
 364       EXPECT_EQ(toFooVector(s3), values3);
 365       for (auto const& foo : membershipFoos()) {
 366         EXPECT_EQ(s1[foo] || s2[foo], s3[foo]);
 367         EXPECT_EQ(s3[foo], inFooVector(values3, foo));
 368       }
 369       EXPECT_EQ(s1.none() && s2.none(), s3.none());
 370       EXPECT_EQ(values3.empty(), s3.none());
 371     }
 372   }
 373 }
 374
 375 namespace {
 376
 377 template <typename F> void forEachEraseOpCase(F&& f) {
 378   for (auto const& values : sortedEraseOpSubsets()) {
 379     for (auto const& p : eraseOpFoosWithZeroPairs()) {
 380       FooSet s;
 381       for (auto const& value : values) s.add(value);
 382       s.erase(p.first);
 383       s.erase(p.second);
 384       auto v = values;
 385       removeFromFooVector(v, p.first);
 386       removeFromFooVector(v, p.second);
 387       f(s, v);
 388     }
 389   }
 390 }
 391
 392 template <typename F> void forEachEraseOpPair(F&& f) {
 393   for (auto const& values1 : sortedEraseOpSubsets()) {
 394     for (auto const& values2 : sortedEraseOpSubsets()) {
 395       for (auto const& erase1 : eraseOpFoosWithZeroPairs()) {
 396         for (auto const& erase2 : eraseOpFoosWithZeroPairs()) {
 397           FooSet s1, s2;
 398           for (auto const& value : values1) s1.add(value);
 399           for (auto const& value : values2) s2.add(value);
 400           s1.erase(erase1.first);
 401           s1.erase(erase1.second);
 402           s2.erase(erase2.first);
 403           s2.erase(erase2.second);
 404
 405           auto v1 = values1;
 406           auto v2 = values2;
 407           removeFromFooVector(v1, erase1.first);
 408           removeFromFooVector(v1, erase1.second);
 409           removeFromFooVector(v2, erase2.first);
 410           removeFromFooVector(v2, erase2.second);
 411           f(s1, v1, s2, v2);
 412         }
 413       }
 414     }
 415   }
 416 }
 417
 418 }
 419
 420 TEST(IdSet, EraseCopy) {
 421   forEachEraseOpCase(
 422     [&] (const FooSet& s1, const FooVector& v1) {
 423       auto const s2 = s1;
 424       EXPECT_EQ(toFooVector(s1), toFooVector(s2));
 425       EXPECT_EQ(toFooVector(s2), v1);
 426       for (auto const& foo : eraseOpFoos()) {
 427         EXPECT_EQ(s1[foo], s2[foo]);
 428         EXPECT_EQ(s2[foo], inFooVector(v1, foo));
 429       }
 430       EXPECT_EQ(s1.none(), s2.none());
 431       EXPECT_EQ(v1.empty(), s2.none());
 432     }
 433   );
 434 }
 435
 436 TEST(IdSet, EraseAssign) {
 437   forEachEraseOpPair(
 438     [&] (FooSet& s1, const FooVector&,
 439          const FooSet& s2, const FooVector& v2) {
 440       s1 = s2;
 441       EXPECT_EQ(toFooVector(s1), toFooVector(s2));
 442       EXPECT_EQ(toFooVector(s1), v2);
 443       for (auto const& foo : eraseOpFoos()) {
 444         EXPECT_EQ(s1[foo], s2[foo]);
 445         EXPECT_EQ(s1[foo], inFooVector(v2, foo));
 446       }
 447       EXPECT_EQ(s1.none(), s2.none());
 448       EXPECT_EQ(v2.empty(), s1.none());
 449     }
 450   );
 451 }
 452
 453 TEST(IdSet, EraseUnion) {
 454   forEachEraseOpPair(
 455     [&] (FooSet& s1, const FooVector& v1,
 456          const FooSet& s2, const FooVector& v2) {
 457       auto const v3 = unionFooVector(v1, v2);
 458       auto const copy = s1;
 459       s1 |= s2;
 460       EXPECT_EQ(toFooVector(s1), v3);
 461       for (auto const& foo : eraseOpFoos()) {
 462         EXPECT_EQ(copy[foo] || s2[foo], s1[foo]);
 463         EXPECT_EQ(s1[foo], inFooVector(v3, foo));
 464       }
 465       EXPECT_EQ(copy.none() && s2.none(), s1.none());
 466       EXPECT_EQ(v3.empty(), s1.none());
 467     }
 468   );
 469 }
 470
 471 }