/*

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

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

#include "library.h"

#include "mathlib.h"

#include "refthunk.h"

#include "pathanalysis.h"

#include "settings.h"

#include "standards.h"

#include "symboldatabase.h"

#include "token.h"

#include "tokenize.h"

#include "utils.h"

#include "valueflow.h"

#include "vfvalue.h"

#include "checknullpointer.h"

#include <algorithm>

#include <functional>

#include <initializer_list>

#include <iterator>

#include <list>

#include <map>

#include <set>

#include <sstream>

#include <tuple>

#include <unordered_map>

#include <utility>

#include <vector>

// CWE IDs used:

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

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

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

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

static const CWE CWE667(667U); // Improper Locking

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

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

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

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

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

static const CWE CWE833(833U); // Deadlock

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

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

{

return contains({Library::Container::Yield::ITEM, Library::Container::Yield::AT_INDEX}, yield);

}

static bool containerAppendsElement(const Library::Container* container, const Token* parent)

{

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

const Library::Container::Action action = container->getAction(parent->strAt(1));

if (contains({Library::Container::Action::INSERT,

Library::Container::Action::APPEND,

Library::Container::Action::CHANGE,

Library::Container::Action::CHANGE_INTERNAL,

Library::Container::Action::PUSH,

Library::Container::Action::RESIZE},

action))

return true;

}

return false;

}

static bool containerYieldsElement(const Library::Container* container, const Token* parent)

{

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

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

if (isElementAccessYield(yield))

return true;

}

return false;

}

static bool containerPopsElement(const Library::Container* container, const Token* parent)

{

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

const Library::Container::Action action = container->getAction(parent->strAt(1));

if (contains({ Library::Container::Action::POP }, action))

return true;

}

return false;

}

static const Token* getContainerIndex(const Library::Container* container, const Token* parent)

{

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

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

if (yield == Library::Container::Yield::AT_INDEX && !Token::simpleMatch(parent->tokAt(2), "( )"))

return parent->tokAt(2)->astOperand2();

}

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

return nullptr;

if (Token::simpleMatch(parent, "["))

return parent->astOperand2();

return nullptr;

}

static const Token* getContainerFromSize(const Library::Container* container, const Token* tok)

{

if (!tok)

return nullptr;

if (Token::Match(tok->tokAt(-2), ". %name% (")) {

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

if (yield == Library::Container::Yield::SIZE)

return tok->tokAt(-2)->astOperand1();

}

return nullptr;

}

// A value that out of bounds analysis can use: not impossible, and inconclusive only when enabled

static bool isUsableValue(const ValueFlow::Value& value, const Settings& settings)

{

if (value.isImpossible())

return false;

if (value.isInconclusive() && !settings.certainty.isEnabled(Certainty::inconclusive))

return false;

return true;

}

void CheckStlImpl::outOfBounds()

{

logChecker("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 || container->stdAssociativeLike)

continue;

const Token * parent = astParentSkipParens(tok);

const Token* accessTok = parent;

if (Token::simpleMatch(accessTok, ".") && Token::simpleMatch(accessTok->astParent(), "("))

accessTok = accessTok->astParent();

if (astIsIterator(accessTok) && Token::simpleMatch(accessTok->astParent(), "+"))

accessTok = accessTok->astParent();

const Token* indexTok = getContainerIndex(container, parent);

if (indexTok == tok)

continue;

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

if (!value.isContainerSizeValue())

continue;

if (!isUsableValue(value, mSettings))

continue;

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

continue;

if (value.intvalue == 0 && (indexTok ||

(containerYieldsElement(container, parent) && !containerAppendsElement(container, parent)) ||

containerPopsElement(container, parent))) {

std::string indexExpr;

if (indexTok && !indexTok->hasKnownValue())

indexExpr = indexTok->expressionString();

outOfBoundsError(accessTok, tok->expressionString(), &value, indexExpr, nullptr);

continue;

}

if (indexTok) {

std::vector<ValueFlow::Value> indexValues =

ValueFlow::isOutOfBounds(value, indexTok, mSettings.severity.isEnabled(Severity::warning));

if (!indexValues.empty()) {

outOfBoundsError(

accessTok, tok->expressionString(), &value, indexTok->expressionString(), &indexValues.front());

continue;

}

}

}

if (indexTok && !indexTok->hasKnownIntValue()) {

const ValueFlow::Value* value =

ValueFlow::findValue(indexTok->values(), mSettings, [&](const ValueFlow::Value& v) {

if (!v.isSymbolicValue())

return false;

if (v.isImpossible())

return false;

if (v.intvalue < 0)

return false;

const Token* sizeTok = v.tokvalue;

if (sizeTok && sizeTok->isCast())

sizeTok = sizeTok->astOperand2() ? sizeTok->astOperand2() : sizeTok->astOperand1();

const Token* containerTok = getContainerFromSize(container, sizeTok);

if (!containerTok)

return false;

return containerTok->exprId() == tok->exprId();

});

if (!value)

continue;

outOfBoundsError(accessTok, tok->expressionString(), nullptr, indexTok->expressionString(), value);

}

}

}

}

static std::string indexValueString(const ValueFlow::Value& indexValue, const std::string& containerName = "")

{

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";

std::string indexString = MathLib::toString(indexValue.intvalue);

if (indexValue.isSymbolicValue()) {

indexString = containerName + ".size()";

if (indexValue.intvalue != 0)

indexString += "+" + MathLib::toString(indexValue.intvalue);

}

if (indexValue.bound == ValueFlow::Value::Bound::Lower)

return "greater or equal to " + indexString;

return indexString;

}

void CheckStlImpl::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) {

if (indexValue && indexValue->condition)

errmsg = ValueFlow::eitherTheConditionIsRedundant(indexValue->condition) + " or '" + index +

"' can have the value " + indexValueString(*indexValue, containerName) + ". Expression '" +

expression + "' causes access out of bounds.";

else

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

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

if (containerSize->condition)

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

else if (indexValue == nullptr && !index.empty() && tok->valueType() && tok->valueType()->type == ValueType::ITERATOR)

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 size of '$symbol' can be " + MathLib::toString(containerSize->intvalue) + ". Expression '" + expression + "' causes access out of bounds.";

else if (indexValue->condition)

errmsg = ValueFlow::eitherTheConditionIsRedundant(indexValue->condition) + " or '" + index + "' can have the value " + indexValueString(*indexValue) + ". Expression '" + expression + "' causes 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 = getErrorPath(tok, containerSize, "Access out of bounds");

if (indexValue) {

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

if (errorPathIdx.size() >= errorPath.size())

errorPath = std::move(errorPathIdx);

}

reportError(std::move(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 CheckStlImpl::isContainerSize(const Token *containerToken, const Token *expr) const

{

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

return false;

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

return false;

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

return false;

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

}

bool CheckStlImpl::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->getKnownIntValue() != 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 CheckStlImpl::outOfBoundsIndexExpression()

{

logChecker("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 CheckStlImpl::outOfBoundsIndexExpressionError(const Token *tok, const Token *index)

{

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

const std::string i = index ? index->expressionString() : (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 CheckStlImpl::invalidIteratorError(const Token *tok, const std::string &iteratorName)

{

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

}

void CheckStlImpl::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 CheckStlImpl::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 '$symbol' that are temporaries or defined in different scopes.",

CWE664,

Certainty::normal);

}

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

void CheckStlImpl::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;

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;

}

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 CheckStlImpl::iterators()

{

logChecker("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->strAt(-1) == "*")

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->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 CheckStlImpl::mismatchingContainerIteratorError(const Token* containerTok, const Token* iterTok, const Token* containerTok2)

{

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

const std::string containerTemp(isTemporary(containerTok, &mSettings.library) ? " temporary " : " ");

const std::string container2(containerTok2 ? containerTok2->expressionString() : std::string("v2"));

const std::string containerTemp2(isTemporary(containerTok2, &mSettings.library) ? " temporary " : " ");

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

reportError(containerTok,

Severity::error,

"mismatchingContainerIterator",

"Iterator '" + iter + "' referring to" + containerTemp2 + "container '" + container2 + "' is used with" + containerTemp + "container '" + container + "'.",

CWE664,

Certainty::normal);

}

// Error message for bad iterator usage..

void CheckStlImpl::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 CheckStlImpl::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 CheckStlImpl::sameIteratorExpressionError(const Token *tok)

{

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

}

static std::vector<const Token*> getAddressContainer(const Token* tok)

{

if (Token::simpleMatch(tok, "[") && tok->astOperand1())

return { tok->astOperand1() };

while (Token::simpleMatch(tok, "::") && tok->astOperand2())

tok = tok->astOperand2();

std::vector<ValueFlow::Value> values = ValueFlow::getLifetimeObjValues(tok, /*inconclusive*/ false);

