1 //===- unittests/StaticAnalyzer/RangeSetTest.cpp ----------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "clang/Basic/Builtins.h" 10 #include "clang/Basic/FileManager.h" 11 #include "clang/Basic/SourceManager.h" 12 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" 13 #include "clang/Tooling/Tooling.h" 14 #include "llvm/ADT/APSInt.h" 15 #include "llvm/Support/raw_ostream.h" 16 #include "gtest/gtest.h" 17 18 using namespace clang; 19 using namespace ento; 20 21 namespace clang { 22 namespace ento { 23 24 template <class RangeOrSet> static std::string toString(const RangeOrSet &Obj) { 25 std::string ObjRepresentation; 26 llvm::raw_string_ostream SS(ObjRepresentation); 27 Obj.dump(SS); 28 return SS.str(); 29 } 30 LLVM_ATTRIBUTE_UNUSED static std::string toString(const llvm::APSInt &Point) { 31 return toString(Point, 10); 32 } 33 // We need it here for better fail diagnostics from gtest. 34 LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS, 35 const RangeSet &Set) { 36 return OS << toString(Set); 37 } 38 // We need it here for better fail diagnostics from gtest. 39 LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS, 40 const Range &R) { 41 return OS << toString(R); 42 } 43 44 } // namespace ento 45 } // namespace clang 46 47 namespace { 48 49 template <typename T> struct TestValues { 50 static constexpr T MIN = std::numeric_limits<T>::min(); 51 static constexpr T MAX = std::numeric_limits<T>::max(); 52 // MID is a value in the middle of the range 53 // which unary minus does not affect on, 54 // e.g. int8/int32(0), uint8(128), uint32(2147483648). 55 static constexpr T MID = 56 std::is_signed<T>::value ? 0 : ~(static_cast<T>(-1) / static_cast<T>(2)); 57 static constexpr T A = MID - (MAX - MID) / 3 * 2; 58 static constexpr T B = MID - (MAX - MID) / 3; 59 static constexpr T C = -B; 60 static constexpr T D = -A; 61 62 static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, 63 "Values shall be in an ascending order"); 64 }; 65 66 template <typename BaseType> class RangeSetTest : public testing::Test { 67 public: 68 // Init block 69 std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;"); 70 ASTContext &Context = AST->getASTContext(); 71 llvm::BumpPtrAllocator Arena; 72 BasicValueFactory BVF{Context, Arena}; 73 RangeSet::Factory F{BVF}; 74 // End init block 75 76 using Self = RangeSetTest<BaseType>; 77 using RawRange = std::pair<BaseType, BaseType>; 78 using RawRangeSet = std::initializer_list<RawRange>; 79 80 const llvm::APSInt &from(BaseType X) { 81 static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT, 82 std::is_unsigned<BaseType>::value}; 83 Base = X; 84 return BVF.getValue(Base); 85 } 86 87 Range from(const RawRange &Init) { 88 return Range(from(Init.first), from(Init.second)); 89 } 90 91 RangeSet from(const RawRangeSet &Init) { 92 RangeSet RangeSet = F.getEmptySet(); 93 for (const auto &Raw : Init) { 94 RangeSet = F.add(RangeSet, from(Raw)); 95 } 96 return RangeSet; 97 } 98 99 template <class F, class... RawArgTypes> 100 void wrap(F ActualFunction, RawArgTypes &&... Args) { 101 (this->*ActualFunction)(from(std::forward<RawArgTypes>(Args))...); 102 } 103 104 void checkNegateImpl(RangeSet Original, RangeSet Expected) { 105 RangeSet NegatedFromOriginal = F.negate(Original); 106 EXPECT_EQ(NegatedFromOriginal, Expected); 107 // Negate negated back and check with original. 108 RangeSet NegatedBackward = F.negate(NegatedFromOriginal); 109 EXPECT_EQ(NegatedBackward, Original); 110 } 111 112 void checkNegate(RawRangeSet RawOriginal, RawRangeSet RawExpected) { 113 wrap(&Self::checkNegateImpl, RawOriginal, RawExpected); 114 } 115 116 template <class PointOrSet> 117 void checkIntersectImpl(RangeSet LHS, PointOrSet RHS, RangeSet Expected) { 118 RangeSet Result = F.intersect(LHS, RHS); 119 EXPECT_EQ(Result, Expected) 120 << "while intersecting " << toString(LHS) << " and " << toString(RHS); 121 } 122 123 void checkIntersectRangeImpl(RangeSet LHS, const llvm::APSInt &Lower, 124 const llvm::APSInt &Upper, RangeSet Expected) { 125 RangeSet Result = F.intersect(LHS, Lower, Upper); 126 EXPECT_EQ(Result, Expected) 127 << "while intersecting " << toString(LHS) << " and [" << toString(Lower) 128 << ", " << toString(Upper) << "]"; 129 } 130 131 void checkIntersect(RawRangeSet RawLHS, RawRangeSet RawRHS, 132 RawRangeSet RawExpected) { 133 wrap(&Self::checkIntersectImpl<RangeSet>, RawLHS, RawRHS, RawExpected); 134 } 135 136 void checkIntersect(RawRangeSet RawLHS, BaseType RawRHS, 137 RawRangeSet RawExpected) { 138 wrap(&Self::checkIntersectImpl<const llvm::APSInt &>, RawLHS, RawRHS, 139 RawExpected); 140 } 141 142 void checkIntersect(RawRangeSet RawLHS, BaseType RawLower, BaseType RawUpper, 143 RawRangeSet RawExpected) { 144 wrap(&Self::checkIntersectRangeImpl, RawLHS, RawLower, RawUpper, 145 RawExpected); 146 } 147 148 void checkContainsImpl(RangeSet LHS, const llvm::APSInt &RHS, bool Expected) { 149 bool Result = LHS.contains(RHS); 150 EXPECT_EQ(Result, Expected) 151 << toString(LHS) << (Result ? " contains " : " doesn't contain ") 152 << toString(RHS); 153 } 154 155 void checkContains(RawRangeSet RawLHS, BaseType RawRHS, bool Expected) { 156 checkContainsImpl(from(RawLHS), from(RawRHS), Expected); 157 } 158 159 template <class RHSType> 160 void checkAddImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) { 161 RangeSet Result = F.add(LHS, RHS); 162 EXPECT_EQ(Result, Expected) 163 << "while adding " << toString(LHS) << " and " << toString(RHS); 164 } 165 166 void checkAdd(RawRangeSet RawLHS, RawRange RawRHS, RawRangeSet RawExpected) { 167 wrap(&Self::checkAddImpl<Range>, RawLHS, RawRHS, RawExpected); 168 } 169 170 void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS, 171 RawRangeSet RawExpected) { 172 wrap(&Self::checkAddImpl<RangeSet>, RawLHS, RawRHS, RawExpected); 173 } 174 175 void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) { 176 wrap(&Self::checkAddImpl<const llvm::APSInt &>, RawLHS, RawRHS, 177 RawExpected); 178 } 179 180 template <class RHSType> 181 void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) { 182 RangeSet Result = F.unite(LHS, RHS); 183 EXPECT_EQ(Result, Expected) 184 << "while uniting " << toString(LHS) << " and " << toString(RHS); 185 } 186 187 void checkUnite(RawRangeSet RawLHS, RawRange RawRHS, 188 RawRangeSet RawExpected) { 189 wrap(&Self::checkUniteImpl<Range>, RawLHS, RawRHS, RawExpected); 190 } 191 192 void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS, 193 RawRangeSet RawExpected) { 194 wrap(&Self::checkUniteImpl<RangeSet>, RawLHS, RawRHS, RawExpected); 195 } 196 197 void checkUnite(RawRangeSet RawLHS, BaseType RawRHS, 198 RawRangeSet RawExpected) { 199 wrap(&Self::checkUniteImpl<const llvm::APSInt &>, RawLHS, RawRHS, 200 RawExpected); 201 } 202 203 void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From, 204 RangeSet Expected) { 205 RangeSet Result = F.deletePoint(From, Point); 206 EXPECT_EQ(Result, Expected) 207 << "while deleting " << toString(Point) << " from " << toString(From); 208 } 209 210 void checkDelete(BaseType Point, RawRangeSet RawFrom, 211 RawRangeSet RawExpected) { 212 wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected); 213 } 214 }; 215 216 } // namespace 217 218 using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t, 219 uint32_t, int64_t, uint64_t>; 220 TYPED_TEST_SUITE(RangeSetTest, IntTypes, ); 221 222 TYPED_TEST(RangeSetTest, RangeSetNegateTest) { 223 using TV = TestValues<TypeParam>; 224 constexpr auto MIN = TV::MIN; 225 constexpr auto MAX = TV::MAX; 226 constexpr auto MID = TV::MID; 227 constexpr auto A = TV::A; 228 constexpr auto B = TV::B; 229 constexpr auto C = TV::C; 230 constexpr auto D = TV::D; 231 232 this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}}); 233 this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}}); 234 this->checkNegate({{MIN, MID}}, {{MIN, MIN}, {MID, MAX}}); 235 this->checkNegate({{MIN, MAX}}, {{MIN, MAX}}); 236 this->checkNegate({{A, D}}, {{A, D}}); 237 this->checkNegate({{A, B}}, {{C, D}}); 238 this->checkNegate({{MIN, A}, {D, MAX}}, {{MIN, A}, {D, MAX}}); 239 this->checkNegate({{MIN, B}, {MID, D}}, {{MIN, MIN}, {A, MID}, {C, MAX}}); 240 this->checkNegate({{MIN, MID}, {C, D}}, {{MIN, MIN}, {A, B}, {MID, MAX}}); 241 this->checkNegate({{MIN, MID}, {C, MAX}}, {{MIN, B}, {MID, MAX}}); 242 this->checkNegate({{A, MID}, {D, MAX}}, {{MIN + 1, A}, {MID, D}}); 243 this->checkNegate({{A, A}}, {{D, D}}); 244 this->checkNegate({{MID, MID}}, {{MID, MID}}); 245 this->checkNegate({{MAX, MAX}}, {{MIN + 1, MIN + 1}}); 246 } 247 248 TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) { 249 // Check that we can correctly intersect empty sets. 250 this->checkIntersect({}, 42, {}); 251 // Check that intersection with itself produces the same set. 252 this->checkIntersect({{42, 42}}, 42, {{42, 42}}); 253 // Check more general cases. 254 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 42, {}); 255 this->checkIntersect({{0, 10}, {20, 30}, {30, 60}}, 42, {{42, 42}}); 256 } 257 258 TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) { 259 using TV = TestValues<TypeParam>; 260 constexpr auto MIN = TV::MIN; 261 constexpr auto MAX = TV::MAX; 262 263 // Check that we can correctly intersect empty sets. 264 this->checkIntersect({}, 10, 20, {}); 265 this->checkIntersect({}, 20, 10, {}); 266 // Check that intersection with itself produces the same set. 267 this->checkIntersect({{10, 20}}, 10, 20, {{10, 20}}); 268 this->checkIntersect({{MIN, 10}, {20, MAX}}, 20, 10, {{MIN, 10}, {20, MAX}}); 269 // Check non-overlapping range intersections. 270 this->checkIntersect({{10, 20}}, 21, 9, {}); 271 this->checkIntersect({{MIN, 9}, {21, MAX}}, 10, 20, {}); 272 // Check more general cases. 273 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 10, 35, 274 {{10, 10}, {20, 30}, {30, 35}}); 275 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 35, 10, 276 {{0, 10}, {35, 40}, {50, 60}}); 277 } 278 279 TYPED_TEST(RangeSetTest, RangeSetGenericIntersectTest) { 280 // Check that we can correctly intersect empty sets. 281 this->checkIntersect({}, {}, {}); 282 this->checkIntersect({}, {{0, 10}}, {}); 283 this->checkIntersect({{0, 10}}, {}, {}); 284 285 this->checkIntersect({{0, 10}}, {{4, 6}}, {{4, 6}}); 286 this->checkIntersect({{0, 10}}, {{4, 20}}, {{4, 10}}); 287 // Check that intersection with points works as expected. 288 this->checkIntersect({{0, 10}}, {{4, 4}}, {{4, 4}}); 289 // All ranges are closed, check that intersection with edge points works as 290 // expected. 291 this->checkIntersect({{0, 10}}, {{10, 10}}, {{10, 10}}); 292 293 // Let's check that we can skip some intervals and partially intersect 294 // other intervals. 295 this->checkIntersect({{0, 2}, {4, 5}, {6, 9}, {10, 11}, {12, 12}, {13, 15}}, 296 {{8, 14}, {20, 30}}, 297 {{8, 9}, {10, 11}, {12, 12}, {13, 14}}); 298 // Check more generic case. 299 this->checkIntersect( 300 {{0, 1}, {2, 3}, {5, 6}, {7, 15}, {25, 30}}, 301 {{4, 10}, {11, 11}, {12, 16}, {17, 17}, {19, 20}, {21, 23}, {24, 27}}, 302 {{5, 6}, {7, 10}, {11, 11}, {12, 15}, {25, 27}}); 303 } 304 305 TYPED_TEST(RangeSetTest, RangeSetContainsTest) { 306 // Check with an empty set. 307 this->checkContains({}, 10, false); 308 // Check contains with sets of size one: 309 // * when the whole range is less 310 this->checkContains({{0, 5}}, 10, false); 311 // * when the whole range is greater 312 this->checkContains({{20, 25}}, 10, false); 313 // * when the range is just the point we are looking for 314 this->checkContains({{10, 10}}, 10, true); 315 // * when the range starts with the point 316 this->checkContains({{10, 15}}, 10, true); 317 // * when the range ends with the point 318 this->checkContains({{5, 10}}, 10, true); 319 // * when the range has the point somewhere in the middle 320 this->checkContains({{0, 25}}, 10, true); 321 // Check similar cases, but with larger sets. 322 this->checkContains({{0, 5}, {10, 10}, {15, 20}}, 10, true); 323 this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true); 324 this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true); 325 326 using TV = TestValues<TypeParam>; 327 constexpr auto MIN = TV::MIN; 328 constexpr auto MAX = TV::MAX; 329 constexpr auto MID = TV::MID; 330 331 this->checkContains({{MIN, MAX}}, 0, true); 332 this->checkContains({{MIN, MAX}}, MID, true); 333 this->checkContains({{MIN, MAX}}, -10, true); 334 this->checkContains({{MIN, MAX}}, 10, true); 335 } 336 337 TYPED_TEST(RangeSetTest, RangeSetAddTest) { 338 // Check adding single points 339 this->checkAdd({}, 10, {{10, 10}}); 340 this->checkAdd({{0, 5}}, 10, {{0, 5}, {10, 10}}); 341 this->checkAdd({{0, 5}, {30, 40}}, 10, {{0, 5}, {10, 10}, {30, 40}}); 342 343 // Check adding single ranges. 344 this->checkAdd({}, {10, 20}, {{10, 20}}); 345 this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}}); 346 this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}}); 347 348 // Check adding whole sets of ranges. 349 this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}}); 350 // Check that ordering of ranges is as expected. 351 this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}}); 352 this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}}, 353 {{0, 5}, {10, 20}, {30, 40}, {50, 60}}); 354 this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}}, 355 {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}}); 356 } 357 358 TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) { 359 using TV = TestValues<TypeParam>; 360 constexpr auto MIN = TV::MIN; 361 constexpr auto MAX = TV::MAX; 362 constexpr auto MID = TV::MID; 363 364 this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}}); 365 // Check that delete works with an empty set. 366 this->checkDelete(10, {}, {}); 367 // Check that delete can remove entire ranges. 368 this->checkDelete(10, {{10, 10}}, {}); 369 this->checkDelete(10, {{0, 5}, {10, 10}, {20, 30}}, {{0, 5}, {20, 30}}); 370 // Check that delete can split existing ranges into two. 371 this->checkDelete(10, {{0, 5}, {7, 15}, {20, 30}}, 372 {{0, 5}, {7, 9}, {11, 15}, {20, 30}}); 373 // Check that delete of the point not from the range set works as expected. 374 this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}}); 375 } 376 377 TYPED_TEST(RangeSetTest, RangeSetUniteTest) { 378 using TV = TestValues<TypeParam>; 379 constexpr auto MIN = TV::MIN; 380 constexpr auto MAX = TV::MAX; 381 constexpr auto MID = TV::MID; 382 constexpr auto A = TV::A; 383 constexpr auto B = TV::B; 384 constexpr auto C = TV::C; 385 constexpr auto D = TV::D; 386 387 // LHS and RHS is empty. 388 // RHS => 389 // LHS => = 390 // ___________________ ___________________ 391 this->checkUnite({}, {}, {}); 392 393 // RHS is empty. 394 // RHS => 395 // LHS => _____ = _____ 396 // ______/_____\______ ______/_____\______ 397 this->checkUnite({{A, B}}, {}, {{A, B}}); 398 this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}}); 399 this->checkUnite({{MIN, MIN}}, {}, {{MIN, MIN}}); 400 this->checkUnite({{MAX, MAX}}, {}, {{MAX, MAX}}); 401 this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {}, {{MIN, MIN}, {MAX, MAX}}); 402 403 // LHS is empty. 404 // RHS => ___ 405 // LHS => / \ = _____ 406 // ______/_____\______ ______/_____\______ 407 this->checkUnite({}, B, {{B, B}}); 408 this->checkUnite({}, {B, C}, {{B, C}}); 409 this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}}); 410 this->checkUnite({}, {{MIN, MIN}}, {{MIN, MIN}}); 411 this->checkUnite({}, {{MAX, MAX}}, {{MAX, MAX}}); 412 this->checkUnite({}, {{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}}); 413 414 // RHS is detached from LHS. 415 // RHS => ___ 416 // LHS => ___ / \ = ___ _____ 417 // __/___\___/_____\__ __/___\___/_____\__ 418 this->checkUnite({{A, C}}, D, {{A, C}, {D, D}}); 419 this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}}); 420 this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}}); 421 this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}}); 422 this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}}, 423 {{MIN, A}, {B, MID}, {C, C}, {D, MAX}}); 424 this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}}, 425 {{MIN, A}, {B, MID}, {C, C}, {D, MAX}}); 426 this->checkUnite({{A, B}}, {{MAX, MAX}}, {{A, B}, {MAX, MAX}}); 427 this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}}); 428 this->checkUnite({{MIN, MIN}}, {MAX, MAX}, {{MIN, MIN}, {MAX, MAX}}); 429 430 // RHS is inside LHS. 431 // RHS => ___ 432 // LHS => ___/___\___ = ___________ 433 // ___/__/_____\__\___ ___/___________\___ 434 this->checkUnite({{A, C}}, MID, {{A, C}}); 435 this->checkUnite({{A, D}}, {B, C}, {{A, D}}); 436 this->checkUnite({{MIN, MAX}}, {B, C}, {{MIN, MAX}}); 437 438 // RHS wraps LHS. 439 // RHS => _________ 440 // LHS => / _____ \ = ___________ 441 // ___/__/_____\__\___ ___/___________\___ 442 this->checkUnite({{MID, MID}}, {A, D}, {{A, D}}); 443 this->checkUnite({{B, C}}, {A, D}, {{A, D}}); 444 this->checkUnite({{A, B}}, {MIN, MAX}, {{MIN, MAX}}); 445 446 // RHS equals to LHS. 447 // RHS => _________ 448 // LHS => /_________\ = ___________ 449 // ___/___________\___ ___/___________\___ 450 this->checkUnite({{MIN, MIN}}, MIN, {{MIN, MIN}}); 451 this->checkUnite({{A, B}}, {A, B}, {{A, B}}); 452 this->checkUnite({{MAX, MAX}}, {{MAX, MAX}}, {{MAX, MAX}}); 453 this->checkUnite({{MIN, MIN}}, {{MIN, MIN}}, {{MIN, MIN}}); 454 this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}}, 455 {{MIN, MIN}, {MAX, MAX}}); 456 457 // RHS edge is MIN and attached and inside LHS. 458 // RHS => _____ 459 // LHS => /_____\_____ = ___________ 460 // /_______\____\___ /___________\___ 461 this->checkUnite({{MIN, A}}, {MIN, B}, {{MIN, B}}); 462 463 // RHS edge is MIN and attached and outsude LHS. 464 // RHS => __________ 465 // LHS => /______ \ = ___________ 466 // /_______\____\___ /___________\___ 467 this->checkUnite({{MIN, B}}, {MIN, A}, {{MIN, B}}); 468 469 // RHS intersects right of LHS. 470 // RHS => ______ 471 // LHS => ___/____ \ = ___________ 472 // ___/__/_____\__\___ ___/___________\___ 473 this->checkUnite({{A, C}}, C, {{A, C}}); 474 this->checkUnite({{A, C}}, {B, D}, {{A, D}}); 475 476 // RHS intersects left of LHS. 477 // RHS => ______ 478 // LHS => / ____\___ = ___________ 479 // ___/__/_____\__\___ ___/___________\___ 480 this->checkUnite({{B, D}}, B, {{B, D}}); 481 this->checkUnite({{B, D}}, {A, C}, {{A, D}}); 482 this->checkUnite({{MID, MAX}}, {MIN, MID}, {{MIN, MAX}}); 483 484 // RHS adjacent to LHS on right. 485 // RHS => _____ 486 // LHS => ______ / \ = _______________ 487 // _/______\/_______\_ _/_______________\_ 488 this->checkUnite({{A, B - 1}}, B, {{A, B}}); 489 this->checkUnite({{A, C}}, {C + 1, D}, {{A, D}}); 490 this->checkUnite({{MIN, MID}}, {MID + 1, MAX}, {{MIN, MAX}}); 491 492 // RHS adjacent to LHS on left. 493 // RHS => _____ 494 // LHS => / \ ______ = _______________ 495 // _/_______\/______\_ _/_______________\_ 496 this->checkUnite({{B + 1, C}}, B, {{B, C}}); 497 this->checkUnite({{B, D}}, {A, B - 1}, {{A, D}}); 498 499 // RHS adjacent to LHS in between. 500 // RHS => ___ 501 // LHS => ___ / \ ___ = _______________ 502 // _/___\/_____\/___\_ _/_______________\_ 503 this->checkUnite({{A, MID - 1}, {MID + 1, D}}, MID, {{A, D}}); 504 this->checkUnite({{MIN, A}, {D, MAX}}, {A + 1, D - 1}, {{MIN, MAX}}); 505 506 // RHS adjacent to LHS on the outside. 507 // RHS => __ __ 508 // LHS => / \ ___ / \ = _______________ 509 // _/____\/___\/____\_ _/_______________\_ 510 this->checkUnite({{C, C}}, {{A, C - 1}, {C + 1, D}}, {{A, D}}); 511 this->checkUnite({{B, MID}}, {{A, B - 1}, {MID + 1, D}}, {{A, D}}); 512 513 // RHS wraps two subranges of LHS. 514 // RHS => ___________ 515 // LHS => / ___ ___ \ = _____________ 516 // __/_/___\_/___\_\__ __/_____________\__ 517 this->checkUnite({{B, B}, {MID, MID}, {C, C}}, {{A, D}}, {{A, D}}); 518 this->checkUnite({{A, B}, {MID, C}}, {{MIN, D}}, {{MIN, D}}); 519 520 // RHS intersects two subranges of LHS. 521 // RHS => _________ 522 // LHS => __/__ _\__ = _______________ 523 // _/_/___\____/__\_\_ _/_______________\_ 524 this->checkUnite({{MIN, B}, {C, MAX}}, {{A, D}}, {{MIN, MAX}}); 525 this->checkUnite({{A, MID}, {C, MAX}}, {{B, D}}, {{A, MAX}}); 526 527 // Multiple intersections. 528 529 // clang-format off 530 // RHS => 531 // LHS => /\ /\ = __ __ 532 // _/__\_/__\_/\_/\_/\_ _/__\_/__\_/\_/\_/\_ 533 this->checkUnite({{MID, C}, {C + 2, D - 2}, {D, MAX}}, 534 {{MIN, A}, {A + 2, B}}, 535 {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}}); 536 this->checkUnite({{B, B}, {C, C}, {MAX, MAX}}, 537 {{MIN, MIN}, {A, A}}, 538 {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}}); 539 540 // RHS => 541 // LHS => /\ /\ = __ __ 542 // _/\_/\_/\__/__\_/__\_ _/\_/\_/\_/__\_/__\_ 543 this->checkUnite({{MIN, A}, {A + 2, B}, {MID, C}}, 544 {{C + 2, D - 2}, {D, MAX}}, 545 {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}}); 546 this->checkUnite({{MIN, MIN}, {A, A}, {B, B}}, 547 {{C, C}, {MAX, MAX}}, 548 {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}}); 549 550 // RHS => 551 // LHS => _ /\ _ /\ _ /\ = 552 // _/_\_/__\_/_\_/__\_/_\_/__\_ 553 // 554 // RSLT => _ __ _ __ _ __ 555 // _/_\_/__\_/_\_/__\_/_\_/__\_ 556 this->checkUnite({{MIN, A}, {B + 2, MID}, {C + 2, D}}, 557 {{A + 2, B}, {MID + 2, C}, {D + 2, MAX}}, 558 {{MIN, A}, {A + 2, B}, {B + 2, MID}, {MID + 2, C}, {C + 2, D}, {D + 2, MAX}}); 559 this->checkUnite({{MIN, MIN}, {B, B}, {D, D}}, 560 {{A, A}, {C, C}, {MAX, MAX}}, 561 {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}}); 562 563 // RHS => 564 // LHS => /\ _ /\ _ /\ _ = 565 // _/__\_/_\_/__\_/_\_/__\_/_\_ 566 // 567 // RSLT => __ _ __ _ __ _ 568 // _/__\_/_\_/__\_/_\_/__\_/_\_ 569 this->checkUnite({{A + 2, B}, {MID + 2, C}, {D + 2, MAX}}, 570 {{MIN, A}, {B + 2, MID}, {C + 2, D}}, 571 {{MIN, A}, {A + 2, B}, {B + 2, MID}, {MID + 2, C}, {C + 2, D}, {D + 2, MAX}}); 572 this->checkUnite({{A, A}, {C, C}, {MAX, MAX}}, 573 {{MIN, MIN}, {B, B}, {D, D}}, 574 {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}}); 575 576 // RHS => _ __ _ 577 // LHS => /_\ /_ \ _ / \ = ___ ____________ 578 // _/___\_/__\_\/_\/___\_ _/___\_/____________\_ 579 this->checkUnite({{MIN, A}, {B, C}, {D, MAX}}, 580 {{MIN, A}, {B, C - 2}, {C + 1, D - 1}}, 581 {{MIN, A}, {B, MAX}}); 582 this->checkUnite({{A, A}, {B, MID}, {D, D}}, 583 {{A, A}, {B, B}, {MID + 1, D - 1}}, 584 {{A, A}, {B, D}}); 585 586 // RHS => ___ ___ 587 // LHS => /\ _/_ \_ / _ \ /\ = 588 // _/\_/__\//__\ /\\_/_/_\_\_/__\_ 589 // 590 // RSLT => ___________ _____ __ 591 // _/\_/___________\_/_____\_/__\_ 592 this->checkUnite({{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}}, 593 {{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}}, 594 {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}}); 595 // clang-format on 596 } 597