vsavchenko updated this revision to Diff 331008.
vsavchenko added a comment.

Add minor fix in tests


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D86465/new/

https://reviews.llvm.org/D86465

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===================================================================
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -11,120 +11,340 @@
 #include "clang/Basic/SourceManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest-typed-test.h"
 #include "gtest/gtest.h"
 
+using namespace clang;
+using namespace ento;
+
 namespace clang {
 namespace ento {
-namespace {
 
-// TestCase contains to lists of ranges.
-// Original one has to be negated.
-// Expected one has to be compared to negated original range.
-template <typename T> struct TestCase {
-  RangeSet original;
-  RangeSet expected;
-
-  TestCase(BasicValueFactory &BVF, RangeSet::Factory &F,
-           const std::initializer_list<T> &originalList,
-           const std::initializer_list<T> &expectedList)
-      : original(createRangeSetFromList(BVF, F, originalList)),
-        expected(createRangeSetFromList(BVF, F, expectedList)) {}
-
-private:
-  RangeSet createRangeSetFromList(BasicValueFactory &BVF, RangeSet::Factory &F,
-                                  const std::initializer_list<T> rangeList) {
-    llvm::APSInt from(sizeof(T) * 8, std::is_unsigned<T>::value);
-    llvm::APSInt to = from;
-    RangeSet rangeSet = F.getEmptySet();
-    for (auto it = rangeList.begin(); it != rangeList.end(); it += 2) {
-      from = *it;
-      to = *(it + 1);
-      rangeSet = rangeSet.addRange(
-          F, RangeSet(F, BVF.getValue(from), BVF.getValue(to)));
-    }
-    return rangeSet;
-  }
+template <class RangeOrSet> static std::string toString(const RangeOrSet &Obj) {
+  std::string ObjRepresentation;
+  llvm::raw_string_ostream SS(ObjRepresentation);
+  Obj.dump(SS);
+  return SS.str();
+}
+LLVM_ATTRIBUTE_UNUSED static std::string toString(const llvm::APSInt &Point) {
+  return Point.toString(10);
+}
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+                                                      const RangeSet &Set) {
+  return OS << toString(Set);
+}
 
-  void printNegate(const TestCase &TestCase) {
-    TestCase.original.print(llvm::dbgs());
-    llvm::dbgs() << " => ";
-    TestCase.expected.print(llvm::dbgs());
-  }
-};
+} // namespace ento
+} // namespace clang
 
-class RangeSetTest : public testing::Test {
-protected:
+namespace {
+
+template <typename BaseType> class RangeSetTest : public testing::Test {
+public:
   // Init block
   std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;");
-  ASTContext &context = AST->getASTContext();
-  llvm::BumpPtrAllocator alloc;
-  BasicValueFactory BVF{context, alloc};
-  RangeSet::Factory F;
+  ASTContext &Context = AST->getASTContext();
+  llvm::BumpPtrAllocator Arena;
+  BasicValueFactory BVF{Context, Arena};
+  RangeSet::Factory F{BVF};
   // End init block
 
-  template <typename T> void checkNegate() {
-    using type = T;
-
-    // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-    // MID is a value in the middle of the range
-    // which unary minus does not affect on,
-    // e.g. int8/int32(0), uint8(128), uint32(2147483648).
-
-    constexpr type MIN = std::numeric_limits<type>::min();
-    constexpr type MAX = std::numeric_limits<type>::max();
-    constexpr type MID = std::is_signed<type>::value
-                             ? 0
-                             : ~(static_cast<type>(-1) / static_cast<type>(2));
-    constexpr type A = MID - static_cast<type>(42 + 42);
-    constexpr type B = MID - static_cast<type>(42);
-    constexpr type C = -B;
-    constexpr type D = -A;
-
-    static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
-                  "Values shall be in an ascending order");
-
-    // Left {[x, y], [x, y]} is what shall be negated.
-    // Right {[x, y], [x, y]} is what shall be compared to a negation result.
-    TestCase<type> cases[] = {
-        {BVF, F, {MIN, A}, {MIN, MIN, D, MAX}},
-        {BVF, F, {MIN, C}, {MIN, MIN, B, MAX}},
-        {BVF, F, {MIN, MID}, {MIN, MIN, MID, MAX}},
-        {BVF, F, {MIN, MAX}, {MIN, MAX}},
-        {BVF, F, {A, D}, {A, D}},
-        {BVF, F, {A, B}, {C, D}},
-        {BVF, F, {MIN, A, D, MAX}, {MIN, A, D, MAX}},
-        {BVF, F, {MIN, B, MID, D}, {MIN, MIN, A, MID, C, MAX}},
-        {BVF, F, {MIN, MID, C, D}, {MIN, MIN, A, B, MID, MAX}},
-        {BVF, F, {MIN, MID, C, MAX}, {MIN, B, MID, MAX}},
-        {BVF, F, {A, MID, D, MAX}, {MIN + 1, A, MID, D}},
-        {BVF, F, {A, A}, {D, D}},
-        {BVF, F, {MID, MID}, {MID, MID}},
-        {BVF, F, {MAX, MAX}, {MIN + 1, MIN + 1}},
-    };
-
-    for (const auto &c : cases) {
-      // Negate original and check with expected.
-      RangeSet negatedFromOriginal = c.original.Negate(BVF, F);
-      EXPECT_EQ(negatedFromOriginal, c.expected);
-      // Negate negated back and check with original.
-      RangeSet negatedBackward = negatedFromOriginal.Negate(BVF, F);
-      EXPECT_EQ(negatedBackward, c.original);
+  using Self = RangeSetTest<BaseType>;
+  using RawRange = std::pair<BaseType, BaseType>;
+  using RawRangeSet = std::initializer_list<RawRange>;
+
+  static constexpr BaseType getMin() {
+    return std::numeric_limits<BaseType>::min();
+  }
+  static constexpr BaseType getMax() {
+    return std::numeric_limits<BaseType>::max();
+  }
+  static constexpr BaseType getMid() {
+    return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
+  }
+
+  static constexpr bool isSigned() { return std::is_signed<BaseType>::value; }
+  static constexpr BaseType fromInt(int X) { return static_cast<BaseType>(X); }
+
+  static llvm::APSInt Base;
+  const llvm::APSInt &from(BaseType X) {
+    llvm::APSInt Dummy = Base;
+    Dummy = X;
+    return BVF.getValue(Dummy);
+  }
+
+  Range from(const RawRange &Init) {
+    return Range(from(Init.first), from(Init.second));
+  }
+
+  RangeSet from(const RawRangeSet &Init) {
+    RangeSet RangeSet = F.getEmptySet();
+    for (const auto &Raw : Init) {
+      RangeSet = F.add(RangeSet, from(Raw));
     }
+    return RangeSet;
+  }
+
+  template <class F, class... RawArgTypes>
+  void wrap(F ActualFunction, RawArgTypes &&... Args) {
+    (this->*ActualFunction)(from(std::forward<RawArgTypes>(Args))...);
+  }
+
+  void checkNegateImpl(RangeSet Original, RangeSet Expected) {
+    RangeSet NegatedFromOriginal = F.negate(Original);
+    EXPECT_EQ(NegatedFromOriginal, Expected);
+    // Negate negated back and check with original.
+    RangeSet NegatedBackward = F.negate(NegatedFromOriginal);
+    EXPECT_EQ(NegatedBackward, Original);
+  }
+
+  void checkNegate(RawRangeSet RawOriginal, RawRangeSet RawExpected) {
+    wrap(&Self::checkNegateImpl, RawOriginal, RawExpected);
+  }
+
+  template <class PointOrSet>
+  void checkIntersectImpl(RangeSet LHS, PointOrSet RHS, RangeSet Expected) {
+    RangeSet Result = F.intersect(LHS, RHS);
+    EXPECT_EQ(Result, Expected)
+        << "while intersecting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkIntersectRangeImpl(RangeSet LHS, const llvm::APSInt &Lower,
+                               const llvm::APSInt &Upper, RangeSet Expected) {
+    RangeSet Result = F.intersect(LHS, Lower, Upper);
+    EXPECT_EQ(Result, Expected)
+        << "while intersecting " << toString(LHS) << " and [" << toString(Lower)
+        << ", " << toString(Upper) << "]";
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, RawRangeSet RawRHS,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, BaseType RawRHS,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+         RawExpected);
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, BaseType RawLower, BaseType RawUpper,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectRangeImpl, RawLHS, RawLower, RawUpper,
+         RawExpected);
+  }
+
+  void checkContainsImpl(RangeSet LHS, const llvm::APSInt &RHS, bool Expected) {
+    bool Result = LHS.contains(RHS);
+    EXPECT_EQ(Result, Expected)
+        << toString(LHS) << (Result ? " contains " : " doesn't contain ")
+        << toString(RHS);
+  }
+
+  void checkContains(RawRangeSet RawLHS, BaseType RawRHS, bool Expected) {
+    checkContainsImpl(from(RawLHS), from(RawRHS), Expected);
+  }
+
+  template <class RHSType>
+  void checkAddImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+    RangeSet Result = F.add(LHS, RHS);
+    EXPECT_EQ(Result, Expected)
+        << "while adding " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkAdd(RawRangeSet RawLHS, RawRange RawRHS, RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<Range>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
+                RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<RangeSet>, RawRHS, RawLHS, RawExpected);
+  }
+
+  void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+         RawExpected);
+  }
+
+  void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
+                       RangeSet Expected) {
+    RangeSet Result = F.deletePoint(From, Point);
+    EXPECT_EQ(Result, Expected)
+        << "while deleting " << toString(Point) << " from " << toString(From);
+  }
+
+  void checkDelete(BaseType Point, RawRangeSet RawFrom,
+                   RawRangeSet RawExpected) {
+    wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected);
   }
 };
 
