[analyzer] Replace StoreManager::evalIntegralCast with SValBuilder::evalCast

[ASDenysPetrov]

Summary

Simplify and move functionality from evalIntegralCast to evalCast. Replace evalIntegralCast with evalCast.

This patch shall not change any behavior.

[ASDenysPetrov]

A bit improved.

[steakhal]

Please make sure that you specify the parent revision or the patch can be applied on top of the tree.
Your lines clearly not match the top of the tree state.
https://github.com/llvm/llvm-project/blob/13f4448ae7db1a477ec2d48776e46415a3401314/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h#L129-L131

I really want to help you by finding regressions and stuff. But these mistakes hinder me a lot in applying your patches.

[ASDenysPetrov]

@steakhal

Please make sure that you specify the parent revision or the patch can be applied on top of the tree.

Sorry, probably missed to add a parent revision. Done.

[NoQ]

That's definitely an improvement for our API surface. I think this is good but like @steakhal said I recommend running on a large codebase looking for potential regressions because this code is (still) very much spaghetti and hard to reason about.

[ASDenysPetrov]

Rebased on main.

[steakhal]

All reports and crashes are preserved at this point of the patch stack - with or without z3 crosscheck on multiple projects - even on llvm.

[steakhal]

If @NoQ doesn't have any objections I'm ok with this change.

[NoQ]

Ok then, let's try to land it! 🤞

[ASDenysPetrov]

In D97388#2615104, @NoQ wrote:

Ok then, let's try to land it! 🤞

Thanks for the approval. Before land this we should land the preparatory revision D97296. Please, take a look. It should be safe as well.

[ASDenysPetrov]

This comment was removed by ASDenysPetrov.

[ASDenysPetrov]

Mistakenly erased with another patch. Restored. But anyway this revision should be abandoned as irrelevant any more. D103096 is a new revision which makes this patch deprecated.

[ASDenysPetrov]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

public:
     ///             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);
+    /// Create a new set which is a union of two given ranges.
+    /// Possible intersections are not checked here.
+    ///
+    /// Complexity: O(N + M)
+    ///             where N = size(LHS), M = size(RHS)
+    RangeSet unite(RangeSet LHS, RangeSet RHS);
+    /// Create a new set by uniting given range set with the given range.
+    /// All intersections and adjacent ranges are handled here.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet unite(RangeSet Original, Range Element);
+    /// Create a new set by uniting given range set with the given point.
+    /// All intersections and adjacent ranges are handled here.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet unite(RangeSet Original, llvm::APSInt Point);
+    /// Create a new set by uniting given range set with the given range
+    /// between points. All intersections and adjacent ranges are handled here.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet unite(RangeSet Original, llvm::APSInt From, llvm::APSInt To);
 
     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));
public:
 
   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);
