Skip to content

Commit b1c56d3

Browse files
pfultz2pfultz2
authored
Fix issue 9133: Invalid iterator; vector::push_back, functions (cppcheck-opensource#3008)
1 parent 678ee00 commit b1c56d3

6 files changed

Lines changed: 245 additions & 111 deletions

File tree

‎lib/astutils.cpp‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1877,6 +1877,16 @@ std::vector<const Token *> getArguments(const Token *ftok)
18771877
return astFlatten(startTok, ",");
18781878
}
18791879

1880+
int getArgumentPos(const Variable* var, const Function* f)
1881+
{
1882+
auto arg_it = std::find_if(f->argumentList.begin(), f->argumentList.end(), [&](const Variable& v) {
1883+
return v.nameToken() == var->nameToken();
1884+
});
1885+
if (arg_it == f->argumentList.end())
1886+
return -1;
1887+
return std::distance(f->argumentList.begin(), arg_it);
1888+
}
1889+
18801890
const Token *findLambdaStartToken(const Token *last)
18811891
{
18821892
if (!last || last->str() != "}")

‎lib/astutils.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@
3030
#include "errortypes.h"
3131
#include "utils.h"
3232

33+
class Function;
3334
class Library;
3435
class Scope;
3536
class Settings;
@@ -234,6 +235,8 @@ int numberOfArguments(const Token *start);
234235
*/
235236
std::vector<const Token *> getArguments(const Token *ftok);
236237

238+
int getArgumentPos(const Variable* var, const Function* f);
239+
237240
const Token *findLambdaStartToken(const Token *last);
238241

239242
/**

‎lib/checkstl.cpp‎

Lines changed: 184 additions & 87 deletions
Original file line numberDiff line numberDiff line change
@@ -18,17 +18,18 @@
1818

1919
#include "checkstl.h"
2020

21+
#include "astutils.h"
2122
#include "check.h"
2223
#include "checknullpointer.h"
24+
#include "errortypes.h"
2325
#include "library.h"
2426
#include "mathlib.h"
27+
#include "pathanalysis.h"
2528
#include "settings.h"
2629
#include "standards.h"
2730
#include "symboldatabase.h"
2831
#include "token.h"
2932
#include "utils.h"
30-
#include "astutils.h"
31-
#include "pathanalysis.h"
3233
#include "valueflow.h"
3334

3435
#include <algorithm>
@@ -38,6 +39,8 @@
3839
#include <map>
3940
#include <set>
4041
#include <sstream>
42+
#include <unordered_map>
43+
#include <unordered_set>
4144
#include <utility>
4245

4346
// Register this check class (by creating a static instance of it)
@@ -843,6 +846,105 @@ static bool isInvalidMethod(const Token * tok)
843846
return false;
844847
}
845848

849+
struct InvalidContainerAnalyzer {
850+
struct Info {
851+
struct Reference {
852+
const Token* tok;
853+
ErrorPath errorPath;
854+
};
855+
std::unordered_map<int, Reference> expressions;
856+
ErrorPath errorPath;
857+
void add(const std::vector<Reference>& refs)
858+
{
859+
for (const Reference& r : refs) {
860+
add(r);
861+
}
862+
}
863+
void add(const Reference& r)
864+
{
865+
if (!r.tok)
866+
return;
867+
expressions.insert(std::make_pair(r.tok->exprId(), r));
868+
}
869+
870+
std::vector<Reference> invalidTokens() const
871+
{
872+
std::vector<Reference> result;
873+
std::transform(expressions.begin(), expressions.end(), std::back_inserter(result), SelectMapValues{});
874+
return result;
875+
}
876+
};
877+
std::unordered_map<const Function*, Info> invalidMethods;
878+
879+
std::vector<Info::Reference> invalidatesContainer(const Token* tok) const
880+
{
881+
std::vector<Info::Reference> result;
882+
if (Token::Match(tok, "%name% (")) {
883+
const Function* f = tok->function();
884+
if (!f)
885+
return result;
886+
ErrorPathItem epi = std::make_pair(tok, "Calling function " + tok->str());
887+
const bool dependsOnThis = exprDependsOnThis(tok->next());
888+
auto it = invalidMethods.find(f);
889+
if (it != invalidMethods.end()) {
890+
std::vector<Info::Reference> refs = it->second.invalidTokens();
891+
std::copy_if(refs.begin(), refs.end(), std::back_inserter(result), [&](const Info::Reference& r) {
892+
const Variable* var = r.tok->variable();
893+
if (!var)
894+
return false;
895+
if (dependsOnThis && !var->isLocal() && !var->isGlobal() && !var->isStatic())
896+
return true;
897+
if (!var->isArgument())
898+
return false;
899+
if (!var->isReference())
900+
return false;
901+
return true;
902+
});
903+
std::vector<const Token*> args = getArguments(tok);
904+
for (Info::Reference& r : result) {
905+
r.errorPath.push_front(epi);
906+
const Variable* var = r.tok->variable();
907+
if (!var)
908+
continue;
909+
if (var->isArgument()) {
910+
int n = getArgumentPos(var, f);
911+
const Token* tok2 = nullptr;
912+
if (n >= 0 && n < args.size())
913+
tok2 = args[n];
914+
r.tok = tok2;
915+
}
916+
}
917+
}
918+
} else if (astIsContainer(tok)) {
919+
if (isInvalidMethod(tok)) {
920+
ErrorPath ep;
921+
ep.emplace_front(tok,
922+
"After calling '" + tok->strAt(2) +
923+
"', iterators or references to the container's data may be invalid .");
924+
result.push_back(Info::Reference{tok, ep});
925+
}
926+
}
927+
return result;
928+
}
929+
930+
void analyze(const SymbolDatabase* symboldatabase)
931+
{
932+
for (const Scope* scope : symboldatabase->functionScopes) {
933+
const Function* f = scope->function;
934+
if (!f)
935+
continue;
936+
for (const Token* tok = scope->bodyStart; tok != scope->bodyEnd; tok = tok->next()) {
937+
if (Token::Match(tok, "if|while|for|goto|return"))
938+
break;
939+
std::vector<Info::Reference> c = invalidatesContainer(tok);
940+
if (c.empty())
941+
continue;
942+
invalidMethods[f].add(c);
943+
}
944+
}
945+
}
946+
};
947+
846948
static bool isVariableDecl(const Token* tok)
847949
{
848950
if (!tok)
@@ -861,91 +963,91 @@ void CheckStl::invalidContainer()
861963
{
862964
const SymbolDatabase *symbolDatabase = mTokenizer->getSymbolDatabase();
863965
const Library& library = mSettings->library;
966+
InvalidContainerAnalyzer analyzer;
967+
analyzer.analyze(symbolDatabase);
864968
for (const Scope * scope : symbolDatabase->functionScopes) {
865969
for (const Token* tok = scope->bodyStart->next(); tok != scope->bodyEnd; tok = tok->next()) {
866-
if (!Token::Match(tok, "%var%"))
867-
continue;
868-
if (tok->varId() == 0)
869-
continue;
870-
if (!astIsContainer(tok))
871-
continue;
872-
if (!isInvalidMethod(tok))
873-
continue;
874-
std::set<nonneg int> skipVarIds;
875-
// Skip if the variable is assigned to
876-
const Token* assignExpr = tok;
877-
while (assignExpr->astParent()) {
878-
bool isRHS = astIsRHS(assignExpr);
879-
assignExpr = assignExpr->astParent();
880-
if (Token::Match(assignExpr, "%assign%")) {
881-
if (!isRHS)
882-
assignExpr = nullptr;
883-
break;
884-
}
885-
}
886-
if (Token::Match(assignExpr, "%assign%") && Token::Match(assignExpr->astOperand1(), "%var%"))
887-
skipVarIds.insert(assignExpr->astOperand1()->varId());
888-
const Token * endToken = nextAfterAstRightmostLeaf(tok->next()->astParent());
889-
if (!endToken)
890-
endToken = tok->next();
891-
const ValueFlow::Value* v = nullptr;
892-
ErrorPath errorPath;
893-
PathAnalysis::Info info = PathAnalysis{endToken, library} .forwardFind([&](const PathAnalysis::Info& info) {
894-
if (!info.tok->variable())
895-
return false;
896-
if (info.tok->varId() == 0)
897-
return false;
898-
if (skipVarIds.count(info.tok->varId()) > 0)
899-
return false;
900-
// if (Token::simpleMatch(info.tok->next(), "."))
901-
// return false;
902-
if (Token::Match(info.tok->astParent(), "%assign%") && astIsLHS(info.tok))
903-
skipVarIds.insert(info.tok->varId());
904-
if (info.tok->variable()->isReference() &&
905-
!isVariableDecl(info.tok) &&
906-
reaches(info.tok->variable()->nameToken(), tok, library, nullptr)) {
907-
908-
ErrorPath ep;
909-
bool addressOf = false;
910-
const Variable* var = getLifetimeVariable(info.tok, ep, &addressOf);
911-
// Check the reference is created before the change
912-
if (var && var->declarationId() == tok->varId() && !addressOf) {
913-
// An argument always reaches
914-
if (var->isArgument() || (!var->isReference() && !var->isRValueReference() &&
915-
!isVariableDecl(tok) && reaches(var->nameToken(), tok, library, &ep))) {
916-
errorPath = ep;
917-
return true;
918-
}
970+
for (const InvalidContainerAnalyzer::Info::Reference& r : analyzer.invalidatesContainer(tok)) {
971+
if (!astIsContainer(r.tok))
972+
continue;
973+
std::set<nonneg int> skipVarIds;
974+
// Skip if the variable is assigned to
975+
const Token* assignExpr = tok;
976+
while (assignExpr->astParent()) {
977+
bool isRHS = astIsRHS(assignExpr);
978+
assignExpr = assignExpr->astParent();
979+
if (Token::Match(assignExpr, "%assign%")) {
980+
if (!isRHS)
981+
assignExpr = nullptr;
982+
break;
919983
}
920984
}
921-
for (const ValueFlow::Value& val:info.tok->values()) {
922-
if (!val.isLocalLifetimeValue())
923-
continue;
924-
if (val.lifetimeKind == ValueFlow::Value::LifetimeKind::Address)
925-
continue;
926-
if (val.lifetimeKind == ValueFlow::Value::LifetimeKind::SubObject)
927-
continue;
928-
if (!val.tokvalue->variable())
929-
continue;
930-
if (val.tokvalue->varId() != tok->varId())
931-
continue;
932-
ErrorPath ep;
933-
// Check the iterator is created before the change
934-
if (val.tokvalue != tok && reaches(val.tokvalue, tok, library, &ep)) {
935-
v = &val;
936-
errorPath = ep;
937-
return true;
938-
}
985+
if (Token::Match(assignExpr, "%assign%") && Token::Match(assignExpr->astOperand1(), "%var%"))
986+
skipVarIds.insert(assignExpr->astOperand1()->varId());
987+
const Token* endToken = nextAfterAstRightmostLeaf(tok->next()->astParent());
988+
if (!endToken)
989+
endToken = tok->next();
990+
const ValueFlow::Value* v = nullptr;
991+
ErrorPath errorPath;
992+
PathAnalysis::Info info =
993+
PathAnalysis{endToken, library}.forwardFind([&](const PathAnalysis::Info& info) {
994+
if (!info.tok->variable())
995+
return false;
996+
if (info.tok->varId() == 0)
997+
return false;
998+
if (skipVarIds.count(info.tok->varId()) > 0)
999+
return false;
1000+
// if (Token::simpleMatch(info.tok->next(), "."))
1001+
// return false;
1002+
if (Token::Match(info.tok->astParent(), "%assign%") && astIsLHS(info.tok))
1003+
skipVarIds.insert(info.tok->varId());
1004+
if (info.tok->variable()->isReference() && !isVariableDecl(info.tok) &&
1005+
reaches(info.tok->variable()->nameToken(), tok, library, nullptr)) {
1006+
1007+
ErrorPath ep;
1008+
bool addressOf = false;
1009+
const Variable* var = getLifetimeVariable(info.tok, ep, &addressOf);
1010+
// Check the reference is created before the change
1011+
if (var && var->declarationId() == r.tok->varId() && !addressOf) {
1012+
// An argument always reaches
1013+
if (var->isArgument() ||
1014+
(!var->isReference() && !var->isRValueReference() && !isVariableDecl(tok) &&
1015+
reaches(var->nameToken(), tok, library, &ep))) {
1016+
errorPath = ep;
1017+
return true;
1018+
}
1019+
}
1020+
}
1021+
for (const ValueFlow::Value& val : info.tok->values()) {
1022+
if (!val.isLocalLifetimeValue())
1023+
continue;
1024+
if (val.lifetimeKind == ValueFlow::Value::LifetimeKind::Address)
1025+
continue;
1026+
if (val.lifetimeKind == ValueFlow::Value::LifetimeKind::SubObject)
1027+
continue;
1028+
if (!val.tokvalue->variable())
1029+
continue;
1030+
if (val.tokvalue->varId() != r.tok->varId())
1031+
continue;
1032+
ErrorPath ep;
1033+
// Check the iterator is created before the change
1034+
if (val.tokvalue != tok && reaches(val.tokvalue, tok, library, &ep)) {
1035+
v = &val;
1036+
errorPath = ep;
1037+
return true;
1038+
}
1039+
}
1040+
return false;
1041+
});
1042+
if (!info.tok)
1043+
continue;
1044+
errorPath.insert(errorPath.end(), info.errorPath.begin(), info.errorPath.end());
1045+
errorPath.insert(errorPath.end(), r.errorPath.begin(), r.errorPath.end());
1046+
if (v) {
1047+
invalidContainerError(info.tok, r.tok, v, errorPath);
1048+
} else {
1049+
invalidContainerReferenceError(info.tok, r.tok, errorPath);
9391050
}
940-
return false;
941-
});
942-
if (!info.tok)
943-
continue;
944-
errorPath.insert(errorPath.end(), info.errorPath.begin(), info.errorPath.end());
945-
if (v) {
946-
invalidContainerError(info.tok, tok, v, errorPath);
947-
} else {
948-
invalidContainerReferenceError(info.tok, tok, errorPath);
9491051
}
9501052
}
9511053
}
@@ -1011,8 +1113,6 @@ void CheckStl::invalidContainerLoopError(const Token *tok, const Token * loopTok
10111113
void CheckStl::invalidContainerError(const Token *tok, const Token * contTok, const ValueFlow::Value *val, ErrorPath errorPath)
10121114
{
10131115
const bool inconclusive = val ? val->isInconclusive() : false;
1014-
std::string method = contTok ? contTok->strAt(2) : "erase";
1015-
errorPath.emplace_back(contTok, "After calling '" + method + "', iterators or references to the container's data may be invalid .");
10161116
if (val)
10171117
errorPath.insert(errorPath.begin(), val->errorPath.begin(), val->errorPath.end());
10181118
std::string msg = "Using " + lifetimeMessage(tok, val, errorPath);
@@ -1022,10 +1122,7 @@ void CheckStl::invalidContainerError(const Token *tok, const Token * contTok, co
10221122

10231123
void CheckStl::invalidContainerReferenceError(const Token* tok, const Token* contTok, ErrorPath errorPath)
10241124
{
1025-
std::string method = contTok ? contTok->strAt(2) : "erase";
10261125
std::string name = contTok ? contTok->expressionString() : "x";
1027-
errorPath.emplace_back(
1028-
contTok, "After calling '" + method + "', iterators or references to the container's data may be invalid .");
10291126
std::string msg = "Reference to " + name;
10301127
errorPath.emplace_back(tok, "");
10311128
reportError(errorPath, Severity::error, "invalidContainerReference", msg + " that may be invalid.", CWE664, false);

‎lib/utils.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,22 @@
2828
#include <string>
2929
#include <vector>
3030

31+
struct SelectMapKeys {
32+
template <class Pair>
33+
typename Pair::first_type operator()(const Pair& p) const
34+
{
35+
return p.first;
36+
}
37+
};
38+
39+
struct SelectMapValues {
40+
template <class Pair>
41+
typename Pair::second_type operator()(const Pair& p) const
42+
{
43+
return p.second;
44+
}
45+
};
46+
3147
inline bool endsWith(const std::string &str, char c)
3248
{
3349
return str[str.size()-1U] == c;

0 commit comments

Comments
 (0)