-TEST_F(RangeSetTest, RangeSetNegateTest) {
-  checkNegate<int8_t>();
-  checkNegate<uint8_t>();
-  checkNegate<int16_t>();
-  checkNegate<uint16_t>();
-  checkNegate<int32_t>();
-  checkNegate<uint32_t>();
-  checkNegate<int64_t>();
-  checkNegate<uint64_t>();
+} // namespace
+
+template <typename BaseType>
+llvm::APSInt RangeSetTest<BaseType>::Base{sizeof(BaseType) * 8, !isSigned()};
+
+using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
+                                  uint32_t, int64_t, uint64_t>;
+TYPED_TEST_CASE(RangeSetTest, IntTypes);
+
+TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  // MID is a value in the middle of the range
+  // which unary minus does not affect on,
+  // e.g. int8/int32(0), uint8(128), uint32(2147483648).
+  constexpr TypeParam MID = TestFixture::getMid();
+  constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
+  constexpr TypeParam B = MID - TestFixture::fromInt(42);
+  constexpr TypeParam C = -B;
+  constexpr TypeParam D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+                "Values shall be in an ascending order");
+
+  this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
+  this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}});
+  this->checkNegate({{MIN, MID}}, {{MIN, MIN}, {MID, MAX}});
+  this->checkNegate({{MIN, MAX}}, {{MIN, MAX}});
+  this->checkNegate({{A, D}}, {{A, D}});
+  this->checkNegate({{A, B}}, {{C, D}});
+  this->checkNegate({{MIN, A}, {D, MAX}}, {{MIN, A}, {D, MAX}});
+  this->checkNegate({{MIN, B}, {MID, D}}, {{MIN, MIN}, {A, MID}, {C, MAX}});
+  this->checkNegate({{MIN, MID}, {C, D}}, {{MIN, MIN}, {A, B}, {MID, MAX}});
+  this->checkNegate({{MIN, MID}, {C, MAX}}, {{MIN, B}, {MID, MAX}});
+  this->checkNegate({{A, MID}, {D, MAX}}, {{MIN + 1, A}, {MID, D}});
+  this->checkNegate({{A, A}}, {{D, D}});
+  this->checkNegate({{MID, MID}}, {{MID, MID}});
+  this->checkNegate({{MAX, MAX}}, {{MIN + 1, MIN + 1}});
 }
 