+    /// NOTE: This function relies on the fact that all values in the
+    /// containers are persistent (created via BasicValueFactory::getValue).
+    ContainerType unite(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;

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 };
 
 //===----------------------------------------------------------------------===//
 //                           RangeSet implementation
 //===----------------------------------------------------------------------===//
 
 RangeSet::ContainerType RangeSet::Factory::EmptySet{};
 
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+  ContainerType Result;
+  Result.reserve(LHS.size() + RHS.size());
+  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
+             std::back_inserter(Result));
+  return makePersistent(std::move(Result));
+}
+
 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::unite(RangeSet LHS, RangeSet RHS) {
+  ContainerType Result = unite(*LHS.Impl, *RHS.Impl);
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, Range R) {
+  ContainerType Result;
+  Result.push_back(R);
+  Result = unite(*Original.Impl, Result);
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+  return unite(Original, Range(ValueFactory.getValue(Point)));
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From,
+                                  llvm::APSInt To) {
+  return unite(Original,
+               Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
+}
+
+RangeSet::ContainerType RangeSet::Factory::unite(const ContainerType &LHS,
+                                                 const ContainerType &RHS) {
+  if (LHS.empty())
+    return RHS;
+  if (RHS.empty())
+    return LHS;
+
+  using llvm::APSInt;
+  using iterator = ContainerType::const_iterator;
+
+  iterator I1 = LHS.begin();
+  iterator E1 = LHS.end();
+  iterator I2 = RHS.begin();
+  iterator E2 = RHS.end();
+  APSIntType Ty = APSIntType(I1->From());
+  const APSInt One = Ty.getValue(1);
+  const APSInt Min = Ty.getMinValue();
+  const APSInt *F = nullptr;
+  ContainerType Result;
+
+  // Handle a corner case first when both range sets start from MIN.
+  // This helps to avoid complicated conditions below.
+  if (Min == I1->From() && Min == I2->From()) {
+    if (I1->To() > I2->From()) {
+      // The second range is entirely inside the first one. Skip it.
+      // Check for the end of the range for every incrementation.
+      if (++I2 == E2)
+        goto end2;
+    } else {
+      // The first range is entirely inside the second one. Skip it.
+      // Check for the end of the range for every incrementation.
+      if (++I1 == E1)
+        goto end1;
+    }
+  }
+
+  while (true) {
+    // I1->From() shall be lower than I2->From().
+    // Otherwise, swap the iterators.
+    if (I1->From() > I2->From()) {
+      std::swap(I1, I2);
+      std::swap(E1, E2);
+    }
+
+    // Build a new range.
+    while (true) {
+      // Skip all enclosed ranges.
+      while (I1->To() >= I2->To()) {
+        // Check for the end of the range for every incrementation.
+        if (++I2 == E2)
+          goto end2;
+      }
+
+      // Check if the second range intersects or adjucent to the first one.
+      if (I1->To() < I2->From() - One)
+        break;
+
+      // We use `F` as a flag to notify that we are in a building of a new
+      // range. Set `From` of a new range if it is not set yet. If it has
+      // already been set, then we are inside this range and just looking for
+      // its end.
+      if (!F)
+        F = &I1->From();
+
+      // The first range is entirely inside the new range. Go next.
+      // Check for the end of the range for every incrementation.
+      if (++I1 == E1)
+        goto end1;
+
+      // Now we can surely swap the iterators without any check, as we know
+      // I2-From() to be lower than I1-From().
+      std::swap(I1, I2);
+      std::swap(E1, E2);
+    }
+
+    // Here the first and second ranges are disjoint. So we can add a new
+    // range, if expected, or add just the first range.
+    if (F) {
+      Result.emplace_back(*F, I1->To());
+      // Clear `F` to notify we are out of the new range.
+      F = nullptr;
+    } else
+      Result.push_back(*I1);
+
+    // The first range is entirely inside the added range. Go next.
+    // Check for the end of the range for every incrementation.
+    if (++I1 == E1)
+      goto end1;
+  };
+
+// There are no ranges left in one of the ranges. Append the rest of the ranges
+// from another range set to the Result.
+end1:
+  I1 = I2;
+  E1 = E2;
+end2:
+  // Do not forget to add a new range if it expects to be set.
+  if (F) {
+    Result.emplace_back(*F, I1->To());
+    // Skip the current range as it was enclosed by a new range.
+    // We don't need to check `I1 == E1` here, as it handles in `append`
+    // function below.
+    ++I1;
+  }
+  Result.append(I1, E1);
+  return Result;
+}
+
 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;
RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
   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 {
   assert(!isEmpty());
   return begin()->From();
 }
 
 const llvm::APSInt &RangeSet::getMaxValue() const {
   assert(!isEmpty());
   return std::prev(end())->To();

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
   return OS << toString(Set);
 }
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template <typename T> struct TestValues {
+  static constexpr T MIN = std::numeric_limits<T>::min();
+  static constexpr T MAX = std::numeric_limits<T>::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).
+  static constexpr T MID =
+      std::is_signed<T>::value ? 0 : ~(static_cast<T>(-1) / static_cast<T>(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+                "Values shall be in an ascending order");
+};
+
 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 Arena;
   BasicValueFactory BVF{Context, Arena};
   RangeSet::Factory F{BVF};
   // End init block
 
   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);
+    static llvm::APSInt Base{sizeof(BaseType) * 8,
+                             std::is_unsigned<BaseType>::value};
+    Base = X;
+    return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
     return Range(from(Init.first), from(Init.second));
   }
 
   RangeSet from(const RawRangeSet &Init) {
     RangeSet RangeSet = F.getEmptySet();
public:
   }
 
   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);
+    wrap(&Self::checkAddImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
     wrap(&Self::checkAddImpl<const llvm::APSInt &>, RawLHS, RawRHS,
          RawExpected);
   }
 
+  template <class RHSType>
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+    RangeSet Result = F.unite(LHS, RHS);
+    EXPECT_EQ(Result, Expected)
+        << "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+                  RawRangeSet RawExpected) {
+    wrap(&Self::checkUniteImpl<Range>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+                  RawRangeSet RawExpected) {
+    wrap(&Self::checkUniteImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+                  RawRangeSet RawExpected) {
+    wrap(&Self::checkUniteImpl<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);
   }
 };
 
 } // 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");
+  using TV = TestValues<TypeParam>;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+  constexpr auto A = TV::A;
+  constexpr auto B = TV::B;
+  constexpr auto C = TV::C;
+  constexpr auto D = TV::D;
 
   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}});
TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) {
   // 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();
+  using TV = TestValues<TypeParam>;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
 
   // 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.
TYPED_TEST(RangeSetTest, RangeSetContainsTest) {
   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();
+  using TV = TestValues<TypeParam>;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+
   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
TYPED_TEST(RangeSetTest, RangeSetAddTest) {
   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();
+  using TV = TestValues<TypeParam>;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
 
   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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+  using TV = TestValues<TypeParam>;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+  constexpr auto A = TV::A;
+  constexpr auto B = TV::B;
+  constexpr auto C = TV::C;
+  constexpr auto D = TV::D;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS =>                     =
+  //        ___________________   ___________________
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>        _____        =        _____
+  //        ______/_____\______   ______/_____\______
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+  this->checkUnite({{MIN, MIN}}, {}, {{MIN, MIN}});
+  this->checkUnite({{MAX, MAX}}, {}, {{MAX, MAX}});
+  this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {}, {{MIN, MIN}, {MAX, MAX}});
+
+  // LHS is empty.
+  // RHS =>         ___
+  // LHS =>        /   \        =        _____
+  //        ______/_____\______   ______/_____\______
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+  this->checkUnite({}, {{MIN, MIN}}, {{MIN, MIN}});
+  this->checkUnite({}, {{MAX, MAX}}, {{MAX, MAX}});
+  this->checkUnite({}, {{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS =>             ___
+  // LHS =>    ___     /   \    =    ___     _____
+  //        __/___\___/_____\__   __/___\___/_____\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+                   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+                   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MAX, MAX}}, {A, B}, {{A, B}, {MAX, MAX}});
+  this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}});
+  this->checkUnite({{MIN, MIN}}, {MAX, MAX}, {{MIN, MIN}, {MAX, MAX}});
+
+  // RHS is inside LHS.
+  // RHS =>         ___
+  // LHS =>     ___/___\___     =     ___________
+  //        ___/__/_____\__\___   ___/___________\___
+  this->checkUnite({{A, C}}, MID, {{A, C}});
+  this->checkUnite({{A, D}}, {B, C}, {{A, D}});
+
+  // RHS wraps LHS.
+  // RHS =>      _________
+  // LHS =>     /  _____  \     =     ___________
+  //        ___/__/_____\__\___   ___/___________\___
+  this->checkUnite({{MID, MID}}, {A, D}, {{A, D}});
+  this->checkUnite({{B, C}}, {A, D}, {{A, D}});
+  this->checkUnite({{A, B}}, {MIN, MAX}, {{MIN, MAX}});
+
+  // RHS equals to LHS.
+  // RHS =>      _________
+  // LHS =>     /_________\     =     ___________
+  //        ___/___________\___   ___/___________\___
+  this->checkUnite({{MIN, MIN}}, MIN, {{MIN, MIN}});
+  this->checkUnite({{A, B}}, {A, B}, {{A, B}});
+  this->checkUnite({{MAX, MAX}}, {{MAX, MAX}}, {{MAX, MAX}});
+  this->checkUnite({{MIN, MIN}}, {{MIN, MIN}}, {{MIN, MIN}});
+  this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}},
+                   {{MIN, MIN}, {MAX, MAX}});
+
+  // RHS intersects right of LHS.
+  // RHS =>         ______
+  // LHS =>     ___/____  \     =     ___________
+  //        ___/__/_____\__\___   ___/___________\___
+  this->checkUnite({{A, C}}, C, {{A, C}});
+  this->checkUnite({{A, C}}, {B, D}, {{A, D}});
+
+  // RHS intersects left of LHS.
+  // RHS =>      ______
+  // LHS =>     /  ____\___     =     ___________
+  //        ___/__/_____\__\___   ___/___________\___
+  this->checkUnite({{B, D}}, B, {{B, D}});
+  this->checkUnite({{B, D}}, {A, C}, {{A, D}});
+
+  // RHS adjacent to LHS on right.
+  // RHS =>            _____
+  // LHS =>   ______  /     \   =   _______________
+  //        _/______\/_______\_   _/_______________\_
+  this->checkUnite({{A, B - 1}}, B, {{A, B}});
+  this->checkUnite({{A, C}}, {C + 1, D}, {{A, D}});
+
+  // RHS adjacent to LHS on left.
+  // RHS =>    _____
+  // LHS =>   /     \  ______   =   _______________
+  //        _/_______\/______\_   _/_______________\_
+  this->checkUnite({{B + 1, C}}, B, {{B, C}});
+  this->checkUnite({{B, D}}, {A, B - 1}, {{A, D}});
+
+  // RHS adjacent to LHS in between.
+  // RHS =>         ___
+  // LHS =>   ___  /   \  ___   =   _______________
+  //        _/___\/_____\/___\_   _/_______________\_
+  this->checkUnite({{A, MID - 1}, {MID + 1, D}}, MID, {{A, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {A + 1, D - 1}, {{MIN, MAX}});
+
+  // RHS adjacent to LHS on the outside.
+  // RHS =>    __         __
+  // LHS =>   /  \  ___  /  \   =   _______________
+  //        _/____\/___\/____\_   _/_______________\_
+  this->checkUnite({{C, C}}, {{A, C - 1}, {C + 1, D}}, {{A, D}});
+  this->checkUnite({{B, MID}}, {{A, B - 1}, {MID + 1, D}}, {{A, D}});
+
+  // RHS wraps two subranges of LHS.
+  // RHS =>     ___________
+  // LHS =>    / ___   ___ \    =    _____________
+  //        __/_/___\_/___\_\__   __/_____________\__
+  this->checkUnite({{B, B}, {MID, MID}, {C, C}}, {{A, D}}, {{A, D}});
+  this->checkUnite({{A, B}, {MID, C}}, {{MIN, D}}, {{MIN, D}});
+
+  // RHS intersects two subranges of LHS.
+  // RHS =>      _________
+  // LHS =>   __/__      _\__   =   _______________
+  //        _/_/___\____/__\_\_   _/_______________\_
+  this->checkUnite({{MIN, B}, {C, MAX}}, {{A, D}}, {{MIN, MAX}});
+
+  // Multiple intersections.
+
+  // RHS =>
+  // LHS =>   /\   /\            =   __   __
+  //        _/__\_/__\_/\_/\_/\_   _/__\_/__\_/\_/\_/\_
+  this->checkUnite({{MIN, A}, {A + 2, B}}, {{MID, C}, {C + 2, D - 2}, {D, MAX}},
+                   {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}});
+  this->checkUnite({{MIN, MIN}, {A, A}}, {{B, B}, {C, C}, {MAX, MAX}},
+                   {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}});
+
+  // RHS =>
+  // LHS =>             /\   /\   =            __   __
+  //        _/\_/\_/\__/__\_/__\_   _/\_/\_/\_/__\_/__\_
+  this->checkUnite({{C + 2, D - 2}, {D, MAX}}, {{MIN, A}, {A + 2, B}, {MID, C}},
+                   {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}});
+  this->checkUnite({{C, C}, {MAX, MAX}}, {{MIN, MIN}, {A, A}, {B, B}},
+                   {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}});
+
+  // RHS =>
+  // LHS =>   _   /\   _   /\   _   /\  =
+  //        _/_\_/__\_/_\_/__\_/_\_/__\_
+  //
+  // RSLT =>  _   __   _   __   _   __
+  //        _/_\_/__\_/_\_/__\_/_\_/__\_
+  this->checkUnite({{A + 2, B}, {MID + 2, C}, {D + 2, MAX}},
+                   {{MIN, A}, {B + 2, MID}, {C + 2, D}},
+                   {{MIN, A},
+                    {A + 2, B},
+                    {B + 2, MID},
+                    {MID + 2, C},
+                    {C + 2, D},
+                    {D + 2, MAX}});
+  this->checkUnite({{A, A}, {C, C}, {MAX, MAX}}, {{MIN, MIN}, {B, B}, {D, D}},
+                   {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}});
+
+  // RHS =>
+  // LHS =>   /\   _   /\   _   /\   _  =
+  //        _/__\_/_\_/__\_/_\_/__\_/_\_
+  //
+  // RSLT =>  __   _   __   _   __   _
+  //        _/__\_/_\_/__\_/_\_/__\_/_\_
+  this->checkUnite({{MIN, A}, {B + 2, MID}, {C + 2, D}},
+                   {{A + 2, B}, {MID + 2, C}, {D + 2, MAX}},
+                   {{MIN, A},
+                    {A + 2, B},
+                    {B + 2, MID},
+                    {MID + 2, C},
+                    {C + 2, D},
+                    {D + 2, MAX}});
+  this->checkUnite({{MIN, MIN}, {B, B}, {D, D}}, {{A, A}, {C, C}, {MAX, MAX}},
+                   {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}});
+
+  // RHS =>    _     __       _
+  // LHS =>   /_\   /_ \  _  / \   =   ___   ____________
+  //        _/___\_/__\_\/_\/___\_   _/___\_/____________\_
+  this->checkUnite({{MIN, A}, {B, C}, {D, MAX}},
+                   {{MIN, A}, {B, C - 2}, {C + 1, D - 1}},
+                   {{MIN, A}, {B, MAX}});
+  this->checkUnite({{A, A}, {B, MID}, {D, D}},
+                   {{A, A}, {B, B}, {MID + 1, D - 1}}, {{A, A}, {B, D}});
+
+  // RHS =>            ___      ___
+  // LHS =>      /\  _/_  \_   / _ \   /\  =
+  //        _/\_/__\//__\ /\\_/_/_\_\_/__\_
+  //
+  // RSLT =>     ___________   _____   __
+  //        _/\_/___________\_/_____\_/__\_
+  this->checkUnite({{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}},
+                   {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}},
+                   {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}});
+}