104 lines · cpp
1//===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.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/DAGDeltaAlgorithm.h"10#include "llvm/ADT/STLExtras.h"11#include "gtest/gtest.h"12#include <cstdarg>13using namespace llvm;14 15namespace {16 17using edge_ty = DAGDeltaAlgorithm::edge_ty;18 19class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {20 changeset_ty FailingSet;21 unsigned NumTests;22 23protected:24 bool ExecuteOneTest(const changeset_ty &Changes) override {25 ++NumTests;26 return llvm::includes(Changes, FailingSet);27 }28 29public:30 FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)31 : FailingSet(_FailingSet),32 NumTests(0) {}33 34 unsigned getNumTests() const { return NumTests; }35};36 37std::set<unsigned> fixed_set(unsigned N, ...) {38 std::set<unsigned> S;39 va_list ap;40 va_start(ap, N);41 for (unsigned i = 0; i != N; ++i)42 S.insert(va_arg(ap, unsigned));43 va_end(ap);44 return S;45}46 47std::set<unsigned> range(unsigned Start, unsigned End) {48 std::set<unsigned> S;49 while (Start != End)50 S.insert(Start++);51 return S;52}53 54std::set<unsigned> range(unsigned N) {55 return range(0, N);56}57 58TEST(DAGDeltaAlgorithmTest, Basic) {59 std::vector<edge_ty> Deps;60 61 // Dependencies:62 // 1 - 363 Deps.clear();64 Deps.push_back(std::make_pair(3, 1));65 66 // P = {3,5,7} \in S,67 // [0, 20),68 // should minimize to {1,3,5,7} in a reasonable number of tests.69 FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));70 EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));71 EXPECT_GE(46U, FDA.getNumTests());72 73 // Dependencies:74 // 0 - 175 // \- 2 - 376 // \- 477 Deps.clear();78 Deps.push_back(std::make_pair(1, 0));79 Deps.push_back(std::make_pair(2, 0));80 Deps.push_back(std::make_pair(4, 0));81 Deps.push_back(std::make_pair(3, 2));82 83 // This is a case where we must hold required changes.84 //85 // P = {1,3} \in S,86 // [0, 5),87 // should minimize to {0,1,2,3} in a small number of tests.88 FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));89 EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));90 EXPECT_GE(9U, FDA2.getNumTests());91 92 // This is a case where we should quickly prune part of the tree.93 //94 // P = {4} \in S,95 // [0, 5),96 // should minimize to {0,4} in a small number of tests.97 FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));98 EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));99 EXPECT_GE(6U, FDA3.getNumTests());100}101 102}103 104