[analyzer] Improved RangeSet::Negate support of unsigned ranges

[ASDenysPetrov]

Summary

This fixes https://bugs.llvm.org/show_bug.cgi?id=41588
RangeSet Negate function shall handle unsigned ranges as well as signed ones.
RangeSet getRangeForMinusSymbol function shall use wider variety of ranges, not only concrete value ranges.
RangeSet Intersect functions shall not produce assertions.

Changes:
Improved safety of RangeSet::Intersect function. Added isEmpty() check to prevent an assertion.
Added support of handling unsigned ranges to RangeSet::Negate and RangeSet::getRangeForMinusSymbol.
Extended RangeSet::getRangeForMinusSymbol to return not only range sets with single value [n,n], but with wide ranges [n,m].
Added unit test for Negate function.
Added regression tests for unsigned values.

[steakhal]

It took me some time to understand what you were doing.
Probably a bit ASCII-art would have had help (eg. about the wrapping behavior).

By the same token, I wouldn't mind more tests, especially exercising the implemented behavior.
Probably unit-tests would fit better than lit-tests for this purpose.
Eg. showing that if the RangeSet includes the MIN, then the negated RangeSet also includes that.
And the negated RangeSet really unites consecutive ranges.

Please note that I'm not a math expert and I haven't spent much time working with RangeSets.

[baloghadamsoftware]

Thank you for fixing this issue!

Please add a bit more tests where we can see that the negated of unsigned range of [n..m] is UINT_MAX-m+1..UINT_MAX-n+1].

[ASDenysPetrov]

@steakhal, thank you for your time!
@baloghadamsoftware

Please add a bit more tests where we can see that the negated of unsigned range of [n..m] is UINT_MAX-m+1..UINT_MAX-n+1].

Yes. I am writing them. Thanks for the review.

[ASDenysPetrov]

Improved Negate function in terms of handling [MIN,A]U[B,MAX] => [MIN,-B]U[-A,MAX] (previously was [MIN,MIN]U[MIN+1,-B]U[-A,MAX]).
Added unit test for Negate function.

[ASDenysPetrov]

@baloghadamsoftware
Please, review my changes. If you think they are OK, could you, please, commit the patch on my behalf as an author:
git commit --amend --author="Denys Petrov <[e-mail]>"

[baloghadamsoftware]

The unit test you added is very welcome. However, please still extend the current tests (which are for the signed) also for the unsigned as well. Since this is a core change in the analyzer, let us wait for @NoQ as well before accepting it.

[steakhal]

I'm impressed.
Though, I had some nits, please don't take it to heart :)

And consider joining the to the pre-merge beta testing project to benefit from buildbots and much more - for free.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

217

Should we take it as const ref to prevent copying?

235

AFAIK in a RangeSet the ranges are sorted by the From point in ascending order.
We should not check it for each range, only for the first.

Also, note that small and flat loops are more readable.
Consider using pure lambdas to reduce the body of the loop and of course to bind algorithms to names.

572–573

Couldn't we simplify the disjunction to single T->isEnumerationType() or to something similar?

clang/test/Analysis/constraint_manager_negate_difference.c

114–118

What does this test case demonstrate? Could you elaborate on that?
Why do you evaluate the x - y != 0 here twice?

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

23

According to the LLVM coding style we should use UpperCamelCase for variable names for new code.

Note that the Analyzer Core was written in a different style, we should follow that there instead (at least IMO).

27–28

AFAIK since std::initializer_list is just two pointers we should take it by value.

51

Generally, new expressions are a code smell. We should use something like an std::make_unique to prevent memory leaks on exceptions.
Though, I'm not sure if there is a similar function for llvm::IntrusiveRefCntPtr<T>s.

66

To be honest, I'm not sure if type is more descriptive than T.

68

AFAIK full sentences are required for comments.
https://llvm.org/docs/CodingStandards.html#commenting

113–120

Should we keep this?

[ASDenysPetrov]

