/*

* Cppcheck - A tool for static C/C++ code analysis

* Copyright (C) 2007-2016 Cppcheck team.

*

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

#include "checkstl.h"

#include "checknullpointer.h"

#include "errorlogger.h"

#include "settings.h"

#include "standards.h"

#include "symboldatabase.h"

#include "token.h"

#include "utils.h"

#include <cstddef>

#include <list>

#include <set>

#include <sstream>

#include <utility>

// Register this check class (by creating a static instance of it)

namespace {

CheckStl instance;

}

// CWE IDs used:

static const struct CWE CWE398(398U); // Indicator of Poor Code Quality

static const struct CWE CWE597(597U); // Use of Wrong Operator in String Comparison

static const struct CWE CWE628(628U); // Function Call with Incorrectly Specified Arguments

static const struct CWE CWE664(664U); // Improper Control of a Resource Through its Lifetime

static const struct CWE CWE704(704U); // Incorrect Type Conversion or Cast

static const struct CWE CWE762(762U); // Mismatched Memory Management Routines

static const struct CWE CWE786(786U); // Access of Memory Location Before Start of Buffer

static const struct CWE CWE788(788U); // Access of Memory Location After End of Buffer

static const struct CWE CWE825(825U); // Expired Pointer Dereference

static const struct CWE CWE834(834U); // Excessive Iteration

// Error message for bad iterator usage..

void CheckStl::invalidIteratorError(const Token *tok, const std::string &iteratorName)

{

reportError(tok, Severity::error, "invalidIterator1", "Invalid iterator: " + iteratorName, CWE664, false);

}

void CheckStl::iteratorsError(const Token *tok, const std::string &container1, const std::string &container2)

{

reportError(tok, Severity::error, "iterators", "Same iterator is used with different containers '" + container1 + "' and '" + container2 + "'.", CWE664, false);

}

// Error message used when dereferencing an iterator that has been erased..

void CheckStl::dereferenceErasedError(const Token *erased, const Token* deref, const std::string &itername)

{

if (erased) {

std::list<const Token*> callstack;

callstack.push_back(deref);

callstack.push_back(erased);

reportError(callstack, Severity::error, "eraseDereference",

"Iterator '" + itername + "' used after element has been erased.\n"

"The iterator '" + itername + "' is invalid after the element it pointed to has been erased. "

"Dereferencing or comparing it with another iterator is invalid operation.", CWE664, false);

} else {

reportError(deref, Severity::error, "eraseDereference",

"Invalid iterator '" + itername + "' used.\n"

"The iterator '" + itername + "' is invalid before being assigned. "

"Dereferencing or comparing it with another iterator is invalid operation.", CWE664, false);

}

}

static const Token *skipMembers(const Token *tok)

{

while (Token::Match(tok, "%name% ."))

tok = tok->tokAt(2);

return tok;

}

static bool isIterator(const Variable *var)

{

// Check that its an iterator

if (!var || !var->isLocal() || !Token::Match(var->typeEndToken(), "iterator|const_iterator|reverse_iterator|const_reverse_iterator|auto"))

return false;

if (var->typeEndToken()->str() == "auto")

return (var->nameToken()->valueType() && var->nameToken()->valueType()->type == ValueType::Type::ITERATOR);

if (var->type()) { // If it is defined, ensure that it is defined like an iterator

// look for operator* and operator++

const Function* end = var->type()->getFunction("operator*");

const Function* incOperator = var->type()->getFunction("operator++");

if (!end || end->argCount() > 0 || !incOperator)

return false;

}

return true;

}

void CheckStl::iterators()

{

const SymbolDatabase *symbolDatabase = _tokenizer->getSymbolDatabase();

for (unsigned int iteratorId = 1; iteratorId < symbolDatabase->getVariableListSize(); iteratorId++) {

const Variable* var = symbolDatabase->getVariableFromVarId(iteratorId);

if (!isIterator(var))

continue;

// the validIterator flag says if the iterator has a valid value or not

bool validIterator = Token::Match(var->nameToken()->next(), "[(=:]");

const Scope* invalidationScope = nullptr;

// The container this iterator can be used with

const Variable* container = nullptr;

const Scope* containerAssignScope = nullptr;

// When "validatingToken" is reached the validIterator is set to true

const Token* validatingToken = nullptr;

const Token* eraseToken = nullptr;

// Scan through the rest of the code and see if the iterator is

// used against other containers.

for (const Token *tok2 = var->nameToken(); tok2 && tok2 != var->scope()->classEnd; tok2 = tok2->next()) {

if (invalidationScope && tok2 == invalidationScope->classEnd)

validIterator = true; // Assume that the iterator becomes valid again

if (containerAssignScope && tok2 == containerAssignScope->classEnd)

container = nullptr; // We don't know which containers might be used with the iterator

if (tok2 == validatingToken) {

validIterator = true;

eraseToken = nullptr;

invalidationScope = nullptr;

}

// Is iterator compared against different container?

if (tok2->isComparisonOp() && container && tok2->astOperand1() && tok2->astOperand2()) {

const Token *other = nullptr;

if (tok2->astOperand1()->varId() == iteratorId)

other = tok2->astOperand2()->tokAt(-3);

else if (tok2->astOperand2()->varId() == iteratorId)

other = tok2->astOperand1()->tokAt(-3);

if (Token::Match(other, "%name% . end|rend|cend|crend ( )") && other->varId() != container->declarationId())

iteratorsError(tok2, container->name(), other->str());

}

// Is the iterator used in a insert/erase operation?

else if (Token::Match(tok2, "%name% . insert|erase ( *| %varid% )|,", iteratorId)) {

const Token* itTok = tok2->tokAt(4);

if (itTok->str() == "*") {

if (tok2->strAt(2) == "insert")

continue;

itTok = itTok->next();

}

// It is bad to insert/erase an invalid iterator

if (!validIterator)

invalidIteratorError(tok2, itTok->str());

// If insert/erase is used on different container then

// report an error

if (container && tok2->varId() != container->declarationId()) {

// skip error message if container is a set..

const Variable *variableInfo = tok2->variable();

const Token *decltok = variableInfo ? variableInfo->typeStartToken() : nullptr;

if (Token::simpleMatch(decltok, "std :: set"))

continue; // No warning

// skip error message if the iterator is erased/inserted by value

if (itTok->previous()->str() == "*")

continue;

// inserting iterator range..

if (tok2->strAt(2) == "insert") {

const Token *par2 = itTok->nextArgument();

if (!par2 || par2->nextArgument())

continue;

while (par2->str() != ")") {

if (par2->varId() == container->declarationId())

break;

if (isIterator(par2->variable()))

break; // TODO: check if iterator points at same container

if (par2->str() == "(")

par2 = par2->link();

par2 = par2->next();

}

if (par2->str() != ")")

continue;

}

// Show error message, mismatching iterator is used.

iteratorsError(tok2, container->name(), tok2->str());

}

// invalidate the iterator if it is erased

else if (tok2->strAt(2) == "erase" && (tok2->strAt(4) != "*" || (container && tok2->varId() == container->declarationId()))) {

validIterator = false;

eraseToken = tok2;

invalidationScope = tok2->scope();

}

// skip the operation

tok2 = itTok->next();

}

// it = foo.erase(..

// taking the result of an erase is ok

else if (Token::Match(tok2, "%varid% = %name% .", iteratorId) &&

Token::simpleMatch(skipMembers(tok2->tokAt(2)), "erase (")) {

// the returned iterator is valid

validatingToken = tok2->linkAt(5);

tok2 = tok2->tokAt(5);

}

// Reassign the iterator

else if (Token::Match(tok2, "%varid% = %name% . begin|rbegin|cbegin|crbegin|find (", iteratorId)) {

validatingToken = tok2->linkAt(5);

container = tok2->tokAt(2)->variable();

containerAssignScope = tok2->scope();

// skip ahead

tok2 = tok2->tokAt(5);

}

// Reassign the iterator

else if (Token::Match(tok2, "%varid% =", iteratorId)) {

// Assume that the iterator becomes valid.

// TODO: add checking that checks if the iterator becomes valid or not

validatingToken = Token::findmatch(tok2->tokAt(2), "[;)]");

// skip ahead

tok2 = tok2->tokAt(2);

}

// Passing iterator to function. Iterator might be initialized

else if (Token::Match(tok2, "%varid% ,|)", iteratorId)) {

validIterator = true;

}

// Dereferencing invalid iterator?

else if (!validIterator && Token::Match(tok2, "* %varid%", iteratorId)) {

dereferenceErasedError(eraseToken, tok2, tok2->strAt(1));

tok2 = tok2->next();

} else if (!validIterator && Token::Match(tok2, "%varid% . %name%", iteratorId)) {

dereferenceErasedError(eraseToken, tok2, tok2->str());

tok2 = tok2->tokAt(2);

}

// bailout handling. Assume that the iterator becomes valid if we see return/break.

// TODO: better handling

else if (tok2->scope() == invalidationScope && Token::Match(tok2, "return|break|continue")) {

validatingToken = Token::findsimplematch(tok2->next(), ";");

}

// bailout handling. Assume that the iterator becomes valid if we see else.

// TODO: better handling

else if (tok2->str() == "else") {

validIterator = true;

}

}

}

}

// Error message for bad iterator usage..

void CheckStl::mismatchingContainersError(const Token *tok)

{

reportError(tok, Severity::error, "mismatchingContainers", "Iterators of different containers are used together.", CWE664, false);

}

static const std::set<std::string> algorithm2 = make_container< std::set<std::string> >() // func(begin1, end1

<< "binary_search" << "copy" << "copy_if" << "equal_range"

<< "generate" << "is_heap" << "is_heap_until" << "is_partitioned"

<< "is_permutation" << "is_sorted" << "is_sorted_until" << "lower_bound" << "make_heap" << "max_element" << "minmax_element"

<< "min_element" << "mismatch" << "move" << "move_backward" << "next_permutation" << "partition" << "partition_copy"

<< "partition_point" << "pop_heap" << "prev_permutation" << "push_heap" << "random_shuffle" << "remove" << "remove_copy"

<< "remove_copy_if" << "remove_if" << "replace" << "replace_copy" << "replace_copy_if" << "replace_if" << "reverse" << "reverse_copy"

<< "shuffle" << "sort" << "sort_heap" << "stable_partition" << "stable_sort" << "swap_ranges" << "transform" << "unique"

<< "unique_copy" << "upper_bound" << "string" << "wstring" << "u16string" << "u32string";

static const std::set<std::string> algorithm22 = make_container< std::set<std::string> >() // func(begin1 << end1 << begin2 << end2

<< "includes" << "lexicographical_compare" << "merge" << "partial_sort_copy"

<< "set_difference" << "set_intersection" << "set_symmetric_difference" << "set_union";

static const std::set<std::string> algorithm1x1 = make_container< std::set<std::string> >() // func(begin1 << x << end1

<< "nth_element" << "partial_sort" << "rotate" << "rotate_copy";

static const std::string iteratorBeginFuncPattern = "begin|cbegin|rbegin|crbegin";

static const std::string iteratorEndFuncPattern = "end|cend|rend|crend";

static const std::string pattern1x1_1 = "%name% . " + iteratorBeginFuncPattern + " ( ) , ";

static const std::string pattern1x1_2 = "%name% . " + iteratorEndFuncPattern + " ( ) ,|)";

static const std::string pattern2 = pattern1x1_1 + pattern1x1_2;

static const Variable *getContainer(const Token *argtok)

{

while (argtok && argtok->astOperand1())

argtok = argtok->astOperand1();

if (!Token::Match(argtok, "%var% . begin|end|rbegin|rend ( )")) // TODO: use Library yield

return nullptr;

const Variable *var = argtok->variable();

if (var && Token::simpleMatch(var->typeStartToken(), "std ::"))

return var;

return nullptr;

}

void CheckStl::mismatchingContainers()

{

// Check if different containers are used in various calls of standard functions

const SymbolDatabase *symbolDatabase = _tokenizer->getSymbolDatabase();

const std::size_t functions = symbolDatabase->functionScopes.size();

for (std::size_t ii = 0; ii < functions; ++ii) {

const Scope * scope = symbolDatabase->functionScopes[ii];

for (const Token* tok = scope->classStart->next(); tok != scope->classEnd; tok = tok->next()) {

if (!Token::Match(tok, "%name% ( !!)"))

continue;

const Token * const ftok = tok;

const Token * const arg1 = tok->tokAt(2);

int argnr = 1;

std::map<const Variable *, unsigned int> containerNr;

for (const Token *argTok = arg1; argTok; argTok = argTok->nextArgument()) {

const Library::ArgumentChecks::IteratorInfo *i = _settings->library.getArgIteratorInfo(ftok,argnr++);

if (!i)

continue;

const Variable *c = getContainer(argTok);

if (!c)

continue;

std::map<const Variable *, unsigned int>::const_iterator it = containerNr.find(c);

if (it == containerNr.end()) {

for (it = containerNr.begin(); it != containerNr.end(); ++it) {

if (it->second == i->container) {

mismatchingContainersError(argTok);

break;

}

}

containerNr[c] = i->container;

} else if (it->second != i->container) {

mismatchingContainersError(argTok);

}

}

int ret = _settings->library.returnValueContainer(ftok);

if (ret != -1 && Token::Match(ftok->next()->astParent(), "==|!=")) {

const Token *parent = ftok->next()->astParent();

const Token *other = (parent->astOperand1() == ftok->next()) ? parent->astOperand2() : parent->astOperand1();

const Variable *c = getContainer(other);

if (c) {

std::map<const Variable *, unsigned int>::const_iterator it = containerNr.find(c);

if (it == containerNr.end() || it->second != ret)

mismatchingContainersError(other);

}

}

}

}

for (unsigned int varid = 0; varid < symbolDatabase->getVariableListSize(); varid++) {

const Variable* var = symbolDatabase->getVariableFromVarId(varid);

if (var && var->isStlStringType() && Token::Match(var->nameToken(), "%var% (") && Token::Match(var->nameToken()->tokAt(2), pattern2.c_str())) {

if (var->nameToken()->strAt(2) != var->nameToken()->strAt(8)) {

mismatchingContainersError(var->nameToken());

}

}

}

}

void CheckStl::stlOutOfBounds()

{

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

// Scan through all scopes..

for (std::list<Scope>::const_iterator i = symbolDatabase->scopeList.begin(); i != symbolDatabase->scopeList.end(); ++i) {

const Token* tok = i->classDef;

// only interested in conditions

if ((i->type != Scope::eFor && i->type != Scope::eWhile && i->type != Scope::eIf && i->type != Scope::eDo) || !tok)

continue;

if (i->type == Scope::eFor)

tok = Token::findsimplematch(tok->tokAt(2), ";");

else if (i->type == Scope::eDo) {

tok = tok->linkAt(1)->tokAt(2);

} else

tok = tok->next();

if (!tok)

continue;

tok = tok->next();

// check if the for loop condition is wrong

if (!Token::Match(tok, "%var% <= %var% . %name% ( ) ;|)|%oror%"))

continue;

// Is it a vector?

const Variable *var = tok->tokAt(2)->variable();

if (!var)

continue;

const Library::Container* container = _settings->library.detectContainer(var->typeStartToken());

if (!container)

continue;

if (container->getYield(tok->strAt(4)) != Library::Container::SIZE)

continue;

// variable id for loop variable.

const unsigned int numId = tok->varId();

// variable id for the container variable

const unsigned int declarationId = var->declarationId();

for (const Token *tok3 = i->classStart; tok3 && tok3 != i->classEnd; tok3 = tok3->next()) {

if (tok3->varId() == declarationId) {

tok3 = tok3->next();

if (Token::Match(tok3, ". %name% ( )")) {

if (container->getYield(tok3->strAt(1)) == Library::Container::SIZE)

break;

} else if (container->arrayLike_indexOp && Token::Match(tok3, "[ %varid% ]", numId))

stlOutOfBoundsError(tok3, tok3->strAt(1), var->name(), false);

else if (Token::Match(tok3, ". %name% ( %varid% )", numId)) {

Library::Container::Yield yield = container->getYield(tok3->strAt(1));

if (yield == Library::Container::AT_INDEX)

stlOutOfBoundsError(tok3, tok3->strAt(3), var->name(), true);

}

}

}

}

}

void CheckStl::stlOutOfBoundsError(const Token *tok, const std::string &num, const std::string &var, bool at)

{

if (at)

reportError(tok, Severity::error, "stlOutOfBounds", "When " + num + "==" + var + ".size(), " + var + ".at(" + num + ") is out of bounds.", CWE788, false);

else

reportError(tok, Severity::error, "stlOutOfBounds", "When " + num + "==" + var + ".size(), " + var + "[" + num + "] is out of bounds.", CWE788, false);

}

void CheckStl::negativeIndex()

{

// Negative index is out of bounds..

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

const std::size_t functions = symbolDatabase->functionScopes.size();

for (std::size_t ii = 0; ii < functions; ++ii) {

const Scope * scope = symbolDatabase->functionScopes[ii];

for (const Token* tok = scope->classStart->next(); tok != scope->classEnd; tok = tok->next()) {

if (!Token::Match(tok, "%var% [") || WRONG_DATA(!tok->next()->astOperand2(), tok))

continue;

const Variable * const var = tok->variable();

if (!var || tok == var->nameToken())

continue;

const Library::Container * const container = _settings->library.detectContainer(var->typeStartToken());

if (!container || !container->arrayLike_indexOp)

continue;

const ValueFlow::Value *index = tok->next()->astOperand2()->getValueLE(-1, _settings);

if (!index)

continue;

negativeIndexError(tok, *index);

}

}

}

void CheckStl::negativeIndexError(const Token *tok, const ValueFlow::Value &index)

{

const ErrorPath errorPath = getErrorPath(tok, &index, "Negative array index");

std::ostringstream errmsg;

if (index.condition)

errmsg << ValueFlow::eitherTheConditionIsRedundant(index.condition)

<< ", otherwise there is negative array index " << index.intvalue << ".";

else

errmsg << "Array index " << index.intvalue << " is out of bounds.";

reportError(errorPath, index.errorSeverity() ? Severity::error : Severity::warning, "negativeContainerIndex", errmsg.str(), CWE786, index.isInconclusive());

}

void CheckStl::erase()

{

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

for (std::list<Scope>::const_iterator i = symbolDatabase->scopeList.begin(); i != symbolDatabase->scopeList.end(); ++i) {

if (i->type == Scope::eFor && Token::simpleMatch(i->classDef, "for (")) {

const Token *tok = i->classDef->linkAt(1);

if (!Token::Match(tok->tokAt(-3), "; ++| %var% ++| ) {"))

continue;

tok = tok->previous();

if (!tok->isName())

tok = tok->previous();

eraseCheckLoopVar(*i, tok->variable());

} else if (i->type == Scope::eWhile && Token::Match(i->classDef, "while ( %var% !=")) {

eraseCheckLoopVar(*i, i->classDef->tokAt(2)->variable());

}

}

}

void CheckStl::eraseCheckLoopVar(const Scope &scope, const Variable *var)

{

if (!var || !Token::simpleMatch(var->typeEndToken(), "iterator"))

return;

for (const Token *tok = scope.classStart; tok != scope.classEnd; tok = tok->next()) {

if (tok->str() != "(")

continue;

if (!Token::Match(tok->tokAt(-2), ". erase ( ++| %varid% )", var->declarationId()))

continue;

if (Token::simpleMatch(tok->astParent(), "="))

continue;

// Iterator is invalid..

unsigned int indentlevel = 0U;

const Token *tok2 = tok->link();

for (; tok2 != scope.classEnd; tok2 = tok2->next()) {

if (tok2->str() == "{") {

++indentlevel;

continue;

}

if (tok2->str() == "}") {

if (indentlevel > 0U)

--indentlevel;

else if (Token::simpleMatch(tok2, "} else {"))

tok2 = tok2->linkAt(2);

continue;

}

if (tok2->varId() == var->declarationId()) {

if (Token::simpleMatch(tok2->next(), "="))

break;

dereferenceErasedError(tok, tok2, tok2->str());

break;

}

if (indentlevel == 0U && Token::Match(tok2, "break|return|goto"))

break;

}

if (tok2 == scope.classEnd)

dereferenceErasedError(tok, scope.classDef, var->nameToken()->str());

}

}

void CheckStl::pushback()

{

// Pointer can become invalid after push_back, push_front, reserve or resize..

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

const std::size_t functions = symbolDatabase->functionScopes.size();

for (std::size_t i = 0; i < functions; ++i) {

const Scope * scope = symbolDatabase->functionScopes[i];

for (const Token* tok = scope->classStart->next(); tok != scope->classEnd; tok = tok->next()) {

if (Token::Match(tok, "%var% = & %var% [")) {

// Skip it directly if it is a pointer or an array

const Token* containerTok = tok->tokAt(3);

if (containerTok->variable() && containerTok->variable()->isArrayOrPointer())

continue;

// Variable id for pointer

const unsigned int pointerId(tok->varId());

bool invalidPointer = false;

const Token* function = nullptr;

const Token* end2 = tok->scope()->classEnd;

for (const Token *tok2 = tok; tok2 != end2; tok2 = tok2->next()) {

// push_back on vector..

if (Token::Match(tok2, "%varid% . push_front|push_back|insert|reserve|resize|clear", containerTok->varId())) {

invalidPointer = true;

function = tok2->tokAt(2);

}

// Using invalid pointer..

if (invalidPointer && tok2->varId() == pointerId) {

bool unknown = false;

if (CheckNullPointer::isPointerDeRef(tok2, unknown))

invalidPointerError(tok2, function->str(), tok2->str());

break;

}

}

}

}

}

// Iterator becomes invalid after reserve, resize, insert, push_back or push_front..

for (unsigned int iteratorId = 1; iteratorId < symbolDatabase->getVariableListSize(); iteratorId++) {

const Variable* var = symbolDatabase->getVariableFromVarId(iteratorId);

// Check that its an iterator

if (!var || !var->isLocal() || !Token::Match(var->typeEndToken(), "iterator|const_iterator|reverse_iterator|const_reverse_iterator"))

continue;

// ... on std::vector

if (!Token::Match(var->typeStartToken(), "std| ::| vector <"))

continue;

// the variable id for the vector

unsigned int vectorid = 0;

const Token* validatingToken = nullptr;

std::string invalidIterator;

const Token* end2 = var->scope()->classEnd;

for (const Token *tok2 = var->nameToken(); tok2 != end2; tok2 = tok2->next()) {

if (validatingToken == tok2) {

invalidIterator.clear();

validatingToken = nullptr;

}

// Using push_back or push_front inside a loop..

if (Token::simpleMatch(tok2, "for (")) {

tok2 = tok2->tokAt(2);

}

if (Token::Match(tok2, "%varid% = %var% . begin|rbegin|cbegin|crbegin ( ) ; %varid% != %var% . end|rend|cend|crend ( ) ; ++| %varid% ++| ) {", iteratorId)) {

// variable id for the loop iterator

const unsigned int varId(tok2->tokAt(2)->varId());

const Token *pushbackTok = nullptr;

// Count { and } for tok3

const Token *tok3 = tok2->tokAt(20);

for (const Token* const end3 = tok3->linkAt(-1); tok3 != end3; tok3 = tok3->next()) {

if (tok3->str() == "break" || tok3->str() == "return") {

pushbackTok = nullptr;

break;

} else if (Token::Match(tok3, "%varid% . push_front|push_back|insert|reserve|resize|clear|erase (", varId) && !tok3->previous()->isAssignmentOp()) {

if (tok3->strAt(2) != "erase" || (tok3->tokAt(4)->varId() != iteratorId && tok3->tokAt(5)->varId() != iteratorId)) // This case is handled in: CheckStl::iterators()

pushbackTok = tok3->tokAt(2);

}

}

if (pushbackTok)

invalidIteratorError(pushbackTok, pushbackTok->str(), tok2->str());

}

// Assigning iterator..

if (Token::Match(tok2, "%varid% =", iteratorId)) {

if (Token::Match(tok2->tokAt(2), "%var% . begin|end|rbegin|rend|cbegin|cend|crbegin|crend|insert|erase|find (")) {

if (!invalidIterator.empty() && Token::Match(tok2->tokAt(4), "insert|erase ( *| %varid% )|,", iteratorId)) {

invalidIteratorError(tok2, invalidIterator, var->name());

break;

}

vectorid = tok2->tokAt(2)->varId();

tok2 = tok2->linkAt(5);

} else {

vectorid = 0;

}

invalidIterator.clear();

}

// push_back on vector..

if (vectorid > 0 && Token::Match(tok2, "%varid% . push_front|push_back|insert|reserve|resize|clear|erase (", vectorid)) {

if (!invalidIterator.empty() && Token::Match(tok2->tokAt(2), "insert|erase ( *| %varid% ,|)", iteratorId)) {

invalidIteratorError(tok2, invalidIterator, var->name());

break;

}

if (tok2->strAt(2) != "erase" || (tok2->tokAt(4)->varId() != iteratorId && tok2->tokAt(5)->varId() != iteratorId)) // This case is handled in: CheckStl::iterators()

invalidIterator = tok2->strAt(2);

tok2 = tok2->linkAt(3);

}

else if (tok2->str() == "return" || tok2->str() == "throw")

validatingToken = Token::findsimplematch(tok2->next(), ";");

// TODO: instead of bail out for 'else' try to check all execution paths.

else if (tok2->str() == "break" || tok2->str() == "else")

invalidIterator.clear();

// Using invalid iterator..

if (!invalidIterator.empty()) {

if (Token::Match(tok2, "++|--|*|+|-|(|,|=|!= %varid%", iteratorId))

invalidIteratorError(tok2, invalidIterator, tok2->strAt(1));

if (Token::Match(tok2, "%varid% ++|--|+|-|.", iteratorId))

invalidIteratorError(tok2, invalidIterator, tok2->str());

}

}

}

}

// Error message for bad iterator usage..

void CheckStl::invalidIteratorError(const Token *tok, const std::string &func, const std::string &iterator_name)

{

reportError(tok, Severity::error, "invalidIterator2", "After " + func + "(), the iterator '" + iterator_name + "' may be invalid.", CWE664, false);

}

// Error message for bad iterator usage..

void CheckStl::invalidPointerError(const Token *tok, const std::string &func, const std::string &pointer_name)

{

reportError(tok, Severity::error, "invalidPointer", "Invalid pointer '" + pointer_name + "' after " + func + "().", CWE664, false);

}

void CheckStl::stlBoundaries()

{

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

for (unsigned int iteratorId = 1; iteratorId < symbolDatabase->getVariableListSize(); iteratorId++) {

const Variable* var = symbolDatabase->getVariableFromVarId(iteratorId);

if (!var || !var->scope() || !var->scope()->isExecutable())

continue;

const Library::Container* container = _settings->library.detectContainer(var->typeStartToken(), true);

if (!container || container->opLessAllowed)

continue;

const Token* const end = var->scope()->classEnd;

for (const Token *tok = var->nameToken(); tok != end; tok = tok->next()) {

if (Token::Match(tok, "!!* %varid% <", var->declarationId())) {

stlBoundariesError(tok);

} else if (Token::Match(tok, "> %varid% !!.", var->declarationId())) {

stlBoundariesError(tok);

}

}

}

}

// Error message for bad boundary usage..

void CheckStl::stlBoundariesError(const Token *tok)

{

reportError(tok, Severity::error, "stlBoundaries",

"Dangerous comparison using operator< on iterator.\n"

"Iterator compared with operator<. This is dangerous since the order of items in the "

"container is not guaranteed. One should use operator!= instead to compare iterators.", CWE664, false);

}

static bool if_findCompare(const Token * const tokBack)

{

const Token *tok = tokBack->astParent();

if (!tok)

return true;

if (tok->isComparisonOp())

return (!tok->astOperand1()->isNumber() && !tok->astOperand2()->isNumber());

if (tok->isArithmeticalOp()) // result is used in some calculation

return true; // TODO: check if there is a comparison of the result somewhere

if (tok->str() == ".")

return true; // Dereferencing is OK, the programmer might know that the element exists - TODO: An inconclusive warning might be appropriate

if (tok->isAssignmentOp())

return if_findCompare(tok); // Go one step upwards in the AST

return false;

}

void CheckStl::if_find()

{

const bool printWarning = _settings->isEnabled(Settings::WARNING);

const bool printPerformance = _settings->isEnabled(Settings::PERFORMANCE);

if (!printWarning && !printPerformance)

return;

const SymbolDatabase *symbolDatabase = _tokenizer->getSymbolDatabase();

for (std::list<Scope>::const_iterator i = symbolDatabase->scopeList.begin(); i != symbolDatabase->scopeList.end(); ++i) {

if ((i->type != Scope::eIf && i->type != Scope::eWhile) || !i->classDef)

continue;

for (const Token *tok = i->classDef->next(); tok->str() != "{"; tok = tok->next()) {

const Token* funcTok = nullptr;

const Library::Container* container = nullptr;

if (Token::Match(tok, "%name% ("))

tok = tok->linkAt(1);

else if (tok->variable() && Token::Match(tok, "%var% . %name% (")) {

container = _settings->library.detectContainer(tok->variable()->typeStartToken());

funcTok = tok->tokAt(2);

}

// check also for vector-like or pointer containers

else if (tok->variable() && tok->astParent() && (tok->astParent()->str() == "*" || tok->astParent()->str() == "[")) {

const Token *tok2 = tok->astParent();

if (!Token::Match(tok2->astParent(), ". %name% ("))

continue;

funcTok = tok2->astParent()->next();

if (tok->variable()->isArrayOrPointer())

container = _settings->library.detectContainer(tok->variable()->typeStartToken());

else { // Container of container - find the inner container

container = _settings->library.detectContainer(tok->variable()->typeStartToken()); // outer container

tok2 = Token::findsimplematch(tok->variable()->typeStartToken(), "<", tok->variable()->typeEndToken());

if (container && container->type_templateArgNo >= 0 && tok2) {

tok2 = tok2->next();

for (int j = 0; j < container->type_templateArgNo; j++)

tok2 = tok2->nextTemplateArgument();

container = _settings->library.detectContainer(tok2); // innner container

} else

container = nullptr;

}

}

if (container && container->getAction(funcTok->str()) == Library::Container::FIND) {

if (if_findCompare(funcTok->next()))

continue;

if (printWarning && container->getYield(funcTok->str()) == Library::Container::ITERATOR)

if_findError(tok, false);

else if (printPerformance && container->stdStringLike && funcTok->str() == "find")

if_findError(tok, true);

} else if (printWarning && Token::Match(tok, "std :: find|find_if (")) {

// check that result is checked properly

if (!if_findCompare(tok->tokAt(3))) {

if_findError(tok, false);

}

}

}

}

}

void CheckStl::if_findError(const Token *tok, bool str)

{

if (str)

reportError(tok, Severity::performance, "stlIfStrFind",

"Inefficient usage of string::find() in condition; string::compare() would be faster.\n"

"Either inefficient or wrong usage of string::find(). string::compare() will be faster if "

"string::find's result is compared with 0, because it will not scan the whole "

"string. If your intention is to check that there are no findings in the string, "

"you should compare with std::string::npos.", CWE597, false);

else

reportError(tok, Severity::warning, "stlIfFind", "Suspicious condition. The result of find() is an iterator, but it is not properly checked.", CWE398, false);

}

/**

* Is container.size() slow?

*/

