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 Point.toString(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 39 } // namespace ento 40 } // namespace clang 41 42 namespace { 43 44 template <typename BaseType> class RangeSetTest : public testing::Test { 45 public: 46 // Init block 47 std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;"); 48 ASTContext &Context = AST->getASTContext(); 49 llvm::BumpPtrAllocator Arena; 50 BasicValueFactory BVF{Context, Arena}; 51 RangeSet::Factory F{BVF}; 52 // End init block 53 54 using Self = RangeSetTest<BaseType>; 55 using RawRange = std::pair<BaseType, BaseType>; 56 using RawRangeSet = std::initializer_list<RawRange>; 57 58 static constexpr BaseType getMin() { 59 return std::numeric_limits<BaseType>::min(); 60 } 61 static constexpr BaseType getMax() { 62 return std::numeric_limits<BaseType>::max(); 63 } 64 static constexpr BaseType getMid() { 65 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2)); 66 } 67 68 static constexpr bool isSigned() { return std::is_signed<BaseType>::value; } 69 static constexpr BaseType fromInt(int X) { return static_cast<BaseType>(X); } 70 71 static llvm::APSInt Base; 72 const llvm::APSInt &from(BaseType X) { 73 llvm::APSInt Dummy = Base; 74 Dummy = X; 75 return BVF.getValue(Dummy); 76 } 77 78 Range from(const RawRange &Init) { 79 return Range(from(Init.first), from(Init.second)); 80 } 81 82 RangeSet from(const RawRangeSet &Init) { 83 RangeSet RangeSet = F.getEmptySet(); 84 for (const auto &Raw : Init) { 85 RangeSet = F.add(RangeSet, from(Raw)); 86 } 87 return RangeSet; 88 } 89 90 template <class F, class... RawArgTypes> 91 void wrap(F ActualFunction, RawArgTypes &&... Args) { 92 (this->*ActualFunction)(from(std::forward<RawArgTypes>(Args))...); 93 } 94 95 void checkNegateImpl(RangeSet Original, RangeSet Expected) { 96 RangeSet NegatedFromOriginal = F.negate(Original); 97 EXPECT_EQ(NegatedFromOriginal, Expected); 98 // Negate negated back and check with original. 99 RangeSet NegatedBackward = F.negate(NegatedFromOriginal); 100 EXPECT_EQ(NegatedBackward, Original); 101 } 102 103 void checkNegate(RawRangeSet RawOriginal, RawRangeSet RawExpected) { 104 wrap(&Self::checkNegateImpl, RawOriginal, RawExpected); 105 } 106 107 template <class PointOrSet> 108 void checkIntersectImpl(RangeSet LHS, PointOrSet RHS, RangeSet Expected) { 109 RangeSet Result = F.intersect(LHS, RHS); 110 EXPECT_EQ(Result, Expected) 111 << "while intersecting " << toString(LHS) << " and " << toString(RHS); 112 } 113 114 void checkIntersectRangeImpl(RangeSet LHS, const llvm::APSInt &Lower, 115 const llvm::APSInt &Upper, RangeSet Expected) { 116 RangeSet Result = F.intersect(LHS, Lower, Upper); 117 EXPECT_EQ(Result, Expected) 118 << "while intersecting " << toString(LHS) << " and [" << toString(Lower) 119 << ", " << toString(Upper) << "]"; 120 } 121 122 void checkIntersect(RawRangeSet RawLHS, RawRangeSet RawRHS, 123 RawRangeSet RawExpected) { 124 wrap(&Self::checkIntersectImpl<RangeSet>, RawLHS, RawRHS, RawExpected); 125 } 126 127 void checkIntersect(RawRangeSet RawLHS, BaseType RawRHS, 128 RawRangeSet RawExpected) { 129 wrap(&Self::checkIntersectImpl<const llvm::APSInt &>, RawLHS, RawRHS, 130 RawExpected); 131 } 132 133 void checkIntersect(RawRangeSet RawLHS, BaseType RawLower, BaseType RawUpper, 134 RawRangeSet RawExpected) { 135 wrap(&Self::checkIntersectRangeImpl, RawLHS, RawLower, RawUpper, 136 RawExpected); 137 } 138 139 void checkContainsImpl(RangeSet LHS, const llvm::APSInt &RHS, bool Expected) { 140 bool Result = LHS.contains(RHS); 141 EXPECT_EQ(Result, Expected) 142 << toString(LHS) << (Result ? " contains " : " doesn't contain ") 143 << toString(RHS); 144 } 145 146 void checkContains(RawRangeSet RawLHS, BaseType RawRHS, bool Expected) { 147 checkContainsImpl(from(RawLHS), from(RawRHS), Expected); 148 } 149 150 template <class RHSType> 151 void checkAddImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) { 152 RangeSet Result = F.add(LHS, RHS); 153 EXPECT_EQ(Result, Expected) 154 << "while adding " << toString(LHS) << " and " << toString(RHS); 155 } 156 157 void checkAdd(RawRangeSet RawLHS, RawRange RawRHS, RawRangeSet RawExpected) { 158 wrap(&Self::checkAddImpl<Range>, RawLHS, RawRHS, RawExpected); 159 } 160 161 void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS, 162 RawRangeSet RawExpected) { 163 wrap(&Self::checkAddImpl<RangeSet>, RawRHS, RawLHS, RawExpected); 164 } 165 166 void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) { 167 wrap(&Self::checkAddImpl<const llvm::APSInt &>, RawLHS, RawRHS, 168 RawExpected); 169 } 170 171 void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From, 172 RangeSet Expected) { 173 RangeSet Result = F.deletePoint(From, Point); 174 EXPECT_EQ(Result, Expected) 175 << "while deleting " << toString(Point) << " from " << toString(From); 176 } 177 178 void checkDelete(BaseType Point, RawRangeSet RawFrom, 179 RawRangeSet RawExpected) { 180 wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected); 181 } 182 }; 183 184 } // namespace 185 186 template <typename BaseType> 187 llvm::APSInt RangeSetTest<BaseType>::Base{sizeof(BaseType) * 8, !isSigned()}; 188 189 using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t, 190 uint32_t, int64_t, uint64_t>; 191 TYPED_TEST_CASE(RangeSetTest, IntTypes); 192 193 TYPED_TEST(RangeSetTest, RangeSetNegateTest) { 194 // Use next values of the range {MIN, A, B, MID, C, D, MAX}. 195 196 constexpr TypeParam MIN = TestFixture::getMin(); 197 constexpr TypeParam MAX = TestFixture::getMax(); 198 // MID is a value in the middle of the range 199 // which unary minus does not affect on, 200 // e.g. int8/int32(0), uint8(128), uint32(2147483648). 201 constexpr TypeParam MID = TestFixture::getMid(); 202 constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42); 203 constexpr TypeParam B = MID - TestFixture::fromInt(42); 204 constexpr TypeParam C = -B; 205 constexpr TypeParam D = -A; 206 207 static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, 208 "Values shall be in an ascending order"); 209 210 this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}}); 211 this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}}); 212 this->checkNegate({{MIN, MID}}, {{MIN, MIN}, {MID, MAX}}); 213 this->checkNegate({{MIN, MAX}}, {{MIN, MAX}}); 214 this->checkNegate({{A, D}}, {{A, D}}); 215 this->checkNegate({{A, B}}, {{C, D}}); 216 this->checkNegate({{MIN, A}, {D, MAX}}, {{MIN, A}, {D, MAX}}); 217 this->checkNegate({{MIN, B}, {MID, D}}, {{MIN, MIN}, {A, MID}, {C, MAX}}); 218 this->checkNegate({{MIN, MID}, {C, D}}, {{MIN, MIN}, {A, B}, {MID, MAX}}); 219 this->checkNegate({{MIN, MID}, {C, MAX}}, {{MIN, B}, {MID, MAX}}); 220 this->checkNegate({{A, MID}, {D, MAX}}, {{MIN + 1, A}, {MID, D}}); 221 this->checkNegate({{A, A}}, {{D, D}}); 222 this->checkNegate({{MID, MID}}, {{MID, MID}}); 223 this->checkNegate({{MAX, MAX}}, {{MIN + 1, MIN + 1}}); 224 } 225 226 TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) { 227 // Check that we can correctly intersect empty sets. 228 this->checkIntersect({}, 42, {}); 229 // Check that intersection with itself produces the same set. 230 this->checkIntersect({{42, 42}}, 42, {{42, 42}}); 231 // Check more general cases. 232 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 42, {}); 233 this->checkIntersect({{0, 10}, {20, 30}, {30, 60}}, 42, {{42, 42}}); 234 } 235 236 TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) { 237 constexpr TypeParam MIN = TestFixture::getMin(); 238 constexpr TypeParam MAX = TestFixture::getMax(); 239 240 // Check that we can correctly intersect empty sets. 241 this->checkIntersect({}, 10, 20, {}); 242 this->checkIntersect({}, 20, 10, {}); 243 // Check that intersection with itself produces the same set. 244 this->checkIntersect({{10, 20}}, 10, 20, {{10, 20}}); 245 this->checkIntersect({{MIN, 10}, {20, MAX}}, 20, 10, {{MIN, 10}, {20, MAX}}); 246 // Check non-overlapping range intersections. 247 this->checkIntersect({{10, 20}}, 21, 9, {}); 248 this->checkIntersect({{MIN, 9}, {21, MAX}}, 10, 20, {}); 249 // Check more general cases. 250 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 10, 35, 251 {{10, 10}, {20, 30}, {30, 35}}); 252 this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 35, 10, 253 {{0, 10}, {35, 40}, {50, 60}}); 254 } 255 256 TYPED_TEST(RangeSetTest, RangeSetGenericIntersectTest) { 257 // Check that we can correctly intersect empty sets. 258 this->checkIntersect({}, {}, {}); 259 this->checkIntersect({}, {{0, 10}}, {}); 260 this->checkIntersect({{0, 10}}, {}, {}); 261 262 this->checkIntersect({{0, 10}}, {{4, 6}}, {{4, 6}}); 263 this->checkIntersect({{0, 10}}, {{4, 20}}, {{4, 10}}); 264 // Check that intersection with points works as expected. 265 this->checkIntersect({{0, 10}}, {{4, 4}}, {{4, 4}}); 266 // All ranges are closed, check that intersection with edge points works as 267 // expected. 268 this->checkIntersect({{0, 10}}, {{10, 10}}, {{10, 10}}); 269 270 // Let's check that we can skip some intervals and partially intersect 271 // other intervals. 272 this->checkIntersect({{0, 2}, {4, 5}, {6, 9}, {10, 11}, {12, 12}, {13, 15}}, 273 {{8, 14}, {20, 30}}, 274 {{8, 9}, {10, 11}, {12, 12}, {13, 14}}); 275 // Check more generic case. 276 this->checkIntersect( 277 {{0, 1}, {2, 3}, {5, 6}, {7, 15}, {25, 30}}, 278 {{4, 10}, {11, 11}, {12, 16}, {17, 17}, {19, 20}, {21, 23}, {24, 27}}, 279 {{5, 6}, {7, 10}, {11, 11}, {12, 15}, {25, 27}}); 280 } 281 282 TYPED_TEST(RangeSetTest, RangeSetContainsTest) { 283 // Check with an empty set. 284 this->checkContains({}, 10, false); 285 // Check contains with sets of size one: 286 // * when the whole range is less 287 this->checkContains({{0, 5}}, 10, false); 288 // * when the whole range is greater 289 this->checkContains({{20, 25}}, 10, false); 290 // * when the range is just the point we are looking for 291 this->checkContains({{10, 10}}, 10, true); 292 // * when the range starts with the point 293 this->checkContains({{10, 15}}, 10, true); 294 // * when the range ends with the point 295 this->checkContains({{5, 10}}, 10, true); 296 // * when the range has the point somewhere in the middle 297 this->checkContains({{0, 25}}, 10, true); 298 // Check similar cases, but with larger sets. 299 this->checkContains({{0, 5}, {10, 10}, {15, 20}}, 10, true); 300 this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true); 301 this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true); 302 303 constexpr TypeParam MIN = TestFixture::getMin(); 304 constexpr TypeParam MAX = TestFixture::getMax(); 305 constexpr TypeParam MID = TestFixture::getMid(); 306 this->checkContains({{MIN, MAX}}, 0, true); 307 this->checkContains({{MIN, MAX}}, MID, true); 308 this->checkContains({{MIN, MAX}}, -10, true); 309 this->checkContains({{MIN, MAX}}, 10, true); 310 } 311 312 TYPED_TEST(RangeSetTest, RangeSetAddTest) { 313 // Check adding single points 314 this->checkAdd({}, 10, {{10, 10}}); 315 this->checkAdd({{0, 5}}, 10, {{0, 5}, {10, 10}}); 316 this->checkAdd({{0, 5}, {30, 40}}, 10, {{0, 5}, {10, 10}, {30, 40}}); 317 318 // Check adding single ranges. 319 this->checkAdd({}, {10, 20}, {{10, 20}}); 320 this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}}); 321 this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}}); 322 323 // Check adding whole sets of ranges. 324 this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}}); 325 // Check that ordering of ranges is as expected. 326 this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}}); 327 this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}}, 328 {{0, 5}, {10, 20}, {30, 40}, {50, 60}}); 329 this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}}, 330 {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}}); 331 } 332 333 TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) { 334 constexpr TypeParam MIN = TestFixture::getMin(); 335 constexpr TypeParam MAX = TestFixture::getMax(); 336 constexpr TypeParam MID = TestFixture::getMid(); 337 338 this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}}); 339 // Check that delete works with an empty set. 340 this->checkDelete(10, {}, {}); 341 // Check that delete can remove entire ranges. 342 this->checkDelete(10, {{10, 10}}, {}); 343 this->checkDelete(10, {{0, 5}, {10, 10}, {20, 30}}, {{0, 5}, {20, 30}}); 344 // Check that delete can split existing ranges into two. 345 this->checkDelete(10, {{0, 5}, {7, 15}, {20, 30}}, 346 {{0, 5}, {7, 9}, {11, 15}, {20, 30}}); 347 // Check that delete of the point not from the range set works as expected. 348 this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}}); 349 } 350