std::vector<const Token*> res;

for (const auto& v : values) {

if (v.tokvalue)

res.emplace_back(v.tokvalue);

}

if (res.empty())

res.emplace_back(tok);

return res;

}

static bool isSameIteratorContainerExpression(const Token* tok1,

const Token* tok2,

const Settings& settings,

ValueFlow::Value::LifetimeKind kind = ValueFlow::Value::LifetimeKind::Iterator)

{

if (isSameExpression(false, tok1, tok2, settings, false, false)) {

return !astIsContainerOwned(tok1) || !isTemporary(tok1, &settings.library);

}

if (astContainerYield(tok2, settings.library) == Library::Container::Yield::ITEM)

return true;

if (kind == ValueFlow::Value::LifetimeKind::Address || kind == ValueFlow::Value::LifetimeKind::Iterator) {

const auto address1 = getAddressContainer(tok1);

const auto address2 = getAddressContainer(tok2);

return std::any_of(address1.begin(), address1.end(), [&](const Token* tok1) {

return std::any_of(address2.begin(), address2.end(), [&](const Token* tok2) {

return isSameExpression(false, tok1, tok2, settings, false, false);

});

});

}

return false;

}

// First it groups the lifetimes together using std::partition with the lifetimes that refer to the same token or token of a subexpression.