-} // namespace
-} // namespace ento
-} // namespace clang
+TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) {
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, 42, {});
+  // Check that intersection with itself produces the same set.
+  this->checkIntersect({{42, 42}}, 42, {{42, 42}});
+  // Check more general cases.
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 42, {});
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 60}}, 42, {{42, 42}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) {
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, 10, 20, {});
+  this->checkIntersect({}, 20, 10, {});
+  // Check that intersection with itself produces the same set.
+  this->checkIntersect({{10, 20}}, 10, 20, {{10, 20}});
+  this->checkIntersect({{MIN, 10}, {20, MAX}}, 20, 10, {{MIN, 10}, {20, MAX}});
+  // Check non-overlapping range intersections.
+  this->checkIntersect({{10, 20}}, 21, 9, {});
+  this->checkIntersect({{MIN, 9}, {21, MAX}}, 10, 20, {});
+  // Check more general cases.
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 10, 35,
+                       {{10, 10}, {20, 30}, {30, 35}});
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 35, 10,
+                       {{0, 10}, {35, 40}, {50, 60}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetGenericIntersectTest) {
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, {}, {});
+  this->checkIntersect({}, {{0, 10}}, {});
+  this->checkIntersect({{0, 10}}, {}, {});
+
+  this->checkIntersect({{0, 10}}, {{4, 6}}, {{4, 6}});
+  this->checkIntersect({{0, 10}}, {{4, 20}}, {{4, 10}});
+  // Check that intersection with points works as expected.
+  this->checkIntersect({{0, 10}}, {{4, 4}}, {{4, 4}});
+  // All ranges are closed, check that intersection with edge points works as
+  // expected.
+  this->checkIntersect({{0, 10}}, {{10, 10}}, {{10, 10}});
+
+  // Let's check that we can skip some intervals and partially intersect
+  // other intervals.
+  this->checkIntersect({{0, 2}, {4, 5}, {6, 9}, {10, 11}, {12, 12}, {13, 15}},
+                       {{8, 14}, {20, 30}},
+                       {{8, 9}, {10, 11}, {12, 12}, {13, 14}});
+  // Check more generic case.
+  this->checkIntersect(
+      {{0, 1}, {2, 3}, {5, 6}, {7, 15}, {25, 30}},
+      {{4, 10}, {11, 11}, {12, 16}, {17, 17}, {19, 20}, {21, 23}, {24, 27}},
+      {{5, 6}, {7, 10}, {11, 11}, {12, 15}, {25, 27}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetContainsTest) {
+  // Check with an empty set.
+  this->checkContains({}, 10, false);
+  // Check contains with sets of size one:
+  //   * when the whole range is less
+  this->checkContains({{0, 5}}, 10, false);
+  //   * when the whole range is greater
+  this->checkContains({{20, 25}}, 10, false);
+  //   * when the range is just the point we are looking for
+  this->checkContains({{10, 10}}, 10, true);
+  //   * when the range starts with the point
+  this->checkContains({{10, 15}}, 10, true);
+  //   * when the range ends with the point
+  this->checkContains({{5, 10}}, 10, true);
+  //   * when the range has the point somewhere in the middle
+  this->checkContains({{0, 25}}, 10, true);
+  // Check similar cases, but with larger sets.
+  this->checkContains({{0, 5}, {10, 10}, {15, 20}}, 10, true);
+  this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true);
+  this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true);
+
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  constexpr TypeParam MID = TestFixture::getMid();
+  this->checkContains({{MIN, MAX}}, 0, true);
+  this->checkContains({{MIN, MAX}}, MID, true);
+  this->checkContains({{MIN, MAX}}, -10, true);
+  this->checkContains({{MIN, MAX}}, 10, true);
+}
+
+TYPED_TEST(RangeSetTest, RangeSetAddTest) {
+  // Check adding single points
+  this->checkAdd({}, 10, {{10, 10}});
+  this->checkAdd({{0, 5}}, 10, {{0, 5}, {10, 10}});
+  this->checkAdd({{0, 5}, {30, 40}}, 10, {{0, 5}, {10, 10}, {30, 40}});
+
+  // Check adding single ranges.
+  this->checkAdd({}, {10, 20}, {{10, 20}});
+  this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}});
+  this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}});
+
+  // Check adding whole sets of ranges.
+  this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}});
+  // Check that ordering of ranges is as expected.
+  this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}});
+  this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}},
+                 {{0, 5}, {10, 20}, {30, 40}, {50, 60}});
+  this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}},
+                 {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) {
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  constexpr TypeParam MID = TestFixture::getMid();
+
+  this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}});
+  // Check that delete works with an empty set.
+  this->checkDelete(10, {}, {});
+  // Check that delete can remove entire ranges.
+  this->checkDelete(10, {{10, 10}}, {});
+  this->checkDelete(10, {{0, 5}, {10, 10}, {20, 30}}, {{0, 5}, {20, 30}});
+  // Check that delete can split existing ranges into two.
+  this->checkDelete(10, {{0, 5}, {7, 15}, {20, 30}},
+                    {{0, 5}, {7, 9}, {11, 15}, {20, 30}});
+  // Check that delete of the point not from the range set works as expected.
+  this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}});
+}
Index: clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
@@ -220,5 +220,4 @@
 }
 
 } // end of namespace ento
-
 } // end of namespace clang
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -22,6 +22,8 @@
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iterator>
 
 using namespace clang;
 using namespace ento;
@@ -99,47 +101,63 @@
     return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
   }
 };
+
 //===----------------------------------------------------------------------===//
 //                           RangeSet implementation
 //===----------------------------------------------------------------------===//
 
