Line data    Source code

       1             : /*
       2             :  * Cppcheck - A tool for static C/C++ code analysis
       3             :  * Copyright (C) 2007-2023 Cppcheck team.
       4             :  *
       5             :  * This program is free software: you can redistribute it and/or modify
       6             :  * it under the terms of the GNU General Public License as published by
       7             :  * the Free Software Foundation, either version 3 of the License, or
       8             :  * (at your option) any later version.
       9             :  *
      10             :  * This program is distributed in the hope that it will be useful,
      11             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13             :  * GNU General Public License for more details.
      14             :  *
      15             :  * You should have received a copy of the GNU General Public License
      16             :  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
      17             :  */
      18             : 
      19             : #include "infer.h"
      20             : 
      21             : #include "calculate.h"
      22             : #include "errortypes.h"
      23             : #include "valueptr.h"
      24             : 
      25             : #include <cassert>
      26             : #include <algorithm>
      27             : #include <functional>
      28             : #include <iterator>
      29             : #include <unordered_set>
      30             : #include <utility>
      31             : 
      32             : class Token;
      33             : 
      34             : template<class Predicate, class Compare>
      35      286145 : static const ValueFlow::Value* getCompareValue(const std::list<ValueFlow::Value>& values, Predicate pred, Compare compare)
      36             : {
      37      286145 :     const ValueFlow::Value* result = nullptr;
      38      758118 :     for (const ValueFlow::Value& value : values) {
      39      471973 :         if (!pred(value))
      40        1316 :             continue;
      41      470657 :         if (result)
      42      370972 :             result = &std::min(value, *result, [compare](const ValueFlow::Value& x, const ValueFlow::Value& y) {
      43      185486 :                 return compare(x.intvalue, y.intvalue);
      44             :             });
      45             :         else
      46      285171 :             result = &value;
      47             :     }
      48      286145 :     return result;
      49             : }
      50             : 
      51             : namespace {
      52             :     struct Interval {
      53             :         std::vector<MathLib::bigint> minvalue, maxvalue;
      54             :         std::vector<const ValueFlow::Value*> minRef, maxRef;
      55             : 
      56      152368 :         void setMinValue(MathLib::bigint x, const ValueFlow::Value* ref = nullptr)
      57             :         {
      58      152368 :             minvalue = {x};
      59      152368 :             if (ref)
      60      152368 :                 minRef = {ref};
      61      152368 :         }
      62             : 
      63      115964 :         void setMaxValue(MathLib::bigint x, const ValueFlow::Value* ref = nullptr)
      64             :         {
      65      115964 :             maxvalue = {x};
      66      115964 :             if (ref)
      67      115964 :                 maxRef = {ref};
      68      115964 :         }
      69             : 
      70      116559 :         bool isLessThan(MathLib::bigint x, std::vector<const ValueFlow::Value*>* ref = nullptr) const
      71             :         {
      72      116559 :             if (!this->maxvalue.empty() && this->maxvalue.front() < x) {
      73        9182 :                 if (ref)
      74        9182 :                     *ref = maxRef;
      75        9182 :                 return true;
      76             :             }
      77      107377 :             return false;
      78             :         }
      79             : 
      80      134871 :         bool isGreaterThan(MathLib::bigint x, std::vector<const ValueFlow::Value*>* ref = nullptr) const
      81             :         {
      82      134871 :             if (!this->minvalue.empty() && this->minvalue.front() > x) {
      83       18312 :                 if (ref)
      84       18312 :                     *ref = minRef;
      85       18312 :                 return true;
      86             :             }
      87      116559 :             return false;
      88             :         }
      89             : 
      90      217952 :         bool isScalar() const {
      91      217952 :             return minvalue.size() == 1 && minvalue == maxvalue;
      92             :         }
      93             : 
      94       70415 :         bool empty() const {
      95       70415 :             return minvalue.empty() && maxvalue.empty();
      96             :         }
      97             : 
      98       70415 :         bool isScalarOrEmpty() const {
      99       70415 :             return empty() || isScalar();
     100             :         }
     101             : 
     102       25631 :         MathLib::bigint getScalar() const
     103             :         {
     104       25631 :             assert(isScalar());
     105       25631 :             return minvalue.front();
     106             :         }
     107             : 
     108       10418 :         std::vector<const ValueFlow::Value*> getScalarRef() const
     109             :         {
     110       10418 :             assert(isScalar());
     111       10418 :             if (minRef != maxRef)
     112          44 :                 return merge(minRef, maxRef);
     113       10374 :             return minRef;
     114             :         }
     115             : 
     116       95133 :         static Interval fromInt(MathLib::bigint x, const ValueFlow::Value* ref = nullptr)
     117             :         {
     118       95133 :             Interval result;
     119       95133 :             result.setMinValue(x, ref);
     120       95133 :             result.setMaxValue(x, ref);
     121       95133 :             return result;
     122             :         }
     123             : 
     124             :         template<class Predicate>
     125      190639 :         static Interval fromValues(const std::list<ValueFlow::Value>& values, Predicate predicate)
     126             :         {
     127      381278 :             Interval result;
     128      190639 :             const ValueFlow::Value* minValue = getCompareValue(values, predicate, std::less<MathLib::bigint>{});
     129      190639 :             if (minValue) {
     130      190152 :                 if (minValue->isImpossible() && minValue->bound == ValueFlow::Value::Bound::Upper)
     131       56987 :                     result.setMinValue(minValue->intvalue + 1, minValue);
     132      190152 :                 if (minValue->isPossible() && minValue->bound == ValueFlow::Value::Bound::Lower)
     133         248 :                     result.setMinValue(minValue->intvalue, minValue);
     134      291222 :                 if (!minValue->isImpossible() && (minValue->bound == ValueFlow::Value::Bound::Point || minValue->isKnown()) &&
     135      101070 :                     std::count_if(values.begin(), values.end(), predicate) == 1)
     136       95133 :                     return Interval::fromInt(minValue->intvalue, minValue);
     137             :             }
     138       95506 :             const ValueFlow::Value* maxValue = getCompareValue(values, predicate, std::greater<MathLib::bigint>{});
     139       95506 :             if (maxValue) {
     140       95019 :                 if (maxValue->isImpossible() && maxValue->bound == ValueFlow::Value::Bound::Lower)
     141       20304 :                     result.setMaxValue(maxValue->intvalue - 1, maxValue);
     142       95019 :                 if (maxValue->isPossible() && maxValue->bound == ValueFlow::Value::Bound::Upper)
     143         527 :                     result.setMaxValue(maxValue->intvalue, maxValue);
     144       95019 :                 assert(!maxValue->isKnown());
     145             :             }
     146       95506 :             return result;
     147             :         }
     148             : 
     149      189218 :         static Interval fromValues(const std::list<ValueFlow::Value>& values)
     150             :         {
     151      576203 :             return Interval::fromValues(values, [](const ValueFlow::Value&) {
     152      576203 :                 return true;
     153      189218 :             });
     154             :         }
     155             : 
     156             :         template<class F>
     157      143260 :         static std::vector<MathLib::bigint> apply(const std::vector<MathLib::bigint>& x,
     158             :                                                   const std::vector<MathLib::bigint>& y,
     159             :                                                   F f)
     160             :         {
     161      143260 :             if (x.empty())
     162       65248 :                 return {};
     163       78012 :             if (y.empty())
     164        5087 :                 return {};
     165      145850 :             return {f(x.front(), y.front())};
     166             :         }
     167             : 
     168       75944 :         static std::vector<const ValueFlow::Value*> merge(std::vector<const ValueFlow::Value*> x,
     169             :                                                           const std::vector<const ValueFlow::Value*>& y)
     170             :         {
     171       75944 :             x.insert(x.end(), y.cbegin(), y.cend());
     172       75944 :             return x;
     173             :         }
     174             : 
     175       71630 :         friend Interval operator-(const Interval& lhs, const Interval& rhs)
     176             :         {
     177       71630 :             Interval result;
     178       71630 :             result.minvalue = Interval::apply(lhs.minvalue, rhs.maxvalue, std::minus<MathLib::bigint>{});
     179       71630 :             result.maxvalue = Interval::apply(lhs.maxvalue, rhs.minvalue, std::minus<MathLib::bigint>{});
     180       71630 :             if (!result.minvalue.empty())
     181       51364 :                 result.minRef = merge(lhs.minRef, rhs.maxRef);
     182       71630 :             if (!result.maxvalue.empty())
     183       21561 :                 result.maxRef = merge(lhs.maxRef, rhs.minRef);
     184       71630 :             return result;
     185             :         }
     186             : 
     187       63826 :         static std::vector<int> equal(const Interval& lhs,
     188             :                                       const Interval& rhs,
     189             :                                       std::vector<const ValueFlow::Value*>* ref = nullptr)
     190             :         {
     191       63826 :             if (!lhs.isScalar())
     192       62261 :                 return {};
     193        1565 :             if (!rhs.isScalar())
     194        1244 :                 return {};
     195         321 :             if (ref)
     196         321 :                 *ref = merge(lhs.getScalarRef(), rhs.getScalarRef());
     197         642 :             return {lhs.minvalue == rhs.minvalue};
     198             :         }
     199             : 
     200       71366 :         static std::vector<int> compare(const Interval& lhs,
     201             :                                         const Interval& rhs,
     202             :                                         std::vector<const ValueFlow::Value*>* ref = nullptr)
     203             :         {
     204      142732 :             Interval diff = lhs - rhs;
     205       71366 :             if (diff.isGreaterThan(0, ref))
     206        4128 :                 return {1};
     207       69302 :             if (diff.isLessThan(0, ref))
     208       10952 :                 return {-1};
     209      127652 :             std::vector<int> eq = Interval::equal(lhs, rhs, ref);
     210       63826 :             if (!eq.empty()) {
     211         321 :                 if (eq.front() == 0)
     212           0 :                     return {1, -1};
     213         642 :                 return {0};
     214             :             }
     215       63505 :             if (diff.isGreaterThan(-1, ref))
     216       32496 :                 return {0, 1};
     217       47257 :             if (diff.isLessThan(1, ref))
     218        7412 :                 return {0, -1};
     219       43551 :             return {};
     220             :         }
     221             : 
     222       71366 :         static std::vector<bool> compare(const std::string& op,
     223             :                                          const Interval& lhs,
     224             :                                          const Interval& rhs,
     225             :                                          std::vector<const ValueFlow::Value*>* ref = nullptr)
     226             :         {
     227      142732 :             std::vector<int> r = compare(lhs, rhs, ref);
     228       71366 :             if (r.empty())
     229       43551 :                 return {};
     230       27815 :             bool b = calculate(op, r.front(), 0);
     231       27815 :             if (std::all_of(r.cbegin() + 1, r.cend(), [&](int i) {
     232       19954 :                 return b == calculate(op, i, 0);
     233             :             }))
     234       21206 :                 return {b};
     235       17212 :             return {};
     236             :         }
     237             :     };
     238             : }
     239             : 
     240       17833 : static void addToErrorPath(ValueFlow::Value& value, const std::vector<const ValueFlow::Value*>& refs)
     241             : {
     242       35666 :     std::unordered_set<const Token*> locations;
     243       49212 :     for (const ValueFlow::Value* ref : refs) {
     244       31379 :         if (ref->condition && !value.condition)
     245        7220 :             value.condition = ref->condition;
     246             :         std::copy_if(ref->errorPath.cbegin(),
     247             :                      ref->errorPath.cend(),
     248       31379 :                      std::back_inserter(value.errorPath),
     249       13220 :                      [&](const ErrorPathItem& e) {
     250       13220 :             return locations.insert(e.first).second;
     251       31379 :         });
     252             :         std::copy_if(ref->debugPath.cbegin(),
     253             :                      ref->debugPath.cend(),
     254       31379 :                      std::back_inserter(value.debugPath),
     255           0 :                      [&](const ErrorPathItem& e) {
     256           0 :             return locations.insert(e.first).second;
     257       31379 :         });
     258             :     }
     259       17833 : }
     260             : 
     261       17725 : static void setValueKind(ValueFlow::Value& value, const std::vector<const ValueFlow::Value*>& refs)
     262             : {
     263       17725 :     bool isPossible = false;
     264       17725 :     bool isInconclusive = false;
     265       48888 :     for (const ValueFlow::Value* ref : refs) {
     266       31163 :         if (ref->isPossible())
     267        4671 :             isPossible = true;
     268       31163 :         if (ref->isInconclusive())
     269         124 :             isInconclusive = true;
     270             :     }
     271       17725 :     if (isInconclusive)
     272         124 :         value.setInconclusive();
     273       17601 :     else if (isPossible)
     274        4644 :         value.setPossible();
     275             :     else
     276       12957 :         value.setKnown();
     277       17725 : }
     278             : 
     279       20188 : static bool inferNotEqual(const std::list<ValueFlow::Value>& values, MathLib::bigint x)
     280             : {
     281       20188 :     return std::any_of(values.cbegin(), values.cend(), [&](const ValueFlow::Value& value) {
     282       42987 :         return value.isImpossible() && value.intvalue == x;
     283       20188 :     });
     284             : }
     285             : 
     286      196034 : std::vector<ValueFlow::Value> infer(const ValuePtr<InferModel>& model,
     287             :                                     const std::string& op,
     288             :                                     std::list<ValueFlow::Value> lhsValues,
     289             :                                     std::list<ValueFlow::Value> rhsValues)
     290             : {
     291      196034 :     std::vector<ValueFlow::Value> result;
     292      404352 :     auto notMatch = [&](const ValueFlow::Value& value) {
     293      404352 :         return !model->match(value);
     294      196034 :     };
     295      196034 :     lhsValues.remove_if(notMatch);
     296      196034 :     rhsValues.remove_if(notMatch);
     297      196034 :     if (lhsValues.empty() || rhsValues.empty())
     298      101425 :         return result;
     299             : 
     300      189218 :     Interval lhs = Interval::fromValues(lhsValues);
     301      189218 :     Interval rhs = Interval::fromValues(rhsValues);
     302             : 
     303       94609 :     if (op == "-") {
     304         528 :         Interval diff = lhs - rhs;
     305         264 :         if (diff.isScalar()) {
     306         270 :             std::vector<const ValueFlow::Value*> refs = diff.getScalarRef();
     307         270 :             ValueFlow::Value value(diff.getScalar());
     308         135 :             addToErrorPath(value, refs);
     309         135 :             setValueKind(value, refs);
     310         135 :             result.push_back(std::move(value));
     311             :         } else {
     312         129 :             if (!diff.minvalue.empty()) {
     313         168 :                 ValueFlow::Value value(diff.minvalue.front() - 1);
     314          84 :                 value.setImpossible();
     315          84 :                 value.bound = ValueFlow::Value::Bound::Upper;
     316          84 :                 addToErrorPath(value, diff.minRef);
     317          84 :                 result.push_back(std::move(value));
     318             :             }
     319         129 :             if (!diff.maxvalue.empty()) {
     320          48 :                 ValueFlow::Value value(diff.maxvalue.front() + 1);
     321          24 :                 value.setImpossible();
     322          24 :                 value.bound = ValueFlow::Value::Bound::Lower;
     323          24 :                 addToErrorPath(value, diff.maxRef);
     324          24 :                 result.push_back(std::move(value));
     325             :             }
     326             :         }
     327       94345 :     } else if ((op == "!=" || op == "==") && lhs.isScalarOrEmpty() && rhs.isScalarOrEmpty()) {
     328       22979 :         if (lhs.isScalar() && rhs.isScalar()) {
     329        7962 :             std::vector<const ValueFlow::Value*> refs = Interval::merge(lhs.getScalarRef(), rhs.getScalarRef());
     330        5308 :             ValueFlow::Value value(calculate(op, lhs.getScalar(), rhs.getScalar()));
     331        2654 :             addToErrorPath(value, refs);
     332        2654 :             setValueKind(value, refs);
     333        2654 :             result.push_back(std::move(value));
     334             :         } else {
     335       40650 :             std::vector<const ValueFlow::Value*> refs;
     336       20325 :             if (lhs.isScalar() && inferNotEqual(rhsValues, lhs.getScalar()))
     337          22 :                 refs = lhs.getScalarRef();
     338       20303 :             else if (rhs.isScalar() && inferNotEqual(lhsValues, rhs.getScalar()))
     339        4311 :                 refs = rhs.getScalarRef();
     340       20325 :             if (!refs.empty()) {
     341        8666 :                 ValueFlow::Value value(op == "!=");
     342        4333 :                 addToErrorPath(value, refs);
     343        4333 :                 setValueKind(value, refs);
     344        4333 :                 result.push_back(std::move(value));
     345             :             }
     346             :         }
     347             :     } else {
     348      142732 :         std::vector<const ValueFlow::Value*> refs;
     349      142732 :         std::vector<bool> r = Interval::compare(op, lhs, rhs, &refs);
     350       71366 :         if (!r.empty()) {
     351       21206 :             ValueFlow::Value value(r.front());
     352       10603 :             addToErrorPath(value, refs);
     353       10603 :             setValueKind(value, refs);
     354       10603 :             result.push_back(std::move(value));
     355             :         }
     356             :     }
     357             : 
     358       94609 :     return result;
     359             : }
     360             : 
     361        2905 : std::vector<ValueFlow::Value> infer(const ValuePtr<InferModel>& model,
     362             :                                     const std::string& op,
     363             :                                     MathLib::bigint lhs,
     364             :                                     std::list<ValueFlow::Value> rhsValues)
     365             : {
     366        5810 :     return infer(model, op, {model->yield(lhs)}, std::move(rhsValues));
     367             : }
     368             : 
     369       27085 : std::vector<ValueFlow::Value> infer(const ValuePtr<InferModel>& model,
     370             :                                     const std::string& op,
     371             :                                     std::list<ValueFlow::Value> lhsValues,
     372             :                                     MathLib::bigint rhs)
     373             : {
     374       54170 :     return infer(model, op, std::move(lhsValues), {model->yield(rhs)});
     375             : }
     376             : 
     377        1421 : std::vector<MathLib::bigint> getMinValue(const ValuePtr<InferModel>& model, const std::list<ValueFlow::Value>& values)
     378             : {
     379        1421 :     return Interval::fromValues(values, [&](const ValueFlow::Value& v) {
     380        3236 :         return model->match(v);
     381        1421 :     }).minvalue;
     382             : }
     383           0 : std::vector<MathLib::bigint> getMaxValue(const ValuePtr<InferModel>& model, const std::list<ValueFlow::Value>& values)
     384             : {
     385           0 :     return Interval::fromValues(values, [&](const ValueFlow::Value& v) {
     386           0 :         return model->match(v);
     387           0 :     }).maxvalue;
     388             : }