Fix issue 9979: false positive: containerOutOfBounds with conditional…

… resize (#3136)
danmar · Mar 30, 2021 · 5077663 · 5077663 · danmar · May 14, 2021
1 parent 5c102a0
commit 5077663
Show file tree

Hide file tree

Showing 11 changed files with 460 additions and 169 deletions.
diff --git a/Makefile b/Makefile
diff --git a/addons/test/misra/misra-test.c b/addons/test/misra/misra-test.c
@@ -241,7 +241,7 @@ void misra_7_2(void) {
     unsigned short h = 0x8000U;
     unsigned int i = 0x80000000; // 7.2
     unsigned int j = 0x80000000U;
-    unsigned long long k = 0x8000000000000000; // 7.2
+    unsigned long long k = 0x8000000000000000; // TODO 7.2
     unsigned long long l = 0x8000000000000000ULL;
 
     unsigned int m = 1 + 0x80000000; // 7.2 10.4

diff --git a/lib/astutils.cpp b/lib/astutils.cpp
@@ -167,6 +167,11 @@ bool astIsIntegral(const Token *tok, bool unknown)
     return vt->isIntegral() && vt->pointer == 0U;
 }
 
+bool astIsUnsigned(const Token* tok)
+{
+    return tok && tok->valueType() && tok->valueType()->sign == ValueType::UNSIGNED;
+}
+
 bool astIsFloat(const Token *tok, bool unknown)
 {
     const ValueType *vt = tok ? tok->valueType() : nullptr;

diff --git a/lib/astutils.h b/lib/astutils.h
@@ -70,6 +70,7 @@ bool astIsSignedChar(const Token *tok);
 bool astIsUnknownSignChar(const Token *tok);
 /** Is expression of integral type? */
 bool astIsIntegral(const Token *tok, bool unknown);
+bool astIsUnsigned(const Token* tok);
 /** Is expression of floating point type? */
 bool astIsFloat(const Token *tok, bool unknown);
 /** Is expression of boolean type? */

diff --git a/lib/programmemory.cpp b/lib/programmemory.cpp
@@ -4,6 +4,7 @@
 #include "mathlib.h"
 #include "symboldatabase.h"
 #include "token.h"
+#include "valueflow.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdio>
@@ -424,20 +425,34 @@ void execute(const Token *expr,
 
     else if (expr->isComparisonOp()) {
         MathLib::bigint result1(0), result2(0);
-        execute(expr->astOperand1(), programMemory, &result1, error);
-        execute(expr->astOperand2(), programMemory, &result2, error);
-        if (expr->str() == "<")
-            *result = result1 < result2;
-        else if (expr->str() == "<=")
-            *result = result1 <= result2;
-        else if (expr->str() == ">")
-            *result = result1 > result2;
-        else if (expr->str() == ">=")
-            *result = result1 >= result2;
-        else if (expr->str() == "==")
-            *result = result1 == result2;
-        else if (expr->str() == "!=")
-            *result = result1 != result2;
+        bool error1 = 0;
+        bool error2 = 0;
+        execute(expr->astOperand1(), programMemory, &result1, &error1);
+        execute(expr->astOperand2(), programMemory, &result2, &error2);
+        if (error1 && error2) {
+            *error = true;
+        } else if (error1 && !error2) {
+            ValueFlow::Value v = inferCondition(expr->str(), expr->astOperand1(), result2);
+            *error = !v.isKnown();
+            *result = v.intvalue;
+        } else if (!error1 && error2) {
+            ValueFlow::Value v = inferCondition(expr->str(), result1, expr->astOperand2());
+            *error = !v.isKnown();
+            *result = v.intvalue;
+        } else {
+            if (expr->str() == "<")
+                *result = result1 < result2;
+            else if (expr->str() == "<=")
+                *result = result1 <= result2;
+            else if (expr->str() == ">")
+                *result = result1 > result2;
+            else if (expr->str() == ">=")
+                *result = result1 >= result2;
+            else if (expr->str() == "==")
+                *result = result1 == result2;
+            else if (expr->str() == "!=")
+                *result = result1 != result2;
+        }
     }
 
     else if (expr->isAssignmentOp()) {

diff --git a/lib/token.cpp b/lib/token.cpp
@@ -24,11 +24,13 @@
 #include "symboldatabase.h"
 #include "tokenlist.h"
 #include "utils.h"
+#include "valueflow.h"
 
 #include <algorithm>
 #include <cassert>
 #include <cctype>
 #include <cstring>
+#include <functional>
 #include <iostream>
 #include <map>
 #include <set>
@@ -1947,6 +1949,25 @@ const Token *Token::getValueTokenDeadPointer() const
     return nullptr;
 }
 
+static bool isAdjacent(const ValueFlow::Value& x, const ValueFlow::Value& y)
+{
+    if (x.bound != ValueFlow::Value::Bound::Point && x.bound == y.bound)
+        return true;
+    if (x.valueType == ValueFlow::Value::ValueType::FLOAT)
+        return false;
+    return std::abs(x.intvalue - y.intvalue) == 1;
+}
+
+static bool removePointValue(std::list<ValueFlow::Value>& values, ValueFlow::Value& x)
+{
+    const bool isPoint = x.bound == ValueFlow::Value::Bound::Point;
+    if (!isPoint)
+        x.decreaseRange();
+    else
+        values.remove(x);
+    return isPoint;
+}
+
 static bool removeContradiction(std::list<ValueFlow::Value>& values)
 {
     bool result = false;
@@ -1962,26 +1983,110 @@ static bool removeContradiction(std::list<ValueFlow::Value>& values)
                 continue;
             if (x.isImpossible() == y.isImpossible())
                 continue;
-            if (!x.equalValue(y))
+            if (!x.equalValue(y)) {
+                auto compare = [](const ValueFlow::Value& x, const ValueFlow::Value& y) {
+                    return x.compareValue(y, ValueFlow::less{});
+                };
+                const ValueFlow::Value& maxValue = std::max(x, y, compare);
+                const ValueFlow::Value& minValue = std::min(x, y, compare);
+                // TODO: Adjust non-points instead of removing them
+                if (maxValue.isImpossible() && maxValue.bound == ValueFlow::Value::Bound::Upper) {
+                    values.remove(minValue);
+                    return true;
+                }
+                if (minValue.isImpossible() && minValue.bound == ValueFlow::Value::Bound::Lower) {
+                    values.remove(maxValue);
+                    return true;
+                }
                 continue;
-            if (x.bound == y.bound ||
-                (x.bound != ValueFlow::Value::Bound::Point && y.bound != ValueFlow::Value::Bound::Point)) {
-                const bool removex = !x.isImpossible() || y.isKnown();
-                const bool removey = !y.isImpossible() || x.isKnown();
+            }
+            const bool removex = !x.isImpossible() || y.isKnown();
+            const bool removey = !y.isImpossible() || x.isKnown();
+            if (x.bound == y.bound) {
                 if (removex)
                     values.remove(x);
                 if (removey)
                     values.remove(y);
                 return true;
-            } else if (x.bound == ValueFlow::Value::Bound::Point) {
-                y.decreaseRange();
-                result = true;
+            } else {
+                result = removex || removey;
+                bool bail = false;
+                if (removex && removePointValue(values, x))
+                    bail = true;
+                if (removey && removePointValue(values, y))
+                    bail = true;
+                if (bail)
+                    return true;
             }
         }
     }
     return result;
 }
 
+using ValueIterator = std::list<ValueFlow::Value>::iterator;
+
+template <class Iterator>
+static ValueIterator removeAdjacentValues(std::list<ValueFlow::Value>& values, ValueIterator x, Iterator start, Iterator last)
+{
+    if (!isAdjacent(*x, **start))
+        return std::next(x);
+    auto it = std::adjacent_find(start, last, [](ValueIterator x, ValueIterator y) { return !isAdjacent(*x, *y); });
+    if (it == last)
+        it--;
+    (*it)->bound = x->bound;
+    std::for_each(start, it, [&](ValueIterator y) { values.erase(y); });
+    return values.erase(x);
+}
+
+static void mergeAdjacent(std::list<ValueFlow::Value>& values)
+{
+    for (auto x = values.begin(); x != values.end();) {
+        if (x->isNonValue()) {
+            x++;
+            continue;
+        }
+        if (x->bound == ValueFlow::Value::Bound::Point) {
+            x++;
+            continue;
+        }
+        std::vector<ValueIterator> adjValues;
+        for (auto y = values.begin(); y != values.end(); y++) {
+            if (x == y)
+                continue;
+            if (y->isNonValue())
+                continue;
+            if (x->valueType != y->valueType)
+                continue;
+            if (x->valueKind != y->valueKind)
+                continue;
+            if (x->bound != y->bound) {
+                // No adjacent points for floating points
+                if (x->valueType == ValueFlow::Value::ValueType::FLOAT)
+                    continue;
+                if (y->bound != ValueFlow::Value::Bound::Point)
+                    continue;
+            }
+            if (x->bound == ValueFlow::Value::Bound::Lower && !y->compareValue(*x, ValueFlow::less{}))
+                continue;
+            if (x->bound == ValueFlow::Value::Bound::Upper && !x->compareValue(*y, ValueFlow::less{}))
+                continue;
+            adjValues.push_back(y);
+        }
+        if (adjValues.empty()) {
+            x++;
+            continue;
+        }
+        std::sort(adjValues.begin(), adjValues.end(), [&values](ValueIterator xx, ValueIterator yy) {
+            assert(xx != values.end() && yy != values.end());
+            return xx->compareValue(*yy, ValueFlow::less{});
+        });
+        if (x->bound == ValueFlow::Value::Bound::Lower)
+            x = removeAdjacentValues(values, x, adjValues.rbegin(), adjValues.rend());
+        else if (x->bound == ValueFlow::Value::Bound::Upper)
+            x = removeAdjacentValues(values, x, adjValues.begin(), adjValues.end());
+    }
+}
+
 static void removeOverlaps(std::list<ValueFlow::Value>& values)
 {
     for (ValueFlow::Value& x : values) {
@@ -2005,12 +2110,14 @@ static void removeOverlaps(std::list<ValueFlow::Value>& values)
             return true;
         });
     }
+    mergeAdjacent(values);
 }
 
 // Removing contradictions is an NP-hard problem. Instead we run multiple
 // passes to try to catch most contradictions
 static void removeContradictions(std::list<ValueFlow::Value>& values)
 {
+    removeOverlaps(values);
     for (int i = 0; i < 4; i++) {
         if (!removeContradiction(values))
             return;