-void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
-                                const llvm::APSInt &Lower,
-                                const llvm::APSInt &Upper,
-                                PrimRangeSet &newRanges,
-                                PrimRangeSet::iterator &i,
-                                PrimRangeSet::iterator &e) const {
-  // There are six cases for each range R in the set:
-  //   1. R is entirely before the intersection range.
-  //   2. R is entirely after the intersection range.
-  //   3. R contains the entire intersection range.
-  //   4. R starts before the intersection range and ends in the middle.
-  //   5. R starts in the middle of the intersection range and ends after it.
-  //   6. R is entirely contained in the intersection range.
-  // These correspond to each of the conditions below.
-  for (/* i = begin(), e = end() */; i != e; ++i) {
-    if (i->To() < Lower) {
-      continue;
-    }
-    if (i->From() > Upper) {
-      break;
-    }
+RangeSet::ContainerType RangeSet::Factory::EmptySet{};
 
-    if (i->Includes(Lower)) {
-      if (i->Includes(Upper)) {
-        newRanges =
-            F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
-        break;
-      } else
-        newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
-    } else {
-      if (i->Includes(Upper)) {
-        newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
-        break;
-      } else
-        newRanges = F.add(newRanges, *i);
-    }
+RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
+  ContainerType Result;
+  Result.reserve(Original.size() + 1);
+
+  const_iterator Lower = llvm::lower_bound(Original, Element);
+  Result.insert(Result.end(), Original.begin(), Lower);
+  Result.push_back(Element);
+  Result.insert(Result.end(), Lower, Original.end());
+
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) {
+  return add(Original, Range(Point));
+}
+
+RangeSet RangeSet::Factory::getRangeSet(Range From) {
+  ContainerType Result;
+  Result.push_back(From);
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
+  llvm::FoldingSetNodeID ID;
+  void *InsertPos;
+
+  From.Profile(ID);
+  ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);
+
+  if (!Result) {
+    // It is cheaper to fully construct the resulting range on stack
+    // and move it to the freshly allocated buffer if we don't have
+    // a set like this already.
+    Result = construct(std::move(From));
+    Cache.InsertNode(Result, InsertPos);
   }
+
+  return Result;
+}
+
+RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
+  void *Buffer = Arena.Allocate();
+  return new (Buffer) ContainerType(std::move(From));
+}
+
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+  ContainerType Result;
+  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
+             std::back_inserter(Result));
+  return makePersistent(std::move(Result));
 }
 
 const llvm::APSInt &RangeSet::getMinValue() const {
@@ -149,22 +167,31 @@
 
 const llvm::APSInt &RangeSet::getMaxValue() const {
   assert(!isEmpty());
-  // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
-  //       the whole tree to get to the last element.
-  //       llvm::ImmutableSet should support decrement for 'end' iterators
-  //       or reverse order iteration.
-  auto It = begin();
-  for (auto End = end(); std::next(It) != End; ++It) {
-  }
-  return It->To();
+  return std::prev(end())->To();
 }
 
-bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
-  if (isEmpty()) {
-    // This range is already infeasible.
+bool RangeSet::containsImpl(llvm::APSInt &Point) const {
+  if (isEmpty() || !pin(Point))
     return false;
-  }
 
+  Range Dummy(Point);
+  const_iterator It = llvm::upper_bound(*this, Dummy);
+  if (It == begin())
+    return false;
+
+  return std::prev(It)->Includes(Point);
+}
+
+bool RangeSet::pin(llvm::APSInt &Point) const {
+  APSIntType Type(getMinValue());
+  if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
+    return false;
+
+  Type.apply(Point);
+  return true;
+}
+
+bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
   // This function has nine cases, the cartesian product of range-testing
   // both the upper and lower bounds against the symbol's type.
   // Each case requires a different pinning operation.
@@ -245,129 +272,216 @@
   return true;
 }
 
-// Returns a set containing the values in the receiving set, intersected with
-// the closed range [Lower, Upper]. Unlike the Range type, this range uses
-// modular arithmetic, corresponding to the common treatment of C integer
-// overflow. Thus, if the Lower bound is greater than the Upper bound, the
-// range is taken to wrap around. This is equivalent to taking the
-// intersection with the two ranges [Min, Upper] and [Lower, Max],
-// or, alternatively, /removing/ all integers between Upper and Lower.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
-                             llvm::APSInt Lower, llvm::APSInt Upper) const {
-  PrimRangeSet newRanges = F.getEmptySet();
-
-  if (isEmpty() || !pin(Lower, Upper))
-    return newRanges;
-
-  PrimRangeSet::iterator i = begin(), e = end();
-  if (Lower <= Upper)
-    IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
-  else {
-    // The order of the next two statements is important!
-    // IntersectInRange() does not reset the iteration state for i and e.
-    // Therefore, the lower range most be handled first.
-    IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
-    IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
-  }
-
-  return newRanges;
-}
-
-// Returns a set containing the values in the receiving set, intersected with
-// the range set passed as parameter.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
-                             const RangeSet &Other) const {
-  PrimRangeSet newRanges = F.getEmptySet();
-
-  for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
-    RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
-    for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
-      newRanges = F.add(newRanges, *j);
-    }
+RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower,
+                                      llvm::APSInt Upper) {
+  if (What.isEmpty() || !What.pin(Lower, Upper))
+    return getEmptySet();
+
+  ContainerType DummyContainer;
+
+  if (Lower <= Upper) {
+    // [Lower, Upper] is a regular range.
+    //
+    // Shortcut: check that there is even a possibility of the intersection
+    //           by checking the two following situations:
+    //
+    //               <---[  What  ]---[------]------>
+    //                              Lower  Upper
+    //                            -or-
+    //               <----[------]----[  What  ]---->
+    //                  Lower  Upper
+    if (What.getMaxValue() < Lower || Upper < What.getMinValue())
+      return getEmptySet();
+
+    DummyContainer.push_back(
+        Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
+  } else {
+    // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX]
+    //
+    // Shortcut: check that there is even a possibility of the intersection
+    //           by checking the following situation:
+    //
+    //               <------]---[  What  ]---[------>
+    //                    Upper             Lower
+    if (What.getMaxValue() < Lower && Upper < What.getMinValue())
+      return getEmptySet();
+
+    DummyContainer.push_back(
+        Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
+    DummyContainer.push_back(
+        Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
   }
 
-  return newRanges;
+  return intersect(*What.Impl, DummyContainer);
 }
 
-// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
-// operation under the values of the type.
-//
-// We also handle MIN because applying unary minus to MIN does not change it.
-// Example 1:
-// char x = -128;        // -128 is a MIN value in a range of 'char'
-// char y = -x;          // y: -128
-// Example 2:
-// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
-// unsigned char y = -x; // y: 0
-//
-// And it makes us to separate the range
-// like [MIN, N] to [MIN, MIN] U [-N,MAX].
-// For instance, whole range is {-128..127} and subrange is [-128,-126],
-// thus [-128,-127,-126,.....] negates to [-128,.....,126,127].
-//
-// Negate restores disrupted ranges on bounds,
-// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
-RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
-  PrimRangeSet newRanges = F.getEmptySet();
+RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,
+                                      const RangeSet::ContainerType &RHS) {
+  ContainerType Result;
+  Result.reserve(std::max(LHS.size(), RHS.size()));
+
+  const_iterator First = LHS.begin(), Second = RHS.begin(),
+                 FirstEnd = LHS.end(), SecondEnd = RHS.end();
+
+  const auto SwapIterators = [&First, &FirstEnd, &Second, &SecondEnd]() {
+    std::swap(First, Second);
+    std::swap(FirstEnd, SecondEnd);
+  };
+
+  // If we ran out of ranges in one set, but not in the other,
+  // it means that those elements are definitely not in the
+  // intersection.
+  while (First != FirstEnd && Second != SecondEnd) {
+    // We want to keep the following invariant at all times:
+    //
+    //    ----[ First ---------------------->
+    //    --------[ Second ----------------->
+    if (Second->From() < First->From())
+      SwapIterators();
+
+    // Loop where the invariant holds:
+    do {
+      // Check for the following situation:
+      //
+      //    ----[ First ]--------------------->
+      //    ---------------[ Second ]--------->
+      //
+      // which means that...
+      if (Second->From() > First->To()) {
+        // ...First is not in the intersection.
+        //
+        // We should move on to the next range after First and break out of the
+        // loop because the invariant might not be true.
+        ++First;
+        break;
+      }
+
+      // We have a guaranteed intersection at this point!
+      // And this is the current situation:
+      //
+      //    ----[   First   ]----------------->
+      //    -------[ Second ------------------>
+      //
+      // Additionally, it definitely starts with Second->From().
+      const llvm::APSInt &IntersectionStart = Second->From();
+
+      // It is important to know which of the two ranges' ends
+      // is greater.  That "longer" range might have some other
+      // intersections, while the "shorter" range might not.
+      if (Second->To() > First->To()) {
+        // Here we make a decision to keep First as the "longer"
+        // range.
+        SwapIterators();
+      }
+
+      // At this point, we have the following situation:
+      //
+      //    ---- First      ]-------------------->
+      //    ---- Second ]--[  Second+1 ---------->
+      //
+      // We don't know the relationship between First->From and
+      // Second->From and we don't know whether Second+1 intersects
+      // with First.
+      //
+      // However, we know that [IntersectionStart, Second->To] is
+      // a part of the intersection...
+      Result.push_back(Range(IntersectionStart, Second->To()));
+      ++Second;
+      // ...and that the invariant will hold for a valid Second+1
+      // because First->From <= Second->To < (Second+1)->From.
+    } while (Second != SecondEnd);
+  }
+
+  if (Result.empty())
+    return getEmptySet();
+
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) {
+  // Shortcut: let's see if the intersection is even possible.
+  if (LHS.isEmpty() || RHS.isEmpty() || LHS.getMaxValue() < RHS.getMinValue() ||
+      RHS.getMaxValue() < LHS.getMinValue())
+    return getEmptySet();
+
+  return intersect(*LHS.Impl, *RHS.Impl);
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
+  if (LHS.containsImpl(Point))
+    return getRangeSet(ValueFactory.getValue(Point));
+
+  return getEmptySet();
+}
+
+RangeSet RangeSet::Factory::negate(RangeSet What) {
+  if (What.isEmpty())
+    return getEmptySet();
 
-  if (isEmpty())
-    return newRanges;
+  const llvm::APSInt SampleValue = What.getMinValue();
+  const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
+  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
 
-  const llvm::APSInt sampleValue = getMinValue();
-  const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
-  const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+  ContainerType Result;
+  Result.reserve(What.size() + (SampleValue == MIN));
 
   // Handle a special case for MIN value.
-  iterator i = begin();
-  const llvm::APSInt &from = i->From();
-  const llvm::APSInt &to = i->To();
-  if (from == MIN) {
-    // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX].
-    if (to == MAX) {
-      newRanges = ranges;
+  const_iterator It = What.begin();
+  const_iterator End = What.end();
+
+  const llvm::APSInt &From = It->From();
+  const llvm::APSInt &To = It->To();
+
+  if (From == MIN) {
+    // If the range [From, To] is [MIN, MAX], then result is also [MIN, MAX].
+    if (To == MAX) {
+      return What;
+    }
+
+    const_iterator Last = std::prev(End);
+
+    // Try to find and unite the following ranges:
+    // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
+    if (Last->To() == MAX) {
+      // It means that in the original range we have ranges
+      //   [MIN, A], ... , [B, MAX]
+      // And the result should be [MIN, -B], ..., [-A, MAX]
+      Result.emplace_back(MIN, ValueFactory.getValue(-Last->From()));
+      // We already negated Last, so we can skip it.
+      End = Last;
     } else {
-      // Add separate range for the lowest value.
-      newRanges = F.add(newRanges, Range(MIN, MIN));
-      // Skip adding the second range in case when [from, to] are [MIN, MIN].
-      if (to != MIN) {
-        newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
-      }
+      // Add a separate range for the lowest value.
+      Result.emplace_back(MIN, MIN);
     }
+
+    // Skip adding the second range in case when [From, To] are [MIN, MIN].
+    if (To != MIN) {
+      Result.emplace_back(ValueFactory.getValue(-To), MAX);
+    }
+
     // Skip the first range in the loop.
-    ++i;
+    ++It;
   }
 
   // Negate all other ranges.
-  for (iterator e = end(); i != e; ++i) {
+  for (; It != End; ++It) {
     // Negate int values.
-    const llvm::APSInt &newFrom = BV.getValue(-i->To());
-    const llvm::APSInt &newTo = BV.getValue(-i->From());
-    // Add a negated range.
-    newRanges = F.add(newRanges, Range(newFrom, newTo));
-  }
-
-  if (newRanges.isSingleton())
-    return newRanges;
+    const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
+    const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
 
-  // Try to find and unite next ranges:
-  // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
-  iterator iter1 = newRanges.begin();
-  iterator iter2 = std::next(iter1);
-
-  if (iter1->To() == MIN && (iter2->From() - 1) == MIN) {
-    const llvm::APSInt &to = iter2->To();
-    // remove adjacent ranges
-    newRanges = F.remove(newRanges, *iter1);
-    newRanges = F.remove(newRanges, *newRanges.begin());
-    // add united range
-    newRanges = F.add(newRanges, Range(MIN, to));
+    // Add a negated range.
+    Result.emplace_back(NewFrom, NewTo);
   }
 
-  return newRanges;
+  llvm::sort(Result);
+  return makePersistent(std::move(Result));
 }
 
-RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F,
-                          const llvm::APSInt &Point) const {
+RangeSet RangeSet::Factory::deletePoint(RangeSet From,
+                                        const llvm::APSInt &Point) {
+  if (!From.contains(Point))
+    return From;
+
   llvm::APSInt Upper = Point;
   llvm::APSInt Lower = Point;
 
@@ -375,22 +489,17 @@
   --Lower;
 
   // Notice that the lower bound is greater than the upper bound.
-  return Intersect(BV, F, Upper, Lower);
+  return intersect(From, Upper, Lower);
 }
 
-void RangeSet::print(raw_ostream &os) const {
-  bool isFirst = true;
-  os << "{ ";
-  for (iterator i = begin(), e = end(); i != e; ++i) {
-    if (isFirst)
-      isFirst = false;
-    else
-      os << ", ";
+void Range::dump(raw_ostream &OS) const {
+  OS << '[' << From().toString(10) << ", " << To().toString(10) << ']';
+}
 
-    os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
-       << ']';
-  }
-  os << " }";
+void RangeSet::dump(raw_ostream &OS) const {
+  OS << "{ ";
+  llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });
+  OS << " }";
 }
 
 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
@@ -653,7 +762,7 @@
                                          RangeSet Second, RestTy... Tail) {
   // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
   // of the function and can be sure that the result is RangeSet.
-  return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+  return intersect(BV, F, F.intersect(Head, Second), Tail...);
 }
 
 template <class SecondTy, class... RestTy>
@@ -942,7 +1051,7 @@
   /// Return a range set subtracting zero from \p Domain.
   RangeSet assumeNonZero(RangeSet Domain, QualType T) {
     APSIntType IntType = ValueFactory.getAPSIntType(T);
-    return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue());
+    return RangeFactory.deletePoint(Domain, IntType.getZeroValue());
   }
 
   // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
@@ -965,7 +1074,7 @@
             SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
 
         if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
-          return NegatedRange->Negate(ValueFactory, RangeFactory);
+          return RangeFactory.negate(*NegatedRange);
         }
       }
     }
