llvm/unittests/ADT/DeltaAlgorithmTest.cpp

   1 //===- llvm/unittest/ADT/DeltaAlgorithmTest.cpp ---------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/DeltaAlgorithm.h"
  10 #include "gtest/gtest.h"
  11 #include <algorithm>
  12 #include <cstdarg>
  13 using namespace llvm;
  14
  15 namespace std {
  16
  17 std::ostream &operator<<(std::ostream &OS,
  18                          const std::set<unsigned> &S) {
  19   OS << "{";
  20   for (std::set<unsigned>::const_iterator it = S.begin(),
  21          ie = S.end(); it != ie; ++it) {
  22     if (it != S.begin())
  23       OS << ",";
  24     OS << *it;
  25   }
  26   OS << "}";
  27   return OS;
  28 }
  29
  30 }
  31
  32 namespace {
  33
  34 class FixedDeltaAlgorithm final : public DeltaAlgorithm {
  35   changeset_ty FailingSet;
  36   unsigned NumTests;
  37
  38 protected:
  39   bool ExecuteOneTest(const changeset_ty &Changes) override {
  40     ++NumTests;
  41     return std::includes(Changes.begin(), Changes.end(),
  42                          FailingSet.begin(), FailingSet.end());
  43   }
  44
  45 public:
  46   FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
  47     : FailingSet(_FailingSet),
  48       NumTests(0) {}
  49
  50   unsigned getNumTests() const { return NumTests; }
  51 };
  52
  53 std::set<unsigned> fixed_set(unsigned N, ...) {
  54   std::set<unsigned> S;
  55   va_list ap;
  56   va_start(ap, N);
  57   for (unsigned i = 0; i != N; ++i)
  58     S.insert(va_arg(ap, unsigned));
  59   va_end(ap);
  60   return S;
  61 }
  62
  63 std::set<unsigned> range(unsigned Start, unsigned End) {
  64   std::set<unsigned> S;
  65   while (Start != End)
  66     S.insert(Start++);
  67   return S;
  68 }
  69
  70 std::set<unsigned> range(unsigned N) {
  71   return range(0, N);
  72 }
  73
  74 TEST(DeltaAlgorithmTest, Basic) {
  75   // P = {3,5,7} \in S
  76   //   [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
  77   std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
  78   FixedDeltaAlgorithm FDA(Fails);
  79   EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
  80   EXPECT_GE(33U, FDA.getNumTests());
  81
  82   // P = {3,5,7} \in S
  83   //   [10, 20) should minimize to [10,20)
  84   EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
  85
  86   // P = [0,4) \in S
  87   //   [0, 4) should minimize to [0,4) in 11 tests.
  88   //
  89   // 11 = |{ {},
  90   //         {0}, {1}, {2}, {3},
  91   //         {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
  92   //         {0, 1}, {2, 3} }|
  93   FDA = FixedDeltaAlgorithm(range(10));
  94   EXPECT_EQ(range(4), FDA.Run(range(4)));
  95   EXPECT_EQ(11U, FDA.getNumTests());
  96 }
  97
  98 }
  99