Cppcheck
checkstl.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 "checkstl.h"
20 
21 #include "astutils.h"
22 #include "errortypes.h"
23 #include "library.h"
24 #include "mathlib.h"
25 #include "pathanalysis.h"
26 #include "settings.h"
27 #include "standards.h"
28 #include "symboldatabase.h"
29 #include "token.h"
30 #include "tokenize.h"
31 #include "utils.h"
32 #include "valueflow.h"
33 
34 #include "checknullpointer.h"
35 
36 #include <algorithm>
37 #include <cassert>
38 #include <iterator>
39 #include <list>
40 #include <map>
41 #include <set>
42 #include <sstream>
43 #include <tuple>
44 #include <unordered_map>
45 #include <utility>
46 #include <vector>
47 
48 // Register this check class (by creating a static instance of it)
49 namespace {
50  CheckStl instance;
51 }
52 
53 // CWE IDs used:
54 static const CWE CWE398(398U); // Indicator of Poor Code Quality
55 static const CWE CWE597(597U); // Use of Wrong Operator in String Comparison
56 static const CWE CWE628(628U); // Function Call with Incorrectly Specified Arguments
57 static const CWE CWE664(664U); // Improper Control of a Resource Through its Lifetime
58 static const CWE CWE667(667U); // Improper Locking
59 static const CWE CWE704(704U); // Incorrect Type Conversion or Cast
60 static const CWE CWE762(762U); // Mismatched Memory Management Routines
61 static const CWE CWE786(786U); // Access of Memory Location Before Start of Buffer
62 static const CWE CWE788(788U); // Access of Memory Location After End of Buffer
63 static const CWE CWE825(825U); // Expired Pointer Dereference
64 static const CWE CWE833(833U); // Deadlock
65 static const CWE CWE834(834U); // Excessive Iteration
66 
68 {
70 }
71 
72 static bool containerAppendsElement(const Library::Container* container, const Token* parent)
73 {
74  if (Token::Match(parent, ". %name% (")) {
75  const Library::Container::Action action = container->getAction(parent->strAt(1));
81  action))
82  return true;
83  }
84  return false;
85 }
86 
87 static bool containerYieldsElement(const Library::Container* container, const Token* parent)
88 {
89  if (Token::Match(parent, ". %name% (")) {
90  const Library::Container::Yield yield = container->getYield(parent->strAt(1));
91  if (isElementAccessYield(yield))
92  return true;
93  }
94  return false;
95 }
96 
97 static bool containerPopsElement(const Library::Container* container, const Token* parent)
98 {
99  if (Token::Match(parent, ". %name% (")) {
100  const Library::Container::Action action = container->getAction(parent->strAt(1));
101  if (contains({ Library::Container::Action::POP }, action))
102  return true;
103  }
104  return false;
105 }
106 
107 static const Token* getContainerIndex(const Library::Container* container, const Token* parent)
108 {
109  if (Token::Match(parent, ". %name% (")) {
110  const Library::Container::Yield yield = container->getYield(parent->strAt(1));
111  if (yield == Library::Container::Yield::AT_INDEX && !Token::simpleMatch(parent->tokAt(2), "( )"))
112  return parent->tokAt(2)->astOperand2();
113  }
114  if (!container->arrayLike_indexOp && !container->stdStringLike)
115  return nullptr;
116  if (Token::simpleMatch(parent, "["))
117  return parent->astOperand2();
118  return nullptr;
119 }
120 
121 static const Token* getContainerFromSize(const Library::Container* container, const Token* tok)
122 {
123  if (!tok)
124  return nullptr;
125  if (Token::Match(tok->tokAt(-2), ". %name% (")) {
126  const Library::Container::Yield yield = container->getYield(tok->strAt(-1));
127  if (yield == Library::Container::Yield::SIZE)
128  return tok->tokAt(-2)->astOperand1();
129  }
130  return nullptr;
131 }
132 
134 {
135  logChecker("CheckStl::outOfBounds");
136 
137  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
138  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
139  const Library::Container *container = getLibraryContainer(tok);
140  if (!container || container->stdAssociativeLike)
141  continue;
142  const Token * parent = astParentSkipParens(tok);
143  const Token* accessTok = parent;
144  if (Token::simpleMatch(accessTok, ".") && Token::simpleMatch(accessTok->astParent(), "("))
145  accessTok = accessTok->astParent();
146  if (astIsIterator(accessTok) && Token::simpleMatch(accessTok->astParent(), "+"))
147  accessTok = accessTok->astParent();
148  const Token* indexTok = getContainerIndex(container, parent);
149  if (indexTok == tok)
150  continue;
151  for (const ValueFlow::Value &value : tok->values()) {
152  if (!value.isContainerSizeValue())
153  continue;
154  if (value.isImpossible())
155  continue;
156  if (value.isInconclusive() && !mSettings->certainty.isEnabled(Certainty::inconclusive))
157  continue;
158  if (!value.errorSeverity() && !mSettings->severity.isEnabled(Severity::warning))
159  continue;
160  if (value.intvalue == 0 && (indexTok ||
161  (containerYieldsElement(container, parent) && !containerAppendsElement(container, parent)) ||
162  containerPopsElement(container, parent))) {
163  std::string indexExpr;
164  if (indexTok && !indexTok->hasKnownValue())
165  indexExpr = indexTok->expressionString();
166  outOfBoundsError(accessTok, tok->expressionString(), &value, indexExpr, nullptr);
167  continue;
168  }
169  if (indexTok) {
170  std::vector<ValueFlow::Value> indexValues =
172  if (!indexValues.empty()) {
174  accessTok, tok->expressionString(), &value, indexTok->expressionString(), &indexValues.front());
175  continue;
176  }
177  }
178  }
179  if (indexTok && !indexTok->hasKnownIntValue()) {
180  const ValueFlow::Value* value =
181  ValueFlow::findValue(indexTok->values(), *mSettings, [&](const ValueFlow::Value& v) {
182  if (!v.isSymbolicValue())
183  return false;
184  if (v.isImpossible())
185  return false;
186  if (v.intvalue < 0)
187  return false;
188  const Token* sizeTok = v.tokvalue;
189  if (sizeTok && sizeTok->isCast())
190  sizeTok = sizeTok->astOperand2() ? sizeTok->astOperand2() : sizeTok->astOperand1();
191  const Token* containerTok = getContainerFromSize(container, sizeTok);
192  if (!containerTok)
193  return false;
194  return containerTok->exprId() == tok->exprId();
195  });
196  if (!value)
197  continue;
198  outOfBoundsError(accessTok, tok->expressionString(), nullptr, indexTok->expressionString(), value);
199  }
200  }
201  }
202 }
203 
204 static std::string indexValueString(const ValueFlow::Value& indexValue, const std::string& containerName = emptyString)
205 {
206  if (indexValue.isIteratorStartValue())
207  return "at position " + std::to_string(indexValue.intvalue) + " from the beginning";
208  if (indexValue.isIteratorEndValue())
209  return "at position " + std::to_string(-indexValue.intvalue) + " from the end";
210  std::string indexString = std::to_string(indexValue.intvalue);
211  if (indexValue.isSymbolicValue()) {
212  indexString = containerName + ".size()";
213  if (indexValue.intvalue != 0)
214  indexString += "+" + std::to_string(indexValue.intvalue);
215  }
216  if (indexValue.bound == ValueFlow::Value::Bound::Lower)
217  return "greater or equal to " + indexString;
218  return indexString;
219 }
220 
221 void CheckStl::outOfBoundsError(const Token *tok, const std::string &containerName, const ValueFlow::Value *containerSize, const std::string &index, const ValueFlow::Value *indexValue)
222 {
223  // Do not warn if both the container size and index value are possible
224  if (containerSize && indexValue && containerSize->isPossible() && indexValue->isPossible())
225  return;
226 
227  const std::string expression = tok ? tok->expressionString() : (containerName+"[x]");
228 
229  std::string errmsg;
230  if (!containerSize) {
231  if (indexValue && indexValue->condition)
232  errmsg = ValueFlow::eitherTheConditionIsRedundant(indexValue->condition) + " or '" + index +
233  "' can have the value " + indexValueString(*indexValue, containerName) + ". Expression '" +
234  expression + "' causes access out of bounds.";
235  else
236  errmsg = "Out of bounds access in expression '" + expression + "'";
237  } else if (containerSize->intvalue == 0) {
238  if (containerSize->condition)
239  errmsg = ValueFlow::eitherTheConditionIsRedundant(containerSize->condition) + " or expression '" + expression + "' causes access out of bounds.";
240  else if (indexValue == nullptr && !index.empty() && tok->valueType() && tok->valueType()->type == ValueType::ITERATOR)
241  errmsg = "Out of bounds access in expression '" + expression + "' because '$symbol' is empty and '" + index + "' may be non-zero.";
242  else
243  errmsg = "Out of bounds access in expression '" + expression + "' because '$symbol' is empty.";
244  } else if (indexValue) {
245  if (containerSize->condition)
246  errmsg = ValueFlow::eitherTheConditionIsRedundant(containerSize->condition) + " or size of '$symbol' can be " + std::to_string(containerSize->intvalue) + ". Expression '" + expression + "' causes access out of bounds.";
247  else if (indexValue->condition)
248  errmsg = ValueFlow::eitherTheConditionIsRedundant(indexValue->condition) + " or '" + index + "' can have the value " + indexValueString(*indexValue) + ". Expression '" + expression + "' causes access out of bounds.";
249  else
250  errmsg = "Out of bounds access in '" + expression + "', if '$symbol' size is " + std::to_string(containerSize->intvalue) + " and '" + index + "' is " + indexValueString(*indexValue);
251  } else {
252  // should not happen
253  return;
254  }
255 
256  ErrorPath errorPath;
257  if (!indexValue)
258  errorPath = getErrorPath(tok, containerSize, "Access out of bounds");
259  else {
260  ErrorPath errorPath1 = getErrorPath(tok, containerSize, "Access out of bounds");
261  ErrorPath errorPath2 = getErrorPath(tok, indexValue, "Access out of bounds");
262  if (errorPath1.size() <= 1)
263  errorPath = std::move(errorPath2);
264  else if (errorPath2.size() <= 1)
265  errorPath = std::move(errorPath1);
266  else {
267  errorPath = std::move(errorPath1);
268  errorPath.splice(errorPath.end(), errorPath2);
269  }
270  }
271 
272  reportError(errorPath,
273  (containerSize && !containerSize->errorSeverity()) || (indexValue && !indexValue->errorSeverity()) ? Severity::warning : Severity::error,
274  "containerOutOfBounds",
275  "$symbol:" + containerName +"\n" + errmsg,
276  CWE398,
277  (containerSize && containerSize->isInconclusive()) || (indexValue && indexValue->isInconclusive()) ? Certainty::inconclusive : Certainty::normal);
278 }
279 
280 bool CheckStl::isContainerSize(const Token *containerToken, const Token *expr) const
281 {
282  if (!Token::simpleMatch(expr, "( )"))
283  return false;
284  if (!Token::Match(expr->astOperand1(), ". %name% ("))
285  return false;
286  if (!isSameExpression(false, containerToken, expr->astOperand1()->astOperand1(), *mSettings, false, false))
287  return false;
288  return containerToken->valueType()->container->getYield(expr->previous()->str()) == Library::Container::Yield::SIZE;
289 }
290 
291 bool CheckStl::isContainerSizeGE(const Token * containerToken, const Token *expr) const
292 {
293  if (!expr)
294  return false;
295  if (isContainerSize(containerToken, expr))
296  return true;
297  if (expr->str() == "*") {
298  const Token *mul;
299  if (isContainerSize(containerToken, expr->astOperand1()))
300  mul = expr->astOperand2();
301  else if (isContainerSize(containerToken, expr->astOperand2()))
302  mul = expr->astOperand1();
303  else
304  return false;
305  return mul && (!mul->hasKnownIntValue() || mul->values().front().intvalue != 0);
306  }
307  if (expr->str() == "+") {
308  const Token *op;
309  if (isContainerSize(containerToken, expr->astOperand1()))
310  op = expr->astOperand2();
311  else if (isContainerSize(containerToken, expr->astOperand2()))
312  op = expr->astOperand1();
313  else
314  return false;
315  return op && op->getValueGE(0, *mSettings);
316  }
317  return false;
318 }
319 
321 {
322  logChecker("CheckStl::outOfBoundsIndexExpression");
323  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
324  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
325  if (!tok->isName() || !tok->valueType())
326  continue;
327  const Library::Container *container = tok->valueType()->container;
328  if (!container)
329  continue;
330  if (!container->arrayLike_indexOp && !container->stdStringLike)
331  continue;
332  if (!Token::Match(tok, "%name% ["))
333  continue;
334  if (isContainerSizeGE(tok, tok->next()->astOperand2()))
335  outOfBoundsIndexExpressionError(tok, tok->next()->astOperand2());
336  }
337  }
338 }
339 
341 {
342  const std::string varname = tok ? tok->str() : std::string("var");
343  const std::string i = index ? index->expressionString() : std::string(varname + ".size()");
344 
345  std::string errmsg = "Out of bounds access of $symbol, index '" + i + "' is out of bounds.";
346 
347  reportError(tok,
349  "containerOutOfBoundsIndexExpression",
350  "$symbol:" + varname +"\n" + errmsg,
351  CWE398,
353 }
354 
355 
356 
357 // Error message for bad iterator usage..
358 void CheckStl::invalidIteratorError(const Token *tok, const std::string &iteratorName)
359 {
360  reportError(tok, Severity::error, "invalidIterator1", "$symbol:"+iteratorName+"\nInvalid iterator: $symbol", CWE664, Certainty::normal);
361 }
362 
363 void CheckStl::iteratorsError(const Token* tok, const std::string& containerName1, const std::string& containerName2)
364 {
365  reportError(tok, Severity::error, "iterators1",
366  "$symbol:" + containerName1 + "\n"
367  "$symbol:" + containerName2 + "\n"
368  "Same iterator is used with different containers '" + containerName1 + "' and '" + containerName2 + "'.", CWE664, Certainty::normal);
369 }
370 
371 void CheckStl::iteratorsError(const Token* tok, const Token* containerTok, const std::string& containerName1, const std::string& containerName2)
372 {
373  std::list<const Token*> callstack = { tok, containerTok };
374  reportError(callstack, Severity::error, "iterators2",
375  "$symbol:" + containerName1 + "\n"
376  "$symbol:" + containerName2 + "\n"
377  "Same iterator is used with different containers '" + containerName1 + "' and '" + containerName2 + "'.", CWE664, Certainty::normal);
378 }
379 
380 void CheckStl::iteratorsError(const Token* tok, const Token* containerTok, const std::string& containerName)
381 {
382  std::list<const Token*> callstack = { tok, containerTok };
383  reportError(callstack,
385  "iterators3",
386  "$symbol:" + containerName +
387  "\n"
388  "Same iterator is used with containers '$symbol' that are temporaries or defined in different scopes.",
389  CWE664,
391 }
392 
393 // Error message used when dereferencing an iterator that has been erased..
394 void CheckStl::dereferenceErasedError(const Token *erased, const Token* deref, const std::string &itername, bool inconclusive)
395 {
396  if (erased) {
397  std::list<const Token*> callstack = { deref, erased };
398  reportError(callstack, Severity::error, "eraseDereference",
399  "$symbol:" + itername + "\n"
400  "Iterator '$symbol' used after element has been erased.\n"
401  "The iterator '$symbol' is invalid after the element it pointed to has been erased. "
402  "Dereferencing or comparing it with another iterator is invalid operation.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);
403  } else {
404  reportError(deref, Severity::error, "eraseDereference",
405  "$symbol:" + itername + "\n"
406  "Invalid iterator '$symbol' used.\n"
407  "The iterator '$symbol' is invalid before being assigned. "
408  "Dereferencing or comparing it with another iterator is invalid operation.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);
409  }
410 }
411 
412 static const Token *skipMembers(const Token *tok)
413 {
414  while (Token::Match(tok, "%name% ."))
415  tok = tok->tokAt(2);
416  return tok;
417 }
418 
419 static bool isIterator(const Variable *var, bool& inconclusiveType)
420 {
421  // Check that its an iterator
422  if (!var || !var->isLocal() || !Token::Match(var->typeEndToken(), "iterator|const_iterator|reverse_iterator|const_reverse_iterator|auto"))
423  return false;
424 
425  inconclusiveType = false;
426  if (var->typeEndToken()->str() == "auto")
427  return (var->nameToken()->valueType() && var->nameToken()->valueType()->type == ValueType::Type::ITERATOR);
428 
429  if (var->type()) { // If it is defined, ensure that it is defined like an iterator
430  // look for operator* and operator++
431  const Function* end = var->type()->getFunction("operator*");
432  const Function* incOperator = var->type()->getFunction("operator++");
433  if (!end || end->argCount() > 0 || !incOperator)
434  return false;
435 
436  inconclusiveType = true; // heuristics only
437  }
438 
439  return true;
440 }
441 
442 static std::string getContainerName(const Token *containerToken)
443 {
444  if (!containerToken)
445  return std::string();
446  std::string ret(containerToken->str());
447  for (const Token *nametok = containerToken; nametok; nametok = nametok->tokAt(-2)) {
448  if (!Token::Match(nametok->tokAt(-2), "%name% ."))
449  break;
450  ret = nametok->strAt(-2) + '.' + ret;
451  }
452  return ret;
453 }
454 
455 static bool isVector(const Token* tok)
456 {
457  if (!tok)
458  return false;
459  const Variable *var = tok->variable();
460  const Token *decltok = var ? var->typeStartToken() : nullptr;
461  return Token::simpleMatch(decltok, "std :: vector");
462 }
463 
465 {
466  logChecker("CheckStl::iterators");
467 
468  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
469 
470  // Filling map of iterators id and their scope begin
471  std::map<int, const Token*> iteratorScopeBeginInfo;
472  for (const Variable* var : symbolDatabase->variableList()) {
473  bool inconclusiveType=false;
474  if (!isIterator(var, inconclusiveType))
475  continue;
476  const int iteratorId = var->declarationId();
477  if (iteratorId != 0)
478  iteratorScopeBeginInfo[iteratorId] = var->nameToken();
479  }
480 
481  for (const Variable* var : symbolDatabase->variableList()) {
482  bool inconclusiveType=false;
483  if (!isIterator(var, inconclusiveType))
484  continue;
485  if (inconclusiveType && !mSettings->certainty.isEnabled(Certainty::inconclusive))
486  continue;
487 
488  const int iteratorId = var->declarationId();
489 
490  // the validIterator flag says if the iterator has a valid value or not
491  bool validIterator = Token::Match(var->nameToken()->next(), "[(=:{]");
492  const Scope* invalidationScope = nullptr;
493 
494  // The container this iterator can be used with
495  const Token* containerToken = nullptr;
496  const Scope* containerAssignScope = nullptr;
497 
498  // When "validatingToken" is reached the validIterator is set to true
499  const Token* validatingToken = nullptr;
500 
501  const Token* eraseToken = nullptr;
502 
503  // Scan through the rest of the code and see if the iterator is
504  // used against other containers.
505  for (const Token *tok2 = var->nameToken(); tok2 && tok2 != var->scope()->bodyEnd; tok2 = tok2->next()) {
506  if (invalidationScope && tok2 == invalidationScope->bodyEnd)
507  validIterator = true; // Assume that the iterator becomes valid again
508  if (containerAssignScope && tok2 == containerAssignScope->bodyEnd)
509  containerToken = nullptr; // We don't know which containers might be used with the iterator
510 
511  if (tok2 == validatingToken) {
512  validIterator = true;
513  eraseToken = nullptr;
514  invalidationScope = nullptr;
515  }
516 
517  // Is the iterator used in a insert/erase operation?
518  if (Token::Match(tok2, "%name% . insert|erase ( *| %varid% )|,", iteratorId) && !isVector(tok2)) {
519  const Token* itTok = tok2->tokAt(4);
520  if (itTok->str() == "*") {
521  if (tok2->strAt(2) == "insert")
522  continue;
523 
524  itTok = itTok->next();
525  }
526  // It is bad to insert/erase an invalid iterator
527  if (!validIterator)
528  invalidIteratorError(tok2, itTok->str());
529 
530  // If insert/erase is used on different container then
531  // report an error
532  if (containerToken && tok2->varId() != containerToken->varId()) {
533  // skip error message if container is a set..
534  const Variable *variableInfo = tok2->variable();
535  const Token *decltok = variableInfo ? variableInfo->typeStartToken() : nullptr;
536 
537  if (Token::simpleMatch(decltok, "std :: set"))
538  continue; // No warning
539 
540  // skip error message if the iterator is erased/inserted by value
541  if (itTok->previous()->str() == "*")
542  continue;
543 
544  // inserting iterator range..
545  if (tok2->strAt(2) == "insert") {
546  const Token *par2 = itTok->nextArgument();
547  if (!par2 || par2->nextArgument())
548  continue;
549  while (par2->str() != ")") {
550  if (par2->varId() == containerToken->varId())
551  break;
552  bool inconclusiveType2=false;
553  if (isIterator(par2->variable(), inconclusiveType2))
554  break; // TODO: check if iterator points at same container
555  if (par2->str() == "(")
556  par2 = par2->link();
557  par2 = par2->next();
558  }
559  if (par2->str() != ")")
560  continue;
561  }
562 
563  // Not different containers if a reference is used..
564  if (containerToken && containerToken->variable() && containerToken->variable()->isReference()) {
565  const Token *nameToken = containerToken->variable()->nameToken();
566  if (Token::Match(nameToken, "%name% =")) {
567  const Token *name1 = nameToken->tokAt(2);
568  const Token *name2 = tok2;
569  while (Token::Match(name1, "%name%|.|::") && name2 && name1->str() == name2->str()) {
570  name1 = name1->next();
571  name2 = name2->next();
572  }
573  if (!Token::simpleMatch(name1, ";") || !Token::Match(name2, "[;,()=]"))
574  continue;
575  }
576  }
577 
578  // Show error message, mismatching iterator is used.
579  iteratorsError(tok2, getContainerName(containerToken), getContainerName(tok2));
580  }
581 
582  // invalidate the iterator if it is erased
583  else if (tok2->strAt(2) == "erase" && (tok2->strAt(4) != "*" || (containerToken && tok2->varId() == containerToken->varId()))) {
584  validIterator = false;
585  eraseToken = tok2;
586  invalidationScope = tok2->scope();
587  }
588 
589  // skip the operation
590  tok2 = itTok->next();
591  }
592 
593  // it = foo.erase(..
594  // taking the result of an erase is ok
595  else if (Token::Match(tok2, "%varid% = %name% .", iteratorId) &&
596  Token::simpleMatch(skipMembers(tok2->tokAt(2)), "erase (")) {
597  // the returned iterator is valid
598  validatingToken = skipMembers(tok2->tokAt(2))->linkAt(1);
599  tok2 = validatingToken->link();
600  }
601 
602  // Reassign the iterator
603  else if (Token::Match(tok2, "%varid% = %name% .", iteratorId) &&
604  Token::Match(skipMembers(tok2->tokAt(2)), "begin|rbegin|cbegin|crbegin|find (")) {
605  validatingToken = skipMembers(tok2->tokAt(2))->linkAt(1);
606  containerToken = skipMembers(tok2->tokAt(2))->tokAt(-2);
607  if (containerToken->varId() == 0 || Token::simpleMatch(validatingToken, ") ."))
608  containerToken = nullptr;
609  containerAssignScope = tok2->scope();
610 
611  // skip ahead
612  tok2 = validatingToken->link();
613  }
614 
615  // Reassign the iterator
616  else if (Token::Match(tok2, "%varid% =", iteratorId)) {
617  break;
618  }
619 
620  // Passing iterator to function. Iterator might be initialized
621  else if (Token::Match(tok2, "%varid% ,|)", iteratorId)) {
622  validIterator = true;
623  }
624 
625  // Dereferencing invalid iterator?
626  else if (!validIterator && Token::Match(tok2, "* %varid%", iteratorId)) {
627  dereferenceErasedError(eraseToken, tok2, tok2->strAt(1), inconclusiveType);
628  tok2 = tok2->next();
629  } else if (!validIterator && Token::Match(tok2, "%varid% . %name%", iteratorId)) {
630  dereferenceErasedError(eraseToken, tok2, tok2->str(), inconclusiveType);
631  tok2 = tok2->tokAt(2);
632  }
633 
634  // bailout handling. Assume that the iterator becomes valid if we see return/break.
635  // TODO: better handling
636  else if (tok2->scope() == invalidationScope && Token::Match(tok2, "return|break|continue")) {
637  validatingToken = Token::findsimplematch(tok2->next(), ";");
638  }
639 
640  // bailout handling. Assume that the iterator becomes valid if we see else.
641  // TODO: better handling
642  else if (tok2->str() == "else") {
643  validIterator = true;
644  }
645  }
646  }
647 }
648 
649 void CheckStl::mismatchingContainerIteratorError(const Token* containerTok, const Token* iterTok, const Token* containerTok2)
650 {
651  const std::string container(containerTok ? containerTok->expressionString() : std::string("v1"));
652  const std::string container2(containerTok2 ? containerTok2->expressionString() : std::string("v2"));
653  const std::string iter(iterTok ? iterTok->expressionString() : std::string("it"));
654  reportError(containerTok,
656  "mismatchingContainerIterator",
657  "Iterator '" + iter + "' referring to container '" + container2 + "' is used with container '" + container + "'.",
658  CWE664,
660 }
661 
662 // Error message for bad iterator usage..
663 void CheckStl::mismatchingContainersError(const Token* tok1, const Token* tok2)
664 {
665  const std::string expr1(tok1 ? tok1->expressionString() : std::string("v1"));
666  const std::string expr2(tok2 ? tok2->expressionString() : std::string("v2"));
667  reportError(tok1,
669  "mismatchingContainers",
670  "Iterators of different containers '" + expr1 + "' and '" + expr2 + "' are used together.",
671  CWE664,
673 }
674 
676 {
677  const std::string expr1(tok1 ? tok1->expressionString() : std::string("v1"));
678  const std::string expr2(tok2 ? tok2->expressionString() : std::string("v2"));
679  reportError(tok1, Severity::warning, "mismatchingContainerExpression",
680  "Iterators to containers from different expressions '" +
681  expr1 + "' and '" + expr2 + "' are used together.", CWE664, Certainty::normal);
682 }
683 
685 {
686  reportError(tok, Severity::style, "sameIteratorExpression", "Same iterators expression are used for algorithm.", CWE664, Certainty::normal);
687 }
688 
689 static std::vector<const Token*> getAddressContainer(const Token* tok)
690 {
691  if (Token::simpleMatch(tok, "[") && tok->astOperand1())
692  return { tok->astOperand1() };
693  while (Token::simpleMatch(tok, "::") && tok->astOperand2())
694  tok = tok->astOperand2();
695  std::vector<ValueFlow::Value> values = ValueFlow::getLifetimeObjValues(tok, /*inconclusive*/ false);
696  std::vector<const Token*> res;
697  for (const auto& v : values) {
698  if (v.tokvalue)
699  res.emplace_back(v.tokvalue);
700  }
701  if (res.empty())
702  res.emplace_back(tok);
703  return res;
704 }
705 
706 static bool isSameIteratorContainerExpression(const Token* tok1,
707  const Token* tok2,
708  const Settings& settings,
710 {
711  if (isSameExpression(false, tok1, tok2, settings, false, false)) {
712  return !astIsContainerOwned(tok1) || !isTemporary(tok1, &settings.library);
713  }
715  return true;
717  const auto address1 = getAddressContainer(tok1);
718  const auto address2 = getAddressContainer(tok2);
719  return std::any_of(address1.begin(), address1.end(), [&](const Token* tok1) {
720  return std::any_of(address2.begin(), address2.end(), [&](const Token* tok2) {
721  return isSameExpression(false, tok1, tok2, settings, false, false);
722  });
723  });
724  }
725  return false;
726 }
727 
729 {
730  auto findIterVal = [](const std::vector<ValueFlow::Value>& values, const std::vector<ValueFlow::Value>::const_iterator beg) {
731  return std::find_if(beg, values.cend(), [](const ValueFlow::Value& v) {
732  return v.lifetimeKind == ValueFlow::Value::LifetimeKind::Iterator;
733  });
734  };
735  std::vector<ValueFlow::Value> values = ValueFlow::getLifetimeObjValues(tok, false, path);
736  auto it = findIterVal(values, values.begin());
737  if (it != values.end()) {
738  auto it2 = findIterVal(values, it + 1);
739  if (it2 == values.cend())
740  return *it;
741  }
742  if (values.size() == 1)
743  return values.front();
744  return ValueFlow::Value{};
745 }
746 
747 bool CheckStl::checkIteratorPair(const Token* tok1, const Token* tok2)
748 {
749  if (!tok1)
750  return false;
751  if (!tok2)
752  return false;
755  if (val1.tokvalue && val2.tokvalue && val1.lifetimeKind == val2.lifetimeKind) {
757  return false;
758  if (tok1->astParent() == tok2->astParent() && Token::Match(tok1->astParent(), "%comp%|-")) {
760  return false;
762  (!astIsContainer(val1.tokvalue) || !astIsContainer(val2.tokvalue)))
763  return false;
764  }
766  return false;
767  if (val1.tokvalue->expressionString() == val2.tokvalue->expressionString())
768  iteratorsError(tok1, val1.tokvalue, val1.tokvalue->expressionString());
769  else
771  return true;
772  }
773 
774  if (Token::Match(tok1->astParent(), "%comp%|-")) {
775  if (astIsIntegral(tok1, true) || astIsIntegral(tok2, true) ||
776  astIsFloat(tok1, true) || astIsFloat(tok2, true))
777  return false;
778  }
779  const Token* iter1 = getIteratorExpression(tok1);
780  const Token* iter2 = getIteratorExpression(tok2);
781  if (iter1 && iter2 && !isSameIteratorContainerExpression(iter1, iter2, *mSettings)) {
783  return true;
784  }
785  return false;
786 }
787 
788 namespace {
789  struct ArgIteratorInfo {
790  const Token* tok;
792  };
793 }
794 
796 {
797  logChecker("CheckStl::misMatchingContainers");
798 
799  // Check if different containers are used in various calls of standard functions
800  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
801  for (const Scope * scope : symbolDatabase->functionScopes) {
802  for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
803  if (Token::Match(tok, "%comp%|-")) {
804  if (checkIteratorPair(tok->astOperand1(), tok->astOperand2()))
805  continue;
806  }
807  if (!Token::Match(tok, "%name% ( !!)"))
808  continue;
809  const Token * const ftok = tok;
810 
811  const std::vector<const Token *> args = getArguments(ftok);
812  if (args.size() < 2)
813  continue;
814 
815  // Group args together by container
816  std::map<int, std::vector<ArgIteratorInfo>> containers;
817  for (int argnr = 1; argnr <= args.size(); ++argnr) {
819  if (!i)
820  continue;
821  const Token * const argTok = args[argnr - 1];
822  containers[i->container].emplace_back(ArgIteratorInfo{argTok, i});
823  }
824 
825  // Lambda is used to escape the nested loops
826  [&] {
827  for (const auto& p : containers)
828  {
829  const std::vector<ArgIteratorInfo>& cargs = p.second;
830  for (ArgIteratorInfo iter1 : cargs) {
831  for (ArgIteratorInfo iter2 : cargs) {
832  if (iter1.tok == iter2.tok)
833  continue;
834  if (iter1.info->first && iter2.info->last &&
835  isSameExpression(false, iter1.tok, iter2.tok, *mSettings, false, false))
836  sameIteratorExpressionError(iter1.tok);
837  if (checkIteratorPair(iter1.tok, iter2.tok))
838  return;
839  }
840  }
841  }
842  }();
843  }
844  }
845  for (const Variable *var : symbolDatabase->variableList()) {
846  if (var && var->isStlStringType() && Token::Match(var->nameToken(), "%var% (") &&
847  Token::Match(var->nameToken()->tokAt(2), "%name% . begin|cbegin|rbegin|crbegin ( ) , %name% . end|cend|rend|crend ( ) ,|)")) {
848  if (var->nameToken()->strAt(2) != var->nameToken()->strAt(8)) {
849  mismatchingContainersError(var->nameToken(), var->nameToken()->tokAt(2));
850  }
851  }
852  }
853 }
854 
856 {
857  logChecker("CheckStl::misMatchingContainerIterator");
858 
859  // Check if different containers are used in various calls of standard functions
860  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
861  for (const Scope * scope : symbolDatabase->functionScopes) {
862  for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
863  if (!astIsContainer(tok))
864  continue;
865  if (!astIsLHS(tok))
866  continue;
867  if (!Token::Match(tok->astParent(), ". %name% ( !!)"))
868  continue;
869  const Token* const ftok = tok->astParent()->next();
870  const std::vector<const Token *> args = getArguments(ftok);
871 
872  const Library::Container * c = tok->valueType()->container;
873  const Library::Container::Action action = c->getAction(tok->strAt(2));
874  const Token* iterTok = nullptr;
875  if (action == Library::Container::Action::INSERT && args.size() == 2) {
876  // Skip if iterator pair
877  if (astIsIterator(args.back()))
878  continue;
879  if (!astIsIterator(args.front()))
880  continue;
881  iterTok = args.front();
882  } else if (action == Library::Container::Action::ERASE) {
883  if (!astIsIterator(args.front()))
884  continue;
885  iterTok = args.front();
886  } else {
887  continue;
888  }
889 
891  if (!val.tokvalue)
892  continue;
893  if (!val.isKnown() && Token::simpleMatch(val.tokvalue->astParent(), ":"))
894  continue;
896  continue;
897  if (iterTok->str() == "*" && iterTok->astOperand1()->valueType() && iterTok->astOperand1()->valueType()->type == ValueType::ITERATOR)
898  continue;
900  continue;
901  mismatchingContainerIteratorError(tok, iterTok, val.tokvalue);
902  }
903  }
904 }
905 
906 static const Token* getInvalidMethod(const Token* tok)
907 {
908  if (!astIsLHS(tok))
909  return nullptr;
910  if (Token::Match(tok->astParent(), ". assign|clear|swap"))
911  return tok->astParent()->next();
912  if (Token::Match(tok->astParent(), "%assign%"))
913  return tok->astParent();
914  const Token* ftok = nullptr;
915  if (Token::Match(tok->astParent(), ". %name% ("))
916  ftok = tok->astParent()->next();
917  if (!ftok)
918  return nullptr;
919  if (const Library::Container * c = tok->valueType()->container) {
920  const Library::Container::Action action = c->getAction(ftok->str());
921  if (c->unstableErase) {
922  if (action == Library::Container::Action::ERASE)
923  return ftok;
924  }
925  if (c->unstableInsert) {
927  return ftok;
928  if (action == Library::Container::Action::CLEAR)
929  return ftok;
930  if (action == Library::Container::Action::PUSH)
931  return ftok;
932  if (action == Library::Container::Action::POP)
933  return ftok;
935  return ftok;
937  return ftok;
939  return ftok;
940  if (Token::Match(ftok, "insert|emplace"))
941  return ftok;
942  }
943  }
944  return nullptr;
945 }
946 
947 namespace {
948  struct InvalidContainerAnalyzer {
949  struct Info {
950  struct Reference {
951  const Token* tok;
952  ErrorPath errorPath;
953  const Token* ftok;
954  };
955  std::unordered_map<int, Reference> expressions;
956 
957  void add(const std::vector<Reference>& refs) {
958  for (const Reference& r : refs) {
959  add(r);
960  }
961  }
962  void add(const Reference& r) {
963  if (!r.tok)
964  return;
965  expressions.insert(std::make_pair(r.tok->exprId(), r));
966  }
967 
968  std::vector<Reference> invalidTokens() const {
969  std::vector<Reference> result;
970  std::transform(expressions.cbegin(), expressions.cend(), std::back_inserter(result), SelectMapValues{});
971  return result;
972  }
973  };
974  std::unordered_map<const Function*, Info> invalidMethods;
975 
976  std::vector<Info::Reference> invalidatesContainer(const Token* tok) const {
977  std::vector<Info::Reference> result;
978  if (Token::Match(tok, "%name% (")) {
979  const Function* f = tok->function();
980  if (!f)
981  return result;
982  ErrorPathItem epi = std::make_pair(tok, "Calling function " + tok->str());
983  const bool dependsOnThis = exprDependsOnThis(tok->next());
984  auto it = invalidMethods.find(f);
985  if (it != invalidMethods.end()) {
986  std::vector<Info::Reference> refs = it->second.invalidTokens();
987  std::copy_if(refs.cbegin(), refs.cend(), std::back_inserter(result), [&](const Info::Reference& r) {
988  const Variable* var = r.tok->variable();
989  if (!var)
990  return false;
991  if (dependsOnThis && !var->isLocal() && !var->isGlobal() && !var->isStatic())
992  return true;
993  if (!var->isArgument())
994  return false;
995  if (!var->isReference())
996  return false;
997  return true;
998  });
999  std::vector<const Token*> args = getArguments(tok);
1000  for (Info::Reference& r : result) {
1001  r.errorPath.push_front(epi);
1002  r.ftok = tok;
1003  const Variable* var = r.tok->variable();
1004  if (!var)
1005  continue;
1006  if (var->isArgument()) {
1007  const int n = getArgumentPos(var, f);
1008  const Token* tok2 = nullptr;
1009  if (n >= 0 && n < args.size())
1010  tok2 = args[n];
1011  r.tok = tok2;
1012  }
1013  }
1014  }
1015  } else if (astIsContainer(tok)) {
1016  const Token* ftok = getInvalidMethod(tok);
1017  if (ftok) {
1018  ErrorPath ep;
1019  ep.emplace_front(ftok,
1020  "After calling '" + ftok->expressionString() +
1021  "', iterators or references to the container's data may be invalid .");
1022  result.emplace_back(Info::Reference{tok, std::move(ep), ftok});
1023  }
1024  }
1025  return result;
1026  }
1027 
1028  void analyze(const SymbolDatabase* symboldatabase) {
1029  for (const Scope* scope : symboldatabase->functionScopes) {
1030  const Function* f = scope->function;
1031  if (!f)
1032  continue;
1033  for (const Token* tok = scope->bodyStart; tok != scope->bodyEnd; tok = tok->next()) {
1034  if (Token::Match(tok, "if|while|for|goto|return"))
1035  break;
1036  std::vector<Info::Reference> c = invalidatesContainer(tok);
1037  if (c.empty())
1038  continue;
1039  invalidMethods[f].add(c);
1040  }
1041  }
1042  }
1043  };
1044 }
1045 
1046 static const Token* getLoopContainer(const Token* tok)
1047 {
1048  if (!Token::simpleMatch(tok, "for ("))
1049  return nullptr;
1050  const Token* sepTok = tok->next()->astOperand2();
1051  if (!Token::simpleMatch(sepTok, ":"))
1052  return nullptr;
1053  return sepTok->astOperand2();
1054 }
1055 
1056 static const ValueFlow::Value* getInnerLifetime(const Token* tok,
1057  nonneg int id,
1058  ErrorPath* errorPath = nullptr,
1059  int depth = 4)
1060 {
1061  if (depth < 0)
1062  return nullptr;
1063  if (!tok)
1064  return nullptr;
1065  for (const ValueFlow::Value& val : tok->values()) {
1066  if (!val.isLocalLifetimeValue())
1067  continue;
1071  val.lifetimeKind)) {
1072  if (val.isInconclusive())
1073  return nullptr;
1074  if (val.capturetok)
1075  return getInnerLifetime(val.capturetok, id, errorPath, depth - 1);
1076  if (errorPath)
1077  errorPath->insert(errorPath->end(), val.errorPath.cbegin(), val.errorPath.cend());
1078  return getInnerLifetime(val.tokvalue, id, errorPath, depth - 1);
1079  }
1080  if (!val.tokvalue->variable())
1081  continue;
1082  if (val.tokvalue->varId() != id)
1083  continue;
1084  return &val;
1085  }
1086  return nullptr;
1087 }
1088 
1089 static const Token* endOfExpression(const Token* tok)
1090 {
1091  if (!tok)
1092  return nullptr;
1093  const Token* parent = tok->astParent();
1094  while (Token::simpleMatch(parent, "."))
1095  parent = parent->astParent();
1096  if (!parent)
1097  return tok->next();
1098  const Token* endToken = nextAfterAstRightmostLeaf(parent);
1099  if (!endToken)
1100  return parent->next();
1101  return endToken;
1102 }
1103 
1105 {
1106  logChecker("CheckStl::invalidContainer");
1107  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
1108  const Library& library = mSettings->library;
1109  InvalidContainerAnalyzer analyzer;
1110  analyzer.analyze(symbolDatabase);
1111  for (const Scope * scope : symbolDatabase->functionScopes) {
1112  for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
1113  if (const Token* contTok = getLoopContainer(tok)) {
1114  const Token* blockStart = tok->next()->link()->next();
1115  const Token* blockEnd = blockStart->link();
1116  if (contTok->exprId() == 0)
1117  continue;
1118  if (!astIsContainer(contTok))
1119  continue;
1120  for (const Token* tok2 = blockStart; tok2 != blockEnd; tok2 = tok2->next()) {
1121  bool bail = false;
1122  for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok2)) {
1123  if (!astIsContainer(r.tok))
1124  continue;
1125  if (r.tok->exprId() != contTok->exprId())
1126  continue;
1127  const Scope* s = tok2->scope();
1128  if (!s)
1129  continue;
1131  continue;
1132  invalidContainerLoopError(r.ftok, tok, r.errorPath);
1133  bail = true;
1134  break;
1135  }
1136  if (bail)
1137  break;
1138  }
1139  } else {
1140  for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok)) {
1141  if (!astIsContainer(r.tok))
1142  continue;
1143  std::set<nonneg int> skipVarIds;
1144  // Skip if the variable is assigned to
1145  const Token* assignExpr = tok;
1146  while (assignExpr->astParent()) {
1147  const bool isRHS = astIsRHS(assignExpr);
1149  if (Token::Match(assignExpr, "%assign%")) {
1150  if (!isRHS)
1151  assignExpr = nullptr;
1152  break;
1153  }
1154  }
1155  if (Token::Match(assignExpr, "%assign%") && Token::Match(assignExpr->astOperand1(), "%var%"))
1156  skipVarIds.insert(assignExpr->astOperand1()->varId());
1157  const Token* endToken = endOfExpression(tok);
1158  const ValueFlow::Value* v = nullptr;
1159  ErrorPath errorPath;
1160  PathAnalysis::Info info =
1161  PathAnalysis{endToken, library}.forwardFind([&](const PathAnalysis::Info& info) {
1162  if (!info.tok->variable())
1163  return false;
1164  if (info.tok->varId() == 0)
1165  return false;
1166  if (skipVarIds.count(info.tok->varId()) > 0)
1167  return false;
1168  // if (Token::simpleMatch(info.tok->next(), "."))
1169  // return false;
1170  if (Token::Match(info.tok->astParent(), "%assign%") && astIsLHS(info.tok))
1171  skipVarIds.insert(info.tok->varId());
1172  if (info.tok->variable()->isReference() && !isVariableDecl(info.tok) &&
1173  reaches(info.tok->variable()->nameToken(), tok, library, nullptr)) {
1174 
1175  ErrorPath ep;
1176  bool addressOf = false;
1177  const Variable* var = ValueFlow::getLifetimeVariable(info.tok, ep, *mSettings, &addressOf);
1178  // Check the reference is created before the change
1179  if (var && var->declarationId() == r.tok->varId() && !addressOf) {
1180  // An argument always reaches
1181  if (var->isArgument() ||
1182  (!var->isReference() && !var->isRValueReference() && !isVariableDecl(tok) &&
1183  reaches(var->nameToken(), tok, library, &ep))) {
1184  errorPath = std::move(ep);
1185  return true;
1186  }
1187  }
1188  }
1189  ErrorPath ep;
1190  const ValueFlow::Value* val = getInnerLifetime(info.tok, r.tok->varId(), &ep);
1191  // Check the iterator is created before the change
1192  if (val && val->tokvalue != tok && reaches(val->tokvalue, tok, library, &ep)) {
1193  v = val;
1194  errorPath = std::move(ep);
1195  return true;
1196  }
1197  return false;
1198  });
1199  if (!info.tok)
1200  continue;
1201  errorPath.insert(errorPath.end(), info.errorPath.cbegin(), info.errorPath.cend());
1202  errorPath.insert(errorPath.end(), r.errorPath.cbegin(), r.errorPath.cend());
1203  if (v) {
1204  invalidContainerError(info.tok, r.tok, v, std::move(errorPath));
1205  } else {
1206  invalidContainerReferenceError(info.tok, r.tok, std::move(errorPath));
1207  }
1208  }
1209  }
1210  }
1211  }
1212 }
1213 
1214 void CheckStl::invalidContainerLoopError(const Token* tok, const Token* loopTok, ErrorPath errorPath)
1215 {
1216  const std::string method = tok ? tok->str() : "erase";
1217  errorPath.emplace_back(loopTok, "Iterating container here.");
1218 
1219  // Remove duplicate entries from error path
1220  errorPath.remove_if([&](const ErrorPathItem& epi) {
1221  return epi.first == tok;
1222  });
1223 
1224  const std::string msg = "Calling '" + method + "' while iterating the container is invalid.";
1225  errorPath.emplace_back(tok, "");
1226  reportError(errorPath, Severity::error, "invalidContainerLoop", msg, CWE664, Certainty::normal);
1227 }
1228 
1229 void CheckStl::invalidContainerError(const Token *tok, const Token * /*contTok*/, const ValueFlow::Value *val, ErrorPath errorPath)
1230 {
1231  const bool inconclusive = val ? val->isInconclusive() : false;
1232  if (val)
1233  errorPath.insert(errorPath.begin(), val->errorPath.cbegin(), val->errorPath.cend());
1234  std::string msg = "Using " + lifetimeMessage(tok, val, errorPath);
1235  errorPath.emplace_back(tok, "");
1236  reportError(errorPath, Severity::error, "invalidContainer", msg + " that may be invalid.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);
1237 }
1238 
1239 void CheckStl::invalidContainerReferenceError(const Token* tok, const Token* contTok, ErrorPath errorPath)
1240 {
1241  std::string name = contTok ? contTok->expressionString() : "x";
1242  std::string msg = "Reference to " + name;
1243  errorPath.emplace_back(tok, "");
1244  reportError(errorPath, Severity::error, "invalidContainerReference", msg + " that may be invalid.", CWE664, Certainty::normal);
1245 }
1246 
1248 {
1249  logChecker("CheckStl::stlOutOfBounds");
1250 
1251  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1252 
1253  // Scan through all scopes..
1254  for (const Scope &scope : symbolDatabase->scopeList) {
1255  const Token* tok = scope.classDef;
1256  // only interested in conditions
1257  if ((!scope.isLoopScope() && scope.type != Scope::eIf) || !tok)
1258  continue;
1259 
1260  const Token *condition = nullptr;
1261  if (scope.type == Scope::eFor) {
1262  if (Token::simpleMatch(tok->next()->astOperand2(), ";") && Token::simpleMatch(tok->next()->astOperand2()->astOperand2(), ";"))
1263  condition = tok->next()->astOperand2()->astOperand2()->astOperand1();
1264  } else if (Token::simpleMatch(tok, "do {") && Token::simpleMatch(tok->linkAt(1), "} while ("))
1265  condition = tok->linkAt(1)->tokAt(2)->astOperand2();
1266  else
1267  condition = tok->next()->astOperand2();
1268 
1269  if (!condition)
1270  continue;
1271 
1272  std::vector<const Token *> conds;
1273 
1274  visitAstNodes(condition,
1275  [&](const Token *cond) {
1276  if (Token::Match(cond, "%oror%|&&"))
1278  if (cond->isComparisonOp())
1279  conds.emplace_back(cond);
1280  return ChildrenToVisit::none;
1281  });
1282 
1283  for (const Token *cond : conds) {
1284  const Token *vartok;
1285  const Token *containerToken;
1286  // check in the ast that cond is of the form "%var% <= %var% . %name% ( )"
1287  if (cond->str() == "<=" && Token::Match(cond->astOperand1(), "%var%") &&
1288  cond->astOperand2()->str() == "(" && cond->astOperand2()->astOperand1()->str() == "." &&
1289  Token::Match(cond->astOperand2()->astOperand1()->astOperand1(), "%var%") &&
1290  Token::Match(cond->astOperand2()->astOperand1()->astOperand2(), "%name%")) {
1291  vartok = cond->astOperand1();
1292  containerToken = cond->next();
1293  } else {
1294  continue;
1295  }
1296 
1298  continue;
1299 
1300  // Is it a array like container?
1301  const Library::Container* container = containerToken->valueType() ? containerToken->valueType()->container : nullptr;
1302  if (!container)
1303  continue;
1304  if (container->getYield(containerToken->strAt(2)) != Library::Container::Yield::SIZE)
1305  continue;
1306 
1307  // variable id for loop variable.
1308  const int numId = vartok->varId();
1309 
1310  // variable id for the container variable
1311  const int declarationId = containerToken->varId();
1312  const std::string &containerName = containerToken->str();
1313 
1314  for (const Token *tok3 = scope.bodyStart; tok3 && tok3 != scope.bodyEnd; tok3 = tok3->next()) {
1315  if (tok3->varId() == declarationId) {
1316  tok3 = tok3->next();
1317  if (Token::Match(tok3, ". %name% ( )")) {
1318  if (container->getYield(tok3->strAt(1)) == Library::Container::Yield::SIZE)
1319  break;
1320  } else if (container->arrayLike_indexOp && Token::Match(tok3, "[ %varid% ]", numId))
1321  stlOutOfBoundsError(tok3, tok3->strAt(1), containerName, false);
1322  else if (Token::Match(tok3, ". %name% ( %varid% )", numId)) {
1323  const Library::Container::Yield yield = container->getYield(tok3->strAt(1));
1325  stlOutOfBoundsError(tok3, tok3->strAt(3), containerName, true);
1326  }
1327  }
1328  }
1329  }
1330  }
1331 }
1332 
1333 void CheckStl::stlOutOfBoundsError(const Token *tok, const std::string &num, const std::string &var, bool at)
1334 {
1335  if (at)
1336  reportError(tok, Severity::error, "stlOutOfBounds", "$symbol:" + var + "\nWhen " + num + "==$symbol.size(), $symbol.at(" + num + ") is out of bounds.", CWE788, Certainty::normal);
1337  else
1338  reportError(tok, Severity::error, "stlOutOfBounds", "$symbol:" + var + "\nWhen " + num + "==$symbol.size(), $symbol[" + num + "] is out of bounds.", CWE788, Certainty::normal);
1339 }
1340 
1342 {
1343  logChecker("CheckStl::negativeIndex");
1344 
1345  // Negative index is out of bounds..
1346  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1347  for (const Scope * scope : symbolDatabase->functionScopes) {
1348  for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
1349  if (!Token::Match(tok, "%var% [") || !tok->next()->astOperand2())
1350  continue;
1351  const Variable * const var = tok->variable();
1352  if (!var || tok == var->nameToken())
1353  continue;
1354  const Library::Container * const container = mSettings->library.detectContainer(var->typeStartToken());
1355  if (!container || !container->arrayLike_indexOp)
1356  continue;
1357  const ValueFlow::Value *index = tok->next()->astOperand2()->getValueLE(-1, *mSettings);
1358  if (!index)
1359  continue;
1360  negativeIndexError(tok, *index);
1361  }
1362  }
1363 }
1364 
1366 {
1367  const ErrorPath errorPath = getErrorPath(tok, &index, "Negative array index");
1368  std::ostringstream errmsg;
1369  if (index.condition)
1371  << ", otherwise there is negative array index " << index.intvalue << ".";
1372  else
1373  errmsg << "Array index " << index.intvalue << " is out of bounds.";
1374  const auto severity = index.errorSeverity() && index.isKnown() ? Severity::error : Severity::warning;
1375  const auto certainty = index.isInconclusive() ? Certainty::inconclusive : Certainty::normal;
1376  reportError(errorPath, severity, "negativeContainerIndex", errmsg.str(), CWE786, certainty);
1377 }
1378 
1380 {
1381  logChecker("CheckStl::erase");
1382 
1383  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1384 
1385  for (const Scope &scope : symbolDatabase->scopeList) {
1386  if (scope.type == Scope::eFor && Token::simpleMatch(scope.classDef, "for (")) {
1387  const Token *tok = scope.classDef->linkAt(1);
1388  if (!Token::Match(tok->tokAt(-3), "; ++| %var% ++| ) {"))
1389  continue;
1390  tok = tok->previous();
1391  if (!tok->isName())
1392  tok = tok->previous();
1393  eraseCheckLoopVar(scope, tok->variable());
1394  } else if (scope.type == Scope::eWhile && Token::Match(scope.classDef, "while ( %var% !=")) {
1395  eraseCheckLoopVar(scope, scope.classDef->tokAt(2)->variable());
1396  }
1397  }
1398 }
1399 
1400 void CheckStl::eraseCheckLoopVar(const Scope &scope, const Variable *var)
1401 {
1402  bool inconclusiveType=false;
1403  if (!isIterator(var, inconclusiveType))
1404  return;
1405  for (const Token *tok = scope.bodyStart; tok != scope.bodyEnd; tok = tok->next()) {
1406  if (tok->str() != "(")
1407  continue;
1408  if (!Token::Match(tok->tokAt(-2), ". erase ( ++| %varid% )", var->declarationId()))
1409  continue;
1410  // Vector erases are handled by invalidContainer check
1411  if (isVector(tok->tokAt(-3)))
1412  continue;
1413  if (Token::Match(tok->astParent(), "=|return"))
1414  continue;
1415  // Iterator is invalid..
1416  int indentlevel = 0U;
1417  const Token *tok2 = tok->link();
1418  for (; tok2 != scope.bodyEnd; tok2 = tok2->next()) {
1419  if (tok2->str() == "{") {
1420  ++indentlevel;
1421  continue;
1422  }
1423  if (tok2->str() == "}") {
1424  if (indentlevel > 0U)
1425  --indentlevel;
1426  else if (Token::simpleMatch(tok2, "} else {"))
1427  tok2 = tok2->linkAt(2);
1428  continue;
1429  }
1430  if (tok2->varId() == var->declarationId()) {
1431  if (Token::simpleMatch(tok2->next(), "="))
1432  break;
1433  dereferenceErasedError(tok, tok2, tok2->str(), inconclusiveType);
1434  break;
1435  }
1436  if (indentlevel == 0U && Token::Match(tok2, "break|return|goto"))
1437  break;
1438  }
1439  if (tok2 == scope.bodyEnd)
1440  dereferenceErasedError(tok, scope.classDef, var->nameToken()->str(), inconclusiveType);
1441  }
1442 }
1443 
1445 {
1446  logChecker("CheckStl::stlBoundaries");
1447 
1448  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1449  for (const Variable* var : symbolDatabase->variableList()) {
1450  if (!var || !var->scope() || !var->scope()->isExecutable())
1451  continue;
1452 
1454  if (!container || container->opLessAllowed)
1455  continue;
1456 
1457  const Token* const end = var->scope()->bodyEnd;
1458  for (const Token *tok = var->nameToken(); tok != end; tok = tok->next()) {
1459  if (Token::Match(tok, "!!* %varid% <", var->declarationId())) {
1460  stlBoundariesError(tok);
1461  } else if (Token::Match(tok, "> %varid% !!.", var->declarationId())) {
1462  stlBoundariesError(tok);
1463  }
1464  }
1465  }
1466 }
1467 
1468 // Error message for bad boundary usage..
1470 {
1471  reportError(tok, Severity::error, "stlBoundaries",
1472  "Dangerous comparison using operator< on iterator.\n"
1473  "Iterator compared with operator<. This is dangerous since the order of items in the "
1474  "container is not guaranteed. One should use operator!= instead to compare iterators.", CWE664, Certainty::normal);
1475 }
1476 
1477 static bool if_findCompare(const Token * const tokBack, bool stdStringLike)
1478 {
1479  const Token *tok = tokBack->astParent();
1480  if (!tok)
1481  return true;
1482  if (tok->isComparisonOp()) {
1483  if (stdStringLike) {
1484  const Token * const tokOther = tokBack->astSibling();
1485  return !tokOther || !tokOther->hasKnownIntValue() || tokOther->getKnownIntValue() != 0;
1486  }
1487  return (!tok->astOperand1()->isNumber() && !tok->astOperand2()->isNumber());
1488  }
1489  if (tok->isArithmeticalOp()) // result is used in some calculation
1490  return true; // TODO: check if there is a comparison of the result somewhere
1491  if (tok->str() == ".")
1492  return true; // Dereferencing is OK, the programmer might know that the element exists - TODO: An inconclusive warning might be appropriate
1493  if (tok->isAssignmentOp())
1494  return if_findCompare(tok, stdStringLike); // Go one step upwards in the AST
1495  return false;
1496 }
1497 
1499 {
1500  const bool printWarning = mSettings->severity.isEnabled(Severity::warning);
1501  const bool printPerformance = mSettings->severity.isEnabled(Severity::performance);
1502  if (!printWarning && !printPerformance)
1503  return;
1504 
1505  logChecker("CheckStl::if_find"); // warning,performance
1506 
1507  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
1508 
1509  for (const Scope &scope : symbolDatabase->scopeList) {
1510  if ((scope.type != Scope::eIf && scope.type != Scope::eWhile) || !scope.classDef)
1511  continue;
1512 
1513  const Token *conditionStart = scope.classDef->next();
1514  if (Token::simpleMatch(conditionStart->astOperand2(), ";"))
1515  conditionStart = conditionStart->astOperand2();
1516 
1517  for (const Token *tok = conditionStart; tok->str() != "{"; tok = tok->next()) {
1518  const Token* funcTok = nullptr;
1519  const Library::Container* container = nullptr;
1520 
1521  if (Token::Match(tok, "%name% ("))
1522  tok = tok->linkAt(1);
1523 
1524  else if (tok->variable() && Token::Match(tok, "%var% . %name% (")) {
1525  container = mSettings->library.detectContainer(tok->variable()->typeStartToken());
1526  funcTok = tok->tokAt(2);
1527  }
1528 
1529  // check also for vector-like or pointer containers
1530  else if (tok->variable() && tok->astParent() && (tok->astParent()->str() == "*" || tok->astParent()->str() == "[")) {
1531  const Token *tok2 = tok->astParent();
1532 
1533  if (!Token::Match(tok2->astParent(), ". %name% ("))
1534  continue;
1535 
1536  funcTok = tok2->astParent()->next();
1537 
1538  if (tok->variable()->isArrayOrPointer())
1539  container = mSettings->library.detectContainer(tok->variable()->typeStartToken());
1540  else { // Container of container - find the inner container
1541  container = mSettings->library.detectContainer(tok->variable()->typeStartToken()); // outer container
1542  tok2 = Token::findsimplematch(tok->variable()->typeStartToken(), "<", tok->variable()->typeEndToken());
1543  if (container && container->type_templateArgNo >= 0 && tok2) {
1544  tok2 = tok2->next();
1545  for (int j = 0; j < container->type_templateArgNo; j++)
1546  tok2 = tok2->nextTemplateArgument();
1547 
1548  container = mSettings->library.detectContainer(tok2); // inner container
1549  } else
1550  container = nullptr;
1551  }
1552  }
1553 
1554  Library::Container::Action action{};
1555  if (container &&
1556  ((action = container->getAction(funcTok->str())) == Library::Container::Action::FIND || action == Library::Container::Action::FIND_CONST)) {
1557  if (if_findCompare(funcTok->next(), container->stdStringLike))
1558  continue;
1559 
1560  if (printWarning && container->getYield(funcTok->str()) == Library::Container::Yield::ITERATOR)
1561  if_findError(tok, false);
1562  else if (printPerformance && container->stdStringLike && funcTok->str() == "find")
1563  if_findError(tok, true);
1564  } else if (printWarning && Token::Match(tok, "std :: find|find_if (")) {
1565  // check that result is checked properly
1566  if (!if_findCompare(tok->tokAt(3), false)) {
1567  if_findError(tok, false);
1568  }
1569  }
1570  }
1571  }
1572 }
1573 
1574 
1575 void CheckStl::if_findError(const Token *tok, bool str)
1576 {
1577  if (str && mSettings->standards.cpp >= Standards::CPP20)
1578  reportError(tok, Severity::performance, "stlIfStrFind",
1579  "Inefficient usage of string::find() in condition; string::starts_with() could be faster.\n"
1580  "Either inefficient or wrong usage of string::find(). string::starts_with() will be faster if "
1581  "string::find's result is compared with 0, because it will not scan the whole "
1582  "string. If your intention is to check that there are no findings in the string, "
1583  "you should compare with std::string::npos.", CWE597, Certainty::normal);
1584  if (!str)
1585  reportError(tok, Severity::warning, "stlIfFind", "Suspicious condition. The result of find() is an iterator, but it is not properly checked.", CWE398, Certainty::normal);
1586 }
1587 
1588 static std::pair<const Token *, const Token *> isMapFind(const Token *tok)
1589 {
1590  if (!Token::simpleMatch(tok, "("))
1591  return {};
1592  if (!Token::simpleMatch(tok->astOperand1(), "."))
1593  return {};
1594  if (!astIsContainer(tok->astOperand1()->astOperand1()))
1595  return {};
1596  const Token * contTok = tok->astOperand1()->astOperand1();
1597  const Library::Container * container = contTok->valueType()->container;
1598  if (!container)
1599  return {};
1600  if (!container->stdAssociativeLike)
1601  return {};
1602  if (!Token::Match(tok->astOperand1(), ". find|count ("))
1603  return {};
1604  if (!tok->astOperand2())
1605  return {};
1606  return {contTok, tok->astOperand2()};
1607 }
1608 
1609 static const Token* skipLocalVars(const Token* const tok)
1610 {
1611  if (!tok)
1612  return tok;
1613  if (Token::simpleMatch(tok, "{"))
1614  return skipLocalVars(tok->next());
1615 
1616  const Token *top = tok->astTop();
1617  if (!top) {
1618  const Token *semi = Token::findsimplematch(tok, ";");
1619  if (!semi)
1620  return tok;
1621  if (!Token::Match(semi->previous(), "%var% ;"))
1622  return tok;
1623  const Token *varTok = semi->previous();
1624  const Variable *var = varTok->variable();
1625  if (!var)
1626  return tok;
1627  if (var->nameToken() != varTok)
1628  return tok;
1629  return skipLocalVars(semi->next());
1630  }
1631  if (tok->isAssignmentOp()) {
1632  const Token *varTok = top->astOperand1();
1633  const Variable *var = varTok->variable();
1634  if (!var)
1635  return tok;
1636  if (var->scope() != tok->scope())
1637  return tok;
1638  const Token *endTok = nextAfterAstRightmostLeaf(top);
1639  if (!endTok)
1640  return tok;
1641  return skipLocalVars(endTok->next());
1642  }
1643  return tok;
1644 }
1645 
1646 static const Token *findInsertValue(const Token *tok, const Token *containerTok, const Token *keyTok, const Settings &settings)
1647 {
1648  const Token *startTok = skipLocalVars(tok);
1649  const Token *top = startTok->astTop();
1650 
1651  const Token *icontainerTok = nullptr;
1652  const Token *ikeyTok = nullptr;
1653  const Token *ivalueTok = nullptr;
1654  if (Token::simpleMatch(top, "=") && Token::simpleMatch(top->astOperand1(), "[")) {
1655  icontainerTok = top->astOperand1()->astOperand1();
1656  ikeyTok = top->astOperand1()->astOperand2();
1657  ivalueTok = top->astOperand2();
1658  }
1659  if (Token::simpleMatch(top, "(") && Token::Match(top->astOperand1(), ". insert|emplace (") && !astIsIterator(top->astOperand1()->tokAt(2))) {
1660  icontainerTok = top->astOperand1()->astOperand1();
1661  const Token *itok = top->astOperand1()->tokAt(2)->astOperand2();
1662  if (Token::simpleMatch(itok, ",")) {
1663  ikeyTok = itok->astOperand1();
1664  ivalueTok = itok->astOperand2();
1665  } else {
1666  ikeyTok = itok;
1667  }
1668  }
1669  if (!ikeyTok || !icontainerTok)
1670  return nullptr;
1671  if (isSameExpression(true, containerTok, icontainerTok, settings, true, false) &&
1672  isSameExpression(true, keyTok, ikeyTok, settings, true, true)) {
1673  if (ivalueTok)
1674  return ivalueTok;
1675  return ikeyTok;
1676  }
1677  return nullptr;
1678 }
1679 
1681 {
1683  return;
1684 
1685  logChecker("CheckStl::checkFindInsert"); // performance
1686 
1687  const SymbolDatabase *const symbolDatabase = mTokenizer->getSymbolDatabase();
1688  for (const Scope *scope : symbolDatabase->functionScopes) {
1689  for (const Token *tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
1690  if (!Token::simpleMatch(tok, "if ("))
1691  continue;
1692  if (!Token::simpleMatch(tok->next()->link(), ") {"))
1693  continue;
1694  if (!Token::Match(tok->next()->astOperand2(), "%comp%"))
1695  continue;
1696  const Token *condTok = tok->next()->astOperand2();
1697  const Token *containerTok;
1698  const Token *keyTok;
1699  std::tie(containerTok, keyTok) = isMapFind(condTok->astOperand1());
1700  if (!containerTok)
1701  continue;
1702  // In < C++17 we only warn for small simple types
1703  if (mSettings->standards.cpp < Standards::CPP17 && !(keyTok && keyTok->valueType() && (keyTok->valueType()->isIntegral() || keyTok->valueType()->pointer > 0)))
1704  continue;
1705 
1706  const Token *thenTok = tok->next()->link()->next();
1707  const Token *valueTok = findInsertValue(thenTok, containerTok, keyTok, *mSettings);
1708  if (!valueTok)
1709  continue;
1710 
1711  if (Token::simpleMatch(thenTok->link(), "} else {")) {
1712  const Token *valueTok2 =
1713  findInsertValue(thenTok->link()->tokAt(2), containerTok, keyTok, *mSettings);
1714  if (!valueTok2)
1715  continue;
1716  if (isSameExpression(true, valueTok, valueTok2, *mSettings, true, true)) {
1717  checkFindInsertError(valueTok);
1718  }
1719  } else {
1720  checkFindInsertError(valueTok);
1721  }
1722  }
1723  }
1724 }
1725 
1727 {
1728  std::string replaceExpr;
1729  if (tok && Token::simpleMatch(tok->astParent(), "=") && tok == tok->astParent()->astOperand2() && Token::simpleMatch(tok->astParent()->astOperand1(), "[")) {
1731  // We will recommend using emplace/try_emplace instead
1732  return;
1733  const std::string f = (mSettings->standards.cpp < Standards::CPP17) ? "emplace" : "try_emplace";
1734  replaceExpr = " Instead of '" + tok->astParent()->expressionString() + "' consider using '" +
1735  tok->astParent()->astOperand1()->astOperand1()->expressionString() +
1736  "." + f + "(" +
1737  tok->astParent()->astOperand1()->astOperand2()->expressionString() +
1738  ", " +
1739  tok->expressionString() +
1740  ");'.";
1741  }
1742 
1743  reportError(
1744  tok, Severity::performance, "stlFindInsert", "Searching before insertion is not necessary." + replaceExpr, CWE398, Certainty::normal);
1745 }
1746 
1747 /**
1748  * Is container.size() slow?
1749  */
1750 static bool isCpp03ContainerSizeSlow(const Token *tok)
1751 {
1752  if (!tok)
1753  return false;
1754  const Variable* var = tok->variable();
1755  return var && var->isStlType("list");
1756 }
1757 
1759 {
1761  return;
1762 
1764  return;
1765 
1766  logChecker("CheckStl::size"); // performance,c++03
1767 
1768  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1769  for (const Scope * scope : symbolDatabase->functionScopes) {
1770  for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
1771  if (Token::Match(tok, "%var% . size ( )") ||
1772  Token::Match(tok, "%name% . %var% . size ( )")) {
1773  // get the variable
1774  const Token *varTok = tok;
1775  if (tok->strAt(2) != "size")
1776  varTok = varTok->tokAt(2);
1777 
1778  const Token* const end = varTok->tokAt(5);
1779 
1780  // check for comparison to zero
1781  if ((!tok->previous()->isArithmeticalOp() && Token::Match(end, "==|<=|!=|> 0")) ||
1782  (end->next() && !end->next()->isArithmeticalOp() && Token::Match(tok->tokAt(-2), "0 ==|>=|!=|<"))) {
1783  if (isCpp03ContainerSizeSlow(varTok)) {
1784  sizeError(varTok);
1785  continue;
1786  }
1787  }
1788 
1789  // check for comparison to one
1790  if ((!tok->previous()->isArithmeticalOp() && Token::Match(end, ">=|< 1") && !end->tokAt(2)->isArithmeticalOp()) ||
1791  (end->next() && !end->next()->isArithmeticalOp() && Token::Match(tok->tokAt(-2), "1 <=|>") && !tok->tokAt(-3)->isArithmeticalOp())) {
1792  if (isCpp03ContainerSizeSlow(varTok))
1793  sizeError(varTok);
1794  }
1795 
1796  // check for using as boolean expression
1797  else if ((Token::Match(tok->tokAt(-2), "if|while (") && end->str() == ")") ||
1798  (tok->previous()->tokType() == Token::eLogicalOp && Token::Match(end, "&&|)|,|;|%oror%"))) {
1799  if (isCpp03ContainerSizeSlow(varTok))
1800  sizeError(varTok);
1801  }
1802  }
1803  }
1804  }
1805 }
1806 
1807 void CheckStl::sizeError(const Token *tok)
1808 {
1809  const std::string varname = tok ? tok->str() : std::string("list");
1810  reportError(tok, Severity::performance, "stlSize",
1811  "$symbol:" + varname + "\n"
1812  "Possible inefficient checking for '$symbol' emptiness.\n"
1813  "Checking for '$symbol' emptiness might be inefficient. "
1814  "Using $symbol.empty() instead of $symbol.size() can be faster. "
1815  "$symbol.size() can take linear time but $symbol.empty() is "
1816  "guaranteed to take constant time.", CWE398, Certainty::normal);
1817 }
1818 
1820 {
1821  if (!mSettings->severity.isEnabled(Severity::style) && !mSettings->isPremiumEnabled("redundantIfRemove"))
1822  return;
1823 
1824  logChecker("CheckStl::redundantCondition"); // style
1825 
1826  const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
1827 
1828  for (const Scope &scope : symbolDatabase->scopeList) {
1829  if (scope.type != Scope::eIf)
1830  continue;
1831 
1832  const Token* tok = scope.classDef->tokAt(2);
1833  if (!Token::Match(tok, "%name% . find ( %any% ) != %name% . end|rend|cend|crend ( ) ) { %name% . remove|erase ( %any% ) ;"))
1834  continue;
1835 
1836  // Get tokens for the fields %name% and %any%
1837  const Token *var1 = tok;
1838  const Token *any1 = var1->tokAt(4);
1839  const Token *var2 = any1->tokAt(3);
1840  const Token *var3 = var2->tokAt(7);
1841  const Token *any2 = var3->tokAt(4);
1842 
1843  // Check if all the "%name%" fields are the same and if all the "%any%" are the same..
1844  if (var1->str() == var2->str() &&
1845  var2->str() == var3->str() &&
1846  any1->str() == any2->str()) {
1848  }
1849  }
1850 }
1851 
1853 {
1854  reportError(tok, Severity::style, "redundantIfRemove",
1855  "Redundant checking of STL container element existence before removing it.\n"
1856  "Redundant checking of STL container element existence before removing it. "
1857  "It is safe to call the remove method on a non-existing element.", CWE398, Certainty::normal);
1858 }
1859 
1861 {
1863  return;
1864 
1865  logChecker("CheckStl::missingComparison"); // warning
1866 
1867  const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
1868 
1869  for (const Scope &scope : symbolDatabase->scopeList) {
1870  if (scope.type != Scope::eFor || !scope.classDef)
1871  continue;
1872 
1873  for (const Token *tok2 = scope.classDef->tokAt(2); tok2 != scope.bodyStart; tok2 = tok2->next()) {
1874  if (tok2->str() == ";")
1875  break;
1876 
1877  if (!Token::Match(tok2, "%var% = %name% . begin|rbegin|cbegin|crbegin ( ) ; %name% != %name% . end|rend|cend|crend ( ) ; ++| %name% ++| ) {"))
1878  continue;
1879 
1880  // same container
1881  if (tok2->strAt(2) != tok2->strAt(10))
1882  break;
1883 
1884  const int iteratorId(tok2->varId());
1885 
1886  // same iterator
1887  if (iteratorId == tok2->tokAt(10)->varId())
1888  break;
1889 
1890  // increment iterator
1891  if (!Token::Match(tok2->tokAt(16), "++ %varid% )", iteratorId) &&
1892  !Token::Match(tok2->tokAt(16), "%varid% ++ )", iteratorId)) {
1893  break;
1894  }
1895 
1896  const Token *incrementToken = nullptr;
1897  // Parse loop..
1898  for (const Token *tok3 = scope.bodyStart; tok3 != scope.bodyEnd; tok3 = tok3->next()) {
1899  if (tok3->varId() == iteratorId) {
1900  if (Token::Match(tok3, "%varid% = %name% . insert ( ++| %varid% ++| ,", iteratorId)) {
1901  // skip insertion..
1902  tok3 = tok3->linkAt(6);
1903  if (!tok3)
1904  break;
1905  } else if (Token::simpleMatch(tok3->astParent(), "++"))
1906  incrementToken = tok3;
1907  else if (Token::simpleMatch(tok3->astParent(), "+")) {
1908  if (Token::Match(tok3->astSibling(), "%num%")) {
1909  const Token* tokenGrandParent = tok3->astParent()->astParent();
1910  if (Token::Match(tokenGrandParent, "==|!="))
1911  break;
1912  }
1913  } else if (Token::Match(tok3->astParent(), "==|!="))
1914  incrementToken = nullptr;
1915  } else if (tok3->str() == "break" || tok3->str() == "return")
1916  incrementToken = nullptr;
1917  }
1918  if (incrementToken)
1919  missingComparisonError(incrementToken, tok2->tokAt(16));
1920  }
1921  }
1922 }
1923 
1924 void CheckStl::missingComparisonError(const Token *incrementToken1, const Token *incrementToken2)
1925 {
1926  std::list<const Token*> callstack = { incrementToken1,incrementToken2 };
1927 
1928  std::ostringstream errmsg;
1929  errmsg << "Missing bounds check for extra iterator increment in loop.\n"
1930  << "The iterator incrementing is suspicious - it is incremented at line ";
1931  if (incrementToken1)
1932  errmsg << incrementToken1->linenr();
1933  errmsg << " and then at line ";
1934  if (incrementToken2)
1935  errmsg << incrementToken2->linenr();
1936  errmsg << ". The loop might unintentionally skip an element in the container. "
1937  << "There is no comparison between these increments to prevent that the iterator is "
1938  << "incremented beyond the end.";
1939 
1940  reportError(callstack, Severity::warning, "StlMissingComparison", errmsg.str(), CWE834, Certainty::normal);
1941 }
1942 
1943 
1944 static bool isLocal(const Token *tok)
1945 {
1946  const Variable *var = tok->variable();
1947  return var && !var->isStatic() && var->isLocal();
1948 }
1949 
1950 namespace {
1951  const std::set<std::string> stl_string_stream = {
1952  "istringstream", "ostringstream", "stringstream", "wstringstream"
1953  };
1954 }
1955 
1957 {
1958  const bool printInconclusive = mSettings->certainty.isEnabled(Certainty::inconclusive);
1959  const bool printPerformance = mSettings->severity.isEnabled(Severity::performance);
1960 
1961  const SymbolDatabase* symbolDatabase = mTokenizer->getSymbolDatabase();
1962 
1963  logChecker("CheckStl::string_c_str");
1964 
1965  // Find all functions that take std::string as argument
1966  struct StrArg {
1967  nonneg int n;
1968  std::string argtype;
1969  };
1970  std::multimap<const Function*, StrArg> c_strFuncParam;
1971  if (printPerformance) {
1972  for (const Scope &scope : symbolDatabase->scopeList) {
1973  for (const Function &func : scope.functionList) {
1974  nonneg int numpar = 0;
1975  for (const Variable &var : func.argumentList) {
1976  numpar++;
1977  if ((var.isStlStringType() || var.isStlStringViewType()) && (!var.isReference() || var.isConst()))
1978  c_strFuncParam.emplace(&func, StrArg{ numpar, var.getTypeName() });
1979  }
1980  }
1981  }
1982  }
1983 
1984  auto isString = [](const Token* str) -> bool {
1985  while (Token::Match(str, "::|."))
1986  str = str->astOperand2();
1987  if (Token::Match(str, "(|[") && !(str->valueType() && str->valueType()->type == ValueType::ITERATOR))
1988  str = str->previous();
1989  return str && ((str->variable() && str->variable()->isStlStringType()) || // variable
1990  (str->function() && isStlStringType(str->function()->retDef)) || // function returning string
1991  (str->valueType() && str->valueType()->type == ValueType::ITERATOR && isStlStringType(str->valueType()->containerTypeToken))); // iterator pointing to string
1992  };
1993 
1994  // Try to detect common problems when using string::c_str()
1995  for (const Scope &scope : symbolDatabase->scopeList) {
1996  if (scope.type != Scope::eFunction || !scope.function)
1997  continue;
1998 
1999  enum {charPtr, stdString, stdStringConstRef, Other} returnType = Other;
2000  if (Token::Match(scope.function->tokenDef->tokAt(-2), "char|wchar_t *"))
2001  returnType = charPtr;
2002  else if (Token::Match(scope.function->tokenDef->tokAt(-5), "const std :: string|wstring &"))
2003  returnType = stdStringConstRef;
2004  else if (Token::Match(scope.function->tokenDef->tokAt(-3), "std :: string|wstring !!&"))
2005  returnType = stdString;
2006 
2007  for (const Token *tok = scope.bodyStart; tok && tok != scope.bodyEnd; tok = tok->next()) {
2008  // Invalid usage..
2009  if (Token::Match(tok, "throw %var% . c_str|data ( ) ;") && isLocal(tok->next()) &&
2010  tok->next()->variable() && tok->next()->variable()->isStlStringType()) {
2012  } else if (tok->variable() && tok->strAt(1) == "=") {
2013  if (Token::Match(tok->tokAt(2), "%var% . str ( ) . c_str|data ( ) ;")) {
2014  const Variable* var = tok->variable();
2015  const Variable* var2 = tok->tokAt(2)->variable();
2016  if (var->isPointer() && var2 && var2->isStlType(stl_string_stream))
2017  string_c_strError(tok);
2018  } else if (Token::Match(tok->tokAt(2), "%name% (") &&
2019  Token::Match(tok->linkAt(3), ") . c_str|data ( ) ;") &&
2020  tok->tokAt(2)->function() && Token::Match(tok->tokAt(2)->function()->retDef, "std :: string|wstring %name%")) {
2021  const Variable* var = tok->variable();
2022  if (var->isPointer())
2023  string_c_strError(tok);
2024  } else if (printPerformance && tok->tokAt(1)->astOperand2() && Token::Match(tok->tokAt(1)->astOperand2()->tokAt(-3), "%var% . c_str|data ( ) ;")) {
2025  const Token* vartok = tok->tokAt(1)->astOperand2()->tokAt(-3);
2026  if ((tok->variable()->isStlStringType() || tok->variable()->isStlStringViewType()) && vartok->variable() && vartok->variable()->isStlStringType())
2027  string_c_strAssignment(tok, tok->variable()->getTypeName());
2028  }
2029  } else if (printPerformance && tok->function() && Token::Match(tok, "%name% ( !!)") && tok->str() != scope.className) {
2030  const auto range = c_strFuncParam.equal_range(tok->function());
2031  for (std::multimap<const Function*, StrArg>::const_iterator i = range.first; i != range.second; ++i) {
2032  if (i->second.n == 0)
2033  continue;
2034 
2035  const Token* tok2 = tok->tokAt(2);
2036  int j;
2037  for (j = 0; tok2 && j < i->second.n - 1; j++)
2038  tok2 = tok2->nextArgument();
2039  if (tok2)
2040  tok2 = tok2->nextArgument();
2041  else
2042  break;
2043  if (!tok2 && j == i->second.n - 1)
2044  tok2 = tok->next()->link();
2045  else if (tok2)
2046  tok2 = tok2->previous();
2047  else
2048  break;
2049  if (tok2 && Token::Match(tok2->tokAt(-4), ". c_str|data ( )")) {
2050  if (isString(tok2->tokAt(-4)->astOperand1())) {
2051  string_c_strParam(tok, i->second.n, i->second.argtype);
2052  } else if (Token::Match(tok2->tokAt(-9), "%name% . str ( )")) { // Check ss.str().c_str() as parameter
2053  const Variable* ssVar = tok2->tokAt(-9)->variable();
2054  if (ssVar && ssVar->isStlType(stl_string_stream))
2055  string_c_strParam(tok, i->second.n, i->second.argtype);
2056  }
2057  }
2058  }
2059  } else if (printPerformance && Token::Match(tok, "%var% (|{ %var% . c_str|data ( ) !!,") &&
2060  tok->variable() && (tok->variable()->isStlStringType() || tok->variable()->isStlStringViewType()) &&
2061  tok->tokAt(2)->variable() && tok->tokAt(2)->variable()->isStlStringType()) {
2062  string_c_strConstructor(tok, tok->variable()->getTypeName());
2063  } else if (printPerformance && tok->next() && tok->next()->variable() && tok->next()->variable()->isStlStringType() && tok->valueType() && tok->valueType()->type == ValueType::CONTAINER &&
2064  ((Token::Match(tok->previous(), "%var% + %var% . c_str|data ( )") && tok->previous()->variable() && tok->previous()->variable()->isStlStringType()) ||
2065  (Token::Match(tok->tokAt(-5), "%var% . c_str|data ( ) + %var%") && tok->tokAt(-5)->variable() && tok->tokAt(-5)->variable()->isStlStringType()))) {
2066  string_c_strConcat(tok);
2067  } else if (printPerformance && Token::simpleMatch(tok, "<<") && tok->astOperand2() && Token::Match(tok->astOperand2()->astOperand1(), ". c_str|data ( )")) {
2068  const Token* str = tok->astOperand2()->astOperand1()->astOperand1();
2069  if (isString(str)) {
2070  const Token* strm = tok;
2071  while (Token::simpleMatch(strm, "<<"))
2072  strm = strm->astOperand1();
2073  if (strm && strm->variable() && strm->variable()->isStlType())
2074  string_c_strStream(tok);
2075  }
2076  }
2077 
2078  // Using c_str() to get the return value is only dangerous if the function returns a char*
2079  else if ((returnType == charPtr || (printPerformance && (returnType == stdString || returnType == stdStringConstRef))) && tok->str() == "return") {
2080  bool err = false;
2081 
2082  const Token* tok2 = tok->next();
2083  if (Token::Match(tok2, "std :: string|wstring (") &&
2084  Token::Match(tok2->linkAt(3), ") . c_str|data ( ) ;")) {
2085  err = true;
2086  } else if (Token::simpleMatch(tok2, "(") &&
2087  Token::Match(tok2->link(), ") . c_str|data ( ) ;")) {
2088  // Check for "+ localvar" or "+ std::string(" inside the bracket
2089  bool is_implicit_std_string = printInconclusive;
2090  const Token *search_end = tok2->link();
2091  for (const Token *search_tok = tok2->next(); search_tok != search_end; search_tok = search_tok->next()) {
2092  if (Token::Match(search_tok, "+ %var%") && isLocal(search_tok->next()) &&
2093  search_tok->next()->variable() && search_tok->next()->variable()->isStlStringType()) {
2094  is_implicit_std_string = true;
2095  break;
2096  }
2097  if (Token::Match(search_tok, "+ std :: string|wstring (")) {
2098  is_implicit_std_string = true;
2099  break;
2100  }
2101  }
2102 
2103  if (is_implicit_std_string)
2104  err = true;
2105  }
2106 
2107  bool local = false;
2108  bool ptrOrRef = false;
2109  const Variable* lastVar = nullptr;
2110  const Function* lastFunc = nullptr;
2111  bool funcStr = false;
2112  if (Token::Match(tok2, "%var% .")) {
2113  local = isLocal(tok2);
2114  bool refToNonLocal = false;
2115  if (tok2->variable() && tok2->variable()->isReference()) {
2116  const Token *refTok = tok2->variable()->nameToken();
2117  refToNonLocal = true; // safe assumption is default to avoid FPs
2118  if (Token::Match(refTok, "%var% = %var% .|;|["))
2119  refToNonLocal = !isLocal(refTok->tokAt(2));
2120  }
2121  ptrOrRef = refToNonLocal || (tok2->variable() && (tok2->variable()->isPointer() || tok2->variable()->isSmartPointer()));
2122  }
2123  while (tok2) {
2124  if (Token::Match(tok2, "%var% .|::")) {
2125  if (ptrOrRef)
2126  local = false;
2127  lastVar = tok2->variable();
2128  tok2 = tok2->tokAt(2);
2129  } else if (Token::Match(tok2, "%name% (") && Token::simpleMatch(tok2->linkAt(1), ") .")) {
2130  lastFunc = tok2->function();
2131  local = false;
2132  funcStr = tok2->str() == "str";
2133  tok2 = tok2->linkAt(1)->tokAt(2);
2134  } else
2135  break;
2136  }
2137 
2138  if (Token::Match(tok2, "c_str|data ( ) ;")) {
2139  if ((local || returnType != charPtr) && lastVar && lastVar->isStlStringType())
2140  err = true;
2141  else if (funcStr && lastVar && lastVar->isStlType(stl_string_stream))
2142  err = true;
2143  else if (lastFunc && Token::Match(lastFunc->tokenDef->tokAt(-3), "std :: string|wstring"))
2144  err = true;
2145  }
2146 
2147  if (err) {
2148  if (returnType == charPtr)
2149  string_c_strError(tok);
2150  else
2151  string_c_strReturn(tok);
2152  }
2153  }
2154  }
2155  }
2156 }
2157 
2159 {
2160  reportError(tok, Severity::error, "stlcstrthrow", "Dangerous usage of c_str(). The value returned by c_str() is invalid after throwing exception.\n"
2161  "Dangerous usage of c_str(). The string is destroyed after the c_str() call so the thrown pointer is invalid.");
2162 }
2163 
2165 {
2166  reportError(tok, Severity::error, "stlcstr", "Dangerous usage of c_str(). The value returned by c_str() is invalid after this call.\n"
2167  "Dangerous usage of c_str(). The c_str() return value is only valid until its string is deleted.", CWE664, Certainty::normal);
2168 }
2169 
2171 {
2172  reportError(tok, Severity::performance, "stlcstrReturn", "Returning the result of c_str() in a function that returns std::string is slow and redundant.\n"
2173  "The conversion from const char* as returned by c_str() to std::string creates an unnecessary string copy. Solve that by directly returning the string.", CWE704, Certainty::normal);
2174 }
2175 
2176 void CheckStl::string_c_strParam(const Token* tok, nonneg int number, const std::string& argtype)
2177 {
2178  std::ostringstream oss;
2179  oss << "Passing the result of c_str() to a function that takes " << argtype << " as argument no. " << number << " is slow and redundant.\n"
2180  "The conversion from const char* as returned by c_str() to " << argtype << " creates an unnecessary string copy or length calculation. Solve that by directly passing the string.";
2181  reportError(tok, Severity::performance, "stlcstrParam", oss.str(), CWE704, Certainty::normal);
2182 }
2183 
2184 void CheckStl::string_c_strConstructor(const Token* tok, const std::string& argtype)
2185 {
2186  std::string msg = "Constructing a " + argtype + " from the result of c_str() is slow and redundant.\n"
2187  "Constructing a " + argtype + " from const char* requires a call to strlen(). Solve that by directly passing the string.";
2188  reportError(tok, Severity::performance, "stlcstrConstructor", msg, CWE704, Certainty::normal);
2189 }
2190 
2191 void CheckStl::string_c_strAssignment(const Token* tok, const std::string& argtype)
2192 {
2193  std::string msg = "Assigning the result of c_str() to a " + argtype + " is slow and redundant.\n"
2194  "Assigning a const char* to a " + argtype + " requires a call to strlen(). Solve that by directly assigning the string.";
2195  reportError(tok, Severity::performance, "stlcstrAssignment", msg, CWE704, Certainty::normal);
2196 }
2197 
2199 {
2200  std::string msg = "Concatenating the result of c_str() and a std::string is slow and redundant.\n"
2201  "Concatenating a const char* with a std::string requires a call to strlen(). Solve that by directly concatenating the strings.";
2202  reportError(tok, Severity::performance, "stlcstrConcat", msg, CWE704, Certainty::normal);
2203 }
2204 
2206 {
2207  std::string msg = "Passing the result of c_str() to a stream is slow and redundant.\n"
2208  "Passing a const char* to a stream requires a call to strlen(). Solve that by directly passing the string.";
2209  reportError(tok, Severity::performance, "stlcstrStream", msg, CWE704, Certainty::normal);
2210 }
2211 
2212 //---------------------------------------------------------------------------
2213 //
2214 //---------------------------------------------------------------------------
2215 
2216 namespace {
2217  const std::set<std::string> stl_containers_with_empty_and_clear = {
2218  "deque", "forward_list", "list",
2219  "map", "multimap", "multiset", "set", "string",
2220  "unordered_map", "unordered_multimap", "unordered_multiset",
2221  "unordered_set", "vector", "wstring"
2222  };
2223 
2224 }
2225 
2227 {
2228  const bool printPerformance = mSettings->severity.isEnabled(Severity::performance);
2229  const bool printWarning = mSettings->severity.isEnabled(Severity::warning);
2230  if (!printPerformance && !printWarning)
2231  return;
2232 
2233  logChecker("CheckStl::uselessCalls"); // performance,warning
2234 
2235  const SymbolDatabase* symbolDatabase = mTokenizer->getSymbolDatabase();
2236  for (const Scope * scope : symbolDatabase->functionScopes) {
2237  for (const Token* tok = scope->bodyStart; tok != scope->bodyEnd; tok = tok->next()) {
2238  if (printWarning && Token::Match(tok, "%var% . compare|find|rfind|find_first_not_of|find_first_of|find_last_not_of|find_last_of ( %name% [,)]") &&
2239  tok->varId() == tok->tokAt(4)->varId()) {
2240  const Variable* var = tok->variable();
2241  if (!var || !var->isStlType())
2242  continue;
2243  uselessCallsReturnValueError(tok->tokAt(4), tok->str(), tok->strAt(2));
2244  } else if (printPerformance && Token::Match(tok, "%var% . swap ( %name% )") &&
2245  tok->varId() == tok->tokAt(4)->varId()) {
2246  const Variable* var = tok->variable();
2247  if (!var || !var->isStlType())
2248  continue;
2249  uselessCallsSwapError(tok, tok->str());
2250  } else if (printPerformance && Token::Match(tok, "%var% . substr (") && tok->variable() && tok->variable()->isStlStringType()) {
2251  const Token* funcTok = tok->tokAt(3);
2252  const std::vector<const Token*> args = getArguments(funcTok);
2253  if (Token::Match(tok->tokAt(-2), "%var% =") && tok->varId() == tok->tokAt(-2)->varId() &&
2254  !args.empty() && args[0]->hasKnownIntValue() && args[0]->getKnownIntValue() == 0) {
2256  } else if (args.empty() || (args[0]->hasKnownIntValue() && args[0]->getKnownIntValue() == 0 &&
2257  (args.size() == 1 || (args.size() == 2 && tok->linkAt(3)->strAt(-1) == "npos" && !tok->linkAt(3)->previous()->variable())))) {
2259  } else if (args.size() == 2 && args[1]->hasKnownIntValue() && args[1]->getKnownIntValue() == 0) {
2261  }
2262  } else if (printWarning && Token::Match(tok, "[{};] %var% . empty ( ) ;") &&
2263  !tok->tokAt(4)->astParent() &&
2264  tok->next()->variable() && tok->next()->variable()->isStlType(stl_containers_with_empty_and_clear))
2265  uselessCallsEmptyError(tok->next());
2266  else if (Token::Match(tok, "[{};] std :: remove|remove_if|unique (") && tok->tokAt(5)->nextArgument())
2267  uselessCallsRemoveError(tok->next(), tok->strAt(3));
2268  else if (printPerformance && tok->valueType() && tok->valueType()->type == ValueType::CONTAINER) {
2269  if (Token::Match(tok, "%var% = { %var% . begin ( ) ,") && tok->varId() == tok->tokAt(3)->varId())
2271  else if (const Variable* var = tok->variable()) {
2272  std::string pattern = "%var% = ";
2273  for (const Token* t = var->typeStartToken(); t != var->typeEndToken()->next(); t = t->next()) {
2274  pattern += t->str();
2275  pattern += ' ';
2276  }
2277  pattern += "{|( %varid% . begin ( ) ,";
2278  if (Token::Match(tok, pattern.c_str(), tok->varId()))
2280  }
2281  }
2282  }
2283  }
2284 }
2285 
2286 
2287 void CheckStl::uselessCallsReturnValueError(const Token *tok, const std::string &varname, const std::string &function)
2288 {
2289  std::ostringstream errmsg;
2290  errmsg << "$symbol:" << varname << '\n';
2291  errmsg << "$symbol:" << function << '\n';
2292  errmsg << "It is inefficient to call '" << varname << "." << function << "(" << varname << ")' as it always returns 0.\n"
2293  << "'std::string::" << function << "()' returns zero when given itself as parameter "
2294  << "(" << varname << "." << function << "(" << varname << ")). As it is currently the "
2295  << "code is inefficient. It is possible either the string searched ('"
2296  << varname << "') or searched for ('" << varname << "') is wrong.";
2297  reportError(tok, Severity::warning, "uselessCallsCompare", errmsg.str(), CWE628, Certainty::normal);
2298 }
2299 
2300 void CheckStl::uselessCallsSwapError(const Token *tok, const std::string &varname)
2301 {
2302  reportError(tok, Severity::performance, "uselessCallsSwap",
2303  "$symbol:" + varname + "\n"
2304  "It is inefficient to swap a object with itself by calling '$symbol.swap($symbol)'\n"
2305  "The 'swap()' function has no logical effect when given itself as parameter "
2306  "($symbol.swap($symbol)). As it is currently the "
2307  "code is inefficient. Is the object or the parameter wrong here?", CWE628, Certainty::normal);
2308 }
2309 
2311 {
2312  std::string msg = "Ineffective call of function 'substr' because ";
2313  switch (type) {
2315  msg += "it returns an empty string.";
2316  break;
2317  case SubstrErrorType::COPY:
2318  msg += "it returns a copy of the object. Use operator= instead.";
2319  break;
2321  msg += "a prefix of the string is assigned to itself. Use resize() or pop_back() instead.";
2322  break;
2324  msg += "a prefix of the string is assigned to itself. Use replace() instead.";
2325  break;
2326  }
2327  reportError(tok, Severity::performance, "uselessCallsSubstr", msg, CWE398, Certainty::normal);
2328 }
2329 
2331 {
2332  const std::string msg = "Inefficient constructor call: container '" + tok->str() + "' is assigned a partial copy of itself. Use erase() or resize() instead.";
2333  reportError(tok, Severity::performance, "uselessCallsConstructor", msg, CWE398, Certainty::normal);
2334 }
2335 
2337 {
2338  reportError(tok, Severity::warning, "uselessCallsEmpty", "Ineffective call of function 'empty()'. Did you intend to call 'clear()' instead?", CWE398, Certainty::normal);
2339 }
2340 
2341 void CheckStl::uselessCallsRemoveError(const Token *tok, const std::string& function)
2342 {
2343  reportError(tok, Severity::warning, "uselessCallsRemove",
2344  "$symbol:" + function + "\n"
2345  "Return value of std::$symbol() ignored. Elements remain in container.\n"
2346  "The return value of std::$symbol() is ignored. This function returns an iterator to the end of the range containing those elements that should be kept. "
2347  "Elements past new end remain valid but with unspecified values. Use the erase method of the container to delete them.", CWE762, Certainty::normal);
2348 }
2349 
2350 // Check for iterators being dereferenced before being checked for validity.
2351 // E.g. if (*i && i != str.end()) { }
2353 {
2355  return;
2356 
2357  logChecker("CheckStl::checkDereferenceInvalidIterator"); // warning
2358 
2359  // Iterate over "if", "while", and "for" conditions where there may
2360  // be an iterator that is dereferenced before being checked for validity.
2361  for (const Scope &scope : mTokenizer->getSymbolDatabase()->scopeList) {
2362  if (!(scope.type == Scope::eIf || scope.isLoopScope()))
2363  continue;
2364 
2365  const Token* const tok = scope.classDef;
2366  const Token* startOfCondition = tok->next();
2367  if (scope.type == Scope::eDo)
2368  startOfCondition = startOfCondition->link()->tokAt(2);
2369  if (!startOfCondition) // ticket #6626 invalid code
2370  continue;
2371  const Token* endOfCondition = startOfCondition->link();
2372  if (!endOfCondition)
2373  continue;
2374 
2375  // For "for" loops, only search between the two semicolons
2376  if (scope.type == Scope::eFor) {
2377  startOfCondition = Token::findsimplematch(tok->tokAt(2), ";", endOfCondition);
2378  if (!startOfCondition)
2379  continue;
2380  endOfCondition = Token::findsimplematch(startOfCondition->next(), ";", endOfCondition);
2381  if (!endOfCondition)
2382  continue;
2383  }
2384 
2385  // Only consider conditions composed of all "&&" terms and
2386  // conditions composed of all "||" terms
2387  const bool isOrExpression =
2388  Token::findsimplematch(startOfCondition, "||", endOfCondition) != nullptr;
2389  const bool isAndExpression =
2390  Token::findsimplematch(startOfCondition, "&&", endOfCondition) != nullptr;
2391 
2392  // Look for a check of the validity of an iterator
2393  const Token* validityCheckTok = nullptr;
2394  if (!isOrExpression && isAndExpression) {
2395  validityCheckTok =
2396  Token::findmatch(startOfCondition, "&& %var% != %name% . end|rend|cend|crend ( )", endOfCondition);
2397  } else if (isOrExpression && !isAndExpression) {
2398  validityCheckTok =
2399  Token::findmatch(startOfCondition, "%oror% %var% == %name% . end|rend|cend|crend ( )", endOfCondition);
2400  }
2401 
2402  if (!validityCheckTok)
2403  continue;
2404  const int iteratorVarId = validityCheckTok->next()->varId();
2405 
2406  // If the iterator dereference is to the left of the check for
2407  // the iterator's validity, report an error.
2408  const Token* const dereferenceTok =
2409  Token::findmatch(startOfCondition, "* %varid%", validityCheckTok, iteratorVarId);
2410  if (dereferenceTok)
2411  dereferenceInvalidIteratorError(dereferenceTok, dereferenceTok->strAt(1));
2412  }
2413 }
2414 
2415 
2417 {
2418  const bool printInconclusive = (mSettings->certainty.isEnabled(Certainty::inconclusive));
2419 
2420  logChecker("CheckStl::checkDereferenceInvalidIterator2");
2421 
2422  for (const Token *tok = mTokenizer->tokens(); tok; tok = tok->next()) {
2423  if (Token::Match(tok, "sizeof|decltype|typeid|typeof (")) {
2424  tok = tok->next()->link();
2425  continue;
2426  }
2427 
2428  if (Token::Match(tok, "%assign%"))
2429  continue;
2430 
2431  std::vector<ValueFlow::Value> contValues;
2432  std::copy_if(tok->values().cbegin(), tok->values().cend(), std::back_inserter(contValues), [&](const ValueFlow::Value& value) {
2433  if (value.isImpossible())
2434  return false;
2435  if (!printInconclusive && value.isInconclusive())
2436  return false;
2437  return value.isContainerSizeValue();
2438  });
2439 
2440 
2441  // Can iterator point to END or before START?
2442  for (const ValueFlow::Value& value:tok->values()) {
2443  if (value.isImpossible())
2444  continue;
2445  if (!printInconclusive && value.isInconclusive())
2446  continue;
2447  if (!value.isIteratorValue())
2448  continue;
2449  bool isInvalidIterator = false;
2450  const ValueFlow::Value* cValue = nullptr;
2451  if (value.isIteratorEndValue() && value.intvalue >= 0) {
2452  isInvalidIterator = value.intvalue > 0;
2453  } else if (value.isIteratorStartValue() && value.intvalue < 0) {
2454  isInvalidIterator = true;
2455  } else {
2456  auto it = std::find_if(contValues.cbegin(), contValues.cend(), [&](const ValueFlow::Value& c) {
2457  if (value.path != c.path)
2458  return false;
2459  if (value.isIteratorStartValue() && value.intvalue >= c.intvalue)
2460  return true;
2461  if (value.isIteratorEndValue() && -value.intvalue > c.intvalue)
2462  return true;
2463  return false;
2464  });
2465  if (it == contValues.end())
2466  continue;
2467  cValue = &*it;
2468  if (value.isIteratorStartValue() && value.intvalue > cValue->intvalue)
2469  isInvalidIterator = true;
2470  }
2471  bool inconclusive = false;
2472  bool unknown = false;
2473  const Token* emptyAdvance = nullptr;
2474  const Token* advanceIndex = nullptr;
2475  if (cValue && cValue->intvalue == 0) {
2476  if (Token::Match(tok->astParent(), "+|-") && astIsIntegral(tok->astSibling(), false)) {
2477  if (tok->astSibling() && tok->astSibling()->hasKnownIntValue()) {
2478  if (tok->astSibling()->values().front().intvalue == 0)
2479  continue;
2480  } else {
2481  advanceIndex = tok->astSibling();
2482  }
2483  emptyAdvance = tok->astParent();
2484  } else if (Token::Match(tok->astParent(), "++|--")) {
2485  emptyAdvance = tok->astParent();
2486  }
2487  }
2488  if (!CheckNullPointer::isPointerDeRef(tok, unknown, *mSettings) && !isInvalidIterator && !emptyAdvance) {
2489  if (!unknown)
2490  continue;
2491  inconclusive = true;
2492  }
2493  if (cValue) {
2494  const ValueFlow::Value& lValue = getLifetimeIteratorValue(tok, cValue->path);
2495  if (!lValue.isLifetimeValue())
2496  continue;
2497  if (emptyAdvance)
2498  outOfBoundsError(emptyAdvance,
2499  lValue.tokvalue->expressionString(),
2500  cValue,
2501  advanceIndex ? advanceIndex->expressionString() : emptyString,
2502  nullptr);
2503  else
2504  outOfBoundsError(tok, lValue.tokvalue->expressionString(), cValue, tok->expressionString(), &value);
2505  } else {
2507  }
2508  }
2509  }
2510 }
2511 
2512 void CheckStl::dereferenceInvalidIteratorError(const Token* tok, const ValueFlow::Value *value, bool inconclusive)
2513 {
2514  const std::string& varname = tok ? tok->expressionString() : "var";
2515  const std::string errmsgcond("$symbol:" + varname + '\n' + ValueFlow::eitherTheConditionIsRedundant(value ? value->condition : nullptr) + " or there is possible dereference of an invalid iterator: $symbol.");
2516  if (!tok || !value) {
2517  reportError(tok, Severity::error, "derefInvalidIterator", "Dereference of an invalid iterator", CWE825, Certainty::normal);
2518  reportError(tok, Severity::warning, "derefInvalidIteratorRedundantCheck", errmsgcond, CWE825, Certainty::normal);
2519  return;
2520  }
2521  if (!mSettings->isEnabled(value, inconclusive))
2522  return;
2523 
2524  const ErrorPath errorPath = getErrorPath(tok, value, "Dereference of an invalid iterator");
2525 
2526  if (value->condition) {
2527  reportError(errorPath, Severity::warning, "derefInvalidIteratorRedundantCheck", errmsgcond, CWE825, (inconclusive || value->isInconclusive()) ? Certainty::inconclusive : Certainty::normal);
2528  } else {
2529  std::string errmsg = std::string(value->isKnown() ? "Dereference" : "Possible dereference") + " of an invalid iterator";
2530  if (!varname.empty())
2531  errmsg = "$symbol:" + varname + '\n' + errmsg + ": $symbol";
2532 
2533  reportError(errorPath,
2535  "derefInvalidIterator",
2536  errmsg,
2538  }
2539 }
2540 
2541 void CheckStl::dereferenceInvalidIteratorError(const Token* deref, const std::string &iterName)
2542 {
2544  "derefInvalidIterator",
2545  "$symbol:" + iterName + "\n"
2546  "Possible dereference of an invalid iterator: $symbol\n"
2547  "Possible dereference of an invalid iterator: $symbol. Make sure to check that the iterator is valid before dereferencing it - not after.", CWE825, Certainty::normal);
2548 }
2549 
2550 void CheckStl::useStlAlgorithmError(const Token *tok, const std::string &algoName)
2551 {
2552  reportError(tok, Severity::style, "useStlAlgorithm",
2553  "Consider using " + algoName + " algorithm instead of a raw loop.", CWE398, Certainty::normal);
2554 }
2555 
2556 static bool isEarlyExit(const Token *start)
2557 {
2558  if (start->str() != "{")
2559  return false;
2560  const Token *endToken = start->link();
2561  const Token *tok = Token::findmatch(start, "return|throw|break", endToken);
2562  if (!tok)
2563  return false;
2564  const Token *endStatement = Token::findsimplematch(tok, "; }", endToken);
2565  if (!endStatement)
2566  return false;
2567  if (endStatement->next() != endToken)
2568  return false;
2569  return true;
2570 }
2571 
2572 static const Token *singleStatement(const Token *start)
2573 {
2574  if (start->str() != "{")
2575  return nullptr;
2576  const Token *endToken = start->link();
2577  const Token *endStatement = Token::findsimplematch(start->next(), ";");
2578  if (!Token::simpleMatch(endStatement, "; }"))
2579  return nullptr;
2580  if (endStatement->next() != endToken)
2581  return nullptr;
2582  return endStatement;
2583 }
2584 
2585 static const Token *singleAssignInScope(const Token *start, nonneg int varid, bool &input, bool &hasBreak, const Settings& settings)
2586 {
2587  const Token *endStatement = singleStatement(start);
2588  if (!endStatement)
2589  return nullptr;
2590  if (!Token::Match(start->next(), "%var% %assign%"))
2591  return nullptr;
2592  const Token *assignTok = start->tokAt(2);
2593  if (isVariableChanged(assignTok->next(), endStatement, assignTok->astOperand1()->varId(), /*globalvar*/ false, settings))
2594  return nullptr;
2595  if (isVariableChanged(assignTok->next(), endStatement, varid, /*globalvar*/ false, settings))
2596  return nullptr;
2597  input = Token::findmatch(assignTok->next(), "%varid%", endStatement, varid) || !Token::Match(start->next(), "%var% =");
2598  hasBreak = Token::simpleMatch(endStatement->previous(), "break");
2599  return assignTok;
2600 }
2601 
2602 static const Token *singleMemberCallInScope(const Token *start, nonneg int varid, bool &input, const Settings& settings)
2603 {
2604  if (start->str() != "{")
2605  return nullptr;
2606  const Token *endToken = start->link();
2607  if (!Token::Match(start->next(), "%var% . %name% ("))
2608  return nullptr;
2609  if (!Token::simpleMatch(start->linkAt(4), ") ; }"))
2610  return nullptr;
2611  const Token *endStatement = start->linkAt(4)->next();
2612  if (endStatement->next() != endToken)
2613  return nullptr;
2614 
2615  const Token *dotTok = start->tokAt(2);
2616  if (!Token::findmatch(dotTok->tokAt(2), "%varid%", endStatement, varid))
2617  return nullptr;
2618  input = Token::Match(start->next(), "%var% . %name% ( %varid% )", varid);
2619  if (isVariableChanged(dotTok->next(), endStatement, dotTok->astOperand1()->varId(), /*globalvar*/ false, settings))
2620  return nullptr;
2621  return dotTok;
2622 }
2623 
2624 static const Token *singleIncrementInScope(const Token *start, nonneg int varid, bool &input)
2625 {
2626  if (start->str() != "{")
2627  return nullptr;
2628  const Token *varTok = nullptr;
2629  if (Token::Match(start->next(), "++ %var% ; }"))
2630  varTok = start->tokAt(2);
2631  else if (Token::Match(start->next(), "%var% ++ ; }"))
2632  varTok = start->tokAt(1);
2633  if (!varTok)
2634  return nullptr;
2635  input = varTok->varId() == varid;
2636  return varTok;
2637 }
2638 
2639 static const Token *singleConditionalInScope(const Token *start, nonneg int varid, const Settings& settings)
2640 {
2641  if (start->str() != "{")
2642  return nullptr;
2643  const Token *endToken = start->link();
2644  if (!Token::simpleMatch(start->next(), "if ("))
2645  return nullptr;
2646  if (!Token::simpleMatch(start->linkAt(2), ") {"))
2647  return nullptr;
2648  const Token *bodyTok = start->linkAt(2)->next();
2649  const Token *endBodyTok = bodyTok->link();
2650  if (!Token::simpleMatch(endBodyTok, "} }"))
2651  return nullptr;
2652  if (endBodyTok->next() != endToken)
2653  return nullptr;
2654  if (!Token::findmatch(start, "%varid%", bodyTok, varid))
2655  return nullptr;
2656  if (isVariableChanged(start, bodyTok, varid, /*globalvar*/ false, settings))
2657  return nullptr;
2658  return bodyTok;
2659 }
2660 
2661 static bool addByOne(const Token *tok, nonneg int varid)
2662 {
2663  if (Token::Match(tok, "+= %any% ;") &&
2664  tok->tokAt(1)->hasKnownIntValue() &&
2665  tok->tokAt(1)->getValue(1)) {
2666  return true;
2667  }
2668  if (Token::Match(tok, "= %varid% + %any% ;", varid) &&
2669  tok->tokAt(3)->hasKnownIntValue() &&
2670  tok->tokAt(3)->getValue(1)) {
2671  return true;
2672  }
2673  return false;
2674 }
2675 
2676 static bool accumulateBoolLiteral(const Token *tok, nonneg int varid)
2677 {
2678  if (Token::Match(tok, "%assign% %bool% ;") &&
2679  tok->tokAt(1)->hasKnownIntValue()) {
2680  return true;
2681  }
2682  if (Token::Match(tok, "= %varid% %oror%|%or%|&&|& %bool% ;", varid) &&
2683  tok->tokAt(3)->hasKnownIntValue()) {
2684  return true;
2685  }
2686  return false;
2687 }
2688 
2689 static bool accumulateBool(const Token *tok, nonneg int varid)
2690 {
2691  // Missing %oreq% so we have to check both manually
2692  if (Token::simpleMatch(tok, "&=") || Token::simpleMatch(tok, "|=")) {
2693  return true;
2694  }
2695  if (Token::Match(tok, "= %varid% %oror%|%or%|&&|&", varid)) {
2696  return true;
2697  }
2698  return false;
2699 }
2700 
2701 static bool hasVarIds(const Token *tok, nonneg int var1, nonneg int var2)
2702 {
2703  if (tok->astOperand1()->varId() == tok->astOperand2()->varId())
2704  return false;
2705  if (tok->astOperand1()->varId() == var1 || tok->astOperand1()->varId() == var2) {
2706  if (tok->astOperand2()->varId() == var1 || tok->astOperand2()->varId() == var2) {
2707  return true;
2708  }
2709  }
2710  return false;
2711 }
2712 
2713 static std::string flipMinMax(const std::string &algo)
2714 {
2715  if (algo == "std::max_element")
2716  return "std::min_element";
2717  if (algo == "std::min_element")
2718  return "std::max_element";
2719  return algo;
2720 }
2721 
2722 static std::string minmaxCompare(const Token *condTok, nonneg int loopVar, nonneg int assignVar, bool invert = false)
2723 {
2724  if (!Token::Match(condTok, "<|<=|>=|>"))
2725  return "std::accumulate";
2726  if (!hasVarIds(condTok, loopVar, assignVar))
2727  return "std::accumulate";
2728  std::string algo = "std::max_element";
2729  if (Token::Match(condTok, "<|<="))
2730  algo = "std::min_element";
2731  if (condTok->astOperand1()->varId() == assignVar)
2732  algo = flipMinMax(algo);
2733  if (invert)
2734  algo = flipMinMax(algo);
2735  return algo;
2736 }
2737 
2738 namespace {
2739  struct LoopAnalyzer {
2740  const Token* bodyTok = nullptr;
2741  const Token* loopVar = nullptr;
2742  const Settings* settings = nullptr;
2743  std::set<nonneg int> varsChanged;
2744 
2745  explicit LoopAnalyzer(const Token* tok, const Settings* psettings)
2746  : bodyTok(tok->next()->link()->next()), settings(psettings)
2747  {
2748  const Token* splitTok = tok->next()->astOperand2();
2749  if (Token::simpleMatch(splitTok, ":") && splitTok->previous()->varId() != 0) {
2750  loopVar = splitTok->previous();
2751  }
2752  if (valid()) {
2753  findChangedVariables();
2754  }
2755  }
2756  bool isLoopVarChanged() const {
2757  return varsChanged.count(loopVar->varId()) > 0;
2758  }
2759 
2760  bool isModified(const Token* tok) const
2761  {
2762  if (tok->variable() && tok->variable()->isConst())
2763  return false;
2764  int n = 1 + (astIsPointer(tok) ? 1 : 0);
2765  for (int i = 0; i < n; i++) {
2766  bool inconclusive = false;
2767  if (isVariableChangedByFunctionCall(tok, i, *settings, &inconclusive))
2768  return true;
2769  if (inconclusive)
2770  return true;
2771  if (isVariableChanged(tok, i, *settings))
2772  return true;
2773  }
2774  return false;
2775  }
2776 
2777  template<class Predicate, class F>
2778  void findTokens(Predicate pred, F f) const
2779  {
2780  for (const Token* tok = bodyTok; precedes(tok, bodyTok->link()); tok = tok->next()) {
2781  if (pred(tok))
2782  f(tok);
2783  }
2784  }
2785 
2786  template<class Predicate>
2787  const Token* findToken(Predicate pred) const
2788  {
2789  for (const Token* tok = bodyTok; precedes(tok, bodyTok->link()); tok = tok->next()) {
2790  if (pred(tok))
2791  return tok;
2792  }
2793  return nullptr;
2794  }
2795 
2796  bool hasGotoOrBreak() const
2797  {
2798  return findToken([](const Token* tok) {
2799  return Token::Match(tok, "goto|break");
2800  });
2801  }
2802 
2803  bool valid() const {
2804  return bodyTok && loopVar;
2805  }
2806 
2807  std::string findAlgo() const
2808  {
2809  if (!valid())
2810  return "";
2811  bool loopVarChanged = isLoopVarChanged();
2812  if (!loopVarChanged && varsChanged.empty()) {
2813  if (hasGotoOrBreak())
2814  return "";
2815  bool alwaysTrue = true;
2816  bool alwaysFalse = true;
2817  auto hasReturn = [](const Token* tok) {
2818  return Token::simpleMatch(tok, "return");
2819  };
2820  findTokens(hasReturn, [&](const Token* tok) {
2821  const Token* returnTok = tok->astOperand1();
2822  if (!returnTok || !returnTok->hasKnownIntValue() || !astIsBool(returnTok)) {
2823  alwaysTrue = false;
2824  alwaysFalse = false;
2825  return;
2826  }
2827  (returnTok->values().front().intvalue ? alwaysTrue : alwaysFalse) &= true;
2828  (returnTok->values().front().intvalue ? alwaysFalse : alwaysTrue) &= false;
2829  });
2830  if (alwaysTrue == alwaysFalse)
2831  return "";
2832  if (alwaysTrue)
2833  return "std::any_of";
2834  return "std::all_of or std::none_of";
2835  }
2836  return "";
2837  }
2838 
2839  bool isLocalVar(const Variable* var) const
2840  {
2841  if (!var)
2842  return false;
2843  if (var->isPointer() || var->isReference())
2844  return false;
2845  if (var->declarationId() == loopVar->varId())
2846  return false;
2847  const Scope* scope = var->scope();
2848  return scope && scope->isNestedIn(bodyTok->scope());
2849  }
2850 
2851  private:
2852  void findChangedVariables()
2853  {
2854  std::set<nonneg int> vars;
2855  for (const Token* tok = bodyTok; precedes(tok, bodyTok->link()); tok = tok->next()) {
2856  if (tok->varId() == 0)
2857  continue;
2858  if (vars.count(tok->varId()) > 0)
2859  continue;
2860  if (isLocalVar(tok->variable())) {
2861  vars.insert(tok->varId());
2862  continue;
2863  }
2864  if (!isModified(tok))
2865  continue;
2866  varsChanged.insert(tok->varId());
2867  vars.insert(tok->varId());
2868  }
2869  }
2870  };
2871 } // namespace
2872 
2874 {
2875  if (!mSettings->severity.isEnabled(Severity::style) && !mSettings->isPremiumEnabled("useStlAlgorithm"))
2876  return;
2877 
2878  logChecker("CheckStl::useStlAlgorithm"); // style
2879 
2880  auto checkAssignee = [](const Token* tok) {
2881  if (astIsBool(tok)) // std::accumulate is not a good fit for bool values, std::all/any/none_of return early
2882  return false;
2883  return !astIsContainer(tok); // don't warn for containers, where overloaded operators can be costly
2884  };
2885 
2886  auto isConditionWithoutSideEffects = [this](const Token* tok) -> bool {
2887  if (!Token::simpleMatch(tok, "{") || !Token::simpleMatch(tok->previous(), ")"))
2888  return false;
2889  return isConstExpression(tok->previous()->link()->astOperand2(), mSettings->library);
2890  };
2891 
2892  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
2893  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
2894  // Parse range-based for loop
2895  if (!Token::simpleMatch(tok, "for ("))
2896  continue;
2897  if (!Token::simpleMatch(tok->next()->link(), ") {"))
2898  continue;
2899  LoopAnalyzer a{tok, mSettings};
2900  std::string algoName = a.findAlgo();
2901  if (!algoName.empty()) {
2902  useStlAlgorithmError(tok, algoName);
2903  continue;
2904  }
2905 
2906  const Token *bodyTok = tok->next()->link()->next();
2907  const Token *splitTok = tok->next()->astOperand2();
2908  const Token* loopVar{};
2909  bool isIteratorLoop = false;
2910  if (Token::simpleMatch(splitTok, ":")) {
2911  loopVar = splitTok->previous();
2912  if (loopVar->varId() == 0)
2913  continue;
2914  if (Token::simpleMatch(splitTok->astOperand2(), "{"))
2915  continue;
2916  }
2917  else { // iterator-based loop?
2918  const Token* initTok = getInitTok(tok);
2919  const Token* condTok = getCondTok(tok);
2920  const Token* stepTok = getStepTok(tok);
2921  if (!initTok || !condTok || !stepTok)
2922  continue;
2923  loopVar = Token::Match(condTok, "%comp%") ? condTok->astOperand1() : nullptr;
2924  if (!Token::Match(loopVar, "%var%") || !loopVar->valueType() || loopVar->valueType()->type != ValueType::Type::ITERATOR)
2925  continue;
2926  if (!Token::simpleMatch(initTok, "=") || !Token::Match(initTok->astOperand1(), "%varid%", loopVar->varId()))
2927  continue;
2928  if (!stepTok->isIncDecOp())
2929  continue;
2930  isIteratorLoop = true;
2931  }
2932 
2933  // Check for single assignment
2934  bool useLoopVarInAssign{}, hasBreak{};
2935  const Token *assignTok = singleAssignInScope(bodyTok, loopVar->varId(), useLoopVarInAssign, hasBreak, *mSettings);
2936  if (assignTok) {
2937  if (!checkAssignee(assignTok->astOperand1()))
2938  continue;
2939  const int assignVarId = assignTok->astOperand1()->varId();
2940  std::string algo;
2941  if (assignVarId == loopVar->varId()) {
2942  if (useLoopVarInAssign)
2943  algo = "std::transform";
2944  else if (Token::Match(assignTok->next(), "%var%|%bool%|%num%|%char% ;"))
2945  algo = "std::fill";
2946  else if (Token::Match(assignTok->next(), "%name% ( )"))
2947  algo = "std::generate";
2948  else
2949  algo = "std::fill or std::generate";
2950  } else {
2951  if (addByOne(assignTok, assignVarId))
2952  algo = "std::distance";
2953  else if (accumulateBool(assignTok, assignVarId))
2954  algo = "std::any_of, std::all_of, std::none_of, or std::accumulate";
2955  else if (Token::Match(assignTok, "= %var% <|<=|>=|> %var% ? %var% : %var%") && hasVarIds(assignTok->tokAt(6), loopVar->varId(), assignVarId))
2956  algo = minmaxCompare(assignTok->tokAt(2), loopVar->varId(), assignVarId, assignTok->tokAt(5)->varId() == assignVarId);
2957  else
2958  algo = "std::accumulate";
2959  }
2960  useStlAlgorithmError(assignTok, algo);
2961  continue;
2962  }
2963  // Check for container calls
2964  bool useLoopVarInMemCall;
2965  const Token *memberAccessTok = singleMemberCallInScope(bodyTok, loopVar->varId(), useLoopVarInMemCall, *mSettings);
2966  if (memberAccessTok && !isIteratorLoop) {
2967  const Token *memberCallTok = memberAccessTok->astOperand2();
2968  const int contVarId = memberAccessTok->astOperand1()->varId();
2969  if (contVarId == loopVar->varId())
2970  continue;
2971  if (memberCallTok->str() == "push_back" ||
2972  memberCallTok->str() == "push_front" ||
2973  memberCallTok->str() == "emplace_back") {
2974  std::string algo;
2975  if (useLoopVarInMemCall)
2976  algo = "std::copy";
2977  else
2978  algo = "std::transform";
2979  useStlAlgorithmError(memberCallTok, algo);
2980  }
2981  continue;
2982  }
2983 
2984  // Check for increment in loop
2985  bool useLoopVarInIncrement;
2986  const Token *incrementTok = singleIncrementInScope(bodyTok, loopVar->varId(), useLoopVarInIncrement);
2987  if (incrementTok) {
2988  std::string algo;
2989  if (useLoopVarInIncrement)
2990  algo = "std::transform";
2991  else
2992  algo = "std::distance";
2993  useStlAlgorithmError(incrementTok, algo);
2994  continue;
2995  }
2996 
2997  // Check for conditionals
2998  const Token *condBodyTok = singleConditionalInScope(bodyTok, loopVar->varId(), *mSettings);
2999  if (condBodyTok) {
3000  // Check for single assign
3001  assignTok = singleAssignInScope(condBodyTok, loopVar->varId(), useLoopVarInAssign, hasBreak, *mSettings);
3002  if (assignTok) {
3003  if (!checkAssignee(assignTok->astOperand1()))
3004  continue;
3005  const int assignVarId = assignTok->astOperand1()->varId();
3006  std::string algo;
3007  if (assignVarId == loopVar->varId()) {
3008  if (useLoopVarInAssign)
3009  algo = "std::transform";
3010  else
3011  algo = "std::replace_if";
3012  } else {
3013  if (addByOne(assignTok, assignVarId))
3014  algo = "std::count_if";
3015  else if (accumulateBoolLiteral(assignTok, assignVarId))
3016  algo = "std::any_of, std::all_of, std::none_of, or std::accumulate";
3017  else if (assignTok->str() != "=")
3018  algo = "std::accumulate";
3019  else if (hasBreak && isConditionWithoutSideEffects(condBodyTok))
3020  algo = "std::any_of, std::all_of, std::none_of";
3021  else
3022  continue;
3023  }
3024  useStlAlgorithmError(assignTok, algo);
3025  continue;
3026  }
3027 
3028  // Check for container call
3029  memberAccessTok = singleMemberCallInScope(condBodyTok, loopVar->varId(), useLoopVarInMemCall, *mSettings);
3030  if (memberAccessTok) {
3031  const Token *memberCallTok = memberAccessTok->astOperand2();
3032  const int contVarId = memberAccessTok->astOperand1()->varId();
3033  if (contVarId == loopVar->varId())
3034  continue;
3035  if (memberCallTok->str() == "push_back" ||
3036  memberCallTok->str() == "push_front" ||
3037  memberCallTok->str() == "emplace_back") {
3038  if (useLoopVarInMemCall)
3039  useStlAlgorithmError(memberAccessTok, "std::copy_if");
3040  // There is no transform_if to suggest
3041  }
3042  continue;
3043  }
3044 
3045  // Check for increment in loop
3046  incrementTok = singleIncrementInScope(condBodyTok, loopVar->varId(), useLoopVarInIncrement);
3047  if (incrementTok) {
3048  std::string algo;
3049  if (useLoopVarInIncrement)
3050  algo = "std::transform";
3051  else
3052  algo = "std::count_if";
3053  useStlAlgorithmError(incrementTok, algo);
3054  continue;
3055  }
3056 
3057  // Check early return
3058  if (isEarlyExit(condBodyTok)) {
3059  const Token *loopVar2 = Token::findmatch(condBodyTok, "%varid%", condBodyTok->link(), loopVar->varId());
3060  std::string algo;
3061  if (loopVar2 ||
3062  (isIteratorLoop && loopVar->variable() && precedes(loopVar->variable()->nameToken(), tok))) // iterator declared outside the loop
3063  algo = "std::find_if";
3064  else
3065  algo = "std::any_of";
3066  useStlAlgorithmError(condBodyTok, algo);
3067  continue;
3068  }
3069  }
3070  }
3071  }
3072 }
3073 
3074 void CheckStl::knownEmptyContainerError(const Token *tok, const std::string& algo)
3075 {
3076  const std::string var = tok ? tok->expressionString() : std::string("var");
3077 
3078  std::string msg;
3079  if (astIsIterator(tok)) {
3080  msg = "Using " + algo + " with iterator '" + var + "' that is always empty.";
3081  } else {
3082  msg = "Iterating over container '" + var + "' that is always empty.";
3083  }
3084 
3086  "knownEmptyContainer",
3087  msg, CWE398, Certainty::normal);
3088 }
3089 
3090 static bool isKnownEmptyContainer(const Token* tok)
3091 {
3092  if (!tok)
3093  return false;
3094  return std::any_of(tok->values().begin(), tok->values().end(), [&](const ValueFlow::Value& v) {
3095  if (!v.isKnown())
3096  return false;
3097  if (!v.isContainerSizeValue())
3098  return false;
3099  if (v.intvalue != 0)
3100  return false;
3101  return true;
3102  });
3103 }
3104 
3106 {
3107  if (!mSettings->severity.isEnabled(Severity::style) && !mSettings->isPremiumEnabled("knownEmptyContainer"))
3108  return;
3109  logChecker("CheckStl::knownEmptyContainer"); // style
3110  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
3111  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
3112 
3113  if (!Token::Match(tok, "%name% ( !!)"))
3114  continue;
3115 
3116  // Parse range-based for loop
3117  if (tok->str() == "for") {
3118  if (!Token::simpleMatch(tok->next()->link(), ") {"))
3119  continue;
3120  const Token *splitTok = tok->next()->astOperand2();
3121  if (!Token::simpleMatch(splitTok, ":"))
3122  continue;
3123  const Token* contTok = splitTok->astOperand2();
3124  if (!isKnownEmptyContainer(contTok))
3125  continue;
3127  } else {
3128  const std::vector<const Token *> args = getArguments(tok);
3129  if (args.empty())
3130  continue;
3131 
3132  for (int argnr = 1; argnr <= args.size(); ++argnr) {
3134  if (!i)
3135  continue;
3136  const Token * const argTok = args[argnr - 1];
3137  if (!isKnownEmptyContainer(argTok))
3138  continue;
3139  knownEmptyContainerError(argTok, tok->str());
3140  break;
3141 
3142  }
3143  }
3144  }
3145  }
3146 }
3147 
3148 void CheckStl::eraseIteratorOutOfBoundsError(const Token *ftok, const Token* itertok, const ValueFlow::Value* val)
3149 {
3150  if (!ftok || !itertok || !val) {
3151  reportError(ftok, Severity::error, "eraseIteratorOutOfBounds",
3152  "Calling function 'erase()' on the iterator 'iter' which is out of bounds.", CWE628, Certainty::normal);
3153  reportError(ftok, Severity::warning, "eraseIteratorOutOfBoundsCond",
3154  "Either the condition 'x' is redundant or function 'erase()' is called on the iterator 'iter' which is out of bounds.", CWE628, Certainty::normal);
3155  return;
3156  }
3157  const std::string& func = ftok->str();
3158  const std::string iter = itertok->expressionString();
3159 
3160  const bool isConditional = val->isPossible();
3161  std::string msg;
3162  if (isConditional) {
3163  msg = ValueFlow::eitherTheConditionIsRedundant(val->condition) + " or function '" + func + "()' is called on the iterator '" + iter + "' which is out of bounds.";
3164  } else {
3165  msg = "Calling function '" + func + "()' on the iterator '" + iter + "' which is out of bounds.";
3166  }
3167 
3168  const Severity severity = isConditional ? Severity::warning : Severity::error;
3169  const std::string id = isConditional ? "eraseIteratorOutOfBoundsCond" : "eraseIteratorOutOfBounds";
3170  reportError(ftok, severity,
3171  id,
3172  msg, CWE628, Certainty::normal);
3173 }
3174 
3175 static const ValueFlow::Value* getOOBIterValue(const Token* tok, const ValueFlow::Value* sizeVal)
3176 {
3177  auto it = std::find_if(tok->values().begin(), tok->values().end(), [&](const ValueFlow::Value& v) {
3178  if (v.isPossible() || v.isKnown()) {
3179  switch (v.valueType) {
3180  case ValueFlow::Value::ValueType::ITERATOR_END:
3181  return v.intvalue >= 0;
3182  case ValueFlow::Value::ValueType::ITERATOR_START:
3183  return (v.intvalue < 0) || (sizeVal && v.intvalue >= sizeVal->intvalue);
3184  default:
3185  break;
3186  }
3187  }
3188  return false;
3189  });
3190  return it != tok->values().end() ? &*it : nullptr;
3191 }
3192 
3194 {
3195  logChecker("CheckStl::eraseIteratorOutOfBounds");
3196  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
3197  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
3198 
3199  if (!tok->valueType())
3200  continue;
3201  const Library::Container* container = tok->valueType()->container;
3202  if (!container || !astIsLHS(tok) || !Token::simpleMatch(tok->astParent(), "."))
3203  continue;
3204  const Token* const ftok = tok->astParent()->astOperand2();
3205  const Library::Container::Action action = container->getAction(ftok->str());
3206  if (action != Library::Container::Action::ERASE)
3207  continue;
3208  const std::vector<const Token*> args = getArguments(ftok);
3209  if (args.size() != 1) // TODO: check range overload
3210  continue;
3211 
3213  if (const ValueFlow::Value* errVal = getOOBIterValue(args[0], sizeVal))
3214  eraseIteratorOutOfBoundsError(ftok, args[0], errVal);
3215  }
3216  }
3217 }
3218 
3219 static bool isMutex(const Variable* var)
3220 {
3221  const Token* tok = Token::typeDecl(var->nameToken()).first;
3222  return Token::Match(tok, "std :: mutex|recursive_mutex|timed_mutex|recursive_timed_mutex|shared_mutex");
3223 }
3224 
3225 static bool isLockGuard(const Variable* var)
3226 {
3227  const Token* tok = Token::typeDecl(var->nameToken()).first;
3228  return Token::Match(tok, "std :: lock_guard|unique_lock|scoped_lock|shared_lock");
3229 }
3230 
3231 static bool isLocalMutex(const Variable* var, const Scope* scope)
3232 {
3233  if (!var)
3234  return false;
3235  if (isLockGuard(var))
3236  return false;
3237  return !var->isReference() && !var->isRValueReference() && !var->isStatic() && var->scope() == scope;
3238 }
3239 
3241 {
3243  "globalLockGuard",
3244  "Lock guard is defined globally. Lock guards are intended to be local. A global lock guard could lead to a deadlock since it won't unlock until the end of the program.", CWE833, Certainty::normal);
3245 }
3246 
3248 {
3250  "localMutex",
3251  "The lock is ineffective because the mutex is locked at the same scope as the mutex itself.", CWE667, Certainty::normal);
3252 }
3253 
3255 {
3257  return;
3258  logChecker("CheckStl::checkMutexes"); // warning
3259  for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
3260  std::set<nonneg int> checkedVars;
3261  for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
3262  if (!Token::Match(tok, "%var%"))
3263  continue;
3264  const Variable* var = tok->variable();
3265  if (!var)
3266  continue;
3267  if (Token::Match(tok, "%var% . lock ( )")) {
3268  if (!isMutex(var))
3269  continue;
3270  if (!checkedVars.insert(var->declarationId()).second)
3271  continue;
3272  if (isLocalMutex(var, tok->scope()))
3273  localMutexError(tok);
3274  } else if (Token::Match(tok, "%var% (|{ %var% )|}|,")) {
3275  if (!isLockGuard(var))
3276  continue;
3277  const Variable* mvar = tok->tokAt(2)->variable();
3278  if (!mvar)
3279  continue;
3280  if (!checkedVars.insert(mvar->declarationId()).second)
3281  continue;
3282  if (var->isStatic() || var->isGlobal())
3283  globalLockGuardError(tok);
3284  else if (isLocalMutex(mvar, tok->scope()))
3285  localMutexError(tok);
3286  }
3287  }
3288  }
3289 }
3290 
bool astIsContainer(const Token *tok)
Definition: astutils.cpp:244
const Token * getIteratorExpression(const Token *tok)
Definition: astutils.cpp:3097
std::vector< const Token * > getArguments(const Token *ftok)
Get arguments (AST)
Definition: astutils.cpp:3083
bool isSameExpression(bool macro, const Token *tok1, const Token *tok2, const Settings &settings, bool pure, bool followVar, ErrorPath *errors)
Definition: astutils.cpp:1556
bool astIsIntegral(const Token *tok, bool unknown)
Is expression of integral type?
Definition: astutils.cpp:194
bool exprDependsOnThis(const Token *expr, bool onVar, nonneg int depth)
Definition: astutils.cpp:1105
bool isTemporary(const Token *tok, const Library *library, bool unknown)
Definition: astutils.cpp:415
bool precedes(const Token *tok1, const Token *tok2)
If tok2 comes after tok1.
Definition: astutils.cpp:994
bool astIsPointer(const Token *tok)
Definition: astutils.cpp:220
bool isStlStringType(const Token *tok)
Definition: astutils.cpp:409
bool astIsContainerOwned(const Token *tok)
Definition: astutils.cpp:260
bool astIsLHS(const Token *tok)
Definition: astutils.cpp:784
bool astIsBool(const Token *tok)
Is expression of boolean type?
Definition: astutils.cpp:215
bool isVariableDecl(const Token *tok)
Definition: astutils.cpp:396
static int getArgumentPos(const Token *ftok, const Token *tokToFind)
Definition: astutils.cpp:98
Token * getInitTok(Token *tok)
Definition: astutils.cpp:898
const Token * astParentSkipParens(const Token *tok)
Definition: astutils.cpp:557
Token * getCondTok(Token *tok)
Definition: astutils.cpp:880
bool astIsRHS(const Token *tok)
Definition: astutils.cpp:797
bool astIsFloat(const Token *tok, bool unknown)
Is expression of floating point type?
Definition: astutils.cpp:207
const Token * nextAfterAstRightmostLeaf(const Token *tok)
Definition: astutils.cpp:548
Token * getStepTok(Token *tok)
Definition: astutils.cpp:905
bool isVariableChangedByFunctionCall(const Token *tok, int indirect, nonneg int varid, const Settings &settings, bool *inconclusive)
Is variable changed by function call? In case the answer of the question is inconclusive,...
Definition: astutils.cpp:2263
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 astIsIterator(const Token *tok)
Definition: astutils.cpp:239
bool isConstExpression(const Token *tok, const Library &library)
Definition: astutils.cpp:2049
Library::Container::Yield astContainerYield(const Token *tok, const Token **ftok)
Definition: astutils.cpp:297
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
static std::string flipMinMax(const std::string &algo)
Definition: checkstl.cpp:2713
static const CWE CWE788(788U)
static const Token * getContainerIndex(const Library::Container *container, const Token *parent)
Definition: checkstl.cpp:107
static bool isElementAccessYield(Library::Container::Yield yield)
Definition: checkstl.cpp:67
static const CWE CWE398(398U)
static const CWE CWE762(762U)
static bool accumulateBool(const Token *tok, nonneg int varid)
Definition: checkstl.cpp:2689
static const Token * singleConditionalInScope(const Token *start, nonneg int varid, const Settings &settings)
Definition: checkstl.cpp:2639
static bool isVector(const Token *tok)
Definition: checkstl.cpp:455
static const Token * singleIncrementInScope(const Token *start, nonneg int varid, bool &input)
Definition: checkstl.cpp:2624
static bool containerAppendsElement(const Library::Container *container, const Token *parent)
Definition: checkstl.cpp:72
static const Token * singleMemberCallInScope(const Token *start, nonneg int varid, bool &input, const Settings &settings)
Definition: checkstl.cpp:2602
static bool isKnownEmptyContainer(const Token *tok)
Definition: checkstl.cpp:3090
static std::vector< const Token * > getAddressContainer(const Token *tok)
Definition: checkstl.cpp:689
static const CWE CWE704(704U)
static const CWE CWE597(597U)
static bool isLocalMutex(const Variable *var, const Scope *scope)
Definition: checkstl.cpp:3231
static bool containerYieldsElement(const Library::Container *container, const Token *parent)
Definition: checkstl.cpp:87
static const Token * getInvalidMethod(const Token *tok)
Definition: checkstl.cpp:906
static const CWE CWE825(825U)
static const Token * getContainerFromSize(const Library::Container *container, const Token *tok)
Definition: checkstl.cpp:121
static bool isLocal(const Token *tok)
Definition: checkstl.cpp:1944
static const Token * endOfExpression(const Token *tok)
Definition: checkstl.cpp:1089
static const Token * singleStatement(const Token *start)
Definition: checkstl.cpp:2572
static bool isEarlyExit(const Token *start)
Definition: checkstl.cpp:2556
static const CWE CWE833(833U)
static bool containerPopsElement(const Library::Container *container, const Token *parent)
Definition: checkstl.cpp:97
static const Token * skipLocalVars(const Token *const tok)
Definition: checkstl.cpp:1609
static const CWE CWE667(667U)
static std::pair< const Token *, const Token * > isMapFind(const Token *tok)
Definition: checkstl.cpp:1588
static bool isCpp03ContainerSizeSlow(const Token *tok)
Is container.size() slow?
Definition: checkstl.cpp:1750
static const Token * findInsertValue(const Token *tok, const Token *containerTok, const Token *keyTok, const Settings &settings)
Definition: checkstl.cpp:1646
static std::string indexValueString(const ValueFlow::Value &indexValue, const std::string &containerName=emptyString)
Definition: checkstl.cpp:204
static const CWE CWE786(786U)
static std::string minmaxCompare(const Token *condTok, nonneg int loopVar, nonneg int assignVar, bool invert=false)
Definition: checkstl.cpp:2722
static const CWE CWE834(834U)
static bool hasVarIds(const Token *tok, nonneg int var1, nonneg int var2)
Definition: checkstl.cpp:2701
static bool isLockGuard(const Variable *var)
Definition: checkstl.cpp:3225
static bool isSameIteratorContainerExpression(const Token *tok1, const Token *tok2, const Settings &settings, ValueFlow::Value::LifetimeKind kind=ValueFlow::Value::LifetimeKind::Iterator)
Definition: checkstl.cpp:706
static bool accumulateBoolLiteral(const Token *tok, nonneg int varid)
Definition: checkstl.cpp:2676
static const Token * getLoopContainer(const Token *tok)
Definition: checkstl.cpp:1046
static const ValueFlow::Value * getOOBIterValue(const Token *tok, const ValueFlow::Value *sizeVal)
Definition: checkstl.cpp:3175
static std::string getContainerName(const Token *containerToken)
Definition: checkstl.cpp:442
static bool addByOne(const Token *tok, nonneg int varid)
Definition: checkstl.cpp:2661
static bool isMutex(const Variable *var)
Definition: checkstl.cpp:3219
static const CWE CWE664(664U)
static const Token * singleAssignInScope(const Token *start, nonneg int varid, bool &input, bool &hasBreak, const Settings &settings)
Definition: checkstl.cpp:2585
static const CWE CWE628(628U)
static bool if_findCompare(const Token *const tokBack, bool stdStringLike)
Definition: checkstl.cpp:1477
static const Token * skipMembers(const Token *tok)
Definition: checkstl.cpp:412
static const ValueFlow::Value * getInnerLifetime(const Token *tok, nonneg int id, ErrorPath *errorPath=nullptr, int depth=4)
Definition: checkstl.cpp:1056
static bool isIterator(const Variable *var, bool &inconclusiveType)
Definition: checkstl.cpp:419
static ValueFlow::Value getLifetimeIteratorValue(const Token *tok, MathLib::bigint path=0)
Definition: checkstl.cpp:728
bool isPointerDeRef(const Token *tok, bool &unknown) const
Is there a pointer dereference? Everything that should result in a nullpointer dereference error mess...
Check STL usage (invalidation of iterators, mismatching containers, etc)
Definition: checkstl.h:45
void outOfBoundsIndexExpression()
Accessing container out of bounds, following index expression.
Definition: checkstl.cpp:320
void missingComparison()
Missing inner comparison, when incrementing iterator inside loop Dangers:
Definition: checkstl.cpp:1860
void erase()
Dangerous usage of erase.
Definition: checkstl.cpp:1379
void missingComparisonError(const Token *incrementToken1, const Token *incrementToken2)
Definition: checkstl.cpp:1924
void sizeError(const Token *tok)
Definition: checkstl.cpp:1807
void uselessCalls()
Check calls that using them is useless
Definition: checkstl.cpp:2226
void checkDereferenceInvalidIterator2()
Definition: checkstl.cpp:2416
void stlBoundariesError(const Token *tok)
Definition: checkstl.cpp:1469
void uselessCallsSubstrError(const Token *tok, SubstrErrorType type)
Definition: checkstl.cpp:2310
void invalidContainerError(const Token *tok, const Token *contTok, const ValueFlow::Value *val, ErrorPath errorPath)
Definition: checkstl.cpp:1229
void mismatchingContainerIteratorError(const Token *containerTok, const Token *iterTok, const Token *containerTok2)
Definition: checkstl.cpp:649
void uselessCallsSwapError(const Token *tok, const std::string &varname)
Definition: checkstl.cpp:2300
void knownEmptyContainerError(const Token *tok, const std::string &algo)
Definition: checkstl.cpp:3074
void size()
Suggest using empty() instead of checking size() against zero for containers.
Definition: checkstl.cpp:1758
void mismatchingContainersError(const Token *tok1, const Token *tok2)
Definition: checkstl.cpp:663
void eraseIteratorOutOfBoundsError(const Token *ftok, const Token *itertok, const ValueFlow::Value *val=nullptr)
Definition: checkstl.cpp:3148
void string_c_strStream(const Token *tok)
Definition: checkstl.cpp:2205
void uselessCallsRemoveError(const Token *tok, const std::string &function)
Definition: checkstl.cpp:2341
void uselessCallsReturnValueError(const Token *tok, const std::string &varname, const std::string &function)
Definition: checkstl.cpp:2287
void sameIteratorExpressionError(const Token *tok)
Definition: checkstl.cpp:684
bool isContainerSize(const Token *containerToken, const Token *expr) const
Definition: checkstl.cpp:280
void stlOutOfBounds()
Finds errors like this: for (unsigned ii = 0; ii <= foo.size(); ++ii)
Definition: checkstl.cpp:1247
void string_c_strParam(const Token *tok, nonneg int number, const std::string &argtype="std::string")
Definition: checkstl.cpp:2176
void dereferenceInvalidIteratorError(const Token *deref, const std::string &iterName)
Definition: checkstl.cpp:2541
void invalidIteratorError(const Token *tok, const std::string &iteratorName)
Definition: checkstl.cpp:358
void negativeIndexError(const Token *tok, const ValueFlow::Value &index)
Definition: checkstl.cpp:1365
void checkMutexes()
Definition: checkstl.cpp:3254
void outOfBounds()
Accessing container out of bounds using ValueFlow.
Definition: checkstl.cpp:133
void mismatchingContainerIterator()
Definition: checkstl.cpp:855
SubstrErrorType
Definition: checkstl.h:227
void invalidContainer()
Definition: checkstl.cpp:1104
void negativeIndex()
negative index for array like containers
Definition: checkstl.cpp:1341
void dereferenceErasedError(const Token *erased, const Token *deref, const std::string &itername, bool inconclusive)
Dereferencing an erased iterator.
Definition: checkstl.cpp:394
void mismatchingContainerExpressionError(const Token *tok1, const Token *tok2)
Definition: checkstl.cpp:675
void if_find()
if (a.find(x)) - possibly incorrect condition
Definition: checkstl.cpp:1498
void stlOutOfBoundsError(const Token *tok, const std::string &num, const std::string &var, bool at)
Definition: checkstl.cpp:1333
void checkFindInsertError(const Token *tok)
Definition: checkstl.cpp:1726
void useStlAlgorithm()
Look for loops that can replaced with std algorithms.
Definition: checkstl.cpp:2873
void invalidContainerReferenceError(const Token *tok, const Token *contTok, ErrorPath errorPath)
Definition: checkstl.cpp:1239
void iterators()
Finds errors like this: for (it = foo.begin(); it != bar.end(); ++it)
Definition: checkstl.cpp:464
void string_c_strThrowError(const Token *tok)
Definition: checkstl.cpp:2158
void useStlAlgorithmError(const Token *tok, const std::string &algoName)
Definition: checkstl.cpp:2550
void outOfBoundsError(const Token *tok, const std::string &containerName, const ValueFlow::Value *containerSize, const std::string &index, const ValueFlow::Value *indexValue)
Definition: checkstl.cpp:221
void stlBoundaries()
bad condition.
Definition: checkstl.cpp:1444
void string_c_str()
Check for common mistakes when using the function string::c_str()
Definition: checkstl.cpp:1956
void mismatchingContainers()
Mismatching containers: std::find(foo.begin(), bar.end(), x)
Definition: checkstl.cpp:795
void knownEmptyContainer()
Definition: checkstl.cpp:3105
void string_c_strConcat(const Token *tok)
Definition: checkstl.cpp:2198
bool isContainerSizeGE(const Token *containerToken, const Token *expr) const
Definition: checkstl.cpp:291
void globalLockGuardError(const Token *tok)
Definition: checkstl.cpp:3240
void checkDereferenceInvalidIterator()
Check for dereferencing an iterator that is invalid
Definition: checkstl.cpp:2352
void iteratorsError(const Token *tok, const std::string &containerName1, const std::string &containerName2)
Definition: checkstl.cpp:363
void redundantCondition()
Check for redundant condition 'if (ints.find(1) != ints.end()) ints.remove(123);'.
Definition: checkstl.cpp:1819
void localMutexError(const Token *tok)
Definition: checkstl.cpp:3247
void eraseCheckLoopVar(const Scope &scope, const Variable *var)
Definition: checkstl.cpp:1400
void redundantIfRemoveError(const Token *tok)
Definition: checkstl.cpp:1852
void eraseIteratorOutOfBounds()
Definition: checkstl.cpp:3193
void uselessCallsConstructorError(const Token *tok)
Definition: checkstl.cpp:2330
void string_c_strError(const Token *tok)
Definition: checkstl.cpp:2164
void string_c_strAssignment(const Token *tok, const std::string &argtype="std::string")
Definition: checkstl.cpp:2191
void string_c_strConstructor(const Token *tok, const std::string &argtype="std::string")
Definition: checkstl.cpp:2184
bool checkIteratorPair(const Token *tok1, const Token *tok2)
Definition: checkstl.cpp:747
void if_findError(const Token *tok, bool str)
Definition: checkstl.cpp:1575
void string_c_strReturn(const Token *tok)
Definition: checkstl.cpp:2170
void invalidContainerLoopError(const Token *tok, const Token *loopTok, ErrorPath errorPath)
Definition: checkstl.cpp:1214
void checkFindInsert()
Definition: checkstl.cpp:1680
void outOfBoundsIndexExpressionError(const Token *tok, const Token *index)
Definition: checkstl.cpp:340
void uselessCallsEmptyError(const Token *tok)
Definition: checkstl.cpp:2336
void reportError(const Token *tok, const Severity severity, const std::string &id, const std::string &msg)
report an error
Definition: check.h:138
const Settings *const mSettings
Definition: check.h:134
ErrorPath getErrorPath(const Token *errtok, const ValueFlow::Value *value, std::string bug) const
Definition: check.cpp:111
const Tokenizer *const mTokenizer
Definition: check.h:133
void logChecker(const char id[])
log checker
Definition: check.cpp:129
const std::string & name() const
class name, used to generate documentation
Definition: check.h:88
nonneg int argCount() const
const Token * tokenDef
function name token in class definition
std::list< Variable > argumentList
argument list, must remain list due to clangimport usage!
bool arrayLike_indexOp
Definition: library.h:239
int type_templateArgNo
Definition: library.h:236
Action getAction(const std::string &function) const
Definition: library.h:248
Yield getYield(const std::string &function) const
Definition: library.h:255
bool stdAssociativeLike
Definition: library.h:241
Library definitions handling.
Definition: library.h:52
const Container * detectIterator(const Token *typeStart) const
Definition: library.cpp:1236
const ArgumentChecks::IteratorInfo * getArgIteratorInfo(const Token *ftok, int argnr) const
Definition: library.h:362
const Container * detectContainer(const Token *typeStart) const
Definition: library.cpp:1231
long long bigint
Definition: mathlib.h:68
std::list< Function > functionList
bool isNestedIn(const Scope *outer) const
ScopeType type
Function * function
function info for this function
bool isLoopScope() const
const Token * classDef
class/struct/union/namespace token
const Token * bodyStart
'{' token
const Token * bodyEnd
'}' token
std::string className
bool isExecutable() const
This is just a container for general settings so that we don't need to pass individual values to func...
Definition: settings.h:95
bool isEnabled(const ValueFlow::Value *value, bool inconclusiveCheck=false) const
Returns true if given value can be shown.
Definition: settings.cpp:274
Library library
Library.
Definition: settings.h:237
bool isPremiumEnabled(const char id[]) const
Is checker id enabled by premiumArgs.
Definition: settings.cpp:608
SimpleEnableGroup< Certainty > certainty
Definition: settings.h:359
SimpleEnableGroup< Severity > severity
Definition: settings.h:358
Standards standards
Struct contains standards settings.
Definition: settings.h:366
bool isEnabled(T flag) const
Definition: settings.h:66
const std::vector< const Variable * > & variableList() const
std::vector< const Scope * > functionScopes
Fast access to function scopes.
std::list< Scope > scopeList
Information about all namespaces/classes/structures.
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
bool hasKnownValue() const
Definition: token.cpp:2528
const ValueFlow::Value * getValue(const MathLib::bigint val) const
Definition: token.cpp:2562
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 isName() const
Definition: token.h:361
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
MathLib::bigint getKnownIntValue() const
Definition: token.h:1218
static std::pair< const Token *, const Token * > typeDecl(const Token *tok, bool pointedToType=false)
Definition: token.cpp:2397
const Token * nextTemplateArgument() const
Definition: token.cpp:896
bool isArithmeticalOp() const
Definition: token.h:395
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
void function(const Function *f)
Associate this token with given function.
Definition: token.cpp:1093
nonneg int varId() const
Definition: token.h:870
std::string expressionString() const
Definition: token.cpp:1647
bool isIncDecOp() const
Definition: token.h:407
const ValueFlow::Value * getValueGE(const MathLib::bigint val, const Settings &settings) const
Definition: token.cpp:1954
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
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
@ eLogicalOp
Definition: token.h:163
Token * previous()
Definition: token.h:862
bool isAssignmentOp() const
Definition: token.h:401
nonneg int linenr() const
Definition: token.h:816
Token * astSibling()
Definition: token.h:1396
void variable(const Variable *v)
Associate this token with given variable.
Definition: token.h:1070
bool isComparisonOp() const
Definition: token.h:398
Token * next()
Definition: token.h:830
const std::list< ValueFlow::Value > & values() const
Definition: token.h:1197
const Token * nextArgument() const
Definition: token.cpp:869
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
const Token * tokens() const
Definition: tokenize.h:592
const SymbolDatabase * getSymbolDatabase() const
Definition: tokenize.h:563
const Function * getFunction(const std::string &funcName) const
bool isSymbolicValue() const
Definition: vfvalue.h:244
Bound bound
The value bound
Definition: vfvalue.h:265
MathLib::bigint path
Path id.
Definition: vfvalue.h:307
bool isIteratorValue() const
Definition: vfvalue.h:235
ErrorPath errorPath
Definition: vfvalue.h:282
bool errorSeverity() const
Definition: vfvalue.h:387
bool isLifetimeValue() const
Definition: vfvalue.h:229
bool isImpossible() const
Definition: vfvalue.h:365
bool isKnown() const
Definition: vfvalue.h:353
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
enum ValueFlow::Value::LifetimeKind lifetimeKind
bool isIteratorStartValue() const
Definition: vfvalue.h:238
bool isIteratorEndValue() const
Definition: vfvalue.h:241
bool isInconclusive() const
Definition: vfvalue.h:378
bool isPossible() const
Definition: vfvalue.h:361
enum ValueType::Type type
const Library::Container * container
If the type is a container defined in a cfg file, this is the used.
bool isIntegral() const
nonneg int pointer
0=>not pointer, 1=>*, 2=>**, 3=>***, etc
Information about a member variable.
bool isArgument() const
Is variable a function argument.
bool isReference() const
Is reference variable.
bool isStlStringViewType() const
std::string getTypeName() const
bool isRValueReference() const
Is reference variable.
bool isStlType() const
Checks if the variable is an STL type ('std::') E.g.
bool isLocal() const
Is variable local.
const Type * type() const
Get Type pointer of known type.
const Scope * scope() const
Get Scope pointer of enclosing scope.
bool isGlobal() const
Is variable global.
const Token * typeEndToken() const
Get type end token.
bool isConst() const
Is variable const.
const Token * nameToken() const
Get name token.
nonneg int declarationId() const
Get declaration ID (varId used for variable in its declaration).
const Token * typeStartToken() const
Get type start token.
bool isPointer() const
Is pointer variable.
bool isStlStringType() const
Checks if the variable is an STL type ('std::') E.g.
bool isStatic() const
Is variable static.
static const std::string emptyString
Definition: config.h:127
#define nonneg
Definition: config.h:138
T * findToken(T *start, const Token *end, const Predicate &pred)
Definition: findtoken.h:67
std::vector< T * > findTokens(T *start, const Token *end, const Predicate &pred)
Definition: findtoken.h:56
Severity
enum class for severity.
Definition: errortypes.h:63
std::pair< const Token *, std::string > ErrorPathItem
Definition: errortypes.h:129
const Library::Container * getLibraryContainer(const Token *tok)
Definition: library.cpp:1731
std::list< ErrorPathItem > ErrorPath
Definition: errortypes.h:130
@ warning
Warning.
@ style
Style warning.
@ performance
Performance warning.
@ error
Programming error.
std::string eitherTheConditionIsRedundant(const Token *condition)
Definition: valueflow.cpp:9680
const Value * findValue(const std::list< Value > &values, const Settings &settings, const std::function< bool(const Value &)> &pred)
std::string lifetimeMessage(const Token *tok, const Value *val, Value::ErrorPath &errorPath)
Definition: valueflow.cpp:3490
std::vector< Value > isOutOfBounds(const Value &size, const Token *indexTok, bool possible=true)
Definition: valueflow.cpp:9757
CPPCHECKLIB std::vector< Value > getLifetimeObjValues(const Token *tok, bool inconclusive=false, MathLib::bigint path=0)
Definition: valueflow.cpp:3528
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
enum Standards::cppstd_t cpp
Reference
bool contains(const Range &r, const T &x)
Definition: utils.h:62