ASDenysPetrov updated this revision to Diff 448161.
ASDenysPetrov added a comment.
Make changes according to the remarks.
- Add complexity to function description.
- Rewrite the loop making it deterministic.
- Add back invert operation to the tests.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D130372/new/
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,20 @@
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);
+ // Do invert back, except empty range because it is not permitted.
+ if (Result.isEmpty())
+ return;
+ RangeSet BackResult = F.invert(Result);
+ EXPECT_EQ(BackResult, What) << "while inverting " << toString(Result);
+ }
+
+ 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 +1103,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,46 @@
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);
+ const bool NoMin = What.getMinValue() != MIN;
+ const bool NoMax = What.getMaxValue() != MAX;
+
+ // Shortcut: Return an empty range set for a full range.
+ if (What.size() == 1 && !NoMin && !NoMax)
+ return getEmptySet();
+
+ const_iterator It = What.begin();
+ ContainerType Result;
+ Result.reserve(What.size() - 1 + NoMin + NoMax);
+
+ auto Inc = [&](llvm::APSInt I) -> const llvm::APSInt & {
+ return ValueFactory.getValue(++I);
+ };
+ auto Dec = [&](llvm::APSInt I) -> const llvm::APSInt & {
+ return ValueFactory.getValue(--I);
+ };
+
+ if (NoMin)
+ Result.emplace_back(MIN, Dec(It->From()));
+
+ for (size_t i = 0; i < What.size() - 1; ++i) {
+ const llvm::APSInt &NewFrom = Inc(It->To());
+ ++It;
+ Result.emplace_back(NewFrom, Dec(It->From()));
+ }
+
+ if (NoMax)
+ Result.emplace_back(Inc(It->To()), 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,20 @@
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
+ ///
+ /// Complexity: O(N)
+ /// where N = size(What)
+ 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
