ASDenysPetrov updated this revision to Diff 388512.
ASDenysPetrov added a comment.
Fixed missed part during rebasing in the unit test.
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,8 +67,40 @@
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 constexpr T ClearLowBytes =
+ static_cast<T>(static_cast<uint64_t>(Value)
+ << ((Bytes >= CHAR_BIT) ? 0 : Bytes) * CHAR_BIT);
+
+ 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 T>
+static constexpr APSIntType APSIntTy = APSIntType(sizeof(T) * CHAR_BIT,
+ !is_signed_v<T>);
+
template <typename BaseType> class RangeSetTest : public testing::Test {
public:
// Init block
@@ -74,21 +112,24 @@
// 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) * CHAR_BIT,
- 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> 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 +252,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 +643,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
@@ -353,6 +353,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;
@@ -655,6 +670,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
@@ -237,6 +237,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; }
@@ -252,6 +275,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;
@@ -303,6 +337,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
