[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

@vsavchenko Many thanks for your feedback!
I will make a new separate function for checking intersections considering all 
your suggestions along with the old quick `add` versions. I'll be more 
optimized.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:142
+  ContainerType::size_type InsertIdx = 0;
+  for (auto it = Original.begin(), e = Original.end(); it != e; ++it) {
+const llvm::APSInt  = it->From();

vsavchenko wrote:
> Is there a reason not to use range-based loop in this case?
You are right. Working on restoring O(N) I been played with iterators, then 
found another solution, but forgot to return range-based loop back. Thnx.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:150
+if (!IsIntersected) {
+  auto One = APSIntType(From).getValue(1);
+  const bool isCurrentRangeOnTheLeft = RTo < From;

vsavchenko wrote:
> This should be done outside of the loop, we assume that all the ranges are of 
> the same type.
+1 I'll move it outside the loop.


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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:114-115
+return RHS;
+  for (const Range  : RHS)
+LHS = add(LHS, R);
+  return LHS;

This is REAL bad.  The main benefit of the new `RangeSet` over the old one is 
the fact that common operations that consist of many basic operations are done 
on mutable containers, i.e. when `RHS` has 10 elements this code will create 
and copy a new array 10 times discarding 9 of them.

That's why every implementation method here operates on mutable `ContainerType` 
and then makes is persistent.

Additionally, merging add can be done with one iteration over two containers, 
but instead we do `O(N)` operation here `M` times, so it is not `O(N + M)`, but 
`O(N * M)`.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:142
+  ContainerType::size_type InsertIdx = 0;
+  for (auto it = Original.begin(), e = Original.end(); it != e; ++it) {
+const llvm::APSInt  = it->From();

Is there a reason not to use range-based loop in this case?



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:150
+if (!IsIntersected) {
+  auto One = APSIntType(From).getValue(1);
+  const bool isCurrentRangeOnTheLeft = RTo < From;

This should be done outside of the loop, we assume that all the ranges are of 
the same type.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:172
+  Range NewRange{ValueFactory.getValue(From), ValueFactory.getValue(To)};
+  Result.insert(Result.begin() + InsertIdx, NewRange);
+

This is a problem here.  This essentially doubles the work you did before.  
What can be done in one `O(N)` loop is done with two.

However, I don't really see a point in fixing this algorithm because the more 
generic `RangeSet` + `RangeSet` should be optimal `O(N + M)` and this one can 
be implemented as a special case.


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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:138-139
 
-  return makePersistent(std::move(Result));
-}
+  if (!Original.pin(From, To))
+return getEmptySet();
 

ASDenysPetrov wrote:
> This allows to add a RangeSet of any type. E.g. RangeSet(uchar) + 
> RangeSet(int) = valid, because of `pin`
> 
> I'm wondering whether we really need it here in practice?
We mix ranges of different types way more than one would expect.


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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added a comment.

In D99797#2666565 , @ASDenysPetrov 
wrote:

> @vsavchenko
> OK, what do you think of ***adjacency*** feature? I mean it simplifies such 
> ranges `[1,2][3,4][5,6]` to `[1,6]`. Is it worth for implementation?

I want to clarify my position here.  It's not that I am opposed to this change 
in principle, but I want to understand the motivation (a small example will be 
sufficient) and I don't want to sacrifice a single bit of performance 
efficiency of this part of code.
Even for the `O(N + M)` solution, I'd still be standing strong on keeping the 
old functions as is (except for maybe renaming them).  Range sets are small and 
asymptotics don't work that well when reasoning about the expected performance 
benefits and gains.
For this reason, whenever we can, we should have the simplest operation 
possible in terms of the number of instructions, ie the constant factor is very 
strong here.




Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:128
 ///
-/// Complexity: O(N + M)
+/// Complexity: O(N + Mlog(N))
 /// where N = size(LHS), M = size(RHS)

ASDenysPetrov wrote:
> vsavchenko wrote:
> > This most certainly can be done in `O(N + M)` the same way the intersection 
> > is done.
> Actually yes, it can. And it was, when I played with different solutions. But 
> the code was poor readable. So I decided make it easier to understand to 
> bring to review. Of couse I can move further to improve it and retain 
> readability. I'll do.
Bring it here and we'll see what can be done on that front. *makeover time!*



Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:146
+///
+/// Complexity: O(N + log(N))
+/// where N = size(Original)

nit: `O(N + log(N)) == O(N)`


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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

@vsavchenko FYI.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:112-113
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+  if (LHS.isEmpty())
+return RHS;
+  for (const Range  : RHS)

Also optimized this particular case.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:138-139
 
-  return makePersistent(std::move(Result));
-}
+  if (!Original.pin(From, To))
+return getEmptySet();
 

This allows to add a RangeSet of any type. E.g. RangeSet(uchar) + RangeSet(int) 
= valid, because of `pin`

I'm wondering whether we really need it here in practice?



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:166
 RawRangeSet RawExpected) {
-wrap(::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }

Fixed the misprint.


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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 335011.
ASDenysPetrov added a comment.

Updated. Restored complexity to O(N).


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

https://reviews.llvm.org/D99797

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

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::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 BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -195,9 +198,6 @@
 
   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);
@@ -310,24 +310,124 @@
 }
 
 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}});
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkAdd({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkAdd({{A, B}}, {}, {{A, B}});
+  this->checkAdd({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkAdd({}, B, {{B, B}});
+  this->checkAdd({}, {B, C}, {{B, C}});
+  this->checkAdd({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkAdd({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkAdd({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkAdd({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkAdd({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkAdd({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkAdd({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+
+  // RHS is inside LHS.
+  // RHS => ___
+  // LHS => ___/___\___ = ___
+  //___/__/_\__\___   ___/___\___
+  this->checkAdd({{A, C}}, MID, {{A, C}});
+  this->checkAdd({{A, D}}, {B, C}, {{A, D}});
+
+  // RHS wraps LHS.
+  // RHS =>  _
+  // LHS => /  _  \ = ___
+  //___/__/_\__\___   ___/___\___
+  this->checkAdd({{MID, MID}}, {A, D}, {{A, D}});
+ 

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

@vsavchenko
OK, what do you think of ***adjacency*** feature? I mean it simplifies such 
ranges `[1,2][3,4][5,6]` to `[1,6]`. Is it worth for implementation?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

In D99797#2666358 , @vsavchenko wrote:

> Thanks for working on improvements of the solver and constraints!  However, I 
> have some tough questions about this patch.
>
> What I really want to understand here is motivation.  Why do we need to have 
> `add` operation semantics like this in the first place?  My guess is that 
> "the user" will be in the following patch.
> Additionally, I don't really like the idea of replacing something simple and 
> fast (old `add` methods`) with something more complex unconditionally.  Old 
> users still don't need this additional logic.  C++ has always been the 
> language where we "pay for what we use".
> So, with good motivation, I'd still prefer methods like `add` and 
> `addUnchecked` or smith similar.

My motivation is that I'm currently working on some bigger improvement 
(symbolic integral cast) and stucked here of the lack of handling 
intersections. Would you mind of accepting this revision in case if I restore 
complexity to O(N+M)?




Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:128
 ///
-/// Complexity: O(N + M)
+/// Complexity: O(N + Mlog(N))
 /// where N = size(LHS), M = size(RHS)

vsavchenko wrote:
> This most certainly can be done in `O(N + M)` the same way the intersection 
> is done.
Actually yes, it can. And it was, when I played with different solutions. But 
the code was poor readable. So I decided make it easier to understand to bring 
to review. Of couse I can move further to improve it and retain readability. 
I'll do.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added a comment.

Thanks for working on improvements of the solver and constraints!  However, I 
have some tough questions about this patch.

What I really want to understand here is motivation.  Why do we need to have 
`add` operation semantics like this in the first place?  My guess is that "the 
user" will be in the following patch.
Additionally, I don't really like the idea of replacing something simple and 
fast (old `add` methods`) with something more complex unconditionally.  Old 
users still don't need this additional logic.  C++ has always been the language 
where we "pay for what we use".
So, with good motivation, I'd still prefer methods like `add` and 
`addUnchecked` or smith similar.




Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:128
 ///
-/// Complexity: O(N + M)
+/// Complexity: O(N + Mlog(N))
 /// where N = size(LHS), M = size(RHS)

This most certainly can be done in `O(N + M)` the same way the intersection is 
done.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: vsavchenko, steakhal, NoQ, xazax.hun, dcoughlin, 
Szelethus.
ASDenysPetrov added a project: clang.
Herald added subscribers: martong, Charusso, dkrupp, donat.nagy, 
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware.
ASDenysPetrov requested review of this revision.
Herald added a subscriber: cfe-commits.

Handle **intersected** and **adjacent** ranges uniting them into a single one.
Example:
intersection `[0, 10] U [5, 20] = [0, 20]`
adjacency `[0, 10] U [11, 20] = [0, 20]`


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D99797

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

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::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 BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -195,9 +198,6 @@
 
   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);
@@ -310,24 +310,124 @@
 }
 
 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}});
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkAdd({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkAdd({{A, B}}, {}, {{A, B}});
+  this->checkAdd({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkAdd({}, B, {{B, B}});
+  this->checkAdd({}, {B, C}, {{B, C}});
+  this->checkAdd({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkAdd({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkAdd({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkAdd({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkAdd({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkAdd({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkAdd({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+
+  // RHS is inside LHS.
+  // RHS =>