ASDenysPetrov updated this revision to Diff 383065. ASDenysPetrov added a comment.
Fixed nits. 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 @@ -35,12 +35,34 @@ const RangeSet &Set) { return OS << toString(Set); } +// We need it here for better fail diagnostics from gtest. +LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS, + const Range &R) { + return OS << toString(R); +} } // namespace ento } // namespace clang namespace { +template <typename T> struct TestValues { + static constexpr T MIN = std::numeric_limits<T>::min(); + static constexpr T MAX = std::numeric_limits<T>::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 T MID = + std::is_signed<T>::value ? 0 : ~(static_cast<T>(-1) / static_cast<T>(2)); + static constexpr T A = MID - (MAX - MID) / 3 * 2; + static constexpr T B = MID - (MAX - MID) / 3; + static constexpr T C = -B; + static constexpr T D = -A; + + static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, + "Values shall be in an ascending order"); +}; + template <typename BaseType> class RangeSetTest : public testing::Test { public: // Init block @@ -55,24 +77,11 @@ using RawRange = std::pair<BaseType, BaseType>; using RawRangeSet = std::initializer_list<RawRange>; - static constexpr BaseType getMin() { - return std::numeric_limits<BaseType>::min(); - } - static constexpr BaseType getMax() { - return std::numeric_limits<BaseType>::max(); - } - static constexpr BaseType getMid() { - return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2)); - } - - static constexpr bool isSigned() { return std::is_signed<BaseType>::value; } - static constexpr BaseType fromInt(int X) { return static_cast<BaseType>(X); } - - static llvm::APSInt Base; const llvm::APSInt &from(BaseType X) { - llvm::APSInt Dummy = Base; - Dummy = X; - return BVF.getValue(Dummy); + static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT, + std::is_unsigned<BaseType>::value}; + Base = X; + return BVF.getValue(Base); } Range from(const RawRange &Init) { @@ -160,7 +169,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 +177,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); @@ -183,29 +215,19 @@ } // namespace -template <typename BaseType> -llvm::APSInt RangeSetTest<BaseType>::Base{sizeof(BaseType) * 8, !isSigned()}; - using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t, uint64_t>; TYPED_TEST_SUITE(RangeSetTest, IntTypes, ); TYPED_TEST(RangeSetTest, RangeSetNegateTest) { - // Use next values of the range {MIN, A, B, MID, C, D, MAX}. - - 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); - constexpr TypeParam C = -B; - constexpr TypeParam D = -A; - - static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, - "Values shall be in an ascending order"); + 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; this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}}); this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}}); @@ -234,8 +256,9 @@ } TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) { - constexpr TypeParam MIN = TestFixture::getMin(); - constexpr TypeParam MAX = TestFixture::getMax(); + using TV = TestValues<TypeParam>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; // Check that we can correctly intersect empty sets. this->checkIntersect({}, 10, 20, {}); @@ -300,9 +323,11 @@ this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true); this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true); - constexpr TypeParam MIN = TestFixture::getMin(); - constexpr TypeParam MAX = TestFixture::getMax(); - constexpr TypeParam MID = TestFixture::getMid(); + using TV = TestValues<TypeParam>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; + this->checkContains({{MIN, MAX}}, 0, true); this->checkContains({{MIN, MAX}}, MID, true); this->checkContains({{MIN, MAX}}, -10, true); @@ -331,9 +356,10 @@ } TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) { - constexpr TypeParam MIN = TestFixture::getMin(); - constexpr TypeParam MAX = TestFixture::getMax(); - constexpr TypeParam MID = TestFixture::getMid(); + using TV = TestValues<TypeParam>; + constexpr auto MIN = TV::MIN; + constexpr auto MAX = TV::MAX; + constexpr auto MID = TV::MID; this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}}); // Check that delete works with an empty set. @@ -347,3 +373,221 @@ // 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) { + 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; + + // 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}}); + this->checkUnite({{MIN, MIN}}, {}, {{MIN, MIN}}); + this->checkUnite({{MAX, MAX}}, {}, {{MAX, MAX}}); + this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {}, {{MIN, MIN}, {MAX, MAX}}); + + // 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}}); + this->checkUnite({}, {{MIN, MIN}}, {{MIN, MIN}}); + this->checkUnite({}, {{MAX, MAX}}, {{MAX, MAX}}); + this->checkUnite({}, {{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, 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}}); + this->checkUnite({{MAX, MAX}}, {A, B}, {{A, B}, {MAX, MAX}}); + this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}}); + this->checkUnite({{MIN, MIN}}, {MAX, MAX}, {{MIN, MIN}, {MAX, 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}}); + this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}}, + {{MIN, MIN}, {MAX, MAX}}); + + // RHS equals to LHS. + // RHS => _____ + // LHS => /_____\_____ = ___________ + // /_______\____\___ /___________\___ + this->checkUnite({{MIN, A}}, {MIN, B}, {{MIN, B}}); + + // RHS equals to LHS. + // RHS => __________ + // LHS => /______ \ = ___________ + // /_______\____\___ /___________\___ + this->checkUnite({{MIN, B}}, {MIN, A}, {{MIN, B}}); + + // 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}}); + + // Multiple intersections. + + // RHS => + // LHS => /\ /\ = __ __ + // _/__\_/__\_/\_/\_/\_ _/__\_/__\_/\_/\_/\_ + this->checkUnite({{MIN, A}, {A + 2, B}}, {{MID, C}, {C + 2, D - 2}, {D, MAX}}, + {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}}); + this->checkUnite({{MIN, MIN}, {A, A}}, {{B, B}, {C, C}, {MAX, MAX}}, + {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}}); + + // RHS => + // LHS => /\ /\ = __ __ + // _/\_/\_/\__/__\_/__\_ _/\_/\_/\_/__\_/__\_ + this->checkUnite({{C + 2, D - 2}, {D, MAX}}, {{MIN, A}, {A + 2, B}, {MID, C}}, + {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}}); + this->checkUnite({{C, C}, {MAX, MAX}}, {{MIN, MIN}, {A, A}, {B, B}}, + {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {MAX, MAX}}); + + // RHS => + // LHS => _ /\ _ /\ _ /\ = + // _/_\_/__\_/_\_/__\_/_\_/__\_ + // + // RSLT => _ __ _ __ _ __ + // _/_\_/__\_/_\_/__\_/_\_/__\_ + this->checkUnite({{A + 2, B}, {MID + 2, C}, {D + 2, MAX}}, + {{MIN, A}, {B + 2, MID}, {C + 2, D}}, + {{MIN, A}, + {A + 2, B}, + {B + 2, MID}, + {MID + 2, C}, + {C + 2, D}, + {D + 2, MAX}}); + this->checkUnite({{A, A}, {C, C}, {MAX, MAX}}, {{MIN, MIN}, {B, B}, {D, D}}, + {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}}); + + // RHS => + // LHS => /\ _ /\ _ /\ _ = + // _/__\_/_\_/__\_/_\_/__\_/_\_ + // + // RSLT => __ _ __ _ __ _ + // _/__\_/_\_/__\_/_\_/__\_/_\_ + this->checkUnite({{MIN, A}, {B + 2, MID}, {C + 2, D}}, + {{A + 2, B}, {MID + 2, C}, {D + 2, MAX}}, + {{MIN, A}, + {A + 2, B}, + {B + 2, MID}, + {MID + 2, C}, + {C + 2, D}, + {D + 2, MAX}}); + this->checkUnite({{MIN, MIN}, {B, B}, {D, D}}, {{A, A}, {C, C}, {MAX, MAX}}, + {{MIN, MIN}, {A, A}, {B, B}, {C, C}, {D, D}, {MAX, MAX}}); + + // RHS => _ __ _ + // LHS => /_\ /_ \ _ / \ = ___ ____________ + // _/___\_/__\_\/_\/___\_ _/___\_/____________\_ + this->checkUnite({{MIN, A}, {B, C}, {D, MAX}}, + {{MIN, A}, {B, C - 2}, {C + 1, D - 1}}, + {{MIN, A}, {B, MAX}}); + this->checkUnite({{A, A}, {B, MID}, {D, D}}, + {{A, A}, {B, B}, {MID + 1, D - 1}}, {{A, A}, {B, D}}); + + // RHS => ___ ___ + // LHS => /\ _/_ \_ / _ \ /\ = + // _/\_/__\//__\ /\\_/_/_\_\_/__\_ + // + // RSLT => ___________ _____ __ + // _/\_/___________\_/_____\_/__\_ + this->checkUnite({{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}}, + {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}}, + {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}}); +} Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -110,6 +110,14 @@ RangeSet::ContainerType RangeSet::Factory::EmptySet{}; +RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) { + ContainerType Result; + Result.reserve(LHS.size() + RHS.size()); + 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); @@ -126,6 +134,186 @@ return add(Original, Range(Point)); } +RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) { + ContainerType Result = unite(*LHS.Impl, *RHS.Impl); + return makePersistent(std::move(Result)); +} + +RangeSet RangeSet::Factory::unite(RangeSet Original, Range R) { + ContainerType Result; + Result.push_back(R); + Result = unite(*Original.Impl, Result); + return makePersistent(std::move(Result)); +} + +RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) { + return unite(Original, Range(ValueFactory.getValue(Point))); +} + +RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From, + llvm::APSInt To) { + return unite(Original, + Range(ValueFactory.getValue(From), ValueFactory.getValue(To))); +} + +template <typename T> +void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd) { + std::swap(First, Second); + std::swap(FirstEnd, SecondEnd); +} + +RangeSet::ContainerType RangeSet::Factory::unite(const ContainerType &LHS, + const ContainerType &RHS) { + if (LHS.empty()) + return RHS; + if (RHS.empty()) + return LHS; + + using llvm::APSInt; + using iterator = ContainerType::const_iterator; + + iterator First = LHS.begin(); + iterator FirstEnd = LHS.end(); + iterator Second = RHS.begin(); + iterator SecondEnd = RHS.end(); + APSIntType Ty = APSIntType(First->From()); + const APSInt Min = Ty.getMinValue(); + + // Handle a corner case first when both range sets start from MIN. + // This helps to avoid complicated conditions below. Specifically, this + // particular check for `MIN` is not needed in the loop below every time + // when we do `Second->From() - One` operation. + if (Min == First->From() && Min == Second->From()) { + if (First->To() > Second->To()) { + // [ First ]---> + // [ Second ]-----> + // MIN^ + // The Second range is entirely inside the First one. + + // Check if Second is the last in its RangeSet. + if (++Second == SecondEnd) + // [ First ]--[ First + 1 ]---> + // [ Second ]---------------------> + // MIN^ + // The Union is equal to First's RangeSet. + return LHS; + } else { + // case 1: [ First ]-----> + // case 2: [ First ]---> + // [ Second ]---> + // MIN^ + // The First range is entirely inside or equal to the Second one. + + // Check if First is the last in its RangeSet. + if (++First == FirstEnd) + // [ First ]-----------------------> + // [ Second ]--[ Second + 1 ]----> + // MIN^ + // The Union is equal to Second's RangeSet. + return RHS; + } + } + + const APSInt One = Ty.getValue(1); + ContainerType Result; + + // This is called when there are no ranges left in one of the ranges. + // Append the rest of the ranges from another range set to the Result + // and return with that. + const auto AppendTheRest = [&Result](iterator I, iterator E) { + Result.append(I, E); + return Result; + }; + + while (true) { + // We want to keep the following invariant at all times: + // ---[ First ------> + // -----[ Second ---> + if (First->From() > Second->From()) + swapIterators(First, FirstEnd, Second, SecondEnd); + + // The Union definitely starts with First->From(). + // ----------[ First ------> + // ------------[ Second ---> + // ----------[ Union ------> + // UnionStart^ + const llvm::APSInt &UnionStart = First->From(); + + // Loop where the invariant holds. + while (true) { + // Skip all enclosed ranges. + // ---[ First ]---> + // -----[ Second ]--[ Second + 1 ]--[ Second + N ]-----> + while (First->To() >= Second->To()) { + // Check if Second is the last in its RangeSet. + if (++Second == SecondEnd) { + // Append the Union. + // ---[ Union ]---> + // -----[ Second ]-----> + // --------[ First ]---> + // UnionEnd^ + Result.emplace_back(UnionStart, First->To()); + // ---[ Union ]-----------------> + // --------------[ First + 1]---> + // Append all remaining ranges from the First's RangeSet. + return AppendTheRest(++First, FirstEnd); + } + } + + // Check if First and Second are disjoint. It means that we find + // the end of the Union. Exit the loop and append the Union. + // ---[ First ]=-------------> + // ------------=[ Second ]---> + // ----MinusOne^ + if (First->To() < Second->From() - One) + break; + + // First is entirely inside the Union. Go next. + // ---[ Union -----------> + // ---- [ First ]--------> + // -------[ Second ]-----> + // Check if First is the last in its RangeSet. + if (++First == FirstEnd) { + // Append the Union. + // ---[ Union ]---> + // -----[ First ]-------> + // --------[ Second ]---> + // UnionEnd^ + Result.emplace_back(UnionStart, Second->To()); + // ---[ Union ]------------------> + // --------------[ Second + 1]---> + // Append all remaining ranges from the Second's RangeSet. + return AppendTheRest(++Second, SecondEnd); + } + + // We know that we are at one of the two cases: + // case 1: --[ First ]-[ First + 1 ]------> + // case 2: --[ First ]-[ First + 1 ]---> + // -------------------[ Second + 1]-------> + // In any case First + 1 goes after Second. + // Make sure that the loop invariant holds. + swapIterators(First, FirstEnd, Second, SecondEnd); + } + + // Here First and Second are disjoint. + // Append the Union. + // ---[ Union ]---------------> + // -----------------[ Second ]---> + // ------[ First ]---------------> + // UnionEnd^ + Result.emplace_back(UnionStart, First->To()); + + // Check if First is the last in its RangeSet. + if (++First == FirstEnd) + // ---[ Union ]---------------> + // --------------[ Second ]---> + // Append all remaining ranges from the Second's RangeSet. + return AppendTheRest(Second, SecondEnd); + } + + llvm_unreachable("Normally, we should not reach here"); +} + RangeSet RangeSet::Factory::getRangeSet(Range From) { ContainerType Result; Result.push_back(From); @@ -155,13 +343,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(); @@ -325,11 +506,6 @@ const_iterator First = LHS.begin(), Second = RHS.begin(), FirstEnd = LHS.end(), SecondEnd = RHS.end(); - const auto SwapIterators = [&First, &FirstEnd, &Second, &SecondEnd]() { - std::swap(First, Second); - std::swap(FirstEnd, SecondEnd); - }; - // If we ran out of ranges in one set, but not in the other, // it means that those elements are definitely not in the // intersection. @@ -339,7 +515,7 @@ // ----[ First ----------------------> // --------[ Second -----------------> if (Second->From() < First->From()) - SwapIterators(); + swapIterators(First, FirstEnd, Second, SecondEnd); // Loop where the invariant holds: do { @@ -373,7 +549,7 @@ if (Second->To() > First->To()) { // Here we make a decision to keep First as the "longer" // range. - SwapIterators(); + swapIterators(First, FirstEnd, Second, SecondEnd); } // At this point, we have the following situation: 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 @@ -140,6 +140,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(LHS), M = size(RHS) + RangeSet unite(RangeSet LHS, 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; } @@ -224,6 +248,9 @@ ContainerType *construct(ContainerType &&From); RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS); + /// NOTE: This function relies on the fact that all values in the + /// containers are persistent (created via BasicValueFactory::getValue). + ContainerType unite(const ContainerType &LHS, const ContainerType &RHS); // Many operations include producing new APSInt values and that's why // we need this factory.
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits