Skip to content

Commit a08a9c1

Browse files
pfultz2danmar
pfultz2
authored and
danmar
committed
Switch to use lifetime analysis for iterators and pointers to invalid containers
This will diagnose more issues such as: ```cpp void f(std::vector<int> &v) { auto v0 = v.begin(); v.push_back(123); std::cout << *v0 << std::endl; } ```
1 parent 512c1b1 commit a08a9c1

9 files changed

Lines changed: 408 additions & 236 deletions

File tree

‎lib/astutils.cpp‎

Lines changed: 159 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1172,6 +1172,165 @@ static bool hasFunctionCall(const Token *tok)
11721172
return hasFunctionCall(tok->astOperand1()) || hasFunctionCall(tok->astOperand2());
11731173
}
11741174

1175+
const Scope* PathAnalysis::findOuterScope(const Scope * scope)
1176+
{
1177+
if (!scope)
1178+
return nullptr;
1179+
if (scope->isLocal() && scope->type != Scope::eSwitch)
1180+
return findOuterScope(scope->nestedIn);
1181+
return scope;
1182+
}
1183+
1184+
static const Token* getCondTok(const Token* tok)
1185+
{
1186+
if (!tok)
1187+
return nullptr;
1188+
if (Token::simpleMatch(tok, "("))
1189+
return getCondTok(tok->previous());
1190+
if (Token::simpleMatch(tok, "for") && Token::simpleMatch(tok->next()->astOperand2(), ";") && tok->next()->astOperand2()->astOperand2())
1191+
return tok->next()->astOperand2()->astOperand2()->astOperand1();
1192+
if (Token::simpleMatch(tok->next()->astOperand2(), ";"))
1193+
return tok->next()->astOperand2()->astOperand1();
1194+
return tok->next()->astOperand2();
1195+
}
1196+
1197+
std::pair<bool, bool> PathAnalysis::checkCond(const Token * tok, bool& known)
1198+
{
1199+
if (tok->hasKnownIntValue()) {
1200+
known = true;
1201+
return std::make_pair(tok->values().front().intvalue, !tok->values().front().intvalue);
1202+
}
1203+
auto it = std::find_if(tok->values().begin(), tok->values().end(), [](const ValueFlow::Value& v) {
1204+
return v.isIntValue();
1205+
});
1206+
// If all possible values are the same, then assume all paths have the same value
1207+
if (it != tok->values().end() && std::all_of(it, tok->values().end(), [&](const ValueFlow::Value& v) {
1208+
if (v.isIntValue())
1209+
return v.intvalue == it->intvalue;
1210+
return true;
1211+
})) {
1212+
known = false;
1213+
return std::make_pair(it->intvalue, !it->intvalue);
1214+
}
1215+
return std::make_pair(true, true);
1216+
}
1217+
1218+
PathAnalysis::Progress PathAnalysis::forwardRecursive(const Token* tok, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const
1219+
{
1220+
if (!tok)
1221+
return Progress::Continue;
1222+
if (tok->astOperand1() && forwardRecursive(tok->astOperand1(), info, f) == Progress::Break)
1223+
return Progress::Break;
1224+
info.tok = tok;
1225+
if (f(info) == Progress::Break)
1226+
return Progress::Break;
1227+
if (tok->astOperand2() && forwardRecursive(tok->astOperand2(), info, f) == Progress::Break)
1228+
return Progress::Break;
1229+
return Progress::Continue;
1230+
}
1231+
1232+
PathAnalysis::Progress PathAnalysis::forwardRange(const Token* startToken, const Token* endToken, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const
1233+
{
1234+
for (const Token *tok = startToken; tok && tok != endToken; tok = tok->next()) {
1235+
if (Token::Match(tok, "asm|goto|break|continue"))
1236+
return Progress::Break;
1237+
if (Token::Match(tok, "return|throw")) {
1238+
forwardRecursive(tok, info, f);
1239+
return Progress::Break;
1240+
}
1241+
if (Token::simpleMatch(tok, "}") && Token::simpleMatch(tok->link()->previous(), ") {") && Token::Match(tok->link()->linkAt(-1)->previous(), "if|while|for (")) {
1242+
const Token * blockStart = tok->link()->linkAt(-1)->previous();
1243+
const Token * condTok = getCondTok(blockStart);
1244+
if (!condTok)
1245+
continue;
1246+
info.errorPath.emplace_back(condTok, "Assuming condition is true.");
1247+
// Traverse a loop a second time
1248+
if (Token::Match(blockStart, "for|while (")) {
1249+
const Token* endCond = blockStart->linkAt(1);
1250+
bool traverseLoop = true;
1251+
// Only traverse simple for loops
1252+
if (Token::simpleMatch(blockStart, "for") && !Token::Match(endCond->tokAt(-3), "; ++|--|%var% %var%|++|-- ) {"))
1253+
traverseLoop = false;
1254+
// Traverse loop a second time
1255+
if (traverseLoop) {
1256+
// Traverse condition
1257+
if (forwardRecursive(condTok, info, f) == Progress::Break)
1258+
return Progress::Break;
1259+
// TODO: Should we traverse the body: forwardRange(tok->link(), tok, info, f)?
1260+
}
1261+
}
1262+
}
1263+
if (Token::Match(tok, "if|while|for (") && Token::simpleMatch(tok->next()->link(), ") {")) {
1264+
const Token * endCond = tok->next()->link();
1265+
const Token * endBlock = endCond->next()->link();
1266+
const Token * condTok = getCondTok(tok);
1267+
if (!condTok)
1268+
continue;
1269+
// Traverse condition
1270+
if (forwardRange(tok->next(), tok->next()->link(), info, f) == Progress::Break)
1271+
return Progress::Break;
1272+
Info i = info;
1273+
i.known = false;
1274+
i.errorPath.emplace_back(condTok, "Assuming condition is true.");
1275+
1276+
// Check if condition is true or false
1277+
bool checkThen = false;
1278+
bool checkElse = false;
1279+
std::tie(checkThen, checkElse) = checkCond(condTok, i.known);
1280+
1281+
// Traverse then block
1282+
if (checkThen) {
1283+
if (forwardRange(endCond->next(), endBlock, i, f) == Progress::Break)
1284+
return Progress::Break;
1285+
}
1286+
// Traverse else block
1287+
if (Token::simpleMatch(endBlock, "} else {")) {
1288+
if (checkElse) {
1289+
i.errorPath.back().second = "Assuming condition is false.";
1290+
Progress result = forwardRange(endCond->next(), endBlock, i, f);
1291+
if (result == Progress::Break)
1292+
return Progress::Break;
1293+
}
1294+
tok = endBlock->linkAt(2);
1295+
} else {
1296+
tok = endBlock;
1297+
}
1298+
} else if (Token::simpleMatch(tok, "} else {")) {
1299+
tok = tok->linkAt(2);
1300+
} else {
1301+
info.tok = tok;
1302+
if (f(info) == Progress::Break)
1303+
return Progress::Break;
1304+
}
1305+
// Prevent inifinite recursion
1306+
if (tok->next() == start)
1307+
break;
1308+
}
1309+
return Progress::Continue;
1310+
}
1311+
1312+
void PathAnalysis::forward(const std::function<Progress(const Info&)>& f) const
1313+
{
1314+
const Scope * endScope = findOuterScope(start->scope());
1315+
if (!endScope)
1316+
return;
1317+
const Token * endToken = endScope->bodyEnd;
1318+
Info info{start, ErrorPath{}, true};
1319+
forwardRange(start, endToken, info, f);
1320+
}
1321+
1322+
bool reaches(const Token * start, const Token * dest, const Library& library, ErrorPath* errorPath)
1323+
{
1324+
PathAnalysis::Info info = PathAnalysis{start, library} .forwardFind([&](const PathAnalysis::Info& i) {
1325+
return (i.tok == dest);
1326+
});
1327+
if (!info.tok)
1328+
return false;
1329+
if (errorPath)
1330+
errorPath->insert(errorPath->end(), info.errorPath.begin(), info.errorPath.end());
1331+
return true;
1332+
}
1333+
11751334
struct FwdAnalysis::Result FwdAnalysis::checkRecursive(const Token *expr, const Token *startToken, const Token *endToken, const std::set<int> &exprVarIds, bool local, bool inInnerClass)
11761335
{
11771336
// Parse the given tokens

‎lib/astutils.h‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@
3131

3232
class Library;
3333
class Settings;
34+
class Scope;
3435
class Token;
3536
class Variable;
3637

@@ -169,6 +170,62 @@ bool isConstVarExpression(const Token *tok);
169170

170171
const Variable *getLHSVariable(const Token *tok);
171172

173+
struct PathAnalysis {
174+
enum Progress {
175+
Continue,
176+
Break
177+
};
178+
PathAnalysis(const Token* start, const Library& library)
179+
: start(start), library(&library)
180+
{}
181+
const Token * start;
182+
const Library * library;
183+
184+
struct Info {
185+
const Token* tok;
186+
ErrorPath errorPath;
187+
bool known;
188+
};
189+
190+
void forward(const std::function<Progress(const Info&)>& f) const;
191+
template<class F>
192+
void forwardAll(F f) {
193+
forward([&](const Info& info) {
194+
f(info);
195+
return Progress::Continue;
196+
});
197+
}
198+
template<class Predicate>
199+
Info forwardFind(Predicate pred) {
200+
Info result{};
201+
forward([&](const Info& info) {
202+
if (pred(info)) {
203+
result = info;
204+
return Progress::Break;
205+
}
206+
return Progress::Continue;
207+
});
208+
return result;
209+
}
210+
private:
211+
212+
Progress forwardRecursive(const Token* tok, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const;
213+
Progress forwardRange(const Token* startToken, const Token* endToken, Info info, const std::function<Progress(const Info&)>& f) const;
214+
215+
static const Scope* findOuterScope(const Scope * scope);
216+
217+
static std::pair<bool, bool> checkCond(const Token * tok, bool& known);
218+
};
219+
220+
/**
221+
* @brief Returns true if there is a path between the two tokens
222+
*
223+
* @param start Starting point of the path
224+
* @param dest The path destination
225+
* @param errorPath Adds the path traversal to the errorPath
226+
*/
227+
bool reaches(const Token * start, const Token * dest, const Library& library, ErrorPath* errorPath);
228+
172229
/**
173230
* Forward data flow analysis for checks
174231
* - unused value

‎lib/checkautovariables.cpp‎

Lines changed: 0 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -631,38 +631,6 @@ void CheckAutoVariables::checkVarLifetime()
631631
}
632632
}
633633

634-
static std::string lifetimeMessage(const Token *tok, const ValueFlow::Value *val, ErrorPath &errorPath)
635-
{
636-
const Token *tokvalue = val ? val->tokvalue : nullptr;
637-
const Variable *tokvar = tokvalue ? tokvalue->variable() : nullptr;
638-
const Token *vartok = tokvar ? tokvar->nameToken() : nullptr;
639-
std::string type = lifetimeType(tok, val);
640-
std::string msg = type;
641-
if (vartok) {
642-
errorPath.emplace_back(vartok, "Variable created here.");
643-
const Variable * var = vartok->variable();
644-
if (var) {
645-
switch (val->lifetimeKind) {
646-
case ValueFlow::Value::LifetimeKind::Object:
647-
case ValueFlow::Value::LifetimeKind::Address:
648-
if (type == "pointer")
649-
msg += " to local variable";
650-
else
651-
msg += " that points to local variable";
652-
break;
653-
case ValueFlow::Value::LifetimeKind::Lambda:
654-
msg += " that captures local variable";
655-
break;
656-
case ValueFlow::Value::LifetimeKind::Iterator:
657-
msg += " to local container";
658-
break;
659-
}
660-
msg += " '" + var->name() + "'";
661-
}
662-
}
663-
return msg;
664-
}
665-
666634
void CheckAutoVariables::errorReturnDanglingLifetime(const Token *tok, const ValueFlow::Value *val)
667635
{
668636
ErrorPath errorPath = val ? val->errorPath : ErrorPath();

0 commit comments

Comments
 (0)