ASDenysPetrov updated this revision to Diff 335011.
ASDenysPetrov added a comment.
Updated. Restored complexity to O(N).
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D99797/new/
https://reviews.llvm.org/D99797
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
@@ -61,6 +61,9 @@
static constexpr BaseType getMax() {
return std::numeric_limits<BaseType>::max();
}
+ // MID is a value in the middle of the range
+ // which unary minus does not affect on,
+ // e.g. int8/int32(0), uint8(128), uint32(2147483648).
static constexpr BaseType getMid() {
return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
}
@@ -160,7 +163,7 @@
void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
RawRangeSet RawExpected) {
- wrap(&Self::checkAddImpl<RangeSet>, RawRHS, RawLHS, RawExpected);
+ wrap(&Self::checkAddImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
}
void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -195,9 +198,6 @@
constexpr TypeParam MIN = TestFixture::getMin();
constexpr TypeParam MAX = TestFixture::getMax();
- // MID is a value in the middle of the range
- // which unary minus does not affect on,
- // e.g. int8/int32(0), uint8(128), uint32(2147483648).
constexpr TypeParam MID = TestFixture::getMid();
constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -310,24 +310,124 @@
}
TYPED_TEST(RangeSetTest, RangeSetAddTest) {
- // Check adding single points
- this->checkAdd({}, 10, {{10, 10}});
- this->checkAdd({{0, 5}}, 10, {{0, 5}, {10, 10}});
- this->checkAdd({{0, 5}, {30, 40}}, 10, {{0, 5}, {10, 10}, {30, 40}});
-
- // Check adding single ranges.
- this->checkAdd({}, {10, 20}, {{10, 20}});
- this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}});
- this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}});
-
- // Check adding whole sets of ranges.
- this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}});
- // Check that ordering of ranges is as expected.
- this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}});
- this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}},
- {{0, 5}, {10, 20}, {30, 40}, {50, 60}});
- this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}},
- {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}});
+
+ // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+ constexpr TypeParam MIN = TestFixture::getMin();
+ constexpr TypeParam MAX = TestFixture::getMax();
+ constexpr TypeParam MID = TestFixture::getMid();
+ constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
+ constexpr TypeParam B = MID - TestFixture::fromInt(42);
+ constexpr TypeParam C = -B;
+ constexpr TypeParam D = -A;
+
+ // LHS and RHS is empty.
+ // RHS =>
+ // LHS => =
+ // ___________________ ___________________
+ this->checkAdd({}, {}, {});
+
+ // RHS is empty.
+ // RHS =>
+ // LHS => _____ = _____
+ // ______/_____\______ ______/_____\______
+ this->checkAdd({{A, B}}, {}, {{A, B}});
+ this->checkAdd({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+ // LHS is empty.
+ // RHS => ___
+ // LHS => / \ = _____
+ // ______/_____\______ ______/_____\______
+ this->checkAdd({}, B, {{B, B}});
+ this->checkAdd({}, {B, C}, {{B, C}});
+ this->checkAdd({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+ // RHS is detached from LHS.
+ // RHS => ___
+ // LHS => ___ / \ = ___ _____
+ // __/___\___/_____\__ __/___\___/_____\__
+ this->checkAdd({{A, C}}, D, {{A, C}, {D, D}});
+ this->checkAdd({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+ this->checkAdd({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+ this->checkAdd({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+ this->checkAdd({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+ this->checkAdd({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+
+ // RHS is inside LHS.
+ // RHS => ___
+ // LHS => ___/___\___ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkAdd({{A, C}}, MID, {{A, C}});
+ this->checkAdd({{A, D}}, {B, C}, {{A, D}});
+
+ // RHS wraps LHS.
+ // RHS => _________
+ // LHS => / _____ \ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkAdd({{MID, MID}}, {A, D}, {{A, D}});
+ this->checkAdd({{B, C}}, {A, D}, {{A, D}});
+ this->checkAdd({{A, B}}, {MIN, MAX}, {{MIN, MAX}});
+
+ // RHS equals to LHS.
+ // RHS => _________
+ // LHS => /_________\ = ___________
+ // ___/___________\___ ___/___________\___
+ this->checkAdd({{MID, MID}}, MID, {{MID, MID}});
+ this->checkAdd({{A, B}}, {A, B}, {{A, B}});
+ this->checkAdd({{MAX, MAX}}, {{MAX, MAX}}, {{MAX, MAX}});
+
+ // RHS intersects right of LHS.
+ // RHS => ______
+ // LHS => ___/____ \ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkAdd({{A, C}}, {B, D}, {{A, D}});
+
+ // RHS intersects left of LHS.
+ // RHS => ______
+ // LHS => / ____\___ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkAdd({{B, D}}, {A, C}, {{A, D}});
+
+ // RHS adjacent to LHS on right.
+ // RHS => _____
+ // LHS => ______ / \ = _______________
+ // _/______\/_______\_ _/_______________\_
+ this->checkAdd({{A, C}}, {C + 1, D}, {{A, D}});
+
+ // RHS adjacent to LHS on left.
+ // RHS => _____
+ // LHS => / \ ______ = _______________
+ // _/_______\/______\_ _/_______________\_
+ this->checkAdd({{B, C - 1}}, C, {{B, C}});
+ this->checkAdd({{B, D}}, {A, B - 1}, {{A, D}});
+
+ // RHS adjacent to LHS in between.
+ // RHS => ___
+ // LHS => ___ / \ ___ = _______________
+ // _/___\/_____\/___\_ _/_______________\_
+ this->checkAdd({{A, MID - 1}, {MID + 1, D}}, MID, {{A, D}});
+ this->checkAdd({{MIN, A}, {D, MAX}}, {A + 1, D - 1}, {{MIN, MAX}});
+
+ // RHS adjacent to LHS on the outside.
+ // RHS => __ __
+ // LHS => / \ ___ / \ = _______________
+ // _/____\/___\/____\_ _/_______________\_
+ this->checkAdd({{C, C}}, {{A, C - 1}, {C + 1, D}}, {{A, D}});
+ this->checkAdd({{B, MID}}, {{A, B - 1}, {MID + 1, D}}, {{A, D}});
+
+ // RHS wraps two subranges of LHS.
+ // RHS => ___________
+ // LHS => / ___ ___ \ = _____________
+ // __/_/___\_/___\_\__ __/_____________\__
+ this->checkAdd({{B, B}, {MID, MID}, {C, C}}, {{A, D}}, {{A, D}});
+ this->checkAdd({{A, B}, {MID, C}}, {{MIN, D}}, {{MIN, D}});
+
+ // RHS intersects two subranges of LHS.
+ // RHS => _________
+ // LHS => __/__ _\__ = _______________
+ // _/_/___\____/__\_\_ _/_______________\_
+ this->checkAdd({{MIN, B}, {C, MAX}}, {{A, D}}, {{MIN, MAX}});
}
TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) {
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -108,20 +108,70 @@
RangeSet::ContainerType RangeSet::Factory::EmptySet{};
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+ if (LHS.isEmpty())
+ return RHS;
+ for (const Range &R : RHS)
+ LHS = add(LHS, R);
+ return LHS;
+}
+
RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
+ return add(Original, Element.From(), Element.To());
+}
+
+RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) {
+ return add(Original, Point, Point);
+}
+
+RangeSet RangeSet::Factory::add(RangeSet Original, llvm::APSInt From,
+ llvm::APSInt To) {
ContainerType Result;
Result.reserve(Original.size() + 1);
- const_iterator Lower = llvm::lower_bound(Original, Element);
- Result.insert(Result.end(), Original.begin(), Lower);
- Result.push_back(Element);
- Result.insert(Result.end(), Lower, Original.end());
+ if (Original.isEmpty()) {
+ Result.push_back(
+ Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
+ return makePersistent(std::move(Result));
+ }
- return makePersistent(std::move(Result));
-}
+ if (!Original.pin(From, To))
+ return getEmptySet();
-RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) {
- return add(Original, Range(Point));
+ ContainerType::size_type InsertIdx = 0;
+ for (auto it = Original.begin(), e = Original.end(); it != e; ++it) {
+ const llvm::APSInt &RFrom = it->From();
+ const llvm::APSInt &RTo = it->To();
+ // Check for intersected ranges.
+ const bool IsIntersected = From <= RTo && RFrom <= To;
+ // Check for adjacent neighbor ranges.
+ bool IsAdjacent = false;
+ if (!IsIntersected) {
+ auto One = APSIntType(From).getValue(1);
+ const bool isCurrentRangeOnTheLeft = RTo < From;
+ if (isCurrentRangeOnTheLeft) {
+ IsAdjacent = (RTo == From - One);
+ if (!IsAdjacent)
+ ++InsertIdx;
+ } else // isCurrentRangeOnTheRight
+ IsAdjacent = (RFrom == To + One);
+ }
+ // Add only detached ranges.
+ const bool isDetached = (!IsIntersected && !IsAdjacent);
+ if (isDetached)
+ Result.push_back(*it);
+ else {
+ // Expand the bounds for every conjunctive range.
+ From = std::min(From, RFrom);
+ To = std::max(To, RTo);
+ }
+ }
+ // Insert a new range with expanded bounds
+ // to the specific position found in the loop.
+ Range NewRange{ValueFactory.getValue(From), ValueFactory.getValue(To)};
+ Result.insert(Result.begin() + InsertIdx, NewRange);
+
+ return makePersistent(std::move(Result));
}
RangeSet RangeSet::Factory::getRangeSet(Range From) {
@@ -153,13 +203,6 @@
return new (Buffer) ContainerType(std::move(From));
}
-RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
- ContainerType Result;
- std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
- std::back_inserter(Result));
- return makePersistent(std::move(Result));
-}
-
const llvm::APSInt &RangeSet::getMinValue() const {
assert(!isEmpty());
return begin()->From();
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
@@ -122,23 +122,29 @@
Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
/// Create a new set with all ranges from both LHS and RHS.
- /// Possible intersections are not checked here.
+ /// All intersections and adjacent ranges are handled.
///
/// Complexity: O(N + M)
/// where N = size(LHS), M = size(RHS)
RangeSet add(RangeSet LHS, RangeSet RHS);
/// Create a new set with all ranges from the original set plus the new one.
- /// Possible intersections are not checked here.
+ /// All intersections and adjacent ranges are handled.
///
/// Complexity: O(N)
/// where N = size(Original)
RangeSet add(RangeSet Original, Range Element);
/// Create a new set with all ranges from the original set plus the point.
- /// Possible intersections are not checked here.
+ /// All intersections and adjacent ranges are handled.
///
/// Complexity: O(N)
/// where N = size(Original)
RangeSet add(RangeSet Original, const llvm::APSInt &Point);
+ /// Create a new set with all ranges from the original set plus the new
+ /// one. All intersections and adjacent ranges are handled.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(Original)
+ RangeSet add(RangeSet Original, llvm::APSInt From, llvm::APSInt To);
RangeSet getEmptySet() { return &EmptySet; }
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
