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 "gtest/gtest.h" 15 16 namespace clang { 17 namespace ento { 18 namespace { 19 20 // TestCase contains to lists of ranges. 21 // Original one has to be negated. 22 // Expected one has to be compared to negated original range. 23 template <typename T> struct TestCase { 24 RangeSet original; 25 RangeSet expected; 26 27 TestCase(BasicValueFactory &BVF, RangeSet::Factory &F, 28 const std::initializer_list<T> &originalList, 29 const std::initializer_list<T> &expectedList) 30 : original(createRangeSetFromList(BVF, F, originalList)), 31 expected(createRangeSetFromList(BVF, F, expectedList)) {} 32 33 private: 34 RangeSet createRangeSetFromList(BasicValueFactory &BVF, RangeSet::Factory &F, 35 const std::initializer_list<T> rangeList) { 36 llvm::APSInt from(sizeof(T) * 8, std::is_unsigned<T>::value); 37 llvm::APSInt to = from; 38 RangeSet rangeSet = F.getEmptySet(); 39 for (auto it = rangeList.begin(); it != rangeList.end(); it += 2) { 40 from = *it; 41 to = *(it + 1); 42 rangeSet = rangeSet.addRange( 43 F, RangeSet(F, BVF.getValue(from), BVF.getValue(to))); 44 } 45 return rangeSet; 46 } 47 48 void printNegate(const TestCase &TestCase) { 49 TestCase.original.print(llvm::dbgs()); 50 llvm::dbgs() << " => "; 51 TestCase.expected.print(llvm::dbgs()); 52 } 53 }; 54 55 class RangeSetTest : public testing::Test { 56 protected: 57 // Init block 58 std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;"); 59 ASTContext &context = AST->getASTContext(); 60 llvm::BumpPtrAllocator alloc; 61 BasicValueFactory BVF{context, alloc}; 62 RangeSet::Factory F; 63 // End init block 64 65 template <typename T> void checkNegate() { 66 using type = T; 67 68 // Use next values of the range {MIN, A, B, MID, C, D, MAX}. 69 70 // MID is a value in the middle of the range 71 // which unary minus does not affect on, 72 // e.g. int8/int32(0), uint8(128), uint32(2147483648). 73 74 constexpr type MIN = std::numeric_limits<type>::min(); 75 constexpr type MAX = std::numeric_limits<type>::max(); 76 constexpr type MID = std::is_signed<type>::value 77 ? 0 78 : ~(static_cast<type>(-1) / static_cast<type>(2)); 79 constexpr type A = MID - static_cast<type>(42 + 42); 80 constexpr type B = MID - static_cast<type>(42); 81 constexpr type C = -B; 82 constexpr type D = -A; 83 84 static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, 85 "Values shall be in an ascending order"); 86 87 // Left {[x, y], [x, y]} is what shall be negated. 88 // Right {[x, y], [x, y]} is what shall be compared to a negation result. 89 TestCase<type> cases[] = { 90 {BVF, F, {MIN, A}, {MIN, MIN, D, MAX}}, 91 {BVF, F, {MIN, C}, {MIN, MIN, B, MAX}}, 92 {BVF, F, {MIN, MID}, {MIN, MIN, MID, MAX}}, 93 {BVF, F, {MIN, MAX}, {MIN, MAX}}, 94 {BVF, F, {A, D}, {A, D}}, 95 {BVF, F, {A, B}, {C, D}}, 96 {BVF, F, {MIN, A, D, MAX}, {MIN, A, D, MAX}}, 97 {BVF, F, {MIN, B, MID, D}, {MIN, MIN, A, MID, C, MAX}}, 98 {BVF, F, {MIN, MID, C, D}, {MIN, MIN, A, B, MID, MAX}}, 99 {BVF, F, {MIN, MID, C, MAX}, {MIN, B, MID, MAX}}, 100 {BVF, F, {A, MID, D, MAX}, {MIN + 1, A, MID, D}}, 101 {BVF, F, {A, A}, {D, D}}, 102 {BVF, F, {MID, MID}, {MID, MID}}, 103 {BVF, F, {MAX, MAX}, {MIN + 1, MIN + 1}}, 104 }; 105 106 for (const auto &c : cases) { 107 // Negate original and check with expected. 108 RangeSet negatedFromOriginal = c.original.Negate(BVF, F); 109 EXPECT_EQ(negatedFromOriginal, c.expected); 110 // Negate negated back and check with original. 111 RangeSet negatedBackward = negatedFromOriginal.Negate(BVF, F); 112 EXPECT_EQ(negatedBackward, c.original); 113 } 114 } 115 }; 116 117 TEST_F(RangeSetTest, RangeSetNegateTest) { 118 checkNegate<int8_t>(); 119 checkNegate<uint8_t>(); 120 checkNegate<int16_t>(); 121 checkNegate<uint16_t>(); 122 checkNegate<int32_t>(); 123 checkNegate<uint32_t>(); 124 checkNegate<int64_t>(); 125 checkNegate<uint64_t>(); 126 } 127 128 } // namespace 129 } // namespace ento 130 } // namespace clang 131