Cppcheck
forwardanalyzer.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 "forwardanalyzer.h"
20 
21 #include "analyzer.h"
22 #include "astutils.h"
23 #include "config.h"
24 #include "errorlogger.h"
25 #include "errortypes.h"
26 #include "mathlib.h"
27 #include "settings.h"
28 #include "symboldatabase.h"
29 #include "token.h"
30 #include "tokenlist.h"
31 #include "utils.h"
32 #include "valueptr.h"
33 #include "vfvalue.h"
34 
35 #include <algorithm>
36 #include <cassert>
37 #include <cstdio>
38 #include <functional>
39 #include <list>
40 #include <string>
41 #include <tuple>
42 #include <type_traits>
43 #include <utility>
44 #include <vector>
45 
46 namespace {
47  struct ForwardTraversal {
48  enum class Progress { Continue, Break, Skip };
49  enum class Terminate { None, Bail, Inconclusive };
50  ForwardTraversal(const ValuePtr<Analyzer>& analyzer, const TokenList& tokenList, ErrorLogger& errorLogger, const Settings& settings)
51  : analyzer(analyzer), tokenList(tokenList), errorLogger(errorLogger), settings(settings)
52  {}
53  ValuePtr<Analyzer> analyzer;
54  const TokenList& tokenList;
55  ErrorLogger& errorLogger;
56  const Settings& settings;
57  Analyzer::Action actions;
58  bool analyzeOnly{};
59  bool analyzeTerminate{};
61  std::vector<Token*> loopEnds;
62  int branchCount = 0;
63 
65  if ((!analyzeOnly || analyzeTerminate) && t != Analyzer::Terminate::None)
66  terminate = t;
67  return Progress::Break;
68  }
69 
70  struct Branch {
71  explicit Branch(Token* tok = nullptr) : endBlock(tok) {}
72  Token* endBlock = nullptr;
74  bool check = false;
75  bool escape = false;
76  bool escapeUnknown = false;
77  bool active = false;
78  bool isEscape() const {
79  return escape || escapeUnknown;
80  }
81  bool isConclusiveEscape() const {
82  return escape && !escapeUnknown;
83  }
84  bool isModified() const {
85  return action.isModified() && !isConclusiveEscape();
86  }
87  bool isInconclusive() const {
88  return action.isInconclusive() && !isConclusiveEscape();
89  }
90  bool isDead() const {
91  return action.isModified() || action.isInconclusive() || isEscape();
92  }
93  };
94 
95  bool stopUpdates() {
96  analyzeOnly = true;
97  return actions.isModified();
98  }
99 
100  std::pair<bool, bool> evalCond(const Token* tok, const Token* ctx = nullptr) const {
101  if (!tok)
102  return std::make_pair(false, false);
103  std::vector<MathLib::bigint> result = analyzer->evaluate(tok, ctx);
104  // TODO: We should convert to bool
105  const bool checkThen = std::any_of(result.cbegin(), result.cend(), [](int x) {
106  return x != 0;
107  });
108  const bool checkElse = std::any_of(result.cbegin(), result.cend(), [](int x) {
109  return x == 0;
110  });
111  return std::make_pair(checkThen, checkElse);
112  }
113 
114  bool isConditionTrue(const Token* tok, const Token* ctx = nullptr) const {
115  return evalCond(tok, ctx).first;
116  }
117 
118  template<class T, class F, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>
119  Progress traverseTok(T* tok, const F &f, bool traverseUnknown, T** out = nullptr) {
120  if (Token::Match(tok, "asm|goto"))
121  return Break(Analyzer::Terminate::Bail);
122  if (Token::Match(tok, "setjmp|longjmp (")) {
123  // Traverse the parameters of the function before escaping
124  traverseRecursive(tok->next()->astOperand2(), f, traverseUnknown);
125  return Break(Analyzer::Terminate::Bail);
126  }
127  if (Token::simpleMatch(tok, "continue")) {
128  if (loopEnds.empty())
129  return Break(Analyzer::Terminate::Escape);
130  // If we are in a loop then jump to the end
131  if (out)
132  *out = loopEnds.back();
133  } else if (Token::Match(tok, "return|throw")) {
134  traverseRecursive(tok->astOperand2(), f, traverseUnknown);
135  traverseRecursive(tok->astOperand1(), f, traverseUnknown);
136  return Break(Analyzer::Terminate::Escape);
137  } else if (Token::Match(tok, "%name% (") && isEscapeFunction(tok, &settings.library)) {
138  // Traverse the parameters of the function before escaping
139  traverseRecursive(tok->next()->astOperand2(), f, traverseUnknown);
140  return Break(Analyzer::Terminate::Escape);
141  } else if (isUnevaluated(tok->previous())) {
142  if (out)
143  *out = tok->link();
144  return Progress::Skip;
145  } else if (tok->astOperand1() && tok->astOperand2() && Token::Match(tok, "?|&&|%oror%")) {
146  if (traverseConditional(tok, f, traverseUnknown) == Progress::Break)
147  return Break();
148  if (out)
149  *out = nextAfterAstRightmostLeaf(tok);
150  return Progress::Skip;
151  // Skip lambdas
152  } else if (T* lambdaEndToken = findLambdaEndToken(tok)) {
153  if (checkScope(lambdaEndToken).isModified())
154  return Break(Analyzer::Terminate::Bail);
155  if (out)
156  *out = lambdaEndToken->next();
157  // Skip class scope
158  } else if (tok->str() == "{" && tok->scope() && tok->scope()->isClassOrStruct()) {
159  if (out)
160  *out = tok->link();
161  } else {
162  if (f(tok) == Progress::Break)
163  return Break();
164  }
165  return Progress::Continue;
166  }
167 
168  template<class T, class F, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>
169  Progress traverseRecursive(T* tok, const F &f, bool traverseUnknown, unsigned int recursion=0) {
170  if (!tok)
171  return Progress::Continue;
172  if (recursion > 10000)
173  return Progress::Skip;
174  T* firstOp = tok->astOperand1();
175  T* secondOp = tok->astOperand2();
176  // Evaluate:
177  // 1. RHS of assignment before LHS
178  // 2. Unary op before operand
179  // 3. Function arguments before function call
180  if (tok->isAssignmentOp() || !secondOp || isFunctionCall(tok))
181  std::swap(firstOp, secondOp);
182  if (firstOp && traverseRecursive(firstOp, f, traverseUnknown, recursion+1) == Progress::Break)
183  return Break();
184  const Progress p = tok->isAssignmentOp() ? Progress::Continue : traverseTok(tok, f, traverseUnknown);
185  if (p == Progress::Break)
186  return Break();
187  if (p == Progress::Continue && secondOp && traverseRecursive(secondOp, f, traverseUnknown, recursion+1) == Progress::Break)
188  return Break();
189  if (tok->isAssignmentOp() && traverseTok(tok, f, traverseUnknown) == Progress::Break)
190  return Break();
191  return Progress::Continue;
192  }
193 
194  template<class T, class F, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>
195  Progress traverseConditional(T* tok, F f, bool traverseUnknown) {
196  if (Token::Match(tok, "?|&&|%oror%") && tok->astOperand1() && tok->astOperand2()) {
197  T* condTok = tok->astOperand1();
198  T* childTok = tok->astOperand2();
199  bool checkThen, checkElse;
200  std::tie(checkThen, checkElse) = evalCond(condTok);
201  if (!checkThen && !checkElse) {
202  if (!traverseUnknown && analyzer->stopOnCondition(condTok) && stopUpdates()) {
203  return Progress::Continue;
204  }
205  checkThen = true;
206  checkElse = true;
207  }
208  if (childTok->str() == ":") {
209  if (checkThen && traverseRecursive(childTok->astOperand1(), f, traverseUnknown) == Progress::Break)
210  return Break();
211  if (checkElse && traverseRecursive(childTok->astOperand2(), f, traverseUnknown) == Progress::Break)
212  return Break();
213  } else {
214  if (!checkThen && tok->str() == "&&")
215  return Progress::Continue;
216  if (!checkElse && tok->str() == "||")
217  return Progress::Continue;
218  if (traverseRecursive(childTok, f, traverseUnknown) == Progress::Break)
219  return Break();
220  }
221  }
222  return Progress::Continue;
223  }
224 
225  Progress update(Token* tok) {
226  Analyzer::Action action = analyzer->analyze(tok, Analyzer::Direction::Forward);
227  actions |= action;
228  if (!action.isNone() && !analyzeOnly)
229  analyzer->update(tok, action, Analyzer::Direction::Forward);
230  if (action.isInconclusive() && !analyzer->lowerToInconclusive())
231  return Break(Analyzer::Terminate::Inconclusive);
232  if (action.isInvalid())
233  return Break(Analyzer::Terminate::Modified);
234  if (action.isWrite() && !action.isRead())
235  // Analysis of this write will continue separately
236  return Break(Analyzer::Terminate::Modified);
237  return Progress::Continue;
238  }
239 
240  Progress updateTok(Token* tok, Token** out = nullptr) {
241  auto f = [this](Token* tok2) {
242  return update(tok2);
243  };
244  return traverseTok(tok, f, false, out);
245  }
246 
247  Progress updateRecursive(Token* tok) {
248  auto f = [this](Token* tok2) {
249  return update(tok2);
250  };
251  return traverseRecursive(tok, f, false);
252  }
253 
254  Analyzer::Action analyzeRecursive(const Token* start) {
256  auto f = [&](const Token* tok) {
257  result = analyzer->analyze(tok, Analyzer::Direction::Forward);
258  if (result.isModified() || result.isInconclusive())
259  return Break();
260  return Progress::Continue;
261  };
262  traverseRecursive(start, f, true);
263  return result;
264  }
265 
266  Analyzer::Action analyzeRange(const Token* start, const Token* end) const {
268  for (const Token* tok = start; tok && tok != end; tok = tok->next()) {
269  Analyzer::Action action = analyzer->analyze(tok, Analyzer::Direction::Forward);
270  if (action.isModified() || action.isInconclusive())
271  return action;
272  result |= action;
273  }
274  return result;
275  }
276 
277  ForwardTraversal fork(bool analyze = false) const {
278  ForwardTraversal ft = *this;
279  if (analyze) {
280  ft.analyzeOnly = true;
281  ft.analyzeTerminate = true;
282  }
283  ft.actions = Analyzer::Action::None;
284  return ft;
285  }
286 
287  std::vector<ForwardTraversal> tryForkScope(Token* endBlock, bool isModified = false) const {
288  if (analyzer->updateScope(endBlock, isModified)) {
289  ForwardTraversal ft = fork();
290  return {std::move(ft)};
291  }
292  return std::vector<ForwardTraversal> {};
293  }
294 
295  std::vector<ForwardTraversal> tryForkUpdateScope(Token* endBlock, bool isModified = false) const {
296  std::vector<ForwardTraversal> result = tryForkScope(endBlock, isModified);
297  for (ForwardTraversal& ft : result)
298  ft.updateScope(endBlock);
299  return result;
300  }
301 
302  static bool hasGoto(const Token* endBlock) {
303  return Token::findsimplematch(endBlock->link(), "goto", endBlock);
304  }
305 
306  static bool hasJump(const Token* endBlock) {
307  return Token::findmatch(endBlock->link(), "goto|break", endBlock);
308  }
309 
310  bool hasInnerReturnScope(const Token* start, const Token* end) const {
311  for (const Token* tok=start; tok != end; tok = tok->previous()) {
312  if (Token::simpleMatch(tok, "}")) {
313  const Token* ftok = nullptr;
314  const bool r = isReturnScope(tok, settings.library, &ftok);
315  if (r)
316  return true;
317  }
318  }
319  return false;
320  }
321 
322  bool isEscapeScope(const Token* endBlock, bool& unknown) const {
323  const Token* ftok = nullptr;
324  const bool r = isReturnScope(endBlock, settings.library, &ftok);
325  if (!r && ftok)
326  unknown = true;
327  return r;
328  }
329 
330  enum class Status {
331  None,
332  Inconclusive,
333  };
334 
335  Analyzer::Action analyzeScope(const Token* endBlock) const {
336  return analyzeRange(endBlock->link(), endBlock);
337  }
338 
339  Analyzer::Action checkScope(Token* endBlock) const {
340  Analyzer::Action a = analyzeScope(endBlock);
341  tryForkUpdateScope(endBlock, a.isModified());
342  return a;
343  }
344 
345  Analyzer::Action checkScope(const Token* endBlock) const {
346  Analyzer::Action a = analyzeScope(endBlock);
347  return a;
348  }
349 
350  bool checkBranch(Branch& branch) const {
351  Analyzer::Action a = analyzeScope(branch.endBlock);
352  branch.action = a;
353  std::vector<ForwardTraversal> ft1 = tryForkUpdateScope(branch.endBlock, a.isModified());
354  const bool bail = hasGoto(branch.endBlock);
355  if (!a.isModified() && !bail) {
356  if (ft1.empty()) {
357  // Traverse into the branch to see if there is a conditional escape
358  if (!branch.escape && hasInnerReturnScope(branch.endBlock->previous(), branch.endBlock->link())) {
359  ForwardTraversal ft2 = fork(true);
360  ft2.updateScope(branch.endBlock);
361  if (ft2.terminate == Analyzer::Terminate::Escape) {
362  branch.escape = true;
363  branch.escapeUnknown = false;
364  }
365  }
366  } else {
367  if (ft1.front().terminate == Analyzer::Terminate::Escape) {
368  branch.escape = true;
369  branch.escapeUnknown = false;
370  }
371  }
372  }
373  return bail;
374  }
375 
376  bool reentersLoop(Token* endBlock, const Token* condTok, const Token* stepTok) const {
377  if (!condTok)
378  return true;
379  if (Token::simpleMatch(condTok, ":"))
380  return true;
381  bool stepChangesCond = false;
382  if (stepTok) {
383  std::pair<const Token*, const Token*> exprToks = stepTok->findExpressionStartEndTokens();
384  if (exprToks.first != nullptr && exprToks.second != nullptr)
385  stepChangesCond |=
386  findExpressionChanged(condTok, exprToks.first, exprToks.second->next(), settings) != nullptr;
387  }
388  const bool bodyChangesCond = findExpressionChanged(condTok, endBlock->link(), endBlock, settings);
389  // Check for mutation in the condition
390  const bool condChanged =
391  nullptr != findAstNode(condTok, [&](const Token* tok) {
392  return isVariableChanged(tok, 0, settings);
393  });
394  const bool changed = stepChangesCond || bodyChangesCond || condChanged;
395  if (!changed)
396  return true;
397  ForwardTraversal ft = fork(true);
398  ft.updateScope(endBlock);
399  return ft.isConditionTrue(condTok) && bodyChangesCond;
400  }
401 
402  Progress updateInnerLoop(Token* endBlock, Token* stepTok, Token* condTok) {
403  loopEnds.push_back(endBlock);
404  OnExit oe{[&] {
405  loopEnds.pop_back();
406  }};
407  if (endBlock && updateScope(endBlock) == Progress::Break)
408  return Break();
409  if (stepTok && updateRecursive(stepTok) == Progress::Break)
410  return Break();
411  if (condTok && !Token::simpleMatch(condTok, ":") && updateRecursive(condTok) == Progress::Break)
412  return Break();
413  return Progress::Continue;
414  }
415 
416  Progress updateLoop(const Token* endToken,
417  Token* endBlock,
418  Token* condTok,
419  Token* initTok = nullptr,
420  Token* stepTok = nullptr,
421  bool exit = false) {
422  if (initTok && updateRecursive(initTok) == Progress::Break)
423  return Break();
424  const bool isDoWhile = precedes(endBlock, condTok);
425  bool checkThen = true;
426  bool checkElse = false;
427  if (condTok && !Token::simpleMatch(condTok, ":"))
428  std::tie(checkThen, checkElse) = evalCond(condTok, isDoWhile ? endBlock->previous() : nullptr);
429  // exiting a do while(false)
430  if (checkElse && exit) {
431  if (hasJump(endBlock)) {
432  if (!analyzer->lowerToPossible())
433  return Break(Analyzer::Terminate::Bail);
434  if (analyzer->isConditional() && stopUpdates())
435  return Break(Analyzer::Terminate::Conditional);
436  }
437  return Progress::Continue;
438  }
439  Analyzer::Action bodyAnalysis = analyzeScope(endBlock);
440  Analyzer::Action allAnalysis = bodyAnalysis;
441  Analyzer::Action condAnalysis;
442  if (condTok) {
443  condAnalysis = analyzeRecursive(condTok);
444  allAnalysis |= condAnalysis;
445  }
446  if (stepTok)
447  allAnalysis |= analyzeRecursive(stepTok);
448  actions |= allAnalysis;
449  // do while(false) is not really a loop
450  if (checkElse && isDoWhile &&
451  (condTok->hasKnownIntValue() ||
452  (!bodyAnalysis.isModified() && !condAnalysis.isModified() && condAnalysis.isRead()))) {
453  if (updateScope(endBlock) == Progress::Break)
454  return Break();
455  return updateRecursive(condTok);
456  }
457  if (allAnalysis.isInconclusive()) {
458  if (!analyzer->lowerToInconclusive())
459  return Break(Analyzer::Terminate::Bail);
460  } else if (allAnalysis.isModified() || (exit && allAnalysis.isIdempotent())) {
461  if (!analyzer->lowerToPossible())
462  return Break(Analyzer::Terminate::Bail);
463  }
464 
465  if (condTok && !Token::simpleMatch(condTok, ":")) {
466  if (!isDoWhile || (!bodyAnalysis.isModified() && !bodyAnalysis.isIdempotent()))
467  if (updateRecursive(condTok) == Progress::Break)
468  return Break();
469  }
470  if (!checkThen && !checkElse && !isDoWhile && analyzer->stopOnCondition(condTok) && stopUpdates())
471  return Break(Analyzer::Terminate::Conditional);
472  // condition is false, we don't enter the loop
473  if (checkElse)
474  return Progress::Continue;
475  if (checkThen || isDoWhile) {
476  // Since we are re-entering the loop then assume the condition is true to update the state
477  if (exit)
478  analyzer->assume(condTok, true, Analyzer::Assume::Quiet | Analyzer::Assume::Absolute);
479  if (updateInnerLoop(endBlock, stepTok, condTok) == Progress::Break)
480  return Break();
481  // If loop re-enters then it could be modified again
482  if (allAnalysis.isModified() && reentersLoop(endBlock, condTok, stepTok))
483  return Break(Analyzer::Terminate::Bail);
484  if (allAnalysis.isIncremental())
485  return Break(Analyzer::Terminate::Bail);
486  } else if (allAnalysis.isModified()) {
487  std::vector<ForwardTraversal> ftv = tryForkScope(endBlock, allAnalysis.isModified());
488  bool forkContinue = true;
489  for (ForwardTraversal& ft : ftv) {
490  if (condTok)
491  ft.analyzer->assume(condTok, false, Analyzer::Assume::Quiet);
492  if (ft.updateInnerLoop(endBlock, stepTok, condTok) == Progress::Break)
493  forkContinue = false;
494  }
495 
496  if (allAnalysis.isModified() || !forkContinue) {
497  // TODO: Don't bail on missing condition
498  if (!condTok)
499  return Break(Analyzer::Terminate::Bail);
500  if (analyzer->isConditional() && stopUpdates())
501  return Break(Analyzer::Terminate::Conditional);
502  analyzer->assume(condTok, false);
503  }
504  if (forkContinue) {
505  for (ForwardTraversal& ft : ftv) {
506  if (!ft.actions.isIncremental())
507  ft.updateRange(endBlock, endToken);
508  }
509  }
510  if (allAnalysis.isIncremental())
511  return Break(Analyzer::Terminate::Bail);
512  } else {
513  if (updateInnerLoop(endBlock, stepTok, condTok) == Progress::Break)
514  return Progress::Break;
515  if (allAnalysis.isIncremental())
516  return Break(Analyzer::Terminate::Bail);
517  }
518  return Progress::Continue;
519  }
520 
521  Progress updateLoopExit(const Token* endToken,
522  Token* endBlock,
523  Token* condTok,
524  Token* initTok = nullptr,
525  Token* stepTok = nullptr) {
526  return updateLoop(endToken, endBlock, condTok, initTok, stepTok, true);
527  }
528 
529  Progress updateScope(Token* endBlock, int depth = 20)
530  {
531  if (!endBlock)
532  return Break();
533  assert(endBlock->link());
534  Token* ctx = endBlock->link()->previous();
535  if (Token::simpleMatch(ctx, ")"))
536  ctx = ctx->link()->previous();
537  if (ctx)
538  analyzer->updateState(ctx);
539  return updateRange(endBlock->link(), endBlock, depth);
540  }
541 
542  Progress updateRange(Token* start, const Token* end, int depth = 20) {
543  if (depth < 0)
544  return Break(Analyzer::Terminate::Bail);
545  std::size_t i = 0;
546  for (Token* tok = start; precedes(tok, end); tok = tok->next()) {
547  Token* next = nullptr;
548  if (tok->index() <= i)
549  throw InternalError(tok, "Cyclic forward analysis.");
550  i = tok->index();
551 
552  if (tok->link()) {
553  // Skip casts..
554  if (tok->str() == "(" && !tok->astOperand2() && tok->isCast()) {
555  tok = tok->link();
556  continue;
557  }
558  // Skip template arguments..
559  if (tok->str() == "<") {
560  tok = tok->link();
561  continue;
562  }
563  }
564 
565  // Evaluate RHS of assignment before LHS
566  if (Token* assignTok = assignExpr(tok)) {
567  if (updateRecursive(assignTok) == Progress::Break)
568  return Break();
569  tok = nextAfterAstRightmostLeaf(assignTok);
570  if (!tok)
571  return Break();
572  } else if (Token::simpleMatch(tok, ") {") && Token::Match(tok->link()->previous(), "for|while (") &&
573  !Token::simpleMatch(tok->link()->astOperand2(), ":")) {
574  // In the middle of a loop structure so bail
575  return Break(Analyzer::Terminate::Bail);
576  } else if (tok->str() == ";" && tok->astParent()) {
577  Token* top = tok->astTop();
578  if (top && Token::Match(top->previous(), "for|while (") && Token::simpleMatch(top->link(), ") {")) {
579  Token* endCond = top->link();
580  Token* endBlock = endCond->linkAt(1);
581  Token* condTok = getCondTok(top);
582  Token* stepTok = getStepTok(top);
583  // The semicolon should belong to the initTok otherwise something went wrong, so just bail
584  if (tok->astOperand2() != condTok && !Token::simpleMatch(tok->astOperand2(), ";"))
585  return Break(Analyzer::Terminate::Bail);
586  if (updateLoop(end, endBlock, condTok, nullptr, stepTok) == Progress::Break)
587  return Break();
588  }
589  } else if (tok->str() == "break") {
590  const Token *scopeEndToken = findNextTokenFromBreak(tok);
591  if (!scopeEndToken)
592  return Break();
593  tok = skipTo(tok, scopeEndToken, end);
594  if (!precedes(tok, end))
595  return Break(Analyzer::Terminate::Escape);
596  if (!analyzer->lowerToPossible())
597  return Break(Analyzer::Terminate::Bail);
598  // TODO: Don't break, instead move to the outer scope
599  if (!tok)
600  return Break();
601  } else if (!tok->variable() && (Token::Match(tok, "%name% :") || tok->str() == "case")) {
602  if (!analyzer->lowerToPossible())
603  return Break(Analyzer::Terminate::Bail);
604  } else if (tok->link() && tok->str() == "}") {
605  const Scope* scope = tok->scope();
606  if (!scope)
607  return Break();
609  const bool inElse = scope->type == Scope::eElse;
610  const bool inDoWhile = scope->type == Scope::eDo;
611  const bool inLoop = contains({Scope::eDo, Scope::eFor, Scope::eWhile}, scope->type);
612  Token* condTok = getCondTokFromEnd(tok);
613  if (!condTok)
614  return Break();
615  if (!condTok->hasKnownIntValue() || inLoop) {
616  if (!analyzer->lowerToPossible())
617  return Break(Analyzer::Terminate::Bail);
618  } else if (condTok->values().front().intvalue == inElse) {
619  return Break();
620  }
621  // Handle loop
622  if (inLoop) {
623  Token* stepTok = getStepTokFromEnd(tok);
624  bool checkThen, checkElse;
625  std::tie(checkThen, checkElse) = evalCond(condTok);
626  if (stepTok && !checkElse) {
627  if (updateRecursive(stepTok) == Progress::Break)
628  return Break();
629  if (updateRecursive(condTok) == Progress::Break)
630  return Break();
631  // Reevaluate condition
632  std::tie(checkThen, checkElse) = evalCond(condTok);
633  }
634  if (!checkElse) {
635  if (updateLoopExit(end, tok, condTok, nullptr, stepTok) == Progress::Break)
636  return Break();
637  }
638  }
639  analyzer->assume(condTok, !inElse, Analyzer::Assume::Quiet);
640  assert(!inDoWhile || Token::simpleMatch(tok, "} while ("));
641  if (Token::simpleMatch(tok, "} else {") || inDoWhile)
642  tok = tok->linkAt(2);
643  } else if (contains({Scope::eTry, Scope::eCatch}, scope->type)) {
644  if (!analyzer->lowerToPossible())
645  return Break(Analyzer::Terminate::Bail);
646  } else if (scope->type == Scope::eLambda) {
647  return Break();
648  }
649  } else if (tok->isControlFlowKeyword() && Token::Match(tok, "if|while|for (") &&
650  Token::simpleMatch(tok->next()->link(), ") {")) {
651  if (settings.checkLevel == Settings::CheckLevel::normal && ++branchCount > 4) {
652  // TODO: should be logged on function-level instead of file-level
653  reportError(Severity::information, "normalCheckLevelMaxBranches", "Limiting analysis of branches. Use --check-level=exhaustive to analyze all branches.");
654  return Break(Analyzer::Terminate::Bail);
655  }
656  Token* endCond = tok->next()->link();
657  Token* endBlock = endCond->next()->link();
658  Token* condTok = getCondTok(tok);
659  Token* initTok = getInitTok(tok);
660  if (initTok && updateRecursive(initTok) == Progress::Break)
661  return Break();
662  if (Token::Match(tok, "for|while (")) {
663  // For-range loop
664  if (Token::simpleMatch(condTok, ":")) {
665  Token* conTok = condTok->astOperand2();
666  if (conTok && updateRecursive(conTok) == Progress::Break)
667  return Break();
668  bool isEmpty = false;
669  std::vector<MathLib::bigint> result =
670  analyzer->evaluate(Analyzer::Evaluate::ContainerEmpty, conTok);
671  if (result.empty())
672  analyzer->assume(conTok, false, Analyzer::Assume::ContainerEmpty);
673  else
674  isEmpty = result.front() != 0;
675  if (!isEmpty && updateLoop(end, endBlock, condTok) == Progress::Break)
676  return Break();
677  } else {
678  Token* stepTok = getStepTok(tok);
679  // Dont pass initTok since it was already evaluated
680  if (updateLoop(end, endBlock, condTok, nullptr, stepTok) == Progress::Break)
681  return Break();
682  }
683  tok = endBlock;
684  } else {
685  // Traverse condition
686  if (updateRecursive(condTok) == Progress::Break)
687  return Break();
688  Branch thenBranch{endBlock};
689  Branch elseBranch{endBlock->tokAt(2) ? endBlock->linkAt(2) : nullptr};
690  // Check if condition is true or false
691  std::tie(thenBranch.check, elseBranch.check) = evalCond(condTok);
692  if (!thenBranch.check && !elseBranch.check && analyzer->stopOnCondition(condTok) && stopUpdates())
693  return Break(Analyzer::Terminate::Conditional);
694  const bool hasElse = Token::simpleMatch(endBlock, "} else {");
695  bool bail = false;
696 
697  // Traverse then block
698  thenBranch.escape = isEscapeScope(endBlock, thenBranch.escapeUnknown);
699  if (thenBranch.check) {
700  thenBranch.active = true;
701  if (updateScope(endBlock, depth - 1) == Progress::Break)
702  return Break();
703  } else if (!elseBranch.check) {
704  thenBranch.active = true;
705  if (checkBranch(thenBranch))
706  bail = true;
707  }
708  // Traverse else block
709  if (hasElse) {
710  elseBranch.escape = isEscapeScope(endBlock->linkAt(2), elseBranch.escapeUnknown);
711  if (elseBranch.check) {
712  elseBranch.active = true;
713  const Progress result = updateScope(endBlock->linkAt(2), depth - 1);
714  if (result == Progress::Break)
715  return Break();
716  } else if (!thenBranch.check) {
717  elseBranch.active = true;
718  if (checkBranch(elseBranch))
719  bail = true;
720  }
721  tok = endBlock->linkAt(2);
722  } else {
723  tok = endBlock;
724  }
725  if (thenBranch.active)
726  actions |= thenBranch.action;
727  if (elseBranch.active)
728  actions |= elseBranch.action;
729  if (bail)
730  return Break(Analyzer::Terminate::Bail);
731  if (thenBranch.isDead() && elseBranch.isDead()) {
732  if (thenBranch.isModified() && elseBranch.isModified())
733  return Break(Analyzer::Terminate::Modified);
734  if (thenBranch.isConclusiveEscape() && elseBranch.isConclusiveEscape())
735  return Break(Analyzer::Terminate::Escape);
736  return Break(Analyzer::Terminate::Bail);
737  }
738  // Conditional return
739  if (thenBranch.active && thenBranch.isEscape() && !hasElse) {
740  if (!thenBranch.isConclusiveEscape()) {
741  if (!analyzer->lowerToInconclusive())
742  return Break(Analyzer::Terminate::Bail);
743  } else if (thenBranch.check) {
744  return Break();
745  } else {
746  if (analyzer->isConditional() && stopUpdates())
747  return Break(Analyzer::Terminate::Conditional);
748  analyzer->assume(condTok, false);
749  }
750  }
751  if (thenBranch.isInconclusive() || elseBranch.isInconclusive()) {
752  if (!analyzer->lowerToInconclusive())
753  return Break(Analyzer::Terminate::Bail);
754  } else if (thenBranch.isModified() || elseBranch.isModified()) {
755  if (!hasElse && analyzer->isConditional() && stopUpdates())
756  return Break(Analyzer::Terminate::Conditional);
757  if (!analyzer->lowerToPossible())
758  return Break(Analyzer::Terminate::Bail);
759  analyzer->assume(condTok, elseBranch.isModified());
760  }
761  }
762  } else if (Token::simpleMatch(tok, "try {")) {
763  Token* endBlock = tok->next()->link();
764  ForwardTraversal tryTraversal = fork();
765  tryTraversal.updateScope(endBlock, depth - 1);
766  bool bail = tryTraversal.actions.isModified();
767  if (bail) {
768  actions = tryTraversal.actions;
769  terminate = tryTraversal.terminate;
770  return Break();
771  }
772 
773  while (Token::simpleMatch(endBlock, "} catch (")) {
774  Token* endCatch = endBlock->linkAt(2);
775  if (!Token::simpleMatch(endCatch, ") {"))
776  return Break();
777  endBlock = endCatch->linkAt(1);
778  ForwardTraversal ft = fork();
779  ft.updateScope(endBlock, depth - 1);
780  bail |= ft.terminate != Analyzer::Terminate::None || ft.actions.isModified();
781  }
782  if (bail)
783  return Break();
784  tok = endBlock;
785  } else if (Token::simpleMatch(tok, "do {")) {
786  Token* endBlock = tok->next()->link();
787  Token* condTok = Token::simpleMatch(endBlock, "} while (") ? endBlock->tokAt(2)->astOperand2() : nullptr;
788  if (updateLoop(end, endBlock, condTok) == Progress::Break)
789  return Break();
790  if (condTok)
791  tok = endBlock->linkAt(2)->next();
792  else
793  tok = endBlock;
794  } else if (Token::Match(tok, "assert|ASSERT (")) {
795  const Token* condTok = tok->next()->astOperand2();
796  bool checkThen, checkElse;
797  std::tie(checkThen, checkElse) = evalCond(condTok);
798  if (checkElse)
799  return Break();
800  if (!checkThen)
801  analyzer->assume(condTok, true, Analyzer::Assume::Quiet | Analyzer::Assume::Absolute);
802  } else if (Token::simpleMatch(tok, "switch (")) {
803  if (updateRecursive(tok->next()->astOperand2()) == Progress::Break)
804  return Break();
805  return Break();
806  } else if (Token* callTok = callExpr(tok)) {
807  // TODO: Dont traverse tokens a second time
808  if (start != callTok && tok != callTok && updateRecursive(callTok->astOperand1()) == Progress::Break)
809  return Break();
810  // Since the call could be an unknown macro, traverse the tokens as a range instead of recursively
811  if (!Token::simpleMatch(callTok, "( )") &&
812  updateRange(callTok->next(), callTok->link(), depth - 1) == Progress::Break)
813  return Break();
814  if (updateTok(callTok) == Progress::Break)
815  return Break();
816  tok = callTok->link();
817  if (!tok)
818  return Break();
819  } else {
820  if (updateTok(tok, &next) == Progress::Break)
821  return Break();
822  if (next) {
823  if (precedes(next, end))
824  tok = next->previous();
825  else
826  return Progress::Continue;
827  }
828  }
829  // Prevent infinite recursion
830  if (tok->next() == start)
831  break;
832  }
833  return Progress::Continue;
834  }
835 
836  void reportError(Severity severity, const std::string& id, const std::string& msg) {
837  ErrorMessage::FileLocation loc(tokenList.getSourceFilePath(), 0, 0);
838  const ErrorMessage errmsg({std::move(loc)}, tokenList.getSourceFilePath(), severity, msg, id, Certainty::normal);
839  errorLogger.reportErr(errmsg);
840  }
841 
842  static bool isFunctionCall(const Token* tok)
843  {
844  if (!Token::simpleMatch(tok, "("))
845  return false;
846  if (tok->isCast())
847  return false;
848  if (!tok->isBinaryOp())
849  return false;
850  if (Token::simpleMatch(tok->link(), ") {"))
851  return false;
852  if (isUnevaluated(tok->previous()))
853  return false;
854  return Token::Match(tok->previous(), "%name%|)|]|>");
855  }
856 
857  static Token* assignExpr(Token* tok) {
858  while (tok->astParent() && astIsLHS(tok)) {
859  if (tok->astParent()->isAssignmentOp())
860  return tok->astParent();
861  tok = tok->astParent();
862  }
863  return nullptr;
864  }
865 
866  static Token* callExpr(Token* tok)
867  {
868  while (tok->astParent() && astIsLHS(tok)) {
869  if (!Token::Match(tok, "%name%|::|<|."))
870  break;
871  if (Token::simpleMatch(tok, "<") && !tok->link())
872  break;
873  tok = tok->astParent();
874  }
875  if (isFunctionCall(tok))
876  return tok;
877  return nullptr;
878  }
879 
880  static Token* skipTo(Token* tok, const Token* dest, const Token* end = nullptr) {
881  if (end && dest->index() > end->index())
882  return nullptr;
883  const int i = dest->index() - tok->index();
884  if (i > 0)
885  return tok->tokAt(dest->index() - tok->index());
886  return nullptr;
887  }
888 
889  static Token* getStepTokFromEnd(Token* tok) {
890  if (!Token::simpleMatch(tok, "}"))
891  return nullptr;
892  Token* end = tok->link()->previous();
893  if (!Token::simpleMatch(end, ")"))
894  return nullptr;
895  return getStepTok(end->link());
896  }
897  };
898 }
899 
900 Analyzer::Result valueFlowGenericForward(Token* start, const Token* end, const ValuePtr<Analyzer>& a, const TokenList& tokenList, ErrorLogger& errorLogger, const Settings& settings)
901 {
902  if (a->invalid())
904  ForwardTraversal ft{a, tokenList, errorLogger, settings};
905  if (start)
906  ft.analyzer->updateState(start);
907  ft.updateRange(start, end);
908  return Analyzer::Result{ ft.actions, ft.terminate };
909 }
910 
911 Analyzer::Result valueFlowGenericForward(Token* start, const ValuePtr<Analyzer>& a, const TokenList& tokenList, ErrorLogger& errorLogger, const Settings& settings)
912 {
913  if (Settings::terminated())
914  throw TerminateException();
915  if (a->invalid())
917  ForwardTraversal ft{a, tokenList, errorLogger, settings};
918  (void)ft.updateRecursive(start);
919  return Analyzer::Result{ ft.actions, ft.terminate };
920 }
bool precedes(const Token *tok1, const Token *tok2)
If tok2 comes after tok1.
Definition: astutils.cpp:994
const Token * findExpressionChanged(const Token *expr, const Token *start, const Token *end, const Settings &settings, int depth)
Definition: astutils.cpp:3028
bool astIsLHS(const Token *tok)
Definition: astutils.cpp:784
bool isEscapeFunction(const Token *ftok, const Library *library)
Definition: astutils.cpp:2155
static bool isFunctionCall(const Token *tok)
Definition: astutils.cpp:483
Token * getInitTok(Token *tok)
Definition: astutils.cpp:898
const Token * findNextTokenFromBreak(const Token *breakToken)
For a "break" token, locate the next token to execute.
Definition: astutils.cpp:912
Token * getCondTokFromEnd(Token *endBlock)
Definition: astutils.cpp:889
Token * getCondTok(Token *tok)
Definition: astutils.cpp:880
const Token * findLambdaEndToken(const Token *first)
find lambda function end token
Definition: astutils.cpp:3195
const Token * nextAfterAstRightmostLeaf(const Token *tok)
Definition: astutils.cpp:548
Token * getStepTok(Token *tok)
Definition: astutils.cpp:905
bool isReturnScope(const Token *const endToken, const Library &library, const Token **unknownFunc, bool functionScope)
Is scope a return scope (scope will unconditionally return)
Definition: astutils.cpp:2202
bool isUnevaluated(const Token *tok)
Definition: astutils.cpp:3612
bool isVariableChanged(const Token *tok, int indirect, const Settings &settings, int depth)
Definition: astutils.cpp:2546
const Token * findAstNode(const Token *ast, const TFunc &pred)
Definition: astutils.h:88
This is an interface, which the class responsible of error logging should implement.
Definition: errorlogger.h:214
virtual void reportErr(const ErrorMessage &msg)=0
Information about found errors and warnings is directed here.
File name and line number.
Definition: errorlogger.h:55
Wrapper for error messages, provided by reportErr()
Definition: errorlogger.h:48
ScopeType type
This is just a container for general settings so that we don't need to pass individual values to func...
Definition: settings.h:95
CheckLevel checkLevel
Definition: settings.h:465
static bool terminated()
termination requested?
Definition: settings.h:449
Library library
Library.
Definition: settings.h:237
const std::string & getSourceFilePath() const
Definition: tokenlist.cpp:75
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
nonneg int index() const
Definition: token.h:1247
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
static const Token * findmatch(const Token *const startTok, const char pattern[], const nonneg int varId=0)
Definition: token.cpp:1065
bool hasKnownIntValue() const
Definition: token.cpp:2519
bool isControlFlowKeyword() const
Definition: token.h:546
std::pair< const Token *, const Token * > findExpressionStartEndTokens() const
Definition: token.cpp:1514
bool isCast() const
Definition: token.h:458
static const Token * findsimplematch(const Token *const startTok, const char(&pattern)[count])
Definition: token.h:763
const Token * tokAt(int index) const
Definition: token.cpp:393
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
Token * previous()
Definition: token.h:862
bool isBinaryOp() const
Definition: token.h:410
void variable(const Variable *v)
Associate this token with given variable.
Definition: token.h:1070
Token * next()
Definition: token.h:830
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
#define REQUIRES(msg,...)
Definition: config.h:124
Analyzer::Result valueFlowGenericForward(Token *start, const Token *end, const ValuePtr< Analyzer > &a, const TokenList &tokenList, ErrorLogger &errorLogger, const Settings &settings)
Severity
enum class for severity.
Definition: errortypes.h:63
@ information
Checking information.
static const Token * assignExpr(const Token *tok)
bool isNone() const
Definition: analyzer.h:83
bool isInvalid() const
Definition: analyzer.h:75
bool isWrite() const
Definition: analyzer.h:71
bool isInconclusive() const
Definition: analyzer.h:79
bool isIdempotent() const
Definition: analyzer.h:91
bool isModified() const
Definition: analyzer.h:87
bool isIncremental() const
Definition: analyzer.h:95
bool isRead() const
Definition: analyzer.h:67
Terminate terminate
Definition: analyzer.h:140
Simple container to be thrown when internal error is detected.
Definition: errortypes.h:36
Definition: utils.h:53
bool contains(const Range &r, const T &x)
Definition: utils.h:62
static bool isEscapeScope(const Token *tok, const Settings &settings, bool unknown=false)
Definition: valueflow.cpp:386