Remove adjacent values

danmar · danmar · Mar 30, 2021 · Feb 18, 2021 · Feb 18, 2021 · Feb 18, 2021
commit 2a3e9ba168fe41a34636adb6e2416ae0e168a398
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/token.cpp b/lib/token.cpp
@@ -24,10 +24,12 @@
 #include "symboldatabase.h"
 #include "tokenlist.h"
 #include "utils.h"
+#include "valueflow.h"
 
 #include <algorithm>
 #include <cassert>
 #include <cctype>
+#include <cstdlib>
 #include <cstring>
 #include <iostream>
 #include <map>
@@ -2015,6 +2017,94 @@ static void removeContradictions(std::list<ValueFlow::Value>& values)
     }
 }
 
+static bool isAdjacent(const ValueFlow::Value& x, const ValueFlow::Value& y)
+{
+    if (x.bound == y.bound) {
+        return true;
+    } else {
+        if (x.valueType == ValueFlow::Value::ValueType::FLOAT)
+            return false;
+        return std::abs(x.intvalue - y.intvalue) == 1;
+    }
+}
+
+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);
+    });
+    auto end = std::prev(last);
+    if (it != last) {
+        assert(*it != x);
+        end = std::next(it);
+    }
+    (*end)->bound = x->bound;
+    std::for_each(start, end, [&](ValueIterator y) {
+        values.erase(y);
+    });
+    return values.erase(x);
+}
+
+static void mergeAdjacent(std::list<ValueFlow::Value>& values)
+{
+    auto prev = values.end();
+    for (auto x = values.begin(); x != values.end();) {
+        if (x == prev)
+            printf("Infinite\n");
+        // assert(x != prev);
+        prev = x;
+        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());
+
+    }
+}
+
 bool Token::addValue(const ValueFlow::Value &value)
 {
     if (value.isKnown() && mImpl->mValues) {
@@ -2100,6 +2190,8 @@ bool Token::addValue(const ValueFlow::Value &value)
         mImpl->mValues = new std::list<ValueFlow::Value>(1, v);
     }
 
+    removeOverlaps(*mImpl->mValues);
+    mergeAdjacent(*mImpl->mValues);
     removeContradictions(*mImpl->mValues);
 
     return true;

diff --git a/lib/valueflow.cpp b/lib/valueflow.cpp
@@ -1431,6 +1431,49 @@ static void valueFlowRightShift(TokenList *tokenList, const Settings* settings)
     }
 }
 
