cppcheck/lib/pathanalysis.cpp at main · codingman/cppcheck · GitHub

History

172 lines (163 loc) · 6.85 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

#include "pathanalysis.h"

#include "astutils.h"

#include "symboldatabase.h"

#include "token.h"

#include "valueflow.h"

#include <algorithm>

const Scope* PathAnalysis::findOuterScope(const Scope * scope)

{

if (!scope)

return nullptr;

if (scope->isLocal() && scope->type != Scope::eSwitch)

return findOuterScope(scope->nestedIn);

return scope;

}

static const Token* assignExpr(const Token* tok)

{

while (tok->astParent() && astIsLHS(tok)) {

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

return tok->astParent();

tok = tok->astParent();

}

return nullptr;

}

std::pair<bool, bool> PathAnalysis::checkCond(const Token * tok, bool& known)

{

if (tok->hasKnownIntValue()) {

known = true;

return std::make_pair(tok->values().front().intvalue, !tok->values().front().intvalue);

}

auto it = std::find_if(tok->values().begin(), tok->values().end(), [](const ValueFlow::Value& v) {

return v.isIntValue();

});

// If all possible values are the same, then assume all paths have the same value

if (it != tok->values().end() && std::all_of(it, tok->values().end(), [&](const ValueFlow::Value& v) {

if (v.isIntValue())

return v.intvalue == it->intvalue;

return true;

})) {

known = false;

return std::make_pair(it->intvalue, !it->intvalue);

}

return std::make_pair(true, true);

}

PathAnalysis::Progress PathAnalysis::forwardRecursive(const Token* tok, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const

{

if (!tok)

return Progress::Continue;

if (tok->astOperand1() && forwardRecursive(tok->astOperand1(), info, f) == Progress::Break)

return Progress::Break;

info.tok = tok;

if (f(info) == Progress::Break)

return Progress::Break;

if (tok->astOperand2() && forwardRecursive(tok->astOperand2(), info, f) == Progress::Break)

return Progress::Break;

return Progress::Continue;

}

PathAnalysis::Progress PathAnalysis::forwardRange(const Token* startToken, const Token* endToken, Info info, const std::function<PathAnalysis::Progress(const Info&)>& f) const

{

for (const Token *tok = startToken; tok && tok != endToken; tok = tok->next()) {

if (Token::Match(tok, "asm|goto|break|continue"))

return Progress::Break;

else if (Token::Match(tok, "return|throw")) {

forwardRecursive(tok, info, f);

return Progress::Break;

// Evaluate RHS of assignment before LHS

} else if (const Token* assignTok = assignExpr(tok)) {

if (forwardRecursive(assignTok->astOperand2(), info, f) == Progress::Break)

return Progress::Break;

if (forwardRecursive(assignTok->astOperand1(), info, f) == Progress::Break)

return Progress::Break;

tok = nextAfterAstRightmostLeaf(assignTok);

if (!tok)

return Progress::Break;

} else if (Token::simpleMatch(tok, "}") && Token::simpleMatch(tok->link()->previous(), ") {") && Token::Match(tok->link()->linkAt(-1)->previous(), "if|while|for (")) {

const Token * blockStart = tok->link()->linkAt(-1)->previous();

const Token * condTok = getCondTok(blockStart);

if (!condTok)

continue;

info.errorPath.emplace_back(condTok, "Assuming condition is true.");

// Traverse a loop a second time

if (Token::Match(blockStart, "for|while (")) {

const Token* endCond = blockStart->linkAt(1);

bool traverseLoop = true;

// Only traverse simple for loops

if (Token::simpleMatch(blockStart, "for") && !Token::Match(endCond->tokAt(-3), "; ++|--|%var% %var%|++|-- ) {"))

traverseLoop = false;

// Traverse loop a second time

if (traverseLoop) {

// Traverse condition

if (forwardRecursive(condTok, info, f) == Progress::Break)

return Progress::Break;

// TODO: Should we traverse the body: forwardRange(tok->link(), tok, info, f)?

}

if (Token::simpleMatch(tok, "} else {")) {

tok = tok->linkAt(2);

}

} else if (Token::Match(tok, "if|while|for (") && Token::simpleMatch(tok->next()->link(), ") {")) {

const Token * endCond = tok->next()->link();

const Token * endBlock = endCond->next()->link();

const Token * condTok = getCondTok(tok);

if (!condTok)

continue;

// Traverse condition

if (forwardRange(tok->next(), tok->next()->link(), info, f) == Progress::Break)

return Progress::Break;

Info i = info;

i.known = false;

i.errorPath.emplace_back(condTok, "Assuming condition is true.");

// Check if condition is true or false

bool checkThen = false;

bool checkElse = false;

std::tie(checkThen, checkElse) = checkCond(condTok, i.known);

// Traverse then block

if (checkThen) {

if (forwardRange(endCond->next(), endBlock, i, f) == Progress::Break)

return Progress::Break;

}

// Traverse else block

if (Token::simpleMatch(endBlock, "} else {")) {

if (checkElse) {

i.errorPath.back().second = "Assuming condition is false.";

Progress result = forwardRange(endCond->next(), endBlock, i, f);

if (result == Progress::Break)

return Progress::Break;

}

tok = endBlock->linkAt(2);

} else {

tok = endBlock;

}

} else if (Token::simpleMatch(tok, "} else {")) {

tok = tok->linkAt(2);

} else {

info.tok = tok;

if (f(info) == Progress::Break)

return Progress::Break;

}

// Prevent infinite recursion

if (tok->next() == start)

break;

}

return Progress::Continue;

}

void PathAnalysis::forward(const std::function<Progress(const Info&)>& f) const

{

const Scope * endScope = findOuterScope(start->scope());

if (!endScope)

return;

const Token * endToken = endScope->bodyEnd;

Info info{start, ErrorPath{}, true};

forwardRange(start, endToken, info, f);

}

bool reaches(const Token * start, const Token * dest, const Library& library, ErrorPath* errorPath)

{

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

return (i.tok == dest);

});

if (!info.tok)

return false;

if (errorPath)

errorPath->insert(errorPath->end(), info.errorPath.begin(), info.errorPath.end());

return true;

}

cppcheck/lib/pathanalysis.cpp at main · codingman/cppcheck · GitHub

Expand file tree

Breadcrumbs

pathanalysis.cpp

Latest commit

History

Breadcrumbs

pathanalysis.cpp

File metadata and controls