99 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/DeltaAlgorithm.h"10#include "llvm/ADT/STLExtras.h"11#include "gtest/gtest.h"12#include <cstdarg>13using namespace llvm;14 15namespace std {16 17std::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 32namespace {33 34class FixedDeltaAlgorithm final : public DeltaAlgorithm {35 changeset_ty FailingSet;36 unsigned NumTests;37 38protected:39 bool ExecuteOneTest(const changeset_ty &Changes) override {40 ++NumTests;41 return llvm::includes(Changes, FailingSet);42 }43 44public:45 FixedDeltaAlgorithm(const changeset_ty &_FailingSet)46 : FailingSet(_FailingSet),47 NumTests(0) {}48 49 unsigned getNumTests() const { return NumTests; }50};51 52std::set<unsigned> fixed_set(unsigned N, ...) {53 std::set<unsigned> S;54 va_list ap;55 va_start(ap, N);56 for (unsigned i = 0; i != N; ++i)57 S.insert(va_arg(ap, unsigned));58 va_end(ap);59 return S;60}61 62std::set<unsigned> range(unsigned Start, unsigned End) {63 std::set<unsigned> S;64 while (Start != End)65 S.insert(Start++);66 return S;67}68 69std::set<unsigned> range(unsigned N) {70 return range(0, N);71}72 73TEST(DeltaAlgorithmTest, Basic) {74 // P = {3,5,7} \in S75 // [0, 20) should minimize to {3,5,7} in a reasonable number of tests.76 std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);77 FixedDeltaAlgorithm FDA(Fails);78 EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));79 EXPECT_GE(33U, FDA.getNumTests());80 81 // P = {3,5,7} \in S82 // [10, 20) should minimize to [10,20)83 EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));84 85 // P = [0,4) \in S86 // [0, 4) should minimize to [0,4) in 11 tests.87 //88 // 11 = |{ {},89 // {0}, {1}, {2}, {3},90 // {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2}, 91 // {0, 1}, {2, 3} }|92 FDA = FixedDeltaAlgorithm(range(10));93 EXPECT_EQ(range(4), FDA.Run(range(4)));94 EXPECT_EQ(11U, FDA.getNumTests()); 95}96 97}98 99