@@ -1259,7 +1368,7 @@
 class RangeConstraintManager : public RangedConstraintManager {
 public:
   RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
-      : RangedConstraintManager(EE, SVB) {}
+      : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.
@@ -1424,8 +1533,8 @@
     // be simply a constant because we can't reason about range disequalities.
     if (const llvm::APSInt *Point = Constraint.getConcreteValue())
       for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
-        RangeSet UpdatedConstraint =
-            getRange(State, DisequalClass).Delete(getBasicVals(), F, *Point);
+        RangeSet UpdatedConstraint = getRange(State, DisequalClass);
+        UpdatedConstraint = F.deletePoint(UpdatedConstraint, *Point);
 
         // If we end up with at least one of the disequal classes to be
         // constrainted with an empty range-set, the state is infeasible.
@@ -1733,7 +1842,7 @@
       RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
           VF, RF, State, First.getRepresentativeSymbol());
 
-      FirstConstraint = FirstConstraint.Delete(VF, RF, *Point);
+      FirstConstraint = RF.deletePoint(FirstConstraint, *Point);
       Constraints = CRF.add(Constraints, First, FirstConstraint);
     }
 }
@@ -1884,7 +1993,7 @@
   llvm::APSInt Zero = IntType.getZeroValue();
 
   // Check if zero is in the set of possible values.
-  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
+  if (!Ranges->contains(Zero))
     return false;
 
   // Zero is a possible value, but it is not the /only/ possible value.
@@ -2070,7 +2179,8 @@
 
   llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
 
-  RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point);
+  RangeSet New = getRange(St, Sym);
+  New = F.deletePoint(New, Point);
 
   return trackNE(New, St, Sym, Int, Adjustment);
 }
@@ -2086,7 +2196,8 @@
 
   // [Int-Adjustment, Int-Adjustment]
   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
-  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
+  RangeSet New = getRange(St, Sym);
+  New = F.intersect(New, AdjInt);
 
   return trackEQ(New, St, Sym, Int, Adjustment);
 }
@@ -2116,7 +2227,8 @@
   llvm::APSInt Upper = ComparisonVal - Adjustment;
   --Upper;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet Result = getRange(St, Sym);
+  return F.intersect(Result, Lower, Upper);
 }
 
 ProgramStateRef
@@ -2152,7 +2264,8 @@
   llvm::APSInt Upper = Max - Adjustment;
   ++Lower;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet SymRange = getRange(St, Sym);
+  return F.intersect(SymRange, Lower, Upper);
 }
 
 ProgramStateRef
@@ -2188,7 +2301,8 @@
   llvm::APSInt Lower = ComparisonVal - Adjustment;
   llvm::APSInt Upper = Max - Adjustment;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet SymRange = getRange(St, Sym);
+  return F.intersect(SymRange, Lower, Upper);
 }
 
 ProgramStateRef
@@ -2224,7 +2338,8 @@
   llvm::APSInt Lower = Min - Adjustment;
   llvm::APSInt Upper = ComparisonVal - Adjustment;
 
-  return RS().Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet Default = RS();
+  return F.intersect(Default, Lower, Upper);
 }
 
 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
@@ -2257,7 +2372,7 @@
     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
   RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
   RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
-  RangeSet New(RangeLT.addRange(F, RangeGT));
+  RangeSet New(F.add(RangeLT, RangeGT));
   return New.isEmpty() ? nullptr : setConstraint(State, Sym, New);
 }
 
@@ -2292,7 +2407,7 @@
       }
       Indent(Out, Space, IsDot)
           << "{ \"symbol\": \"" << ClassMember << "\", \"range\": \"";
