Cppcheck
pathanalysis.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 "pathanalysis.h"
20 
21 #include "astutils.h"
22 #include "symboldatabase.h"
23 #include "token.h"
24 #include "vfvalue.h"
25 
26 #include <algorithm>
27 #include <string>
28 #include <tuple>
29 
31 {
32  if (!scope)
33  return nullptr;
34  if (scope->isLocal() && scope->type != Scope::eSwitch)
35  return findOuterScope(scope->nestedIn);
36  return scope;
37 }
38 
39 static const Token* assignExpr(const Token* tok)
40 {
41  while (tok->astParent() && astIsLHS(tok)) {
42  if (Token::Match(tok->astParent(), "%assign%"))
43  return tok->astParent();
44  tok = tok->astParent();
45  }
46  return nullptr;
47 }
48 
49 std::pair<bool, bool> PathAnalysis::checkCond(const Token * tok, bool& known)
50 {
51  if (tok->hasKnownIntValue()) {
52  known = true;
53  return std::make_pair(tok->values().front().intvalue, !tok->values().front().intvalue);
54  }
55  auto it = std::find_if(tok->values().cbegin(), tok->values().cend(), [](const ValueFlow::Value& v) {
56  return v.isIntValue();
57  });
58  // If all possible values are the same, then assume all paths have the same value
59  if (it != tok->values().cend() && std::all_of(it, tok->values().cend(), [&](const ValueFlow::Value& v) {
60  if (v.isIntValue())
61  return v.intvalue == it->intvalue;
62  return true;
63  })) {
64  known = false;
65  return std::make_pair(it->intvalue, !it->intvalue);
66  }
67  return std::make_pair(true, true);
68 }
69 
71 {
72  if (!tok)
73  return Progress::Continue;
74  if (tok->astOperand1() && forwardRecursive(tok->astOperand1(), info, f) == Progress::Break)
75  return Progress::Break;
76  info.tok = tok;
77  if (f(info) == Progress::Break)
78  return Progress::Break;
79  if (tok->astOperand2() && forwardRecursive(tok->astOperand2(), std::move(info), f) == Progress::Break)
80  return Progress::Break;
81  return Progress::Continue;
82 }
83 
84 PathAnalysis::Progress PathAnalysis::forwardRange(const Token* startToken, const Token* endToken, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const
85 {
86  for (const Token *tok = startToken; precedes(tok, endToken); tok = tok->next()) {
87  if (Token::Match(tok, "asm|goto|break|continue"))
88  return Progress::Break;
89  if (Token::Match(tok, "return|throw")) {
90  forwardRecursive(tok, std::move(info), f);
91  return Progress::Break;
92  // Evaluate RHS of assignment before LHS
93  }
94  if (const Token* assignTok = assignExpr(tok)) {
95  if (forwardRecursive(assignTok->astOperand2(), info, f) == Progress::Break)
96  return Progress::Break;
97  if (forwardRecursive(assignTok->astOperand1(), info, f) == Progress::Break)
98  return Progress::Break;
99  tok = nextAfterAstRightmostLeaf(assignTok);
100  if (!tok)
101  return Progress::Break;
102  } else if (Token::simpleMatch(tok, "}") && Token::simpleMatch(tok->link()->previous(), ") {") && Token::Match(tok->link()->linkAt(-1)->previous(), "if|while|for (")) {
103  const Token * blockStart = tok->link()->linkAt(-1)->previous();
104  const Token * condTok = getCondTok(blockStart);
105  if (!condTok)
106  continue;
107  info.errorPath.emplace_back(condTok, "Assuming condition is true.");
108  // Traverse a loop a second time
109  if (Token::Match(blockStart, "for|while (")) {
110  const Token* endCond = blockStart->linkAt(1);
111  bool traverseLoop = true;
112  // Only traverse simple for loops
113  if (Token::simpleMatch(blockStart, "for") && !Token::Match(endCond->tokAt(-3), "; ++|--|%var% %var%|++|-- ) {"))
114  traverseLoop = false;
115  // Traverse loop a second time
116  if (traverseLoop) {
117  // Traverse condition
118  if (forwardRecursive(condTok, info, f) == Progress::Break)
119  return Progress::Break;
120  // TODO: Should we traverse the body: forwardRange(tok->link(), tok, info, f)?
121  }
122  }
123  if (Token::simpleMatch(tok, "} else {")) {
124  tok = tok->linkAt(2);
125  }
126  } else if (Token::Match(tok, "if|while|for (") && Token::simpleMatch(tok->next()->link(), ") {")) {
127  const Token * endCond = tok->next()->link();
128  const Token * endBlock = endCond->next()->link();
129  const Token * condTok = getCondTok(tok);
130  if (!condTok)
131  continue;
132  // Traverse condition
133  if (forwardRange(tok->next(), tok->next()->link(), info, f) == Progress::Break)
134  return Progress::Break;
135  Info i = info;
136  i.known = false;
137  i.errorPath.emplace_back(condTok, "Assuming condition is true.");
138 
139  // Check if condition is true or false
140  bool checkThen = false;
141  bool checkElse = false;
142  std::tie(checkThen, checkElse) = checkCond(condTok, i.known);
143 
144  // Traverse then block
145  if (checkThen) {
146  if (forwardRange(endCond->next(), endBlock, i, f) == Progress::Break)
147  return Progress::Break;
148  }
149  // Traverse else block
150  if (Token::simpleMatch(endBlock, "} else {")) {
151  if (checkElse) {
152  i.errorPath.back().second = "Assuming condition is false.";
153  const Progress result = forwardRange(endCond->next(), endBlock, std::move(i), f);
154  if (result == Progress::Break)
155  return Progress::Break;
156  }
157  tok = endBlock->linkAt(2);
158  } else {
159  tok = endBlock;
160  }
161  } else if (Token::simpleMatch(tok, "} else {")) {
162  tok = tok->linkAt(2);
163  } else {
164  info.tok = tok;
165  if (f(info) == Progress::Break)
166  return Progress::Break;
167  }
168  // Prevent infinite recursion
169  if (tok->next() == start)
170  break;
171  }
172  return Progress::Continue;
173 }
174 
175 void PathAnalysis::forward(const std::function<Progress(const Info&)>& f) const
176 {
177  const Scope * endScope = findOuterScope(start->scope());
178  if (!endScope)
179  return;
180  const Token * endToken = endScope->bodyEnd;
181  Info info{start, ErrorPath{}, true};
182  forwardRange(start, endToken, std::move(info), f);
183 }
184 
185 bool reaches(const Token * start, const Token * dest, const Library& library, ErrorPath* errorPath)
186 {
187  PathAnalysis::Info info = PathAnalysis{start, library}.forwardFind([&](const PathAnalysis::Info& i) {
188  return (i.tok == dest);
189  });
190  if (!info.tok)
191  return false;
192  if (errorPath)
193  errorPath->insert(errorPath->end(), info.errorPath.cbegin(), info.errorPath.cend());
194  return true;
195 }
bool precedes(const Token *tok1, const Token *tok2)
If tok2 comes after tok1.
Definition: astutils.cpp:994
bool astIsLHS(const Token *tok)
Definition: astutils.cpp:784
Token * getCondTok(Token *tok)
Definition: astutils.cpp:880
const Token * nextAfterAstRightmostLeaf(const Token *tok)
Definition: astutils.cpp:548
Library definitions handling.
Definition: library.h:52
ScopeType type
const Scope * nestedIn
bool isLocal() const
const Token * bodyEnd
'}' token
The token list that the TokenList generates is a linked-list of this class.
Definition: token.h:150
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
bool hasKnownIntValue() const
Definition: token.cpp:2519
void astOperand1(Token *tok)
Definition: token.cpp:1456
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 * 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
std::list< ErrorPathItem > ErrorPath
Definition: errortypes.h:130
static const Token * assignExpr(const Token *tok)
bool reaches(const Token *start, const Token *dest, const Library &library, ErrorPath *errorPath)
Returns true if there is a path between the two tokens.
const Token * tok
Definition: pathanalysis.h:44
ErrorPath errorPath
Definition: pathanalysis.h:45
static Progress forwardRecursive(const Token *tok, Info info, const std::function< PathAnalysis::Progress(const Info &)> &f)
Progress forwardRange(const Token *startToken, const Token *endToken, Info info, const std::function< Progress(const Info &)> &f) const
const Token * start
Definition: pathanalysis.h:40
static const Scope * findOuterScope(const Scope *scope)
static std::pair< bool, bool > checkCond(const Token *tok, bool &known)
void forward(const std::function< Progress(const Info &)> &f) const