static bool isCpp03ContainerSizeSlow(const Token *tok)

{

if (!tok)

return false;

const Variable* var = tok->variable();

return var && var->isStlType("list");

}

void CheckStl::size()

{

if (!_settings->isEnabled(Settings::PERFORMANCE))

return;

if (_settings->standards.cpp == Standards::CPP11)

return;

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

const std::size_t functions = symbolDatabase->functionScopes.size();

for (std::size_t i = 0; i < functions; ++i) {

const Scope * scope = symbolDatabase->functionScopes[i];

for (const Token* tok = scope->classStart->next(); tok != scope->classEnd; tok = tok->next()) {

if (Token::Match(tok, "%var% . size ( )") ||

Token::Match(tok, "%name% . %var% . size ( )")) {

// get the variable

const Token *varTok = tok;

if (tok->strAt(2) != "size")

varTok = varTok->tokAt(2);

const Token* const end = varTok->tokAt(5);

// check for comparison to zero

if ((tok->previous() && !tok->previous()->isArithmeticalOp() && Token::Match(end, "==|<=|!=|> 0")) ||

(end->next() && !end->next()->isArithmeticalOp() && Token::Match(tok->tokAt(-2), "0 ==|>=|!=|<"))) {

if (isCpp03ContainerSizeSlow(varTok)) {

sizeError(varTok);

continue;

}

}

// check for comparison to one

if ((tok->previous() && !tok->previous()->isArithmeticalOp() && Token::Match(end, ">=|< 1") && !end->tokAt(2)->isArithmeticalOp()) ||

(end->next() && !end->next()->isArithmeticalOp() && Token::Match(tok->tokAt(-2), "1 <=|>") && !tok->tokAt(-3)->isArithmeticalOp())) {

if (isCpp03ContainerSizeSlow(varTok))

sizeError(varTok);

}

// check for using as boolean expression

else if ((Token::Match(tok->tokAt(-2), "if|while (") && end->str() == ")") ||

(tok->previous()->tokType() == Token::eLogicalOp && Token::Match(end, "&&|)|,|;|%oror%"))) {

if (isCpp03ContainerSizeSlow(varTok))

sizeError(varTok);

}

}

}

}

}

