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; } 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/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::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, RawRHS, RawLHS, RawExpected); + wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected); } void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) { @@ -168,6 +171,29 @@ RawExpected); } + template + 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, RawLHS, RawRHS, RawExpected); + } + + void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS, + RawRangeSet RawExpected) { + wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected); + } + + void checkUnite(RawRangeSet RawLHS, BaseType RawRHS, + RawRangeSet RawExpected) { + wrap(&Self::checkUniteImpl, 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}}); +}