/*

* Cppcheck - A tool for static C/C++ code analysis

* Copyright (C) 2007-2016 Cppcheck team.

*

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

#include "templatesimplifier.h"

#include "mathlib.h"

#include "token.h"

#include "tokenize.h"

#include "errorlogger.h"

#include "settings.h"

#include <algorithm>

#include <sstream>

#include <list>

#include <set>

#include <stack>

#include <vector>

#include <string>

#include <cassert>

#include <iostream>

#ifdef GDB_HELPERS

static void printlist(const std::list<Token *> &list)

{

for (std::list<Token *>::const_iterator it = list.begin(); it != list.end(); ++it) {

const Token *token = *it;

std::cout << " ";

while (token && !Token::Match(token, "[{};]")) {

std::cout << " " << token->str();

token = token->next();

}

std::cout << std::endl;

}

}

static void printvector(const std::vector<const Token *> &v)

{

for (std::size_t i = 0; i < v.size(); i++) {

const Token *token = v[i];

std::cout << " " << i << ":";

while (token && !Token::Match(token, "[{};]")) {

std::cout << " " << token->str();

token = token->next();

}

std::cout << std::endl;

}

}

#endif

//---------------------------------------------------------------------------

void TemplateSimplifier::cleanupAfterSimplify(Token *tokens)

{

bool goback = false;

for (Token *tok = tokens; tok; tok = tok->next()) {

if (goback) {

tok = tok->previous();

goback = false;

}

if (tok->str() == "(")

tok = tok->link();

else if (Token::Match(tok, "template < > %name%")) {

const Token *end = tok;

while (end) {

if (end->str() == ";")

break;

if (end->str() == "{") {

end = end->link()->next();

break;

}

if (!Token::Match(end, "%name%|::|<|>|,")) {

end = nullptr;

break;

}

end = end->next();

}

if (end) {

Token::eraseTokens(tok,end);

tok->deleteThis();

}

}

else if (Token::Match(tok, "%type% <") &&

(!tok->previous() || tok->previous()->str() == ";")) {

const Token *tok2 = tok->tokAt(2);

std::string type;

while (Token::Match(tok2, "%type% ,") || Token::Match(tok2, "%num% ,")) {

type += tok2->str() + ",";

tok2 = tok2->tokAt(2);

}

if (Token::Match(tok2, "%type% > (") || Token::Match(tok2, "%num% > (")) {

type += tok2->str();

tok->str(tok->str() + "<" + type + ">");

Token::eraseTokens(tok, tok2->tokAt(2));

if (tok == tokens)

goback = true;

}

}

}

}

void TemplateSimplifier::checkComplicatedSyntaxErrorsInTemplates(const Token *tokens)

{

// check for more complicated syntax errors when using templates..

for (const Token *tok = tokens; tok; tok = tok->next()) {

// skip executing scopes (ticket #3183)..

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

tok = tok->link();

if (!tok)

syntaxError(nullptr);

}

// skip executing scopes..

const Token *start = Tokenizer::startOfExecutableScope(tok);

if (start) {

tok = start->link();

}

// skip executing scopes (ticket #1985)..

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

tok = tok->next()->link();

while (Token::simpleMatch(tok, "} catch (")) {

tok = tok->linkAt(2);

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

tok = tok->next()->link();

}

}

if (!tok)

syntaxError(nullptr);

// not start of statement?

if (tok->previous() && !Token::Match(tok, "[;{}]"))

continue;

// skip starting tokens.. ;;; typedef typename foo::bar::..

while (Token::Match(tok, "[;{}]"))

tok = tok->next();

while (Token::Match(tok, "typedef|typename"))

tok = tok->next();

while (Token::Match(tok, "%type% ::"))

tok = tok->tokAt(2);

if (!tok)

break;

// template variable or type..

if (Token::Match(tok, "%type% <")) {

// these are used types..

std::set<std::string> usedtypes;

// parse this statement and see if the '<' and '>' are matching

unsigned int level = 0;

for (const Token *tok2 = tok; tok2 && !Token::Match(tok2, "[;{}]"); tok2 = tok2->next()) {

if (tok2->str() == "(")

tok2 = tok2->link();

else if (tok2->str() == "<") {

bool inclevel = false;

if (Token::simpleMatch(tok2->previous(), "operator <"))

;

else if (level == 0)

inclevel = true;

else if (tok2->next() && tok2->next()->isStandardType())

inclevel = true;

else if (Token::simpleMatch(tok2, "< typename"))

inclevel = true;

else if (Token::Match(tok2->tokAt(-2), "<|, %type% <") && usedtypes.find(tok2->previous()->str()) != usedtypes.end())

inclevel = true;

else if (Token::Match(tok2, "< %type%") && usedtypes.find(tok2->next()->str()) != usedtypes.end())

inclevel = true;

else if (Token::Match(tok2, "< %type%")) {

// is the next token a type and not a variable/constant?

// assume it's a type if there comes another "<"

const Token *tok3 = tok2->next();

while (Token::Match(tok3, "%type% ::"))

tok3 = tok3->tokAt(2);

if (Token::Match(tok3, "%type% <"))

inclevel = true;

}

if (inclevel) {

++level;

if (Token::Match(tok2->tokAt(-2), "<|, %type% <"))

usedtypes.insert(tok2->previous()->str());

}

} else if (tok2->str() == ">") {

if (level > 0)

--level;

} else if (tok2->str() == ">>") {

if (level > 0)

--level;

if (level > 0)

--level;

}

}

if (level > 0)

syntaxError(tok);

}

}

}

unsigned int TemplateSimplifier::templateParameters(const Token *tok)

{

unsigned int numberOfParameters = 1;

if (!tok)

return 0;

if (tok->str() != "<")

return 0;

tok = tok->next();

unsigned int level = 0;

while (tok) {

// skip const/volatile

if (Token::Match(tok, "const|volatile"))

tok = tok->next();

// skip struct/union

if (Token::Match(tok, "struct|union"))

tok = tok->next();

// Skip '&'

if (Token::Match(tok, "& ::| %name%"))

tok = tok->next();

// Skip variadic types (Ticket #5774, #6059, #6172)

if (Token::Match(tok, "%type% . . .")) {

tok = tok->tokAt(4);

continue;

}

// Skip '=', '?', ':'

if (tok && Token::Match(tok, "=|?|:"))

tok = tok->next();

if (!tok)

return 0;

// Skip casts

if (tok->str() == "(") {

tok = tok->link();

if (tok)

tok = tok->next();

}

// skip std::

if (tok && tok->str() == "::")

tok = tok->next();

while (Token::Match(tok, "%name% ::")) {

tok = tok->tokAt(2);

if (tok && tok->str() == "*") // Ticket #5759: Class member pointer as a template argument; skip '*'

tok = tok->next();

}

if (!tok)

return 0;

// num/type ..

if (!tok->isNumber() && tok->tokType() != Token::eChar && !tok->isName())

return 0;

tok = tok->next();

if (!tok)

return 0;

// * / const

while (Token::Match(tok, "*|&|const"))

tok = tok->next();

if (!tok)

return 0;

// Function pointer or prototype..

while (Token::Match(tok, "(|[")) {

if (!tok->link())

syntaxError(tok);

tok = tok->link()->next();

while (Token::Match(tok, "const|volatile")) // Ticket #5786: Skip function cv-qualifiers

tok = tok->next();

}

if (!tok)

return 0;

// inner template

if (tok->str() == "<") {

++level;

tok = tok->next();

}

if (!tok)

return 0;

// ,/>

while (Token::Match(tok, ">|>>")) {

if (level == 0)

return ((tok->str() == ">") ? numberOfParameters : 0);

--level;

if (tok->str() == ">>") {

if (level == 0)

return numberOfParameters;

--level;

}

tok = tok->next();

// * / &

while (Token::Match(tok, "[*&]"))

tok = tok->next();

if (!tok)

return 0;

}

if (tok->str() != ",")

continue;

if (level == 0)

++numberOfParameters;

tok = tok->next();

}

return 0;

}

bool TemplateSimplifier::removeTemplate(Token *tok)

{

if (!Token::simpleMatch(tok, "template <"))

return false;

int indentlevel = 0;

unsigned int countgt = 0; // Counter for ">"

for (const Token *tok2 = tok->next(); tok2; tok2 = tok2->next()) {

if (tok2->str() == "(") {

tok2 = tok2->link();

} else if (tok2->str() == ")") { // garbage code! (#3504)

Token::eraseTokens(tok,tok2);

tok->deleteThis();

return false;

}

else if (tok2->str() == "{") {

tok2 = tok2->link()->next();

Token::eraseTokens(tok, tok2);

if (tok2 && tok2->str() == ";" && tok2->next())

tok->deleteNext();

tok->deleteThis();

return true;

} else if (tok2->str() == "}") { // garbage code! (#3449)

Token::eraseTokens(tok,tok2);

tok->deleteThis();

return false;

}

// Count ">"

if (tok2->str() == ">")

countgt++;

// don't remove constructor

if (tok2->str() == "explicit" ||

(countgt == 1 && Token::Match(tok2->previous(), "> %type% (") &&

Tokenizer::startOfExecutableScope(tok2->linkAt(1)))) {

Token::eraseTokens(tok, tok2);

tok->deleteThis();

return true;

}

if (tok2->str() == ";") {

tok2 = tok2->next();

Token::eraseTokens(tok, tok2);

tok->deleteThis();

return true;

}

if (tok2->str() == "<")

++indentlevel;

else if (indentlevel >= 2 && tok2->str() == ">")

--indentlevel;

else if (Token::Match(tok2, "> class|struct %name% [,)]")) {

tok2 = tok2->next();

Token::eraseTokens(tok, tok2);

tok->deleteThis();

return true;

}

}

return false;

}

std::set<std::string> TemplateSimplifier::expandSpecialized(Token *tokens)

{

std::set<std::string> expandedtemplates;

// Locate specialized templates..

for (Token *tok = tokens; tok; tok = tok->next()) {

if (!Token::simpleMatch(tok, "template < >"))

continue;

// what kind of template is this?

Token *tok2 = tok->tokAt(3);

while (tok2 && (tok2->isName() || tok2->str() == "*"))

tok2 = tok2->next();

if (!TemplateSimplifier::templateParameters(tok2))

continue;

// unknown template.. bail out

if (!tok2->previous()->isName())

continue;

tok2 = tok2->previous();

std::string s;

{

std::ostringstream ostr;

const Token *tok3 = tok2;

for (; tok3 && tok3->str() != ">"; tok3 = tok3->next()) {

if (tok3 != tok2)

ostr << " ";

ostr << tok3->str();

}

if (!Token::Match(tok3, "> (|{|:"))

continue;

s = ostr.str();

}

// save search pattern..

const std::string pattern(s + " >");

// remove spaces to create new name

s.erase(std::remove(s.begin(), s.end(), ' '), s.end());

const std::string name(s + ">");

expandedtemplates.insert(name);

// Rename template..

Token::eraseTokens(tok2, Token::findsimplematch(tok2, "<")->findClosingBracket()->next());

tok2->str(name);

// delete the "template < >"

tok->deleteNext(2);

tok->deleteThis();

// Use this special template in the code..

while (nullptr != (tok2 = const_cast<Token *>(Token::findsimplematch(tok2, pattern.c_str())))) {

Token::eraseTokens(tok2, Token::findsimplematch(tok2, "<")->findClosingBracket()->next());

tok2->str(name);

}

}

return expandedtemplates;

}

std::list<Token *> TemplateSimplifier::getTemplateDeclarations(Token *tokens, bool &codeWithTemplates)

{

std::list<Token *> templates;

for (Token *tok = tokens; tok; tok = tok->next()) {

// TODO: handle namespaces. Right now we don't instantiate templates that are defined in namespaces.

if (Token::Match(tok, "namespace %type% {"))

tok = tok->linkAt(2);

if (Token::simpleMatch(tok, "template <")) {

// Some syntax checks, see #6865

if (!tok->tokAt(2))

syntaxError(tok->next());

if (tok->strAt(2)=="typename" &&

(!tok->tokAt(3) || !Token::Match(tok->tokAt(3), "%name%|.|,|>")))

syntaxError(tok->next());

codeWithTemplates = true;

Token *parmEnd = tok->next()->findClosingBracket();

int indentlevel = 0;

for (const Token *tok2 = parmEnd; tok2; tok2 = tok2->next()) {

if (tok2->str() == "(")

++indentlevel;

else if (tok2->str() == ")")

--indentlevel;

if (indentlevel) // In an argument list; move to the next token

continue;

// Just a declaration => ignore this

if (tok2->str() == ";")

break;

// Implementation => add to "templates"

if (tok2->str() == "{") {

templates.push_back(tok);

break;

}

}

}

}

return templates;

}

std::list<Token *> TemplateSimplifier::getTemplateInstantiations(Token *tokens)

{

std::list<Token *> used;

for (Token *tok = tokens; tok; tok = tok->next()) {

// template definition.. skip it

if (Token::simpleMatch(tok, "template <")) {

tok = tok->next()->findClosingBracket();

if (!tok)

break;

} else if (Token::Match(tok->previous(), "[({};=] %name% <") ||

Token::Match(tok->previous(), "%type% %name% <") ||

Token::Match(tok->tokAt(-2), "[,:] private|protected|public %name% <")) {

// Add inner template instantiations first => go to the ">"

// and then parse backwards, adding all seen instantiations

const Token *tok2 = tok->next()->findClosingBracket();

// parse backwards and add template instantiations

for (; tok2 && tok2 != tok; tok2 = tok2->previous()) {

if (Token::Match(tok2, ", %name% <") &&

TemplateSimplifier::templateParameters(tok2->tokAt(2))) {

used.push_back(tok2->next());

}

}

// Add outer template..

if (TemplateSimplifier::templateParameters(tok->next()))

used.push_back(tok);

}

}

return used;

}

void TemplateSimplifier::useDefaultArgumentValues(const std::list<Token *> &templates,

std::list<Token *> * const templateInstantiations)

{

for (std::list<Token *>::const_iterator iter1 = templates.begin(); iter1 != templates.end(); ++iter1) {

// template parameters with default value has syntax such as:

// x = y

// this list will contain all the '=' tokens for such arguments

std::list<Token *> eq;

// and this set the position of parameters with a default value

std::set<std::size_t> defaultedArgPos;

// parameter number. 1,2,3,..

std::size_t templatepar = 1;

// parameter depth

std::size_t templateParmDepth = 0;

// the template classname. This will be empty for template functions

std::string classname;

// Scan template declaration..

for (Token *tok = *iter1; tok; tok = tok->next()) {

if (Token::simpleMatch(tok, "template < >")) { // Ticket #5762: Skip specialization tokens

tok = tok->tokAt(2);

if (0 == templateParmDepth)

break;

continue;

}

if (tok->str() == "(") { // Ticket #6835

tok = tok->link();

continue;

}

if (tok->str() == "<" && templateParameters(tok))

++templateParmDepth;

// end of template parameters?

if (tok->str() == ">") {

if (Token::Match(tok, "> class|struct %name%"))

classname = tok->strAt(2);

if (templateParmDepth<2)

break;

else

--templateParmDepth;

}

// next template parameter

if (tok->str() == "," && (1 == templateParmDepth)) // Ticket #5823: Properly count parameters

++templatepar;

// default parameter value?

else if (Token::Match(tok, "= !!>")) {

if (defaultedArgPos.insert(templatepar).second) {

eq.push_back(tok);

} else {

// Ticket #5605: Syntax error (two equal signs for the same parameter), bail out

eq.clear();

break;

}

}

}

if (eq.empty() || classname.empty())

continue;

// iterate through all template instantiations

for (std::list<Token *>::const_iterator iter2 = templateInstantiations->begin(); iter2 != templateInstantiations->end(); ++iter2) {

Token *tok = *iter2;

if (!Token::simpleMatch(tok, (classname + " <").c_str()))

continue;

// count the parameters..

tok = tok->next();

const unsigned int usedpar = TemplateSimplifier::templateParameters(tok);

tok = tok->findClosingBracket();

if (tok && tok->str() == ">") {

tok = tok->previous();

std::list<Token *>::const_iterator it = eq.begin();

for (std::size_t i = (templatepar - eq.size()); it != eq.end() && i < usedpar; ++i)

++it;

while (it != eq.end()) {

int indentlevel = 0;

tok->insertToken(",");

tok = tok->next();

const Token *from = (*it)->next();

std::stack<Token *> links;

while (from && (!links.empty() || (from->str() != "," && (indentlevel || from->str() != ">")))) {

if (from->str() == "<")

++indentlevel;

else if (from->str() == ">")

--indentlevel;

tok->insertToken(from->str(), from->originalName());

tok = tok->next();

if (Token::Match(tok, "(|["))

links.push(tok);

else if (!links.empty() && Token::Match(tok, ")|]")) {

Token::createMutualLinks(links.top(), tok);

links.pop();

}

from = from->next();

}

++it;

}

}

}

for (std::list<Token *>::iterator it = eq.begin(); it != eq.end(); ++it) {

Token * const eqtok = *it;

Token *tok2;

int indentlevel = 0;

for (tok2 = eqtok->next(); tok2; tok2 = tok2->next()) {

if (Token::Match(tok2, ";|)|}|]")) { // bail out #6607

tok2 = nullptr;

break;

}

if (Token::Match(tok2, "(|{|["))

tok2 = tok2->link();

else if (Token::Match(tok2, "%type% <") && templateParameters(tok2->next())) {

std::list<Token*>::iterator ti = std::find(templateInstantiations->begin(),

templateInstantiations->end(),

tok2);

if (ti != templateInstantiations->end())

templateInstantiations->erase(ti);

++indentlevel;

} else if (indentlevel > 0 && tok2->str() == ">")

--indentlevel;

else if (indentlevel == 0 && Token::Match(tok2, ",|>"))

break;

if (indentlevel < 0)

break;

}

// something went wrong, don't call eraseTokens()

// with a nullptr "end" parameter (=all remaining tokens).

if (!tok2)

continue;

Token::eraseTokens(eqtok, tok2);

eqtok->deleteThis();

}

}

}

bool TemplateSimplifier::instantiateMatch(const Token *instance, const std::string &name, std::size_t numberOfArguments, const char patternAfter[])

{

if (!Token::simpleMatch(instance, (name + " <").c_str()))

return false;

if (numberOfArguments != TemplateSimplifier::templateParameters(instance->next()))

return false;

if (patternAfter) {

const Token *tok = instance;

unsigned int indentlevel = 0;

for (tok = instance; tok && (tok->str() != ">" || indentlevel > 0); tok = tok->next()) {

if (Token::Match(tok, "[<,] %name% <") && templateParameters(tok->tokAt(2)) > 0)

++indentlevel;

if (indentlevel > 0 && tok->str() == ">")

--indentlevel;

}

if (!tok || !Token::Match(tok->next(), patternAfter))

return false;

}

// nothing mismatching was found..

return true;

}

int TemplateSimplifier::getTemplateNamePosition(const Token *tok)

{

// get the position of the template name

int namepos = 0, starAmpPossiblePosition = 0;

if (Token::Match(tok, "> class|struct %type% {|:|<"))

namepos = 2;

else if (Token::Match(tok, "> %type% *|&| %type% ("))

namepos = 2;

else if (Token::Match(tok, "> %type% %type% *|&| %type% ("))

namepos = 3;

else if (Token::Match(tok, "> %type% *|&| %type% :: %type% (")) {

namepos = 4;

starAmpPossiblePosition = 2;

} else if (Token::Match(tok, "> %type% %type% *|&| %type% :: %type% (")) {

namepos = 5;

starAmpPossiblePosition = 3;

} else {

// Name not found

return -1;

}

if (Token::Match(tok->tokAt(starAmpPossiblePosition ? starAmpPossiblePosition : namepos), "*|&"))

++namepos;

return namepos;

}

void TemplateSimplifier::expandTemplate(

TokenList& tokenlist,

const Token *tok,

const std::string &name,

std::vector<const Token *> &typeParametersInDeclaration,

const std::string &newName,

std::vector<const Token *> &typesUsedInTemplateInstantiation,

std::list<Token *> &templateInstantiations)

{

bool inTemplateDefinition=false;

std::vector<const Token *> localTypeParametersInDeclaration;

for (const Token *tok3 = tokenlist.front(); tok3; tok3 = tok3 ? tok3->next() : nullptr) {

if (tok3->str()=="template") {

if (tok3->next() && tok3->next()->str()=="<") {

TemplateParametersInDeclaration(tok3->tokAt(2), localTypeParametersInDeclaration);

if (localTypeParametersInDeclaration.size() != typeParametersInDeclaration.size())

inTemplateDefinition = false; // Partial specialization

else

inTemplateDefinition = true;

} else

inTemplateDefinition = false; // Only template instantiation

}

if (Token::Match(tok3, "{|(|["))

tok3 = tok3->link();

// Start of template..

if (tok3 == tok) {

tok3 = tok3->next();

}

// member function implemented outside class definition

else if (inTemplateDefinition &&

TemplateSimplifier::instantiateMatch(tok3, name, typeParametersInDeclaration.size(), ":: ~| %name% (")) {

tokenlist.addtoken(newName, tok3->linenr(), tok3->fileIndex());

while (tok3 && tok3->str() != "::")

tok3 = tok3->next();

}

// not part of template.. go on to next token

else

continue;

int indentlevel = 0;

std::stack<Token *> brackets; // holds "(", "[" and "{" tokens

for (; tok3; tok3 = tok3->next()) {

if (tok3->isName()) {

// search for this token in the type vector

unsigned int itype = 0;

while (itype < typeParametersInDeclaration.size() && typeParametersInDeclaration[itype]->str() != tok3->str())

++itype;

// replace type with given type..

if (itype < typeParametersInDeclaration.size()) {

unsigned int typeindentlevel = 0;

for (const Token *typetok = typesUsedInTemplateInstantiation[itype];

typetok && (typeindentlevel>0 || !Token::Match(typetok, ",|>"));

typetok = typetok->next()) {

if (Token::simpleMatch(typetok, ". . .")) {

typetok = typetok->tokAt(2);

continue;

}

if (Token::Match(typetok, "%name% <") && templateParameters(typetok->next()) > 0)

++typeindentlevel;

else if (typeindentlevel > 0 && typetok->str() == ">")

--typeindentlevel;

tokenlist.addtoken(typetok, tok3->linenr(), tok3->fileIndex());

}

continue;

}

}

// replace name..

if (Token::Match(tok3, (name + " !!<").c_str())) {

tokenlist.addtoken(newName, tok3->linenr(), tok3->fileIndex());

continue;

}

// copy

tokenlist.addtoken(tok3, tok3->linenr(), tok3->fileIndex());

if (Token::Match(tok3, "%type% <")) {

//if (!Token::simpleMatch(tok3, (name + " <").c_str()))

//done = false;

templateInstantiations.push_back(tokenlist.back());

}

// link() newly tokens manually

else if (tok3->str() == "{") {

brackets.push(tokenlist.back());

indentlevel++;

} else if (tok3->str() == "(") {

brackets.push(tokenlist.back());

} else if (tok3->str() == "[") {

brackets.push(tokenlist.back());

} else if (tok3->str() == "}") {

assert(brackets.empty() == false && brackets.top()->str() == "{");

Token::createMutualLinks(brackets.top(), tokenlist.back());

if (tok3->strAt(1) == ";") {

const Token * tokSemicolon = tok3->next();

tokenlist.addtoken(tokSemicolon, tokSemicolon->linenr(), tokSemicolon->fileIndex());

}

brackets.pop();

if (indentlevel <= 1 && brackets.empty()) {

// there is a bug if indentlevel is 0

// the "}" token should only be added if indentlevel is 1 but I add it always intentionally

// if indentlevel ever becomes 0, cppcheck will write:

// ### Error: Invalid number of character {

break;

}

--indentlevel;

} else if (tok3->str() == ")") {

assert(brackets.empty() == false && brackets.top()->str() == "(");

Token::createMutualLinks(brackets.top(), tokenlist.back());

brackets.pop();

} else if (tok3->str() == "]") {

assert(brackets.empty() == false && brackets.top()->str() == "[");

Token::createMutualLinks(brackets.top(), tokenlist.back());

brackets.pop();

}

}

assert(brackets.empty());

}

}

static bool isLowerThanLogicalAnd(const Token *lower)

{

return lower->isAssignmentOp() || Token::Match(lower, "}|;|(|[|]|)|,|?|:|%oror%|return|throw|case");

}

static bool isLowerThanOr(const Token* lower)

{

return isLowerThanLogicalAnd(lower) || lower->str() == "&&";

}

static bool isLowerThanXor(const Token* lower)

{

return isLowerThanOr(lower) || lower->str() == "|";

}

static bool isLowerThanAnd(const Token* lower)

{

return isLowerThanXor(lower) || lower->str() == "^";

}

static bool isLowerThanShift(const Token* lower)

{

return isLowerThanAnd(lower) || lower->str() == "&";

}

static bool isLowerThanPlusMinus(const Token* lower)

{

return isLowerThanShift(lower) || Token::Match(lower, "%comp%|<<|>>");

}

static bool isLowerThanMulDiv(const Token* lower)

{

return isLowerThanPlusMinus(lower) || Token::Match(lower, "+|-");

}

static bool isLowerEqualThanMulDiv(const Token* lower)

{

return isLowerThanMulDiv(lower) || Token::Match(lower, "[*/%]");

}

