ASDenysPetrov updated this revision to Diff 358661. ASDenysPetrov added a comment.
Rebased CHANGES SINCE LAST ACTION https://reviews.llvm.org/D103094/new/ https://reviews.llvm.org/D103094 Files: clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h 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 @@ -40,12 +40,18 @@ const Range &R) { return OS << toString(R); } +LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS, + APSIntType Ty) { + return OS << (Ty.isUnsigned() ? "u" : "s") << Ty.getBitWidth(); +} } // namespace ento } // namespace clang namespace { +template <class T> constexpr bool is_signed_v = std::is_signed<T>::value; + template <typename T> struct TestValues { static constexpr T MIN = std::numeric_limits<T>::min(); static constexpr T MAX = std::numeric_limits<T>::max(); @@ -53,7 +59,7 @@ // 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)); + is_signed_v<T> ? 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; @@ -61,6 +67,34 @@ static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, "Values shall be in an ascending order"); + // Clear bits in low bytes by the given amount. + template <T Value, size_t Bytes> + static const T ClearLowBytes = static_cast<T>(static_cast<uint64_t>(Value) + << ((Bytes >= 8) ? 0 : Bytes) * + 8); + + template <T Value, typename Base> + static constexpr T TruncZeroOf = ClearLowBytes<Value + 1, sizeof(Base)>; + + // Random number with active bits in every byte. 0xAAAA'AAAA + static constexpr T XAAA = static_cast<T>( + 0b10101010'10101010'10101010'10101010'10101010'10101010'10101010'10101010); + template <typename Base> + static constexpr T XAAATruncZeroOf = TruncZeroOf<XAAA, Base>; // 0xAAAA'AB00 + + // Random number with active bits in every byte. 0x5555'5555 + static constexpr T X555 = static_cast<T>( + 0b01010101'01010101'01010101'01010101'01010101'01010101'01010101'01010101); + template <typename Base> + static constexpr T X555TruncZeroOf = TruncZeroOf<X555, Base>; // 0x5555'5600 + + // Numbers for ranges with the same bits in the lowest byte. + // 0xAAAA'AA2A + static constexpr T FromA = ClearLowBytes<XAAA, sizeof(T) - 1> + 42; + static constexpr T ToA = FromA + 2; // 0xAAAA'AA2C + // 0x5555'552A + static constexpr T FromB = ClearLowBytes<X555, sizeof(T) - 1> + 42; + static constexpr T ToB = FromB + 2; // 0x5555'552C }; template <typename BaseType> class RangeSetTest : public testing::Test { @@ -74,21 +108,27 @@ // End init block using Self = RangeSetTest<BaseType>; - using RawRange = std::pair<BaseType, BaseType>; - using RawRangeSet = std::initializer_list<RawRange>; - - const llvm::APSInt &from(BaseType X) { - static llvm::APSInt Base{sizeof(BaseType) * 8, - std::is_unsigned<BaseType>::value}; - Base = X; - return BVF.getValue(Base); + template <typename T> using RawRangeT = std::pair<T, T>; + template <typename T> + using RawRangeSetT = std::initializer_list<RawRangeT<T>>; + using RawRange = RawRangeT<BaseType>; + using RawRangeSet = RawRangeSetT<BaseType>; + template <typename T> + static constexpr APSIntType APSIntTy = APSIntType(sizeof(T) * 8, + !is_signed_v<T>); + + template <typename T> const llvm::APSInt &from(T X) { + static llvm::APSInt Int = APSIntTy<T>.getZeroValue(); + Int = X; + return BVF.getValue(Int); } - Range from(const RawRange &Init) { + template <typename T> Range from(const RawRangeT<T> &Init) { return Range(from(Init.first), from(Init.second)); } - RangeSet from(const RawRangeSet &Init) { + template <typename T> + RangeSet from(RawRangeSetT<T> Init, APSIntType Ty = APSIntTy<BaseType>) { RangeSet RangeSet = F.getEmptySet(); for (const auto &Raw : Init) { RangeSet = F.add(RangeSet, from(Raw)); @@ -211,9 +251,20 @@ RawRangeSet RawExpected) { wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected); } -}; -} // namespace + void checkCastToImpl(RangeSet What, APSIntType Ty, RangeSet Expected) { + RangeSet Result = F.castTo(What, Ty); + EXPECT_EQ(Result, Expected) + << "while casting " << toString(What) << " to " << Ty; + } + + template <typename From, typename To> + void checkCastTo(RawRangeSetT<From> What, RawRangeSetT<To> Expected) { + static constexpr APSIntType FromTy = APSIntTy<From>; + static constexpr APSIntType ToTy = APSIntTy<To>; + this->checkCastToImpl(from(What, FromTy), ToTy, from(Expected, ToTy)); + } +}; using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t, uint64_t>; @@ -591,3 +642,425 @@ {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}}, {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}}); } + +template <typename From, typename To> struct CastType { + using FromType = From; + using ToType = To; +}; + +template <typename Type> +class RangeSetCastToNoopTest : public RangeSetTest<typename Type::FromType> {}; +template <typename Type> +class RangeSetCastToPromotionTest + : public RangeSetTest<typename Type::FromType> {}; +template <typename Type> +class RangeSetCastToTruncationTest + : public RangeSetTest<typename Type::FromType> {}; +template <typename Type> +class RangeSetCastToConversionTest + : public RangeSetTest<typename Type::FromType> {}; +template <typename Type> +class RangeSetCastToPromotionConversionTest + : public RangeSetTest<typename Type::FromType> {}; +template <typename Type> +class RangeSetCastToTruncationConversionTest + : public RangeSetTest<typename Type::FromType> {}; + +using NoopCastTypes = + ::testing::Types<CastType<int8_t, int8_t>, CastType<uint8_t, uint8_t>, + CastType<int16_t, int16_t>, CastType<uint16_t, uint16_t>, + CastType<int32_t, int32_t>, CastType<uint32_t, uint32_t>, + CastType<int64_t, int64_t>, CastType<uint64_t, uint64_t>>; + +using PromotionCastTypes = + ::testing::Types<CastType<int8_t, int16_t>, CastType<int8_t, int32_t>, + CastType<int8_t, int64_t>, CastType<uint8_t, uint16_t>, + CastType<uint8_t, uint32_t>, CastType<uint8_t, uint64_t>, + CastType<int16_t, int32_t>, CastType<int16_t, int64_t>, + CastType<uint16_t, uint32_t>, CastType<uint16_t, uint64_t>, + CastType<int32_t, int64_t>, CastType<uint32_t, uint64_t>>; + +using TruncationCastTypes = + ::testing::Types<CastType<int16_t, int8_t>, CastType<uint16_t, uint8_t>, + CastType<int32_t, int16_t>, CastType<int32_t, int8_t>, + CastType<uint32_t, uint16_t>, CastType<uint32_t, uint8_t>, + CastType<int64_t, int32_t>, CastType<int64_t, int16_t>, + CastType<int64_t, int8_t>, CastType<uint64_t, uint32_t>, + CastType<uint64_t, uint16_t>, CastType<uint64_t, uint8_t>>; + +using ConversionCastTypes = + ::testing::Types<CastType<int8_t, uint8_t>, CastType<uint8_t, int8_t>, + CastType<int16_t, uint16_t>, CastType<uint16_t, int16_t>, + CastType<int32_t, uint32_t>, CastType<uint32_t, int32_t>, + CastType<int64_t, uint64_t>, CastType<uint64_t, int64_t>>; + +using PromotionConversionCastTypes = + ::testing::Types<CastType<int8_t, uint16_t>, CastType<int8_t, uint32_t>, + CastType<int8_t, uint64_t>, CastType<uint8_t, int16_t>, + CastType<uint8_t, int32_t>, CastType<uint8_t, int64_t>, + CastType<int16_t, uint32_t>, CastType<int16_t, uint64_t>, + CastType<uint16_t, int32_t>, CastType<uint16_t, int64_t>, + CastType<int32_t, uint64_t>, CastType<uint32_t, int64_t>>; + +using TruncationConversionCastTypes = + ::testing::Types<CastType<int16_t, uint8_t>, CastType<uint16_t, int8_t>, + CastType<int32_t, uint16_t>, CastType<int32_t, uint8_t>, + CastType<uint32_t, int16_t>, CastType<uint32_t, int8_t>, + CastType<int64_t, uint32_t>, CastType<int64_t, uint16_t>, + CastType<int64_t, uint8_t>, CastType<uint64_t, int32_t>, + CastType<uint64_t, int16_t>, CastType<uint64_t, int8_t>>; + +TYPED_TEST_SUITE(RangeSetCastToNoopTest, NoopCastTypes); +TYPED_TEST_SUITE(RangeSetCastToPromotionTest, PromotionCastTypes); +TYPED_TEST_SUITE(RangeSetCastToTruncationTest, TruncationCastTypes); +TYPED_TEST_SUITE(RangeSetCastToConversionTest, ConversionCastTypes); +TYPED_TEST_SUITE(RangeSetCastToPromotionConversionTest, + PromotionConversionCastTypes); +TYPED_TEST_SUITE(RangeSetCastToTruncationConversionTest, + TruncationConversionCastTypes); + +TYPED_TEST(RangeSetCastToNoopTest, RangeSetCastToNoopTest) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<T>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, + {{MIN, MIN}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + // One range + this->template checkCastTo<F, T>({{MIN, MAX}}, {{MIN, MAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{MIN, MID}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{MID, MAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{B, MAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{C, MAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{MIN, C}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{MIN, B}}); + this->template checkCastTo<F, T>({{B, C}}, {{B, C}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, {{B, MID}, {C, MAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{MIN, B}, {MID, C}}); +} + +TYPED_TEST(RangeSetCastToPromotionTest, Test) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<F>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, + {{MIN, MIN}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + // One range + this->template checkCastTo<F, T>({{MIN, MAX}}, {{MIN, MAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{MIN, MID}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{MID, MAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{B, MAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{C, MAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{MIN, C}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{MIN, B}}); + this->template checkCastTo<F, T>({{B, C}}, {{B, C}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, {{B, MID}, {C, MAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{MIN, B}, {MID, C}}); +} + +TYPED_TEST(RangeSetCastToTruncationTest, Test) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<F>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + // Use `if constexpr` here. + if (is_signed_v<F>) { + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, {{MAX, MIN}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, {{MAX, MID}}); + } else { + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, + {{MIN, MIN}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + } + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + // One range + constexpr auto ToMIN = TestValues<T>::MIN; + constexpr auto ToMAX = TestValues<T>::MAX; + this->template checkCastTo<F, T>({{MIN, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, C}}, {{ToMIN, ToMAX}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{ToMIN, ToMAX}}); + constexpr auto XAAA = TV::XAAA; + constexpr auto X555 = TV::X555; + constexpr auto ZA = TV::template XAAATruncZeroOf<T>; + constexpr auto Z5 = TV::template X555TruncZeroOf<T>; + this->template checkCastTo<F, T>({{XAAA, ZA}, {X555, Z5}}, + {{ToMIN, 0}, {X555, ToMAX}}); + // Use `if constexpr` here. + if (is_signed_v<F>) { + // One range + this->template checkCastTo<F, T>({{XAAA, ZA}}, {{XAAA, 0}}); + // Two ranges + this->template checkCastTo<F, T>({{XAAA, ZA}, {1, 42}}, {{XAAA, 42}}); + } else { + // One range + this->template checkCastTo<F, T>({{XAAA, ZA}}, {{0, 0}, {XAAA, ToMAX}}); + // Two ranges + this->template checkCastTo<F, T>({{1, 42}, {XAAA, ZA}}, + {{0, 42}, {XAAA, ToMAX}}); + } + constexpr auto FromA = TV::FromA; + constexpr auto ToA = TV::ToA; + constexpr auto FromB = TV::FromB; + constexpr auto ToB = TV::ToB; + this->template checkCastTo<F, T>({{FromA, ToA}, {FromB, ToB}}, + {{FromA, ToA}}); +} + +TYPED_TEST(RangeSetCastToConversionTest, Test) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<F>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, {{MAX, MIN}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + // One range + constexpr auto ToMIN = TestValues<T>::MIN; + constexpr auto ToMAX = TestValues<T>::MAX; + this->template checkCastTo<F, T>({{MIN, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, + {{ToMIN, ToMIN}, {MIN, ToMAX}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{MID, MAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{ToMIN, MAX}, {B, ToMAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{C, MAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{ToMIN, C}, {MIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{MIN, B}}); + this->template checkCastTo<F, T>({{B, C}}, {{ToMIN, C}, {B, ToMAX}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, {{C, B}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, + {{MID, MID}, {C, MAX}, {B, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{MID, C}, {MIN, B}}); +} + +TYPED_TEST(RangeSetCastToPromotionConversionTest, Test) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<F>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, + {{MAX, MAX}, {MIN, MIN}}); + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + + // Use `if constexpr` here. + if (is_signed_v<F>) { + // One range + this->template checkCastTo<F, T>({{MIN, MAX}}, {{0, MAX}, {MIN, -1}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{0, 0}, {MIN, -1}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{0, MAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{0, MAX}, {B, -1}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{C, MAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{0, C}, {MIN, -1}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{MIN, B}}); + this->template checkCastTo<F, T>({{B, C}}, {{0, C}, {B, -1}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, + {{C, MAX}, {MIN, B}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, + {{0, 0}, {C, MAX}, {B, -1}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{0, C}, {MIN, B}}); + } else { + // One range + this->template checkCastTo<F, T>({{MIN, MAX}}, {{MIN, MAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{MIN, MID}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{MID, MAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{B, MAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{C, MAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{MIN, C}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{MIN, B}}); + this->template checkCastTo<F, T>({{B, C}}, {{B, C}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, + {{MIN, B}, {C, MAX}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, + {{B, MID}, {C, MAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, + {{MIN, B}, {MID, C}}); + } +} + +TYPED_TEST(RangeSetCastToTruncationConversionTest, Test) { + // Just to reduce the verbosity. + using F = typename TypeParam::FromType; // From + using T = typename TypeParam::ToType; // To + + using TV = TestValues<F>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + constexpr auto B = TV::B; + constexpr auto C = TV::C; + // One point + this->template checkCastTo<F, T>({{MIN, MIN}}, {{MIN, MIN}}); + this->template checkCastTo<F, T>({{MAX, MAX}}, {{MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}}, {{MID, MID}}); + this->template checkCastTo<F, T>({{B, B}}, {{B, B}}); + this->template checkCastTo<F, T>({{C, C}}, {{C, C}}); + // Two points + // Use `if constexpr` here. + if (is_signed_v<F>) { + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, + {{MIN, MIN}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, + {{MID, MID}, {MAX, MAX}}); + } else { + this->template checkCastTo<F, T>({{MIN, MIN}, {MAX, MAX}}, {{MAX, MIN}}); + this->template checkCastTo<F, T>({{MID, MID}, {MAX, MAX}}, {{MAX, MIN}}); + } + this->template checkCastTo<F, T>({{MIN, MIN}, {B, B}}, {{MIN, MIN}, {B, B}}); + this->template checkCastTo<F, T>({{C, C}, {MAX, MAX}}, {{C, C}, {MAX, MAX}}); + this->template checkCastTo<F, T>({{MID, MID}, {C, C}}, {{MID, MID}, {C, C}}); + this->template checkCastTo<F, T>({{B, B}, {MID, MID}}, {{B, B}, {MID, MID}}); + this->template checkCastTo<F, T>({{B, B}, {C, C}}, {{B, B}, {C, C}}); + // One range + constexpr auto ToMIN = TestValues<T>::MIN; + constexpr auto ToMAX = TestValues<T>::MAX; + this->template checkCastTo<F, T>({{MIN, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, MID}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MID, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, C}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, C}}, {{ToMIN, ToMAX}}); + // Two ranges + this->template checkCastTo<F, T>({{MIN, B}, {C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{B, MID}, {C, MAX}}, {{ToMIN, ToMAX}}); + this->template checkCastTo<F, T>({{MIN, B}, {MID, C}}, {{ToMIN, ToMAX}}); + constexpr auto XAAA = TV::XAAA; + constexpr auto X555 = TV::X555; + constexpr auto ZA = TV::template XAAATruncZeroOf<T>; + constexpr auto Z5 = TV::template X555TruncZeroOf<T>; + this->template checkCastTo<F, T>({{XAAA, ZA}, {X555, Z5}}, + {{ToMIN, 0}, {X555, ToMAX}}); + // Use `if constexpr` here. + if (is_signed_v<F>) { + // One range + this->template checkCastTo<F, T>({{XAAA, ZA}}, {{0, 0}, {XAAA, ToMAX}}); + // Two ranges + this->template checkCastTo<F, T>({{XAAA, ZA}, {1, 42}}, + {{0, 42}, {XAAA, ToMAX}}); + } else { + // One range + this->template checkCastTo<F, T>({{XAAA, ZA}}, {{XAAA, 0}}); + // Two ranges + this->template checkCastTo<F, T>({{1, 42}, {XAAA, ZA}}, {{XAAA, 42}}); + } + constexpr auto FromA = TV::FromA; + constexpr auto ToA = TV::ToA; + constexpr auto FromB = TV::FromB; + constexpr auto ToB = TV::ToB; + this->template checkCastTo<F, T>({{FromA, ToA}, {FromB, ToB}}, + {{FromA, ToA}}); +} + +} // namespace Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -296,6 +296,21 @@ return std::prev(end())->To(); } +bool clang::ento::RangeSet::isUnsigned() const { + assert(!isEmpty()); + return begin()->From().isUnsigned(); +} + +uint32_t clang::ento::RangeSet::getBitWidth() const { + assert(!isEmpty()); + return begin()->From().getBitWidth(); +} + +APSIntType clang::ento::RangeSet::getAPSIntType() const { + assert(!isEmpty()); + return APSIntType(begin()->From()); +} + bool RangeSet::containsImpl(llvm::APSInt &Point) const { if (isEmpty() || !pin(Point)) return false; @@ -603,6 +618,163 @@ return makePersistent(std::move(Result)); } +// Convert range set to the given integral type using truncation and promotion. +// This works similar to APSIntType::apply function but for the range set. +RangeSet RangeSet::Factory::castTo(RangeSet What, APSIntType Ty) { + // Set is empty or NOOP (aka cast to the same type). + if (What.isEmpty() || What.getAPSIntType() == Ty) + return What; + + const bool IsConversion = What.isUnsigned() != Ty.isUnsigned(); + const bool IsTruncation = What.getBitWidth() > Ty.getBitWidth(); + const bool IsPromotion = What.getBitWidth() < Ty.getBitWidth(); + + if (IsTruncation) + return makePersistent(truncateTo(What, Ty)); + + if (IsConversion && (!IsPromotion || !What.isUnsigned())) + return makePersistent(convertTo(What, Ty)); + + // Promotion from unsigneds to signeds/unsigneds left. + + using llvm::APInt; + using llvm::APSInt; + ContainerType Result; + // We definitely know the size of the result set. + Result.reserve(What.size()); + + // Each unsigned value fits every larger type without any changes, + // whether the larger type is signed or unsigned. So just promote and push + // back each range one by one. + for (const Range &R : What) { + // Get bounds of the given range. + APSInt FromInt = R.From(); + APSInt ToInt = R.To(); + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + Result.emplace_back(ValueFactory.getValue(FromInt), + ValueFactory.getValue(ToInt)); + } + return makePersistent(std::move(Result)); +} + +RangeSet RangeSet::Factory::castTo(RangeSet What, QualType T) { + assert(T->isIntegralOrEnumerationType() && "T shall be an integral type."); + return castTo(What, ValueFactory.getAPSIntType(T)); +} + +RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What, + APSIntType Ty) { + using llvm::APInt; + using llvm::APSInt; + ContainerType Result; + ContainerType Dummy; + // CastRangeSize is an amount of all possible values of cast type. + // Example: `char` has 256 values; `short` has 65536 values. + // But in fact we use `amount of values` - 1, because + // we can't keep `amount of values of UINT64` inside uint64_t. + // E.g. 256 is an amount of all possible values of `char` and we can't keep + // it inside `char`. + // And it's OK, it's enough to do correct calculations. + uint64_t CastRangeSize = APInt::getMaxValue(Ty.getBitWidth()).getZExtValue(); + for (const Range &R : What) { + // Get bounds of the given range. + APSInt FromInt = R.From(); + APSInt ToInt = R.To(); + // CurrentRangeSize is an amount of all possible values of the current + // range minus one. + uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue(); + // This is an optimization for specific case when we are enough to cover + // the whole range. + Dummy.clear(); + if (CurrentRangeSize >= CastRangeSize) { + Dummy.emplace_back(ValueFactory.getMinValue(Ty), + ValueFactory.getMaxValue(Ty)); + Result = std::move(Dummy); + break; + } + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + const APSInt &PersistentFrom = ValueFactory.getValue(FromInt); + const APSInt &PersistentTo = ValueFactory.getValue(ToInt); + if (FromInt > ToInt) { + Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo); + Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty)); + } else + Dummy.emplace_back(PersistentFrom, PersistentTo); + // Every range retrieved after truncation potentialy has garbage values. + // So, we have to unite every next range with the previouses. + Result = unite(Result, Dummy); + } + + return Result; +} + +RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What, + APSIntType Ty) { + using llvm::APInt; + using llvm::APSInt; + using Bounds = std::pair<const APSInt &, const APSInt &>; + ContainerType Result; + ContainerType Dummy; + // Divide the cast into two phases (presented as loops here). + // First phase(loop) works when casted values go in ascending order. + // E.g. char{1,3,5,127} -> uint{1,3,5,127} + // Interrupt the first phase and go to second one when casted values start + // go in descending order. That means that we crossed over the middle of + // the type value set (aka 0 for signeds and MAX/2+1 for unsigneds). + // For instance: + // 1: uchar{1,3,5,128,255} -> char{1,3,5,-128,-1} + // Here we put {1,3,5} to one array and {-128, -1} to another + // 2: char{-128,-127,-1,0,1,2} -> uchar{128,129,255,0,1,3} + // Here we put {128,129,255} to one array and {0,1,3} to another. + // After that we unite both arrays. + // NOTE: We don't just concatenate the arrays, because they may have + // adjacent ranges, e.g.: + // 1: char(-128, 127) -> uchar -> arr1(128, 255), arr2(0, 127) -> + // unite -> uchar(0, 255) + // 2: uchar(0, 1)U(254, 255) -> char -> arr1(0, 1), arr2(-2, -1) -> + // unite -> uchar(-2, 1) + auto CastRange = [Ty, &VF = ValueFactory](const Range &R) -> Bounds { + // Get bounds of the given range. + APSInt FromInt = R.From(); + APSInt ToInt = R.To(); + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + return {VF.getValue(FromInt), VF.getValue(ToInt)}; + }; + // Phase 1. Fill the first array. + APSInt LastFromInt = Ty.getMinValue(); + const auto *It = What.begin(); + const auto *E = What.end(); + while (It != E) { + Bounds NewBounds = CastRange(*(It++)); + // If values stop going acsending order, go to the second phase(loop). + if (NewBounds.first < LastFromInt) { + Dummy.emplace_back(NewBounds.first, NewBounds.second); + break; + } + if (NewBounds.first > NewBounds.second) { + Dummy.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second); + Result.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty)); + } else + Result.emplace_back(NewBounds.first, NewBounds.second); + LastFromInt = NewBounds.first; + } + // Phase 2. Fill the second array. + while (It != E) { + Bounds NewBounds = CastRange(*(It++)); + Dummy.emplace_back(NewBounds.first, NewBounds.second); + } + // Unite both arrays. + Result = unite(Result, Dummy); + + return Result; +} + RangeSet RangeSet::Factory::deletePoint(RangeSet From, const llvm::APSInt &Point) { if (!From.contains(Point)) Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -236,6 +236,29 @@ /// Complexity: O(N) /// where N = size(What) RangeSet negate(RangeSet What); + /// Performs promotions, truncations and conversions of the given set. + /// + /// This function optimized for each of the six cast cases: + /// - noop + /// - conversion + /// - truncation + /// - truncation-conversion + /// - promotion + /// - promotion-conversion + /// + /// NOTE: This function is NOT self-inverse for truncations, because of + /// the higher bits loss: + /// - castTo(castTo(OrigRangeOfInt, char), int) != OrigRangeOfInt. + /// - castTo(castTo(OrigRangeOfChar, int), char) == OrigRangeOfChar. + /// But it is self-inverse for all the rest casts. + /// + /// Complexity: + /// - Noop O(1); + /// - Truncation O(N^2); + /// - Another case O(N); + /// where N = size(What) + RangeSet castTo(RangeSet What, APSIntType Ty); + RangeSet castTo(RangeSet What, QualType T); /// Return associated value factory. BasicValueFactory &getValueFactory() const { return ValueFactory; } @@ -251,6 +274,17 @@ /// containers are persistent (created via BasicValueFactory::getValue). ContainerType unite(const ContainerType &LHS, const ContainerType &RHS); + /// This is a helper function for `castTo` method. Implies not to be used + /// separately. + /// Performs a truncation case of a cast operation. + ContainerType truncateTo(RangeSet What, APSIntType Ty); + + /// This is a helper function for `castTo` method. Implies not to be used + /// separately. + /// Performs a conversion case and a promotion-conversion case for signeds + /// of a cast operation. + ContainerType convertTo(RangeSet What, APSIntType Ty); + // Many operations include producing new APSInt values and that's why // we need this factory. BasicValueFactory &ValueFactory; @@ -302,6 +336,10 @@ /// Complexity: O(1) const llvm::APSInt &getMaxValue() const; + bool isUnsigned() const; + uint32_t getBitWidth() const; + APSIntType getAPSIntType() const; + /// Test whether the given point is contained by any of the ranges. /// /// Complexity: O(logN) Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h @@ -21,8 +21,8 @@ bool IsUnsigned; public: - APSIntType(uint32_t Width, bool Unsigned) - : BitWidth(Width), IsUnsigned(Unsigned) {} + constexpr APSIntType(uint32_t Width, bool Unsigned) + : BitWidth(Width), IsUnsigned(Unsigned) {} /* implicit */ APSIntType(const llvm::APSInt &Value) : BitWidth(Value.getBitWidth()), IsUnsigned(Value.isUnsigned()) {}
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits