ExprEngineException(const Token *tok, const std::string &what) : tok(tok), what(what) {}

const Token *tok;

const std::string what;

{

const char *typestr = "???UnknownValueType???";

switch (val->type) {

case ExprEngine::ValueType::AddressOfValue:

typestr = "AddressOfValue";

break;

case ExprEngine::ValueType::ArrayValue:

typestr = "ArrayValue";

break;

case ExprEngine::ValueType::UninitValue:

typestr = "UninitValue";

break;

case ExprEngine::ValueType::IntRange:

typestr = "IntRange";

break;

case ExprEngine::ValueType::FloatRange:

typestr = "FloatRange";

break;

case ExprEngine::ValueType::ConditionalValue:

typestr = "ConditionalValue";

break;

case ExprEngine::ValueType::StringLiteralValue:

typestr = "StringLiteralValue";

break;

case ExprEngine::ValueType::StructValue:

typestr = "StructValue";

break;

case ExprEngine::ValueType::BinOpResult:

typestr = "BinOpResult";

break;

case ExprEngine::ValueType::IntegerTruncation:

typestr = "IntegerTruncation";

break;

case ExprEngine::ValueType::FunctionCallArgumentValues:

typestr = "FunctionCallArgumentValues";

break;

case ExprEngine::ValueType::BailoutValue:

typestr = "BailoutValue";

break;

}

return val->name + "=" + std::string(typestr) + "(" + val->getRange() + ")";

{

int indent = 0;

for (; pos < str.size(); ++pos) {

if (indent <= 0 && str[pos] == what[0])

return pos;

else if (str[pos] == '\"') {

++pos;

while (pos < str.size()) {

if (str[pos] == '\"')

break;

if (pos == '\\')

++pos;

++pos;

}

} else if (str[pos] == '(')

++indent;

else if (str[pos] == ')')

--indent;

}

return std::string::npos;

{

std::ostringstream ostr;

#ifdef __GNUC__

if (value == (int)value) {

ostr << (int) value;

return ostr.str();

}

if (value < 0) {

ostr << "-";

value = -value;

}

uint64_t high = value >> 64;

uint64_t low = value;

if (high > 0)

ostr << "h" << std::hex << high << "l";

ostr << std::hex << low;

#else

ostr << value;

#endif

return ostr.str();

public:

TrackExecution() : mDataIndexCounter(0), mAbortLine(-1) {}

int getNewDataIndex() {

return mDataIndexCounter++;

}

void symbolRange(const Token *tok, ExprEngine::ValuePtr value) {

if (!tok || !value)

return;

if (tok->index() == 0)

return;

const std::string &symbolicExpression = value->getSymbolicExpression();

if (std::isdigit(symbolicExpression[0]) || value->type == ExprEngine::ValueType::BinOpResult || value->type == ExprEngine::ValueType::UninitValue)

return;

if (mSymbols.find(symbolicExpression) != mSymbols.end())

return;

mSymbols.insert(symbolicExpression);

mMap[tok].push_back(str(value));

}

void state(const Token *tok, const std::string &s) {

mMap[tok].push_back(s);

}

void print(std::ostream &out) {

std::set<std::pair<int,int>> locations;

for (const auto& it : mMap) {

locations.insert(std::pair<int,int>(it.first->linenr(), it.first->column()));

}

for (const std::pair<int,int> &loc : locations) {

int lineNumber = loc.first;

int column = loc.second;

for (auto &it : mMap) {

const Token *tok = it.first;

if (lineNumber != tok->linenr())

continue;

if (column != tok->column())

continue;

const std::vector<std::string> &dumps = it.second;

for (const std::string &dump : dumps)

out << lineNumber << ":" << column << ": " << dump << "\n";

}

}

}

void report(std::ostream &out, const Scope *functionScope) const {

int linenr = -1;

std::string code;

for (const Token *tok = functionScope->bodyStart->next(); tok != functionScope->bodyEnd; tok = tok->next()) {

if (tok->linenr() > linenr) {

if (!code.empty())

out << getStatus(linenr) << " " << code << std::endl;

linenr = tok->linenr();

code.clear();

}

code += " " + tok->str();

}

out << getStatus(linenr) << " " << code << std::endl;

}

void setAbortLine(int linenr) {

if (linenr > 0 && (mAbortLine == -1 || linenr < mAbortLine))

mAbortLine = linenr;

}

void addError(int linenr) {

mErrors.insert(linenr);

}

bool isAllOk() const {

return mErrors.empty();

}

void addMissingContract(const std::string &f) {

mMissingContracts.insert(f);

}

const std::set<std::string> getMissingContracts() const {

return mMissingContracts;

}

void ifSplit(const Token *tok, unsigned int thenIndex, unsigned int elseIndex) {

mMap[tok].push_back("D" + std::to_string(thenIndex) + ": Split. Then:D" + std::to_string(thenIndex) + " Else:D" + std::to_string(elseIndex));

}

private:

const char *getStatus(int linenr) const {

if (mErrors.find(linenr) != mErrors.end())

return "ERROR";

if (mAbortLine > 0 && linenr >= mAbortLine)

return "--";

return "ok";

}

std::map<const Token *, std::vector<std::string>> mMap;

int mDataIndexCounter;

int mAbortLine;

std::set<std::string> mSymbols;

std::set<int> mErrors;

std::set<std::string> mMissingContracts;

public:

Data(int *symbolValueIndex, ErrorLogger *errorLogger, const Tokenizer *tokenizer, const Settings *settings, const std::string &currentFunction, const std::vector<ExprEngine::Callback> &callbacks, TrackExecution *trackExecution)

: DataBase(currentFunction, settings)

, symbolValueIndex(symbolValueIndex)

, errorLogger(errorLogger)

, tokenizer(tokenizer)

, callbacks(callbacks)

, recursion(0)

, startTime(std::time(nullptr))

, mTrackExecution(trackExecution)

, mDataIndex(trackExecution->getNewDataIndex()) {}

Data(const Data &old)

: DataBase(old.currentFunction, old.settings)

, memory(old.memory)

, symbolValueIndex(old.symbolValueIndex)

, errorLogger(old.errorLogger)

, tokenizer(old.tokenizer)

, callbacks(old.callbacks)

, constraints(old.constraints)

, recursion(old.recursion)

, startTime(old.startTime)

, mTrackExecution(old.mTrackExecution)

, mDataIndex(mTrackExecution->getNewDataIndex()) {

for (auto &it: memory) {

if (!it.second)

continue;

if (auto oldValue = std::dynamic_pointer_cast<ExprEngine::ArrayValue>(it.second))

it.second = std::make_shared<ExprEngine::ArrayValue>(getNewSymbolName(), *oldValue);

}

}

using Memory = std::map<nonneg int, ExprEngine::ValuePtr>;

Memory memory;

int * const symbolValueIndex;

ErrorLogger *errorLogger;

const Tokenizer * const tokenizer;

const std::vector<ExprEngine::Callback> &callbacks;

std::vector<ExprEngine::ValuePtr> constraints;

int recursion;

std::time_t startTime;

bool isC() const override {

return tokenizer->isC();

}

bool isCPP() const override {

return tokenizer->isCPP();

}

#ifdef CONTRACT

ExprEngine::ValuePtr executeContract(const Function *function, ExprEngine::ValuePtr (*executeExpression)(const Token*, Data&)) {

const auto it = settings->functionContracts.find(function->fullName());

if (it == settings->functionContracts.end())

return ExprEngine::ValuePtr();

const std::string &expects = it->second;

TokenList tokenList(settings);

std::istringstream istr(expects);

tokenList.createTokens(istr);

tokenList.createAst();

SymbolDatabase *symbolDatabase = const_cast<SymbolDatabase*>(tokenizer->getSymbolDatabase());

for (Token *tok = tokenList.front(); tok; tok = tok->next()) {

for (const Variable &arg: function->argumentList) {

if (arg.name() == tok->str()) {

tok->variable(&arg);

tok->varId(arg.declarationId());

}

}

}

symbolDatabase->setValueTypeInTokenList(false, tokenList.front());

return executeExpression(tokenList.front()->astTop(), *this);

}

void contractConstraints(const Function *function, ExprEngine::ValuePtr (*executeExpression)(const Token*, Data&)) {

auto value = executeContract(function, executeExpression);

if (value)

constraints.push_back(value);

}

#endif

void assignValue(const Token *tok, unsigned int varId, ExprEngine::ValuePtr value) {

if (varId == 0)

return;

mTrackExecution->symbolRange(tok, value);

if (value) {

if (auto arr = std::dynamic_pointer_cast<ExprEngine::ArrayValue>(value)) {

for (const auto &dim: arr->size)

mTrackExecution->symbolRange(tok, dim);

for (const auto &indexAndValue: arr->data)

mTrackExecution->symbolRange(tok, indexAndValue.value);

} else if (auto s = std::dynamic_pointer_cast<ExprEngine::StructValue>(value)) {

for (const auto &m: s->member)

mTrackExecution->symbolRange(tok, m.second);

}

}

memory[varId] = value;

}

void assignStructMember(const Token *tok, ExprEngine::StructValue *structVal, const std::string &memberName, ExprEngine::ValuePtr value) {

mTrackExecution->symbolRange(tok, value);

structVal->member[memberName] = value;

}

void functionCall() {

// Remove values for global variables

const SymbolDatabase *symbolDatabase = tokenizer->getSymbolDatabase();

for (std::map<nonneg int, ExprEngine::ValuePtr>::iterator it = memory.begin(); it != memory.end();) {

unsigned int varid = it->first;

const Variable *var = symbolDatabase->getVariableFromVarId(varid);

if (var && var->isGlobal())

it = memory.erase(it);

else

++it;

}

}

std::string getNewSymbolName() final {

return "$" + std::to_string(++(*symbolValueIndex));

}

std::shared_ptr<ExprEngine::ArrayValue> getArrayValue(const Token *tok) {

const Memory::iterator it = memory.find(tok->varId());

if (it != memory.end())

return std::dynamic_pointer_cast<ExprEngine::ArrayValue>(it->second);

if (tok->varId() == 0 || !tok->variable())

return std::shared_ptr<ExprEngine::ArrayValue>();

auto val = std::make_shared<ExprEngine::ArrayValue>(this, tok->variable());

assignValue(tok, tok->varId(), val);

return val;

}

ExprEngine::ValuePtr getValue(unsigned int varId, const ValueType *valueType, const Token *tok) {

const Memory::const_iterator it = memory.find(varId);

if (it != memory.end())

return it->second;

if (!valueType)

return ExprEngine::ValuePtr();

// constant value..

const Variable *var = tokenizer->getSymbolDatabase()->getVariableFromVarId(varId);

if (var && valueType->constness == 1 && Token::Match(var->nameToken(), "%var% =")) {

const Token *initExpr = var->nameToken()->next()->astOperand2();

if (initExpr && initExpr->hasKnownIntValue()) {

auto intval = initExpr->getKnownIntValue();

return std::make_shared<ExprEngine::IntRange>(std::to_string(intval), intval, intval);

}

}

ExprEngine::ValuePtr value = getValueRangeFromValueType(getNewSymbolName(), valueType, *settings);

if (value) {

if (tok->variable() && tok->variable()->nameToken())

addConstraints(value, tok->variable()->nameToken());

assignValue(tok, varId, value);

}

return value;

}

void trackCheckContract(const Token *tok, const std::string &solverOutput) {

std::ostringstream os;

os << "checkContract:{\n";

std::string line;

std::istringstream istr(solverOutput);

while (std::getline(istr, line))

os << " " << line << "\n";

os << "}";

mTrackExecution->state(tok, os.str());

}

void trackProgramState(const Token *tok) {

if (memory.empty())

return;

const SymbolDatabase * const symbolDatabase = tokenizer->getSymbolDatabase();

std::ostringstream s;

s << "D" << mDataIndex << ":" << "memory:{";

bool first = true;

for (const auto &mem : memory) {

ExprEngine::ValuePtr value = mem.second;

const Variable *var = symbolDatabase->getVariableFromVarId(mem.first);

if (!var)

continue;

if (!first)

s << " ";

first = false;

s << var->name() << "=";

if (!value)

s << "(null)";

else if (value->name[0] == '$' && value->getSymbolicExpression() != value->name)

s << "(" << value->name << "," << value->getSymbolicExpression() << ")";

else

s << value->name;

}

s << "}";

if (!constraints.empty()) {

s << " constraints:{";

first = true;

for (const auto &constraint: constraints) {

if (!first)

s << " ";

first = false;

s << constraint->getSymbolicExpression();

}

s << "}";

}

mTrackExecution->state(tok, s.str());

}

void addMissingContract(const std::string &f) {

mTrackExecution->addMissingContract(f);

}

ExprEngine::ValuePtr notValue(ExprEngine::ValuePtr v) {

auto b = std::dynamic_pointer_cast<ExprEngine::BinOpResult>(v);

if (b) {

std::string binop;

if (b->binop == "==")

binop = "!=";

else if (b->binop == "!=")

binop = "==";

else if (b->binop == ">=")

binop = "<";

else if (b->binop == "<=")

binop = ">";

else if (b->binop == ">")

binop = "<=";

else if (b->binop == "<")

binop = ">=";

if (!binop.empty())

return std::make_shared<ExprEngine::BinOpResult>(binop, b->op1, b->op2);

}

if (std::dynamic_pointer_cast<ExprEngine::FloatRange>(v)) {

auto zero = std::make_shared<ExprEngine::FloatRange>("0.0", 0.0, 0.0);

return std::make_shared<ExprEngine::BinOpResult>("==", v, zero);

}

auto zero = std::make_shared<ExprEngine::IntRange>("0", 0, 0);

return std::make_shared<ExprEngine::BinOpResult>("==", v, zero);

}

void addConstraint(ExprEngine::ValuePtr condValue, bool trueCond) {

if (!condValue)

return;

if (trueCond)

constraints.push_back(condValue);

else

constraints.push_back(notValue(condValue));

}

void addConstraint(ExprEngine::ValuePtr lhsValue, ExprEngine::ValuePtr rhsValue, bool equals) {

if (!lhsValue || !rhsValue)

return;

constraints.push_back(std::make_shared<ExprEngine::BinOpResult>(equals?"==":"!=", lhsValue, rhsValue));

}

void addConstraints(ExprEngine::ValuePtr value, const Token *tok) {

#ifdef CONTRACT

MathLib::bigint low;

if (tok->getCppcheckAttribute(TokenImpl::CppcheckAttributes::Type::LOW, &low))

addConstraint(std::make_shared<ExprEngine::BinOpResult>(">=", value, std::make_shared<ExprEngine::IntRange>(std::to_string(low), low, low)), true);

MathLib::bigint high;

if (tok->getCppcheckAttribute(TokenImpl::CppcheckAttributes::Type::HIGH, &high))

addConstraint(std::make_shared<ExprEngine::BinOpResult>("<=", value, std::make_shared<ExprEngine::IntRange>(std::to_string(high), high, high)), true);

#endif

}

void reportError(const Token *tok,

Severity::SeverityType severity,

const char id[],

const std::string &text,

CWE cwe,

bool inconclusive,

bool incomplete,

const std::string &functionName) override {

if (errorPath.empty())

mTrackExecution->addError(tok->linenr());

ErrorPath e = errorPath;

e.push_back(ErrorPathItem(tok, text));

ErrorMessage errmsg(e, &tokenizer->list, severity, id, text, cwe, inconclusive ? Certainty::inconclusive : Certainty::normal, true);

errmsg.incomplete = incomplete;

errmsg.function = functionName.empty() ? currentFunction : functionName;

errorLogger->reportErr(errmsg);

}

std::string str() const {

std::ostringstream ret;

std::map<std::string, ExprEngine::ValuePtr> vars;

for (const auto &mem: memory) {

if (!mem.second)

continue;

const Variable *var = tokenizer->getSymbolDatabase()->getVariableFromVarId(mem.first);

if (var && var->isLocal())

continue;

ret << " @" << mem.first << ":" << mem.second->name;

getSymbols(vars, mem.second);

}

for (const auto &var: vars) {

if (var.second->name[0] == '$')

ret << " " << ::str(var.second);

}

for (const auto &c: constraints)

ret << " (" << c->getSymbolicExpression() << ")";

ret << std::endl;

return ret.str();

}

void load(const std::string &s) {

std::vector<ImportData> importData;

parsestr(s, &importData);

//simplify(importData);

if (importData.empty())

return;

std::map<std::string, ExprEngine::ValuePtr> symbols;

for (const auto &mem: memory) {

getSymbols(symbols, mem.second);

}

// TODO: combined symbolvalue

std::map<int, std::string> combinedMemory;

for (const ImportData &d: importData) {

for (const auto &mem: d.mem) {

auto c = combinedMemory.find(mem.first);

if (c == combinedMemory.end()) {

combinedMemory[mem.first] = mem.second;

continue;

}

if (c->second == mem.second)

continue;

if (c->second == "?" || mem.second == "?")

c->second = "?";

else

c->second.clear();

}

}

for (const auto &mem: combinedMemory) {

int varid = mem.first;

const std::string &name = mem.second;

auto it = memory.find(varid);

if (it != memory.end() && it->second && it->second->name == name)

continue;

if (name.empty()) {

if (it != memory.end())

memory.erase(it);

continue;

}

auto it2 = symbols.find(name);

if (it2 != symbols.end()) {

memory[varid] = it2->second;

continue;

}

if (name == "?") {

auto uninitValue = std::make_shared<ExprEngine::UninitValue>();

symbols[name] = uninitValue;

memory[varid] = uninitValue;

continue;

}

if (std::isdigit(name[0])) {

long long v = std::stoi(name);

auto intRange = std::make_shared<ExprEngine::IntRange>(name, v, v);

symbols[name] = intRange;

memory[varid] = intRange;

continue;

}

// TODO: handle this value..

if (it != memory.end())

memory.erase(it);

}

}

static void ifSplit(const Token *tok, const Data& thenData, const Data& elseData) {

thenData.mTrackExecution->ifSplit(tok, thenData.mDataIndex, elseData.mDataIndex);

}

private:

TrackExecution * const mTrackExecution;

const int mDataIndex;

struct ImportData {

std::map<int, std::string> mem;

std::map<std::string, std::string> sym;

std::vector<std::string> constraints;

};

static void parsestr(const std::string &s, std::vector<ImportData> *importData) {

std::string line;

std::istringstream istr(s);

while (std::getline(istr, line)) {

if (line.empty())

continue;

line += " ";

ImportData d;

for (std::string::size_type pos = 0; pos < line.size();) {

pos = line.find_first_not_of(" ", pos);

if (pos == std::string::npos)

break;

if (line[pos] == '@') {

++pos;

std::string::size_type colon = line.find(":", pos);

std::string::size_type end = line.find(" ", colon);

const std::string lhs = line.substr(pos, colon-pos);

pos = colon + 1;

const std::string rhs = line.substr(pos, end-pos);

d.mem[std::stoi(lhs)] = rhs;

pos = end;

} else if (line[pos] == '$') {

const std::string::size_type eq = line.find("=", pos);

const std::string lhs = line.substr(pos, eq-pos);

pos = eq + 1;

const std::string::size_type end = extfind(line, " ", pos);

const std::string rhs = line.substr(pos, end-pos);

pos = end;

d.sym[lhs] = rhs;

} else if (line[pos] == '(') {

const std::string::size_type end = extfind(line, " ", pos);

const std::string c = line.substr(pos, end-pos);

pos = end;

d.constraints.push_back(c);

} else {

throw ExprEngineException(nullptr, "Internal Error: Data::parsestr(), line:" + line);

}

}

importData->push_back(d);

}

}

void getSymbols(std::map<std::string, ExprEngine::ValuePtr> &symbols, ExprEngine::ValuePtr val) const {

if (!val)

return;

symbols[val->name] = val;

if (auto arrayValue = std::dynamic_pointer_cast<ExprEngine::ArrayValue>(val)) {

for (const auto &sizeValue: arrayValue->size)

getSymbols(symbols, sizeValue);

for (const auto &indexValue: arrayValue->data) {

getSymbols(symbols, indexValue.index);

getSymbols(symbols, indexValue.value);

}

}

if (auto structValue = std::dynamic_pointer_cast<ExprEngine::StructValue>(val)) {

for (const auto &memberNameValue: structValue->member)

getSymbols(symbols, memberNameValue.second);

}

}

{

auto b = std::dynamic_pointer_cast<ExprEngine::BinOpResult>(origValue);

if (!b)

return origValue;

if (!b->op1 || !b->op2)

return origValue;

auto intRange1 = std::dynamic_pointer_cast<ExprEngine::IntRange>(b->op1);

auto intRange2 = std::dynamic_pointer_cast<ExprEngine::IntRange>(b->op2);

if (intRange1 && intRange2 && intRange1->minValue == intRange1->maxValue && intRange2->minValue == intRange2->maxValue) {

const std::string &binop = b->binop;

int128_t v;

if (binop == "+")

v = intRange1->minValue + intRange2->minValue;

else if (binop == "-")

v = intRange1->minValue - intRange2->minValue;

else if (binop == "*")

v = intRange1->minValue * intRange2->minValue;

else if (binop == "/" && intRange2->minValue != 0)

v = intRange1->minValue / intRange2->minValue;

else if (binop == "%" && intRange2->minValue != 0)

v = intRange1->minValue % intRange2->minValue;

else

return origValue;

return std::make_shared<ExprEngine::IntRange>(ExprEngine::str(v), v, v);

}

return origValue;

{

if (!value)

return value;

if (value->type == ExprEngine::ValueType::UninitValue) {

auto rangeValue = getValueRangeFromValueType(data.getNewSymbolName(), valueType, *data.settings);

if (rangeValue)

return rangeValue;

}

if (auto conditionalValue = std::dynamic_pointer_cast<ExprEngine::ConditionalValue>(value)) {

if (conditionalValue->values.size() == 1 && conditionalValue->values[0].second && conditionalValue->values[0].second->type == ExprEngine::ValueType::UninitValue) {

auto rangeValue = getValueRangeFromValueType(data.getNewSymbolName(), valueType, *data.settings);

if (rangeValue)

return rangeValue;

}

}

return value;

{

value = value & (((int128_t)1 << bits) - 1);

// Sign extension

if (sign == 's' && value & (1ULL << (bits - 1)))

value |= ~(((int128_t)1 << bits) - 1);

return value;

{

if (!v1 || !v2)

return !v1 && !v2;

return v1->name == v2->name;

{

if (!v1 || !v2)

return false; // Don't know!

auto intRange1 = std::dynamic_pointer_cast<ExprEngine::IntRange>(v1);

auto intRange2 = std::dynamic_pointer_cast<ExprEngine::IntRange>(v2);

if (intRange1 && intRange2 && (intRange1->minValue > intRange2->maxValue || intRange1->maxValue < intRange2->maxValue))

return true;

return false;