Skip to content

Evaluate symbolic values #3495

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
danmar merged 12 commits into from
Oct 11, 2021
Merged

Evaluate symbolic values #3495

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
2ff54c3
Evaluate symbolic values
pfultz2 Oct 9, 2021
4393bcc
Fix FP with impossible values
pfultz2 Oct 9, 2021
9e2a8dc
Update value instead
pfultz2 Oct 9, 2021
0683139
Merge branch 'main' into evaluate-symbolic-values
pfultz2 Oct 9, 2021
13fce10
Evaluate with bigint
pfultz2 Oct 9, 2021
6c01ee3
Add test for calulation
pfultz2 Oct 10, 2021
e504482
Handle impossible symbolic values
pfultz2 Oct 10, 2021
44013f2
Update bounds
pfultz2 Oct 10, 2021
cdca20d
Add TODO test case
pfultz2 Oct 10, 2021
f04ca16
Format
pfultz2 Oct 10, 2021
69d5cb0
Revert
pfultz2 Oct 10, 2021
417a740
Merge branch 'valueflow-increment-symbolic' into evaluate-symbolic-va…
pfultz2 Oct 10, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 4 additions & 2 deletions lib/analyzer.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,6 +20,7 @@
#define analyzerH

#include "config.h"
#include "mathlib.h"
#include <string>
#include <type_traits>
#include <vector>
Expand Down Expand Up @@ -155,8 +156,9 @@ struct Analyzer {
/// Update the state of the value
virtual void update(Token* tok, Action a, Direction d) = 0;
/// Try to evaluate the value of a token(most likely a condition)
virtual std::vector<int> evaluate(Evaluate e, const Token* tok, const Token* ctx = nullptr) const = 0;
std::vector<int> evaluate(const Token* tok, const Token* ctx = nullptr) const {
virtual std::vector<MathLib::bigint> evaluate(Evaluate e, const Token* tok, const Token* ctx = nullptr) const = 0;
std::vector<MathLib::bigint> evaluate(const Token* tok, const Token* ctx = nullptr) const
{
return evaluate(Evaluate::Integral, tok, ctx);
}
/// Lower any values to possible
Expand Down
5 changes: 3 additions & 2 deletions lib/forwardanalyzer.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -74,7 +74,7 @@ struct ForwardTraversal {
std::pair<bool, bool> evalCond(const Token* tok, const Token* ctx = nullptr) const {
if (!tok)
return std::make_pair(false, false);
std::vector<int> result = analyzer->evaluate(tok, ctx);
std::vector<MathLib::bigint> result = analyzer->evaluate(tok, ctx);
// TODO: We should convert to bool
bool checkThen = std::any_of(result.begin(), result.end(), [](int x) {
return x != 0;
Expand Down Expand Up @@ -600,7 +600,8 @@ struct ForwardTraversal {
if (conTok && updateRecursive(conTok) == Progress::Break)
return Break();
bool isEmpty = false;
std::vector<int> result = analyzer->evaluate(Analyzer::Evaluate::ContainerEmpty, conTok);
std::vector<MathLib::bigint> result =
analyzer->evaluate(Analyzer::Evaluate::ContainerEmpty, conTok);
if (result.empty())
analyzer->assume(conTok, false, Analyzer::Assume::ContainerEmpty);
else
Expand Down
2 changes: 1 addition & 1 deletion lib/reverseanalyzer.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,7 +18,7 @@ struct ReverseTraversal {
const Settings* settings;

std::pair<bool, bool> evalCond(const Token* tok) {
std::vector<int> result = analyzer->evaluate(tok);
std::vector<MathLib::bigint> result = analyzer->evaluate(tok);
// TODO: We should convert to bool
bool checkThen = std::any_of(result.begin(), result.end(), [](int x) {
return x == 1;
Expand Down
53 changes: 40 additions & 13 deletions lib/valueflow.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -803,11 +803,11 @@ static void setTokenValue(Token* tok, ValueFlow::Value value, const Settings* se
// increment
else if (parent->str() == "++") {
for (const ValueFlow::Value &val : tok->values()) {
if (!val.isIntValue() && !val.isFloatValue())
if (!val.isIntValue() && !val.isFloatValue() && !val.isSymbolicValue())
continue;
ValueFlow::Value v(val);
if (parent == tok->previous()) {
if (v.isIntValue())
if (v.isIntValue() || v.isSymbolicValue())
v.intvalue = v.intvalue + 1;
else
v.floatValue = v.floatValue + 1.0;
Expand All @@ -819,11 +819,11 @@ static void setTokenValue(Token* tok, ValueFlow::Value value, const Settings* se
// decrement
else if (parent->str() == "--") {
for (const ValueFlow::Value &val : tok->values()) {
if (!val.isIntValue() && !val.isFloatValue())
if (!val.isIntValue() && !val.isFloatValue() && !val.isSymbolicValue())
continue;
ValueFlow::Value v(val);
if (parent == tok->previous()) {
if (v.isIntValue())
if (v.isIntValue() || v.isSymbolicValue())
v.intvalue = v.intvalue - 1;
else
v.floatValue = v.floatValue - 1.0;
Expand Down Expand Up @@ -2080,7 +2080,7 @@ struct ValueFlowAnalyzer : Analyzer {
// Check if its assigned to the same value
if (value && !value->isImpossible() && Token::simpleMatch(tok->astParent(), "=") && astIsLHS(tok) &&
astIsIntegral(tok->astParent()->astOperand2(), false)) {
std::vector<int> result = evaluate(Evaluate::Integral, tok->astParent()->astOperand2());
std::vector<MathLib::bigint> result = evaluate(Evaluate::Integral, tok->astParent()->astOperand2());
if (!result.empty() && value->equalTo(result.front()))
return Action::Idempotent;
}
Expand Down Expand Up @@ -2188,22 +2188,48 @@ struct ValueFlowAnalyzer : Analyzer {
return true;
}

bool isSameSymbolicValue(const Token* tok, ErrorPath* errorPath = nullptr) const
const Token* findMatch(const Token* tok) const
{
return findAstNode(tok, [&](const Token* child) {
return match(child);
});
}

bool isSameSymbolicValue(const Token* tok, ValueFlow::Value* value = nullptr) const
{
if (!useSymbolicValues())
return false;
if (Token::Match(tok, "%assign%"))
return false;
const ValueFlow::Value* currValue = getValue(tok);
if (!currValue)
return false;
const bool exact = !currValue->isIntValue() || currValue->isImpossible();
for (const ValueFlow::Value& v : tok->values()) {
if (!v.isSymbolicValue())
continue;
if (!v.isKnown())
const bool toImpossible = v.isImpossible() && currValue->isKnown();
if (!v.isKnown() && !toImpossible)
continue;
if (v.intvalue != 0)
if (exact && v.intvalue != 0)
continue;
std::vector<MathLib::bigint> r;
ValueFlow::Value::Bound bound = currValue->bound;
if (match(v.tokvalue)) {
if (errorPath)
errorPath->insert(errorPath->end(), v.errorPath.begin(), v.errorPath.end());
r = {currValue->intvalue};
} else if (!exact && findMatch(v.tokvalue)) {
r = evaluate(Evaluate::Integral, v.tokvalue, tok);
if (bound == ValueFlow::Value::Bound::Point)
bound = v.bound;
}
if (!r.empty()) {
if (value) {
value->errorPath.insert(value->errorPath.end(), v.errorPath.begin(), v.errorPath.end());
value->intvalue = r.front() + v.intvalue;
if (toImpossible)
value->setImpossible();
value->bound = bound;
}
return true;
}
}
Expand Down Expand Up @@ -2302,11 +2328,12 @@ struct ValueFlowAnalyzer : Analyzer {
return Action::None;
}

virtual std::vector<int> evaluate(Evaluate e, const Token* tok, const Token* ctx = nullptr) const OVERRIDE {
virtual std::vector<MathLib::bigint> evaluate(Evaluate e, const Token* tok, const Token* ctx = nullptr) const OVERRIDE
{
if (e == Evaluate::Integral) {
if (tok->hasKnownIntValue())
return {static_cast<int>(tok->values().front().intvalue)};
std::vector<int> result;
std::vector<MathLib::bigint> result;
ProgramMemory pm = pms.get(tok, ctx, getProgramState());
if (Token::Match(tok, "&&|%oror%")) {
if (conditionIsTrue(tok, pm))
Expand Down Expand Up @@ -2384,7 +2411,7 @@ struct ValueFlowAnalyzer : Analyzer {
// Make a copy of the value to modify it
localValue = *value;
value = &localValue;
isSameSymbolicValue(tok, &value->errorPath);
isSameSymbolicValue(tok, &localValue);
}
// Read first when moving forward
if (d == Direction::Forward && a.isRead())
Expand Down
10 changes: 10 additions & 0 deletions test/testcondition.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3826,6 +3826,16 @@ class TestCondition : public TestFixture {
"}\n");
ASSERT_EQUALS("[test.cpp:2] -> [test.cpp:4]: (style) Condition 'z<1' is always false\n", errout.str());

check("bool f(int &index, const int s, const double * const array, double & x) {\n"
" if (index >= s)\n"
" return false;\n"
" else {\n"
" x = array[index];\n"
" return (index++) >= s;\n"
" }\n"
"}\n");
ASSERT_EQUALS("[test.cpp:2] -> [test.cpp:6]: (style) Condition '(index++)>=s' is always false\n", errout.str());

check("struct a {\n"
" a *b() const;\n"
"} c;\n"
Expand Down
71 changes: 71 additions & 0 deletions test/testvalueflow.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6357,6 +6357,77 @@ class TestValueFlow : public TestFixture {
"}";
ASSERT_EQUALS(true, testValueOfX(code, 3U, "y", 0));
ASSERT_EQUALS(true, testValueOfXImpossible(code, 3U, "y", -1));

code = "void f(int y) {\n"
" int x = y - 1;\n"
" if (y == 1)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXKnown(code, 4U, 0));

code = "void f(int y) {\n"
" int x = y * y;\n"
" if (y == 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXKnown(code, 4U, 4));

code = "void f(int x, int y) {\n"
" if (x == y*y)\n"
" if (y == 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXKnown(code, 4U, 4));

code = "void f(int x, int y) {\n"
" if (x > y*y)\n"
" if (y == 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXImpossible(code, 4U, 4));

code = "void f(int x, int y) {\n"
" if (x != y*y)\n"
" if (y == 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXImpossible(code, 4U, 4));

code = "void f(int x, int y) {\n"
" if (x >= y*y)\n"
" if (y == 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfXImpossible(code, 4U, 3));

code = "void f(int x, int y) {\n"
" if (x == y*y)\n"
" if (y != 2)\n"
" int a = x;\n"
"}\n";
TODO_ASSERT_EQUALS(true, false, testValueOfXImpossible(code, 4U, 4));

code = "void f(int x, int y) {\n"
" if (x == y*y)\n"
" if (y > 2)\n"
" int a = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfX(code, 4U, 9));

code = "struct A {\n"
" A* b();\n"
" int c() const;\n"
"};\n"
"void f(A *d) {\n"
" if (!d || d->c() != 1)\n"
" return;\n"
" A * y = d;\n"
" d = d->b();\n"
" A * x = d;\n"
" A* z = x;\n"
"}\n";
ASSERT_EQUALS(true, testValueOfX(code, 11U, "d", 0));
ASSERT_EQUALS(false, testValueOfXImpossible(code, 11U, 0));
}

void valueFlowSmartPointer()
Expand Down