-      P.second.print(Out);
+      P.second.dump(Out);
       Out << "\" }";
     }
   }
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -16,6 +16,8 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/Allocator.h"
 
 namespace clang {
 
@@ -24,21 +26,19 @@
 /// A Range represents the closed range [from, to].  The caller must
 /// guarantee that from <= to.  Note that Range is immutable, so as not
 /// to subvert RangeSet's immutability.
-class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
+class Range {
 public:
-  Range(const llvm::APSInt &from, const llvm::APSInt &to)
-      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
-    assert(from <= to);
+  Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) {
+    assert(From <= To);
   }
 
-  Range(const llvm::APSInt &point)
-      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {}
+  Range(const llvm::APSInt &Point) : Range(Point, Point) {}
 
-  bool Includes(const llvm::APSInt &v) const {
-    return *first <= v && v <= *second;
+  bool Includes(const llvm::APSInt &Point) const {
+    return From() <= Point && Point <= To();
   }
-  const llvm::APSInt &From() const { return *first; }
-  const llvm::APSInt &To() const { return *second; }
+  const llvm::APSInt &From() const { return *Impl.first; }
+  const llvm::APSInt &To() const { return *Impl.second; }
   const llvm::APSInt *getConcreteValue() const {
     return &From() == &To() ? &From() : nullptr;
   }
@@ -47,93 +47,264 @@
     ID.AddPointer(&From());
     ID.AddPointer(&To());
   }
-};
+  void dump(raw_ostream &OS) const;
 
-class RangeTrait : public llvm::ImutContainerInfo<Range> {
-public:
-  // When comparing if one Range is less than another, we should compare
-  // the actual APSInt values instead of their pointers.  This keeps the order
-  // consistent (instead of comparing by pointer values) and can potentially
-  // be used to speed up some of the operations in RangeSet.
-  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
-    return *lhs.first < *rhs.first ||
-           (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
-  }
+  // In order to keep non-overlapping ranges sorted, we can compare only From
+  // points.
+  bool operator<(const Range &RHS) const { return From() < RHS.From(); }
+
+  bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }
+  bool operator!=(const Range &RHS) const { return !operator==(RHS); }
+
+private:
+  std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;
 };
 
-/// RangeSet contains a set of ranges. If the set is empty, then
-///  there the value of a symbol is overly constrained and there are no
-///  possible values for that symbol.
+/// @class RangeSet is a persistent set of non-overlapping ranges.
+///
+/// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which
+/// also supports the most common operations performed on range sets.
+///
+/// Empty set corresponds to an overly constrained symbol meaning that there
+/// are no possible values for that symbol.
 class RangeSet {
-  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
-  PrimRangeSet ranges; // no need to make const, since it is an
-                       // ImmutableSet - this allows default operator=
-                       // to work.
 public:
-  typedef PrimRangeSet::Factory Factory;
-  typedef PrimRangeSet::iterator iterator;
-
-  RangeSet(PrimRangeSet RS) : ranges(RS) {}
-
-  /// Create a new set with all ranges of this set and RS.
-  /// Possible intersections are not checked here.
-  RangeSet addRange(Factory &F, const RangeSet &RS) {
-    PrimRangeSet Ranges(RS.ranges);
-    for (const auto &range : ranges)
-      Ranges = F.add(Ranges, range);
-    return RangeSet(Ranges);
-  }
-
-  iterator begin() const { return ranges.begin(); }
-  iterator end() const { return ranges.end(); }
+  class Factory;
 
-  bool isEmpty() const { return ranges.isEmpty(); }
+private:
+  // We use llvm::SmallVector as the underlying container for the following
+  // reasons:
+  //
+  //   * Range sets are usually very simple, 1 or 2 ranges.
+  //     That's why llvm::ImmutableSet is not perfect.
+  //
+  //   * Ranges in sets are NOT overlapping, so it is natural to keep them
+  //     sorted for efficient operations and queries.  For this reason,
+  //     llvm::SmallSet doesn't fit the requirements, it is not sorted when it
+  //     is a vector.
+  //
+  //   * Range set operations usually a bit harder than add/remove a range.
+  //     Complex operations might do many of those for just one range set.
+  //     Formerly it used to be llvm::ImmutableSet, which is inefficient for our
+  //     purposes as we want to make these operations BOTH immutable AND
+  //     efficient.
+  //
+  //   * Iteration over ranges is widespread and a more cache-friendly
+  //     structure is preferred.
+  using ImplType = llvm::SmallVector<Range, 4>;
+
+  struct ContainerType : public ImplType, public llvm::FoldingSetNode {
+    void Profile(llvm::FoldingSetNodeID &ID) const {
+      for (const Range &It : *this) {
+        It.Profile(ID);
+      }
+    }
+  };
+  // This is a non-owning pointer to an actual container.
+  // The memory is fully managed by the factory and is alive as long as the
+  // factory itself is alive.
+  // It is a pointer as opposed to a reference, so we can easily reassign
+  // RangeSet objects.
+  using UnderlyingType = const ContainerType *;
+  UnderlyingType Impl;
 
-  /// Construct a new RangeSet representing '{ [from, to] }'.
-  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
-      : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
+public:
+  using const_iterator = ImplType::const_iterator;
+
+  const_iterator begin() const { return Impl->begin(); }
+  const_iterator end() const { return Impl->end(); }
+  size_t size() const { return Impl->size(); }
+
+  bool isEmpty() const { return Impl->empty(); }
+
+  class Factory {
+  public:
+    Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
+
+    /// Create a new set with all ranges from both LHS and RHS.
+    /// Possible intersections are not checked here.
+    ///
+    /// Complexity: O(N + M)
+    ///             where N = size(LHS), M = size(RHS)
+    RangeSet add(RangeSet LHS, RangeSet RHS);
+    /// Create a new set with all ranges from the original set plus the new one.
+    /// Possible intersections are not checked here.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet add(RangeSet Original, Range Element);
+    /// Create a new set with all ranges from the original set plus the point.
+    /// Possible intersections are not checked here.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet add(RangeSet Original, const llvm::APSInt &Point);
+
+    RangeSet getEmptySet() { return &EmptySet; }
+
+    /// Create a new set with just one range.
+    /// @{
+    RangeSet getRangeSet(Range Origin);
+    RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) {
+      return getRangeSet(Range(From, To));
+    }
+    RangeSet getRangeSet(const llvm::APSInt &Origin) {
+      return getRangeSet(Origin, Origin);
+    }
+    /// @}
+
+    /// Intersect the given range sets.
+    ///
+    /// Complexity: O(N + M)
+    ///             where N = size(LHS), M = size(RHS)
+    RangeSet intersect(RangeSet LHS, RangeSet RHS);
+    /// Intersect the given set with the closed range [Lower, Upper].
+    ///
+    /// Unlike the Range type, this range uses modular arithmetic, corresponding
+    /// to the common treatment of C integer overflow. Thus, if the Lower bound
+    /// is greater than the Upper bound, the range is taken to wrap around. This
+    /// is equivalent to taking the intersection with the two ranges [Min,
+    /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers
+    /// between Upper and Lower.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(What)
+    RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper);
+    /// Intersect the given range with the given point.
+    ///
+    /// The result can be either an empty set or a set containing the given
+    /// point depending on whether the point is in the range set.
+    ///
+    /// Complexity: O(logN)
+    ///             where N = size(What)
+    RangeSet intersect(RangeSet What, llvm::APSInt Point);
+
+    /// Delete the given point from the range set.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(From)
+    RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point);
+    /// Negate the given range set.
+    ///
+    /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
+    /// operation under the values of the type.
+    ///
+    /// We also handle MIN because applying unary minus to MIN does not change
+    /// it.
+    /// Example 1:
+    /// char x = -128;        // -128 is a MIN value in a range of 'char'
+    /// char y = -x;          // y: -128
+    ///
+    /// Example 2:
+    /// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
+    /// unsigned char y = -x; // y: 0
+    ///
+    /// And it makes us to separate the range
+    /// like [MIN, N] to [MIN, MIN] U [-N, MAX].
+    /// For instance, whole range is {-128..127} and subrange is [-128,-126],
+    /// thus [-128,-127,-126,...] negates to [-128,...,126,127].
+    ///
+    /// Negate restores disrupted ranges on bounds,
+    /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
+    ///
+    /// Negate is a self-inverse function, i.e. negate(negate(R)) == R.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(What)
+    RangeSet negate(RangeSet What);
+
+  private:
+    /// Return a persistent version of the given container.
+    RangeSet makePersistent(ContainerType &&From);
+    /// Construct a new persistent version of the given container.
+    ContainerType *construct(ContainerType &&From);
+
+    RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
+
+    // Many operations include producing new APSInt values and that's why
+    // we need this factory.
+    BasicValueFactory &ValueFactory;
+    // Allocator for all the created containers.
+    // Containers might own their own memory and that's why it is specific
+    // for the type, so it calls container destructors upon deletion.
+    llvm::SpecificBumpPtrAllocator<ContainerType> Arena;
+    // Usually we deal with the same ranges and range sets over and over.
+    // Here we track all created containers and try not to repeat ourselves.
+    llvm::FoldingSet<ContainerType> Cache;
+    static ContainerType EmptySet;
+  };
+
+  RangeSet(const RangeSet &) = default;
+  RangeSet &operator=(const RangeSet &) = default;
+  RangeSet(RangeSet &&) = default;
+  RangeSet &operator=(RangeSet &&) = default;
+  ~RangeSet() = default;
+
+  /// Construct a new RangeSet representing '{ [From, To] }'.
+  RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
+      : RangeSet(F.getRangeSet(From, To)) {}
 
   /// Construct a new RangeSet representing the given point as a range.
