From 1cc7da73055d1e0193f357125198524e7ad19735 Mon Sep 17 00:00:00 2001
From: Daniel Berlin <dberlin@dberlin.org>
Date: Mon, 20 Jul 2015 18:26:23 +0000
Subject: [PATCH] Miscellaneous Fixes for SparseBitVector

Summary:

1. Fix return value in `SparseBitVector::operator&=`.
2. Add checks if SBV is being assigned is invoking SBV.

Reviewers: dberlin

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D11342

Committed on behalf of sl@

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@242693 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/SparseBitVector.h    | 32 +++++++++++-
 unittests/ADT/SparseBitVectorTest.cpp | 94 +++++++++++++++++++++++++++++++++++
 2 files changed, 125 insertions(+), 1 deletion(-)

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 20cbe2cddfc..bf7e1544c81 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -453,6 +453,9 @@ public:
 
   // Assignment
   SparseBitVector& operator=(const SparseBitVector& RHS) {
+    if (this == &RHS)
+      return *this;
+
     Elements.clear();
 
     ElementListConstIter ElementIter = RHS.Elements.begin();
@@ -559,6 +562,9 @@ public:
 
   // Union our bitmap with the RHS and return true if we changed.
   bool operator|=(const SparseBitVector &RHS) {
+    if (this == &RHS)
+      return false;
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -587,6 +593,9 @@ public:
 
   // Intersect our bitmap with the RHS and return true if ours changed.
   bool operator&=(const SparseBitVector &RHS) {
+    if (this == &RHS)
+      return false;
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -619,9 +628,13 @@ public:
         ElementListIter IterTmp = Iter1;
         ++Iter1;
         Elements.erase(IterTmp);
+        changed = true;
       }
     }
-    Elements.erase(Iter1, Elements.end());
+    if (Iter1 != Elements.end()) {
+      Elements.erase(Iter1, Elements.end());
+      changed = true;
+    }
     CurrElementIter = Elements.begin();
     return changed;
   }
@@ -629,6 +642,14 @@ public:
   // Intersect our bitmap with the complement of the RHS and return true
   // if ours changed.
   bool intersectWithComplement(const SparseBitVector &RHS) {
+    if (this == &RHS) {
+      if (!empty()) {
+        clear();
+        return true;
+      }
+      return false;
+    }
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -675,6 +696,15 @@ public:
   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
                                const SparseBitVector<ElementSize> &RHS2)
   {
+    if (this == &RHS1) {
+      intersectWithComplement(RHS2);
+      return;
+    } else if (this == &RHS2) {
+      SparseBitVector RHS2Copy(RHS2);
+      intersectWithComplement(RHS1, RHS2Copy);
+      return;
+    }
+
     Elements.clear();
     CurrElementIter = Elements.begin();
     ElementListConstIter Iter1 = RHS1.Elements.begin();
diff --git a/unittests/ADT/SparseBitVectorTest.cpp b/unittests/ADT/SparseBitVectorTest.cpp
index d8fc5ce25db..9127225860b 100644
--- a/unittests/ADT/SparseBitVectorTest.cpp
+++ b/unittests/ADT/SparseBitVectorTest.cpp
@@ -33,4 +33,98 @@ TEST(SparseBitVectorTest, TrivialOperation) {
   EXPECT_FALSE(Vec.test(17));
 }
 
+TEST(SparseBitVectorTest, IntersectWith) {
+  SparseBitVector<> Vec, Other;
+
+  Vec.set(1);
+  Other.set(1);
+  EXPECT_FALSE(Vec &= Other);
+  EXPECT_TRUE(Vec.test(1));
+
+  Vec.clear();
+  Vec.set(5);
+  Other.clear();
+  Other.set(6);
+  EXPECT_TRUE(Vec &= Other);
+  EXPECT_TRUE(Vec.empty());
+
+  Vec.clear();
+  Vec.set(5);
+  Other.clear();
+  Other.set(225);
+  EXPECT_TRUE(Vec &= Other);
+  EXPECT_TRUE(Vec.empty());
+
+  Vec.clear();
+  Vec.set(225);
+  Other.clear();
+  Other.set(5);
+  EXPECT_TRUE(Vec &= Other);
+  EXPECT_TRUE(Vec.empty());
+}
+
+TEST(SparseBitVectorTest, SelfAssignment) {
+  SparseBitVector<> Vec, Other;
+
+  Vec.set(23);
+  Vec.set(234);
+  Vec = Vec;
+  EXPECT_TRUE(Vec.test(23));
+  EXPECT_TRUE(Vec.test(234));
+
+  Vec.clear();
+  Vec.set(17);
+  Vec.set(256);
+  EXPECT_FALSE(Vec |= Vec);
+  EXPECT_TRUE(Vec.test(17));
+  EXPECT_TRUE(Vec.test(256));
+
+  Vec.clear();
+  Vec.set(56);
+  Vec.set(517);
+  EXPECT_FALSE(Vec &= Vec);
+  EXPECT_TRUE(Vec.test(56));
+  EXPECT_TRUE(Vec.test(517));
+
+  Vec.clear();
+  Vec.set(99);
+  Vec.set(333);
+  EXPECT_TRUE(Vec.intersectWithComplement(Vec));
+  EXPECT_TRUE(Vec.empty());
+  EXPECT_FALSE(Vec.intersectWithComplement(Vec));
+
+  Vec.clear();
+  Vec.set(28);
+  Vec.set(43);
+  Vec.intersectWithComplement(Vec, Vec);
+  EXPECT_TRUE(Vec.empty());
+
+  Vec.clear();
+  Vec.set(42);
+  Vec.set(567);
+  Other.set(55);
+  Other.set(567);
+  Vec.intersectWithComplement(Vec, Other);
+  EXPECT_TRUE(Vec.test(42));
+  EXPECT_FALSE(Vec.test(567));
+
+  Vec.clear();
+  Vec.set(19);
+  Vec.set(21);
+  Other.clear();
+  Other.set(19);
+  Other.set(31);
+  Vec.intersectWithComplement(Other, Vec);
+  EXPECT_FALSE(Vec.test(19));
+  EXPECT_TRUE(Vec.test(31));
+
+  Vec.clear();
+  Vec.set(1);
+  Other.clear();
+  Other.set(59);
+  Other.set(75);
+  Vec.intersectWithComplement(Other, Other);
+  EXPECT_TRUE(Vec.empty());
+}
+
 }
-- 
2.11.0