[analyzer] Add a new factory function RangeSet::Factory::invert

[ASDenysPetrov]

Summary

Add a new factory function RangeSet::Factory::invert. It performs an inversion operation on the given set and produces a new one as a result. The inversion of the set is a set containing all the values except those which are in the original one.

NOTE: User shall guarantee that the given set is not empty.

Example:
original: int8[0, 42] inverse: int8[-128, -1]U[43, 127];
original: int8[-128, 127] inverse: int8[];
original: [] inverse: raise an assertion.

The motivation is to extend the set of operations that can be performed on range sets. Specifically, this function is needed for the next patch in the stack.

[martong]

The motivation is to extend the set of operations that can be performed on range sets. Specifically, this function is needed for the next patch in the stack.

Would be great to see the motivation clearly and early. What will be the next patch about?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

711

Could you please document this function and its complexity? (O(N) where N is the number of elements of the RangeSet.)

728–729

There might be a flaw here. Should this be == instead of != ?
Consider e.g. when What has two elements [[MIN, -1], [1, MAX]] then the inverse should be [0,0] which has size 1.

734–735

No goto please. There are better alternatives, e.g. you could have two different while loops for each cases.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

281

I think, it would make sense to test the composition of two invert operations to identity.

EXPECT_EQ(What, F.invert(F.invert(What));

This, of course requires that empty set is a possible input.

1106

Good tests!

1135

I'd expect that inversion on finite sets is an invert-able function thus

this->checkInvert({}, {MIN, MAX});

would make sense instead of assertion.

Besides, it would make sense to test the composition of two invert operations to identity.

[ASDenysPetrov]

@martong Thanks for review.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

728–729

Yes. Definetely. It remained from my previous version of calculation.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

281

Great idea. I will do it, except [].

1135

I'm afraid the function would be overheaded and less usable. Why do we have an assertion here? I thought about this. This is kinda a tradeoff.

What range would be a correct range from inversion of []? [-128, 127]? [0, 65535]?
In order to make [MIN, MAX] from empty range [] we should know the exact APSIntType. We extract the type from the given range What.getAPSIntType();.

But though, let's consider we have QualType as a second parameter. We have two options about what type to use.

1. Always use the second parameter. The function would not only invert but do what castTo actually do. Such behavior would violates a single responsibility principle and duplicate the functionality.
2. Always use the type from the given range and for the case of empty range from the second parameter. The function contract would be more complex and obscure.

So, I decided not to introduce a new parameter and shift responsibility to the user. Empty range is an edge case when we usually produce infeasible state or use infer(QualType). This may pretty fit with what user is going to do first before using invert, so it shouldn't affect the convinience of function usage too much.

[ASDenysPetrov]

Now I'm working on the next patch and you'll see a motivation soon.

[ASDenysPetrov]

Make changes according to the remarks.

• Add complexity to function description.
• Rewrite the loop making it deterministic.
• Add back invert operation to the tests.

[martong]

In D130372#3683275, @ASDenysPetrov wrote:

Now I'm working on the next patch and you'll see a motivation soon.

Thanks for the update! Looks good, but I am still waiting with my formal approve to understand the motivation.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

1135

Okay, I see your point.

So, considering RangeSet::Factory::invert(RangeSet What) we have only one parameter and that is the RangeSet to be inverted. And that set might be empty and in that case we are left without any type information, thus there is no way to return [MIN, MAX]. Please correct me if I am wrong.

[ASDenysPetrov]

@martong

Now I'm working on the next patch and you'll see a motivation soon.

Here is the motivation but it still causes some tests failure D131006.

[ASDenysPetrov]

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

1135

Exactly. That's what I'm talking about..

[martong]

LGTM! Nice work!

[ASDenysPetrov]

Thank you. I prefer to load this along with the motivation part D131006.

[ASDenysPetrov]

The motivation for this revision is lost due to the logical mistake in the later. However, this revision could be used for other improvements in the future. I will not merge it until new motivation has become.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

public:
     /// Complexity:
     ///     - Noop                               O(1);
     ///     - Truncation                         O(N^2);
     ///     - Another case                       O(N);
     ///     where N = size(What)
     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; }
 
   private:
     /// Return a persistent version of the given container.
     RangeSet makePersistent(ContainerType &&From);
     /// Construct a new persistent version of the given container.
     ContainerType *construct(ContainerType &&From);

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
 
   return getEmptySet();
 }
 
 RangeSet RangeSet::Factory::negate(RangeSet What) {
   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();
   const_iterator End = What.end();
 
   const llvm::APSInt &From = It->From();
   const llvm::APSInt &To = It->To();
 
RangeSet RangeSet::Factory::castTo(RangeSet What, APSIntType Ty) {
   return makePersistent(promoteTo(What, Ty));
 }
 
 RangeSet RangeSet::Factory::castTo(RangeSet What, QualType T) {
   assert(T->isIntegralOrEnumerationType() && "T shall be an integral type.");
   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;
   using llvm::APSInt;
   ContainerType Result;
   ContainerType Dummy;
   // CastRangeSize is an amount of all possible values of cast type.
   // Example: `char` has 256 values; `short` has 65536 values.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

public:
   }
 
   template <typename From, typename To>
   void checkCastTo(RawRangeSetT<From> What, RawRangeSetT<To> Expected) {
     static constexpr APSIntType FromTy = APSIntTy<From>;
     static constexpr APSIntType ToTy = APSIntTy<To>;
     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<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) {
   using TV = TestValues<TypeParam>;
TYPED_TEST(RangeSetCastToTruncationConversionTest, Test) {
   constexpr auto FromA = TV::FromA;
   constexpr auto ToA = TV::ToA;
   constexpr auto FromB = TV::FromB;
   constexpr auto ToB = TV::ToB;
   this->template checkCastTo<F, T>({{FromA, ToA}, {FromB, ToB}},
                                    {{FromA, ToA}});
 }
 
+TYPED_TEST(RangeSetTest, RangeSetInvertTest) {
+  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;
+
+  // 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