static std::string ShiftInt(const char cop, const Token* left, const Token* right)

{

if (cop == '&' || cop == '|' || cop == '^')

return MathLib::calculate(left->str(), right->str(), cop);

const MathLib::bigint leftInt = MathLib::toLongNumber(left->str());

const MathLib::bigint rightInt = MathLib::toLongNumber(right->str());

const bool rightIntIsPositive = rightInt >= 0;

if (cop == '<') {

const bool leftOperationIsNotLeftShift = left->previous()->str() != "<<";

const bool operandIsLeftShift = right->previous()->str() == "<<";

// Ensure that its not a shift operator as used for streams

if (leftOperationIsNotLeftShift && operandIsLeftShift && rightIntIsPositive) {

const bool leftIntIsPositive = leftInt >= 0;

if (!leftIntIsPositive) { // In case the left integer is negative, e.g. -1000 << 16. Do not simplify.

return left->str() + " << " + right->str();

}

return MathLib::toString(leftInt << rightInt);

}

} else if (rightIntIsPositive) {

return MathLib::toString(leftInt >> rightInt);

}

return "";

}

static std::string ShiftUInt(const char cop, const Token* left, const Token* right)

{

if (cop == '&' || cop == '|' || cop == '^')

return MathLib::calculate(left->str(), right->str(), cop);

const MathLib::biguint leftInt=MathLib::toULongNumber(left->str());

const MathLib::biguint rightInt=MathLib::toULongNumber(right->str());

if (cop == '<') {

if (left->previous()->str() != "<<") // Ensure that its not a shift operator as used for streams

return MathLib::toString(leftInt << rightInt);

} else {

return MathLib::toString(leftInt >> rightInt);

}

return "";

}

