ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: martong, NoQ, steakhal, balazske.
ASDenysPetrov added a project: clang.
Herald added subscribers: manas, dkrupp, donat.nagy, Szelethus,
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware, xazax.hun.
Herald added a project: All.
ASDenysPetrov requested review of this revision.
Herald added a subscriber: cfe-commits.
Add a new factory function `RangeSet::Factory::invert`. It performs an
inversion operation on the given set and produces a new one as a result. The
inversion of the set is a set containing all the values except those which are
in the original one.
NOTE: User shall guarantee that the given set is not empty.
Example:
original: `int8[0, 42]` inverse: `int8[-128, -1]U[43, 127]`;
original: `int8[-128, 127]` inverse: `int8[]`;
original: `[]` inverse: `raise an assertion`.
The motivation is to extend the set of operations that can be performed on
range sets. Specifically, this function is needed for the next patch in the
stack.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D130372
Files:
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
@@ -275,6 +275,15 @@
static constexpr APSIntType ToTy = APSIntTy<To>;
this->checkCastToImpl(from(What, FromTy), ToTy, from(Expected, ToTy));
}
+
+ void checkInvertImpl(RangeSet What, RangeSet Expected) {
+ RangeSet Result = F.invert(What);
+ EXPECT_EQ(Result, Expected) << "while inverting " << toString(What);
+ }
+
+ void checkInvert(RawRangeSet What, RawRangeSet Expected) {
+ this->checkInvertImpl(from(What), from(Expected));
+ }
};
using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
@@ -1089,4 +1098,56 @@
{{FromA, ToA}});
}
+TYPED_TEST(RangeSetTest, RangeSetInvertTest) {
+ using TV = TestValues<TypeParam>;
+ constexpr auto MIN = TV::MIN;
+ constexpr auto MAX = TV::MAX;
+ constexpr auto MID = TV::MID;
+ constexpr auto A = TV::A;
+ constexpr auto B = TV::B;
+ constexpr auto C = TV::C;
+ constexpr auto D = TV::D;
+
+ // Empty set is forbidden by the function contract.
+ // It produces an assertion.
+ /*this->checkInvert({}, ASSERTION);*/
+
+ // Check inverting single point.
+ this->checkInvert({{MIN, MIN}}, {{MIN + 1, MAX}});
+ this->checkInvert({{MAX, MAX}}, {{MIN, MAX - 1}});
+ this->checkInvert({{MID, MID}}, {{MIN, MID - 1}, {MID + 1, MAX}});
+ this->checkInvert({{A, A}}, {{MIN, A - 1}, {A + 1, MAX}});
+
+ // Check inverting two points.
+ this->checkInvert({{MIN, MIN}, {MAX, MAX}}, {{MIN + 1, MAX - 1}});
+ this->checkInvert({{MID, MID}, {MAX, MAX}},
+ {{MIN, MID - 1}, {MID + 1, MAX - 1}});
+ this->checkInvert({{MIN, MIN}, {D, D}}, {{MIN + 1, D - 1}, {D + 1, MAX}});
+ this->checkInvert({{B, B}, {C, C}},
+ {{MIN, B - 1}, {B + 1, C - 1}, {C + 1, MAX}});
+
+ // Check inverting single range.
+ this->checkInvert({{MIN, MAX}}, {});
+ this->checkInvert({{MIN, MID}}, {{MID + 1, MAX}});
+ this->checkInvert({{MID, MAX}}, {{MIN, MID - 1}});
+ this->checkInvert({{A, D}}, {{MIN, A - 1}, {D + 1, MAX}});
+
+ // Check adding two ranges.
+ this->checkInvert({{MIN, MID - 1}, {MID + 1, MAX}}, {{MID, MID}});
+ this->checkInvert({{MIN, B}, {C, D}}, {{B + 1, C - 1}, {D + 1, MAX}});
+ this->checkInvert({{MIN + 1, A}, {B, MAX}}, {{MIN, MIN}, {A + 1, B - 1}});
+ this->checkInvert({{A, B}, {C, MAX - 1}},
+ {{MIN, A - 1}, {B + 1, C - 1}, {MAX, MAX}});
+
+ // Check adding three ranges.
+ this->checkInvert({{MIN, A}, {B, C}, {D, MAX}},
+ {{A + 1, B - 1}, {C + 1, D - 1}});
+ this->checkInvert({{A, B - 1}, {B + 1, C - 1}, {C + 1, MAX}},
+ {{MIN, A - 1}, {B, B}, {C, C}});
+ this->checkInvert({{MIN, B - 1}, {B + 1, C - 1}, {C + 1, D}},
+ {{B, B}, {C, C}, {D + 1, MAX}});
+ this->checkInvert({{A, B - 1}, {C, C}, {D, D}},
+ {{MIN, A - 1}, {B, C - 1}, {C + 1, D - 1}, {D + 1, MAX}});
+}
+
} // namespace
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -611,12 +611,12 @@
if (What.isEmpty())
return getEmptySet();
- const llvm::APSInt SampleValue = What.getMinValue();
- const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
- const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
+ const APSIntType Ty = What.getAPSIntType();
+ const llvm::APSInt &MIN = ValueFactory.getMinValue(Ty);
+ const llvm::APSInt &MAX = ValueFactory.getMaxValue(Ty);
ContainerType Result;
- Result.reserve(What.size() + (SampleValue == MIN));
+ Result.reserve(What.size() + (What.getMinValue() == MIN));
// Handle a special case for MIN value.
const_iterator It = What.begin();
@@ -708,6 +708,50 @@
return castTo(What, ValueFactory.getAPSIntType(T));
}
+RangeSet RangeSet::Factory::invert(RangeSet What) {
+ assert(!What.isEmpty());
+
+ // Prepare some constants.
+ const APSIntType Ty = What.getAPSIntType();
+ const llvm::APSInt &MIN = ValueFactory.getMinValue(Ty);
+ const llvm::APSInt &MAX = ValueFactory.getMaxValue(Ty);
+
+ // Shortcut: Return an empty range set for a full range.
+ if (What.Impl->size() == 1 && What.Impl->begin()->From() == MIN &&
+ What.Impl->begin()->To() == MAX)
+ return getEmptySet();
+
+ const_iterator It = What.begin();
+ const_iterator End = What.end();
+
+ ContainerType Result;
+ Result.reserve(What.size() + 1 - bool(What.getMinValue() != MIN) -
+ bool(What.getMaxValue() != MAX));
+
+ const llvm::APSInt *From = &MIN;
+ llvm::APSInt TmpInt;
+
+ if (It->From() == MIN)
+ goto loop;
+
+ do {
+ TmpInt = It->From();
+ Result.emplace_back(*From, ValueFactory.getValue(--TmpInt));
+
+ if (It->To() == MAX)
+ return makePersistent(std::move(Result));
+
+ loop:
+
+ TmpInt = It->To();
+ From = &ValueFactory.getValue(++TmpInt);
+
+ } while (++It != End);
+
+ Result.emplace_back(*From, MAX);
+ return makePersistent(std::move(Result));
+}
+
RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What,
APSIntType Ty) {
using llvm::APInt;
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
@@ -261,6 +261,17 @@
RangeSet castTo(RangeSet What, APSIntType Ty);
RangeSet castTo(RangeSet What, QualType T);
+ /// Produce an invertion of the given set.
+ ///
+ /// Note: The given set shall not be empty.
+ ///
+ /// Examples:
+ /// - [A, B] -> [MIN, A - 1]U[B + 1, MAX]
+ /// - [MIN, A] -> [A + 1, MAX]
+ /// - [A, MAX] -> [MIN, A - 1]
+ /// - [MIN, MAX] -> Empty
+ RangeSet invert(RangeSet What);
+
/// Return associated value factory.
BasicValueFactory &getValueFactory() const { return ValueFactory; }
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