void CheckStl::sizeError(const Token *tok)

{

const std::string varname = tok ? tok->str() : std::string("list");

reportError(tok, Severity::performance, "stlSize",

"Possible inefficient checking for '" + varname + "' emptiness.\n"

"Checking for '" + varname + "' emptiness might be inefficient. "

"Using " + varname + ".empty() instead of " + varname + ".size() can be faster. " +

varname + ".size() can take linear time but " + varname + ".empty() is "

"guaranteed to take constant time.", CWE398, false);

}

void CheckStl::redundantCondition()

{

if (!_settings->isEnabled(Settings::STYLE))

return;

const SymbolDatabase *symbolDatabase = _tokenizer->getSymbolDatabase();

for (std::list<Scope>::const_iterator i = symbolDatabase->scopeList.begin(); i != symbolDatabase->scopeList.end(); ++i) {

if (i->type != Scope::eIf)

continue;

const Token* tok = i->classDef->tokAt(2);

if (!Token::Match(tok, "%name% . find ( %any% ) != %name% . end|rend|cend|crend ( ) ) { %name% . remove|erase ( %any% ) ;"))

continue;

// Get tokens for the fields %name% and %any%

const Token *var1 = tok;

const Token *any1 = var1->tokAt(4);

const Token *var2 = any1->tokAt(3);

const Token *var3 = var2->tokAt(7);

const Token *any2 = var3->tokAt(4);

// Check if all the "%name%" fields are the same and if all the "%any%" are the same..

if (var1->str() == var2->str() &&

var2->str() == var3->str() &&

any1->str() == any2->str()) {

redundantIfRemoveError(tok);

}

}

}