// Then it finds the lifetime in that group that refers to the "highest" parent using std::min_element and adds that to the vector.

static std::vector<ValueFlow::Value> pruneLifetimes(std::vector<ValueFlow::Value> lifetimes)

{

std::vector<ValueFlow::Value> result;

auto start = lifetimes.begin();

while (start != lifetimes.end())

{

const Token* tok1 = start->tokvalue;

auto it = std::partition(start, lifetimes.end(), [&](const ValueFlow::Value& v) {

const Token* tok2 = v.tokvalue;

return start->lifetimeKind == v.lifetimeKind && (astHasToken(tok1, tok2) || astHasToken(tok2, tok1));

});

auto root = std::min_element(start, it, [](const ValueFlow::Value& x, const ValueFlow::Value& y) {

return x.tokvalue != y.tokvalue && astHasToken(x.tokvalue, y.tokvalue);

});

result.push_back(*root);

start = it;

}

return result;

}

static ValueFlow::Value getLifetimeIteratorValue(const Token* tok, MathLib::bigint path = 0)

{

auto findIterVal = [](const std::vector<ValueFlow::Value>& values, const std::vector<ValueFlow::Value>::const_iterator beg) {

return std::find_if(beg, values.cend(), [](const ValueFlow::Value& v) {

return v.lifetimeKind == ValueFlow::Value::LifetimeKind::Iterator;

});

};

std::vector<ValueFlow::Value> values = pruneLifetimes(ValueFlow::getLifetimeObjValues(tok, false, path));

auto it = findIterVal(values, values.begin());

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

auto it2 = findIterVal(values, it + 1);

if (it2 == values.cend())

return *it;

}

if (values.size() == 1)

return values.front();

return ValueFlow::Value{};

}

// Whether a container size value found on an iterator token belongs to the range of the given

