[analyzer][solver] Do not negate unsigned ranges

[martong]

Summary

This is a bugfix. Simply put, 2u - 1u != 2u - 1u. See the static
assertion in the test file. The fix simply ban the negation of unsigned
expressions. This way the we are getting a little bit more conservatie,
but at least we do not infer wrong values.

[steakhal]

Seems reasonable.

clang/test/Analysis/constraint_manager_negate_difference.c

145–148

It's not immediately clear what you refer to by the TRUE case. The two evals the opposite condition, consequently one of them should be FALSE. Same for the next case.

[martong]

clang/test/Analysis/constraint_manager_negate_difference.c

125–130

Actually, this test case was correct, because UINT_MID is a special value and for that

_Static_assert(UINT_MID == -UINT_MID, "");

holds.
So, this patch is meaningless.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

private:
   //        only negated SymSymExpr-type expressions, but also of other, simpler
   //        expressions which we currently do not know how to negate.
   Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) {
     if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
       if (SSE->getOpcode() == BO_Sub) {
         QualType T = Sym->getType();
 
         // Do not negate unsigned ranges
-        if (!T->isUnsignedIntegerOrEnumerationType() &&
-            !T->isSignedIntegerOrEnumerationType())
+        if (T->isUnsignedIntegerOrEnumerationType())
           return llvm::None;
 
         SymbolManager &SymMgr = State->getSymbolManager();
         SymbolRef NegatedSym =
             SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
 
         if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
           return RangeFactory.negate(*NegatedRange);

clang/test/Analysis/constraint_manager_negate_difference.c

void negate_unsigned_min(unsigned m, unsigned n) {
   if (m - n == UINT_MIN) {
     clang_analyzer_eval(n - m == UINT_MIN); // expected-warning{{TRUE}}
     clang_analyzer_eval(n - m != UINT_MIN); // expected-warning{{FALSE}}
     clang_analyzer_eval(n - m > UINT_MIN);  // expected-warning{{FALSE}}
     clang_analyzer_eval(n - m < UINT_MIN);  // expected-warning{{FALSE}}
   }
 }
 
+_Static_assert(12u - 1u != 1u - 12u, "Good modulo arithmetic");
 void negate_unsigned_mid(unsigned m, unsigned n) {
   if (m - n == UINT_MID) {
-    clang_analyzer_eval(n - m == UINT_MID); // expected-warning{{TRUE}}
-    clang_analyzer_eval(n - m != UINT_MID); // expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m == UINT_MID); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m != UINT_MID); // expected-warning{{FALSE}} expected-warning{{TRUE}}
   }
 }
 
 void negate_unsigned_mid2(unsigned m, unsigned n) {
   if (m - n < UINT_MID && m - n > UINT_MIN) {
-    clang_analyzer_eval(n - m > UINT_MID); // expected-warning{{TRUE}}
-    clang_analyzer_eval(n - m < UINT_MID); // expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m > UINT_MID); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m < UINT_MID); // expected-warning{{FALSE}} expected-warning{{TRUE}}
   }
 }
 
+
+_Static_assert(1u - 2u == UINT_MAX, "Good modulo arithmetic");
+_Static_assert(2u - 1u == 1, "Good modulo arithmetic");
 void negate_unsigned_max(unsigned m, unsigned n) {
   if (m - n == UINT_MAX) {
-    clang_analyzer_eval(n - m == 1); // expected-warning{{TRUE}}
-    clang_analyzer_eval(n - m != 1); // expected-warning{{FALSE}}
+    // FIXME only the TRUE case should appear. But it is better to be
+    // conservative than faulty.
+    clang_analyzer_eval(n - m == 1); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m != 1); // expected-warning{{FALSE}} expected-warning{{TRUE}}
   }
 }
-
 void negate_unsigned_one(unsigned m, unsigned n) {
   if (m - n == 1) {
-    clang_analyzer_eval(n - m == UINT_MAX); // expected-warning{{TRUE}}
-    clang_analyzer_eval(n - m < UINT_MAX);  // expected-warning{{FALSE}}
+    // FIXME only the TRUE case should appear.
+    clang_analyzer_eval(n - m == UINT_MAX); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+    clang_analyzer_eval(n - m < UINT_MAX);  // expected-warning{{FALSE}} expected-warning{{TRUE}}
   }
 }
 
 // The next code is a repro for the bug PR41588
 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}}
   // expected no assertion on the next line
   clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}}
 }