@baloghadamsoftware

However, please still extend the current tests

I've looked for some appropriate tests to extend, but haven't found. What would you advise to use instead of mine?
@steakhal
Thanks for the comments.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

217

getMinValue returns APSInt by value, so it wouldn't make sense.

572–573

I've looked for similar single function, but there is no appropriate one. I decided not to add a new one to make patch more focused.

clang/test/Analysis/constraint_manager_negate_difference.c

114–118

Why do you evaluate the x - y != 0 here twice?

This is the root line which assertion occured on.
I'll add some comments.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

23

Here is a discussion VariableNames I was guide. Seems like we can use camelBack for new code. Am I right? Also RangeSetTest.cpp already uses mixed naming as you can see.

27–28

I'm not sure about should, since initializer_list is a container and it'd be consistent if we handle it like any other compound object despite its implementation (IMO). But I can change it if you wish.

51

I'll make it more safe.

66

It is useful for debug purposes, for instance you can change it to using type = int; to verify something. It also untie from template argument list and make the code more flexible.

68

I'll correct it.

113–120

I'm not sure, but I'd better keep it, because it is useful for debugging.

[ASDenysPetrov]

Refined Negate function. Divided by steps for clarity.
Made some changes in comments due to guideline.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

217

My fault. Yes, you are right. I've missed &. I used to append & to the type, since it is more readable and actually is a part of type, but I won't debate with clang style guide :).

[ASDenysPetrov]

@baloghadamsoftware
I have added regression tests as you asked. You can now check them. Thanks.
@NoQ,
I kindly ask you to look at the changes, seems that it has a full set to be load-ready. I really need your feedback here, since the changes is in the core.

[NoQ]

The math looks correct, thank you for fixing the crash and adding support for more cases!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

286–287

I don't remember iterator invalidation rules for these containers and it gives me anxiety. Given that these containers are immutable, i wouldn't be surprised if iterators are indeed never invalidated (just keep pointing to the old container) but it definitely deserves a comment.

572–573

isIntegralOrEnumerationType(), i guess.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

27–28

initializer_list is a container

No, it's a view :)

51

I'd rather create ASTContext through tooling, like in other unittests.

113–120

No-no, we don't do that here >.>

If you constructed an awesome debugging facility and you want to save it for future generations, i'd recommend turning it into an actual facility, not just comments. Like, maybe, an unused function that can be invoked for debugging, or something like that.

[ASDenysPetrov]

Thank you for the feedback. I'll update the patch soon.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

286–287

Thanks for the notice. I'm not sure about iterator invalidation, so I'll just replace *iter2 with *newRanges.begin().

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

27–28

No, it's a view :)

Yes, you are right. OK, I'll change it to value argument.

51

I'll look into other tests and try to change to ASTContext.

113–120

OK, I'll move it to function.

[ASDenysPetrov]

@NoQ updated the patch. Review, please.

[ASDenysPetrov]

@NoQ , ping. Look please.

[ASDenysPetrov]

Just a ping.

[NoQ]

Looks fantastic, thanks! I guess let's race with @vsavchenko on whoever commits first :p

[vsavchenko]

@NoQ @ASDenysPetrov I will rebase my changes - no worries :)

[ASDenysPetrov]

@NoQ many thanks. I'll land it.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 // the closed range [Lower, Upper]. Unlike the Range type, this range uses
 // modular arithmetic, corresponding to the common treatment of C integer
 // overflow. Thus, if the Lower bound is greater than the Upper bound, the
 // range is taken to wrap around. This is equivalent to taking the
 // intersection with the two ranges [Min, Upper] and [Lower, Max],
 // or, alternatively, /removing/ all integers between Upper and Lower.
 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
                              llvm::APSInt Lower, llvm::APSInt Upper) const {
-  if (!pin(Lower, Upper))
-    return F.getEmptySet();
-
   PrimRangeSet newRanges = F.getEmptySet();
 
+  if (isEmpty() || !pin(Lower, Upper))
+    return newRanges;
+
   PrimRangeSet::iterator i = begin(), e = end();
   if (Lower <= Upper)
     IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
   else {
     // The order of the next two statements is important!
     // IntersectInRange() does not reset the iteration state for i and e.
     // Therefore, the lower range most be handled first.
     IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
     for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
       newRanges = F.add(newRanges, *j);
     }
   }
 
   return newRanges;
 }
 
-// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
-// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
-// signed values of the type.
+// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
+// operation under the values of the type.
+
+// We also handle MIN because applying unary minus to MIN does not change it.
+// example 1:
+// char x = -128;        // -128 is a MIN value in a range of 'char'
+// char y = -x;          // y: -128
+// example 2:
+// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
+// unsigned char y = -x; // y: 0
+
+// And it makes us to separate the range
+// like [MIN, N] to [MIN, MIN] U [-N,MAX].
+// example: whole range is {-128..127} and subrange is [-128,-126]
+// thus [-128,-127,-126,.....] negates to [-128,.....,126,127]
+
+// Negate restores disrupted ranges on bounds,
+// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]
 RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
   PrimRangeSet newRanges = F.getEmptySet();
 
+  if (isEmpty())
+    return newRanges;
+
+  const llvm::APSInt sampleValue = getMinValue();
+  const bool isUnsigned = sampleValue.isUnsigned();
+  const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
+  const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+  bool hasNewRangesMinValue = false;
+
   for (iterator i = begin(), e = end(); i != e; ++i) {
-    const llvm::APSInt &from = i->From(), &to = i->To();
-    const llvm::APSInt &newTo = (from.isMinSignedValue() ?
-                                 BV.getMaxValue(from) :
-                                 BV.getValue(- from));
-    if (to.isMaxSignedValue() && !newRanges.isEmpty() &&
-        newRanges.begin()->From().isMinSignedValue()) {
-      assert(newRanges.begin()->To().isMinSignedValue() &&
-             "Ranges should not overlap");
-      assert(!from.isMinSignedValue() && "Ranges should not overlap");
-      const llvm::APSInt &newFrom = newRanges.begin()->From();
-      newRanges =
-        F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
-    } else if (!to.isMinSignedValue()) {
-      const llvm::APSInt &newFrom = BV.getValue(- to);
+    const llvm::APSInt &from = i->From();
+    const llvm::APSInt &to = i->To();
+
+    const bool isFromMinValue =
+        isUnsigned ? from.isMinValue() : from.isMinSignedValue();
+    const bool isToMinValue =
+        isUnsigned ? to.isMinValue() : to.isMinSignedValue();
+    const bool isToMaxValue =
+        isUnsigned ? to.isMaxValue() : to.isMaxSignedValue();
+
+    // handle a special case for MIN value
+    if (isFromMinValue) {
+      // if [from, to] are [MIN, MAX], then just return the same [MIN, MAX]
+      if (isToMaxValue) {
+        newRanges = ranges;
+      } else {
+        // add separate range for the lowest value
+        newRanges = F.add(newRanges, Range(MIN, MIN));
+        hasNewRangesMinValue = true;
+        // skip adding the second range in case when [from, to] are [MIN, MIN]
+        if (!isToMinValue) {
+          newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
+        }
+      }
+    } else {
+      const llvm::APSInt &newFrom = BV.getValue(-to);
+      const llvm::APSInt &newTo = BV.getValue(-from);
+
+      // unite ranges [MIN, MIN] & [MIN + 1, N] => [MIN, N]
+      if (hasNewRangesMinValue && (newFrom - 1) == MIN) {
+        hasNewRangesMinValue = false;
+        newRanges = F.remove(newRanges, *newRanges.begin());
+        newRanges = F.add(newRanges, Range(MIN, newTo));
+      } else {
+        // otherwise add an negated range
         newRanges = F.add(newRanges, Range(newFrom, newTo));
       }
-    if (from.isMinSignedValue()) {
-      newRanges = F.add(newRanges, Range(BV.getMinValue(from),
-                                         BV.getMinValue(from)));
     }
   }
 
   return newRanges;
 }
 
 void RangeSet::print(raw_ostream &os) const {
   bool isFirst = true;
void RangeSet::print(raw_ostream &os) const {
   }
   os << " }";
 }
 
 namespace {
 class RangeConstraintManager : public RangedConstraintManager {
 public:
   RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
       : RangedConstraintManager(SE, SVB) {}
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.
   //===------------------------------------------------------------------===//
 
   bool haveEqualConstraints(ProgramStateRef S1,
                             ProgramStateRef S2) const override {
     return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
   }
RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
                                                SymbolRef Sym) {
   if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
     if (SSE->getOpcode() == BO_Sub) {
       QualType T = Sym->getType();
       SymbolManager &SymMgr = State->getSymbolManager();
       SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
                                               SSE->getLHS(), T);
       if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
-        // Unsigned range set cannot be negated, unless it is [0, 0].
-        if ((negV->getConcreteValue() &&
-             (*negV->getConcreteValue() == 0)) ||
+        if (T->isUnsignedIntegerOrEnumerationType() ||
             T->isSignedIntegerOrEnumerationType())
           return negV;
       }
     }
   }
   return nullptr;
 }
 
 //===------------------------------------------------------------------------===

