/*

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

* Copyright (C) 2007-2018 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 "errorlogger.h"

#include "mathlib.h"

#include "settings.h"

#include "token.h"

#include "tokenize.h"

#include "tokenlist.h"

#include <algorithm>

#include <cassert>

#include <iostream>

#include <stack>

#include <utility>

namespace {

class FindToken {

public:

explicit FindToken(const Token *token) : mToken(token) {}

bool operator()(const TemplateSimplifier::TokenAndName &tokenAndName) const {

return tokenAndName.token == mToken;

}

private:

const Token * const mToken;

};

class FindName {

public:

explicit FindName(const std::string &name) : mName(name) {}

bool operator()(const TemplateSimplifier::TokenAndName &tokenAndName) const {

return tokenAndName.name == mName;

}

private:

const std::string mName;

};

}

TemplateSimplifier::TokenAndName::TokenAndName(Token *tok, const std::string &s, const std::string &n) :

token(tok), scope(s), name(n)

{

token->hasTemplateSimplifierPointer(true);

}

TemplateSimplifier::TemplateSimplifier(TokenList &tokenlist, const Settings *settings, ErrorLogger *errorLogger)

: mTokenList(tokenlist), mSettings(settings), mErrorLogger(errorLogger)

{

}

TemplateSimplifier::~TemplateSimplifier()

{

}

void TemplateSimplifier::cleanupAfterSimplify()

{

bool goback = false;

for (Token *tok = mTokenList.front(); 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%|%num% ,")) {

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

tok2 = tok2->tokAt(2);

}

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

type += tok2->str();

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

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

if (tok == mTokenList.front())

goback = true;

}

}

}

}

void TemplateSimplifier::checkComplicatedSyntaxErrorsInTemplates()

{

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

for (const Token *tok = mTokenList.front(); 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::simpleMatch(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 (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() && !tok->isOp())

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();

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

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

if (!tok)

return 0;

}

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

continue;

if (level == 0)

++numberOfParameters;

tok = tok->next();

}

return 0;

}

void TemplateSimplifier::eraseTokens(Token *begin, const Token *end)

{

if (!begin || begin == end)

return;

while (begin->next() && begin->next() != end) {

// check if token has a pointer to it

if (begin->next()->hasTemplateSimplifierPointer()) {

// check if the token is in a list

const std::list<TokenAndName>::iterator it = std::find_if(mTemplateInstantiations.begin(),

mTemplateInstantiations.end(),

FindToken(begin->next()));

if (it != mTemplateInstantiations.end()) {

// remove the pointer flag and prevent the deleted pointer from being used

it->token->hasTemplateSimplifierPointer(false);

it->token = nullptr;

}

const std::list<TokenAndName>::iterator it2 = std::find_if(mTemplateDeclarations.begin(),

mTemplateDeclarations.end(),

FindToken(begin->next()));

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

// remove the pointer flag and prevent the deleted pointer from being used

it2->token->hasTemplateSimplifierPointer(false);

it2->token = nullptr;

}

for (size_t i = 0; i < mTypesUsedInTemplateInstantiation.size(); ++i) {

if (mTypesUsedInTemplateInstantiation[i] == begin->next()) {

mTypesUsedInTemplateInstantiation[i]->hasTemplateSimplifierPointer(false);

mTypesUsedInTemplateInstantiation[i] = nullptr;

}

}

}

begin->deleteNext();

}

}

void TemplateSimplifier::deleteToken(Token *tok)

{

if (tok->next())

tok->next()->deletePrevious();

else

tok->deleteThis();

}

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)

eraseTokens(tok,tok2);

deleteToken(tok);

return false;

}

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

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

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

tok2 = tok2->next();

eraseTokens(tok, tok2);

deleteToken(tok);

return true;

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

eraseTokens(tok,tok2);

deleteToken(tok);

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)))) {

eraseTokens(tok, tok2);

deleteToken(tok);

return true;

}

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

tok2 = tok2->next();

eraseTokens(tok, tok2);

deleteToken(tok);

return true;

}

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

++indentlevel;

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

--indentlevel;

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

tok2 = tok2->next();

eraseTokens(tok, tok2);

deleteToken(tok);

return true;

}

}

return false;

}

/// TODO: This is copy pasted from Tokenizer. We should reuse this code.

namespace {

struct ScopeInfo2 {

ScopeInfo2(const std::string &name_, const Token *bodyEnd_) : name(name_), bodyEnd(bodyEnd_) {}

const std::string name;

const Token * const bodyEnd;

};

}

static std::string getScopeName(const std::list<ScopeInfo2> &scopeInfo)

{

std::string ret;

for (const ScopeInfo2 &i : scopeInfo)

ret += (ret.empty() ? "" : " :: ") + i.name;

return ret;

}

static std::string getFullName(const std::list<ScopeInfo2> &scopeInfo, const std::string &name)

{

const std::string &scopeName = getScopeName(scopeInfo);

return scopeName + (scopeName.empty() ? "" : " :: ") + name;

}

static void setScopeInfo(const Token *tok, std::list<ScopeInfo2> *scopeInfo)

{

while (tok->str() == "}" && !scopeInfo->empty() && tok == scopeInfo->back().bodyEnd)

scopeInfo->pop_back();

if (!Token::Match(tok, "namespace|class|struct|union %name% {|:|::"))

return;

tok = tok->next();

std::string classname = tok->str();

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

tok = tok->tokAt(2);

classname += " :: " + tok->str();

}

tok = tok->next();

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

// ...

}

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

scopeInfo->emplace_back(classname,tok->link());

}

}

std::list<TemplateSimplifier::TokenAndName> TemplateSimplifier::getTemplateDeclarations(bool &codeWithTemplates, bool forward)

{

std::list<ScopeInfo2> scopeInfo;

std::list<TokenAndName> declarations;

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

if (Token::Match(tok, "}|namespace|class|struct|union")) {

setScopeInfo(tok, &scopeInfo);

continue;

}

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

continue;

// Some syntax checks, see #6865

if (!tok->tokAt(2))

syntaxError(tok->next());

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

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

syntaxError(tok->next());

codeWithTemplates = true;

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

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

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

tok2 = tok2->link();

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

break;

// Just a declaration => ignore this

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

if (forward) {

const int namepos = getTemplateNamePosition(parmEnd, forward);

if (namepos > 0)

declarations.emplace_back(tok, getScopeName(scopeInfo), getFullName(scopeInfo, parmEnd->strAt(namepos)));

}

break;

}

// Implementation => add to "templates"

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

if (!forward) {

const int namepos = getTemplateNamePosition(parmEnd, forward);

if (namepos > 0)

declarations.emplace_back(tok, getScopeName(scopeInfo), getFullName(scopeInfo, parmEnd->strAt(namepos)));

}

break;

}

}

}

return declarations;

}

void TemplateSimplifier::getTemplateInstantiations()

{

std::list<ScopeInfo2> scopeList;

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

if (Token::Match(tok, "}|namespace|class|struct|union")) {

setScopeInfo(tok, &scopeList);

continue;

}

// template definition.. skip it

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

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

if (!tok)

break;

// #7914

// Ignore template instantiations within template definitions: they will only be

// handled if the definition is actually instantiated

const Token *tok2 = Token::findmatch(tok, "{|;");

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

tok = tok2->link();

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

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

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

std::string scopeName = getScopeName(scopeList);

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

scopeName += (scopeName.empty() ? "" : " :: ") + tok->str();

tok = tok->tokAt(2);

}

if (!Token::Match(tok, "%name% <"))

continue;

// 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

// TODO

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

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

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

mTemplateInstantiations.emplace_back(tok2->next(), getScopeName(scopeList), getFullName(scopeList, tok2->strAt(1)));

}

}

// Add outer template..

if (templateParameters(tok->next())) {

const std::string scopeName1(scopeName);

while (true) {

const std::string fullName = scopeName + (scopeName.empty()?"":" :: ") + tok->str();

const std::list<TokenAndName>::const_iterator it = std::find_if(mTemplateDeclarations.begin(), mTemplateDeclarations.end(), FindName(fullName));

if (it != mTemplateDeclarations.end()) {

mTemplateInstantiations.emplace_back(tok, getScopeName(scopeList), fullName);

break;

} else {

if (scopeName.empty()) {

mTemplateInstantiations.emplace_back(tok, getScopeName(scopeList), scopeName1 + (scopeName1.empty()?"":" :: ") + tok->str());

break;

}

const std::string::size_type pos = scopeName.rfind(" :: ");

scopeName = (pos == std::string::npos) ? std::string() : scopeName.substr(0,pos);

}

}

}

}

}

}

void TemplateSimplifier::useDefaultArgumentValues()

{

for (const TokenAndName &template1 : mTemplateDeclarations) {

// 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 = template1.token; 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|union %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 (const TokenAndName &templateInst : mTemplateInstantiations) {

Token *tok = templateInst.token;

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

continue;

// count the parameters..

tok = tok->next();

const unsigned int usedpar = 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() || indentlevel || !Token::Match(from, ",|>"))) {

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 (Token * const eqtok : eq) {

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<TokenAndName>::iterator ti = std::find_if(mTemplateInstantiations.begin(),

mTemplateInstantiations.end(),

FindToken(tok2));

if (ti != mTemplateInstantiations.end())

mTemplateInstantiations.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;

// don't strip args from uninstantiated templates

std::list<TokenAndName>::iterator ti2 = std::find_if(mTemplateInstantiations.begin(),

mTemplateInstantiations.end(),

FindName(template1.name));

if (ti2 == mTemplateInstantiations.end())

continue;

eraseTokens(eqtok, tok2);

eqtok->deleteThis();

}

}

}

void TemplateSimplifier::simplifyTemplateAliases()

{

std::list<TokenAndName>::iterator it1, it2;

for (it1 = mTemplateInstantiations.begin(); it1 != mTemplateInstantiations.end();) {

TokenAndName &templateAlias = *it1;

++it1;

Token *startToken = templateAlias.token;

while (Token::Match(startToken->tokAt(-2), "%name% :: %name%"))

startToken = startToken->tokAt(-2);

if (!Token::Match(startToken->tokAt(-4), "> using %name% = %name% ::|<"))

continue;

const std::string aliasName(startToken->strAt(-2));

const Token * const aliasToken1 = startToken;

// Get start token for alias

startToken = startToken->tokAt(-5);

while (Token::Match(startToken, "%name%|<|>|>>|,"))

startToken = startToken->previous();

if (!Token::Match(startToken, "[;{}] template <"))

continue;

// alias parameters..

std::vector<const Token *> aliasParameters;

getTemplateParametersInDeclaration(startToken->tokAt(3), aliasParameters);

std::map<std::string, unsigned int> aliasParameterNames;

for (unsigned int argnr = 0; argnr < aliasParameters.size(); ++argnr)

aliasParameterNames[aliasParameters[argnr]->str()] = argnr;

// Look for alias usages..

const Token *endToken = nullptr;

for (it2 = it1; it2 != mTemplateInstantiations.end(); ++it2) {

TokenAndName &aliasUsage = *it2;

if (aliasUsage.name != aliasName)

continue;

std::vector<std::pair<Token *, Token *>> args;

Token *tok2 = aliasUsage.token->tokAt(2);

while (tok2) {

Token * const start = tok2;

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

if (tok2->link() && Token::Match(tok2, "(|<|["))

tok2 = tok2->link();

tok2 = tok2->next();

}

args.emplace_back(start, tok2);

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

tok2 = tok2->next();

} else {

break;

}

}

if (!tok2 || tok2->str() != ">" || args.size() != aliasParameters.size())

continue;

// Replace template alias code..

aliasUsage.name = templateAlias.name;

if (aliasUsage.name.find(' ') == std::string::npos) {

aliasUsage.token->str(templateAlias.token->str());

} else {

tok2 = TokenList::copyTokens(aliasUsage.token, aliasToken1, templateAlias.token, true);

deleteToken(aliasUsage.token);

aliasUsage.token = tok2;

}

tok2 = aliasUsage.token->next(); // the '<'

const Token * const endToken1 = templateAlias.token->next()->findClosingBracket();

const Token * const endToken2 = TokenList::copyTokens(tok2, templateAlias.token->tokAt(2), endToken1->previous(), false);

for (const Token *tok1 = templateAlias.token->next(); tok2 != endToken2; tok1 = tok1->next(), tok2 = tok2->next()) {

if (!tok2->isName())

continue;

if (aliasParameterNames.find(tok2->str()) == aliasParameterNames.end()) {

// Create template instance..

if (Token::Match(tok1, "%name% <")) {

const std::list<TokenAndName>::iterator it = std::find_if(mTemplateInstantiations.begin(),

mTemplateInstantiations.end(),

FindToken(tok1));

if (it != mTemplateInstantiations.end())

mTemplateInstantiations.emplace_back(tok2, it->scope, it->name);

}

continue;

}

const unsigned int argnr = aliasParameterNames[tok2->str()];

const Token * const fromStart = args[argnr].first;

const Token * const fromEnd = args[argnr].second->previous();

Token * const destToken = tok2;

tok2 = TokenList::copyTokens(tok2, fromStart, fromEnd, true);

if (tok2 == destToken->next())

tok2 = destToken;

destToken->deleteThis();

}

endToken = endToken1->next();

// Remove alias usage code (parameters)

Token::eraseTokens(tok2, args.back().second);

}

if (endToken) {

// Remove all template instantiations in template alias

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

if (!Token::Match(tok, "%name% <"))

continue;

std::list<TokenAndName>::iterator it = std::find_if(mTemplateInstantiations.begin(),

mTemplateInstantiations.end(),

FindToken(tok));

if (it == mTemplateInstantiations.end())

continue;

std::list<TokenAndName>::iterator next = it;

++next;

if (it == it1)

it1 = next;

mTemplateInstantiations.erase(it,next);

}

Token::eraseTokens(startToken, endToken);

}

}

}

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

{

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

// return false;

if (numberOfArguments != 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;

}

// Utility function for TemplateSimplifier::getTemplateNamePosition, that works on template member functions,

// hence this pattern: "> %type% [%type%] < ... > :: %type% ("

static bool getTemplateNamePositionTemplateMember(const Token *tok, int &namepos)

{

namepos = 2;

while (tok && tok->next()) {

if (Token::Match(tok->next(), ";|{"))

return false;

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

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

if (closing && Token::Match(closing->next(), ":: ~| %name% (")) {

if (closing->strAt(1) == "~")

closing = closing->next();

while (tok && tok->next() != closing->next()) {

tok = tok->next();

namepos++;

}

return true;

}

}

tok = tok->next();

namepos++;

}

return false;

}

int TemplateSimplifier::getTemplateNamePosition(const Token *tok, bool forward)

{

// get the position of the template name

int namepos = 0, starAmpPossiblePosition = 0;

if ((forward && Token::Match(tok, "> class|struct|union %type% :|<|;")) ||

(!forward && Token::Match(tok, "> class|struct|union %type% {|:|<")))

namepos = 2;

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

namepos = 2;

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

Token::simpleMatch(tok->tokAt(3)->findClosingBracket(), "> ("))

namepos = 2;

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

namepos = 3;

else if (getTemplateNamePositionTemplateMember(tok, namepos))

;

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(

const Token *templateDeclarationToken,

const std::string &fullName,

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

const std::string &newName,

bool copy)

{

std::list<ScopeInfo2> scopeInfo;

bool inTemplateDefinition = false;

const Token *startOfTemplateDeclaration = nullptr;

const Token *endOfTemplateDefinition = nullptr;

const Token * const templateDeclarationNameToken = templateDeclarationToken->tokAt(getTemplateNamePosition(templateDeclarationToken));

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

if (Token::Match(tok3, "}|namespace|class|struct|union")) {

setScopeInfo(tok3, &scopeInfo);

continue;

}

if (inTemplateDefinition) {

if (!endOfTemplateDefinition && tok3->str() == "{")

endOfTemplateDefinition = tok3->link();

if (tok3 == endOfTemplateDefinition) {

inTemplateDefinition = false;

startOfTemplateDeclaration = nullptr;

}

}

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

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

std::vector<const Token *> localTypeParametersInDeclaration;

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

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

inTemplateDefinition = false; // Partial specialization

else

inTemplateDefinition = true;

} else {

inTemplateDefinition = false; // Only template instantiation

}

startOfTemplateDeclaration = tok3;

}

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

tok3 = tok3->link();