Cppcheck
programmemory.cpp
Go to the documentation of this file.
1 /*
2  * Cppcheck - A tool for static C/C++ code analysis
3  * Copyright (C) 2007-2024 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 "programmemory.h"
20 
21 #include "astutils.h"
22 #include "calculate.h"
23 #include "infer.h"
24 #include "library.h"
25 #include "mathlib.h"
26 #include "settings.h"
27 #include "symboldatabase.h"
28 #include "token.h"
29 #include "utils.h"
30 #include "valueflow.h"
31 #include "valueptr.h"
32 
33 #include <algorithm>
34 #include <cassert>
35 #include <cmath>
36 #include <functional>
37 #include <iterator>
38 #include <list>
39 #include <memory>
40 #include <string>
41 #include <utility>
42 #include <vector>
43 
44 ExprIdToken::ExprIdToken(const Token* tok) : tok(tok), exprid(tok ? tok->exprId() : 0) {}
45 
47  return tok ? tok->exprId() : exprid;
48 }
49 
51 {
52  return std::hash<nonneg int>()(etok.getExpressionId());
53 }
54 
55 void ProgramMemory::setValue(const Token* expr, const ValueFlow::Value& value) {
56  mValues[expr] = value;
57  ValueFlow::Value subvalue = value;
58  const Token* subexpr = solveExprValue(
59  expr,
60  [&](const Token* tok) -> std::vector<MathLib::bigint> {
61  if (tok->hasKnownIntValue())
62  return {tok->values().front().intvalue};
63  MathLib::bigint result = 0;
64  if (getIntValue(tok->exprId(), result))
65  return {result};
66  return {};
67  },
68  subvalue);
69  if (subexpr)
70  mValues[subexpr] = std::move(subvalue);
71 }
72 const ValueFlow::Value* ProgramMemory::getValue(nonneg int exprid, bool impossible) const
73 {
74  const ProgramMemory::Map::const_iterator it = mValues.find(exprid);
75  const bool found = it != mValues.cend() && (impossible || !it->second.isImpossible());
76  if (found)
77  return &it->second;
78  return nullptr;
79 }
80 
81 // cppcheck-suppress unusedFunction
83 {
84  const ValueFlow::Value* value = getValue(exprid);
85  if (value && value->isIntValue()) {
86  result = value->intvalue;
87  return true;
88  }
89  return false;
90 }
91 
92 void ProgramMemory::setIntValue(const Token* expr, MathLib::bigint value, bool impossible)
93 {
94  ValueFlow::Value v(value);
95  if (impossible)
96  v.setImpossible();
97  setValue(expr, v);
98 }
99 
100 bool ProgramMemory::getTokValue(nonneg int exprid, const Token*& result) const
101 {
102  const ValueFlow::Value* value = getValue(exprid);
103  if (value && value->isTokValue()) {
104  result = value->tokvalue;
105  return true;
106  }
107  return false;
108 }
109 
110 // cppcheck-suppress unusedFunction
112 {
113  const ValueFlow::Value* value = getValue(exprid);
114  if (value && value->isContainerSizeValue()) {
115  result = value->intvalue;
116  return true;
117  }
118  return false;
119 }
121 {
122  const ValueFlow::Value* value = getValue(exprid, true);
123  if (value && value->isContainerSizeValue()) {
124  if (value->isImpossible() && value->intvalue == 0) {
125  result = false;
126  return true;
127  }
128  if (!value->isImpossible()) {
129  result = (value->intvalue == 0);
130  return true;
131  }
132  }
133  return false;
134 }
135 
137 {
138  ValueFlow::Value v(value);
140  if (!isEqual)
142  setValue(expr, v);
143 }
144 
145 void ProgramMemory::setUnknown(const Token* expr) {
146  mValues[expr].valueType = ValueFlow::Value::ValueType::UNINIT;
147 }
148 
150 {
151  return mValues.find(exprid) != mValues.end();
152 }
153 
155  return mValues.at(exprid);
156 }
158  return mValues.at(exprid);
159 }
160 
161 void ProgramMemory::erase_if(const std::function<bool(const ExprIdToken&)>& pred)
162 {
163  for (auto it = mValues.begin(); it != mValues.end();) {
164  if (pred(it->first))
165  it = mValues.erase(it);
166  else
167  ++it;
168  }
169 }
170 
172 {
173  mValues.swap(pm.mValues);
174 }
175 
177 {
178  mValues.clear();
179 }
180 
182 {
183  return mValues.empty();
184 }
185 
187 {
188  for (auto&& p : pm.mValues) {
189  mValues[p.first] = std::move(p.second);
190  }
191 }
192 
194 {
195  for (auto&& p : pm)
196  mValues.insert(p);
197 }
198 
199 static ValueFlow::Value execute(const Token* expr, ProgramMemory& pm, const Settings& settings);
200 
201 static bool evaluateCondition(MathLib::bigint r, const Token* condition, ProgramMemory& pm, const Settings& settings)
202 {
203  if (!condition)
204  return false;
205  MathLib::bigint result = 0;
206  bool error = false;
207  execute(condition, pm, &result, &error, settings);
208  return !error && result == r;
209 }
210 
211 bool conditionIsFalse(const Token* condition, ProgramMemory pm, const Settings& settings)
212 {
213  return evaluateCondition(0, condition, pm, settings);
214 }
215 
216 bool conditionIsTrue(const Token* condition, ProgramMemory pm, const Settings& settings)
217 {
218  return evaluateCondition(1, condition, pm, settings);
219 }
220 
221 static bool frontIs(const std::vector<MathLib::bigint>& v, bool i)
222 {
223  if (v.empty())
224  return false;
225  if (v.front())
226  return i;
227  return !i;
228 }
229 
230 static bool isTrue(const ValueFlow::Value& v)
231 {
232  if (v.isUninitValue())
233  return false;
234  if (v.isImpossible())
235  return v.intvalue == 0;
236  return v.intvalue != 0;
237 }
238 
239 static bool isFalse(const ValueFlow::Value& v)
240 {
241  if (v.isUninitValue())
242  return false;
243  if (v.isImpossible())
244  return false;
245  return v.intvalue == 0;
246 }
247 
248 static bool isTrueOrFalse(const ValueFlow::Value& v, bool b)
249 {
250  if (b)
251  return isTrue(v);
252  return isFalse(v);
253 }
254 
255 // If the scope is a non-range for loop
256 static bool isBasicForLoop(const Token* tok)
257 {
258  if (!tok)
259  return false;
260  if (Token::simpleMatch(tok, "}"))
261  return isBasicForLoop(tok->link());
262  if (!Token::simpleMatch(tok->previous(), ") {"))
263  return false;
264  const Token* start = tok->linkAt(-1);
265  if (!start)
266  return false;
267  if (!Token::simpleMatch(start->previous(), "for ("))
268  return false;
269  if (!Token::simpleMatch(start->astOperand2(), ";"))
270  return false;
271  return true;
272 }
273 
274 static void programMemoryParseCondition(ProgramMemory& pm, const Token* tok, const Token* endTok, const Settings& settings, bool then)
275 {
276  auto eval = [&](const Token* t) -> std::vector<MathLib::bigint> {
277  if (!t)
278  return std::vector<MathLib::bigint>{};
279  if (t->hasKnownIntValue())
280  return {t->values().front().intvalue};
281  MathLib::bigint result = 0;
282  bool error = false;
283  execute(t, pm, &result, &error, settings);
284  if (!error)
285  return {result};
286  return std::vector<MathLib::bigint>{};
287  };
288  if (Token::Match(tok, "==|>=|<=|<|>|!=")) {
289  ValueFlow::Value truevalue;
290  ValueFlow::Value falsevalue;
291  const Token* vartok = parseCompareInt(tok, truevalue, falsevalue, eval);
292  if (!vartok)
293  return;
294  if (vartok->exprId() == 0)
295  return;
296  if (!truevalue.isIntValue())
297  return;
298  if (endTok && findExpressionChanged(vartok, tok->next(), endTok, settings))
299  return;
300  const bool impossible = (tok->str() == "==" && !then) || (tok->str() == "!=" && then);
301  const ValueFlow::Value& v = then ? truevalue : falsevalue;
302  pm.setValue(vartok, impossible ? asImpossible(v) : v);
303  const Token* containerTok = settings.library.getContainerFromYield(vartok, Library::Container::Yield::SIZE);
304  if (containerTok)
305  pm.setContainerSizeValue(containerTok, v.intvalue, !impossible);
306  } else if (Token::simpleMatch(tok, "!")) {
307  programMemoryParseCondition(pm, tok->astOperand1(), endTok, settings, !then);
308  } else if (then && Token::simpleMatch(tok, "&&")) {
309  programMemoryParseCondition(pm, tok->astOperand1(), endTok, settings, then);
310  programMemoryParseCondition(pm, tok->astOperand2(), endTok, settings, then);
311  } else if (!then && Token::simpleMatch(tok, "||")) {
312  programMemoryParseCondition(pm, tok->astOperand1(), endTok, settings, then);
313  programMemoryParseCondition(pm, tok->astOperand2(), endTok, settings, then);
314  } else if (Token::Match(tok, "&&|%oror%")) {
315  std::vector<MathLib::bigint> lhs = eval(tok->astOperand1());
316  std::vector<MathLib::bigint> rhs = eval(tok->astOperand2());
317  if (lhs.empty() || rhs.empty()) {
318  if (frontIs(lhs, !then))
319  programMemoryParseCondition(pm, tok->astOperand2(), endTok, settings, then);
320  else if (frontIs(rhs, !then))
321  programMemoryParseCondition(pm, tok->astOperand1(), endTok, settings, then);
322  else
323  pm.setIntValue(tok, 0, then);
324  }
325  } else if (tok && tok->exprId() > 0) {
326  if (endTok && findExpressionChanged(tok, tok->next(), endTok, settings))
327  return;
328  pm.setIntValue(tok, 0, then);
330  if (containerTok)
331  pm.setContainerSizeValue(containerTok, 0, then);
332  }
333 }
334 
335 static void fillProgramMemoryFromConditions(ProgramMemory& pm, const Scope* scope, const Token* endTok, const Settings& settings)
336 {
337  if (!scope)
338  return;
339  if (!scope->isLocal())
340  return;
341  assert(scope != scope->nestedIn);
342  fillProgramMemoryFromConditions(pm, scope->nestedIn, endTok, settings);
343  if (scope->type == Scope::eIf || scope->type == Scope::eWhile || scope->type == Scope::eElse || scope->type == Scope::eFor) {
344  const Token* condTok = getCondTokFromEnd(scope->bodyEnd);
345  if (!condTok)
346  return;
347  MathLib::bigint result = 0;
348  bool error = false;
349  execute(condTok, pm, &result, &error, settings);
350  if (error)
351  programMemoryParseCondition(pm, condTok, endTok, settings, scope->type != Scope::eElse);
352  }
353 }
354 
355 static void fillProgramMemoryFromConditions(ProgramMemory& pm, const Token* tok, const Settings& settings)
356 {
357  fillProgramMemoryFromConditions(pm, tok->scope(), tok, settings);
358 }
359 
360 static void fillProgramMemoryFromAssignments(ProgramMemory& pm, const Token* tok, const Settings& settings, const ProgramMemory& state, const ProgramMemory::Map& vars)
361 {
362  int indentlevel = 0;
363  for (const Token *tok2 = tok; tok2; tok2 = tok2->previous()) {
364  if ((Token::simpleMatch(tok2, "=") || Token::Match(tok2->previous(), "%var% (|{")) && tok2->astOperand1() &&
365  tok2->astOperand2()) {
366  bool setvar = false;
367  const Token* vartok = tok2->astOperand1();
368  for (const auto& p:vars) {
369  if (p.first != vartok->exprId())
370  continue;
371  if (vartok == tok)
372  continue;
373  pm.setValue(vartok, p.second);
374  setvar = true;
375  }
376  if (!setvar) {
377  if (!pm.hasValue(vartok->exprId())) {
378  const Token* valuetok = tok2->astOperand2();
379  pm.setValue(vartok, execute(valuetok, pm, settings));
380  }
381  }
382  } else if (tok2->exprId() > 0 && Token::Match(tok2, ".|(|[|*|%var%") && !pm.hasValue(tok2->exprId()) &&
383  isVariableChanged(tok2, 0, settings)) {
384  pm.setUnknown(tok2);
385  }
386 
387  if (tok2->str() == "{") {
388  if (indentlevel <= 0) {
389  const Token* cond = getCondTokFromEnd(tok2->link());
390  // Keep progressing with anonymous/do scopes and always true branches
391  if (!Token::Match(tok2->previous(), "do|; {") && !conditionIsTrue(cond, state, settings) &&
392  (cond || !isBasicForLoop(tok2)))
393  break;
394  } else
395  --indentlevel;
396  if (Token::simpleMatch(tok2->previous(), "else {"))
397  tok2 = tok2->linkAt(-2)->previous();
398  }
399  if (tok2->str() == "}" && !Token::Match(tok2->link()->previous(), "%var% {")) {
400  const Token *cond = getCondTokFromEnd(tok2);
401  const bool inElse = Token::simpleMatch(tok2->link()->previous(), "else {");
402  if (cond) {
403  if (conditionIsFalse(cond, state, settings)) {
404  if (inElse) {
405  ++indentlevel;
406  continue;
407  }
408  } else if (conditionIsTrue(cond, state, settings)) {
409  if (inElse)
410  tok2 = tok2->link()->tokAt(-2);
411  ++indentlevel;
412  continue;
413  }
414  }
415  break;
416  }
417  }
418 }
419 
420 static void removeModifiedVars(ProgramMemory& pm, const Token* tok, const Token* origin, const Settings& settings)
421 {
422  pm.erase_if([&](const ExprIdToken& e) {
423  return isVariableChanged(origin, tok, e.getExpressionId(), false, settings);
424  });
425 }
426 
428  const Token* origin,
429  const Settings& settings,
430  const ProgramMemory::Map& vars = ProgramMemory::Map {})
431 {
432  ProgramMemory pm;
433  if (origin) {
434  fillProgramMemoryFromConditions(pm, origin, settings);
435  const ProgramMemory state = pm;
436  fillProgramMemoryFromAssignments(pm, tok, settings, state, vars);
437  removeModifiedVars(pm, tok, origin, settings);
438  }
439  return pm;
440 }
441 
443 {
444  assert(settings != nullptr);
445 }
446 
447 void ProgramMemoryState::insert(const ProgramMemory &pm, const Token* origin)
448 {
449  if (origin)
450  for (auto&& p : pm)
451  origins.insert(std::make_pair(p.first.getExpressionId(), origin));
452  state.insert(pm);
453 }
454 
456 {
457  if (origin)
458  for (const auto& p : pm)
459  origins[p.first.getExpressionId()] = origin;
460  state.replace(std::move(pm));
461 }
462 
463 static void addVars(ProgramMemory& pm, const ProgramMemory::Map& vars)
464 {
465  for (const auto& p:vars) {
466  const ValueFlow::Value &value = p.second;
467  pm.setValue(p.first.tok, value);
468  }
469 }
470 
472 {
473  ProgramMemory pm = state;
474  addVars(pm, vars);
476  ProgramMemory local = pm;
477  fillProgramMemoryFromAssignments(pm, tok, *settings, local, vars);
478  addVars(pm, vars);
479  replace(std::move(pm), tok);
480 }
481 
482 void ProgramMemoryState::assume(const Token* tok, bool b, bool isEmpty)
483 {
484  ProgramMemory pm = state;
485  if (isEmpty)
486  pm.setContainerSizeValue(tok, 0, b);
487  else
488  programMemoryParseCondition(pm, tok, nullptr, *settings, b);
489  const Token* origin = tok;
490  const Token* top = tok->astTop();
491  if (top && Token::Match(top->previous(), "for|while|if (") && !Token::simpleMatch(tok->astParent(), "?")) {
492  origin = top->link()->next();
493  if (!b && origin->link()) {
494  origin = origin->link();
495  }
496  }
497  replace(std::move(pm), origin);
498 }
499 
501 {
502  const ProgramMemory& pm = state;
503  auto eval = [&](const Token* cond) -> std::vector<MathLib::bigint> {
504  if (conditionIsTrue(cond, pm, *settings))
505  return {1};
506  if (conditionIsFalse(cond, pm, *settings))
507  return {0};
508  return {};
509  };
510  state.erase_if([&](const ExprIdToken& e) {
511  const Token* start = origins[e.getExpressionId()];
512  const Token* expr = e.tok;
513  if (!expr || findExpressionChangedSkipDeadCode(expr, start, tok, *settings, eval)) {
514  origins.erase(e.getExpressionId());
515  return true;
516  }
517  return false;
518  });
519 }
520 
521 ProgramMemory ProgramMemoryState::get(const Token* tok, const Token* ctx, const ProgramMemory::Map& vars) const
522 {
523  ProgramMemoryState local = *this;
524  if (ctx)
525  local.addState(ctx, vars);
526  const Token* start = previousBeforeAstLeftmostLeaf(tok);
527  if (!start)
528  start = tok;
529 
530  if (!ctx || precedes(start, ctx)) {
531  local.removeModifiedVars(start);
532  local.addState(start, vars);
533  } else {
534  local.removeModifiedVars(ctx);
535  }
536  return local.state;
537 }
538 
539 ProgramMemory getProgramMemory(const Token* tok, const Token* expr, const ValueFlow::Value& value, const Settings& settings)
540 {
541  ProgramMemory programMemory;
542  programMemory.replace(getInitialProgramState(tok, value.tokvalue, settings));
543  programMemory.replace(getInitialProgramState(tok, value.condition, settings));
544  fillProgramMemoryFromConditions(programMemory, tok, settings);
545  programMemory.setValue(expr, value);
546  const ProgramMemory state = programMemory;
547  fillProgramMemoryFromAssignments(programMemory, tok, settings, state, {{expr, value}});
548  return programMemory;
549 }
550 
551 static bool isNumericValue(const ValueFlow::Value& value) {
552  return value.isIntValue() || value.isFloatValue();
553 }
554 
555 static double asFloat(const ValueFlow::Value& value)
556 {
557  return value.isFloatValue() ? value.floatValue : value.intvalue;
558 }
559 
560 static std::string removeAssign(const std::string& assign) {
561  return std::string{assign.cbegin(), assign.cend() - 1};
562 }
563 
564 namespace {
565  struct assign {
566  template<class T, class U>
567  void operator()(T& x, const U& y) const
568  {
569  x = y;
570  }
571  };
572 }
573 
574 static bool isIntegralValue(const ValueFlow::Value& value)
575 {
576  return value.isIntValue() || value.isIteratorValue() || value.isSymbolicValue();
577 }
578 
579 static ValueFlow::Value evaluate(const std::string& op, const ValueFlow::Value& lhs, const ValueFlow::Value& rhs)
580 {
581  ValueFlow::Value result;
582  combineValueProperties(lhs, rhs, result);
583  if (lhs.isImpossible() && rhs.isImpossible())
584  return ValueFlow::Value::unknown();
585  if (lhs.isImpossible() || rhs.isImpossible()) {
586  // noninvertible
587  if (contains({"%", "/", "&", "|"}, op))
588  return ValueFlow::Value::unknown();
589  result.setImpossible();
590  }
591  if (isNumericValue(lhs) && isNumericValue(rhs)) {
592  if (lhs.isFloatValue() || rhs.isFloatValue()) {
594  bool error = false;
595  result.floatValue = calculate(op, asFloat(lhs), asFloat(rhs), &error);
596  if (error)
597  return ValueFlow::Value::unknown();
598  return result;
599  }
600  }
601  // Must be integral types
602  if (!isIntegralValue(lhs) && !isIntegralValue(rhs))
603  return ValueFlow::Value::unknown();
604  // If not the same type then one must be int
605  if (lhs.valueType != rhs.valueType && !lhs.isIntValue() && !rhs.isIntValue())
606  return ValueFlow::Value::unknown();
607  const bool compareOp = contains({"==", "!=", "<", ">", ">=", "<="}, op);
608  // Comparison must be the same type
609  if (compareOp && lhs.valueType != rhs.valueType)
610  return ValueFlow::Value::unknown();
611  // Only add, subtract, and compare for non-integers
612  if (!compareOp && !contains({"+", "-"}, op) && !lhs.isIntValue() && !rhs.isIntValue())
613  return ValueFlow::Value::unknown();
614  // Both can't be iterators for non-compare
615  if (!compareOp && lhs.isIteratorValue() && rhs.isIteratorValue())
616  return ValueFlow::Value::unknown();
617  // Symbolic values must be in the same ring
618  if (lhs.isSymbolicValue() && rhs.isSymbolicValue() && lhs.tokvalue != rhs.tokvalue)
619  return ValueFlow::Value::unknown();
620  if (!lhs.isIntValue() && !compareOp) {
621  result.valueType = lhs.valueType;
622  result.tokvalue = lhs.tokvalue;
623  } else if (!rhs.isIntValue() && !compareOp) {
624  result.valueType = rhs.valueType;
625  result.tokvalue = rhs.tokvalue;
626  } else {
628  }
629  bool error = false;
630  result.intvalue = calculate(op, lhs.intvalue, rhs.intvalue, &error);
631  if (error)
632  return ValueFlow::Value::unknown();
633  if (result.isImpossible() && op == "!=") {
634  if (isTrue(result)) {
635  result.intvalue = 1;
636  } else if (isFalse(result)) {
637  result.intvalue = 0;
638  } else {
639  return ValueFlow::Value::unknown();
640  }
641  result.setPossible();
643  }
644  return result;
645 }
646 
647 using BuiltinLibraryFunction = std::function<ValueFlow::Value(const std::vector<ValueFlow::Value>&)>;
648 static std::unordered_map<std::string, BuiltinLibraryFunction> createBuiltinLibraryFunctions()
649 {
650  std::unordered_map<std::string, BuiltinLibraryFunction> functions;
651  functions["strlen"] = [](const std::vector<ValueFlow::Value>& args) {
652  if (args.size() != 1)
653  return ValueFlow::Value::unknown();
654  ValueFlow::Value v = args[0];
655  if (!(v.isTokValue() && v.tokvalue->tokType() == Token::eString))
656  return ValueFlow::Value::unknown();
659  v.tokvalue = nullptr;
660  return v;
661  };
662  functions["strcmp"] = [](const std::vector<ValueFlow::Value>& args) {
663  if (args.size() != 2)
664  return ValueFlow::Value::unknown();
665  const ValueFlow::Value& lhs = args[0];
666  if (!(lhs.isTokValue() && lhs.tokvalue->tokType() == Token::eString))
667  return ValueFlow::Value::unknown();
668  const ValueFlow::Value& rhs = args[1];
669  if (!(rhs.isTokValue() && rhs.tokvalue->tokType() == Token::eString))
670  return ValueFlow::Value::unknown();
673  return v;
674  };
675  functions["strncmp"] = [](const std::vector<ValueFlow::Value>& args) {
676  if (args.size() != 3)
677  return ValueFlow::Value::unknown();
678  const ValueFlow::Value& lhs = args[0];
679  if (!(lhs.isTokValue() && lhs.tokvalue->tokType() == Token::eString))
680  return ValueFlow::Value::unknown();
681  const ValueFlow::Value& rhs = args[1];
682  if (!(rhs.isTokValue() && rhs.tokvalue->tokType() == Token::eString))
683  return ValueFlow::Value::unknown();
684  const ValueFlow::Value& len = args[2];
685  if (!len.isIntValue())
686  return ValueFlow::Value::unknown();
688  .compare(0, len.intvalue, getStringLiteral(rhs.tokvalue->str()), 0, len.intvalue));
690  return v;
691  };
692  functions["sin"] = [](const std::vector<ValueFlow::Value>& args) {
693  if (args.size() != 1)
694  return ValueFlow::Value::unknown();
695  ValueFlow::Value v = args[0];
696  if (!v.isFloatValue() && !v.isIntValue())
697  return ValueFlow::Value::unknown();
698  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
699  v.floatValue = std::sin(value);
701  return v;
702  };
703  functions["lgamma"] = [](const std::vector<ValueFlow::Value>& args) {
704  if (args.size() != 1)
705  return ValueFlow::Value::unknown();
706  ValueFlow::Value v = args[0];
707  if (!v.isFloatValue() && !v.isIntValue())
708  return ValueFlow::Value::unknown();
709  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
710  v.floatValue = std::lgamma(value);
712  return v;
713  };
714  functions["cos"] = [](const std::vector<ValueFlow::Value>& args) {
715  if (args.size() != 1)
716  return ValueFlow::Value::unknown();
717  ValueFlow::Value v = args[0];
718  if (!v.isFloatValue() && !v.isIntValue())
719  return ValueFlow::Value::unknown();
720  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
721  v.floatValue = std::cos(value);
723  return v;
724  };
725  functions["tan"] = [](const std::vector<ValueFlow::Value>& args) {
726  if (args.size() != 1)
727  return ValueFlow::Value::unknown();
728  ValueFlow::Value v = args[0];
729  if (!v.isFloatValue() && !v.isIntValue())
730  return ValueFlow::Value::unknown();
731  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
732  v.floatValue = std::tan(value);
734  return v;
735  };
736  functions["asin"] = [](const std::vector<ValueFlow::Value>& args) {
737  if (args.size() != 1)
738  return ValueFlow::Value::unknown();
739  ValueFlow::Value v = args[0];
740  if (!v.isFloatValue() && !v.isIntValue())
741  return ValueFlow::Value::unknown();
742  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
743  v.floatValue = std::asin(value);
745  return v;
746  };
747  functions["acos"] = [](const std::vector<ValueFlow::Value>& args) {
748  if (args.size() != 1)
749  return ValueFlow::Value::unknown();
750  ValueFlow::Value v = args[0];
751  if (!v.isFloatValue() && !v.isIntValue())
752  return ValueFlow::Value::unknown();
753  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
754  v.floatValue = std::acos(value);
756  return v;
757  };
758  functions["atan"] = [](const std::vector<ValueFlow::Value>& args) {
759  if (args.size() != 1)
760  return ValueFlow::Value::unknown();
761  ValueFlow::Value v = args[0];
762  if (!v.isFloatValue() && !v.isIntValue())
763  return ValueFlow::Value::unknown();
764  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
765  v.floatValue = std::atan(value);
767  return v;
768  };
769  functions["atan2"] = [](const std::vector<ValueFlow::Value>& args) {
770  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
771  return v.isFloatValue() || v.isIntValue();
772  }))
773  return ValueFlow::Value::unknown();
774  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
776  combineValueProperties(args[0], args[1], v);
777  v.floatValue = std::atan2(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
779  return v;
780  };
781  functions["remainder"] = [](const std::vector<ValueFlow::Value>& args) {
782  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
783  return v.isFloatValue() || v.isIntValue();
784  }))
785  return ValueFlow::Value::unknown();
786  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
788  combineValueProperties(args[0], args[1], v);
789  v.floatValue = std::remainder(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
791  return v;
792  };
793  functions["nextafter"] = [](const std::vector<ValueFlow::Value>& args) {
794  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
795  return v.isFloatValue() || v.isIntValue();
796  }))
797  return ValueFlow::Value::unknown();
798  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
800  combineValueProperties(args[0], args[1], v);
801  v.floatValue = std::nextafter(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
803  return v;
804  };
805  functions["nexttoward"] = [](const std::vector<ValueFlow::Value>& args) {
806  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
807  return v.isFloatValue() || v.isIntValue();
808  }))
809  return ValueFlow::Value::unknown();
810  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
812  combineValueProperties(args[0], args[1], v);
813  v.floatValue = std::nexttoward(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
815  return v;
816  };
817  functions["hypot"] = [](const std::vector<ValueFlow::Value>& args) {
818  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
819  return v.isFloatValue() || v.isIntValue();
820  }))
821  return ValueFlow::Value::unknown();
822  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
824  combineValueProperties(args[0], args[1], v);
825  v.floatValue = std::hypot(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
827  return v;
828  };
829  functions["fdim"] = [](const std::vector<ValueFlow::Value>& args) {
830  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
831  return v.isFloatValue() || v.isIntValue();
832  }))
833  return ValueFlow::Value::unknown();
834  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
836  combineValueProperties(args[0], args[1], v);
837  v.floatValue = std::fdim(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
839  return v;
840  };
841  functions["fmax"] = [](const std::vector<ValueFlow::Value>& args) {
842  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
843  return v.isFloatValue() || v.isIntValue();
844  }))
845  return ValueFlow::Value::unknown();
846  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
848  combineValueProperties(args[0], args[1], v);
849  v.floatValue = std::fmax(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
851  return v;
852  };
853  functions["fmin"] = [](const std::vector<ValueFlow::Value>& args) {
854  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
855  return v.isFloatValue() || v.isIntValue();
856  }))
857  return ValueFlow::Value::unknown();
858  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
860  combineValueProperties(args[0], args[1], v);
861  v.floatValue = std::fmin(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
863  return v;
864  };
865  functions["fmod"] = [](const std::vector<ValueFlow::Value>& args) {
866  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
867  return v.isFloatValue() || v.isIntValue();
868  }))
869  return ValueFlow::Value::unknown();
870  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
872  combineValueProperties(args[0], args[1], v);
873  v.floatValue = std::fmod(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
875  return v;
876  };
877  functions["pow"] = [](const std::vector<ValueFlow::Value>& args) {
878  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
879  return v.isFloatValue() || v.isIntValue();
880  }))
881  return ValueFlow::Value::unknown();
882  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
884  combineValueProperties(args[0], args[1], v);
885  v.floatValue = std::pow(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
887  return v;
888  };
889  functions["scalbln"] = [](const std::vector<ValueFlow::Value>& args) {
890  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
891  return v.isFloatValue() || v.isIntValue();
892  }))
893  return ValueFlow::Value::unknown();
894  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
896  combineValueProperties(args[0], args[1], v);
897  v.floatValue = std::scalbln(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
899  return v;
900  };
901  functions["ldexp"] = [](const std::vector<ValueFlow::Value>& args) {
902  if (args.size() != 2 || !std::all_of(args.cbegin(), args.cend(), [](const ValueFlow::Value& v) {
903  return v.isFloatValue() || v.isIntValue();
904  }))
905  return ValueFlow::Value::unknown();
906  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
908  combineValueProperties(args[0], args[1], v);
909  v.floatValue = std::ldexp(value, args[1].isFloatValue() ? args[1].floatValue : args[1].intvalue);
911  return v;
912  };
913  functions["ilogb"] = [](const std::vector<ValueFlow::Value>& args) {
914  if (args.size() != 1)
915  return ValueFlow::Value::unknown();
916  ValueFlow::Value v = args[0];
917  if (!v.isFloatValue() && !v.isIntValue())
918  return ValueFlow::Value::unknown();
919  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
920  v.intvalue = std::ilogb(value);
922  return v;
923  };
924  functions["erf"] = [](const std::vector<ValueFlow::Value>& args) {
925  if (args.size() != 1)
926  return ValueFlow::Value::unknown();
927  ValueFlow::Value v = args[0];
928  if (!v.isFloatValue() && !v.isIntValue())
929  return ValueFlow::Value::unknown();
930  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
931  v.floatValue = std::erf(value);
933  return v;
934  };
935  functions["erfc"] = [](const std::vector<ValueFlow::Value>& args) {
936  if (args.size() != 1)
937  return ValueFlow::Value::unknown();
938  ValueFlow::Value v = args[0];
939  if (!v.isFloatValue() && !v.isIntValue())
940  return ValueFlow::Value::unknown();
941  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
942  v.floatValue = std::erfc(value);
944  return v;
945  };
946  functions["floor"] = [](const std::vector<ValueFlow::Value>& args) {
947  if (args.size() != 1)
948  return ValueFlow::Value::unknown();
949  ValueFlow::Value v = args[0];
950  if (!v.isFloatValue() && !v.isIntValue())
951  return ValueFlow::Value::unknown();
952  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
953  v.floatValue = std::floor(value);
955  return v;
956  };
957  functions["sqrt"] = [](const std::vector<ValueFlow::Value>& args) {
958  if (args.size() != 1)
959  return ValueFlow::Value::unknown();
960  ValueFlow::Value v = args[0];
961  if (!v.isFloatValue() && !v.isIntValue())
962  return ValueFlow::Value::unknown();
963  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
964  v.floatValue = std::sqrt(value);
966  return v;
967  };
968  functions["cbrt"] = [](const std::vector<ValueFlow::Value>& args) {
969  if (args.size() != 1)
970  return ValueFlow::Value::unknown();
971  ValueFlow::Value v = args[0];
972  if (!v.isFloatValue() && !v.isIntValue())
973  return ValueFlow::Value::unknown();
974  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
975  v.floatValue = std::cbrt(value);
977  return v;
978  };
979  functions["ceil"] = [](const std::vector<ValueFlow::Value>& args) {
980  if (args.size() != 1)
981  return ValueFlow::Value::unknown();
982  ValueFlow::Value v = args[0];
983  if (!v.isFloatValue() && !v.isIntValue())
984  return ValueFlow::Value::unknown();
985  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
986  v.floatValue = std::ceil(value);
988  return v;
989  };
990  functions["exp"] = [](const std::vector<ValueFlow::Value>& args) {
991  if (args.size() != 1)
992  return ValueFlow::Value::unknown();
993  ValueFlow::Value v = args[0];
994  if (!v.isFloatValue() && !v.isIntValue())
995  return ValueFlow::Value::unknown();
996  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
997  v.floatValue = std::exp(value);
999  return v;
1000  };
1001  functions["exp2"] = [](const std::vector<ValueFlow::Value>& args) {
1002  if (args.size() != 1)
1003  return ValueFlow::Value::unknown();
1004  ValueFlow::Value v = args[0];
1005  if (!v.isFloatValue() && !v.isIntValue())
1006  return ValueFlow::Value::unknown();
1007  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1008  v.floatValue = std::exp2(value);
1010  return v;
1011  };
1012  functions["expm1"] = [](const std::vector<ValueFlow::Value>& args) {
1013  if (args.size() != 1)
1014  return ValueFlow::Value::unknown();
1015  ValueFlow::Value v = args[0];
1016  if (!v.isFloatValue() && !v.isIntValue())
1017  return ValueFlow::Value::unknown();
1018  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1019  v.floatValue = std::expm1(value);
1021  return v;
1022  };
1023  functions["fabs"] = [](const std::vector<ValueFlow::Value>& args) {
1024  if (args.size() != 1)
1025  return ValueFlow::Value::unknown();
1026  ValueFlow::Value v = args[0];
1027  if (!v.isFloatValue() && !v.isIntValue())
1028  return ValueFlow::Value::unknown();
1029  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1030  v.floatValue = std::fabs(value);
1032  return v;
1033  };
1034  functions["log"] = [](const std::vector<ValueFlow::Value>& args) {
1035  if (args.size() != 1)
1036  return ValueFlow::Value::unknown();
1037  ValueFlow::Value v = args[0];
1038  if (!v.isFloatValue() && !v.isIntValue())
1039  return ValueFlow::Value::unknown();
1040  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1041  v.floatValue = std::log(value);
1043  return v;
1044  };
1045  functions["log10"] = [](const std::vector<ValueFlow::Value>& args) {
1046  if (args.size() != 1)
1047  return ValueFlow::Value::unknown();
1048  ValueFlow::Value v = args[0];
1049  if (!v.isFloatValue() && !v.isIntValue())
1050  return ValueFlow::Value::unknown();
1051  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1052  v.floatValue = std::log10(value);
1054  return v;
1055  };
1056  functions["log1p"] = [](const std::vector<ValueFlow::Value>& args) {
1057  if (args.size() != 1)
1058  return ValueFlow::Value::unknown();
1059  ValueFlow::Value v = args[0];
1060  if (!v.isFloatValue() && !v.isIntValue())
1061  return ValueFlow::Value::unknown();
1062  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1063  v.floatValue = std::log1p(value);
1065  return v;
1066  };
1067  functions["log2"] = [](const std::vector<ValueFlow::Value>& args) {
1068  if (args.size() != 1)
1069  return ValueFlow::Value::unknown();
1070  ValueFlow::Value v = args[0];
1071  if (!v.isFloatValue() && !v.isIntValue())
1072  return ValueFlow::Value::unknown();
1073  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1074  v.floatValue = std::log2(value);
1076  return v;
1077  };
1078  functions["logb"] = [](const std::vector<ValueFlow::Value>& args) {
1079  if (args.size() != 1)
1080  return ValueFlow::Value::unknown();
1081  ValueFlow::Value v = args[0];
1082  if (!v.isFloatValue() && !v.isIntValue())
1083  return ValueFlow::Value::unknown();
1084  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1085  v.floatValue = std::logb(value);
1087  return v;
1088  };
1089  functions["nearbyint"] = [](const std::vector<ValueFlow::Value>& args) {
1090  if (args.size() != 1)
1091  return ValueFlow::Value::unknown();
1092  ValueFlow::Value v = args[0];
1093  if (!v.isFloatValue() && !v.isIntValue())
1094  return ValueFlow::Value::unknown();
1095  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1096  v.floatValue = std::nearbyint(value);
1098  return v;
1099  };
1100  functions["sinh"] = [](const std::vector<ValueFlow::Value>& args) {
1101  if (args.size() != 1)
1102  return ValueFlow::Value::unknown();
1103  ValueFlow::Value v = args[0];
1104  if (!v.isFloatValue() && !v.isIntValue())
1105  return ValueFlow::Value::unknown();
1106  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1107  v.floatValue = std::sinh(value);
1109  return v;
1110  };
1111  functions["cosh"] = [](const std::vector<ValueFlow::Value>& args) {
1112  if (args.size() != 1)
1113  return ValueFlow::Value::unknown();
1114  ValueFlow::Value v = args[0];
1115  if (!v.isFloatValue() && !v.isIntValue())
1116  return ValueFlow::Value::unknown();
1117  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1118  v.floatValue = std::cosh(value);
1120  return v;
1121  };
1122  functions["tanh"] = [](const std::vector<ValueFlow::Value>& args) {
1123  if (args.size() != 1)
1124  return ValueFlow::Value::unknown();
1125  ValueFlow::Value v = args[0];
1126  if (!v.isFloatValue() && !v.isIntValue())
1127  return ValueFlow::Value::unknown();
1128  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1129  v.floatValue = std::tanh(value);
1131  return v;
1132  };
1133  functions["asinh"] = [](const std::vector<ValueFlow::Value>& args) {
1134  if (args.size() != 1)
1135  return ValueFlow::Value::unknown();
1136  ValueFlow::Value v = args[0];
1137  if (!v.isFloatValue() && !v.isIntValue())
1138  return ValueFlow::Value::unknown();
1139  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1140  v.floatValue = std::asinh(value);
1142  return v;
1143  };
1144  functions["acosh"] = [](const std::vector<ValueFlow::Value>& args) {
1145  if (args.size() != 1)
1146  return ValueFlow::Value::unknown();
1147  ValueFlow::Value v = args[0];
1148  if (!v.isFloatValue() && !v.isIntValue())
1149  return ValueFlow::Value::unknown();
1150  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1151  v.floatValue = std::acosh(value);
1153  return v;
1154  };
1155  functions["atanh"] = [](const std::vector<ValueFlow::Value>& args) {
1156  if (args.size() != 1)
1157  return ValueFlow::Value::unknown();
1158  ValueFlow::Value v = args[0];
1159  if (!v.isFloatValue() && !v.isIntValue())
1160  return ValueFlow::Value::unknown();
1161  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1162  v.floatValue = std::atanh(value);
1164  return v;
1165  };
1166  functions["round"] = [](const std::vector<ValueFlow::Value>& args) {
1167  if (args.size() != 1)
1168  return ValueFlow::Value::unknown();
1169  ValueFlow::Value v = args[0];
1170  if (!v.isFloatValue() && !v.isIntValue())
1171  return ValueFlow::Value::unknown();
1172  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1173  v.floatValue = std::round(value);
1175  return v;
1176  };
1177  functions["tgamma"] = [](const std::vector<ValueFlow::Value>& args) {
1178  if (args.size() != 1)
1179  return ValueFlow::Value::unknown();
1180  ValueFlow::Value v = args[0];
1181  if (!v.isFloatValue() && !v.isIntValue())
1182  return ValueFlow::Value::unknown();
1183  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1184  v.floatValue = std::tgamma(value);
1186  return v;
1187  };
1188  functions["trunc"] = [](const std::vector<ValueFlow::Value>& args) {
1189  if (args.size() != 1)
1190  return ValueFlow::Value::unknown();
1191  ValueFlow::Value v = args[0];
1192  if (!v.isFloatValue() && !v.isIntValue())
1193  return ValueFlow::Value::unknown();
1194  const double value = args[0].isFloatValue() ? args[0].floatValue : args[0].intvalue;
1195  v.floatValue = std::trunc(value);
1197  return v;
1198  };
1199  return functions;
1200 }
1201 
1202 static BuiltinLibraryFunction getBuiltinLibraryFunction(const std::string& name)
1203 {
1204  static const std::unordered_map<std::string, BuiltinLibraryFunction> functions = createBuiltinLibraryFunctions();
1205  auto it = functions.find(name);
1206  if (it == functions.end())
1207  return nullptr;
1208  return it->second;
1209 }
1210 static bool TokenExprIdCompare(const Token* tok1, const Token* tok2) {
1211  return tok1->exprId() < tok2->exprId();
1212 }
1213 static bool TokenExprIdEqual(const Token* tok1, const Token* tok2) {
1214  return tok1->exprId() == tok2->exprId();
1215 }
1216 
1217 static std::vector<const Token*> setDifference(const std::vector<const Token*>& v1, const std::vector<const Token*>& v2)
1218 {
1219  std::vector<const Token*> result;
1220  std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result), &TokenExprIdCompare);
1221  return result;
1222 }
1223 
1224 static bool evalSameCondition(const ProgramMemory& state,
1225  const Token* storedValue,
1226  const Token* cond,
1227  const Settings& settings)
1228 {
1229  assert(!conditionIsTrue(cond, state, settings));
1230  ProgramMemory pm = state;
1231  programMemoryParseCondition(pm, storedValue, nullptr, settings, true);
1232  if (pm == state)
1233  return false;
1234  return conditionIsTrue(cond, std::move(pm), settings);
1235 }
1236 
1237 static void pruneConditions(std::vector<const Token*>& conds,
1238  bool b,
1239  const std::unordered_map<nonneg int, ValueFlow::Value>& state)
1240 {
1241  conds.erase(std::remove_if(conds.begin(),
1242  conds.end(),
1243  [&](const Token* cond) {
1244  if (cond->exprId() == 0)
1245  return false;
1246  auto it = state.find(cond->exprId());
1247  if (it == state.end())
1248  return false;
1249  const ValueFlow::Value& v = it->second;
1250  return isTrueOrFalse(v, !b);
1251  }),
1252  conds.end());
1253 }
1254 
1255 namespace {
1256  struct Executor {
1257  ProgramMemory* pm = nullptr;
1258  const Settings* settings = nullptr;
1259  int fdepth = 4;
1260  int depth = 10;
1261 
1262  Executor(ProgramMemory* pm, const Settings* settings) : pm(pm), settings(settings)
1263  {
1264  assert(settings != nullptr);
1265  }
1266 
1267  static ValueFlow::Value unknown() {
1268  return ValueFlow::Value::unknown();
1269  }
1270 
1271  std::unordered_map<nonneg int, ValueFlow::Value> executeAll(const std::vector<const Token*>& toks,
1272  const bool* b = nullptr) const
1273  {
1274  std::unordered_map<nonneg int, ValueFlow::Value> result;
1275  auto state = *this;
1276  for (const Token* tok : toks) {
1277  ValueFlow::Value r = state.execute(tok);
1278  if (r.isUninitValue())
1279  continue;
1280  const bool brk = b && isTrueOrFalse(r, *b);
1281  result.emplace(tok->exprId(), std::move(r));
1282  // Short-circuit evaluation
1283  if (brk)
1284  break;
1285  }
1286  return result;
1287  }
1288 
1289  static std::vector<const Token*> flattenConditions(const Token* tok)
1290  {
1291  return astFlatten(tok, tok->str().c_str());
1292  }
1293  static bool sortConditions(std::vector<const Token*>& conditions)
1294  {
1295  if (std::any_of(conditions.begin(), conditions.end(), [](const Token* child) {
1296  return Token::Match(child, "&&|%oror%");
1297  }))
1298  return false;
1299  std::sort(conditions.begin(), conditions.end(), &TokenExprIdCompare);
1300  conditions.erase(std::unique(conditions.begin(), conditions.end(), &TokenExprIdCompare), conditions.end());
1301  return !conditions.empty() && conditions.front()->exprId() != 0;
1302  }
1303 
1304  ValueFlow::Value executeMultiCondition(bool b, const Token* expr)
1305  {
1306  if (pm->hasValue(expr->exprId())) {
1307  const ValueFlow::Value& v = pm->at(expr->exprId());
1308  if (v.isIntValue())
1309  return v;
1310  }
1311 
1312  // Evaluate recursively if there are no exprids
1313  if ((expr->astOperand1() && expr->astOperand1()->exprId() == 0) ||
1314  (expr->astOperand2() && expr->astOperand2()->exprId() == 0)) {
1315  ValueFlow::Value lhs = execute(expr->astOperand1());
1316  if (isTrueOrFalse(lhs, b))
1317  return lhs;
1318  ValueFlow::Value rhs = execute(expr->astOperand2());
1319  if (isTrueOrFalse(rhs, b))
1320  return rhs;
1321  if (isTrueOrFalse(lhs, !b) && isTrueOrFalse(rhs, !b))
1322  return lhs;
1323  return unknown();
1324  }
1325 
1326  nonneg int n = astCount(expr, expr->str().c_str());
1327  if (n > 50)
1328  return unknown();
1329  std::vector<const Token*> conditions1 = flattenConditions(expr);
1330  if (conditions1.empty())
1331  return unknown();
1332  std::unordered_map<nonneg int, ValueFlow::Value> condValues = executeAll(conditions1, &b);
1333  bool allNegated = true;
1334  ValueFlow::Value negatedValue = unknown();
1335  for (const auto& p : condValues) {
1336  const ValueFlow::Value& v = p.second;
1337  if (isTrueOrFalse(v, b))
1338  return v;
1339  allNegated &= isTrueOrFalse(v, !b);
1340  if (allNegated && negatedValue.isUninitValue())
1341  negatedValue = v;
1342  }
1343  if (condValues.size() == conditions1.size() && allNegated)
1344  return negatedValue;
1345  if (n > 4)
1346  return unknown();
1347  if (!sortConditions(conditions1))
1348  return unknown();
1349 
1350  for (const auto& p : *pm) {
1351  const Token* tok = p.first.tok;
1352  if (!tok)
1353  continue;
1354  const ValueFlow::Value& value = p.second;
1355 
1356  if (tok->str() == expr->str() && !astHasExpr(tok, expr->exprId())) {
1357  // TODO: Handle when it is greater
1358  if (n != astCount(tok, expr->str().c_str()))
1359  continue;
1360  std::vector<const Token*> conditions2 = flattenConditions(tok);
1361  if (!sortConditions(conditions2))
1362  return unknown();
1363  if (conditions1.size() == conditions2.size() &&
1364  std::equal(conditions1.begin(), conditions1.end(), conditions2.begin(), &TokenExprIdEqual))
1365  return value;
1366  std::vector<const Token*> diffConditions1 = setDifference(conditions1, conditions2);
1367  std::vector<const Token*> diffConditions2 = setDifference(conditions2, conditions1);
1368  pruneConditions(diffConditions1, !b, condValues);
1369  pruneConditions(diffConditions2, !b, executeAll(diffConditions2));
1370  if (diffConditions1.size() != diffConditions2.size())
1371  continue;
1372  if (diffConditions1.size() == conditions1.size())
1373  continue;
1374  for (const Token* cond1 : diffConditions1) {
1375  auto it = std::find_if(diffConditions2.begin(), diffConditions2.end(), [&](const Token* cond2) {
1376  return evalSameCondition(*pm, cond2, cond1, *settings);
1377  });
1378  if (it == diffConditions2.end())
1379  break;
1380  diffConditions2.erase(it);
1381  }
1382  if (diffConditions2.empty())
1383  return value;
1384  }
1385  }
1386  return unknown();
1387  }
1388 
1389  ValueFlow::Value executeImpl(const Token* expr)
1390  {
1391  const ValueFlow::Value* value = nullptr;
1392  if (!expr)
1393  return unknown();
1394  if (expr->hasKnownIntValue() && !expr->isAssignmentOp() && expr->str() != ",")
1395  return expr->values().front();
1396  if ((value = expr->getKnownValue(ValueFlow::Value::ValueType::FLOAT)) ||
1401  return *value;
1402  }
1403  if (expr->isNumber()) {
1404  if (MathLib::isFloat(expr->str()))
1405  return unknown();
1407  if (i < 0 && astIsUnsigned(expr))
1408  return unknown();
1409  return ValueFlow::Value{i};
1410  }
1411  if (expr->isBoolean())
1412  return ValueFlow::Value{expr->str() == "true"};
1413  if (Token::Match(expr->tokAt(-2), ". %name% (") && astIsContainer(expr->tokAt(-2)->astOperand1())) {
1414  const Token* containerTok = expr->tokAt(-2)->astOperand1();
1415  const Library::Container::Yield yield = containerTok->valueType()->container->getYield(expr->strAt(-1));
1416  if (yield == Library::Container::Yield::SIZE) {
1417  ValueFlow::Value v = execute(containerTok);
1418  if (!v.isContainerSizeValue())
1419  return unknown();
1421  return v;
1422  }
1423  if (yield == Library::Container::Yield::EMPTY) {
1424  ValueFlow::Value v = execute(containerTok);
1425  if (!v.isContainerSizeValue())
1426  return unknown();
1427  if (v.isImpossible() && v.intvalue == 0)
1428  return ValueFlow::Value{0};
1429  if (!v.isImpossible())
1430  return ValueFlow::Value{v.intvalue == 0};
1431  }
1432  } else if (expr->isAssignmentOp() && expr->astOperand1() && expr->astOperand2() &&
1433  expr->astOperand1()->exprId() > 0) {
1434  ValueFlow::Value rhs = execute(expr->astOperand2());
1435  if (rhs.isUninitValue())
1436  return unknown();
1437  if (expr->str() != "=") {
1438  if (!pm->hasValue(expr->astOperand1()->exprId()))
1439  return unknown();
1440  ValueFlow::Value& lhs = pm->at(expr->astOperand1()->exprId());
1441  rhs = evaluate(removeAssign(expr->str()), lhs, rhs);
1442  if (lhs.isIntValue())
1443  ValueFlow::Value::visitValue(rhs, std::bind(assign{}, std::ref(lhs.intvalue), std::placeholders::_1));
1444  else if (lhs.isFloatValue())
1446  std::bind(assign{}, std::ref(lhs.floatValue), std::placeholders::_1));
1447  else
1448  return unknown();
1449  return lhs;
1450  }
1451  pm->setValue(expr->astOperand1(), rhs);
1452  return rhs;
1453  } else if (expr->str() == "&&" && expr->astOperand1() && expr->astOperand2()) {
1454  return executeMultiCondition(false, expr);
1455  } else if (expr->str() == "||" && expr->astOperand1() && expr->astOperand2()) {
1456  return executeMultiCondition(true, expr);
1457  } else if (expr->str() == "," && expr->astOperand1() && expr->astOperand2()) {
1458  execute(expr->astOperand1());
1459  return execute(expr->astOperand2());
1460  } else if (expr->tokType() == Token::eIncDecOp && expr->astOperand1() && expr->astOperand1()->exprId() != 0) {
1461  if (!pm->hasValue(expr->astOperand1()->exprId()))
1462  return ValueFlow::Value::unknown();
1463  ValueFlow::Value& lhs = pm->at(expr->astOperand1()->exprId());
1464  if (!lhs.isIntValue())
1465  return unknown();
1466  // overflow
1467  if (!lhs.isImpossible() && lhs.intvalue == 0 && expr->str() == "--" && astIsUnsigned(expr->astOperand1()))
1468  return unknown();
1469 
1470  if (expr->str() == "++")
1471  lhs.intvalue++;
1472  else
1473  lhs.intvalue--;
1474  return lhs;
1475  } else if (expr->str() == "[" && expr->astOperand1() && expr->astOperand2()) {
1476  const Token* tokvalue = nullptr;
1477  if (!pm->getTokValue(expr->astOperand1()->exprId(), tokvalue)) {
1478  auto tokvalue_it = std::find_if(expr->astOperand1()->values().cbegin(),
1479  expr->astOperand1()->values().cend(),
1480  std::mem_fn(&ValueFlow::Value::isTokValue));
1481  if (tokvalue_it == expr->astOperand1()->values().cend() || !tokvalue_it->isKnown()) {
1482  return unknown();
1483  }
1484  tokvalue = tokvalue_it->tokvalue;
1485  }
1486  if (!tokvalue || !tokvalue->isLiteral()) {
1487  return unknown();
1488  }
1489  const std::string strValue = tokvalue->strValue();
1490  ValueFlow::Value rhs = execute(expr->astOperand2());
1491  if (!rhs.isIntValue())
1492  return unknown();
1493  const MathLib::bigint index = rhs.intvalue;
1494  if (index >= 0 && index < strValue.size())
1495  return ValueFlow::Value{strValue[index]};
1496  if (index == strValue.size())
1497  return ValueFlow::Value{};
1498  } else if (Token::Match(expr, "%cop%") && expr->astOperand1() && expr->astOperand2()) {
1499  ValueFlow::Value lhs = execute(expr->astOperand1());
1500  ValueFlow::Value rhs = execute(expr->astOperand2());
1501  ValueFlow::Value r = unknown();
1502  if (!lhs.isUninitValue() && !rhs.isUninitValue())
1503  r = evaluate(expr->str(), lhs, rhs);
1504  if (expr->isComparisonOp() && (r.isUninitValue() || r.isImpossible())) {
1505  if (rhs.isIntValue()) {
1506  std::vector<ValueFlow::Value> result =
1507  infer(ValueFlow::makeIntegralInferModel(), expr->str(), expr->astOperand1()->values(), {std::move(rhs)});
1508  if (!result.empty() && result.front().isKnown())
1509  return result.front();
1510  }
1511  if (lhs.isIntValue()) {
1512  std::vector<ValueFlow::Value> result =
1513  infer(ValueFlow::makeIntegralInferModel(), expr->str(), {std::move(lhs)}, expr->astOperand2()->values());
1514  if (!result.empty() && result.front().isKnown())
1515  return result.front();
1516  }
1517  return unknown();
1518  }
1519  return r;
1520  }
1521  // Unary ops
1522  else if (Token::Match(expr, "!|+|-") && expr->astOperand1() && !expr->astOperand2()) {
1523  ValueFlow::Value lhs = execute(expr->astOperand1());
1524  if (!lhs.isIntValue())
1525  return unknown();
1526  if (expr->str() == "!") {
1527  if (isTrue(lhs)) {
1528  lhs.intvalue = 0;
1529  } else if (isFalse(lhs)) {
1530  lhs.intvalue = 1;
1531  } else {
1532  return unknown();
1533  }
1534  lhs.setPossible();
1536  }
1537  if (expr->str() == "-")
1538  lhs.intvalue = -lhs.intvalue;
1539  return lhs;
1540  } else if (expr->str() == "?" && expr->astOperand1() && expr->astOperand2()) {
1541  ValueFlow::Value cond = execute(expr->astOperand1());
1542  if (!cond.isIntValue())
1543  return unknown();
1544  const Token* child = expr->astOperand2();
1545  if (isFalse(cond))
1546  return execute(child->astOperand2());
1547  if (isTrue(cond))
1548  return execute(child->astOperand1());
1549 
1550  return unknown();
1551  } else if (expr->str() == "(" && expr->isCast()) {
1552  if (Token::simpleMatch(expr->previous(), ">") && expr->previous()->link())
1553  return execute(expr->astOperand2());
1554  return execute(expr->astOperand1());
1555  }
1556  if (expr->exprId() > 0 && pm->hasValue(expr->exprId())) {
1557  ValueFlow::Value result = pm->at(expr->exprId());
1558  if (result.isImpossible() && result.isIntValue() && result.intvalue == 0 && isUsedAsBool(expr, *settings)) {
1559  result.intvalue = !result.intvalue;
1560  result.setKnown();
1561  }
1562  return result;
1563  }
1564 
1565  if (Token::Match(expr->previous(), ">|%name% {|(")) {
1566  const Token* ftok = expr->previous();
1567  const Function* f = ftok->function();
1568  ValueFlow::Value result = unknown();
1569  if (settings && expr->str() == "(") {
1570  std::vector<const Token*> tokArgs = getArguments(expr);
1571  std::vector<ValueFlow::Value> args(tokArgs.size());
1572  std::transform(
1573  tokArgs.cbegin(), tokArgs.cend(), args.begin(), [&](const Token* tok) {
1574  return execute(tok);
1575  });
1576  if (f) {
1577  if (fdepth >= 0 && !f->isImplicitlyVirtual()) {
1578  ProgramMemory functionState;
1579  for (std::size_t i = 0; i < args.size(); ++i) {
1580  const Variable* const arg = f->getArgumentVar(i);
1581  if (!arg)
1582  return unknown();
1583  functionState.setValue(arg->nameToken(), args[i]);
1584  }
1585  Executor ex = *this;
1586  ex.pm = &functionState;
1587  ex.fdepth--;
1588  auto r = ex.execute(f->functionScope);
1589  if (!r.empty())
1590  result = r.front();
1591  // TODO: Track values changed by reference
1592  }
1593  } else {
1595  if (lf)
1596  return lf(args);
1597  const std::string& returnValue = settings->library.returnValue(ftok);
1598  if (!returnValue.empty()) {
1599  std::unordered_map<nonneg int, ValueFlow::Value> arg_map;
1600  int argn = 0;
1601  for (const ValueFlow::Value& v : args) {
1602  if (!v.isUninitValue())
1603  arg_map[argn] = v;
1604  argn++;
1605  }
1606  return evaluateLibraryFunction(arg_map, returnValue, *settings, ftok->isCpp());
1607  }
1608  }
1609  }
1610  // Check if function modifies argument
1611  visitAstNodes(expr->astOperand2(), [&](const Token* child) {
1612  if (child->exprId() > 0 && pm->hasValue(child->exprId())) {
1613  ValueFlow::Value& v = pm->at(child->exprId());
1614  assert(settings != nullptr);
1615  if (v.valueType == ValueFlow::Value::ValueType::CONTAINER_SIZE) {
1616  if (ValueFlow::isContainerSizeChanged(child, v.indirect, *settings))
1617  v = unknown();
1618  } else if (v.valueType != ValueFlow::Value::ValueType::UNINIT) {
1619  if (isVariableChanged(child, v.indirect, *settings))
1620  v = unknown();
1621  }
1622  }
1624  });
1625  return result;
1626  }
1627 
1628  return unknown();
1629  }
1630  static const ValueFlow::Value* getImpossibleValue(const Token* tok)
1631  {
1632  if (!tok)
1633  return nullptr;
1634  std::vector<const ValueFlow::Value*> values;
1635  for (const ValueFlow::Value& v : tok->values()) {
1636  if (!v.isImpossible())
1637  continue;
1638  if (v.isContainerSizeValue() || v.isIntValue()) {
1639  values.push_back(std::addressof(v));
1640  }
1641  }
1642  auto it =
1643  std::max_element(values.begin(), values.end(), [](const ValueFlow::Value* x, const ValueFlow::Value* y) {
1644  return x->intvalue < y->intvalue;
1645  });
1646  if (it == values.end())
1647  return nullptr;
1648  return *it;
1649  }
1650 
1651  static bool updateValue(ValueFlow::Value& v, ValueFlow::Value x)
1652  {
1653  const bool returnValue = !x.isUninitValue() && !x.isImpossible();
1654  if (v.isUninitValue() || returnValue)
1655  v = std::move(x);
1656  return returnValue;
1657  }
1658 
1659  ValueFlow::Value execute(const Token* expr)
1660  {
1661  depth--;
1662  OnExit onExit{[&] {
1663  depth++;
1664  }};
1665  if (depth < 0)
1666  return unknown();
1667  ValueFlow::Value v = unknown();
1668  if (updateValue(v, executeImpl(expr)))
1669  return v;
1670  if (!expr)
1671  return v;
1672  if (expr->exprId() > 0 && pm->hasValue(expr->exprId())) {
1673  if (updateValue(v, pm->at(expr->exprId())))
1674  return v;
1675  }
1676  // Find symbolic values
1677  for (const ValueFlow::Value& value : expr->values()) {
1678  if (!value.isSymbolicValue())
1679  continue;
1680  if (!value.isKnown())
1681  continue;
1682  if (value.tokvalue->exprId() > 0 && !pm->hasValue(value.tokvalue->exprId()))
1683  continue;
1684  ValueFlow::Value v2 = pm->at(value.tokvalue->exprId());
1685  if (!v2.isIntValue() && value.intvalue != 0)
1686  continue;
1687  v2.intvalue += value.intvalue;
1688  return v2;
1689  }
1690  if (v.isImpossible() && v.isIntValue())
1691  return v;
1692  if (const ValueFlow::Value* value = getImpossibleValue(expr))
1693  return *value;
1694  return v;
1695  }
1696 
1697  std::vector<ValueFlow::Value> execute(const Scope* scope)
1698  {
1699  if (!scope)
1700  return {unknown()};
1701  if (!scope->bodyStart)
1702  return {unknown()};
1703  for (const Token* tok = scope->bodyStart->next(); precedes(tok, scope->bodyEnd); tok = tok->next()) {
1704  const Token* top = tok->astTop();
1705  if (!top)
1706  return {unknown()};
1707 
1708  if (Token::simpleMatch(top, "return") && top->astOperand1())
1709  return {execute(top->astOperand1())};
1710 
1711  if (Token::Match(top, "%op%")) {
1712  if (execute(top).isUninitValue())
1713  return {unknown()};
1714  const Token* next = nextAfterAstRightmostLeaf(top);
1715  if (!next)
1716  return {unknown()};
1717  tok = next;
1718  } else if (Token::simpleMatch(top->previous(), "if (")) {
1719  const Token* condTok = top->astOperand2();
1720  ValueFlow::Value v = execute(condTok);
1721  if (!v.isIntValue())
1722  return {unknown()};
1723  const Token* thenStart = top->link()->next();
1724  const Token* next = thenStart->link();
1725  const Token* elseStart = nullptr;
1726  if (Token::simpleMatch(thenStart->link(), "} else {")) {
1727  elseStart = thenStart->link()->tokAt(2);
1728  next = elseStart->link();
1729  }
1730  std::vector<ValueFlow::Value> result;
1731  if (isTrue(v)) {
1732  result = execute(thenStart->scope());
1733  } else if (isFalse(v)) {
1734  if (elseStart)
1735  result = execute(elseStart->scope());
1736  } else {
1737  return {unknown()};
1738  }
1739  if (!result.empty())
1740  return result;
1741  tok = next;
1742  } else {
1743  return {unknown()};
1744  }
1745  }
1746  return {};
1747  }
1748  };
1749 } // namespace
1750 
1751 static ValueFlow::Value execute(const Token* expr, ProgramMemory& pm, const Settings& settings)
1752 {
1753  Executor ex{&pm, &settings};
1754  return ex.execute(expr);
1755 }
1756 
1757 std::vector<ValueFlow::Value> execute(const Scope* scope, ProgramMemory& pm, const Settings& settings)
1758 {
1759  Executor ex{&pm, &settings};
1760  return ex.execute(scope);
1761 }
1762 
1763 ValueFlow::Value evaluateLibraryFunction(const std::unordered_map<nonneg int, ValueFlow::Value>& args,
1764  const std::string& returnValue,
1765  const Settings& settings,
1766  bool cpp)
1767 {
1768  thread_local static std::unordered_map<std::string,
1769  std::function<ValueFlow::Value(const std::unordered_map<nonneg int, ValueFlow::Value>& arg)>>
1770  functions = {};
1771  if (functions.count(returnValue) == 0) {
1772 
1773  std::unordered_map<nonneg int, const Token*> lookupVarId;
1774  std::shared_ptr<Token> expr = createTokenFromExpression(returnValue, settings, cpp, &lookupVarId);
1775 
1776  functions[returnValue] =
1777  [lookupVarId, expr, settings](const std::unordered_map<nonneg int, ValueFlow::Value>& xargs) {
1778  if (!expr)
1779  return ValueFlow::Value::unknown();
1780  ProgramMemory pm{};
1781  for (const auto& p : xargs) {
1782  auto it = lookupVarId.find(p.first);
1783  if (it != lookupVarId.end())
1784  pm.setValue(it->second, p.second);
1785  }
1786  return execute(expr.get(), pm, settings);
1787  };
1788  }
1789  return functions.at(returnValue)(args);
1790 }
1791 
1792 void execute(const Token* expr,
1793  ProgramMemory& programMemory,
1794  MathLib::bigint* result,
1795  bool* error,
1796  const Settings& settings)
1797 {
1798  ValueFlow::Value v = execute(expr, programMemory, settings);
1799  if (!v.isIntValue() || v.isImpossible()) {
1800  if (error)
1801  *error = true;
1802  } else if (result)
1803  *result = v.intvalue;
1804 }
bool astIsContainer(const Token *tok)
Definition: astutils.cpp:244
std::vector< const Token * > getArguments(const Token *ftok)
Get arguments (AST)
Definition: astutils.cpp:3083
bool precedes(const Token *tok1, const Token *tok2)
If tok2 comes after tok1.
Definition: astutils.cpp:994
bool isUsedAsBool(const Token *const tok, const Settings &settings)
Is token used as boolean, that is to say cast to a bool, or used as a condition in a if/while/for.
Definition: astutils.cpp:1489
const Token * findExpressionChanged(const Token *expr, const Token *start, const Token *end, const Settings &settings, int depth)
Definition: astutils.cpp:3028
bool astHasExpr(const Token *tok, nonneg int exprid)
Definition: astutils.cpp:152
std::vector< const Token * > astFlatten(const Token *tok, const char *op)
Definition: astutils.cpp:110
Token * getCondTokFromEnd(Token *endBlock)
Definition: astutils.cpp:889
const Token * nextAfterAstRightmostLeaf(const Token *tok)
Definition: astutils.cpp:548
bool astIsUnsigned(const Token *tok)
Definition: astutils.cpp:202
const Token * previousBeforeAstLeftmostLeaf(const Token *tok)
Definition: astutils.cpp:514
const Token * findExpressionChangedSkipDeadCode(const Token *expr, const Token *start, const Token *end, const Settings &settings, const std::function< std::vector< MathLib::bigint >(const Token *tok)> &evaluate, int depth)
Definition: astutils.cpp:3037
nonneg int astCount(const Token *tok, const char *op, int depth)
Definition: astutils.cpp:124
bool isVariableChanged(const Token *tok, int indirect, const Settings &settings, int depth)
Definition: astutils.cpp:2546
void visitAstNodes(T *ast, const TFunc &visitor)
Visit AST nodes recursively.
Definition: astutils.h:54
bool isEqual(T x, T y)
Definition: calculate.h:28
R calculate(const std::string &s, const T &x, const T &y, bool *error=nullptr)
Definition: calculate.h:50
This class will take a list of filenames and settings and check then all files using threads.
Definition: executor.h:43
Executor(const std::list< FileWithDetails > &files, const std::list< FileSettings > &fileSettings, const Settings &settings, SuppressionList &suppressions, ErrorLogger &errorLogger)
Definition: executor.cpp:33
const Scope * functionScope
scope of function body
const Variable * getArgumentVar(nonneg int num) const
bool isImplicitlyVirtual(bool defaultVal=false) const
check if this function is virtual in the base classes
Yield getYield(const std::string &function) const
Definition: library.h:255
const Token * getContainerFromYield(const Token *tok, Container::Yield yield) const
Definition: library.cpp:1664
const std::string & returnValue(const Token *ftok) const
Definition: library.cpp:1436
long long bigint
Definition: mathlib.h:68
static bigint toBigNumber(const std::string &str)
for conversion of numeric literals - for atoi-like conversions please use strToInt()
Definition: mathlib.cpp:368
static bool isFloat(const std::string &str)
Definition: mathlib.cpp:535
ScopeType type
const Scope * nestedIn
bool isLocal() const
const Token * bodyStart
'{' token
const Token * bodyEnd
'}' token
This is just a container for general settings so that we don't need to pass individual values to func...
Definition: settings.h:95
Library library
Library.
Definition: settings.h:237
The token list that the TokenList generates is a linked-list of this class.
Definition: token.h:150
void str(T &&s)
Definition: token.h:179
Token * astTop()
Definition: token.h:1416
static bool Match(const Token *tok, const char pattern[], nonneg int varid=0)
Match given token (or list of tokens) to a pattern list.
Definition: token.cpp:688
nonneg int exprId() const
Definition: token.h:883
bool hasKnownIntValue() const
Definition: token.cpp:2519
bool isBoolean() const
Definition: token.h:404
bool isCpp() const
Definition: token.cpp:2718
static nonneg int getStrLength(const Token *tok)
Definition: token.cpp:777
const ValueFlow::Value * getKnownValue(ValueFlow::Value::ValueType t) const
Definition: token.cpp:2552
const ValueType * valueType() const
Definition: token.h:331
const std::string & strAt(int index) const
Definition: token.cpp:423
void astOperand1(Token *tok)
Definition: token.cpp:1456
bool isNumber() const
Definition: token.h:371
void function(const Function *f)
Associate this token with given function.
Definition: token.cpp:1093
bool isCast() const
Definition: token.h:458
bool isLiteral() const
Definition: token.h:368
const Token * tokAt(int index) const
Definition: token.cpp:393
Token::Type tokType() const
Definition: token.h:343
void astOperand2(Token *tok)
Definition: token.cpp:1468
void scope(const Scope *s)
Associate this token with given scope.
Definition: token.h:1042
void link(Token *linkToToken)
Create link to given token.
Definition: token.h:1015
const Token * linkAt(int index) const
Definition: token.cpp:413
@ eString
Definition: token.h:162
@ eIncDecOp
Definition: token.h:163
Token * previous()
Definition: token.h:862
std::string strValue() const
This can be called only for tokens that are strings, else the assert() is called.
Definition: token.cpp:223
bool isAssignmentOp() const
Definition: token.h:401
bool isComparisonOp() const
Definition: token.h:398
Token * next()
Definition: token.h:830
const std::list< ValueFlow::Value > & values() const
Definition: token.h:1197
static bool simpleMatch(const Token *tok, const char(&pattern)[count])
Match given token (or list of tokens) to a pattern list.
Definition: token.h:252
void astParent(Token *tok)
Definition: token.cpp:1437
void setImpossible()
Definition: vfvalue.h:369
bool isIntValue() const
Definition: vfvalue.h:211
bool isSymbolicValue() const
Definition: vfvalue.h:244
bool isTokValue() const
Definition: vfvalue.h:214
Bound bound
The value bound
Definition: vfvalue.h:265
enum ValueFlow::Value::ValueType valueType
bool isIteratorValue() const
Definition: vfvalue.h:235
bool isFloatValue() const
Definition: vfvalue.h:217
@ Impossible
Listed values are impossible.
bool isImpossible() const
Definition: vfvalue.h:365
double floatValue
float value
Definition: vfvalue.h:274
bool isUninitValue() const
Definition: vfvalue.h:223
bool isKnown() const
Definition: vfvalue.h:353
static void visitValue(T &self, F f)
Definition: vfvalue.h:101
static Value unknown()
Definition: vfvalue.h:54
const Token * condition
Condition that this value depends on.
Definition: vfvalue.h:280
const Token * tokvalue
token value - the token that has the value.
Definition: vfvalue.h:271
long long intvalue
int value (or sometimes bool value?)
Definition: vfvalue.h:268
void setPossible()
Definition: vfvalue.h:357
enum ValueFlow::Value::ValueKind valueKind
bool isContainerSizeValue() const
Definition: vfvalue.h:226
void setKnown()
Definition: vfvalue.h:349
const Library::Container * container
If the type is a container defined in a cfg file, this is the used.
Information about a member variable.
const Token * nameToken() const
Get name token.
#define nonneg
Definition: config.h:138
std::shared_ptr< Token > createTokenFromExpression(const std::string &returnValue, const Settings &settings, bool cpp, std::unordered_map< nonneg int, const Token * > *lookupVarId)
Definition: library.cpp:1764
@ error
Programming error.
std::vector< ValueFlow::Value > infer(const ValuePtr< InferModel > &model, const std::string &op, std::list< ValueFlow::Value > lhsValues, std::list< ValueFlow::Value > rhsValues)
Definition: infer.cpp:286
const Token * parseCompareInt(const Token *tok, Value &true_value, Value &false_value, const std::function< std::vector< MathLib::bigint >(const Token *)> &evaluate)
Definition: valueflow.cpp:350
CPPCHECKLIB ValuePtr< InferModel > makeIntegralInferModel()
Definition: valueflow.cpp:6977
void combineValueProperties(const Value &value1, const Value &value2, Value &result)
Definition: valueflow.cpp:424
Value asImpossible(Value v)
Definition: valueflow.cpp:6269
static BuiltinLibraryFunction getBuiltinLibraryFunction(const std::string &name)
bool conditionIsFalse(const Token *condition, ProgramMemory pm, const Settings &settings)
Is condition always false when variable has given value?
static bool frontIs(const std::vector< MathLib::bigint > &v, bool i)
static bool isTrueOrFalse(const ValueFlow::Value &v, bool b)
static ValueFlow::Value execute(const Token *expr, ProgramMemory &pm, const Settings &settings)
static bool isFalse(const ValueFlow::Value &v)
static ValueFlow::Value evaluate(const std::string &op, const ValueFlow::Value &lhs, const ValueFlow::Value &rhs)
static void programMemoryParseCondition(ProgramMemory &pm, const Token *tok, const Token *endTok, const Settings &settings, bool then)
static bool evalSameCondition(const ProgramMemory &state, const Token *storedValue, const Token *cond, const Settings &settings)
static bool isNumericValue(const ValueFlow::Value &value)
static bool isTrue(const ValueFlow::Value &v)
static std::string removeAssign(const std::string &assign)
static std::vector< const Token * > setDifference(const std::vector< const Token * > &v1, const std::vector< const Token * > &v2)
ProgramMemory getProgramMemory(const Token *tok, const Token *expr, const ValueFlow::Value &value, const Settings &settings)
Get program memory by looking backwards from given token.
static bool isIntegralValue(const ValueFlow::Value &value)
static bool evaluateCondition(MathLib::bigint r, const Token *condition, ProgramMemory &pm, const Settings &settings)
ValueFlow::Value evaluateLibraryFunction(const std::unordered_map< nonneg int, ValueFlow::Value > &args, const std::string &returnValue, const Settings &settings, bool cpp)
static void removeModifiedVars(ProgramMemory &pm, const Token *tok, const Token *origin, const Settings &settings)
static bool isBasicForLoop(const Token *tok)
static void fillProgramMemoryFromConditions(ProgramMemory &pm, const Scope *scope, const Token *endTok, const Settings &settings)
static bool TokenExprIdCompare(const Token *tok1, const Token *tok2)
static void addVars(ProgramMemory &pm, const ProgramMemory::Map &vars)
static std::unordered_map< std::string, BuiltinLibraryFunction > createBuiltinLibraryFunctions()
std::function< ValueFlow::Value(const std::vector< ValueFlow::Value > &)> BuiltinLibraryFunction
bool conditionIsTrue(const Token *condition, ProgramMemory pm, const Settings &settings)
Is condition always true when variable has given value?
static bool TokenExprIdEqual(const Token *tok1, const Token *tok2)
static void pruneConditions(std::vector< const Token * > &conds, bool b, const std::unordered_map< nonneg int, ValueFlow::Value > &state)
static double asFloat(const ValueFlow::Value &value)
static void fillProgramMemoryFromAssignments(ProgramMemory &pm, const Token *tok, const Settings &settings, const ProgramMemory &state, const ProgramMemory::Map &vars)
static ProgramMemory getInitialProgramState(const Token *tok, const Token *origin, const Settings &settings, const ProgramMemory::Map &vars=ProgramMemory::Map {})
std::size_t operator()(ExprIdToken etok) const
nonneg int exprid
Definition: programmemory.h:41
ExprIdToken()=default
const Token * tok
Definition: programmemory.h:40
nonneg int getExpressionId() const
Definition: utils.h:53
ProgramMemoryState(const Settings *s)
void assume(const Token *tok, bool b, bool isEmpty=false)
std::map< nonneg int, const Token * > origins
void replace(ProgramMemory pm, const Token *origin=nullptr)
void removeModifiedVars(const Token *tok)
ProgramMemory get(const Token *tok, const Token *ctx, const ProgramMemory::Map &vars) const
void insert(const ProgramMemory &pm, const Token *origin=nullptr)
ProgramMemory state
void addState(const Token *tok, const ProgramMemory::Map &vars)
const Settings * settings
void setValue(const Token *expr, const ValueFlow::Value &value)
bool getIntValue(nonneg int exprid, MathLib::bigint &result) const
void insert(const ProgramMemory &pm)
bool getTokValue(nonneg int exprid, const Token *&result) const
void setUnknown(const Token *expr)
const ValueFlow::Value * getValue(nonneg int exprid, bool impossible=false) const
void erase_if(const std::function< bool(const ExprIdToken &)> &pred)
bool getContainerEmptyValue(nonneg int exprid, MathLib::bigint &result) const
bool getContainerSizeValue(nonneg int exprid, MathLib::bigint &result) const
const ValueFlow::Value & at(nonneg int exprid) const
void setContainerSizeValue(const Token *expr, MathLib::bigint value, bool isEqual=true)
std::unordered_map< ExprIdToken, ValueFlow::Value, ExprIdToken::Hash > Map
void replace(ProgramMemory pm)
bool hasValue(nonneg int exprid)
bool empty() const
void swap(ProgramMemory &pm)
void setIntValue(const Token *expr, MathLib::bigint value, bool impossible=false)
static std::string getStringLiteral(const std::string &str)
Definition: utils.h:175
bool contains(const Range &r, const T &x)
Definition: utils.h:62
static const Token * solveExprValue(const Token *expr, ValueFlow::Value &value)
Definition: valueflow.cpp:8434