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 @@ -261,6 +261,20 @@ RangeSet castTo(RangeSet What, APSIntType Ty); RangeSet castTo(RangeSet What, QualType T); + /// Produce an invertion of the given set. + /// + /// Note: The given set shall not be empty. + /// + /// Examples: + /// - [A, B] -> [MIN, A - 1]U[B + 1, MAX] + /// - [MIN, A] -> [A + 1, MAX] + /// - [A, MAX] -> [MIN, A - 1] + /// - [MIN, MAX] -> Empty + /// + /// Complexity: O(N) + /// where N = size(What) + RangeSet invert(RangeSet What); + /// Return associated value factory. BasicValueFactory &getValueFactory() const { return ValueFactory; } Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -611,12 +611,12 @@ if (What.isEmpty()) return getEmptySet(); - const llvm::APSInt SampleValue = What.getMinValue(); - const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue); - const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue); + const APSIntType Ty = What.getAPSIntType(); + const llvm::APSInt &MIN = ValueFactory.getMinValue(Ty); + const llvm::APSInt &MAX = ValueFactory.getMaxValue(Ty); ContainerType Result; - Result.reserve(What.size() + (SampleValue == MIN)); + Result.reserve(What.size() + (What.getMinValue() == MIN)); // Handle a special case for MIN value. const_iterator It = What.begin(); @@ -708,6 +708,46 @@ return castTo(What, ValueFactory.getAPSIntType(T)); } +RangeSet RangeSet::Factory::invert(RangeSet What) { + assert(!What.isEmpty()); + + // Prepare some constants. + const APSIntType Ty = What.getAPSIntType(); + const llvm::APSInt &MIN = ValueFactory.getMinValue(Ty); + const llvm::APSInt &MAX = ValueFactory.getMaxValue(Ty); + const bool NoMin = What.getMinValue() != MIN; + const bool NoMax = What.getMaxValue() != MAX; + + // Shortcut: Return an empty range set for a full range. + if (What.size() == 1 && !NoMin && !NoMax) + return getEmptySet(); + + const_iterator It = What.begin(); + ContainerType Result; + Result.reserve(What.size() - 1 + NoMin + NoMax); + + auto Inc = [&](llvm::APSInt I) -> const llvm::APSInt & { + return ValueFactory.getValue(++I); + }; + auto Dec = [&](llvm::APSInt I) -> const llvm::APSInt & { + return ValueFactory.getValue(--I); + }; + + if (NoMin) + Result.emplace_back(MIN, Dec(It->From())); + + for (size_t i = 0; i < What.size() - 1; ++i) { + const llvm::APSInt &NewFrom = Inc(It->To()); + ++It; + Result.emplace_back(NewFrom, Dec(It->From())); + } + + if (NoMax) + Result.emplace_back(Inc(It->To()), MAX); + + return makePersistent(std::move(Result)); +} + RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What, APSIntType Ty) { using llvm::APInt; Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp =================================================================== --- clang/unittests/StaticAnalyzer/RangeSetTest.cpp +++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp @@ -275,6 +275,20 @@ static constexpr APSIntType ToTy = APSIntTy; this->checkCastToImpl(from(What, FromTy), ToTy, from(Expected, ToTy)); } + + void checkInvertImpl(RangeSet What, RangeSet Expected) { + RangeSet Result = F.invert(What); + EXPECT_EQ(Result, Expected) << "while inverting " << toString(What); + // Do invert back, except empty range because it is not permitted. + if (Result.isEmpty()) + return; + RangeSet BackResult = F.invert(Result); + EXPECT_EQ(BackResult, What) << "while inverting " << toString(Result); + } + + void checkInvert(RawRangeSet What, RawRangeSet Expected) { + this->checkInvertImpl(from(What), from(Expected)); + } }; using IntTypes = ::testing::Types; + 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; + + // Empty set is forbidden by the function contract. + // It produces an assertion. + /*this->checkInvert({}, ASSERTION);*/ + + // Check inverting single point. + this->checkInvert({{MIN, MIN}}, {{MIN + 1, MAX}}); + this->checkInvert({{MAX, MAX}}, {{MIN, MAX - 1}}); + this->checkInvert({{MID, MID}}, {{MIN, MID - 1}, {MID + 1, MAX}}); + this->checkInvert({{A, A}}, {{MIN, A - 1}, {A + 1, MAX}}); + + // Check inverting two points. + this->checkInvert({{MIN, MIN}, {MAX, MAX}}, {{MIN + 1, MAX - 1}}); + this->checkInvert({{MID, MID}, {MAX, MAX}}, + {{MIN, MID - 1}, {MID + 1, MAX - 1}}); + this->checkInvert({{MIN, MIN}, {D, D}}, {{MIN + 1, D - 1}, {D + 1, MAX}}); + this->checkInvert({{B, B}, {C, C}}, + {{MIN, B - 1}, {B + 1, C - 1}, {C + 1, MAX}}); + + // Check inverting single range. + this->checkInvert({{MIN, MAX}}, {}); + this->checkInvert({{MIN, MID}}, {{MID + 1, MAX}}); + this->checkInvert({{MID, MAX}}, {{MIN, MID - 1}}); + this->checkInvert({{A, D}}, {{MIN, A - 1}, {D + 1, MAX}}); + + // Check adding two ranges. + this->checkInvert({{MIN, MID - 1}, {MID + 1, MAX}}, {{MID, MID}}); + this->checkInvert({{MIN, B}, {C, D}}, {{B + 1, C - 1}, {D + 1, MAX}}); + this->checkInvert({{MIN + 1, A}, {B, MAX}}, {{MIN, MIN}, {A + 1, B - 1}}); + this->checkInvert({{A, B}, {C, MAX - 1}}, + {{MIN, A - 1}, {B + 1, C - 1}, {MAX, MAX}}); + + // Check adding three ranges. + this->checkInvert({{MIN, A}, {B, C}, {D, MAX}}, + {{A + 1, B - 1}, {C + 1, D - 1}}); + this->checkInvert({{A, B - 1}, {B + 1, C - 1}, {C + 1, MAX}}, + {{MIN, A - 1}, {B, B}, {C, C}}); + this->checkInvert({{MIN, B - 1}, {B + 1, C - 1}, {C + 1, D}}, + {{B, B}, {C, C}, {D + 1, MAX}}); + this->checkInvert({{A, B - 1}, {C, C}, {D, D}}, + {{MIN, A - 1}, {B, C - 1}, {C + 1, D - 1}, {D + 1, MAX}}); +} + } // namespace