3 files changed, 131 insertions, 5 deletions
diff --git a/unittests/ADT/DAGDeltaAlgorithmTest.cpp b/unittests/ADT/DAGDeltaAlgorithmTest.cpp
new file mode 100644
index 0000000..b90e0c7
--- /dev/null
+++ b/unittests/ADT/DAGDeltaAlgorithmTest.cpp
@@ -0,0 +1,122 @@
+//===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/DAGDeltaAlgorithm.h"
+#include <algorithm>
+#include <cstdarg>
+using namespace llvm;
+
+namespace std {
+
+static std::ostream &operator<<(std::ostream &OS,
+                         const std::set<unsigned> &S) {
+  OS << "{";
+  for (std::set<unsigned>::const_iterator it = S.begin(),
+         ie = S.end(); it != ie; ++it) {
+    if (it != S.begin())
+      OS << ",";
+    OS << *it;
+  }
+  OS << "}";
+  return OS;
+}
+
+}
+
+namespace {
+
+typedef DAGDeltaAlgorithm::edge_ty edge_ty;
+
+class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
+  changeset_ty FailingSet;
+  unsigned NumTests;
+
+protected:
+  virtual bool ExecuteOneTest(const changeset_ty &Changes) {
+    ++NumTests;
+    return std::includes(Changes.begin(), Changes.end(),
+                         FailingSet.begin(), FailingSet.end());
+  }
+
+public:
+  FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
+    : FailingSet(_FailingSet),
+      NumTests(0) {}
+
+  unsigned getNumTests() const { return NumTests; }
+};
+
+std::set<unsigned> fixed_set(unsigned N, ...) {
+  std::set<unsigned> S;
+  va_list ap;
+  va_start(ap, N);
+  for (unsigned i = 0; i != N; ++i)
+    S.insert(va_arg(ap, unsigned));
+  va_end(ap);
+  return S;
+}
+
+std::set<unsigned> range(unsigned Start, unsigned End) {
+  std::set<unsigned> S;
+  while (Start != End)
+    S.insert(Start++);
+  return S;
+}
+
+std::set<unsigned> range(unsigned N) {
+  return range(0, N);
+}
+
+TEST(DAGDeltaAlgorithmTest, Basic) {
+  std::vector<edge_ty> Deps;
+
+  // Dependencies:
+  //  1 - 3
+  Deps.clear();
+  Deps.push_back(std::make_pair(3, 1));
+
+  // P = {3,5,7} \in S,
+  //   [0, 20),
+  // should minimize to {1,3,5,7} in a reasonable number of tests.
+  FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));
+  EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));
+  EXPECT_GE(46U, FDA.getNumTests());
+
+  // Dependencies:
+  // 0 - 1
+  //  \- 2 - 3
+  //  \- 4
+  Deps.clear();
+  Deps.push_back(std::make_pair(1, 0));
+  Deps.push_back(std::make_pair(2, 0));
+  Deps.push_back(std::make_pair(4, 0));
+  Deps.push_back(std::make_pair(3, 2));
+
+  // This is a case where we must hold required changes.
+  //
+  // P = {1,3} \in S,
+  //   [0, 5),
+  // should minimize to {0,1,2,3} in a small number of tests.
+  FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));
+  EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));
+  EXPECT_GE(9U, FDA2.getNumTests());
+
+  // This is a case where we should quickly prune part of the tree.
+  //
+  // P = {4} \in S,
+  //   [0, 5),
+  // should minimize to {0,4} in a small number of tests.
+  FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));
+  EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));
+  EXPECT_GE(6U, FDA3.getNumTests());
+}
+
+}
+
diff --git a/unittests/ADT/ValueMapTest.cpp b/unittests/ADT/ValueMapTest.cpp
index 2fc0938..152e8ea 100644
--- a/unittests/ADT/ValueMapTest.cpp
+++ b/unittests/ADT/ValueMapTest.cpp
@@ -100,10 +100,10 @@ TYPED_TEST(ValueMapTest, OperationsWork) {
 
   // Erase:
   VM.erase(InsertResult2.first);
-  EXPECT_EQ(false, VM.count(this->AddV.get()));
-  EXPECT_EQ(true, VM.count(this->BitcastV.get()));
+  EXPECT_EQ(0U, VM.count(this->AddV.get()));
+  EXPECT_EQ(1U, VM.count(this->BitcastV.get()));
   VM.erase(this->BitcastV.get());
-  EXPECT_EQ(false, VM.count(this->BitcastV.get()));
+  EXPECT_EQ(0U, VM.count(this->BitcastV.get()));
   EXPECT_EQ(0U, VM.size());
 
   // Range insert:
diff --git a/unittests/Makefile.unittest b/unittests/Makefile.unittest
index 8fbcfd2..2a701a0 100644
--- a/unittests/Makefile.unittest
+++ b/unittests/Makefile.unittest
@@ -25,8 +25,12 @@ CPP.Flags += $(NO_MISSING_FIELD_INITIALIZERS) $(NO_VARIADIC_MACROS)
 CPP.Flags += -DGTEST_HAS_RTTI=0
 # libstdc++'s TR1 <tuple> header depends on RTTI and uses C++'0x features not
 # supported by Clang, so force googletest to use its own tuple implementation.
-# When we import googletest >=1.4.0, we can drop this line.
-CPP.Flags += -DGTEST_HAS_TR1_TUPLE=0
+CPP.Flags += -DGTEST_USE_OWN_TR1_TUPLE
+
+# Disable pthreads if LLVM was configured without them.
+ifneq ($(HAVE_PTHREAD), 1)
+  CPP.Flags += -DGTEST_HAS_PTHREAD=0
+endif
 
 TESTLIBS = -lGoogleTest -lUnitTestMain