clang/test/Analysis/constraint_manager_negate_difference.c

 }
 
 void effective_range_2(int m, int n) {
   assert(m - n <= 0);
   assert(n - m <= 0);
   clang_analyzer_eval(m - n == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}}
   clang_analyzer_eval(n - m == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}}
 }
+
+void negated_unsigned_range(unsigned x, unsigned y) {
+  clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+  clang_analyzer_eval(y - x != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+  clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
+}

clang/unittests/StaticAnalyzer/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(StaticAnalysisTests
   AnalyzerOptionsTest.cpp
   CallDescriptionTest.cpp
   StoreTest.cpp
   RegisterCustomCheckersTest.cpp
   SymbolReaperTest.cpp
+  RangeSetTest.cpp
   )
 
 clang_target_link_libraries(StaticAnalysisTests
   PRIVATE
   clangBasic
   clangAnalysis
   clangAST
   clangASTMatchers
   clangCrossTU
   clangFrontend
   clangSerialization
   clangStaticAnalyzerCore
   clangStaticAnalyzerFrontend
   clangTooling
   )

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

+//===- unittests/StaticAnalyzer/RangeSetTest.cpp ----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Basic/Builtins.h"
+#include "clang/Basic/FileManager.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace ento {
+namespace {
+
+// TestCase contains to lists of ranges
+// original one, has to be negated
+// expected one, has to be compared to negated original range
+template <typename T> struct TestCase {
+  RangeSet original;
+  RangeSet expected;
+
+  TestCase(BasicValueFactory &BVF, RangeSet::Factory &F,
+           const std::initializer_list<T> &originalList,
+           const std::initializer_list<T> &expectedList)
+      : original(createRangeSetFromList(BVF, F, originalList)),
+        expected(createRangeSetFromList(BVF, F, expectedList)) {}
+
+private:
+  RangeSet createRangeSetFromList(BasicValueFactory &BVF, RangeSet::Factory &F,
+                                  const std::initializer_list<T> &rangeList) {
+    llvm::APSInt from(sizeof(T) * 8, std::is_unsigned<T>::value);
+    llvm::APSInt to = from;
+    RangeSet rangeSet = F.getEmptySet();
+    for (auto it = rangeList.begin(); it != rangeList.end(); it += 2) {
+      from = *it;
+      to = *(it + 1);
+      rangeSet = rangeSet.addRange(
+          F, RangeSet(F, BVF.getValue(from), BVF.getValue(to)));
+    }
+    return rangeSet;
+  }
+};
+
+class RangeSetTest : public testing::Test {
+protected:
+  // init block
+  DiagnosticsEngine Diag{new DiagnosticIDs, new DiagnosticOptions};
+  FileSystemOptions FileSystemOpts;
+  FileManager FileMgr{FileSystemOpts};
+  SourceManager SM{Diag, FileMgr};
+  LangOptions LOpts;
+  IdentifierTable idents;
+  SelectorTable sels;
+  Builtin::Context builtins;
+  ASTContext context{LOpts, SM, idents, sels, builtins};
+  llvm::BumpPtrAllocator alloc;
+  BasicValueFactory BVF{context, alloc};
+  RangeSet::Factory F;
+  // end init block
+
+  template <typename T> void checkNegate() {
+    using type = T;
+
+    // use next values of the range {MIN, A, B, MID, C, D, 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)
+
+    constexpr type MIN = std::numeric_limits<type>::min();
+    constexpr type MAX = std::numeric_limits<type>::max();
+    constexpr type MID = std::is_signed<type>::value
+                             ? 0
+                             : ~(static_cast<type>(-1) / static_cast<type>(2));
+    constexpr type A = MID - static_cast<type>(42 + 42);
+    constexpr type B = MID - static_cast<type>(42);
+    constexpr type C = -B;
+    constexpr type D = -A;
+
+    static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+                  "Values shall be in an ascending order");
+
+    // left {[x, y], [x, y]} is what shall be negated
+    // right {[x, y], [x, y]}  is what shall be compared to a negation result
+    TestCase<type> cases[] = {
+        {BVF, F, {MIN, A}, {MIN, MIN, D, MAX}},
+        {BVF, F, {MIN, C}, {MIN, MIN, B, MAX}},
+        {BVF, F, {MIN, MID}, {MIN, MIN, MID, MAX}},
+        {BVF, F, {MIN, MAX}, {MIN, MAX}},
+        {BVF, F, {A, D}, {A, D}},
+        {BVF, F, {A, B}, {C, D}},
+        {BVF, F, {MIN, A, D, MAX}, {MIN, A, D, MAX}},
+        {BVF, F, {MIN, B, MID, D}, {MIN, MIN, A, MID, C, MAX}},
+        {BVF, F, {MIN, MID, C, D}, {MIN, MIN, A, B, MID, MAX}},
+        {BVF, F, {MIN, MID, C, MAX}, {MIN, B, MID, MAX}},
+        {BVF, F, {A, MID, D, MAX}, {MIN + 1, A, MID, D}},
+        {BVF, F, {A, A}, {D, D}},
+        {BVF, F, {MID, MID}, {MID, MID}},
+        {BVF, F, {MAX, MAX}, {MIN + 1, MIN + 1}},
+    };
+
+    for (const auto &c : cases) {
+      // negate original and check with expected
+      RangeSet negatedFromOriginal = c.original.Negate(BVF, F);
+      EXPECT_EQ(negatedFromOriginal, c.expected);
+      RangeSet negatedBackward = c.expected.Negate(BVF, F);
+      EXPECT_EQ(negatedBackward, c.original);
+
+      // c.original.print(llvm::dbgs());
+      // llvm::dbgs() << " => ";
+      // c.expected.print(llvm::dbgs());
+      // llvm::dbgs() << " => ";
+      // negatedFromOriginal.print(llvm::dbgs());
+      // llvm::dbgs() << " => ";
+      // negatedBackward.print(llvm::dbgs());
+      // llvm::dbgs() << "\n";
+    }
+  }
+};
+
+TEST_F(RangeSetTest, RangeSetNegateTest) {
+  checkNegate<int8_t>();
+  checkNegate<uint8_t>();
+  checkNegate<int16_t>();
+  checkNegate<uint16_t>();
+  checkNegate<int32_t>();
+  checkNegate<uint32_t>();
+  checkNegate<int64_t>();
+  checkNegate<uint64_t>();
+}
+
+} // namespace
+} // namespace ento
+} // namespace clang