bool TemplateSimplifier::simplifyNumericCalculations(Token *tok)

{

bool ret = false;

// (1-2)

while (tok->tokAt(4) && tok->next()->isNumber() && tok->tokAt(3)->isNumber()) { // %any% %num% %any% %num% %any%

const Token* op = tok->tokAt(2);

const Token* after = tok->tokAt(4);

if (Token::Match(tok, "* %num% /") && (op->strAt(1) != "0") && tok->next()->str() == MathLib::multiply(op->strAt(1), MathLib::divide(tok->next()->str(), op->strAt(1)))) {

// Division where result is a whole number

} else if (!((op->str() == "*" && (isLowerThanMulDiv(tok) || tok->str() == "*") && isLowerEqualThanMulDiv(after)) || // associative

(Token::Match(op, "[/%]") && isLowerThanMulDiv(tok) && isLowerEqualThanMulDiv(after)) || // NOT associative

(Token::Match(op, "[+-]") && isLowerThanMulDiv(tok) && isLowerThanMulDiv(after)) || // Only partially (+) associative, but handled later

(Token::Match(op, ">>|<<") && isLowerThanShift(tok) && isLowerThanPlusMinus(after)) || // NOT associative

(op->str() == "&" && isLowerThanShift(tok) && isLowerThanShift(after)) || // associative

(op->str() == "^" && isLowerThanAnd(tok) && isLowerThanAnd(after)) || // associative

(op->str() == "|" && isLowerThanXor(tok) && isLowerThanXor(after)) || // associative

(op->str() == "&&" && isLowerThanOr(tok) && isLowerThanOr(after)) ||

(op->str() == "||" && isLowerThanLogicalAnd(tok) && isLowerThanLogicalAnd(after))))

break;

tok = tok->next();

// Don't simplify "%num% / 0"

if (Token::Match(op, "[/%] 0"))

continue;

// Integer operations

if (Token::Match(op, ">>|<<|&|^|%or%")) {

// Don't simplify if operand is negative, shifting with negative

// operand is UB. Bitmasking with negative operand is implementation

// defined behaviour.

if (MathLib::isNegative(tok->str()) || MathLib::isNegative(tok->strAt(2)))

continue;

const char cop = op->str()[0];

std::string result;

if (tok->str().find_first_of("uU") != std::string::npos)

result = ShiftUInt(cop, tok, tok->tokAt(2));

else

result = ShiftInt(cop, tok, tok->tokAt(2));

if (result.empty())

break;

tok->str(result);

}

// Logical operations

else if (Token::Match(op, "%oror%|&&")) {

int op1 = !MathLib::isNullValue(tok->str());

int op2 = !MathLib::isNullValue(tok->strAt(2));

int result = (op->str() == "||") ? (op1 || op2) : (op1 && op2);

tok->str(result ? "1" : "0");

}

else if (Token::Match(tok->previous(), "- %num% - %num%"))

tok->str(MathLib::add(tok->str(), tok->strAt(2)));

else if (Token::Match(tok->previous(), "- %num% + %num%"))

tok->str(MathLib::subtract(tok->str(), tok->strAt(2)));

else {

try {

tok->str(MathLib::calculate(tok->str(), tok->strAt(2), op->str()[0]));

} catch (InternalError &e) {

e.token = tok;