ASDenysPetrov updated this revision to Diff 335768.
ASDenysPetrov retitled this revision from "[analyzer] Handle intersections and
adjacency in RangeSet::Factory::add function" to "[analyzer] Implemented
RangeSet::Factory::unite function to handle intersections and adjacency".
ASDenysPetrov added a comment.
Updated. Implemented four separate functions `RangeSet::Factory::unite`. Each
function has the most optimized approach to handle intersections for the
particular case.
@vsavchenko You are welcome to evaluate this changes.
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) {
@@ -168,6 +171,29 @@
RawExpected);
}
+ template <class RHSType>
+ void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+ RangeSet Result = F.unite(LHS, RHS);
+ EXPECT_EQ(Result, Expected)
+ << "while uniting " << toString(LHS) << " and " << toString(RHS);
+ }
+
+ void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkUniteImpl<Range>, RawLHS, RawRHS, RawExpected);
+ }
+
+ void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkUniteImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
+ }
+
+ void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkUniteImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+ RawExpected);
+ }
+
void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,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);
@@ -347,3 +370,128 @@
// Check that delete of the point not from the range set works as expected.
this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}});
}
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+ // 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->checkUnite({}, {}, {});
+
+ // RHS is empty.
+ // RHS =>
+ // LHS => _____ = _____
+ // ______/_____\______ ______/_____\______
+ this->checkUnite({{A, B}}, {}, {{A, B}});
+ this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+ // LHS is empty.
+ // RHS => ___
+ // LHS => / \ = _____
+ // ______/_____\______ ______/_____\______
+ this->checkUnite({}, B, {{B, B}});
+ this->checkUnite({}, {B, C}, {{B, C}});
+ this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+ // RHS is detached from LHS.
+ // RHS => ___
+ // LHS => ___ / \ = ___ _____
+ // __/___\___/_____\__ __/___\___/_____\__
+ this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+ this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+ this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+ this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+ this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+ this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+ {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+
+ // RHS is inside LHS.
+ // RHS => ___
+ // LHS => ___/___\___ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkUnite({{A, C}}, MID, {{A, C}});
+ this->checkUnite({{A, D}}, {B, C}, {{A, D}});
+
+ // RHS wraps LHS.
+ // RHS => _________
+ // LHS => / _____ \ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkUnite({{MID, MID}}, {A, D}, {{A, D}});
+ this->checkUnite({{B, C}}, {A, D}, {{A, D}});
+ this->checkUnite({{A, B}}, {MIN, MAX}, {{MIN, MAX}});
+
+ // RHS equals to LHS.
+ // RHS => _________
+ // LHS => /_________\ = ___________
+ // ___/___________\___ ___/___________\___
+ this->checkUnite({{MIN, MIN}}, MIN, {{MIN, MIN}});
+ this->checkUnite({{A, B}}, {A, B}, {{A, B}});
+ this->checkUnite({{MAX, MAX}}, {{MAX, MAX}}, {{MAX, MAX}});
+ this->checkUnite({{MIN, MIN}}, {{MIN, MIN}}, {{MIN, MIN}});
+
+ // RHS intersects right of LHS.
+ // RHS => ______
+ // LHS => ___/____ \ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkUnite({{A, C}}, C, {{A, C}});
+ this->checkUnite({{A, C}}, {B, D}, {{A, D}});
+
+ // RHS intersects left of LHS.
+ // RHS => ______
+ // LHS => / ____\___ = ___________
+ // ___/__/_____\__\___ ___/___________\___
+ this->checkUnite({{B, D}}, B, {{B, D}});
+ this->checkUnite({{B, D}}, {A, C}, {{A, D}});
+
+ // RHS adjacent to LHS on right.
+ // RHS => _____
+ // LHS => ______ / \ = _______________
+ // _/______\/_______\_ _/_______________\_
+ this->checkUnite({{A, B - 1}}, B, {{A, B}});
+ this->checkUnite({{A, C}}, {C + 1, D}, {{A, D}});
+
+ // RHS adjacent to LHS on left.
+ // RHS => _____
+ // LHS => / \ ______ = _______________
+ // _/_______\/______\_ _/_______________\_
+ this->checkUnite({{B + 1, C}}, B, {{B, C}});
+ this->checkUnite({{B, D}}, {A, B - 1}, {{A, D}});
+
+ // RHS adjacent to LHS in between.
+ // RHS => ___
+ // LHS => ___ / \ ___ = _______________
+ // _/___\/_____\/___\_ _/_______________\_
+ this->checkUnite({{A, MID - 1}, {MID + 1, D}}, MID, {{A, D}});
+ this->checkUnite({{MIN, A}, {D, MAX}}, {A + 1, D - 1}, {{MIN, MAX}});
+
+ // RHS adjacent to LHS on the outside.
+ // RHS => __ __
+ // LHS => / \ ___ / \ = _______________
+ // _/____\/___\/____\_ _/_______________\_
+ this->checkUnite({{C, C}}, {{A, C - 1}, {C + 1, D}}, {{A, D}});
+ this->checkUnite({{B, MID}}, {{A, B - 1}, {MID + 1, D}}, {{A, D}});
+
+ // RHS wraps two subranges of LHS.
+ // RHS => ___________
+ // LHS => / ___ ___ \ = _____________
+ // __/_/___\_/___\_\__ __/_____________\__
+ this->checkUnite({{B, B}, {MID, MID}, {C, C}}, {{A, D}}, {{A, D}});
+ this->checkUnite({{A, B}, {MID, C}}, {{MIN, D}}, {{MIN, D}});
+
+ // RHS intersects two subranges of LHS.
+ // RHS => _________
+ // LHS => __/__ _\__ = _______________
+ // _/_/___\____/__\_\_ _/_______________\_
+ this->checkUnite({{MIN, B}, {C, MAX}}, {{A, D}}, {{MIN, MAX}});
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -108,6 +108,13 @@
RangeSet::ContainerType RangeSet::Factory::EmptySet{};
+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));
+}
+
RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
ContainerType Result;
Result.reserve(Original.size() + 1);
@@ -124,6 +131,210 @@
return add(Original, Range(Point));
}
+static bool pin(APSIntType Type, llvm::APSInt &Lower, llvm::APSInt &Upper);
+
+RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) {
+ if (LHS.isEmpty())
+ return RHS;
+ if (RHS.isEmpty())
+ return LHS;
+
+ using llvm::APSInt;
+
+ /// @class RangeBoundIterator is a helper class for iterating through the
+ /// bounds of every Range from the RangeSet. It points to one of the range
+ /// values (`From`, `To`).
+ /// Incrementation uses RangeSet::const_iterator to pass from one bound to
+ /// another. RangeSet iterator increments if reaches the upper bound.
+ /// Example:
+ /// RangeSet RS{Range1, Range2, ... RangeN}
+ /// RangeBoundIterator it{RS};
+ /// ++it; // Range1->From()
+ /// ++it; // Range1->To()
+ /// ++it; // Range2->From()
+ /// ++it; // Range2->To()
+ /// ...
+ ///
+ class RangeBoundIterator {
+ public:
+ RangeBoundIterator(RangeSet &RS)
+ : RIt(RS.begin()), REnd(RS.end()), PinTy(RIt->From()) {}
+ RangeBoundIterator(RangeSet &RS, APSIntType PinTy, BasicValueFactory &BV)
+ : RIt(RS.begin()), REnd(RS.end()), PinTy(PinTy), BV(&BV) {
+ handlePin();
+ }
+ bool isFrom() const { return !operator bool() || IsFrom; }
+ bool isTo() const { return !IsFrom; }
+ operator bool() const { return RIt != REnd; }
+ void operator++() {
+ if (isTo()) {
+ ++RIt;
+ handlePin();
+ }
+ IsFrom = !IsFrom;
+ }
+ const APSInt &operator*() const {
+ if (IsPinned)
+ return IsFrom ? BV->getValue(From) : BV->getValue(To);
+ else
+ return IsFrom ? RIt->From() : RIt->To();
+ }
+
+ private:
+ // This function adjust each Range to the given type.
+ // Namely, The RHS ranges shall be adjusted to the type of LHS set.
+ void handlePin() {
+ if (!BV || !operator bool() || PinTy == APSIntType(RIt->From()))
+ return;
+ From = RIt->From();
+ To = RIt->To();
+ while (!::pin(PinTy, From, To)) {
+ ++RIt;
+ if (!operator bool())
+ break;
+ From = RIt->From();
+ To = RIt->To();
+ }
+ IsPinned = true;
+ }
+
+ private:
+ RangeSet::const_iterator RIt, REnd;
+ APSInt From, To;
+ APSIntType PinTy;
+ BasicValueFactory *BV = nullptr;
+ bool IsFrom = true;
+ bool IsPinned = false;
+ };
+
+ RangeBoundIterator BIt1{LHS};
+ RangeBoundIterator BIt2{RHS, APSIntType(LHS.getMinValue()), ValueFactory};
+ const APSInt *From = nullptr;
+ const APSInt One = APSIntType(*BIt1).getValue(1);
+
+ ContainerType Result;
+
+ while (BIt1 || BIt2) {
+
+ // Swap iterators if:
+ // 1. BIt1 is null
+ // 2. BI1(Value) > BI2(Value) except when BI1(From) adjacent to BI2(To).
+ // BI1[(3), 4] and BI2[1, (2)]
+ // 3. BI1->To adjacent to BI2->From.
+ // BI1[1, (2)] and BI2[(3), 4]
+ // 4. BI1->To equal to BI2->From.
+ // BI1[1, (2)] and BI2[(2), 4]
+ bool needSwap = false;
+ if (!BIt1)
+ needSwap = true; // case 1
+ else if (BIt2) {
+ const APSInt &Int1 = *BIt1;
+ const APSInt &Int2 = *BIt2;
+ if (Int1 > Int2) {
+ if (!(BIt1.isFrom() && BIt2.isTo() && (Int1 == (Int2 + One))))
+ needSwap = true; // case 2
+ } else if (BIt1.isTo() && BIt2.isFrom()) {
+ if ((Int1 == (Int2 - One)))
+ needSwap = true; // case 3
+ if (Int1 == Int2)
+ needSwap = true; // case 4
+ }
+ }
+ if (needSwap)
+ std::swap(BIt1, BIt2);
+
+ if (BIt2.isFrom()) {
+ if (BIt1.isFrom())
+ From = &*BIt1;
+ else
+ Result.emplace_back(*From, *BIt1);
+ }
+ ++BIt1;
+ }
+
+ return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, Range Element) {
+ if (auto Point = Element.getConcreteValue())
+ return unite(Original, *Point);
+ return unite(Original, Element.From(), Element.To());
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+ if (Original.isEmpty())
+ return getRangeSet(Range(ValueFactory.getValue(Point)));
+
+ if (!Original.pin(Point))
+ return Original;
+
+ using llvm::APSInt;
+
+ auto B = Original.begin();
+ auto E = Original.end();
+ APSIntType Ty = APSIntType(B->From());
+ const APSInt One = Ty.getValue(1);
+ const APSInt Max = Ty.getMaxValue();
+
+ auto It = std::lower_bound(
+ B, E, Range(Point), [&Max, &One](const Range &OrigR, const Range &R) {
+ return OrigR.To() != Max && (OrigR.To() + One) < R.From();
+ });
+
+ if (It != E && It->Includes(Point))
+ return Original;
+
+ ContainerType Result;
+ Result.insert(Result.end(), B, It);
+ const APSInt F = (It != E && Point > It->To()) ? (It++)->From() : Point;
+ const APSInt T = (It != E && It->From() - 1 == Point) ? (It++)->To() : Point;
+ Result.emplace_back(ValueFactory.getValue(F), ValueFactory.getValue(T));
+ Result.insert(Result.end(), It, E);
+ return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From,
+ llvm::APSInt To) {
+ if (Original.isEmpty())
+ return getRangeSet(
+ Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
+
+ if (!Original.pin(From, To))
+ return Original;
+
+ ContainerType Result;
+ Range R(ValueFactory.getValue(From), ValueFactory.getValue(To));
+
+ using llvm::APSInt;
+ auto B = Original.begin();
+ auto E = Original.end();
+ APSIntType Ty = APSIntType(B->From());
+ APSInt One = Ty.getValue(1);
+ APSInt Max = Ty.getMaxValue();
+
+ // Find a left part of disjoint ranges from the new range.
+ auto It = std::lower_bound(
+ B, E, R, [&One, &Max](const Range &OrigR, const Range &R) {
+ return OrigR.To() != Max && (OrigR.To() + One) < R.From();
+ });
+ Result.insert(Result.end(), B, It);
+
+ const APSInt &F = (It == E) ? R.From() : std::min(R.From(), It->From());
+
+ // Find a right part of disjoint ranges from the new range.
+ It = std::lower_bound(
+ It, E, R, [&One, &Max](const Range &OrigR, const Range &R) {
+ return OrigR.From() == Max || (OrigR.From() - One) <= R.To();
+ });
+
+ const APSInt &T = (It == B) ? R.To() : std::max(R.To(), (It - 1)->To());
+
+ Result.emplace_back(F, T);
+ Result.insert(Result.end(), It, E);
+
+ return makePersistent(std::move(Result));
+}
+
RangeSet RangeSet::Factory::getRangeSet(Range From) {
ContainerType Result;
Result.push_back(From);
@@ -153,13 +364,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();
@@ -182,8 +386,7 @@
return std::prev(It)->Includes(Point);
}
-bool RangeSet::pin(llvm::APSInt &Point) const {
- APSIntType Type(getMinValue());
+static bool pin(APSIntType Type, llvm::APSInt &Point) {
if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
return false;
@@ -191,13 +394,12 @@
return true;
}
-bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
+static bool pin(APSIntType Type, llvm::APSInt &Lower, llvm::APSInt &Upper) {
// This function has nine cases, the cartesian product of range-testing
// both the upper and lower bounds against the symbol's type.
// Each case requires a different pinning operation.
// The function returns false if the described range is entirely outside
// the range of values for the associated symbol.
- APSIntType Type(getMinValue());
APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
@@ -272,6 +474,14 @@
return true;
}
+bool RangeSet::pin(llvm::APSInt &Point) const {
+ return ::pin(APSIntType(getMinValue()), Point);
+}
+
+bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
+ return ::pin(APSIntType(getMinValue()), Lower, Upper);
+}
+
RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower,
llvm::APSInt Upper) {
if (What.isEmpty() || !What.pin(Lower, Upper))
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
@@ -139,6 +139,30 @@
/// Complexity: O(N)
/// where N = size(Original)
RangeSet add(RangeSet Original, const llvm::APSInt &Point);
+ /// Create a new set which is a union of two given ranges.
+ /// Possible intersections are not checked here.
+ ///
+ /// Complexity: O(N + M)
+ /// where N = size(Original)
+ RangeSet unite(RangeSet Original, RangeSet RHS);
+ /// Create a new set by uniting given range set with the given range.
+ /// All intersections and adjacent ranges are handled here.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(Original)
+ RangeSet unite(RangeSet Original, Range Element);
+ /// Create a new set by uniting given range set with the given point.
+ /// All intersections and adjacent ranges are handled here.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(Original)
+ RangeSet unite(RangeSet Original, llvm::APSInt Point);
+ /// Create a new set by uniting given range set with the given range
+ /// between points. All intersections and adjacent ranges are handled here.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(Original)
+ RangeSet unite(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