-  RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
+  RangeSet(Factory &F, const llvm::APSInt &Point)
+      : RangeSet(F.getRangeSet(Point)) {}
+
+  static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) {
+    ID.AddPointer(RS.Impl);
+  }
 
   /// Profile - Generates a hash profile of this RangeSet for use
   ///  by FoldingSet.
-  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
+  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); }
 
   /// getConcreteValue - If a symbol is contrained to equal a specific integer
   ///  constant then this method returns that value.  Otherwise, it returns
   ///  NULL.
   const llvm::APSInt *getConcreteValue() const {
-    return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
+    return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr;
   }
 
-  /// Get a minimal value covered by the ranges in the set
+  /// Get the minimal value covered by the ranges in the set.
+  ///
+  /// Complexity: O(1)
   const llvm::APSInt &getMinValue() const;
-  /// Get a maximal value covered by the ranges in the set
+  /// Get the maximal value covered by the ranges in the set.
+  ///
+  /// Complexity: O(1)
   const llvm::APSInt &getMaxValue() const;
 
-private:
-  void IntersectInRange(BasicValueFactory &BV, Factory &F,
-                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
-                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
-                        PrimRangeSet::iterator &e) const;
+  /// Test whether the given point is contained by any of the ranges.
+  ///
+  /// Complexity: O(logN)
+  ///             where N = size(this)
+  bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
+
+  void dump(raw_ostream &OS) const;
+
+  bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
+  bool operator!=(const RangeSet &Other) const { return !(*this == Other); }
 
+private:
+  /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
+  /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
+
+  /// Pin given points to the type represented by the current range set.
+  ///
+  /// This makes parameter points to be in-out parameters.
+  /// In order to maintain consistent types across all of the ranges in the set
+  /// and to keep all the operations to compare ONLY points of the same type, we
+  /// need to pin every point before any operation.
+  ///
+  /// @Returns true if the given points can be converted to the target type
+  ///          without changing the values (i.e. trivially) and false otherwise.
+  /// @{
   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+  bool pin(llvm::APSInt &Point) const;
+  /// @}
 
-public:
-  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
-                     llvm::APSInt Upper) const;
-  RangeSet Intersect(BasicValueFactory &BV, Factory &F,
-                     const RangeSet &Other) const;
-  RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
-  RangeSet Delete(BasicValueFactory &BV, Factory &F,
-                  const llvm::APSInt &Point) const;
-
-  void print(raw_ostream &os) const;
-
-  bool operator==(const RangeSet &other) const {
-    return ranges == other.ranges;
-  }
+  // This version of this function modifies its arguments (pins it).
+  bool containsImpl(llvm::APSInt &Point) const;
+
+  friend class Factory;
 };
 
 using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Reply via email to