void CheckStl::redundantIfRemoveError(const Token *tok)

{

reportError(tok, Severity::style, "redundantIfRemove",

"Redundant checking of STL container element existence before removing it.\n"

"Redundant checking of STL container element existence before removing it. "

"It is safe to call the remove method on a non-existing element.", CWE398, false);

}

void CheckStl::missingComparison()

{

if (!_settings->isEnabled(Settings::WARNING))

return;

const SymbolDatabase* const symbolDatabase = _tokenizer->getSymbolDatabase();

for (std::list<Scope>::const_iterator i = symbolDatabase->scopeList.begin(); i != symbolDatabase->scopeList.end(); ++i) {

if (i->type != Scope::eFor || !i->classDef)

continue;

for (const Token *tok2 = i->classDef->tokAt(2); tok2 != i->classStart; tok2 = tok2->next()) {

if (tok2->str() == ";")

break;

if (!Token::Match(tok2, "%var% = %name% . begin|rbegin|cbegin|crbegin ( ) ; %name% != %name% . end|rend|cend|crend ( ) ; ++| %name% ++| ) {"))

continue;

// same container

if (tok2->strAt(2) != tok2->strAt(10))

break;

const unsigned int iteratorId(tok2->varId());

// same iterator

if (iteratorId == tok2->tokAt(10)->varId())

break;

// increment iterator

if (!Token::Match(tok2->tokAt(16), "++ %varid% )", iteratorId) &&

!Token::Match(tok2->tokAt(16), "%varid% ++ )", iteratorId)) {

break;

}

const Token *incrementToken = nullptr;

// Parse loop..

for (const Token *tok3 = i->classStart; tok3 != i->classEnd; tok3 = tok3->next()) {

if (Token::Match(tok3, "%varid% ++", iteratorId))

incrementToken = tok3;

else if (Token::Match(tok3->previous(), "++ %varid% !!.", iteratorId))

incrementToken = tok3;

else if (Token::Match(tok3, "%varid% !=|==", iteratorId))

incrementToken = nullptr;

else if (tok3->str() == "break" || tok3->str() == "return")

incrementToken = nullptr;

else if (Token::Match(tok3, "%varid% = %name% . insert ( ++| %varid% ++| ,", iteratorId)) {

// skip insertion..

tok3 = tok3->linkAt(6);

if (!tok3)

break;

}

}

if (incrementToken)

missingComparisonError(incrementToken, tok2->tokAt(16));

}

}

}

void CheckStl::missingComparisonError(const Token *incrementToken1, const Token *incrementToken2)

{

std::list<const Token*> callstack;

callstack.push_back(incrementToken1);

callstack.push_back(incrementToken2);

std::ostringstream errmsg;

errmsg << "Missing bounds check for extra iterator increment in loop.\n"

<< "The iterator incrementing is suspicious - it is incremented at line ";

if (incrementToken1)