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 @@ -110,6 +110,7 @@ public: using const_iterator = ImplType::const_iterator; + using iterator = ImplType::iterator; const_iterator begin() const { return Impl->begin(); } const_iterator end() const { return Impl->end(); } @@ -122,23 +123,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) + /// Complexity: O(N + Mlog(N)) /// 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) + /// Complexity: O(N + log(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) + /// Complexity: O(N + log(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 + log(N)) + /// where N = size(Original) + RangeSet add(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,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)); + // Copy all detached ranges and expand the bounds (From, To). + auto IsDetachedPred = [&From, &To](const Range &R) { + const llvm::APSInt &RFrom = R.From(); + const llvm::APSInt &RTo = R.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 isOnLeft = RTo < From; + if (isOnLeft) + IsAdjacent = (RTo == From - One); + else // isOnRight + IsAdjacent = (RFrom == To + One); + } + const bool isDetached = (!IsIntersected && !IsAdjacent); + // Expand the bounds for every conjunctive range. + if (!isDetached) { + From = std::min(From, RFrom); + To = std::max(To, RTo); + } + // Add only detached ranges. + return isDetached; + }; + + // Copy all disjoint ranges and expand the bounds (From, To). + llvm::copy_if(Original, std::back_inserter(Result), IsDetachedPred); + + Range NewRange{ValueFactory.getValue(From), ValueFactory.getValue(To)}; + const_iterator LowerIt = llvm::lower_bound(Result, NewRange); + Result.insert(const_cast(LowerIt), 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/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) { @@ -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) {