/*

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

* Copyright (C) 2007-2021 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 "astutils.h"

#include "check.h"

#include "checknullpointer.h"

#include "errortypes.h"

#include "library.h"

#include "mathlib.h"

#include "pathanalysis.h"

#include "settings.h"

#include "standards.h"

#include "symboldatabase.h"

#include "token.h"

#include "utils.h"

#include "valueflow.h"

#include <algorithm>

#include <cstddef>

#include <iterator>

#include <list>

#include <map>

#include <set>

#include <sstream>

#include <unordered_map>

#include <unordered_set>

#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 CWE667(667U); // Improper Locking

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 CWE833(833U); // Deadlock

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

static bool isElementAccessYield(const Library::Container::Yield& yield)

{

return yield == Library::Container::Yield::ITEM || yield == Library::Container::Yield::AT_INDEX;

}

void CheckStl::outOfBounds()

{

for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {

for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {

const Library::Container *container = getLibraryContainer(tok);

if (!container)

continue;

const Token * parent = astParentSkipParens(tok);

for (const ValueFlow::Value &value : tok->values()) {

if (!value.isContainerSizeValue())

continue;

if (value.isImpossible())

continue;

if (value.isInconclusive() && !mSettings->certainty.isEnabled(Certainty::inconclusive))

continue;

if (!value.errorSeverity() && !mSettings->severity.isEnabled(Severity::warning))

continue;

if (Token::Match(parent, ". %name% (") && isElementAccessYield(container->getYield(parent->strAt(1)))) {

if (value.intvalue == 0) {

outOfBoundsError(parent->tokAt(2), tok->expressionString(), &value, parent->strAt(1), nullptr);

continue;

}

const Token* indexTok = parent->tokAt(2)->astOperand2();

if (!indexTok)

continue;

const ValueFlow::Value* indexValue = indexTok->getMaxValue(false);

if (indexValue && indexValue->intvalue >= value.intvalue) {

outOfBoundsError(

parent, tok->expressionString(), &value, indexTok->expressionString(), indexValue);

continue;

}

if (mSettings->severity.isEnabled(Severity::warning)) {

indexValue = indexTok->getMaxValue(true);

if (indexValue && indexValue->intvalue >= value.intvalue) {

outOfBoundsError(

parent, tok->expressionString(), &value, indexTok->expressionString(), indexValue);

continue;

}

}

}

if (Token::Match(tok, "%name% . %name% (") && container->getYield(tok->strAt(2)) == Library::Container::Yield::START_ITERATOR) {

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

const Token *other = nullptr;

if (Token::simpleMatch(fparent, "+") && fparent->astOperand1() == tok->tokAt(3))

other = fparent->astOperand2();

else if (Token::simpleMatch(fparent, "+") && fparent->astOperand2() == tok->tokAt(3))

other = fparent->astOperand1();

if (other && other->hasKnownIntValue() && other->getKnownIntValue() > value.intvalue) {

outOfBoundsError(fparent, tok->expressionString(), &value, other->expressionString(), &other->values().back());

continue;

} else if (other && !other->hasKnownIntValue() && value.isKnown() && value.intvalue==0) {

outOfBoundsError(fparent, tok->expressionString(), &value, other->expressionString(), nullptr);

continue;

}

}

if (!container->arrayLike_indexOp && !container->stdStringLike)

continue;

if (value.intvalue == 0 && Token::Match(parent, "[") && tok == parent->astOperand1()) {

outOfBoundsError(parent, tok->expressionString(), &value, "", nullptr);

continue;

}

if (container->arrayLike_indexOp && Token::Match(parent, "[")) {

const ValueFlow::Value *indexValue = parent->astOperand2() ? parent->astOperand2()->getMaxValue(false) : nullptr;

if (indexValue && indexValue->intvalue >= value.intvalue) {

outOfBoundsError(parent, tok->expressionString(), &value, parent->astOperand2()->expressionString(), indexValue);

continue;

}

if (mSettings->severity.isEnabled(Severity::warning)) {

indexValue = parent->astOperand2() ? parent->astOperand2()->getMaxValue(true) : nullptr;

if (indexValue && indexValue->intvalue >= value.intvalue) {

outOfBoundsError(parent, tok->expressionString(), &value, parent->astOperand2()->expressionString(), indexValue);

continue;

}

}

}

}

}

}

}

static std::string indexValueString(const ValueFlow::Value& indexValue)

{

if (indexValue.isIteratorStartValue())

return "at position " + MathLib::toString(indexValue.intvalue) + " from the beginning";

if (indexValue.isIteratorEndValue())

return "at position " + MathLib::toString(-indexValue.intvalue) + " from the end";

return MathLib::toString(indexValue.intvalue);

}

void CheckStl::outOfBoundsError(const Token *tok, const std::string &containerName, const ValueFlow::Value *containerSize, const std::string &index, const ValueFlow::Value *indexValue)

{

// Do not warn if both the container size and index value are possible

if (containerSize && indexValue && containerSize->isPossible() && indexValue->isPossible())

return;

const std::string expression = tok ? tok->expressionString() : (containerName+"[x]");

std::string errmsg;

if (!containerSize)

errmsg = "Out of bounds access in expression '" + expression + "'";

else if (containerSize->intvalue == 0) {

if (containerSize->condition)

errmsg = ValueFlow::eitherTheConditionIsRedundant(containerSize->condition) + " or expression '" + expression + "' cause access out of bounds.";

else if (indexValue == nullptr && !index.empty())

errmsg = "Out of bounds access in expression '" + expression + "' because '$symbol' is empty and '" + index + "' may be non-zero.";

else

errmsg = "Out of bounds access in expression '" + expression + "' because '$symbol' is empty.";

} else if (indexValue) {

if (containerSize->condition)

errmsg = ValueFlow::eitherTheConditionIsRedundant(containerSize->condition) + " or $symbol size can be " + MathLib::toString(containerSize->intvalue) + ". Expression '" + expression + "' cause access out of bounds.";

else if (indexValue->condition)

errmsg = ValueFlow::eitherTheConditionIsRedundant(indexValue->condition) + " or '" + index + "' can have the value " + indexValueString(*indexValue) + ". Expression '" + expression + "' cause access out of bounds.";

else

errmsg = "Out of bounds access in '" + expression + "', if '$symbol' size is " + MathLib::toString(containerSize->intvalue) + " and '" + index + "' is " + indexValueString(*indexValue);

} else {

// should not happen

return;

}

ErrorPath errorPath;

if (!indexValue)

errorPath = getErrorPath(tok, containerSize, "Access out of bounds");

else {

ErrorPath errorPath1 = getErrorPath(tok, containerSize, "Access out of bounds");

ErrorPath errorPath2 = getErrorPath(tok, indexValue, "Access out of bounds");

if (errorPath1.size() <= 1)

errorPath = errorPath2;

else if (errorPath2.size() <= 1)

errorPath = errorPath1;

else {

errorPath = errorPath1;

errorPath.splice(errorPath.end(), errorPath2);

}

}

reportError(errorPath,

(containerSize && !containerSize->errorSeverity()) || (indexValue && !indexValue->errorSeverity()) ? Severity::warning : Severity::error,

"containerOutOfBounds",

"$symbol:" + containerName +"\n" + errmsg,

CWE398,

(containerSize && containerSize->isInconclusive()) || (indexValue && indexValue->isInconclusive()) ? Certainty::inconclusive : Certainty::normal);

}

bool CheckStl::isContainerSize(const Token *containerToken, const Token *expr) const

{

if (!Token::simpleMatch(expr, "( )"))

return false;

if (!Token::Match(expr->astOperand1(), ". %name% ("))

return false;

if (!isSameExpression(mTokenizer->isCPP(), false, containerToken, expr->astOperand1()->astOperand1(), mSettings->library, false, false))

return false;

return containerToken->valueType()->container->getYield(expr->previous()->str()) == Library::Container::Yield::SIZE;

}

bool CheckStl::isContainerSizeGE(const Token * containerToken, const Token *expr) const

{

if (!expr)

return false;

if (isContainerSize(containerToken, expr))

return true;

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

const Token *mul;

if (isContainerSize(containerToken, expr->astOperand1()))

mul = expr->astOperand2();

else if (isContainerSize(containerToken, expr->astOperand2()))

mul = expr->astOperand1();

else

return false;

return mul && (!mul->hasKnownIntValue() || mul->values().front().intvalue != 0);

}

if (expr->str() == "+") {

const Token *op;

if (isContainerSize(containerToken, expr->astOperand1()))

op = expr->astOperand2();

else if (isContainerSize(containerToken, expr->astOperand2()))

op = expr->astOperand1();

else

return false;

return op && op->getValueGE(0, mSettings);

}

return false;

}

void CheckStl::outOfBoundsIndexExpression()

{

for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {

for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {

if (!tok->isName() || !tok->valueType())

continue;

const Library::Container *container = tok->valueType()->container;

if (!container)

continue;

if (!container->arrayLike_indexOp && !container->stdStringLike)

continue;

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

continue;

if (isContainerSizeGE(tok, tok->next()->astOperand2()))

outOfBoundsIndexExpressionError(tok, tok->next()->astOperand2());

}

}

}

void CheckStl::outOfBoundsIndexExpressionError(const Token *tok, const Token *index)

{

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

const std::string i = index ? index->expressionString() : std::string(varname + ".size()");

std::string errmsg = "Out of bounds access of $symbol, index '" + i + "' is out of bounds.";

reportError(tok,

Severity::error,

"containerOutOfBoundsIndexExpression",

"$symbol:" + varname +"\n" + errmsg,

CWE398,

Certainty::normal);

}

// Error message for bad iterator usage..

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

{

reportError(tok, Severity::error, "invalidIterator1", "$symbol:"+iteratorName+"\nInvalid iterator: $symbol", CWE664, Certainty::normal);

}

void CheckStl::iteratorsError(const Token* tok, const std::string& containerName1, const std::string& containerName2)

{

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

"$symbol:" + containerName1 + "\n"

"$symbol:" + containerName2 + "\n"

"Same iterator is used with different containers '" + containerName1 + "' and '" + containerName2 + "'.", CWE664, Certainty::normal);

}

void CheckStl::iteratorsError(const Token* tok, const Token* containerTok, const std::string& containerName1, const std::string& containerName2)

{

std::list<const Token*> callstack = { tok, containerTok };

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

"$symbol:" + containerName1 + "\n"

"$symbol:" + containerName2 + "\n"

"Same iterator is used with different containers '" + containerName1 + "' and '" + containerName2 + "'.", CWE664, Certainty::normal);

}

void CheckStl::iteratorsError(const Token* tok, const Token* containerTok, const std::string& containerName)

{

std::list<const Token*> callstack = { tok, containerTok };

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

"$symbol:" + containerName + "\n"

"Same iterator is used with containers '" + containerName + "' that are defined in different scopes.", CWE664, Certainty::normal);

}

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

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

{

if (erased) {

std::list<const Token*> callstack = { deref, erased };

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

"$symbol:" + itername + "\n"

"Iterator '$symbol' used after element has been erased.\n"

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

"Dereferencing or comparing it with another iterator is invalid operation.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);

} else {

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

"$symbol:" + itername + "\n"

"Invalid iterator '$symbol' used.\n"

"The iterator '$symbol' is invalid before being assigned. "

"Dereferencing or comparing it with another iterator is invalid operation.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);

}

}

static const Token *skipMembers(const Token *tok)

{

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

tok = tok->tokAt(2);

return tok;

}

static bool isIterator(const Variable *var, bool& inconclusiveType)

{

// Check that its an iterator

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

return false;

inconclusiveType = 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;

} else {

inconclusiveType = true; // heuristics only

}

}

return true;

}

static std::string getContainerName(const Token *containerToken)

{

if (!containerToken)

return std::string();

std::string ret(containerToken->str());

for (const Token *nametok = containerToken; nametok; nametok = nametok->tokAt(-2)) {

if (!Token::Match(nametok->tokAt(-2), "%name% ."))

break;

ret = nametok->strAt(-2) + '.' + ret;

}

return ret;

}

enum OperandPosition {

Left,

Right

};

static bool isVector(const Token* tok)

{

if (!tok)

return false;

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

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

return Token::simpleMatch(decltok, "std :: vector");

}

void CheckStl::iterators()

{

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

// Filling map of iterators id and their scope begin

std::map<int, const Token*> iteratorScopeBeginInfo;

for (const Variable* var : symbolDatabase->variableList()) {

bool inconclusiveType=false;

if (!isIterator(var, inconclusiveType))

continue;

const int iteratorId = var->declarationId();

if (iteratorId != 0)

iteratorScopeBeginInfo[iteratorId] = var->nameToken();

}

for (const Variable* var : symbolDatabase->variableList()) {

bool inconclusiveType=false;

if (!isIterator(var, inconclusiveType))

continue;

if (inconclusiveType && !mSettings->certainty.isEnabled(Certainty::inconclusive))

continue;

const int iteratorId = var->declarationId();

// 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 Token* containerToken = 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()->bodyEnd; tok2 = tok2->next()) {

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

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

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

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

if (tok2 == validatingToken) {

validIterator = true;

eraseToken = nullptr;

invalidationScope = nullptr;

}

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

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

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 (containerToken && tok2->varId() != containerToken->varId()) {

// 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() == containerToken->varId())

break;

bool inconclusiveType2=false;

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

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

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

par2 = par2->link();

par2 = par2->next();

}

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

continue;

}

// Not different containers if a reference is used..

if (containerToken && containerToken->variable() && containerToken->variable()->isReference()) {

const Token *nameToken = containerToken->variable()->nameToken();

if (Token::Match(nameToken, "%name% =")) {

const Token *name1 = nameToken->tokAt(2);

const Token *name2 = tok2;

while (Token::Match(name1, "%name%|.|::") && name2 && name1->str() == name2->str()) {

name1 = name1->next();

name2 = name2->next();

}

if (!Token::simpleMatch(name1, ";") || !Token::Match(name2, "[;,()=]"))

continue;

}

}

// Show error message, mismatching iterator is used.

iteratorsError(tok2, getContainerName(containerToken), getContainerName(tok2));

}

// invalidate the iterator if it is erased

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

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 = skipMembers(tok2->tokAt(2))->linkAt(1);

tok2 = validatingToken->link();

}

// Reassign the iterator

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

Token::Match(skipMembers(tok2->tokAt(2)), "begin|rbegin|cbegin|crbegin|find (")) {

validatingToken = skipMembers(tok2->tokAt(2))->linkAt(1);

containerToken = skipMembers(tok2->tokAt(2))->tokAt(-2);

if (containerToken->varId() == 0 || Token::simpleMatch(validatingToken, ") ."))

containerToken = nullptr;

containerAssignScope = tok2->scope();

// skip ahead

tok2 = validatingToken->link();

}

// Reassign the iterator

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

break;

}

// 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), inconclusiveType);

tok2 = tok2->next();

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

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

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;

}

}

}

}

void CheckStl::mismatchingContainerIteratorError(const Token* tok, const Token* iterTok)

{

const std::string container(tok ? tok->expressionString() : std::string("v1"));

const std::string iter(iterTok ? iterTok->expressionString() : std::string("it"));

reportError(tok,

Severity::error,

"mismatchingContainerIterator",

"Iterator '" + iter + "' from different container '" + container + "' are used together.",

CWE664,

Certainty::normal);

}

// Error message for bad iterator usage..

void CheckStl::mismatchingContainersError(const Token* tok1, const Token* tok2)

{

const std::string expr1(tok1 ? tok1->expressionString() : std::string("v1"));

const std::string expr2(tok2 ? tok2->expressionString() : std::string("v2"));

reportError(tok1,

Severity::error,

"mismatchingContainers",

"Iterators of different containers '" + expr1 + "' and '" + expr2 + "' are used together.",

CWE664,

Certainty::normal);

}

void CheckStl::mismatchingContainerExpressionError(const Token *tok1, const Token *tok2)

{

const std::string expr1(tok1 ? tok1->expressionString() : std::string("v1"));

const std::string expr2(tok2 ? tok2->expressionString() : std::string("v2"));

reportError(tok1, Severity::warning, "mismatchingContainerExpression",

"Iterators to containers from different expressions '" +

expr1 + "' and '" + expr2 + "' are used together.", CWE664, Certainty::normal);

}

void CheckStl::sameIteratorExpressionError(const Token *tok)

{

reportError(tok, Severity::style, "sameIteratorExpression", "Same iterators expression are used for algorithm.", CWE664, Certainty::normal);

}

static const std::set<std::string> algorithm2 = { // 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 = { // 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 = { // 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 Token * getIteratorExpression(const Token * tok)

{

if (!tok)

return nullptr;

if (tok->isUnaryOp("*"))

return nullptr;

if (!tok->isName()) {

const Token *iter1 = getIteratorExpression(tok->astOperand1());

if (iter1)

return iter1;

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

return nullptr;

const Token *iter2 = getIteratorExpression(tok->astOperand2());

if (iter2)

return iter2;

} else if (Token::Match(tok, "begin|cbegin|rbegin|crbegin|end|cend|rend|crend (")) {

if (Token::Match(tok->previous(), ". %name% ( ) !!."))

return tok->previous()->astOperand1();

if (!Token::simpleMatch(tok->previous(), ".") && Token::Match(tok, "%name% ( !!)") && !Token::simpleMatch(tok->linkAt(1), ") ."))

return tok->next()->astOperand2();

}

return nullptr;

}

bool CheckStl::checkIteratorPair(const Token* tok1, const Token* tok2)

{

if (!tok1)

return false;

if (!tok2)

return false;

ValueFlow::Value val1 = getLifetimeObjValue(tok1);

ValueFlow::Value val2 = getLifetimeObjValue(tok2);

if (val1.tokvalue && val2.tokvalue && val1.lifetimeKind == val2.lifetimeKind) {

if (val1.lifetimeKind == ValueFlow::Value::LifetimeKind::Lambda)

return false;

if (tok1->astParent() == tok2->astParent() && Token::Match(tok1->astParent(), "%comp%|-")) {

if (val1.lifetimeKind == ValueFlow::Value::LifetimeKind::Address)

return false;

if (val1.lifetimeKind == ValueFlow::Value::LifetimeKind::Object &&

(!astIsContainer(val1.tokvalue) || !astIsContainer(val2.tokvalue)))

return false;

}

if (isSameExpression(true, false, val1.tokvalue, val2.tokvalue, mSettings->library, false, false))

return false;

if (val1.tokvalue->expressionString() == val2.tokvalue->expressionString())

iteratorsError(tok1, val1.tokvalue, val1.tokvalue->expressionString());

else

mismatchingContainersError(val1.tokvalue, val2.tokvalue);

return true;

}

const Token* iter1 = getIteratorExpression(tok1);

const Token* iter2 = getIteratorExpression(tok2);

if (iter1 && iter2 && !isSameExpression(true, false, iter1, iter2, mSettings->library, false, false)) {

mismatchingContainerExpressionError(iter1, iter2);

return true;

}

return false;

}

struct ArgIteratorInfo {

const Token* tok;

const Library::ArgumentChecks::IteratorInfo* info;

};

void CheckStl::mismatchingContainers()

{

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

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

for (const Scope * scope : symbolDatabase->functionScopes) {

for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {

if (Token::Match(tok, "%comp%|-")) {

if (checkIteratorPair(tok->astOperand1(), tok->astOperand2()))

continue;

}

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

continue;

const Token * const ftok = tok;

const std::vector<const Token *> args = getArguments(ftok);

if (args.size() < 2)

continue;

// Group args together by container

std::map<int, std::vector<ArgIteratorInfo>> containers;

for (int argnr = 1; argnr <= args.size(); ++argnr) {

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

if (!i)

continue;

const Token * const argTok = args[argnr - 1];

containers[i->container].push_back({argTok, i});

}

// Lambda is used to escape the nested loops

[&] {

for (const auto& p : containers)

{

const std::vector<ArgIteratorInfo>& cargs = p.second;

for (ArgIteratorInfo iter1 : cargs) {

for (ArgIteratorInfo iter2 : cargs) {

if (iter1.tok == iter2.tok)

continue;

if (iter1.info->first && iter2.info->last &&

isSameExpression(true, false, iter1.tok, iter2.tok, mSettings->library, false, false))

sameIteratorExpressionError(iter1.tok);

if (checkIteratorPair(iter1.tok, iter2.tok))

return;

}

}

}

}();

}

}

for (const Variable *var : symbolDatabase->variableList()) {

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(), var->nameToken()->tokAt(2));

}

}

}

}

void CheckStl::mismatchingContainerIterator()

{

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

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

for (const Scope * scope : symbolDatabase->functionScopes) {

for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {

if (!astIsContainer(tok))

continue;

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

continue;

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

const std::vector<const Token *> args = getArguments(ftok);

const Library::Container * c = tok->valueType()->container;

Library::Container::Action action = c->getAction(tok->strAt(2));

const Token* iterTok = nullptr;

if (action == Library::Container::Action::INSERT && args.size() == 2) {

// Skip if iterator pair

if (astIsIterator(args.back()))

continue;

if (!astIsIterator(args.front()))

continue;

iterTok = args.front();

} else if (action == Library::Container::Action::ERASE) {

if (!astIsIterator(args.front()))

continue;

iterTok = args.front();

} else {

continue;

}

ValueFlow::Value val = getLifetimeObjValue(iterTok);

if (!val.tokvalue)

continue;

if (val.lifetimeKind != ValueFlow::Value::LifetimeKind::Iterator)

continue;

for (const LifetimeToken& lt:getLifetimeTokens(tok)) {

if (lt.inconclusive)

continue;

const Token* contTok = lt.token;

if (isSameExpression(true, false, contTok, val.tokvalue, mSettings->library, false, false))

continue;

mismatchingContainerIteratorError(tok, iterTok);

}

}

}

}

static bool isInvalidMethod(const Token * tok)

{

if (Token::Match(tok->next(), ". assign|clear|swap"))

return true;

if (Token::Match(tok->next(), "%assign%"))

return true;

if (const Library::Container * c = tok->valueType()->container) {

Library::Container::Action action = c->getAction(tok->strAt(2));

if (c->unstableErase) {

if (action == Library::Container::Action::ERASE)

return true;

}

if (c->unstableInsert) {

if (action == Library::Container::Action::RESIZE)

return true;

if (action == Library::Container::Action::CLEAR)

return true;

if (action == Library::Container::Action::PUSH)

return true;

if (action == Library::Container::Action::POP)

return true;

if (action == Library::Container::Action::INSERT)

return true;

if (action == Library::Container::Action::CHANGE)

return true;

if (action == Library::Container::Action::CHANGE_INTERNAL)

return true;

if (Token::Match(tok->next(), ". insert|emplace"))

return true;

}

}

return false;

}

struct InvalidContainerAnalyzer {

struct Info {

struct Reference {

const Token* tok;

ErrorPath errorPath;

};

std::unordered_map<int, Reference> expressions;

ErrorPath errorPath;

void add(const std::vector<Reference>& refs) {

for (const Reference& r : refs) {

add(r);

}

}

void add(const Reference& r) {

if (!r.tok)

return;

expressions.insert(std::make_pair(r.tok->exprId(), r));

}

std::vector<Reference> invalidTokens() const {

std::vector<Reference> result;

std::transform(expressions.begin(), expressions.end(), std::back_inserter(result), SelectMapValues{});

return result;

}

};

std::unordered_map<const Function*, Info> invalidMethods;

std::vector<Info::Reference> invalidatesContainer(const Token* tok) const {

std::vector<Info::Reference> result;

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

const Function* f = tok->function();

if (!f)

return result;

ErrorPathItem epi = std::make_pair(tok, "Calling function " + tok->str());

const bool dependsOnThis = exprDependsOnThis(tok->next());

auto it = invalidMethods.find(f);

if (it != invalidMethods.end()) {

std::vector<Info::Reference> refs = it->second.invalidTokens();

std::copy_if(refs.begin(), refs.end(), std::back_inserter(result), [&](const Info::Reference& r) {

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

if (!var)

return false;

if (dependsOnThis && !var->isLocal() && !var->isGlobal() && !var->isStatic())

return true;

if (!var->isArgument())

return false;

if (!var->isReference())

return false;

return true;

});

std::vector<const Token*> args = getArguments(tok);

for (Info::Reference& r : result) {

r.errorPath.push_front(epi);

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

if (!var)

continue;

if (var->isArgument()) {

int n = getArgumentPos(var, f);

const Token* tok2 = nullptr;

if (n >= 0 && n < args.size())

tok2 = args[n];

r.tok = tok2;

}

}

}

} else if (astIsContainer(tok)) {

if (isInvalidMethod(tok)) {

ErrorPath ep;

ep.emplace_front(tok,

"After calling '" + tok->strAt(2) +

"', iterators or references to the container's data may be invalid .");

result.push_back(Info::Reference{tok, ep});

}

}

return result;

}

void analyze(const SymbolDatabase* symboldatabase) {

for (const Scope* scope : symboldatabase->functionScopes) {

const Function* f = scope->function;

if (!f)

continue;

for (const Token* tok = scope->bodyStart; tok != scope->bodyEnd; tok = tok->next()) {

if (Token::Match(tok, "if|while|for|goto|return"))

break;

std::vector<Info::Reference> c = invalidatesContainer(tok);

if (c.empty())

continue;

invalidMethods[f].add(c);

}

}

}

};

static bool isVariableDecl(const Token* tok)

{

if (!tok)

return false;

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

if (!var)

return false;

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

return true;

if (Token::Match(var->declEndToken(), "; %var%") && var->declEndToken()->next() == tok)

return true;

return false;

}

void CheckStl::invalidContainer()

{

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

const Library& library = mSettings->library;

InvalidContainerAnalyzer analyzer;

analyzer.analyze(symbolDatabase);

for (const Scope * scope : symbolDatabase->functionScopes) {

for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {

for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok)) {

if (!astIsContainer(r.tok))

continue;

std::set<nonneg int> skipVarIds;

// Skip if the variable is assigned to

const Token* assignExpr = tok;

while (assignExpr->astParent()) {

bool isRHS = astIsRHS(assignExpr);

assignExpr = assignExpr->astParent();

if (Token::Match(assignExpr, "%assign%")) {

if (!isRHS)

assignExpr = nullptr;

break;

}

}

if (Token::Match(assignExpr, "%assign%") && Token::Match(assignExpr->astOperand1(), "%var%"))

skipVarIds.insert(assignExpr->astOperand1()->varId());

const Token* endToken = nextAfterAstRightmostLeaf(tok->next()->astParent());

if (!endToken)

endToken = tok->next();

const ValueFlow::Value* v = nullptr;

ErrorPath errorPath;

PathAnalysis::Info info =

PathAnalysis{endToken, library} .forwardFind([&](const PathAnalysis::Info& info) {

if (!info.tok->variable())

return false;

if (info.tok->varId() == 0)

return false;

if (skipVarIds.count(info.tok->varId()) > 0)

return false;

// if (Token::simpleMatch(info.tok->next(), "."))

// return false;

if (Token::Match(info.tok->astParent(), "%assign%") && astIsLHS(info.tok))

skipVarIds.insert(info.tok->varId());

if (info.tok->variable()->isReference() && !isVariableDecl(info.tok) &&

reaches(info.tok->variable()->nameToken(), tok, library, nullptr)) {