+static std::vector<MathLib::bigint> minUnsignedValue(const Token* tok, int depth = 8)
+{
+    std::vector<MathLib::bigint> result = {};
+    if (!tok)
+        return result;
+    if (depth < 0)
+        return result;
+    if (tok->hasKnownIntValue()) {
+        result = {tok->values().front().intvalue};
+    } else if (tok->isConstOp() && tok->astOperand1() && tok->astOperand2()) {
+        std::vector<MathLib::bigint> op1 = minUnsignedValue(tok->astOperand1(), depth - 1);
+        std::vector<MathLib::bigint> op2 = minUnsignedValue(tok->astOperand2(), depth - 1);
+        if (!op1.empty() && !op2.empty())
+            result = {calculate(tok->str(), op1.front(), op2.front())};
+    }
+    if (result.empty() && astIsUnsigned(tok))
+        result = {0};
+    return result;
+}
+
+static void valueFlowImpossibleValues(TokenList *tokenList, const Settings* settings)
+{
+    for (Token *tok = tokenList->front(); tok; tok = tok->next()) {
+        if (tok->hasKnownIntValue())
+            continue;
+        if (astIsUnsigned(tok)) {
+            std::vector<MathLib::bigint> minvalue = minUnsignedValue(tok);
+            if (minvalue.empty())
+                continue;
+            ValueFlow::Value value{std::max<MathLib::bigint>(0, minvalue.front()) - 1};
+            value.bound = ValueFlow::Value::Bound::Upper;
+            value.setImpossible();
+            setTokenValue(tok, value, settings);
+        }
+        if (Token::simpleMatch(tok, "%") && tok->astOperand2() && tok->astOperand2()->hasKnownIntValue()) {
+            ValueFlow::Value value{tok->astOperand2()->values().front()};
+            value.bound = ValueFlow::Value::Bound::Lower;
+            value.setImpossible();
+            setTokenValue(tok, value, settings);
+        }
+    }
+}
+
 static void valueFlowEnumValue(SymbolDatabase * symboldatabase, const Settings * settings)
 {
 
@@ -4692,26 +4735,6 @@ static const ValueFlow::Value* proveNotEqual(const std::list<ValueFlow::Value>&
     return result;
 }
 
-static std::vector<MathLib::bigint> minUnsignedValue(const Token* tok, int depth = 8)
-{
-    std::vector<MathLib::bigint> result = {};
-    if (!tok)
-        return result;
-    if (depth < 0)
-        return result;
-    if (tok->hasKnownIntValue()) {
-        result = {tok->values().front().intvalue};
-    } else if (tok->isConstOp() && tok->astOperand1() && tok->astOperand2()) {
-        std::vector<MathLib::bigint> op1 = minUnsignedValue(tok->astOperand1(), depth - 1);
-        std::vector<MathLib::bigint> op2 = minUnsignedValue(tok->astOperand2(), depth - 1);
-        if (!op1.empty() && !op1.empty())
-            result = {calculate(tok->str(), op1.front(), op2.front())};
-    }
-    if (result.empty() && tok->valueType() && tok->valueType()->sign == ValueType::UNSIGNED)
-        result = {0};
-    return result;
-}
-
 ValueFlow::Value inferCondition(const std::string& op, const Token* varTok, MathLib::bigint val)
 {
     if (!varTok)
@@ -4721,19 +4744,6 @@ ValueFlow::Value inferCondition(const std::string& op, const Token* varTok, Math
     if (std::none_of(varTok->values().begin(), varTok->values().end(), [](const ValueFlow::Value& v) {
         return v.isImpossible() && v.valueType == ValueFlow::Value::ValueType::INT;
     })) {
-        if (varTok->valueType() && varTok->valueType()->sign == ValueType::UNSIGNED && (op == ">" || op == ">=")) {
-            std::vector<MathLib::bigint> minvalue = minUnsignedValue(varTok);
-            if (minvalue.empty())
-                return ValueFlow::Value{};
-            bool isTrue = calculate(op, std::max<MathLib::bigint>(0, minvalue.front()), val);
-            if (!isTrue)
-                return ValueFlow::Value{};
-            ValueFlow::Value value;
-            value.intvalue = 1;
-            value.bound = ValueFlow::Value::Bound::Point;
-            value.setKnown();
-            return value;
-        }
         return ValueFlow::Value{};
     }
     const ValueFlow::Value* result = nullptr;
@@ -6798,6 +6808,7 @@ void ValueFlow::setValues(TokenList *tokenlist, SymbolDatabase* symboldatabase,
     std::size_t n = 4;
     while (n > 0 && values < getTotalValues(tokenlist)) {
         values = getTotalValues(tokenlist);
+        valueFlowImpossibleValues(tokenlist, settings);
         valueFlowPointerAliasDeref(tokenlist);
         valueFlowArrayBool(tokenlist);
         valueFlowRightShift(tokenlist, settings);

diff --git a/lib/valueflow.h b/lib/valueflow.h
@@ -21,6 +21,7 @@
 #define valueflowH
 //---------------------------------------------------------------------------
 
+#include "astutils.h"
 #include "config.h"
 #include "mathlib.h"
 #include "utils.h"
@@ -54,6 +55,20 @@ namespace ValueFlow {
         }
     };
 
+    struct less {
+        template<class T, class U>
+        bool operator()(const T& x, const U& y) const {
+            return x < y;
+        }
+    };
+
+    struct adjacent {
+        template<class T, class U>
+        bool operator()(const T& x, const U& y) const {
+            return std::abs(x - y) == 1;
+        }
+    };
+
     struct equalVisitor {
         template <class T, class U>
         void operator()(bool& result, T x, U y) const {
@@ -143,6 +158,28 @@ namespace ValueFlow {
             }
         }
 
+        struct compareVisitor {
+            struct innerVisitor {
+                template<class Compare, class T, class U>
+                void operator()(bool& result, Compare compare, T x, U y) const {
+                    result = compare(x, y);
+                }
+            };
+            template<class Compare, class T>
+            void operator()(bool& result, const Value& rhs, Compare compare, T x) const {
+                visitValue(rhs, std::bind(innerVisitor{}, std::ref(result), std::move(compare), x, std::placeholders::_1));
+            }
+
+        };
+
+        template<class Compare>
+        bool compareValue(const Value& rhs, Compare compare) const
+        {
+            bool result = false;
+            visitValue(*this, std::bind(compareVisitor{}, std::ref(result), std::ref(rhs), std::move(compare), std::placeholders::_1));
+            return result;
+        }
+
         bool operator==(const Value &rhs) const {
             if (!equalValue(rhs))
                 return false;