1 //===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "gtest/gtest.h"
11 #include "llvm/ADT/DAGDeltaAlgorithm.h"
18 static std::ostream &operator<<(std::ostream &OS,
19 const std::set<unsigned> &S) {
21 for (std::set<unsigned>::const_iterator it = S.begin(),
22 ie = S.end(); it != ie; ++it) {
35 typedef DAGDeltaAlgorithm::edge_ty edge_ty;
37 class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
38 changeset_ty FailingSet;
42 virtual bool ExecuteOneTest(const changeset_ty &Changes) {
44 return std::includes(Changes.begin(), Changes.end(),
45 FailingSet.begin(), FailingSet.end());
49 FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
50 : FailingSet(_FailingSet),
53 unsigned getNumTests() const { return NumTests; }
56 std::set<unsigned> fixed_set(unsigned N, ...) {
60 for (unsigned i = 0; i != N; ++i)
61 S.insert(va_arg(ap, unsigned));
66 std::set<unsigned> range(unsigned Start, unsigned End) {
73 std::set<unsigned> range(unsigned N) {
77 TEST(DAGDeltaAlgorithmTest, Basic) {
78 std::vector<edge_ty> Deps;
83 Deps.push_back(std::make_pair(3, 1));
87 // should minimize to {1,3,5,7} in a reasonable number of tests.
88 FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));
89 EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));
90 EXPECT_GE(46U, FDA.getNumTests());
97 Deps.push_back(std::make_pair(1, 0));
98 Deps.push_back(std::make_pair(2, 0));
99 Deps.push_back(std::make_pair(4, 0));
100 Deps.push_back(std::make_pair(3, 2));
102 // This is a case where we must hold required changes.
106 // should minimize to {0,1,2,3} in a small number of tests.
107 FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));
108 EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));
109 EXPECT_GE(9U, FDA2.getNumTests());
111 // This is a case where we should quickly prune part of the tree.
115 // should minimize to {0,4} in a small number of tests.
116 FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));
117 EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));
118 EXPECT_GE(6U, FDA3.getNumTests());