/*
* 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 .
*/
#include "checkstl.h"
#include "astutils.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 "tokenize.h"
#include "utils.h"
#include "valueflow.h"
#include "vfvalue.h"
#include "checknullpointer.h"
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// 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 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;
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() 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 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 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 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 getAddressContainer(const Token* tok)
{
if (Token::simpleMatch(tok, "[") && tok->astOperand1())
return { tok->astOperand1() };
while (Token::simpleMatch(tok, "::") && tok->astOperand2())
tok = tok->astOperand2();
std::vector values = ValueFlow::getLifetimeObjValues(tok, /*inconclusive*/ false);
std::vector 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 pruneLifetimes(std::vector lifetimes)
{
std::vector 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& values, const std::vector::const_iterator beg) {
return std::find_if(beg, values.cend(), [](const ValueFlow::Value& v) {
return v.lifetimeKind == ValueFlow::Value::LifetimeKind::Iterator;
});
};
std::vector 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 args = getArguments(ftok);
if (args.size() < 2)
continue;
// Group args together by container
std::map containers;
for (size_t argnr = 1; argnr container].emplace_back(ArgIteratorInfo{argTok, i});
}
// Lambda is used to escape the nested loops
[&] {
for (const auto& p : containers)
{
const std::vector& 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 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 expressions;
void add(const std::vector& 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 invalidTokens() const {
std::vector result;
std::transform(expressions.cbegin(), expressions.cend(), std::back_inserter(result), SelectMapValues{});
return result;
}
};
std::unordered_map invalidMethods;
std::vector invalidatesContainer(const Token* tok) const {
std::vector 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 refs = it->second.invalidTokens();
std::copy_if(refs.cbegin(), refs.cend(), 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 args = getArguments(tok);
for (Info::Reference& r : result) {
r.errorPath.push_front(epi);
r.ftok = tok;
const Variable* var = r.tok->variable();
if (!var)
continue;
if (var->isArgument()) {
const 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)) {
const Token* ftok = getInvalidMethod(tok);
if (ftok) {
ErrorPath ep;
ep.emplace_front(ftok,
"After calling '" + ftok->expressionString() +
"', iterators or references to the container's data may be invalid .");
result.emplace_back(Info::Reference{tok, std::move(ep), ftok});
}
}
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 c = invalidatesContainer(tok);
if (c.empty())
continue;
invalidMethods[f].add(c);
}
}
}
};
}
static const Token* getLoopContainer(const Token* tok)
{
if (!Token::simpleMatch(tok, "for ("))
return nullptr;
const Token* sepTok = tok->next()->astOperand2();
if (!Token::simpleMatch(sepTok, ":"))
return nullptr;
return sepTok->astOperand2();
}
static const ValueFlow::Value* getInnerLifetime(const Token* tok,
nonneg int id,
ErrorPath* errorPath = nullptr,
int depth = 4)
{
if (depth < 0)
return nullptr;
if (!tok)
return nullptr;
for (const ValueFlow::Value& val : tok->values()) {
if (!val.isLocalLifetimeValue())
continue;
if (contains({ValueFlow::Value::LifetimeKind::Address,
ValueFlow::Value::LifetimeKind::SubObject,
ValueFlow::Value::LifetimeKind::Lambda},
val.lifetimeKind)) {
if (val.isInconclusive())
return nullptr;
if (val.capturetok)
if (const ValueFlow::Value* v = getInnerLifetime(val.capturetok, id, errorPath, depth - 1))
return v;
if (errorPath)
errorPath->insert(errorPath->end(), val.errorPath.cbegin(), val.errorPath.cend());
if (const ValueFlow::Value* v = getInnerLifetime(val.tokvalue, id, errorPath, depth - 1))
return v;
continue;
}
if (!val.tokvalue->variable())
continue;
if (val.tokvalue->varId() != id)
continue;
return &val;
}
return nullptr;
}
static const Token* endOfExpression(const Token* tok)
{
if (!tok)
return nullptr;
const Token* parent = tok->astParent();
while (Token::simpleMatch(parent, "."))
parent = parent->astParent();
if (!parent)
return tok->next();
const Token* endToken = nextAfterAstRightmostLeaf(parent);
if (!endToken)
return parent->next();
return endToken;
}
void CheckStlImpl::invalidContainer()
{
logChecker("CheckStl::invalidContainer");
const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
InvalidContainerAnalyzer analyzer;
analyzer.analyze(symbolDatabase);
for (const Scope * scope : symbolDatabase->functionScopes) {
for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
if (const Token* contTok = getLoopContainer(tok)) {
const Token* blockStart = tok->linkAt(1)->next();
const Token* blockEnd = blockStart->link();
if (contTok->exprId() == 0)
continue;
if (!astIsContainer(contTok))
continue;
for (const Token* tok2 = blockStart; tok2 != blockEnd; tok2 = tok2->next()) {
bool bail = false;
for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok2)) {
if (!astIsContainer(r.tok))
continue;
if (r.tok->exprId() != contTok->exprId())
continue;
const Scope* s = tok2->scope();
if (!s)
continue;
if (isReturnScope(s->bodyEnd, mSettings.library))
continue;
invalidContainerLoopError(r.ftok, tok, r.errorPath);
bail = true;
break;
}
if (bail)
break;
}
} else {
for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok)) {
if (!astIsContainer(r.tok))
continue;
std::set skipVarIds;
// Skip if the variable is assigned to
const Token* assignExpr = tok;
while (assignExpr->astParent()) {
const 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 = endOfExpression(tok);
const ValueFlow::Value* v = nullptr;
ErrorPath errorPath;
PathAnalysis::Info info =
PathAnalysis{endToken}.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, nullptr)) {
if ((assignExpr && Token::Match(assignExpr->astOperand1()->previous(), "& %varid%", info.tok->varId()))) {
return false;
}
ErrorPath ep;
bool addressOf = false;
const Variable* var = ValueFlow::getLifetimeVariable(info.tok, ep, mSettings, &addressOf);
// Check the reference is created before the change
if (var && var->declarationId() == r.tok->varId() && !addressOf) {
// An argument always reaches
if (var->isArgument() ||
(!var->isReference() && !var->isRValueReference() && !isVariableDecl(tok) &&
reaches(var->nameToken(), tok, &ep))) {
errorPath = std::move(ep);
return true;
}
}
}
ErrorPath ep;
const ValueFlow::Value* val = getInnerLifetime(info.tok, r.tok->varId(), &ep);
// Check the iterator is created before the change
if (val && val->tokvalue != tok && reaches(val->tokvalue, tok, &ep)) {
v = val;
errorPath = std::move(ep);
return true;
}
return false;
});
if (!info.tok)
continue;
errorPath.insert(errorPath.end(), info.errorPath.cbegin(), info.errorPath.cend());
errorPath.insert(errorPath.end(), r.errorPath.cbegin(), r.errorPath.cend());
if (v) {
invalidContainerError(info.tok, v, std::move(errorPath));
} else {
invalidContainerReferenceError(info.tok, r.tok, std::move(errorPath));
}
}
}
}
}
}
void CheckStlImpl::invalidContainerLoopError(const Token* tok, const Token* loopTok, ErrorPath errorPath)
{
const std::string method = tok ? tok->str() : "erase";
errorPath.emplace_back(loopTok, "Iterating container here.");
// Remove duplicate entries from error path
errorPath.remove_if([&](const ErrorPathItem& epi) {
return epi.first == tok;
});
const std::string msg = "Calling '" + method + "' while iterating the container is invalid.";
errorPath.emplace_back(tok, "");
reportError(std::move(errorPath), Severity::error, "invalidContainerLoop", msg, CWE664, Certainty::normal);
}
void CheckStlImpl::invalidContainerError(const Token *tok, const ValueFlow::Value *val, ErrorPath errorPath)
{
const bool inconclusive = val ? val->isInconclusive() : false;
if (val)
errorPath.insert(errorPath.begin(), val->errorPath.cbegin(), val->errorPath.cend());
std::string msg = "Using " + lifetimeMessage(tok, val, errorPath);
errorPath.emplace_back(tok, "");
reportError(std::move(errorPath), Severity::error, "invalidContainer", msg + " that may be invalid.", CWE664, inconclusive ? Certainty::inconclusive : Certainty::normal);
}
void CheckStlImpl::invalidContainerReferenceError(const Token* tok, const Token* contTok, ErrorPath errorPath)
{
std::string name = contTok ? contTok->expressionString() : "x";
std::string msg = "Reference to " + name;
errorPath.emplace_back(tok, "");
reportError(std::move(errorPath), Severity::error, "invalidContainerReference", msg + " that may be invalid.", CWE664, Certainty::normal);
}
void CheckStlImpl::stlOutOfBounds()
{
logChecker("CheckStl::stlOutOfBounds");
const SymbolDatabase* const symbolDatabase = mTokenizer->getSymbolDatabase();
// Scan through all scopes..
for (const Scope &scope : symbolDatabase->scopeList) {
const Token* tok = scope.classDef;
// only interested in conditions
if ((!scope.isLoopScope() && scope.type != ScopeType::eIf) || !tok)
continue;
const Token *condition = nullptr;
if (scope.type == ScopeType::eFor) {
if (Token::simpleMatch(tok->next()->astOperand2(), ";") && Token::simpleMatch(tok->next()->astOperand2()->astOperand2(), ";"))
condition = tok->next()->astOperand2()->astOperand2()->astOperand1();
} else if (Token::simpleMatch(tok, "do {") && Token::simpleMatch(tok->linkAt(1), "} while ("))
condition = tok->linkAt(1)->tokAt(2)->astOperand2();
else
condition = tok->next()->astOperand2();
if (!condition)
continue;
std::vector conds;
visitAstNodes(condition,
[&](const Token *cond) {
if (Token::Match(cond, "%oror%|&&"))
return ChildrenToVisit::op1_and_op2;
if (cond->isComparisonOp())
conds.emplace_back(cond);
return ChildrenToVisit::none;
});
for (const Token *cond : conds) {
const Token *vartok;
const Token *containerToken;
// check in the ast that cond is of the form "%var% %varid% !!.", var->declarationId())) {
stlBoundariesError(tok);
}
}
}
}
// Error message for bad boundary usage..
void CheckStlImpl::stlBoundariesError(const Token *tok)
{
reportError(tok, Severity::error, "stlBoundaries",
"Dangerous comparison using operator< on iterator.\n"
"Iterator compared with operatorstrAt(1));
}
}
void CheckStlImpl::checkDereferenceInvalidIterator2()
{
logChecker("CheckStl::checkDereferenceInvalidIterator2");
for (const Token *tok = mTokenizer->tokens(); tok; tok = tok->next()) {
if (Token::Match(tok, "sizeof|decltype|typeid|typeof (")) {
tok = tok->linkAt(1);
continue;
}
if (Token::Match(tok, "%assign%"))
continue;
std::vector contValues;
std::copy_if(tok->values().cbegin(),
tok->values().cend(),
std::back_inserter(contValues),
[&](const ValueFlow::Value& value) {
return isUsableValue(value, mSettings) && value.isContainerSizeValue();
});
// Can iterator point to END or before START?
for (const ValueFlow::Value& value:tok->values()) {
if (!isUsableValue(value, mSettings))
continue;
if (!value.isIteratorValue())
continue;
bool isInvalidIterator = false;
const ValueFlow::Value* cValue = nullptr;
if (value.isIteratorEndValue() && value.intvalue >= 0) {
isInvalidIterator = value.intvalue > 0;
} else if (value.isIteratorStartValue() && value.intvalue < 0) {
isInvalidIterator = true;
} else {
auto it = std::find_if(contValues.cbegin(), contValues.cend(), [&](const ValueFlow::Value& c) {
if (value.path != c.path)
return false;
if (!sizeValueAppliesToIterator(c, value))
return false;
if (value.isIteratorStartValue() && value.intvalue >= c.intvalue)
return true;
if (value.isIteratorEndValue() && -value.intvalue > c.intvalue)
return true;
return false;
});
if (it == contValues.end())
continue;
cValue = &*it;
if (value.isIteratorStartValue() && value.intvalue > cValue->intvalue)
isInvalidIterator = true;
}
bool inconclusive = false;
bool unknown = false;
const Token* emptyAdvance = nullptr;
const Token* advanceIndex = nullptr;
if (cValue && cValue->intvalue == 0) {
if (Token::Match(tok->astParent(), "+|-") && astIsIntegral(tok->astSibling(), false)) {
if (tok->astSibling() && tok->astSibling()->hasKnownIntValue()) {
if (tok->astSibling()->getKnownIntValue() == 0)
continue;
} else {
advanceIndex = tok->astSibling();
}
emptyAdvance = tok->astParent();
} else if (Token::Match(tok->astParent(), "++|--")) {
emptyAdvance = tok->astParent();
}
}
if (!CheckNullPointerImpl::isPointerDeRef(tok, unknown, mSettings.library) && !isInvalidIterator && !emptyAdvance) {
if (!unknown)
continue;
inconclusive = true;
}
if (cValue) {
const ValueFlow::Value& lValue = getLifetimeIteratorValue(tok, cValue->path);
if (!lValue.isLifetimeValue())
continue;
if (emptyAdvance)
outOfBoundsError(emptyAdvance,
lValue.tokvalue->expressionString(),
cValue,
advanceIndex ? advanceIndex->expressionString() : "",
nullptr);
else
outOfBoundsError(tok, lValue.tokvalue->expressionString(), cValue, tok->expressionString(), &value);
} else {
dereferenceInvalidIteratorError(tok, &value, inconclusive);
}
}
}
}
void CheckStlImpl::dereferenceInvalidIteratorError(const Token* tok, const ValueFlow::Value *value, bool inconclusive)
{
const std::string& varname = tok ? tok->expressionString() : "var";
const std::string errmsgcond("$symbol:" + varname + '\n' + ValueFlow::eitherTheConditionIsRedundant(value ? value->condition : nullptr) + " or there is possible dereference of an invalid iterator: $symbol.");
if (!tok || !value) {
reportError(tok, Severity::error, "derefInvalidIterator", "Dereference of an invalid iterator", CWE825, Certainty::normal);
reportError(tok, Severity::warning, "derefInvalidIteratorRedundantCheck", errmsgcond, CWE825, Certainty::normal);
return;
}
if (!mSettings.isEnabled(value, inconclusive))
return;
ErrorPath errorPath = getErrorPath(tok, value, "Dereference of an invalid iterator");
if (value->condition) {
reportError(std::move(errorPath), Severity::warning, "derefInvalidIteratorRedundantCheck", errmsgcond, CWE825, (inconclusive || value->isInconclusive()) ? Certainty::inconclusive : Certainty::normal);
} else {
std::string errmsg = std::string(value->isKnown() ? "Dereference" : "Possible dereference") + " of an invalid iterator";
if (!varname.empty())
errmsg = "$symbol:" + varname + '\n' + errmsg + ": $symbol";
reportError(std::move(errorPath),
value->isKnown() ? Severity::error : Severity::warning,
"derefInvalidIterator",
errmsg,
CWE825, (inconclusive || value->isInconclusive()) ? Certainty::inconclusive : Certainty::normal);
}
}
void CheckStlImpl::dereferenceInvalidIteratorError(const Token* deref, const std::string &iterName)
{
reportError(deref, Severity::warning,
"derefInvalidIterator",
"$symbol:" + iterName + "\n"
"Possible dereference of an invalid iterator: $symbol\n"
"Possible dereference of an invalid iterator: $symbol. Make sure to check that the iterator is valid before dereferencing it - not after.", CWE825, Certainty::normal);
}
void CheckStlImpl::useStlAlgorithmError(const Token *tok, const std::string &algoName)
{
reportError(tok, Severity::style, "useStlAlgorithm",
"Consider using " + algoName + " algorithm instead of a raw loop.", CWE398, Certainty::normal);
}
static bool isEarlyExit(const Token *start)
{
if (start->str() != "{")
return false;
const Token *endToken = start->link();
const Token *tok = Token::findmatch(start, "return|throw|break|continue", endToken);
if (!tok || tok->scope() != start->scope() || tok->str() == "continue")
return false;
const Token *endStatement = Token::findsimplematch(tok, "; }", endToken);
if (!endStatement)
return false;
if (endStatement->next() != endToken)
return false;
return true;
}
static const Token *singleStatement(const Token *start)
{
if (start->str() != "{")
return nullptr;
const Token *endToken = start->link();
const Token *endStatement = Token::findsimplematch(start->next(), ";");
if (!Token::simpleMatch(endStatement, "; }"))
return nullptr;
if (endStatement->next() != endToken)
return nullptr;
return endStatement;
}
enum class LoopType : std::uint8_t { OTHER, RANGE, ITERATOR, INDEX };
static const Token *singleAssignInScope(const Token *start, nonneg int varid, bool &input, bool &hasBreak, LoopType loopType, const Settings& settings)
{
const Token *endStatement = singleStatement(start);
if (!endStatement)
return nullptr;
if (!Token::Match(start->next(), "%var% %assign%"))
return nullptr;
const Token *assignTok = start->tokAt(2);
if (isVariableChanged(assignTok->next(), endStatement, assignTok->astOperand1()->varId(), /*globalvar*/ false, settings))
return nullptr;
if (isVariableChanged(assignTok->next(), endStatement, varid, /*globalvar*/ false, settings))
return nullptr;
input = Token::findmatch(assignTok->next(), "%varid%", endStatement, varid) || !Token::Match(start->next(), "%var% =");
hasBreak = Token::simpleMatch(endStatement->previous(), "break");
if (loopType == LoopType::INDEX) { // check for container access
nonneg int containerId{};
for (const Token* tok = assignTok->next(); tok != endStatement; tok = tok->next()) {
if (tok->varId() == varid) {
if (!Token::simpleMatch(tok->astParent(), "["))
return nullptr;
const Token* contTok = tok->astParent()->astOperand1();
if (!contTok->valueType() || !contTok->valueType()->container || contTok->varId() == 0)
return nullptr;
if (containerId > 0 && containerId != contTok->varId()) // allow only one container
return nullptr;
containerId = contTok->varId();
}
}
return containerId > 0 ? assignTok : nullptr;
}
return assignTok;
}
static const Token *singleMemberCallInScope(const Token *start, nonneg int varid, bool &input, const Settings& settings)
{
if (start->str() != "{")
return nullptr;
const Token *endToken = start->link();
if (!Token::Match(start->next(), "%var% . %name% ("))
return nullptr;
if (!Token::simpleMatch(start->linkAt(4), ") ; }"))
return nullptr;
const Token *endStatement = start->linkAt(4)->next();
if (endStatement->next() != endToken)
return nullptr;
const Token *dotTok = start->tokAt(2);
if (!Token::findmatch(dotTok->tokAt(2), "%varid%", endStatement, varid))
return nullptr;
input = Token::Match(start->next(), "%var% . %name% ( %varid% )", varid);
if (isVariableChanged(dotTok->next(), endStatement, dotTok->astOperand1()->varId(), /*globalvar*/ false, settings))
return nullptr;
return dotTok;
}
static const Token *singleIncrementInScope(const Token *start, nonneg int varid, bool &input)
{
if (start->str() != "{")
return nullptr;
const Token *varTok = nullptr;
if (Token::Match(start->next(), "++ %var% ; }"))
varTok = start->tokAt(2);
else if (Token::Match(start->next(), "%var% ++ ; }"))
varTok = start->tokAt(1);
if (!varTok)
return nullptr;
input = varTok->varId() == varid;
return varTok;
}
static const Token *singleConditionalInScope(const Token *start, nonneg int varid, LoopType loopType, const Settings& settings)
{
if (start->str() != "{")
return nullptr;
const Token *endToken = start->link();
if (!Token::simpleMatch(start->next(), "if ("))
return nullptr;
if (!Token::simpleMatch(start->linkAt(2), ") {"))
return nullptr;
const Token *bodyTok = start->linkAt(2)->next();
const Token *endBodyTok = bodyTok->link();
if (!Token::simpleMatch(endBodyTok, "} }"))
return nullptr;
if (endBodyTok->next() != endToken)
return nullptr;
if (!Token::findmatch(start, "%varid%", bodyTok, varid))
return nullptr;
if (isVariableChanged(start, bodyTok, varid, /*globalvar*/ false, settings))
return nullptr;
if (loopType == LoopType::INDEX) { // check for container access
nonneg int containerId{};
for (const Token* tok = start->tokAt(2); tok != start->linkAt(2); tok = tok->next()) {
if (tok->varId() == varid) {
if (!Token::simpleMatch(tok->astParent(), "["))
return nullptr;
const Token* contTok = tok->astParent()->astOperand1();
if (!contTok->valueType() || !contTok->valueType()->container || contTok->varId() == 0)
return nullptr;
if (containerId > 0 && containerId != contTok->varId()) // allow only one container
return nullptr;
containerId = contTok->varId();
}
}
return containerId > 0 ? bodyTok : nullptr;
}
return bodyTok;
}
static bool addByOne(const Token *tok, nonneg int varid)
{
if (Token::Match(tok, "+= %any% ;") &&
tok->tokAt(1)->hasKnownIntValue() &&
tok->tokAt(1)->getValue(1)) {
return true;
}
if (Token::Match(tok, "= %varid% + %any% ;", varid) &&
tok->tokAt(3)->hasKnownIntValue() &&
tok->tokAt(3)->getValue(1)) {
return true;
}
return false;
}
static bool accumulateBoolLiteral(const Token *tok, nonneg int varid)
{
if (Token::Match(tok, "%assign% %bool% ;") &&
tok->tokAt(1)->hasKnownIntValue()) {
return true;
}
if (Token::Match(tok, "= %varid% %oror%|%or%|&&|& %bool% ;", varid) &&
tok->tokAt(3)->hasKnownIntValue()) {
return true;
}
return false;
}
static bool accumulateBool(const Token *tok, nonneg int varid)
{
// Missing %oreq% so we have to check both manually
if (Token::simpleMatch(tok, "&=") || Token::simpleMatch(tok, "|=")) {
return true;
}
if (Token::Match(tok, "= %varid% %oror%|%or%|&&|&", varid)) {
return true;
}
return false;
}
static bool hasVarIds(const Token *tok, nonneg int var1, nonneg int var2)
{
if (tok->astOperand1()->varId() == tok->astOperand2()->varId())
return false;
if (tok->astOperand1()->varId() == var1 || tok->astOperand1()->varId() == var2) {
if (tok->astOperand2()->varId() == var1 || tok->astOperand2()->varId() == var2) {
return true;
}
}
return false;
}
static std::string flipMinMax(const std::string &algo)
{
if (algo == "std::max_element")
return "std::min_element";
if (algo == "std::min_element")
return "std::max_element";
return algo;
}
static std::string minmaxCompare(const Token *condTok, nonneg int loopVar, nonneg int assignVar, LoopType loopType, bool invert = false)
{
if (loopType == LoopType::RANGE && !hasVarIds(condTok, loopVar, assignVar))
return "std::accumulate";
std::string algo = "std::max_element";
if (Token::Match(condTok, "")
type = ConditionOpType::MAX;
else
type = ConditionOpType::OTHER;
return true;
}
return false;
};
auto isAccumulation = [](const Token* tok, int varId) {
if (tok->str() != "=")
return true;
const Token* end = Token::findmatch(tok, "%varid%|;", varId); // TODO: lambdas?
return end && end->varId() != 0;
};
for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
// Parse range-based for loop
if (!Token::simpleMatch(tok, "for ("))
continue;
if (!Token::simpleMatch(tok->linkAt(1), ") {"))
continue;
LoopAnalyzer a{tok, mSettings};
std::string algoName = a.findAlgo();
if (!algoName.empty()) {
useStlAlgorithmError(tok, algoName);
continue;
}
const Token *bodyTok = tok->linkAt(1)->next();
const Token *splitTok = tok->next()->astOperand2();
const Token* loopVar{};
LoopType loopType{};
if (Token::simpleMatch(splitTok, ":")) {
loopVar = splitTok->previous();
if (loopVar->varId() == 0)
continue;
if (Token::simpleMatch(splitTok->astOperand2(), "{"))
continue;
loopType = LoopType::RANGE;
}
else { // iterator-based loop?
const Token* initTok = getInitTok(tok);
const Token* condTok = getCondTok(tok);
const Token* stepTok = getStepTok(tok);
if (!initTok || !condTok || !stepTok)
continue;
loopVar = Token::Match(condTok, "%comp%") ? condTok->astOperand1() : nullptr;
if (!Token::Match(loopVar, "%var%") || !loopVar->valueType() ||
(loopVar->valueType()->type != ValueType::Type::ITERATOR && !loopVar->valueType()->isIntegral()))
continue;
if (!Token::simpleMatch(initTok, "=") || !Token::Match(initTok->astOperand1(), "%varid%", loopVar->varId()))
continue;
if (!stepTok->isIncDecOp())
continue;
loopType = (loopVar->valueType()->type == ValueType::Type::ITERATOR) ? LoopType::ITERATOR : LoopType::INDEX;
}
// Check for single assignment
bool useLoopVarInAssign{}, hasBreak{};
const Token *assignTok = singleAssignInScope(bodyTok, loopVar->varId(), useLoopVarInAssign, hasBreak, loopType, mSettings);
if (assignTok) {
if (!checkAssignee(assignTok->astOperand1()))
continue;
const int assignVarId = assignTok->astOperand1()->varId();
std::string algo;
if (assignVarId == loopVar->varId()) {
if (useLoopVarInAssign)
algo = "std::transform";
else if (Token::Match(assignTok->next(), "%var%|%bool%|%num%|%char% ;"))
algo = "std::fill";
else if (Token::Match(assignTok->next(), "%name% ( )"))
algo = "std::generate";
else
algo = "std::fill or std::generate";
} else {
if (addByOne(assignTok, assignVarId))
algo = "std::distance";
else if (accumulateBool(assignTok, assignVarId))
algo = "std::any_of, std::all_of, std::none_of, or std::accumulate";
else if (isTernaryAssignment(assignTok, loopVar->varId(), assignVarId, loopType, algo))
;
else if (isAccumulation(assignTok, assignVarId))
algo = "std::accumulate";
else
continue;
}
useStlAlgorithmError(assignTok, algo);
continue;
}
// Check for container calls
bool useLoopVarInMemCall;
const Token *memberAccessTok = singleMemberCallInScope(bodyTok, loopVar->varId(), useLoopVarInMemCall, mSettings);
if (memberAccessTok && loopType == LoopType::RANGE) {
const int contVarId = memberAccessTok->astOperand1()->varId();
if (contVarId == loopVar->varId())
continue;
using Action = Library::Container::Action;
const auto action = astContainerAction(memberAccessTok->astOperand1(), mSettings.library);
if (contains({Action::PUSH, Action::INSERT}, action)) {
std::string algo;
if (useLoopVarInMemCall)
algo = "std::copy";
else
algo = "std::transform";
useStlAlgorithmError(memberAccessTok->astOperand2(), algo);
}
continue;
}
// Check for increment in loop
bool useLoopVarInIncrement;
const Token *incrementTok = singleIncrementInScope(bodyTok, loopVar->varId(), useLoopVarInIncrement);
if (incrementTok) {
std::string algo;
if (useLoopVarInIncrement)
algo = "std::transform";
else
algo = "std::distance";
useStlAlgorithmError(incrementTok, algo);
continue;
}
// Check for conditionals
const Token *condBodyTok = singleConditionalInScope(bodyTok, loopVar->varId(), loopType, mSettings);
if (condBodyTok) {
// Check for single assign
assignTok = singleAssignInScope(condBodyTok, loopVar->varId(), useLoopVarInAssign, hasBreak, loopType, mSettings);
if (assignTok) {
if (!checkAssignee(assignTok->astOperand1()))
continue;
const int assignVarId = assignTok->astOperand1()->varId();
std::string algo;
if (assignVarId == loopVar->varId()) {
if (useLoopVarInAssign)
algo = "std::transform";
else
algo = "std::replace_if";
} else {
ConditionOpType type{};
if (addByOne(assignTok, assignVarId))
algo = "std::count_if";
else if (accumulateBoolLiteral(assignTok, assignVarId))
algo = "std::any_of, std::all_of, std::none_of, or std::accumulate";
else if (assignTok->str() != "=")
algo = "std::accumulate";
else if (isConditionWithoutSideEffects(condBodyTok, type)) {
if (hasBreak)
algo = "std::any_of, std::all_of, std::none_of";
else if (assignTok->astOperand2()->varId() == loopVar->varId()) {
if (type == ConditionOpType::MIN)
algo = "std::min_element";
else if (type == ConditionOpType::MAX)
algo = "std::max_element";
else
continue;
}
else
continue;
}
else
continue;
}
useStlAlgorithmError(assignTok, algo);
continue;
}
// Check for container call
memberAccessTok = singleMemberCallInScope(condBodyTok, loopVar->varId(), useLoopVarInMemCall, mSettings);
if (memberAccessTok) {
const Token *memberCallTok = memberAccessTok->astOperand2();
const int contVarId = memberAccessTok->astOperand1()->varId();
if (contVarId == loopVar->varId())
continue;
if (memberCallTok->str() == "push_back" ||
memberCallTok->str() == "push_front" ||
memberCallTok->str() == "emplace_back") {
if (useLoopVarInMemCall)
useStlAlgorithmError(memberAccessTok, "std::copy_if");
// There is no transform_if to suggest
}
continue;
}
// Check for increment in loop
incrementTok = singleIncrementInScope(condBodyTok, loopVar->varId(), useLoopVarInIncrement);
if (incrementTok) {
std::string algo;
if (useLoopVarInIncrement)
algo = "std::transform";
else
algo = "std::count_if";
useStlAlgorithmError(incrementTok, algo);
continue;
}
// Check early return
if (isEarlyExit(condBodyTok)) {
const Token *loopVar2 = Token::findmatch(condBodyTok, "%varid%", condBodyTok->link(), loopVar->varId());
std::string algo;
if (loopVar2 ||
(loopType == LoopType::ITERATOR && loopVar->variable() && precedes(loopVar->variable()->nameToken(), tok))) // iterator declared outside the loop
algo = "std::find_if";
else
algo = "std::any_of";
useStlAlgorithmError(condBodyTok, algo);
continue;
}
}
}
}
}
void CheckStlImpl::knownEmptyContainerError(const Token *tok, const std::string& algo)
{
const std::string var = tok ? tok->expressionString() : std::string("var");
std::string msg;
if (astIsIterator(tok)) {
msg = "Using " + algo + " with iterator '" + var + "' that is always empty.";
} else {
msg = "Iterating over container '" + var + "' that is always empty.";
}
reportError(tok, Severity::style,
"knownEmptyContainer",
msg, CWE398, Certainty::normal);
}
static bool isKnownEmptyContainer(const Token* tok)
{
if (!tok)
return false;
return std::any_of(tok->values().begin(), tok->values().end(), [&](const ValueFlow::Value& v) {
if (!v.isKnown())
return false;
if (!v.isContainerSizeValue())
return false;
if (v.intvalue != 0)
return false;
return true;
});
}
void CheckStlImpl::knownEmptyContainer()
{
if (!mSettings.severity.isEnabled(Severity::style) && !mSettings.isPremiumEnabled("knownEmptyContainer"))
return;
logChecker("CheckStl::knownEmptyContainer"); // style
for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
if (!Token::Match(tok, "%name% ( !!)"))
continue;
// Parse range-based for loop
if (tok->str() == "for") {
if (!Token::simpleMatch(tok->linkAt(1), ") {"))
continue;
const Token *splitTok = tok->next()->astOperand2();
if (!Token::simpleMatch(splitTok, ":"))
continue;
const Token* contTok = splitTok->astOperand2();
if (!isKnownEmptyContainer(contTok))
continue;
knownEmptyContainerError(contTok, "");
} else {
const std::vector args = getArguments(tok);
if (args.empty())
continue;
for (size_t argnr = 1; argnr str());
break;
}
}
}
}
}
void CheckStlImpl::eraseIteratorOutOfBoundsError(const Token *ftok, const Token* itertok, const ValueFlow::Value* val)
{
if (!ftok || !itertok || !val) {
reportError(ftok, Severity::error, "eraseIteratorOutOfBounds",
"Calling function 'erase()' on the iterator 'iter' which is out of bounds.", CWE628, Certainty::normal);
reportError(ftok, Severity::warning, "eraseIteratorOutOfBoundsCond",
"Either the condition 'x' is redundant or function 'erase()' is called on the iterator 'iter' which is out of bounds.", CWE628, Certainty::normal);
return;
}
const std::string& func = ftok->str();
const std::string iter = itertok->expressionString();
const bool isConditional = val->isPossible();
std::string msg;
if (isConditional) {
msg = ValueFlow::eitherTheConditionIsRedundant(val->condition) + " or function '" + func + "()' is called on the iterator '" + iter + "' which is out of bounds.";
} else {
msg = "Calling function '" + func + "()' on the iterator '" + iter + "' which is out of bounds.";
}
const Severity severity = isConditional ? Severity::warning : Severity::error;
const std::string id = isConditional ? "eraseIteratorOutOfBoundsCond" : "eraseIteratorOutOfBounds";
reportError(ftok, severity,
id,
msg, CWE628, Certainty::normal);
}
static const ValueFlow::Value* getOOBIterValue(const Token* tok, const ValueFlow::Value* sizeVal)
{
auto it = std::find_if(tok->values().begin(), tok->values().end(), [&](const ValueFlow::Value& v) {
if (v.isPossible() || v.isKnown()) {
switch (v.valueType) {
case ValueFlow::Value::ValueType::ITERATOR_END:
return v.intvalue >= 0;
case ValueFlow::Value::ValueType::ITERATOR_START:
return (v.intvalue < 0) || (sizeVal && v.intvalue >= sizeVal->intvalue);
default:
break;
}
}
return false;
});
return it != tok->values().end() ? &*it : nullptr;
}
void CheckStlImpl::eraseIteratorOutOfBounds()
{
logChecker("CheckStl::eraseIteratorOutOfBounds");
for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
if (!tok->valueType())
continue;
const Library::Container* container = tok->valueType()->container;
if (!container || !astIsLHS(tok) || !Token::simpleMatch(tok->astParent(), "."))
continue;
const Token* const ftok = tok->astParent()->astOperand2();
const Library::Container::Action action = container->getAction(ftok->str());
if (action != Library::Container::Action::ERASE)
continue;
const std::vector args = getArguments(ftok);
if (args.size() != 1) // TODO: check range overload
continue;
const ValueFlow::Value* sizeVal = tok->getKnownValue(ValueFlow::Value::ValueType::CONTAINER_SIZE);
if (const ValueFlow::Value* errVal = getOOBIterValue(args[0], sizeVal))
eraseIteratorOutOfBoundsError(ftok, args[0], errVal);
}
}
}
namespace {
// An iterator position described by the ValueFlow values attached to the iterator expression
struct IteratorPosition {
const ValueFlow::Value* value = nullptr; // ITERATOR_START or ITERATOR_END value
const ValueFlow::Value* sizeValue = nullptr; // container size value with the same path, if available
bool fromEnd() const {
return value->isIteratorEndValue();
}
explicit operator bool() const {
return value != nullptr;
}
};
// A number of elements together with the ValueFlow values it was derived from
struct ElementCount {
MathLib::bigint count = 0;
std::vector values;
explicit operator bool() const {
return !values.empty();
}
};
// The best candidate proving an out of bounds access, preferring proofs without possible values
struct BestCandidate {
ElementCount best;
bool certain = false;
void consider(const ElementCount& candidate)
{
const bool candidateCertain =
std::none_of(candidate.values.cbegin(), candidate.values.cend(), std::mem_fn(&ValueFlow::Value::isPossible));
if (best && (certain || !candidateCertain))
return;
best = candidate;
certain = candidateCertain;
}
};
} // namespace
// Get the first ValueFlow value of a token matching the predicate, preferring known values
template
static const ValueFlow::Value* selectPreferredValue(const Token* tok, const Predicate& pred)
{
const ValueFlow::Value* result = nullptr;
for (const ValueFlow::Value& value : tok->values()) {
if (!pred(value))
continue;
if (result && !(value.isKnown() && !result->isKnown()))
continue;
result = &value;
}
return result;
}
// Get the iterator value of an iterator expression together with the container size value that
// ValueFlow has added to the iterator
static IteratorPosition getIteratorPosition(const Token* tok, const Settings& settings)
{
IteratorPosition position;
if (!tok)
return position;
position.value = selectPreferredValue(tok, [&](const ValueFlow::Value& value) {
return isUsableValue(value, settings) && value.isIteratorValue();
});
if (!position.value)
return position;
position.sizeValue = selectPreferredValue(tok, [&](const ValueFlow::Value& value) {
return isUsableValue(value, settings) && value.isContainerSizeValue() && value.path == position.value->path &&
sizeValueAppliesToIterator(value, *position.value);
});
return position;
}
// Compute the distance last-first between two iterators into the same container
static ElementCount getIteratorDistance(const IteratorPosition& first, const IteratorPosition& last)
{
ElementCount distance;
if (first.value->path != last.value->path)
return distance;
// bounded values could make the distance an overestimate
if (first.value->bound != ValueFlow::Value::Bound::Point || last.value->bound != ValueFlow::Value::Bound::Point)
return distance;
if (first.fromEnd() == last.fromEnd()) { // the container size cancels out
distance.count = last.value->intvalue - first.value->intvalue;
distance.values = {first.value, last.value};
return distance;
}
const IteratorPosition& endPosition = first.fromEnd() ? first : last;
if (!endPosition.sizeValue || endPosition.sizeValue->bound != ValueFlow::Value::Bound::Point)
return distance;
const MathLib::bigint endIndex = endPosition.sizeValue->intvalue + endPosition.value->intvalue;
distance.count = last.fromEnd() ? endIndex - first.value->intvalue : last.value->intvalue - endIndex;
distance.values = {first.value, last.value, endPosition.sizeValue};
return distance;
}
// Compute the number of elements available in the container behind the iterator position
static ElementCount getAvailableSpace(const IteratorPosition& position)
{
ElementCount available;
// the position could be smaller, which would make more elements available
if (position.value->bound == ValueFlow::Value::Bound::Upper)
return available;
if (position.fromEnd()) { // the container size cancels out
available.count = -position.value->intvalue;
available.values = {position.value};
return available;
}
// the container size could be larger, which would make more elements available
if (!position.sizeValue || position.sizeValue->bound == ValueFlow::Value::Bound::Lower)
return available;
available.count = position.sizeValue->intvalue - position.value->intvalue;
available.values = {position.value, position.sizeValue};
return available;
}
// Find iterator values and paired container sizes of the iterator that prove accessing
// elements to be out of bounds, preferring a proof that does not rely on possible values
static ElementCount findInsufficientSpace(const Token* tok,
MathLib::bigint accessed,
MathLib::bigint sourcePath,
const Settings& settings)
{
BestCandidate insufficient;
if (!tok)
return insufficient.best;
const auto consider = [&](const ElementCount& candidate) {
if (!candidate)
return;
if (candidate.count < 0 || accessed values()) {
if (!isUsableValue(value, settings) || !value.isIteratorValue())
continue;
if (value.path != 0 && sourcePath != 0 && value.path != sourcePath)
continue;
IteratorPosition position;
position.value = &value;
if (position.fromEnd()) { // the available space does not depend on the container size
consider(getAvailableSpace(position));
continue;
}
for (const ValueFlow::Value& sizeValue : tok->values()) {
if (!isUsableValue(sizeValue, settings) || !sizeValue.isContainerSizeValue() || sizeValue.path != value.path)
continue;
if (!sizeValueAppliesToIterator(sizeValue, value))
continue;
position.sizeValue = &sizeValue;
consider(getAvailableSpace(position));
}
}
return insufficient.best;
}
// Find iterator values and paired container sizes of the source range that prove more than
// elements to be accessed, preferring a proof that does not rely on possible values
static ElementCount findExcessiveDistance(const Token* firstTok,
const Token* lastTok,
MathLib::bigint available,
MathLib::bigint destPath,
const Settings& settings)
{
BestCandidate excessive;
const auto consider = [&](const ElementCount& candidate) {
if (!candidate)
return;
if (candidate.count values()) {
if (!isUsableValue(firstValue, settings) || !firstValue.isIteratorValue())
continue;
if (firstValue.path != 0 && destPath != 0 && firstValue.path != destPath)
continue;
for (const ValueFlow::Value& lastValue : lastTok->values()) {
if (!isUsableValue(lastValue, settings) || !lastValue.isIteratorValue())
continue;
IteratorPosition first, last;
first.value = &firstValue;
last.value = &lastValue;
if (first.fromEnd() == last.fromEnd()) { // the distance does not depend on the container size
consider(getIteratorDistance(first, last));
continue;
}
IteratorPosition& endPosition = first.fromEnd() ? first : last;
const Token* const endTok = first.fromEnd() ? firstTok : lastTok;
for (const ValueFlow::Value& sizeValue : endTok->values()) {
if (!isUsableValue(sizeValue, settings) || !sizeValue.isContainerSizeValue() ||
sizeValue.path != endPosition.value->path)
continue;
if (!sizeValueAppliesToIterator(sizeValue, *endPosition.value))
continue;
endPosition.sizeValue = &sizeValue;
consider(getIteratorDistance(first, last));
}
}
}
return excessive.best;
}
// Find count values of a count-based algorithm that prove more than elements to be accessed
static ElementCount findExcessiveCount(const Token* tok,
MathLib::bigint available,
MathLib::bigint destPath,
const Settings& settings)
{
BestCandidate excessive;
if (!tok)
return excessive.best;
for (const ValueFlow::Value& value : tok->values()) {
if (!isUsableValue(value, settings) || !value.isIntValue())
continue;
// a count with an upper bound could be smaller, which would make fewer elements accessed
if (value.bound == ValueFlow::Value::Bound::Upper)
continue;
if (value.path != 0 && destPath != 0 && value.path != destPath)
continue;
if (value.intvalue getSymbolDatabase()->functionScopes) {
for (const Token* tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
if (!Token::Match(tok, "std :: %name% ("))
continue;
const Token* const nameTok = tok->tokAt(2);
// algorithms accessing the range denoted by the third argument exactly last1-first1 times..
const bool exact = Token::Match(
nameTok,
"copy|move|swap_ranges|transform|replace_copy|replace_copy_if|reverse_copy|equal|mismatch|is_permutation|partial_sum|adjacent_difference|inner_product (");
// ..or at most last1-first1 times, depending on the values in the input range..
const bool atMost = !exact && Token::Match(nameTok, "copy_if|remove_copy|remove_copy_if|unique_copy (");
// ..or accessing their iterator arguments as many times as the count argument says
const bool countBased = !exact && !atMost && Token::Match(nameTok, "copy_n|fill_n|generate_n (");
if (!exact && !atMost && !countBased)
continue;
if (atMost && !mSettings.certainty.isEnabled(Certainty::inconclusive))
continue;
const std::vector args = getArguments(nameTok);
if (args.size() < 3)
continue;
ElementCount accessed; // source access count using the preferred values
std::vector iterArgs;
if (countBased) {
if (const ValueFlow::Value* countValue = getCountValue(args[1], mSettings)) {
accessed.count = countValue->intvalue;
accessed.values.push_back(countValue);
}
iterArgs.push_back(args[0]);
if (Token::simpleMatch(nameTok, "copy_n"))
iterArgs.push_back(args[2]); // copy_n also writes through the third argument
} else {
// two-range overloads taking a last2 iterator do not access the second range out of bounds
if (Token::Match(nameTok, "equal|mismatch|is_permutation") && args.size() >= 4 && astIsIterator(args[3]))
continue;
// both iterators must refer to the same container
const ValueFlow::Value firstLifetime = getLifetimeIteratorValue(args[0]);
const ValueFlow::Value lastLifetime = getLifetimeIteratorValue(args[1]);
if (!firstLifetime.tokvalue || !lastLifetime.tokvalue)
continue;
if (!isSameIteratorContainerExpression(firstLifetime.tokvalue,
lastLifetime.tokvalue,
mSettings,
firstLifetime.lifetimeKind))
continue;
const IteratorPosition first = getIteratorPosition(args[0], mSettings);
const IteratorPosition last = getIteratorPosition(args[1], mSettings);
if (first && last)
accessed = getIteratorDistance(first, last);
iterArgs.push_back(args[2]);
if (Token::simpleMatch(nameTok, "transform") && args.size() == 5)
iterArgs.push_back(args[3]); // binary transform also writes through the fourth argument
}
if (accessed.count path, mSettings);
if (!available || bothSidesPossible(sourceCount, available)) {
// ..or all source access counts against the preferred destination values
const IteratorPosition dest = getIteratorPosition(iterArg, mSettings);
if (!dest)
continue;
available = getAvailableSpace(dest);
if (!available || available.count < 0)
continue;
sourceCount =
countBased
? findExcessiveCount(args[1], available.count, dest.value->path, mSettings)
: findExcessiveDistance(args[0], args[1], available.count, dest.value->path, mSettings);
if (!sourceCount || bothSidesPossible(sourceCount, available))
continue;
}
const ValueFlow::Value* conditionValue = nullptr;
bool inconclusiveValues = false;
std::vector usedValues = sourceCount.values;
usedValues.insert(usedValues.end(), available.values.cbegin(), available.values.cend());
for (const ValueFlow::Value* value : usedValues) {
if (!conditionValue && value->condition)
conditionValue = value;
inconclusiveValues |= value->isInconclusive();
}
if (conditionValue && !mSettings.severity.isEnabled(Severity::warning))
continue;
const ValueFlow::Value* pathValue = conditionValue ? conditionValue : available.values.back();
algorithmOutOfBoundsError(iterArg,
"std::" + nameTok->str(),
sourceCount.count,
available.count,
pathValue,
atMost,
atMost || inconclusiveValues);
}
}
}
}
void CheckStlImpl::algorithmOutOfBoundsError(const Token* tok,
const std::string& algoName,
MathLib::bigint accessed,
MathLib::bigint available,
const ValueFlow::Value* value,
bool mayAccessFewer,
bool inconclusive)
{
const Token* const condition = value ? value->condition : nullptr;
const std::string iterExpr = tok ? tok->expressionString() : "it";
const std::string accessedStr = MathLib::toString(accessed) + (accessed == 1 ? " element" : " elements");
const std::string availableStr = MathLib::toString(available) + (available == 1 ? " element is" : " elements are");
const std::string body = "algorithm '" + algoName + "' " + (mayAccessFewer ? "may access up to " : "accesses ") +
accessedStr + " through the iterator '" + iterExpr + "' but only " + availableStr +
" available.";
const std::string msg =
condition ? (ValueFlow::eitherTheConditionIsRedundant(condition) + " or the " + body) : ("The " + body);
ErrorPath errorPath = getErrorPath(tok, value, "Access out of bounds");
reportError(std::move(errorPath),
(condition || mayAccessFewer) ? Severity::warning : Severity::error,
"algorithmOutOfBounds",
msg,
CWE788,
inconclusive ? Certainty::inconclusive : Certainty::normal);
}
static bool isMutex(const Variable* var)
{
const Token* tok = Token::typeDecl(var->nameToken()).first;
return Token::Match(tok, "std :: mutex|recursive_mutex|timed_mutex|recursive_timed_mutex|shared_mutex");
}
static bool isLockGuard(const Variable* var)
{
const Token* tok = Token::typeDecl(var->nameToken()).first;
return Token::Match(tok, "std :: lock_guard|unique_lock|scoped_lock|shared_lock");
}
static bool isLocalMutex(const Variable* var, const Scope* scope)
{
if (!var)
return false;
if (isLockGuard(var))
return false;
return !var->isReference() && !var->isRValueReference() && !var->isStatic() && var->scope() == scope;
}
void CheckStlImpl::globalLockGuardError(const Token* tok)
{
reportError(tok, Severity::warning,
"globalLockGuard",
"Lock guard is defined globally. Lock guards are intended to be local. A global lock guard could lead to a deadlock since it won't unlock until the end of the program.", CWE833, Certainty::normal);
}
void CheckStlImpl::localMutexError(const Token* tok)
{
reportError(tok, Severity::warning,
"localMutex",
"The lock is ineffective because the mutex is locked at the same scope as the mutex itself.", CWE667, Certainty::normal);
}
void CheckStlImpl::checkMutexes()
{
if (!mSettings.severity.isEnabled(Severity::warning))
return;
logChecker("CheckStl::checkMutexes"); // warning
for (const Scope *function : mTokenizer->getSymbolDatabase()->functionScopes) {
std::set checkedVars;
for (const Token *tok = function->bodyStart; tok != function->bodyEnd; tok = tok->next()) {
if (!Token::Match(tok, "%var%"))
continue;
const Variable* var = tok->variable();
if (!var)
continue;
if (Token::Match(tok, "%var% . lock ( )")) {
if (!isMutex(var))
continue;
if (!checkedVars.insert(var->declarationId()).second)
continue;
if (isLocalMutex(var, tok->scope()))
localMutexError(tok);
} else if (Token::Match(tok, "%var% (|{ %var% )|}|,")) {
if (!isLockGuard(var))
continue;
const Variable* mvar = tok->tokAt(2)->variable();
if (!mvar)
continue;
if (!checkedVars.insert(mvar->declarationId()).second)
continue;
if (var->isStatic() || var->isGlobal())
globalLockGuardError(tok);
else if (isLocalMutex(mvar, tok->scope()))
localMutexError(tok);
}
}
}
}
void CheckStl::runChecks(const Tokenizer &tokenizer, ErrorLogger& errorLogger)
{
if (!tokenizer.isCPP()) {
return;
}
CheckStlImpl checkStl(&tokenizer, tokenizer.getSettings(), errorLogger);
checkStl.erase();
checkStl.if_find();
checkStl.checkFindInsert();
checkStl.iterators();
checkStl.missingComparison();
checkStl.outOfBounds();
checkStl.outOfBoundsIndexExpression();
checkStl.redundantCondition();
checkStl.string_c_str();
checkStl.uselessCalls();
checkStl.useStlAlgorithm();
checkStl.stlOutOfBounds();
checkStl.negativeIndex();
checkStl.invalidContainer();
checkStl.mismatchingContainers();
checkStl.mismatchingContainerIterator();
checkStl.knownEmptyContainer();
checkStl.eraseIteratorOutOfBounds();
checkStl.algorithmOutOfBounds();
checkStl.stlBoundaries();
checkStl.checkDereferenceInvalidIterator();
checkStl.checkDereferenceInvalidIterator2();
checkStl.checkMutexes();
// Style check
checkStl.size();
}
void CheckStl::getErrorMessages(ErrorLogger& errorLogger, const Settings& settings) const
{
CheckStlImpl c(nullptr, settings, errorLogger);
c.outOfBoundsError(nullptr, "container", nullptr, "x", nullptr);
c.invalidIteratorError(nullptr, "iterator");
c.iteratorsError(nullptr, "container1", "container2");
c.iteratorsError(nullptr, nullptr, "container");
c.invalidContainerLoopError(nullptr, nullptr, ErrorPath{});
c.invalidContainerError(nullptr, nullptr, ErrorPath{});
c.invalidContainerReferenceError(nullptr, nullptr, ErrorPath{});
c.mismatchingContainerIteratorError(nullptr, nullptr, nullptr);
c.mismatchingContainersError(nullptr, nullptr);
c.mismatchingContainerExpressionError(nullptr, nullptr);
c.sameIteratorExpressionError(nullptr);
c.dereferenceErasedError(nullptr, nullptr, "iter", false);
c.stlOutOfBoundsError(nullptr, "i", "foo", false);
c.negativeIndexError(nullptr, ValueFlow::Value(-1));
c.stlBoundariesError(nullptr);
c.if_findError(nullptr, false);
c.if_findError(nullptr, true);
c.checkFindInsertError(nullptr);
c.string_c_strError(nullptr);
c.string_c_strReturn(nullptr);
c.string_c_strParam(nullptr, 0);
c.string_c_strConstructor(nullptr);
c.string_c_strAssignment(nullptr);
c.string_c_strConcat(nullptr);
c.string_c_strStream(nullptr);
c.string_c_strThrowError(nullptr);
c.sizeError(nullptr);
c.missingComparisonError(nullptr, nullptr);
c.redundantIfRemoveError(nullptr);
c.uselessCallsReturnValueError(nullptr, "str", "find");
c.uselessCallsSwapError(nullptr, "str");
c.uselessCallsSubstrError(nullptr, CheckStlImpl::SubstrErrorType::COPY);
c.uselessCallsConstructorError(nullptr);
c.uselessCallsEmptyError(nullptr);
c.uselessCallsRemoveError(nullptr, "remove");
c.dereferenceInvalidIteratorError(nullptr, "i");
// TODO: derefInvalidIteratorRedundantCheck
c.eraseIteratorOutOfBoundsError(nullptr, nullptr);
c.algorithmOutOfBoundsError(nullptr, "std::copy", 10, 6, nullptr, false, false);
c.useStlAlgorithmError(nullptr, "");
c.knownEmptyContainerError(nullptr, "");
c.globalLockGuardError(nullptr);
c.localMutexError(nullptr);
c.outOfBoundsIndexExpressionError(nullptr, nullptr);
}