// iterator value. Both values record the container they belong to when it is known.

static bool sizeValueAppliesToIterator(const ValueFlow::Value& sizeValue, const ValueFlow::Value& iterValue)

{

if (!sizeValue.container || !iterValue.container)

return true; // the container of the size or of the iterator is not known

return iterValue.container == sizeValue.container ||

(iterValue.container->exprId() != 0 && iterValue.container->exprId() == sizeValue.container->exprId());

}

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

{

if (!tok1)

return false;

if (!tok2)

return false;

ValueFlow::Value val1 = getLifetimeIteratorValue(tok1);

ValueFlow::Value val2 = getLifetimeIteratorValue(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 (isSameIteratorContainerExpression(val1.tokvalue, val2.tokvalue, mSettings, val1.lifetimeKind))

return false;

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

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

else

mismatchingContainersError(val1.tokvalue, val2.tokvalue);

return true;

}

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

if (astIsIntegral(tok1, true) || astIsIntegral(tok2, true) ||

astIsFloat(tok1, true) || astIsFloat(tok2, true))

return false;

}

const Token* iter1 = getIteratorExpression(tok1);

if (!iter1)

return false;

const Token* iter2 = getIteratorExpression(tok2);

if (!iter2)

return false;

if (!isSameIteratorContainerExpression(iter1, iter2, mSettings)) {

mismatchingContainerExpressionError(iter1, iter2);

return true;

}

return false;

}

namespace {

struct ArgIteratorInfo {

const Token* tok;

const Library::ArgumentChecks::IteratorInfo* info;

};

}

void CheckStlImpl::mismatchingContainers()

{

logChecker("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 (size_t 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].emplace_back(ArgIteratorInfo{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(false, iter1.tok, iter2.tok, mSettings, 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), "%name% . begin|cbegin|rbegin|crbegin ( ) , %name% . end|cend|rend|crend ( ) ,|)")) {

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

mismatchingContainersError(var->nameToken(), var->nameToken()->tokAt(2));

}

}

}

}

void CheckStlImpl::mismatchingContainerIterator()

{

logChecker("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 (!astIsLHS(tok))

continue;

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

continue;

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

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

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

const Library::Container::Action action = c->getAction(ftok->str());

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 = getLifetimeIteratorValue(iterTok);

if (!val.tokvalue)

continue;

if (!val.isKnown() && Token::simpleMatch(val.tokvalue->astParent(), ":"))

continue;

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

continue;

if (iterTok->str() == "*" && iterTok->astOperand1()->valueType() && iterTok->astOperand1()->valueType()->type == ValueType::ITERATOR)

continue;

if (isSameIteratorContainerExpression(tok, val.tokvalue, mSettings))

continue;

mismatchingContainerIteratorError(tok, iterTok, val.tokvalue);

}

}

}

static const Token* getInvalidMethod(const Token* tok)

{

if (!astIsLHS(tok))

return nullptr;

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

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

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

return tok->astParent();

const Token* ftok = nullptr;

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

ftok = tok->astParent()->next();

if (!ftok)

return nullptr;

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

const Library::Container::Action action = c->getAction(ftok->str());

if (c->unstableErase) {

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

return ftok;

}

if (c->unstableInsert) {

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

return ftok;

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

return ftok;

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

return ftok;

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

return ftok;

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

return ftok;

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

return ftok;

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

return ftok;

if (Token::Match(ftok, "insert|emplace"))

return ftok;

}

}

return nullptr;

}

namespace {

struct InvalidContainerAnalyzer {

struct Info {

struct Reference {

const Token* tok;

ErrorPath errorPath;

const Token* ftok;

};

std::unordered_map<int, Reference> expressions;

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

for (const Reference& r : refs) {

add(r);

}

}

void add(const Reference& r) {

if (!r.tok)

return;

expressions.emplace(r.tok->exprId(), r);

}

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

std::vector<Reference> result;

std::transform(expressions.cbegin(), expressions.cend(), std::back_inserter(result), SelectMapValues{});

return result;

}

};