Cppcheck
templatesimplifier.cpp
Go to the documentation of this file.
1 /*
2  * Cppcheck - A tool for static C/C++ code analysis
3  * Copyright (C) 2007-2024 Cppcheck team.
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #include "templatesimplifier.h"
20 
21 #include "errorlogger.h"
22 #include "errortypes.h"
23 #include "mathlib.h"
24 #include "settings.h"
25 #include "standards.h"
26 #include "token.h"
27 #include "tokenize.h"
28 #include "tokenlist.h"
29 #include "utils.h"
30 
31 #include <algorithm>
32 #include <cassert>
33 #include <iostream>
34 #include <map>
35 #include <memory>
36 #include <stack>
37 #include <type_traits>
38 #include <utility>
39 
40 static Token *skipRequires(Token *tok)
41 {
42  if (!Token::simpleMatch(tok, "requires"))
43  return tok;
44 
45  while (Token::Match(tok, "%oror%|&&|requires %name%|(")) {
46  Token *after = tok->next();
47  if (after->str() == "(") {
48  tok = after->link()->next();
49  continue;
50  }
51  if (Token::simpleMatch(after, "requires (") && Token::simpleMatch(after->linkAt(1), ") {")) {
52  tok = after->linkAt(1)->linkAt(1)->next();
53  continue;
54  }
55  while (Token::Match(after, "%name% :: %name%"))
56  after = after->tokAt(2);
57  if (Token::Match(after, "%name% <")) {
58  after = after->next()->findClosingBracket();
59  tok = after ? after->next() : nullptr;
60  } else
61  break;
62  }
63  return tok;
64 }
65 
66 namespace {
67  class FindToken {
68  public:
69  explicit FindToken(const Token *token) : mToken(token) {}
70  bool operator()(const TemplateSimplifier::TokenAndName &tokenAndName) const {
71  return tokenAndName.token() == mToken;
72  }
73  private:
74  const Token * const mToken;
75  };
76 
77  class FindName {
78  public:
79  explicit FindName(std::string name) : mName(std::move(name)) {}
80  bool operator()(const TemplateSimplifier::TokenAndName &tokenAndName) const {
81  return tokenAndName.name() == mName;
82  }
83  private:
84  const std::string mName;
85  };
86 
87  class FindFullName {
88  public:
89  explicit FindFullName(std::string fullName) : mFullName(std::move(fullName)) {}
90  bool operator()(const TemplateSimplifier::TokenAndName &tokenAndName) const {
91  return tokenAndName.fullName() == mFullName;
92  }
93  private:
94  const std::string mFullName;
95  };
96 }
97 
99  mToken(token), mScope(std::move(scope)), mName(mToken ? mToken->str() : ""),
100  mFullName(mScope.empty() ? mName : (mScope + " :: " + mName)),
101  mNameToken(nullptr), mParamEnd(nullptr), mFlags(0)
102 {
103  if (mToken) {
104  if (mToken->strAt(1) == "<") {
105  const Token *end = mToken->next()->findClosingBracket();
106  if (end && end->strAt(1) == "(") {
107  isFunction(true);
108  }
109  }
111  }
112 }
113 
114 TemplateSimplifier::TokenAndName::TokenAndName(Token *token, std::string scope, const Token *nameToken, const Token *paramEnd) :
115  mToken(token), mScope(std::move(scope)), mName(nameToken->str()),
116  mFullName(mScope.empty() ? mName : (mScope + " :: " + mName)),
117  mNameToken(nameToken), mParamEnd(paramEnd), mFlags(0)
118 {
119  // only set flags for declaration
120  if (mToken && mNameToken && mParamEnd) {
121  isSpecialization(Token::simpleMatch(mToken, "template < >"));
122 
123  if (!isSpecialization()) {
124  if (Token::simpleMatch(mToken->next()->findClosingBracket(), "> template <")) {
125  const Token * temp = mNameToken->tokAt(-2);
126  while (Token::Match(temp, ">|%name% ::")) {
127  if (temp->str() == ">")
128  temp = temp->findOpeningBracket()->previous();
129  else
130  temp = temp->tokAt(-2);
131  }
132  isPartialSpecialization(temp->strAt(1) == "<");
133  } else
135  }
136 
137  isAlias(mParamEnd->strAt(1) == "using");
138 
139  if (isAlias() && isPartialSpecialization()) {
140  throw InternalError(mToken, "partial specialization of alias templates is not permitted", InternalError::SYNTAX);
141  }
142  if (isAlias() && isSpecialization()) {
143  throw InternalError(mToken, "explicit specialization of alias templates is not permitted", InternalError::SYNTAX);
144  }
145 
146  isFriend(mParamEnd->strAt(1) == "friend");
147  const Token *next = mParamEnd->next();
148  if (isFriend())
149  next = next->next();
150 
151  isClass(Token::Match(next, "class|struct|union %name% <|{|:|;|::"));
152  if (mToken->strAt(1) == "<" && !isSpecialization()) {
153  const Token *end = mToken->next()->findClosingBracket();
154  isVariadic(end && Token::findmatch(mToken->tokAt(2), "%name% ...", end));
155  }
156  const Token *tok1 = mNameToken->next();
157  if (tok1->str() == "<") {
158  const Token *closing = tok1->findClosingBracket();
159  if (closing)
160  tok1 = closing->next();
161  else
162  throw InternalError(mToken, "unsupported syntax", InternalError::SYNTAX);
163  }
164  isFunction(tok1->str() == "(");
165  isVariable(!isClass() && !isAlias() && !isFriend() && Token::Match(tok1, "=|;"));
166  if (!isFriend()) {
167  if (isVariable())
168  isForwardDeclaration(tok1->str() == ";");
169  else if (!isAlias()) {
170  if (isFunction())
171  tok1 = tok1->link()->next();
172  while (tok1 && !Token::Match(tok1, ";|{")) {
173  if (tok1->str() == "<")
174  tok1 = tok1->findClosingBracket();
175  else if (Token::Match(tok1, "(|[") && tok1->link())
176  tok1 = tok1->link();
177  if (tok1)
178  tok1 = tok1->next();
179  }
180  if (tok1)
181  isForwardDeclaration(tok1->str() == ";");
182  }
183  }
184  // check for member class or function and adjust scope
185  if ((isFunction() || isClass()) &&
186  (mNameToken->strAt(-1) == "::" || Token::simpleMatch(mNameToken->tokAt(-2), ":: ~"))) {
187  const Token * start = mNameToken;
188  if (start->strAt(-1) == "~")
189  start = start->previous();
190  const Token *end = start;
191 
192  while (start && (Token::Match(start->tokAt(-2), "%name% ::") ||
193  (Token::simpleMatch(start->tokAt(-2), "> ::") &&
194  start->tokAt(-2)->findOpeningBracket() &&
195  Token::Match(start->tokAt(-2)->findOpeningBracket()->previous(), "%name% <")))) {
196  if (start->strAt(-2) == ">")
197  start = start->tokAt(-2)->findOpeningBracket()->previous();
198  else
199  start = start->tokAt(-2);
200  }
201 
202  if (start && start != end) {
203  if (!mScope.empty())
204  mScope += " ::";
205  while (start && start->next() != end) {
206  if (start->str() == "<")
207  start = start->findClosingBracket();
208  else {
209  if (!mScope.empty())
210  mScope += " ";
211  mScope += start->str();
212  }
213  start = start->next();
214  }
215  if (start)
216  mFullName = mScope.empty() ? mName : (mScope + " :: " + mName);
217  }
218  }
219  }
220 
221  // make sure at most only one family flag is set
222  assert(isClass() ? !(isFunction() || isVariable()) : true);
223  assert(isFunction() ? !(isClass() || isVariable()) : true);
224  assert(isVariable() ? !(isClass() || isFunction()) : true);
225 
226  if (mToken)
228 }
229 
231  mToken(other.mToken), mScope(other.mScope), mName(other.mName), mFullName(other.mFullName),
232  mNameToken(other.mNameToken), mParamEnd(other.mParamEnd), mFlags(other.mFlags)
233 {
234  if (mToken)
236 }
237 
239 {
240  if (mToken && mToken->templateSimplifierPointers())
241  mToken->templateSimplifierPointers()->erase(this);
242 }
243 
244 std::string TemplateSimplifier::TokenAndName::dump(const std::vector<std::string>& fileNames) const {
245  std::string ret = " <TokenAndName name=\"" + ErrorLogger::toxml(mName) + "\" file=\"" + ErrorLogger::toxml(fileNames.at(mToken->fileIndex())) + "\" line=\"" + std::to_string(mToken->linenr()) + "\">\n";
246  for (const Token* tok = mToken; tok && !Token::Match(tok, "[;{}]"); tok = tok->next())
247  ret += " <template-token str=\"" + ErrorLogger::toxml(tok->str()) + "\"/>\n";
248  return ret + " </TokenAndName>\n";
249 }
250 
252 {
253  if (mParamEnd)
254  return mParamEnd->tokAt(4);
255  return nullptr;
256 }
257 
259 {
260  if (aliasStartToken())
261  return Token::findsimplematch(aliasStartToken(), ";");
262  return nullptr;
263 }
264 
266 {
267  const Token *end = aliasEndToken();
268 
269  for (const Token *tok1 = aliasStartToken(); tok1 != end; tok1 = tok1->next()) {
270  if (tok1 == tok)
271  return true;
272  }
273  return false;
274 }
275 
277  : mTokenizer(tokenizer), mTokenList(mTokenizer.list), mSettings(mTokenizer.getSettings()),
279 {}
280 
282 {
283  // check for more complicated syntax errors when using templates..
284  for (const Token *tok = mTokenList.front(); tok; tok = tok->next()) {
285  // skip executing scopes (ticket #3183)..
286  if (Token::simpleMatch(tok, "( {")) {
287  tok = tok->link();
288  if (!tok)
289  syntaxError(nullptr);
290  }
291  // skip executing scopes..
292  const Token *start = Tokenizer::startOfExecutableScope(tok);
293  if (start) {
294  tok = start->link();
295  }
296 
297  // skip executing scopes (ticket #1985)..
298  else if (Token::simpleMatch(tok, "try {")) {
299  tok = tok->next()->link();
300  while (Token::simpleMatch(tok, "} catch (")) {
301  tok = tok->linkAt(2);
302  if (Token::simpleMatch(tok, ") {"))
303  tok = tok->next()->link();
304  }
305  }
306 
307  if (!tok)
308  syntaxError(nullptr);
309  // not start of statement?
310  if (tok->previous() && !Token::Match(tok, "[;{}]"))
311  continue;
312 
313  // skip starting tokens.. ;;; typedef typename foo::bar::..
314  while (Token::Match(tok, ";|{"))
315  tok = tok->next();
316  while (Token::Match(tok, "typedef|typename"))
317  tok = tok->next();
318  while (Token::Match(tok, "%type% ::"))
319  tok = tok->tokAt(2);
320  if (!tok)
321  break;
322 
323  // template variable or type..
324  if (Token::Match(tok, "%type% <") && !Token::simpleMatch(tok, "template")) {
325  // these are used types..
326  std::set<std::string> usedtypes;
327 
328  // parse this statement and see if the '<' and '>' are matching
329  unsigned int level = 0;
330  for (const Token *tok2 = tok; tok2 && !Token::simpleMatch(tok2, ";"); tok2 = tok2->next()) {
331  if (Token::simpleMatch(tok2, "{") &&
332  (!Token::Match(tok2->previous(), ">|%type%") || Token::simpleMatch(tok2->link(), "} ;")))
333  break;
334  if (tok2->str() == "(")
335  tok2 = tok2->link();
336  else if (tok2->str() == "<") {
337  bool inclevel = false;
338  if (Token::simpleMatch(tok2->previous(), "operator <"))
339  ;
340  else if (level == 0 && Token::Match(tok2->previous(), "%type%")) {
341  // @todo add better expression detection
342  if (!(Token::Match(tok2->next(), "*| %type%|%num% ;") ||
343  Token::Match(tok2->next(), "*| %type% . %type% ;"))) {
344  inclevel = true;
345  }
346  } else if (tok2->next() && tok2->next()->isStandardType() && !Token::Match(tok2->tokAt(2), "(|{"))
347  inclevel = true;
348  else if (Token::simpleMatch(tok2, "< typename"))
349  inclevel = true;
350  else if (Token::Match(tok2->tokAt(-2), "<|, %type% <") && usedtypes.find(tok2->previous()->str()) != usedtypes.end())
351  inclevel = true;
352  else if (Token::Match(tok2, "< %type%") && usedtypes.find(tok2->next()->str()) != usedtypes.end())
353  inclevel = true;
354  else if (Token::Match(tok2, "< %type%")) {
355  // is the next token a type and not a variable/constant?
356  // assume it's a type if there comes another "<"
357  const Token *tok3 = tok2->next();
358  while (Token::Match(tok3, "%type% ::"))
359  tok3 = tok3->tokAt(2);
360  if (Token::Match(tok3, "%type% <"))
361  inclevel = true;
362  } else if (tok2->strAt(-1) == ">")
363  syntaxError(tok);
364 
365  if (inclevel) {
366  ++level;
367  if (Token::Match(tok2->tokAt(-2), "<|, %type% <"))
368  usedtypes.insert(tok2->previous()->str());
369  }
370  } else if (tok2->str() == ">") {
371  if (level > 0)
372  --level;
373  } else if (tok2->str() == ">>") {
374  if (level > 0)
375  --level;
376  if (level > 0)
377  --level;
378  }
379  }
380  if (level > 0)
381  syntaxError(tok);
382  }
383  }
384 }
385 
387 {
388  unsigned int numberOfParameters = 1;
389 
390  if (!tok)
391  return 0;
392  if (tok->str() != "<")
393  return 0;
394  if (Token::Match(tok->previous(), "%var% <"))
395  return 0;
396  tok = tok->next();
397  if (!tok || tok->str() == ">")
398  return 0;
399 
400  unsigned int level = 0;
401 
402  while (tok) {
403  // skip template template
404  if (level == 0 && Token::simpleMatch(tok, "template <")) {
405  const Token *closing = tok->next()->findClosingBracket();
406  if (closing) {
407  if (closing->str() == ">>")
408  return numberOfParameters;
409  tok = closing->next();
410  if (!tok)
411  syntaxError(tok);
412  if (Token::Match(tok, ">|>>|>>="))
413  return numberOfParameters;
414  if (tok->str() == ",") {
415  ++numberOfParameters;
416  tok = tok->next();
417  continue;
418  }
419  } else
420  return 0;
421  }
422 
423  // skip const/volatile
424  if (Token::Match(tok, "const|volatile"))
425  tok = tok->next();
426 
427  // skip struct/union
428  if (Token::Match(tok, "struct|union"))
429  tok = tok->next();
430 
431  // Skip '&'
432  if (Token::Match(tok, "& ::| %name%"))
433  tok = tok->next();
434 
435  // Skip variadic types (Ticket #5774, #6059, #6172)
436  if (Token::simpleMatch(tok, "...")) {
437  if ((tok->previous()->isName() && !Token::Match(tok->tokAt(-2), "<|,|::")) ||
438  (!tok->previous()->isName() && !Token::Match(tok->previous(), ">|&|&&|*")))
439  return 0; // syntax error
440  tok = tok->next();
441  if (!tok)
442  return 0;
443  if (tok->str() == ">") {
444  if (level == 0)
445  return numberOfParameters;
446  --level;
447  } else if (tok->str() == ">>" || tok->str() == ">>=") {
448  if (level == 1)
449  return numberOfParameters;
450  level -= 2;
451  } else if (tok->str() == ",") {
452  if (level == 0)
453  ++numberOfParameters;
454  tok = tok->next();
455  continue;
456  }
457  }
458 
459  // Skip '=', '?', ':'
460  if (Token::Match(tok, "=|?|:"))
461  tok = tok->next();
462  if (!tok)
463  return 0;
464 
465  // Skip links
466  if (Token::Match(tok, "(|{")) {
467  tok = tok->link();
468  if (tok)
469  tok = tok->next();
470  if (!tok)
471  return 0;
472  if (tok->str() == ">" && level == 0)
473  return numberOfParameters;
474  if ((tok->str() == ">>" || tok->str() == ">>=") && level == 1)
475  return numberOfParameters;
476  if (tok->str() == ",") {
477  if (level == 0)
478  ++numberOfParameters;
479  tok = tok->next();
480  }
481  continue;
482  }
483 
484  // skip std::
485  if (tok->str() == "::")
486  tok = tok->next();
487  while (Token::Match(tok, "%name% ::")) {
488  tok = tok->tokAt(2);
489  if (tok && tok->str() == "*") // Ticket #5759: Class member pointer as a template argument; skip '*'
490  tok = tok->next();
491  }
492  if (!tok)
493  return 0;
494 
495  // num/type ..
496  if (!tok->isNumber() && tok->tokType() != Token::eChar && tok->tokType() != Token::eString && !tok->isName() && !tok->isOp())
497  return 0;
498  tok = tok->next();
499  if (!tok)
500  return 0;
501 
502  // * / const
503  while (Token::Match(tok, "*|&|&&|const"))
504  tok = tok->next();
505 
506  if (!tok)
507  return 0;
508 
509  // Function pointer or prototype..
510  while (Token::Match(tok, "(|[")) {
511  if (!tok->link())
512  syntaxError(tok);
513 
514  tok = tok->link()->next();
515  while (Token::Match(tok, "const|volatile")) // Ticket #5786: Skip function cv-qualifiers
516  tok = tok->next();
517  }
518  if (!tok)
519  return 0;
520 
521  // inner template
522  if (tok->str() == "<" && tok->previous()->isName()) {
523  ++level;
524  tok = tok->next();
525  }
526 
527  if (!tok)
528  return 0;
529 
530  // ,/>
531  while (Token::Match(tok, ">|>>|>>=")) {
532  if (level == 0)
533  return tok->str() == ">" && !Token::Match(tok->next(), "%num%") ? numberOfParameters : 0;
534  --level;
535  if (tok->str() == ">>" || tok->str() == ">>=") {
536  if (level == 0)
537  return !Token::Match(tok->next(), "%num%") ? numberOfParameters : 0;
538  --level;
539  }
540  tok = tok->next();
541 
542  if (Token::Match(tok, "(|["))
543  tok = tok->link()->next();
544 
545  if (!tok)
546  return 0;
547  }
548 
549  if (tok->str() != ",")
550  continue;
551  if (level == 0)
552  ++numberOfParameters;
553  tok = tok->next();
554  }
555  return 0;
556 }
557 
558 template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>
560 {
561  if (Token::simpleMatch(tok, "template <")) {
562  tok = tok->next()->findClosingBracket();
563  if (tok)
564  tok = tok->next();
565  }
566 
567  if (!tok)
568  return nullptr;
569 
570  T * tok2 = tok;
571  bool in_init = false;
572  while (tok2 && !Token::Match(tok2, ";|{")) {
573  if (tok2->str() == "<")
574  tok2 = tok2->findClosingBracket();
575  else if (Token::Match(tok2, "(|[") && tok2->link())
576  tok2 = tok2->link();
577  else if (tok2->str() == ":")
578  in_init = true;
579  else if (in_init && Token::Match(tok2, "%name% (|{")) {
580  tok2 = tok2->linkAt(1);
581  if (tok2->strAt(1) == "{")
582  in_init = false;
583  }
584  if (tok2)
585  tok2 = tok2->next();
586  }
587  if (tok2 && tok2->str() == "{") {
588  tok = tok2->link();
589  if (tok && tok->strAt(1) == ";")
590  tok = tok->next();
591  } else if (tok2 && tok2->str() == ";")
592  tok = tok2;
593  else
594  tok = nullptr;
595 
596  return tok;
597 }
598 
600 {
601  return findTemplateDeclarationEndImpl(tok);
602 }
603 
605 {
606  return findTemplateDeclarationEndImpl(tok);
607 }
608 
610 {
611  if (!begin || begin == end)
612  return;
613 
614  while (begin->next() && begin->next() != end) {
615  begin->deleteNext();
616  }
617 }
618 
620 {
621  if (tok->next())
622  tok->next()->deletePrevious();
623  else
624  tok->deleteThis();
625 }
626 
627 static void invalidateForwardDecls(const Token* beg, const Token* end, std::map<Token*, Token*>* forwardDecls) {
628  if (!forwardDecls)
629  return;
630  for (auto& fwd : *forwardDecls) {
631  for (const Token* tok = beg; tok != end; tok = tok->next())
632  if (fwd.second == tok) {
633  fwd.second = nullptr;
634  break;
635  }
636  }
637 }
638 
639 bool TemplateSimplifier::removeTemplate(Token *tok, std::map<Token*, Token*>* forwardDecls)
640 {
641  if (!Token::simpleMatch(tok, "template <"))
642  return false;
643 
644  Token *end = findTemplateDeclarationEnd(tok);
645  if (end && end->next()) {
646  invalidateForwardDecls(tok, end->next(), forwardDecls);
647  eraseTokens(tok, end->next());
648  deleteToken(tok);
649  return true;
650  }
651 
652  return false;
653 }
654 
656 {
657  bool codeWithTemplates = false;
658  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
659  if (!Token::simpleMatch(tok, "template <"))
660  continue;
661  // ignore template template parameter
662  if (tok->strAt(-1) == "<" || tok->strAt(-1) == ",")
663  continue;
664  // ignore nested template
665  if (tok->strAt(-1) == ">")
666  continue;
667  // skip to last nested template parameter
668  const Token *tok1 = tok;
669  while (tok1 && tok1->next()) {
670  const Token *closing = tok1->next()->findClosingBracket();
671  if (!Token::simpleMatch(closing, "> template <"))
672  break;
673  tok1 = closing->next();
674  }
675  if (!Token::Match(tok, "%any% %any%"))
676  syntaxError(tok);
677  if (tok->strAt(2)=="typename" &&
678  !Token::Match(tok->tokAt(3), "%name%|...|,|=|>"))
679  syntaxError(tok->next());
680  codeWithTemplates = true;
681  const Token * const parmEnd = tok1->next()->findClosingBracket();
682  for (const Token *tok2 = parmEnd; tok2; tok2 = tok2->next()) {
683  if (tok2->str() == "(" && tok2->link())
684  tok2 = tok2->link();
685  else if (tok2->str() == ")")
686  break;
687  // skip decltype(...)
688  else if (Token::simpleMatch(tok2, "decltype ("))
689  tok2 = tok2->linkAt(1);
690  else if (Token::Match(tok2, "{|=|;")) {
691  const int namepos = getTemplateNamePosition(parmEnd);
692  if (namepos > 0) {
693  TokenAndName decl(tok, tok->scopeInfo()->name, parmEnd->tokAt(namepos), parmEnd);
694  if (decl.isForwardDeclaration()) {
695  // Declaration => add to mTemplateForwardDeclarations
696  mTemplateForwardDeclarations.emplace_back(std::move(decl));
697  } else {
698  // Implementation => add to mTemplateDeclarations
699  mTemplateDeclarations.emplace_back(std::move(decl));
700  }
701  Token *end = findTemplateDeclarationEnd(tok);
702  if (end)
703  tok = end;
704  break;
705  }
706  }
707  }
708  }
709  return codeWithTemplates;
710 }
711 
712 void TemplateSimplifier::addInstantiation(Token *token, const std::string &scope)
713 {
714  simplifyTemplateArgs(token->tokAt(2), token->next()->findClosingBracket());
715 
716  TokenAndName instantiation(token, scope);
717 
718  // check if instantiation already exists before adding it
719  const std::list<TokenAndName>::const_iterator it = std::find(mTemplateInstantiations.cbegin(),
721  instantiation);
722 
723  if (it == mTemplateInstantiations.cend())
724  mTemplateInstantiations.emplace_back(std::move(instantiation));
725 }
726 
727 static const Token* getFunctionToken(const Token* nameToken)
728 {
729  if (Token::Match(nameToken, "%name% ("))
730  return nameToken->next();
731 
732  if (Token::Match(nameToken, "%name% <")) {
733  const Token* end = nameToken->next()->findClosingBracket();
734  if (Token::simpleMatch(end, "> ("))
735  return end->next();
736  }
737 
738  return nullptr;
739 }
740 
741 static void getFunctionArguments(const Token* nameToken, std::vector<const Token*>& args)
742 {
743  const Token* functionToken = getFunctionToken(nameToken);
744  if (!functionToken)
745  return;
746 
747  const Token* argToken = functionToken->next();
748 
749  if (argToken->str() == ")")
750  return;
751 
752  args.push_back(argToken);
753 
754  while ((argToken = argToken->nextArgumentBeforeCreateLinks2()))
755  args.push_back(argToken);
756 }
757 
758 static bool isConstMethod(const Token* nameToken)
759 {
760  const Token* functionToken = getFunctionToken(nameToken);
761  if (!functionToken)
762  return false;
763  const Token* endToken = functionToken->link();
764  return Token::simpleMatch(endToken, ") const");
765 }
766 
767 static bool areAllParamsTypes(const std::vector<const Token *> &params)
768 {
769  if (params.empty())
770  return false;
771 
772  return std::all_of(params.cbegin(), params.cend(), [](const Token* param) {
773  return Token::Match(param->previous(), "typename|class %name% ,|>");
774  });
775 }
776 
778 {
779  std::multimap<std::string, const TokenAndName *> functionNameMap;
780 
781  for (const auto & decl : mTemplateDeclarations) {
782  if (decl.isFunction())
783  functionNameMap.insert(std::make_pair(decl.name(), &decl));
784  }
785 
786  for (const auto & decl : mTemplateForwardDeclarations) {
787  if (decl.isFunction())
788  functionNameMap.insert(std::make_pair(decl.name(), &decl));
789  }
790 
791  const Token *skip = nullptr;
792 
793  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
794 
795  // template definition.. skip it
796  if (Token::simpleMatch(tok, "template <")) {
797  tok = tok->next()->findClosingBracket();
798  if (!tok)
799  break;
800 
801  const bool isUsing = tok->strAt(1) == "using";
802  if (isUsing && Token::Match(tok->tokAt(2), "%name% <")) {
803  // Can't have specialized type alias so ignore it
804  Token *tok2 = Token::findsimplematch(tok->tokAt(3), ";");
805  if (tok2)
806  tok = tok2;
807  } else if (tok->strAt(-1) == "<") {
808  // Don't ignore user specialization but don't consider it an instantiation.
809  // Instantiations in return type, function parameters, and executable code
810  // are not ignored.
811  const unsigned int pos = getTemplateNamePosition(tok);
812  if (pos > 0)
813  skip = tok->tokAt(pos);
814  } else {
815  // #7914
816  // Ignore template instantiations within template definitions: they will only be
817  // handled if the definition is actually instantiated
818 
819  Token * tok2 = findTemplateDeclarationEnd(tok->next());
820  if (tok2)
821  tok = tok2;
822  }
823  } else if (Token::Match(tok, "template using %name% <")) {
824  // Can't have specialized type alias so ignore it
825  Token *tok2 = Token::findsimplematch(tok->tokAt(3), ";");
826  if (tok2)
827  tok = tok2;
828  } else if (Token::Match(tok, "using %name% <")) {
829  // Can't have specialized type alias so ignore it
830  Token *tok2 = Token::findsimplematch(tok->tokAt(2), ";");
831  if (tok2)
832  tok = tok2;
833  } else if (Token::Match(tok->previous(), "(|{|}|;|=|>|<<|:|.|*|&|return|<|,|!|[ %name% ::|<|(") ||
834  Token::Match(tok->previous(), "%type% %name% ::|<") ||
835  Token::Match(tok->tokAt(-2), "[,:] private|protected|public %name% ::|<")) {
836  std::string scopeName = tok->scopeInfo()->name;
837  std::string qualification;
838  Token * qualificationTok = tok;
839  while (Token::Match(tok, "%name% :: %name%")) {
840  qualification += (qualification.empty() ? "" : " :: ") + tok->str();
841  tok = tok->tokAt(2);
842  }
843 
844  // skip specialization
845  if (tok == skip) {
846  skip = nullptr;
847  continue;
848  }
849 
850  // look for function instantiation with type deduction
851  if (tok->strAt(1) == "(") {
852  std::vector<const Token *> instantiationArgs;
853  getFunctionArguments(tok, instantiationArgs);
854 
855  std::string fullName;
856  if (!qualification.empty())
857  fullName = qualification + " :: " + tok->str();
858  else if (!scopeName.empty())
859  fullName = scopeName + " :: " + tok->str();
860  else
861  fullName = tok->str();
862 
863  // get all declarations with this name
864  auto range = functionNameMap.equal_range(tok->str());
865  for (auto pos = range.first; pos != range.second; ++pos) {
866  // look for declaration with same qualification or constructor with same qualification
867  if (pos->second->fullName() == fullName ||
868  (pos->second->scope() == fullName && tok->str() == pos->second->name())) {
869  std::vector<const Token *> templateParams;
870  getTemplateParametersInDeclaration(pos->second->token()->tokAt(2), templateParams);
871 
872  // todo: handle more than one template parameter
873  if (templateParams.size() != 1 || !areAllParamsTypes(templateParams))
874  continue;
875 
876  std::vector<const Token *> declarationParams;
877  getFunctionArguments(pos->second->nameToken(), declarationParams);
878 
879  // function argument counts must match
880  if (instantiationArgs.empty() || instantiationArgs.size() != declarationParams.size())
881  continue;
882 
883  size_t match = 0;
884  size_t argMatch = 0;
885  for (size_t i = 0; i < declarationParams.size(); ++i) {
886  // fixme: only type deduction from literals is supported
887  const bool isArgLiteral = Token::Match(instantiationArgs[i], "%num%|%str%|%char%|%bool% ,|)");
888  if (isArgLiteral && Token::Match(declarationParams[i], "const| %type% &| %name%| ,|)")) {
889  match++;
890 
891  // check if parameter types match
892  if (templateParams[0]->str() == declarationParams[i]->str())
893  argMatch = i;
894  else {
895  // todo: check if non-template args match for function overloads
896  }
897  }
898  }
899 
900  if (match == declarationParams.size()) {
901  const Token *arg = instantiationArgs[argMatch];
902  tok->insertToken(">");
903  switch (arg->tokType()) {
904  case Token::eBoolean:
905  tok->insertToken("bool");
906  break;
907  case Token::eChar:
908  if (arg->isLong())
909  tok->insertToken("wchar_t");
910  else
911  tok->insertToken("char");
912  break;
913  case Token::eString:
914  tok->insertToken("*");
915  if (arg->isLong())
916  tok->insertToken("wchar_t");
917  else
918  tok->insertToken("char");
919  tok->insertToken("const");
920  break;
921  case Token::eNumber: {
922  MathLib::value num(arg->str());
923  if (num.isFloat()) {
924  // MathLib::getSuffix doesn't work for floating point numbers
925  const char suffix = arg->str().back();
926  if (suffix == 'f' || suffix == 'F')
927  tok->insertToken("float");
928  else if (suffix == 'l' || suffix == 'L') {
929  tok->insertToken("double");
930  tok->next()->isLong(true);
931  } else
932  tok->insertToken("double");
933  } else if (num.isInt()) {
934  std::string suffix = MathLib::getSuffix(tok->strAt(3));
935  if (suffix.find("LL") != std::string::npos) {
936  tok->insertToken("long");
937  tok->next()->isLong(true);
938  } else if (suffix.find('L') != std::string::npos)
939  tok->insertToken("long");
940  else
941  tok->insertToken("int");
942  if (suffix.find('U') != std::string::npos)
943  tok->next()->isUnsigned(true);
944  }
945  break;
946  }
947  default:
948  break;
949  }
950  tok->insertToken("<");
951  break;
952  }
953  }
954  }
955  }
956 
957  if (!Token::Match(tok, "%name% <") ||
958  Token::Match(tok, "const_cast|dynamic_cast|reinterpret_cast|static_cast"))
959  continue;
960 
961  if (tok == skip) {
962  skip = nullptr;
963  continue;
964  }
965 
966  // Add inner template instantiations first => go to the ">"
967  // and then parse backwards, adding all seen instantiations
968  Token *tok2 = tok->next()->findClosingBracket();
969 
970  // parse backwards and add template instantiations
971  // TODO
972  for (; tok2 && tok2 != tok; tok2 = tok2->previous()) {
973  if (Token::Match(tok2, ",|< %name% <") &&
974  (tok2->strAt(3) == ">" || templateParameters(tok2->tokAt(2)))) {
975  addInstantiation(tok2->next(), tok->scopeInfo()->name);
976  } else if (Token::Match(tok2->next(), "class|struct"))
977  tok2->deleteNext();
978  }
979 
980  // Add outer template..
981  if (templateParameters(tok->next()) || tok->strAt(2) == ">") {
982  while (true) {
983  const std::string fullName = scopeName + (scopeName.empty()?"":" :: ") +
984  qualification + (qualification.empty()?"":" :: ") + tok->str();
985  const std::list<TokenAndName>::const_iterator it = std::find_if(mTemplateDeclarations.cbegin(), mTemplateDeclarations.cend(), FindFullName(fullName));
986  if (it != mTemplateDeclarations.end()) {
987  // full name matches
988  addInstantiation(tok, it->scope());
989  break;
990  }
991  // full name doesn't match so try with using namespaces if available
992  bool found = false;
993  for (const auto & nameSpace : tok->scopeInfo()->usingNamespaces) {
994  std::string fullNameSpace = scopeName + (scopeName.empty()?"":" :: ") +
995  nameSpace + (qualification.empty()?"":" :: ") + qualification;
996  std::string newFullName = fullNameSpace + " :: " + tok->str();
997  const std::list<TokenAndName>::const_iterator it1 = std::find_if(mTemplateDeclarations.cbegin(), mTemplateDeclarations.cend(), FindFullName(std::move(newFullName)));
998  if (it1 != mTemplateDeclarations.end()) {
999  // insert using namespace into token stream
1000  std::string::size_type offset = 0;
1001  std::string::size_type pos = 0;
1002  while ((pos = nameSpace.find(' ', offset)) != std::string::npos) {
1003  qualificationTok->insertTokenBefore(nameSpace.substr(offset, pos - offset));
1004  offset = pos + 1;
1005  }
1006  qualificationTok->insertTokenBefore(nameSpace.substr(offset));
1007  qualificationTok->insertTokenBefore("::");
1008  addInstantiation(tok, it1->scope());
1009  found = true;
1010  break;
1011  }
1012  }
1013  if (found)
1014  break;
1015 
1016  if (scopeName.empty()) {
1017  if (!qualification.empty())
1018  addInstantiation(tok, qualification);
1019  else
1020  addInstantiation(tok, tok->scopeInfo()->name);
1021  break;
1022  }
1023  const std::string::size_type pos = scopeName.rfind(" :: ");
1024  scopeName = (pos == std::string::npos) ? std::string() : scopeName.substr(0,pos);
1025  }
1026  }
1027  }
1028  }
1029 }
1030 
1031 
1033 {
1034  for (TokenAndName &declaration : mTemplateDeclarations)
1035  useDefaultArgumentValues(declaration);
1036 
1037  for (TokenAndName &declaration : mTemplateForwardDeclarations)
1038  useDefaultArgumentValues(declaration);
1039 }
1040 
1042 {
1043  // Ticket #5762: Skip specialization tokens
1044  if (declaration.isSpecialization() || declaration.isAlias() || declaration.isFriend())
1045  return;
1046 
1047  // template parameters with default value has syntax such as:
1048  // x = y
1049  // this list will contain all the '=' tokens for such arguments
1050  struct Default {
1051  Token *eq;
1052  Token *end;
1053  };
1054  std::list<Default> eq;
1055  // and this set the position of parameters with a default value
1056  std::set<std::size_t> defaultedArgPos;
1057 
1058  // parameter number. 1,2,3,..
1059  std::size_t templatepar = 1;
1060 
1061  // parameter depth
1062  std::size_t templateParmDepth = 0;
1063 
1064  // map type parameter name to index
1065  std::map<std::string, unsigned int> typeParameterNames;
1066 
1067  // Scan template declaration..
1068  for (Token *tok = declaration.token()->next(); tok; tok = tok->next()) {
1069  if (Token::simpleMatch(tok, "template <")) {
1070  Token* end = tok->next()->findClosingBracket();
1071  if (end)
1072  tok = end;
1073  continue;
1074  }
1075 
1076  if (tok->link() && Token::Match(tok, "{|(|[")) { // Ticket #6835
1077  tok = tok->link();
1078  continue;
1079  }
1080 
1081  if (tok->str() == "<" &&
1082  (tok->strAt(1) == ">" || (tok->previous()->isName() &&
1083  typeParameterNames.find(tok->strAt(-1)) == typeParameterNames.end())))
1084  ++templateParmDepth;
1085 
1086  // end of template parameters?
1087  if (tok->str() == ">") {
1088  if (templateParmDepth<2) {
1089  if (!eq.empty())
1090  eq.back().end = tok;
1091  break;
1092  }
1093  --templateParmDepth;
1094  }
1095 
1096  // map type parameter name to index
1097  if (Token::Match(tok, "typename|class|%type% %name% ,|>"))
1098  typeParameterNames[tok->strAt(1)] = templatepar - 1;
1099 
1100  // next template parameter
1101  if (tok->str() == "," && (1 == templateParmDepth)) { // Ticket #5823: Properly count parameters
1102  if (!eq.empty())
1103  eq.back().end = tok;
1104  ++templatepar;
1105  }
1106 
1107  // default parameter value?
1108  else if (Token::Match(tok, "= !!>")) {
1109  if (defaultedArgPos.insert(templatepar).second) {
1110  eq.emplace_back(Default{tok, nullptr});
1111  } else {
1112  // Ticket #5605: Syntax error (two equal signs for the same parameter), bail out
1113  eq.clear();
1114  break;
1115  }
1116  }
1117  }
1118  if (eq.empty())
1119  return;
1120 
1121  // iterate through all template instantiations
1122  for (const TokenAndName &instantiation : mTemplateInstantiations) {
1123  if (declaration.fullName() != instantiation.fullName())
1124  continue;
1125 
1126  // instantiation arguments..
1127  std::vector<std::vector<const Token *>> instantiationArgs;
1128  std::size_t index = 0;
1129  const Token *end = instantiation.token()->next()->findClosingBracket();
1130  if (!end)
1131  continue;
1132  if (end != instantiation.token()->tokAt(2))
1133  instantiationArgs.resize(1);
1134  for (const Token *tok1 = instantiation.token()->tokAt(2); tok1 && tok1 != end; tok1 = tok1->next()) {
1135  if (tok1->link() && Token::Match(tok1, "{|(|[")) {
1136  const Token *endLink = tok1->link();
1137  do {
1138  instantiationArgs[index].push_back(tok1);
1139  tok1 = tok1->next();
1140  } while (tok1 && tok1 != endLink);
1141  instantiationArgs[index].push_back(tok1);
1142  } else if (tok1->str() == "<" &&
1143  (tok1->strAt(1) == ">" || (tok1->previous()->isName() &&
1144  typeParameterNames.find(tok1->strAt(-1)) == typeParameterNames.end()))) {
1145  const Token *endLink = tok1->findClosingBracket();
1146  do {
1147  instantiationArgs[index].push_back(tok1);
1148  tok1 = tok1->next();
1149  } while (tok1 && tok1 != endLink);
1150  instantiationArgs[index].push_back(tok1);
1151  } else if (tok1->str() == ",") {
1152  ++index;
1153  instantiationArgs.resize(index + 1);
1154  } else
1155  instantiationArgs[index].push_back(tok1);
1156  }
1157 
1158  // count the parameters..
1159  Token *tok = instantiation.token()->next();
1160  unsigned int usedpar = templateParameters(tok);
1161  Token *instantiationEnd = tok->findClosingBracket();
1162  tok = instantiationEnd;
1163 
1164  if (tok && tok->str() == ">") {
1165  tok = tok->previous();
1166  std::list<Default>::const_iterator it = eq.cbegin();
1167  for (std::size_t i = (templatepar - eq.size()); it != eq.cend() && i < usedpar; ++i)
1168  ++it;
1169  int count = 0;
1170  while (it != eq.cend()) {
1171  // check for end
1172  if (!it->end) {
1174  const std::list<const Token*> locationList(1, it->eq);
1175  const ErrorMessage errmsg(locationList, &mTokenizer.list,
1177  "noparamend",
1178  "TemplateSimplifier couldn't find end of template parameter.",
1180  mErrorLogger.reportErr(errmsg);
1181  }
1182  break;
1183  }
1184 
1185  if ((usedpar + count) && usedpar <= (instantiationArgs.size() + count)) {
1186  tok->insertToken(",");
1187  tok = tok->next();
1188  }
1189  std::stack<Token *> links;
1190  for (const Token* from = it->eq->next(); from && from != it->end; from = from->next()) {
1191  auto entry = typeParameterNames.find(from->str());
1192  if (entry != typeParameterNames.end() && entry->second < instantiationArgs.size()) {
1193  for (const Token *tok1 : instantiationArgs[entry->second]) {
1194  tok->insertToken(tok1->str(), tok1->originalName());
1195  tok = tok->next();
1196 
1197  if (Token::Match(tok, "(|[|{"))
1198  links.push(tok);
1199  else if (!links.empty() && Token::Match(tok, ")|]|}")) {
1200  Token::createMutualLinks(links.top(), tok);
1201  links.pop();
1202  }
1203  }
1204  } else {
1205  tok->insertToken(from->str(), from->originalName());
1206  tok = tok->next();
1207 
1208  if (Token::Match(tok, "(|[|{"))
1209  links.push(tok);
1210  else if (!links.empty() && Token::Match(tok, ")|]|}")) {
1211  Token::createMutualLinks(links.top(), tok);
1212  links.pop();
1213  }
1214  }
1215  }
1216  ++it;
1217  count++;
1218  usedpar++;
1219  }
1220  }
1221 
1222  simplifyTemplateArgs(instantiation.token()->next(), instantiationEnd);
1223  }
1224 
1225  for (const auto & entry : eq) {
1226  Token *const eqtok = entry.eq;
1227  Token *tok2;
1228  int indentlevel = 0;
1229  for (tok2 = eqtok->next(); tok2; tok2 = tok2->next()) {
1230  if (Token::Match(tok2, ";|)|}|]")) { // bail out #6607
1231  tok2 = nullptr;
1232  break;
1233  }
1234  if (Token::Match(tok2, "(|{|["))
1235  tok2 = tok2->link();
1236  else if (Token::Match(tok2, "%type% <") && (tok2->strAt(2) == ">" || templateParameters(tok2->next()))) {
1237  const std::list<TokenAndName>::iterator ti = std::find_if(mTemplateInstantiations.begin(),
1239  FindToken(tok2));
1240  if (ti != mTemplateInstantiations.end())
1241  mTemplateInstantiations.erase(ti);
1242  ++indentlevel;
1243  } else if (indentlevel > 0 && tok2->str() == ">")
1244  --indentlevel;
1245  else if (indentlevel == 0 && Token::Match(tok2, ",|>"))
1246  break;
1247  if (indentlevel < 0)
1248  break;
1249  }
1250  // something went wrong, don't call eraseTokens()
1251  // with a nullptr "end" parameter (=all remaining tokens).
1252  if (!tok2)
1253  continue;
1254 
1255  // don't strip args from uninstantiated templates
1256  const std::list<TokenAndName>::iterator ti2 = std::find_if(mTemplateInstantiations.begin(),
1258  FindName(declaration.name()));
1259 
1260  if (ti2 == mTemplateInstantiations.end())
1261  continue;
1262 
1263  eraseTokens(eqtok, tok2);
1264  eqtok->deleteThis();
1265 
1266  // update parameter end pointer
1267  declaration.paramEnd(declaration.token()->next()->findClosingBracket());
1268  }
1269 }
1270 
1272 {
1273  for (std::list<TokenAndName>::iterator it1 = mTemplateDeclarations.begin(); it1 != mTemplateDeclarations.end();) {
1274  const TokenAndName &aliasDeclaration = *it1;
1275 
1276  if (!aliasDeclaration.isAlias()) {
1277  ++it1;
1278  continue;
1279  }
1280 
1281  // alias parameters..
1282  std::vector<const Token *> aliasParameters;
1283  getTemplateParametersInDeclaration(aliasDeclaration.token()->tokAt(2), aliasParameters);
1284  std::map<std::string, unsigned int> aliasParameterNames;
1285  for (unsigned int argnr = 0; argnr < aliasParameters.size(); ++argnr)
1286  aliasParameterNames[aliasParameters[argnr]->str()] = argnr;
1287 
1288  // Look for alias usages..
1289  bool found = false;
1290  for (std::list<TokenAndName>::iterator it2 = mTemplateInstantiations.begin(); it2 != mTemplateInstantiations.end();) {
1291  const TokenAndName &aliasUsage = *it2;
1292  if (!aliasUsage.token() || aliasUsage.fullName() != aliasDeclaration.fullName()) {
1293  ++it2;
1294  continue;
1295  }
1296 
1297  // don't recurse
1298  if (aliasDeclaration.isAliasToken(aliasUsage.token())) {
1299  ++it2;
1300  continue;
1301  }
1302 
1303  std::vector<std::pair<Token *, Token *>> args;
1304  Token *tok2 = aliasUsage.token()->tokAt(2);
1305  while (tok2) {
1306  Token * const start = tok2;
1307  while (tok2 && !Token::Match(tok2, "[,>;{}]")) {
1308  if (tok2->link() && Token::Match(tok2, "(|["))
1309  tok2 = tok2->link();
1310  else if (tok2->str() == "<") {
1311  tok2 = tok2->findClosingBracket();
1312  if (!tok2)
1313  break;
1314  }
1315  tok2 = tok2->next();
1316  }
1317 
1318  args.emplace_back(start, tok2);
1319  if (tok2 && tok2->str() == ",") {
1320  tok2 = tok2->next();
1321  } else {
1322  break;
1323  }
1324  }
1325  if (!tok2 || tok2->str() != ">" ||
1326  (!aliasDeclaration.isVariadic() && (args.size() != aliasParameters.size())) ||
1327  (aliasDeclaration.isVariadic() && (args.size() < aliasParameters.size()))) {
1328  ++it2;
1329  continue;
1330  }
1331 
1332  mChanged = true;
1333 
1334  // copy template-id from declaration to after instantiation
1335  Token * dst = aliasUsage.token()->next()->findClosingBracket();
1336  const Token* end = TokenList::copyTokens(dst, aliasDeclaration.aliasStartToken(), aliasDeclaration.aliasEndToken()->previous(), false)->next();
1337 
1338  // replace parameters
1339  for (Token *tok1 = dst->next(); tok1 != end; tok1 = tok1->next()) {
1340  if (!tok1->isName())
1341  continue;
1342  if (aliasParameterNames.find(tok1->str()) != aliasParameterNames.end()) {
1343  const unsigned int argnr = aliasParameterNames[tok1->str()];
1344  const Token * const fromStart = args[argnr].first;
1345  const Token * const fromEnd = args[argnr].second->previous();
1346  Token *temp = TokenList::copyTokens(tok1, fromStart, fromEnd, true);
1347  const bool tempOK(temp && temp != tok1->next());
1348  tok1->deleteThis();
1349  if (tempOK)
1350  tok1 = temp; // skip over inserted parameters
1351  } else if (tok1->str() == "typename")
1352  tok1->deleteThis();
1353  }
1354 
1355  // add new instantiations
1356  for (Token *tok1 = dst->next(); tok1 != end; tok1 = tok1->next()) {
1357  if (!tok1->isName())
1358  continue;
1359  if (aliasParameterNames.find(tok2->str()) == aliasParameterNames.end()) {
1360  // Create template instance..
1361  if (Token::Match(tok1, "%name% <")) {
1362  const std::list<TokenAndName>::const_iterator it = std::find_if(mTemplateInstantiations.cbegin(),
1363  mTemplateInstantiations.cend(),
1364  FindToken(tok1));
1365  if (it != mTemplateInstantiations.cend())
1366  addInstantiation(tok2, it->scope());
1367  }
1368  }
1369  }
1370 
1371  // erase the instantiation tokens
1372  eraseTokens(aliasUsage.token()->previous(), dst->next());
1373  found = true;
1374 
1375  // erase this instantiation
1376  it2 = mTemplateInstantiations.erase(it2);
1377  }
1378 
1379  if (found) {
1380  auto *end = const_cast<Token *>(aliasDeclaration.aliasEndToken());
1381 
1382  // remove declaration tokens
1383  if (aliasDeclaration.token()->previous())
1384  eraseTokens(aliasDeclaration.token()->previous(), end->next() ? end->next() : end);
1385  else {
1386  eraseTokens(mTokenList.front(), end->next() ? end->next() : end);
1388  }
1389 
1390  // remove declaration
1391  it1 = mTemplateDeclarations.erase(it1);
1392  } else
1393  ++it1;
1394  }
1395 }
1396 
1397 bool TemplateSimplifier::instantiateMatch(const Token *instance, const std::size_t numberOfArguments, bool variadic, const char patternAfter[])
1398 {
1399  assert(instance->strAt(1) == "<");
1400 
1401  auto n = templateParameters(instance->next());
1402  if (variadic ? (n + 1 < numberOfArguments) : (numberOfArguments != n))
1403  return false;
1404 
1405  if (patternAfter) {
1406  const Token *tok = instance->next()->findClosingBracket();
1407  if (!tok || !Token::Match(tok->next(), patternAfter))
1408  return false;
1409  }
1410 
1411  // nothing mismatching was found..
1412  return true;
1413 }
1414 
1415 // Utility function for TemplateSimplifier::getTemplateNamePosition, that works on template functions
1417 {
1418  namepos = 1;
1419  while (tok && tok->next()) {
1420  if (Token::Match(tok->next(), ";|{"))
1421  return false;
1422  // skip decltype(...)
1423  if (Token::simpleMatch(tok->next(), "decltype (")) {
1424  const Token * end = tok->linkAt(2)->previous();
1425  while (tok->next() && tok != end) {
1426  tok = tok->next();
1427  namepos++;
1428  }
1429  } else if (Token::Match(tok->next(), "%type% <")) {
1430  const Token *closing = tok->tokAt(2)->findClosingBracket();
1431  if (closing) {
1432  if (closing->strAt(1) == "(" && Tokenizer::isFunctionHead(closing->next(), ";|{|:"))
1433  return true;
1434  while (tok->next() && tok->next() != closing) {
1435  tok = tok->next();
1436  namepos++;
1437  }
1438  }
1439  } else if (Token::Match(tok->next(), "%type% (") && Tokenizer::isFunctionHead(tok->tokAt(2), ";|{|:")) {
1440  return true;
1441  }
1442  tok = tok->next();
1443  namepos++;
1444  }
1445  return false;
1446 }
1447 
1449 {
1450  namepos = 1;
1451  while (tok && tok->next()) {
1452  if (Token::Match(tok->next(), ";|{|(|using"))
1453  return false;
1454  // skip decltype(...)
1455  if (Token::simpleMatch(tok->next(), "decltype (")) {
1456  const Token * end = tok->linkAt(2);
1457  while (tok->next() && tok != end) {
1458  tok = tok->next();
1459  namepos++;
1460  }
1461  } else if (Token::Match(tok->next(), "%type% <")) {
1462  const Token *closing = tok->tokAt(2)->findClosingBracket();
1463  if (closing) {
1464  if (Token::Match(closing->next(), "=|;"))
1465  return true;
1466  while (tok->next() && tok->next() != closing) {
1467  tok = tok->next();
1468  namepos++;
1469  }
1470  }
1471  } else if (Token::Match(tok->next(), "%type% =|;")) {
1472  return true;
1473  }
1474  tok = tok->next();
1475  namepos++;
1476  }
1477  return false;
1478 }
1479 
1481 {
1482  if (Token::Match(tok, "> friend| class|struct|union %type% :|<|;|{|::")) {
1483  namepos = tok->strAt(1) == "friend" ? 3 : 2;
1484  tok = tok->tokAt(namepos);
1485  while (Token::Match(tok, "%type% :: %type%") ||
1486  (Token::Match(tok, "%type% <") && Token::Match(tok->next()->findClosingBracket(), "> :: %type%"))) {
1487  if (tok->strAt(1) == "::") {
1488  tok = tok->tokAt(2);
1489  namepos += 2;
1490  } else {
1491  const Token *end = tok->next()->findClosingBracket();
1492  if (!end || !end->tokAt(2)) {
1493  // syntax error
1494  namepos = -1;
1495  return true;
1496  }
1497  end = end->tokAt(2);
1498  do {
1499  tok = tok->next();
1500  namepos += 1;
1501  } while (tok && tok != end);
1502  }
1503  }
1504  return true;
1505  }
1506  return false;
1507 }
1508 
1510 {
1511  if (!tok || tok->str() != ">")
1512  syntaxError(tok);
1513 
1514  auto it = mTemplateNamePos.find(tok);
1515  if (!mSettings.debugtemplate && it != mTemplateNamePos.end()) {
1516  return it->second;
1517  }
1518  // get the position of the template name
1519  int namepos = 0;
1520  if (getTemplateNamePositionTemplateClass(tok, namepos))
1521  ;
1522  else if (Token::Match(tok, "> using %name% =")) {
1523  // types may not be defined in alias template declarations
1524  if (!Token::Match(tok->tokAt(4), "class|struct|union|enum %name%| {"))
1525  namepos = 2;
1526  } else if (getTemplateNamePositionTemplateVariable(tok, namepos))
1527  ;
1528  else if (!getTemplateNamePositionTemplateFunction(tok, namepos))
1529  namepos = -1; // Name not found
1530  mTemplateNamePos[tok] = namepos;
1531  return namepos;
1532 }
1533 
1534 void TemplateSimplifier::addNamespace(const TokenAndName &templateDeclaration, const Token *tok)
1535 {
1536  // find start of qualification
1537  const Token * tokStart = tok;
1538  int offset = 0;
1539  while (Token::Match(tokStart->tokAt(-2), "%name% ::")) {
1540  tokStart = tokStart->tokAt(-2);
1541  offset -= 2;
1542  }
1543  // decide if namespace needs to be inserted in or appended to token list
1544  const bool insert = tokStart != tok;
1545 
1546  std::string::size_type start = 0;
1547  std::string::size_type end = 0;
1548  bool inTemplate = false;
1549  int level = 0;
1550  while ((end = templateDeclaration.scope().find(' ', start)) != std::string::npos) {
1551  std::string token = templateDeclaration.scope().substr(start, end - start);
1552  // done if scopes overlap
1553  if (token == tokStart->str() && tok->strAt(-1) != "::")
1554  break;
1555  if (token == "<") {
1556  inTemplate = true;
1557  ++level;
1558  }
1559  if (inTemplate) {
1560  if (insert)
1561  mTokenList.back()->tokAt(offset)->str(mTokenList.back()->strAt(offset) + token);
1562  else
1563  mTokenList.back()->str(mTokenList.back()->str() + token);
1564  if (token == ">") {
1565  --level;
1566  if (level == 0)
1567  inTemplate = false;
1568  }
1569  } else {
1570  if (insert)
1571  mTokenList.back()->tokAt(offset)->insertToken(token, emptyString);
1572  else
1573  mTokenList.addtoken(token, tok->linenr(), tok->column(), tok->fileIndex());
1574  }
1575  start = end + 1;
1576  }
1577  // don't add if it already exists
1578  std::string token = templateDeclaration.scope().substr(start, end - start);
1579  if (token != tokStart->str() || tok->strAt(-1) != "::") {
1580  if (insert) {
1581  if (!inTemplate)
1582  mTokenList.back()->tokAt(offset)->insertToken(templateDeclaration.scope().substr(start), emptyString);
1583  else
1584  mTokenList.back()->tokAt(offset)->str(mTokenList.back()->strAt(offset) + templateDeclaration.scope().substr(start));
1585  mTokenList.back()->tokAt(offset)->insertToken("::", emptyString);
1586  } else {
1587  if (!inTemplate)
1588  mTokenList.addtoken(templateDeclaration.scope().substr(start), tok->linenr(), tok->column(), tok->fileIndex());
1589  else
1590  mTokenList.back()->str(mTokenList.back()->str() + templateDeclaration.scope().substr(start));
1591  mTokenList.addtoken("::", tok->linenr(), tok->column(), tok->fileIndex());
1592  }
1593  }
1594 }
1595 
1596 bool TemplateSimplifier::alreadyHasNamespace(const TokenAndName &templateDeclaration, const Token *tok)
1597 {
1598  const std::string& scope = templateDeclaration.scope();
1599 
1600  // get the length in tokens of the namespace
1601  std::string::size_type pos = 0;
1602  int offset = -2;
1603 
1604  while ((pos = scope.find("::", pos)) != std::string::npos) {
1605  offset -= 2;
1606  pos += 2;
1607  }
1608 
1609  return Token::simpleMatch(tok->tokAt(offset), scope.c_str(), scope.size());
1610 }
1611 
1613  newInstantiation(Token* t, std::string s) : token(t), scope(std::move(s)) {}
1615  std::string scope;
1616 };
1617 
1619  const TokenAndName &templateDeclaration,
1620  const TokenAndName &templateInstantiation,
1621  const std::vector<const Token *> &typeParametersInDeclaration,
1622  const std::string &newName,
1623  bool copy)
1624 {
1625  bool inTemplateDefinition = false;
1626  const Token *startOfTemplateDeclaration = nullptr;
1627  const Token *endOfTemplateDefinition = nullptr;
1628  const Token * const templateDeclarationNameToken = templateDeclaration.nameToken();
1629  const Token * const templateDeclarationToken = templateDeclaration.paramEnd();
1630  const bool isClass = templateDeclaration.isClass();
1631  const bool isFunction = templateDeclaration.isFunction();
1632  const bool isSpecialization = templateDeclaration.isSpecialization();
1633  const bool isVariable = templateDeclaration.isVariable();
1634 
1635  std::vector<newInstantiation> newInstantiations;
1636 
1637  // add forward declarations
1638  if (copy && isClass) {
1639  templateDeclaration.token()->insertTokenBefore(templateDeclarationToken->strAt(1));
1640  templateDeclaration.token()->insertTokenBefore(newName);
1641  templateDeclaration.token()->insertTokenBefore(";");
1642  } else if ((isFunction && (copy || isSpecialization)) ||
1643  (isVariable && !isSpecialization) ||
1644  (isClass && isSpecialization && mTemplateSpecializationMap.find(templateDeclaration.token()) != mTemplateSpecializationMap.end())) {
1645  Token * dst = templateDeclaration.token();
1646  Token * dstStart = dst->previous();
1647  bool isStatic = false;
1648  std::string scope;
1649  const Token * start;
1650  const Token * end;
1651  auto it = mTemplateForwardDeclarationsMap.find(dst);
1652  if (!isSpecialization && it != mTemplateForwardDeclarationsMap.end()) {
1653  dst = it->second;
1654  dstStart = dst->previous();
1655  const Token * temp1 = dst->tokAt(1)->findClosingBracket();
1656  const Token * temp2 = temp1->tokAt(getTemplateNamePosition(temp1));
1657  start = temp1->next();
1658  end = temp2->linkAt(1)->next();
1659  } else {
1660  if (it != mTemplateForwardDeclarationsMap.end()) {
1661  const std::list<TokenAndName>::const_iterator it1 = std::find_if(mTemplateForwardDeclarations.cbegin(),
1663  FindToken(it->second));
1664  if (it1 != mTemplateForwardDeclarations.cend())
1665  mMemberFunctionsToDelete.push_back(*it1);
1666  }
1667 
1668  auto it2 = mTemplateSpecializationMap.find(dst);
1669  if (it2 != mTemplateSpecializationMap.end()) {
1670  dst = it2->second;
1671  dstStart = dst->previous();
1672  isStatic = dst->next()->findClosingBracket()->strAt(1) == "static";
1673  const Token * temp = templateDeclarationNameToken;
1674  while (Token::Match(temp->tokAt(-2), "%name% ::")) {
1675  scope.insert(0, temp->strAt(-2) + " :: ");
1676  temp = temp->tokAt(-2);
1677  }
1678  }
1679  start = templateDeclarationToken->next();
1680  end = templateDeclarationNameToken->next();
1681  if (end->str() == "<")
1682  end = end->findClosingBracket()->next();
1683  if (end->str() == "(")
1684  end = end->link()->next();
1685  else if (isVariable && end->str() == "=") {
1686  const Token *temp = end->next();
1687  while (temp && temp->str() != ";") {
1688  if (temp->link() && Token::Match(temp, "{|[|("))
1689  temp = temp->link();
1690  temp = temp->next();
1691  }
1692  end = temp;
1693  }
1694  }
1695  unsigned int typeindentlevel = 0;
1696  while (end && !(typeindentlevel == 0 && Token::Match(end, ";|{|:"))) {
1697  if (Token::Match(end, "<|(|{"))
1698  ++typeindentlevel;
1699  else if (Token::Match(end, ">|)|}"))
1700  --typeindentlevel;
1701  end = end->next();
1702  }
1703 
1704  if (isStatic) {
1705  dst->insertTokenBefore("static");
1706  if (start) {
1707  dst->previous()->linenr(start->linenr());
1708  dst->previous()->column(start->column());
1709  }
1710  }
1711 
1712  std::map<const Token *, Token *> links;
1713  bool inAssignment = false;
1714  while (start && start != end) {
1715  if (isVariable && start->str() == "=")
1716  inAssignment = true;
1717  unsigned int itype = 0;
1718  while (itype < typeParametersInDeclaration.size() && typeParametersInDeclaration[itype]->str() != start->str())
1719  ++itype;
1720 
1721  if (itype < typeParametersInDeclaration.size() && itype < mTypesUsedInTemplateInstantiation.size() &&
1722  (!isVariable || !Token::Match(typeParametersInDeclaration[itype]->previous(), "<|, %type% >|,"))) {
1723  typeindentlevel = 0;
1724  std::stack<Token *> brackets1; // holds "(" and "{" tokens
1725  bool pointerType = false;
1726  Token * const dst1 = dst->previous();
1727  const bool isVariadicTemplateArg = templateDeclaration.isVariadic() && itype + 1 == typeParametersInDeclaration.size();
1728  if (isVariadicTemplateArg && Token::Match(start, "%name% ... %name%"))
1729  start = start->tokAt(2);
1730  const std::string endStr(isVariadicTemplateArg ? ">" : ",>");
1731  for (const Token *typetok = mTypesUsedInTemplateInstantiation[itype].token();
1732  typetok && (typeindentlevel > 0 || endStr.find(typetok->str()[0]) == std::string::npos);
1733  typetok = typetok->next()) {
1734  if (typeindentlevel == 0 && typetok->str() == "*")
1735  pointerType = true;
1736  if (Token::simpleMatch(typetok, "..."))
1737  continue;
1738  if (Token::Match(typetok, "%name% <") && (typetok->strAt(2) == ">" || templateParameters(typetok->next())))
1739  ++typeindentlevel;
1740  else if (typeindentlevel > 0 && typetok->str() == ">")
1741  --typeindentlevel;
1742  else if (typetok->str() == "(")
1743  ++typeindentlevel;
1744  else if (typetok->str() == ")")
1745  --typeindentlevel;
1746  dst->insertToken(typetok->str(), typetok->originalName(), typetok->getMacroName(), true);
1747  dst->previous()->linenr(start->linenr());
1748  dst->previous()->column(start->column());
1749  Token *previous = dst->previous();
1750  previous->isTemplateArg(true);
1751  previous->isSigned(typetok->isSigned());
1752  previous->isUnsigned(typetok->isUnsigned());
1753  previous->isLong(typetok->isLong());
1754  if (Token::Match(previous, "{|(|[")) {
1755  brackets1.push(previous);
1756  } else if (previous->str() == "}") {
1757  assert(brackets1.empty() == false);
1758  assert(brackets1.top()->str() == "{");
1759  Token::createMutualLinks(brackets1.top(), previous);
1760  brackets1.pop();
1761  } else if (previous->str() == ")") {
1762  assert(brackets1.empty() == false);
1763  assert(brackets1.top()->str() == "(");
1764  Token::createMutualLinks(brackets1.top(), previous);
1765  brackets1.pop();
1766  } else if (previous->str() == "]") {
1767  assert(brackets1.empty() == false);
1768  assert(brackets1.top()->str() == "[");
1769  Token::createMutualLinks(brackets1.top(), previous);
1770  brackets1.pop();
1771  }
1772  }
1773  if (pointerType && Token::simpleMatch(dst1, "const")) {
1774  dst->insertToken("const", dst1->originalName(), dst1->getMacroName(), true);
1775  dst->previous()->linenr(start->linenr());
1776  dst->previous()->column(start->column());
1777  dst1->deleteThis();
1778  }
1779  } else {
1780  if (isSpecialization && !copy && !scope.empty() && Token::Match(start, (scope + templateDeclarationNameToken->str()).c_str())) {
1781  // skip scope
1782  while (start->strAt(1) != templateDeclarationNameToken->str())
1783  start = start->next();
1784  } else if (start->str() == templateDeclarationNameToken->str() &&
1785  !(templateDeclaration.isFunction() && templateDeclaration.scope().empty() &&
1786  (start->strAt(-1) == "." || Token::simpleMatch(start->tokAt(-2), ". template")))) {
1787  if (start->strAt(1) != "<" || Token::Match(start, newName.c_str()) || !inAssignment) {
1788  dst->insertTokenBefore(newName);
1789  dst->previous()->linenr(start->linenr());
1790  dst->previous()->column(start->column());
1791  if (start->strAt(1) == "<")
1792  start = start->next()->findClosingBracket();
1793  } else {
1794  dst->insertTokenBefore(start->str());
1795  dst->previous()->linenr(start->linenr());
1796  dst->previous()->column(start->column());
1797  newInstantiations.emplace_back(dst->previous(), templateDeclaration.scope());
1798  }
1799  } else {
1800  // check if type is a template
1801  if (start->strAt(1) == "<") {
1802  // get the instantiated name
1803  const Token * closing = start->next()->findClosingBracket();
1804  if (closing) {
1805  std::string name;
1806  const Token * type = start;
1807  while (type && type != closing->next()) {
1808  if (!name.empty())
1809  name += " ";
1810  name += type->str();
1811  type = type->next();
1812  }
1813  // check if type is instantiated
1814  if (std::any_of(mTemplateInstantiations.cbegin(), mTemplateInstantiations.cend(), [&](const TokenAndName& inst) {
1815  return Token::simpleMatch(inst.token(), name.c_str(), name.size());
1816  })) {
1817  // use the instantiated name
1818  dst->insertTokenBefore(name);
1819  dst->previous()->linenr(start->linenr());
1820  dst->previous()->column(start->column());
1821  start = closing;
1822  }
1823  }
1824  // just copy the token if it wasn't instantiated
1825  if (start != closing) {
1826  dst->insertToken(start->str(), start->originalName(), start->getMacroName(), true);
1827  dst->previous()->linenr(start->linenr());
1828  dst->previous()->column(start->column());
1829  dst->previous()->isSigned(start->isSigned());
1830  dst->previous()->isUnsigned(start->isUnsigned());
1831  dst->previous()->isLong(start->isLong());
1832  }
1833  } else {
1834  dst->insertToken(start->str(), start->originalName(), start->getMacroName(), true);
1835  dst->previous()->linenr(start->linenr());
1836  dst->previous()->column(start->column());
1837  dst->previous()->isSigned(start->isSigned());
1838  dst->previous()->isUnsigned(start->isUnsigned());
1839  dst->previous()->isLong(start->isLong());
1840  }
1841  }
1842 
1843  if (!start)
1844  continue;
1845 
1846  if (start->link()) {
1847  if (Token::Match(start, "[|{|(")) {
1848  links[start->link()] = dst->previous();
1849  } else if (Token::Match(start, "]|}|)")) {
1850  std::map<const Token *, Token *>::iterator link = links.find(start);
1851  // make sure link is valid
1852  if (link != links.end()) {
1853  Token::createMutualLinks(link->second, dst->previous());
1854  links.erase(start);
1855  }
1856  }
1857  }
1858  }
1859 
1860  start = start->next();
1861  }
1862  dst->insertTokenBefore(";");
1863  dst->previous()->linenr(dst->tokAt(-2)->linenr());
1864  dst->previous()->column(dst->tokAt(-2)->column() + 1);
1865 
1866  if (isVariable || isFunction)
1867  simplifyTemplateArgs(dstStart, dst);
1868  }
1869 
1870  if (copy && (isClass || isFunction)) {
1871  // check if this is an explicit instantiation
1872  Token * start = templateInstantiation.token();
1873  while (start && !Token::Match(start->previous(), "}|;|extern"))
1874  start = start->previous();
1875  if (Token::Match(start, "template !!<")) {
1876  if (start->strAt(-1) == "extern")
1877  start = start->previous();
1878  mExplicitInstantiationsToDelete.emplace_back(start, "");
1879  }
1880  }
1881 
1882  for (Token *tok3 = mTokenList.front(); tok3; tok3 = tok3 ? tok3->next() : nullptr) {
1883  if (inTemplateDefinition) {
1884  if (!endOfTemplateDefinition) {
1885  if (isVariable) {
1886  Token *temp = tok3->findClosingBracket();
1887  if (temp) {
1888  while (temp && temp->str() != ";") {
1889  if (temp->link() && Token::Match(temp, "{|[|("))
1890  temp = temp->link();
1891  temp = temp->next();
1892  }
1893  endOfTemplateDefinition = temp;
1894  }
1895  } else if (tok3->str() == "{")
1896  endOfTemplateDefinition = tok3->link();
1897  }
1898  if (tok3 == endOfTemplateDefinition) {
1899  inTemplateDefinition = false;
1900  startOfTemplateDeclaration = nullptr;
1901  }
1902  }
1903 
1904  if (tok3->str()=="template") {
1905  if (tok3->next() && tok3->next()->str()=="<") {
1906  std::vector<const Token *> localTypeParametersInDeclaration;
1907  getTemplateParametersInDeclaration(tok3->tokAt(2), localTypeParametersInDeclaration);
1908  inTemplateDefinition = localTypeParametersInDeclaration.size() == typeParametersInDeclaration.size(); // Partial specialization
1909  } else {
1910  inTemplateDefinition = false; // Only template instantiation
1911  }
1912  startOfTemplateDeclaration = tok3;
1913  }
1914  if (Token::Match(tok3, "(|["))
1915  tok3 = tok3->link();
1916 
1917  // Start of template..
1918  if (tok3 == templateDeclarationToken) {
1919  tok3 = tok3->next();
1920  if (tok3->str() == "static")
1921  tok3 = tok3->next();
1922  }
1923 
1924  // member function implemented outside class definition
1925  else if (inTemplateDefinition &&
1926  Token::Match(tok3, "%name% <") &&
1927  templateInstantiation.name() == tok3->str() &&
1928  instantiateMatch(tok3, typeParametersInDeclaration.size(), templateDeclaration.isVariadic(), ":: ~| %name% (")) {
1929  // there must be template..
1930  bool istemplate = false;
1931  Token * tok5 = nullptr; // start of function return type
1932  for (Token *prev = tok3; prev && !Token::Match(prev, "[;{}]"); prev = prev->previous()) {
1933  if (prev->str() == "template") {
1934  istemplate = true;
1935  tok5 = prev;
1936  break;
1937  }
1938  }
1939  if (!istemplate)
1940  continue;
1941 
1942  const Token *tok4 = tok3->next()->findClosingBracket();
1943  while (tok4 && tok4->str() != "(")
1944  tok4 = tok4->next();
1945  if (!Tokenizer::isFunctionHead(tok4, ":{"))
1946  continue;
1947  // find function return type start
1948  tok5 = tok5->next()->findClosingBracket();
1949  if (tok5)
1950  tok5 = tok5->next();
1951  // copy return type
1952  std::stack<Token *> brackets2; // holds "(" and "{" tokens
1953  while (tok5 && tok5 != tok3) {
1954  // replace name if found
1955  if (Token::Match(tok5, "%name% <") && tok5->str() == templateInstantiation.name()) {
1956  if (copy) {
1957  if (!templateDeclaration.scope().empty() && tok5->strAt(-1) != "::")
1958  addNamespace(templateDeclaration, tok5);
1959  mTokenList.addtoken(newName, tok5->linenr(), tok5->column(), tok5->fileIndex());
1960  tok5 = tok5->next()->findClosingBracket();
1961  } else {
1962  tok5->str(newName);
1963  eraseTokens(tok5, tok5->next()->findClosingBracket()->next());
1964  }
1965  } else if (copy) {
1966  bool added = false;
1967  if (tok5->isName() && !Token::Match(tok5, "class|typename|struct") && !tok5->isStandardType()) {
1968  // search for this token in the type vector
1969  unsigned int itype = 0;
1970  while (itype < typeParametersInDeclaration.size() && typeParametersInDeclaration[itype]->str() != tok5->str())
1971  ++itype;
1972 
1973  // replace type with given type..
1974  if (itype < typeParametersInDeclaration.size() && itype < mTypesUsedInTemplateInstantiation.size()) {
1975  std::stack<Token *> brackets1; // holds "(" and "{" tokens
1976  for (const Token *typetok = mTypesUsedInTemplateInstantiation[itype].token();
1977  typetok && !Token::Match(typetok, ",|>");
1978  typetok = typetok->next()) {
1979  if (!Token::simpleMatch(typetok, "...")) {
1980  mTokenList.addtoken(typetok, tok5);
1981  Token *back = mTokenList.back();
1982  if (Token::Match(back, "{|(|[")) {
1983  brackets1.push(back);
1984  } else if (back->str() == "}") {
1985  assert(brackets1.empty() == false);
1986  assert(brackets1.top()->str() == "{");
1987  Token::createMutualLinks(brackets1.top(), back);
1988  brackets1.pop();
1989  } else if (back->str() == ")") {
1990  assert(brackets1.empty() == false);
1991  assert(brackets1.top()->str() == "(");
1992  Token::createMutualLinks(brackets1.top(), back);
1993  brackets1.pop();
1994  } else if (back->str() == "]") {
1995  assert(brackets1.empty() == false);
1996  assert(brackets1.top()->str() == "[");
1997  Token::createMutualLinks(brackets1.top(), back);
1998  brackets1.pop();
1999  }
2000  back->isTemplateArg(true);
2001  back->isUnsigned(typetok->isUnsigned());
2002  back->isSigned(typetok->isSigned());
2003  back->isLong(typetok->isLong());
2004  added = true;
2005  break;
2006  }
2007  }
2008  }
2009  }
2010  if (!added) {
2011  mTokenList.addtoken(tok5);
2012  Token *back = mTokenList.back();
2013  if (Token::Match(back, "{|(|[")) {
2014  brackets2.push(back);
2015  } else if (back->str() == "}") {
2016  assert(brackets2.empty() == false);
2017  assert(brackets2.top()->str() == "{");
2018  Token::createMutualLinks(brackets2.top(), back);
2019  brackets2.pop();
2020  } else if (back->str() == ")") {
2021  assert(brackets2.empty() == false);
2022  assert(brackets2.top()->str() == "(");
2023  Token::createMutualLinks(brackets2.top(), back);
2024  brackets2.pop();
2025  } else if (back->str() == "]") {
2026  assert(brackets2.empty() == false);
2027  assert(brackets2.top()->str() == "[");
2028  Token::createMutualLinks(brackets2.top(), back);
2029  brackets2.pop();
2030  }
2031  }
2032  }
2033 
2034  tok5 = tok5->next();
2035  }
2036  if (copy) {
2037  if (!templateDeclaration.scope().empty() && tok3->strAt(-1) != "::")
2038  addNamespace(templateDeclaration, tok3);
2039  mTokenList.addtoken(newName, tok3->linenr(), tok3->column(), tok3->fileIndex());
2040  }
2041 
2042  while (tok3 && tok3->str() != "::")
2043  tok3 = tok3->next();
2044 
2045  const std::list<TokenAndName>::const_iterator it = std::find_if(mTemplateDeclarations.cbegin(),
2046  mTemplateDeclarations.cend(),
2047  FindToken(startOfTemplateDeclaration));
2048  if (it != mTemplateDeclarations.cend())
2049  mMemberFunctionsToDelete.push_back(*it);
2050  }
2051 
2052  // not part of template.. go on to next token
2053  else
2054  continue;
2055 
2056  std::stack<Token *> brackets; // holds "(", "[" and "{" tokens
2057 
2058  // FIXME use full name matching somehow
2059  const std::string lastName = (templateInstantiation.name().find(' ') != std::string::npos) ? templateInstantiation.name().substr(templateInstantiation.name().rfind(' ')+1) : templateInstantiation.name();
2060 
2061  std::stack<const Token *> templates;
2062  for (; tok3; tok3 = tok3->next()) {
2063  if (tok3->isName() && !Token::Match(tok3, "class|typename|struct") && !tok3->isStandardType()) {
2064  // search for this token in the type vector
2065  unsigned int itype = 0;
2066  while (itype < typeParametersInDeclaration.size() && typeParametersInDeclaration[itype]->str() != tok3->str())
2067  ++itype;
2068 
2069  // replace type with given type..
2070  if (itype < typeParametersInDeclaration.size() && itype < mTypesUsedInTemplateInstantiation.size()) {
2071  unsigned int typeindentlevel = 0;
2072  std::stack<Token *> brackets1; // holds "(" and "{" tokens
2073  Token * const beforeTypeToken = mTokenList.back();
2074  bool pointerType = false;
2075  const bool isVariadicTemplateArg = templateDeclaration.isVariadic() && itype + 1 == typeParametersInDeclaration.size();
2076  if (isVariadicTemplateArg && mTypesUsedInTemplateInstantiation.size() > 1 && !Token::simpleMatch(tok3->next(), "..."))
2077  continue;
2078  if (isVariadicTemplateArg && Token::Match(tok3, "%name% ... %name%"))
2079  tok3 = tok3->tokAt(2);
2080  const std::string endStr(isVariadicTemplateArg ? ">" : ",>");
2081  for (Token *typetok = mTypesUsedInTemplateInstantiation[itype].token();
2082  typetok && (typeindentlevel > 0 || endStr.find(typetok->str()[0]) == std::string::npos);
2083  typetok = typetok->next()) {
2084  if (typeindentlevel == 0 && typetok->str() == "*")
2085  pointerType = true;
2086  if (Token::simpleMatch(typetok, "..."))
2087  continue;
2088  if (Token::Match(typetok, "%name% <") &&
2089  (typetok->strAt(2) == ">" || templateParameters(typetok->next()))) {
2090  brackets1.push(typetok->next());
2091  ++typeindentlevel;
2092  } else if (typeindentlevel > 0 && typetok->str() == ">" && brackets1.top()->str() == "<") {
2093  --typeindentlevel;
2094  brackets1.pop();
2095  } else if (Token::Match(typetok, "const_cast|dynamic_cast|reinterpret_cast|static_cast <")) {
2096  brackets1.push(typetok->next());
2097  ++typeindentlevel;
2098  } else if (typetok->str() == "(")
2099  ++typeindentlevel;
2100  else if (typetok->str() == ")")
2101  --typeindentlevel;
2102  Token *back;
2103  if (copy) {
2104  mTokenList.addtoken(typetok, tok3);
2105  back = mTokenList.back();
2106  } else
2107  back = typetok;
2108  if (Token::Match(back, "{|(|["))
2109  brackets1.push(back);
2110  else if (back->str() == "}") {
2111  assert(brackets1.empty() == false);
2112  assert(brackets1.top()->str() == "{");
2113  if (copy)
2114  Token::createMutualLinks(brackets1.top(), back);
2115  brackets1.pop();
2116  } else if (back->str() == ")") {
2117  assert(brackets1.empty() == false);
2118  assert(brackets1.top()->str() == "(");
2119  if (copy)
2120  Token::createMutualLinks(brackets1.top(), back);
2121  brackets1.pop();
2122  } else if (back->str() == "]") {
2123  assert(brackets1.empty() == false);
2124  assert(brackets1.top()->str() == "[");
2125  if (copy)
2126  Token::createMutualLinks(brackets1.top(), back);
2127  brackets1.pop();
2128  }
2129  if (copy)
2130  back->isTemplateArg(true);
2131  }
2132  if (pointerType && Token::simpleMatch(beforeTypeToken, "const")) {
2133  mTokenList.addtoken(beforeTypeToken);
2134  beforeTypeToken->deleteThis();
2135  }
2136  continue;
2137  }
2138  }
2139 
2140  // replace name..
2141  if (tok3->str() == lastName) {
2142  if (Token::simpleMatch(tok3->next(), "<")) {
2143  Token *closingBracket = tok3->next()->findClosingBracket();
2144  if (closingBracket) {
2145  // replace multi token name with single token name
2146  if (tok3 == templateDeclarationNameToken ||
2147  Token::Match(tok3, newName.c_str())) {
2148  if (copy) {
2149  mTokenList.addtoken(newName, tok3);
2150  tok3 = closingBracket;
2151  } else {
2152  tok3->str(newName);
2153  eraseTokens(tok3, closingBracket->next());
2154  }
2155  continue;
2156  }
2157  if (!templateDeclaration.scope().empty() &&
2158  !alreadyHasNamespace(templateDeclaration, tok3) &&
2159  !Token::Match(closingBracket->next(), "(|::")) {
2160  if (copy)
2161  addNamespace(templateDeclaration, tok3);
2162  }
2163  }
2164  } else {
2165  // don't modify friend
2166  if (Token::Match(tok3->tokAt(-3), "> friend class|struct|union")) {
2167  if (copy)
2168  mTokenList.addtoken(tok3);
2169  } else if (copy) {
2170  // add namespace if necessary
2171  if (!templateDeclaration.scope().empty() &&
2172  (isClass ? tok3->strAt(1) != "(" : true)) {
2173  addNamespace(templateDeclaration, tok3);
2174  }
2175  mTokenList.addtoken(newName, tok3);
2176  } else if (!Token::Match(tok3->next(), "[:{=;[]),]"))
2177  tok3->str(newName);
2178  continue;
2179  }
2180  }
2181 
2182  // copy
2183  if (copy)
2184  mTokenList.addtoken(tok3);
2185 
2186  // look for template definitions
2187  if (Token::simpleMatch(tok3, "template <")) {
2188  Token * tok2 = findTemplateDeclarationEnd(tok3);
2189  if (tok2)
2190  templates.push(tok2);
2191  } else if (!templates.empty() && templates.top() == tok3)
2192  templates.pop();
2193 
2194  if (Token::Match(tok3, "%type% <") &&
2195  !Token::Match(tok3, "template|static_cast|const_cast|reinterpret_cast|dynamic_cast") &&
2196  Token::Match(tok3->next()->findClosingBracket(), ">|>>")) {
2197  const Token *closingBracket = tok3->next()->findClosingBracket();
2198  if (Token::simpleMatch(closingBracket->next(), "&")) {
2199  int num = 0;
2200  const Token *par = tok3->next();
2201  while (num < typeParametersInDeclaration.size() && par != closingBracket) {
2202  const std::string pattern("[<,] " + typeParametersInDeclaration[num]->str() + " [,>]");
2203  if (!Token::Match(par, pattern.c_str()))
2204  break;
2205  ++num;
2206  par = par->tokAt(2);
2207  }
2208  if (num < typeParametersInDeclaration.size() || par != closingBracket)
2209  continue;
2210  }
2211 
2212  // don't add instantiations in template definitions
2213  if (!templates.empty())
2214  continue;
2215 
2216  std::string scope;
2217  const Token *prev = tok3;
2218  for (; Token::Match(prev->tokAt(-2), "%name% ::"); prev = prev->tokAt(-2)) {
2219  if (scope.empty())
2220  scope = prev->strAt(-2);
2221  else
2222  scope = prev->strAt(-2) + " :: " + scope;
2223  }
2224 
2225  // check for global scope
2226  if (prev->strAt(-1) != "::") {
2227  // adjust for current scope
2228  std::string token_scope = tok3->scopeInfo()->name;
2229  const std::string::size_type end = token_scope.find_last_of(" :: ");
2230  if (end != std::string::npos) {
2231  token_scope.resize(end);
2232  if (scope.empty())
2233  scope = std::move(token_scope);
2234  else
2235  scope = token_scope + " :: " + scope;
2236  }
2237  }
2238 
2239  if (copy)
2240  newInstantiations.emplace_back(mTokenList.back(), std::move(scope));
2241  else if (!inTemplateDefinition)
2242  newInstantiations.emplace_back(tok3, std::move(scope));
2243  }
2244 
2245  // link() newly tokens manually
2246  else if (copy) {
2247  if (tok3->str() == "{") {
2248  brackets.push(mTokenList.back());
2249  } else if (tok3->str() == "(") {
2250  brackets.push(mTokenList.back());
2251  } else if (tok3->str() == "[") {
2252  brackets.push(mTokenList.back());
2253  } else if (tok3->str() == "}") {
2254  assert(brackets.empty() == false);
2255  assert(brackets.top()->str() == "{");
2256  Token::createMutualLinks(brackets.top(), mTokenList.back());
2257  brackets.pop();
2258  if (brackets.empty() && !Token::Match(tok3, "} >|,|{")) {
2259  inTemplateDefinition = false;
2260  if (isClass && tok3->strAt(1) == ";") {
2261  const Token* tokSemicolon = tok3->next();
2262  mTokenList.addtoken(tokSemicolon, tokSemicolon->linenr(), tokSemicolon->column(), tokSemicolon->fileIndex());
2263  }
2264  break;
2265  }
2266  } else if (tok3->str() == ")") {
2267  assert(brackets.empty() == false);
2268  assert(brackets.top()->str() == "(");
2269  Token::createMutualLinks(brackets.top(), mTokenList.back());
2270  brackets.pop();
2271  } else if (tok3->str() == "]") {
2272  assert(brackets.empty() == false);
2273  assert(brackets.top()->str() == "[");
2274  Token::createMutualLinks(brackets.top(), mTokenList.back());
2275  brackets.pop();
2276  }
2277  }
2278  }
2279 
2280  assert(brackets.empty());
2281  }
2282 
2283  // add new instantiations
2284  for (const auto & inst : newInstantiations) {
2285  if (!inst.token)
2286  continue;
2287  simplifyTemplateArgs(inst.token->tokAt(2), inst.token->next()->findClosingBracket(), &newInstantiations);
2288  // only add recursive instantiation if its arguments are a constant expression
2289  if (templateDeclaration.name() != inst.token->str() ||
2290  (inst.token->tokAt(2)->isNumber() || inst.token->tokAt(2)->isStandardType()))
2291  mTemplateInstantiations.emplace_back(inst.token, inst.scope);
2292  }
2293 }
2294 
2295 static bool isLowerThanLogicalAnd(const Token *lower)
2296 {
2297  return lower->isAssignmentOp() || Token::Match(lower, "}|;|(|[|]|)|,|?|:|%oror%|return|throw|case");
2298 }
2299 static bool isLowerThanOr(const Token* lower)
2300 {
2301  return isLowerThanLogicalAnd(lower) || lower->str() == "&&";
2302 }
2303 static bool isLowerThanXor(const Token* lower)
2304 {
2305  return isLowerThanOr(lower) || lower->str() == "|";
2306 }
2307 static bool isLowerThanAnd(const Token* lower)
2308 {
2309  return isLowerThanXor(lower) || lower->str() == "^";
2310 }
2311 static bool isLowerThanShift(const Token* lower)
2312 {
2313  return isLowerThanAnd(lower) || lower->str() == "&";
2314 }
2315 static bool isLowerThanPlusMinus(const Token* lower)
2316 {
2317  return isLowerThanShift(lower) || Token::Match(lower, "%comp%|<<|>>");
2318 }
2319 static bool isLowerThanMulDiv(const Token* lower)
2320 {
2321  return isLowerThanPlusMinus(lower) || Token::Match(lower, "+|-");
2322 }
2323 static bool isLowerEqualThanMulDiv(const Token* lower)
2324 {
2325  return isLowerThanMulDiv(lower) || Token::Match(lower, "[*/%]");
2326 }
2327 
2328 
2330 {
2331  bool ret = false;
2332  // (1-2)
2333  while (tok->tokAt(3) && tok->isNumber() && tok->tokAt(2)->isNumber()) { // %any% %num% %any% %num% %any%
2334  const Token *before = tok->previous();
2335  if (!before)
2336  break;
2337  const Token* op = tok->next();
2338  const Token* after = tok->tokAt(3);
2339  const std::string &num1 = op->previous()->str();
2340  const std::string &num2 = op->next()->str();
2341  if (Token::Match(before, "* %num% /") && (num2 != "0") && num1 == MathLib::multiply(num2, MathLib::divide(num1, num2))) {
2342  // Division where result is a whole number
2343  } else if (!((op->str() == "*" && (isLowerThanMulDiv(before) || before->str() == "*") && isLowerEqualThanMulDiv(after)) || // associative
2344  (Token::Match(op, "[/%]") && isLowerThanMulDiv(before) && isLowerEqualThanMulDiv(after)) || // NOT associative
2345  (Token::Match(op, "[+-]") && isLowerThanMulDiv(before) && isLowerThanMulDiv(after)) || // Only partially (+) associative, but handled later
2346  (Token::Match(op, ">>|<<") && isLowerThanShift(before) && isLowerThanPlusMinus(after)) || // NOT associative
2347  (op->str() == "&" && isLowerThanShift(before) && isLowerThanShift(after)) || // associative
2348  (op->str() == "^" && isLowerThanAnd(before) && isLowerThanAnd(after)) || // associative
2349  (op->str() == "|" && isLowerThanXor(before) && isLowerThanXor(after)) || // associative
2350  (op->str() == "&&" && isLowerThanOr(before) && isLowerThanOr(after)) ||
2351  (op->str() == "||" && isLowerThanLogicalAnd(before) && isLowerThanLogicalAnd(after))))
2352  break;
2353 
2354  // Don't simplify "%num% / 0"
2355  if (Token::Match(op, "[/%] 0")) {
2356  if (isTemplate)
2357  throw InternalError(op, "Instantiation error: Divide by zero in template instantiation.", InternalError::INSTANTIATION);
2358  return ret;
2359  }
2360 
2361  // Integer operations
2362  if (Token::Match(op, ">>|<<|&|^|%or%")) {
2363  // Don't simplify if operand is negative, shifting with negative
2364  // operand is UB. Bitmasking with negative operand is implementation
2365  // defined behaviour.
2366  if (MathLib::isNegative(num1) || MathLib::isNegative(num2))
2367  break;
2368 
2369  const MathLib::value v1(num1);
2370  const MathLib::value v2(num2);
2371 
2372  if (!v1.isInt() || !v2.isInt())
2373  break;
2374 
2375  switch (op->str()[0]) {
2376  case '<':
2377  tok->str((v1 << v2).str());
2378  break;
2379  case '>':
2380  tok->str((v1 >> v2).str());
2381  break;
2382  case '&':
2383  tok->str((v1 & v2).str());
2384  break;
2385  case '|':
2386  tok->str((v1 | v2).str());
2387  break;
2388  case '^':
2389  tok->str((v1 ^ v2).str());
2390  break;
2391  }
2392  }
2393 
2394  // Logical operations
2395  else if (Token::Match(op, "%oror%|&&")) {
2396  const bool op1 = !MathLib::isNullValue(num1);
2397  const bool op2 = !MathLib::isNullValue(num2);
2398  const bool result = (op->str() == "||") ? (op1 || op2) : (op1 && op2);
2399  tok->str(result ? "1" : "0");
2400  }
2401 
2402  else if (Token::Match(tok->previous(), "- %num% - %num%"))
2403  tok->str(MathLib::add(num1, num2));
2404  else if (Token::Match(tok->previous(), "- %num% + %num%"))
2405  tok->str(MathLib::subtract(num1, num2));
2406  else {
2407  try {
2408  tok->str(MathLib::calculate(num1, num2, op->str()[0]));
2409  } catch (InternalError &e) {
2410  e.token = tok;
2411  throw;
2412  }
2413  }
2414 
2415  tok->deleteNext(2);
2416 
2417  ret = true;
2418  }
2419 
2420  return ret;
2421 }
2422 
2423 static Token *skipTernaryOp(Token *tok, const Token *backToken)
2424 {
2425  unsigned int colonLevel = 1;
2426  while (nullptr != (tok = tok->next())) {
2427  if (tok->str() == "?") {
2428  ++colonLevel;
2429  } else if (tok->str() == ":") {
2430  --colonLevel;
2431  if (colonLevel == 0) {
2432  tok = tok->next();
2433  break;
2434  }
2435  }
2436  if (tok->link() && tok->str() == "(")
2437  tok = tok->link();
2438  else if (Token::Match(tok->next(), "[{};)]") || tok->next() == backToken)
2439  break;
2440  }
2441  if (colonLevel > 0) // Ticket #5214: Make sure the ':' matches the proper '?'
2442  return nullptr;
2443  return tok;
2444 }
2445 
2446 static void invalidateInst(const Token* beg, const Token* end, std::vector<newInstantiation>* newInst) {
2447  if (!newInst)
2448  return;
2449  for (auto& inst : *newInst) {
2450  for (const Token* tok = beg; tok != end; tok = tok->next())
2451  if (inst.token == tok) {
2452  inst.token = nullptr;
2453  break;
2454  }
2455  }
2456 }
2457 
2458 void TemplateSimplifier::simplifyTemplateArgs(Token *start, const Token *end, std::vector<newInstantiation>* newInst)
2459 {
2460  // start could be erased so use the token before start if available
2461  Token * first = (start && start->previous()) ? start->previous() : mTokenList.front();
2462  bool again = true;
2463 
2464  while (again) {
2465  again = false;
2466 
2467  for (Token *tok = first->next(); tok && tok != end; tok = tok->next()) {
2468  if (tok->str() == "sizeof") {
2469  // sizeof('x')
2470  if (Token::Match(tok->next(), "( %char% )")) {
2471  tok->deleteNext();
2472  tok->deleteThis();
2473  tok->deleteNext();
2474  tok->str(std::to_string(1));
2475  again = true;
2476  }
2477 
2478  // sizeof ("text")
2479  else if (Token::Match(tok->next(), "( %str% )")) {
2480  tok->deleteNext();
2481  tok->deleteThis();
2482  tok->deleteNext();
2483  tok->str(std::to_string(Token::getStrLength(tok) + 1));
2484  again = true;
2485  }
2486 
2487  else if (Token::Match(tok->next(), "( %type% * )")) {
2488  tok->str(std::to_string(mTokenizer.sizeOfType(tok->tokAt(3))));
2489  tok->deleteNext(4);
2490  again = true;
2491  } else if (Token::simpleMatch(tok->next(), "( * )")) {
2492  tok->str(std::to_string(mTokenizer.sizeOfType(tok->tokAt(2))));
2493  tok->deleteNext(3);
2494  again = true;
2495  } else if (Token::Match(tok->next(), "( %type% )")) {
2496  const unsigned int size = mTokenizer.sizeOfType(tok->tokAt(2));
2497  if (size > 0) {
2498  tok->str(std::to_string(size));
2499  tok->deleteNext(3);
2500  again = true;
2501  }
2502  } else if (tok->strAt(1) == "(") {
2503  tok = tok->linkAt(1);
2504  }
2505  } else if (Token::Match(tok, "%num% %comp% %num%") &&
2506  MathLib::isInt(tok->str()) &&
2507  MathLib::isInt(tok->strAt(2))) {
2508  if ((Token::Match(tok->previous(), "(|&&|%oror%|,") || tok == start) &&
2509  (Token::Match(tok->tokAt(3), ")|&&|%oror%|?") || tok->tokAt(3) == end)) {
2510  const MathLib::bigint op1(MathLib::toBigNumber(tok->str()));
2511  const std::string &cmp(tok->next()->str());
2512  const MathLib::bigint op2(MathLib::toBigNumber(tok->strAt(2)));
2513 
2514  std::string result;
2515 
2516  if (cmp == "==")
2517  result = bool_to_string(op1 == op2);
2518  else if (cmp == "!=")
2519  result = bool_to_string(op1 != op2);
2520  else if (cmp == "<=")
2521  result = bool_to_string(op1 <= op2);
2522  else if (cmp == ">=")
2523  result = bool_to_string(op1 >= op2);
2524  else if (cmp == "<")
2525  result = bool_to_string(op1 < op2);
2526  else
2527  result = bool_to_string(op1 > op2);
2528 
2529  tok->str(result);
2530  tok->deleteNext(2);
2531  again = true;
2532  tok = tok->previous();
2533  }
2534  }
2535  }
2536 
2537  if (simplifyCalculations(first->next(), end))
2538  again = true;
2539 
2540  for (Token *tok = first->next(); tok && tok != end; tok = tok->next()) {
2541  if (tok->str() == "?" &&
2542  ((tok->previous()->isNumber() || tok->previous()->isBoolean()) ||
2543  Token::Match(tok->tokAt(-3), "( %bool%|%num% )"))) {
2544  const int offset = (tok->previous()->str() == ")") ? 2 : 1;
2545 
2546  // Find the token ":" then go to the next token
2547  Token *colon = skipTernaryOp(tok, end);
2548  if (!colon || colon->previous()->str() != ":" || !colon->next())
2549  continue;
2550 
2551  //handle the GNU extension: "x ? : y" <-> "x ? x : y"
2552  if (colon->previous() == tok->next())
2553  tok->insertToken(tok->strAt(-offset));
2554 
2555  // go back before the condition, if possible
2556  tok = tok->tokAt(-2);
2557  if (offset == 2) {
2558  // go further back before the "("
2559  tok = tok->tokAt(-2);
2560  //simplify the parentheses
2561  tok->deleteNext();
2562  tok->next()->deleteNext();
2563  }
2564 
2565  if (Token::Match(tok->next(), "false|0")) {
2566  invalidateInst(tok->next(), colon, newInst);
2567  // Use code after colon, remove code before it.
2568  Token::eraseTokens(tok, colon);
2569 
2570  tok = tok->next();
2571  again = true;
2572  }
2573 
2574  // The condition is true. Delete the operator after the ":"..
2575  else {
2576  // delete the condition token and the "?"
2577  tok->deleteNext(2);
2578 
2579  unsigned int ternaryOplevel = 0;
2580  for (const Token *endTok = colon; endTok; endTok = endTok->next()) {
2581  if (Token::Match(endTok, "(|[|{"))
2582  endTok = endTok->link();
2583  else if (endTok->str() == "<" && (endTok->strAt(1) == ">" || templateParameters(endTok)))
2584  endTok = endTok->findClosingBracket();
2585  else if (endTok->str() == "?")
2586  ++ternaryOplevel;
2587  else if (Token::Match(endTok, ")|}|]|;|,|:|>")) {
2588  if (endTok->str() == ":" && ternaryOplevel)
2589  --ternaryOplevel;
2590  else if (endTok->str() == ">" && !end)
2591  ;
2592  else {
2593  invalidateInst(colon->tokAt(-1), endTok, newInst);
2594  Token::eraseTokens(colon->tokAt(-2), endTok);
2595  again = true;
2596  break;
2597  }
2598  }
2599  }
2600  }
2601  }
2602  }
2603 
2604  for (Token *tok = first->next(); tok && tok != end; tok = tok->next()) {
2605  if (Token::Match(tok, "( %num%|%bool% )") &&
2606  (tok->previous() && !tok->previous()->isName())) {
2607  tok->deleteThis();
2608  tok->deleteNext();
2609  again = true;
2610  }
2611  }
2612  }
2613 }
2614 
2615 static bool validTokenStart(bool bounded, const Token *tok, const Token *frontToken, int offset)
2616 {
2617  if (!bounded)
2618  return true;
2619 
2620  if (frontToken)
2621  frontToken = frontToken->previous();
2622 
2623  while (tok && offset <= 0) {
2624  if (tok == frontToken)
2625  return false;
2626  ++offset;
2627  tok = tok->previous();
2628  }
2629 
2630  return tok && offset > 0;
2631 }
2632 
2633 static bool validTokenEnd(bool bounded, const Token *tok, const Token *backToken, int offset)
2634 {
2635  if (!bounded)
2636  return true;
2637 
2638  while (tok && offset >= 0) {
2639  if (tok == backToken)
2640  return false;
2641  --offset;
2642  tok = tok->next();
2643  }
2644 
2645  return tok && offset < 0;
2646 }
2647 
2648 // TODO: This is not the correct class for simplifyCalculations(), so it
2649 // should be moved away.
2650 bool TemplateSimplifier::simplifyCalculations(Token* frontToken, const Token *backToken, bool isTemplate)
2651 {
2652  bool ret = false;
2653  const bool bounded = frontToken || backToken;
2654  if (!frontToken) {
2655  frontToken = mTokenList.front();
2656  }
2657  for (Token *tok = frontToken; tok && tok != backToken; tok = tok->next()) {
2658  // Remove parentheses around variable..
2659  // keep parentheses here: dynamic_cast<Fred *>(p);
2660  // keep parentheses here: A operator * (int);
2661  // keep parentheses here: int ( * ( * f ) ( ... ) ) (int) ;
2662  // keep parentheses here: int ( * * ( * compilerHookVector ) (void) ) ( ) ;
2663  // keep parentheses here: operator new [] (size_t);
2664  // keep parentheses here: Functor()(a ... )
2665  // keep parentheses here: ) ( var ) ;
2666  if (validTokenEnd(bounded, tok, backToken, 4) &&
2667  (Token::Match(tok->next(), "( %name% ) ;|)|,|]") ||
2668  (Token::Match(tok->next(), "( %name% ) %cop%") &&
2669  (tok->tokAt(2)->varId()>0 ||
2670  !Token::Match(tok->tokAt(4), "[*&+-~]")))) &&
2671  !tok->isName() &&
2672  tok->str() != ">" &&
2673  tok->str() != ")" &&
2674  tok->str() != "]") {
2675  tok->deleteNext();
2676  tok = tok->next();
2677  tok->deleteNext();
2678  ret = true;
2679  }
2680 
2681  if (validTokenEnd(bounded, tok, backToken, 3) &&
2682  Token::Match(tok->previous(), "(|&&|%oror% %char% %comp% %num% &&|%oror%|)")) {
2683  tok->str(std::to_string(MathLib::toBigNumber(tok->str())));
2684  }
2685 
2686  if (validTokenEnd(bounded, tok, backToken, 5) &&
2687  Token::Match(tok, "decltype ( %type% { } )")) {
2688  tok->deleteThis();
2689  tok->deleteThis();
2690  tok->deleteNext();
2691  tok->deleteNext();
2692  tok->deleteNext();
2693  ret = true;
2694  }
2695 
2696  if (validTokenEnd(bounded, tok, backToken, 3) &&
2697  Token::Match(tok, "decltype ( %bool%|%num% )")) {
2698  tok->deleteThis();
2699  tok->deleteThis();
2700  if (tok->isBoolean())
2701  tok->str("bool");
2702  else if (MathLib::isFloat(tok->str())) {
2703  // MathLib::getSuffix doesn't work for floating point numbers
2704  const char suffix = tok->str().back();
2705  if (suffix == 'f' || suffix == 'F')
2706  tok->str("float");
2707  else if (suffix == 'l' || suffix == 'L') {
2708  tok->str("double");
2709  tok->isLong(true);
2710  } else
2711  tok->str("double");
2712  } else if (MathLib::isInt(tok->str())) {
2713  std::string suffix = MathLib::getSuffix(tok->str());
2714  if (suffix.find("LL") != std::string::npos) {
2715  tok->str("long");
2716  tok->isLong(true);
2717  } else if (suffix.find('L') != std::string::npos)
2718  tok->str("long");
2719  else
2720  tok->str("int");
2721  tok->isUnsigned(suffix.find('U') != std::string::npos);
2722  }
2723  tok->deleteNext();
2724  ret = true;
2725  }
2726 
2727  if (validTokenEnd(bounded, tok, backToken, 2) &&
2728  (Token::Match(tok, "char|short|int|long { }") ||
2729  Token::Match(tok, "char|short|int|long ( )"))) {
2730  tok->str("0"); // FIXME add type suffix
2731  tok->isSigned(false);
2732  tok->isUnsigned(false);
2733  tok->isLong(false);
2734  tok->deleteNext();
2735  tok->deleteNext();
2736  ret = true;
2737  }
2738 
2739  if (tok && tok->isNumber()) {
2740  if (validTokenEnd(bounded, tok, backToken, 2) &&
2741  simplifyNumericCalculations(tok, isTemplate)) {
2742  ret = true;
2743  Token *prev = tok->tokAt(-2);
2744  while (validTokenStart(bounded, tok, frontToken, -2) &&
2745  prev && simplifyNumericCalculations(prev, isTemplate)) {
2746  tok = prev;
2747  prev = prev->tokAt(-2);
2748  }
2749  }
2750 
2751  // Remove redundant conditions (0&&x) (1||x)
2752  if (validTokenStart(bounded, tok, frontToken, -1) &&
2753  validTokenEnd(bounded, tok, backToken, 1) &&
2754  (Token::Match(tok->previous(), "[(=,] 0 &&") ||
2755  Token::Match(tok->previous(), "[(=,] 1 %oror%"))) {
2756  unsigned int par = 0;
2757  const Token *tok2 = tok;
2758  const bool andAnd = (tok->next()->str() == "&&");
2759  for (; tok2; tok2 = tok2->next()) {
2760  if (tok2->str() == "(" || tok2->str() == "[")
2761  ++par;
2762  else if (tok2->str() == ")" || tok2->str() == "]") {
2763  if (par == 0)
2764  break;
2765  --par;
2766  } else if (par == 0 && isLowerThanLogicalAnd(tok2) && (andAnd || tok2->str() != "||"))
2767  break;
2768  }
2769  if (tok2) {
2770  eraseTokens(tok, tok2);
2771  ret = true;
2772  }
2773  continue;
2774  }
2775 
2776  if (tok->str() == "0" && validTokenStart(bounded, tok, frontToken, -1)) {
2777  if (validTokenEnd(bounded, tok, backToken, 1) &&
2778  ((Token::Match(tok->previous(), "[+-] 0 %cop%|;") && isLowerThanMulDiv(tok->next())) ||
2779  (Token::Match(tok->previous(), "%or% 0 %cop%|;") && isLowerThanXor(tok->next())))) {
2780  tok = tok->previous();
2781  if (Token::Match(tok->tokAt(-4), "[;{}] %name% = %name% [+-|] 0 ;") &&
2782  tok->strAt(-3) == tok->previous()->str()) {
2783  tok = tok->tokAt(-4);
2784  tok->deleteNext(5);
2785  } else {
2786  tok = tok->previous();
2787  tok->deleteNext(2);
2788  }
2789  ret = true;
2790  } else if (validTokenEnd(bounded, tok, backToken, 1) &&
2791  (Token::Match(tok->previous(), "[=([,] 0 [+|]") ||
2792  Token::Match(tok->previous(), "return|case 0 [+|]"))) {
2793  tok = tok->previous();
2794  tok->deleteNext(2);
2795  ret = true;
2796  } else if ((((Token::Match(tok->previous(), "[=[(,] 0 * %name%|%num% ,|]|)|;|=|%cop%") ||
2797  Token::Match(tok->previous(), "return|case 0 *|&& %name%|%num% ,|:|;|=|%cop%")) &&
2798  validTokenEnd(bounded, tok, backToken, 3)) ||
2799  (((Token::Match(tok->previous(), "[=[(,] 0 * (") ||
2800  Token::Match(tok->previous(), "return|case 0 *|&& (")) &&
2801  validTokenEnd(bounded, tok, backToken, 2))))) {
2802  tok->deleteNext();
2803  if (tok->next()->str() == "(")
2804  eraseTokens(tok, tok->next()->link());
2805  tok->deleteNext();
2806  ret = true;
2807  } else if (validTokenEnd(bounded, tok, backToken, 4) &&
2808  (Token::Match(tok->previous(), "[=[(,] 0 && *|& %any% ,|]|)|;|=|%cop%") ||
2809  Token::Match(tok->previous(), "return|case 0 && *|& %any% ,|:|;|=|%cop%"))) {
2810  tok->deleteNext();
2811  tok->deleteNext();
2812  if (tok->next()->str() == "(")
2813  eraseTokens(tok, tok->next()->link());
2814  tok->deleteNext();
2815  ret = true;
2816  }
2817  }
2818 
2819  if (tok->str() == "1" && validTokenStart(bounded, tok, frontToken, -1)) {
2820  if (validTokenEnd(bounded, tok, backToken, 3) &&
2821  (Token::Match(tok->previous(), "[=[(,] 1 %oror% %any% ,|]|)|;|=|%cop%") ||
2822  Token::Match(tok->previous(), "return|case 1 %oror% %any% ,|:|;|=|%cop%"))) {
2823  tok->deleteNext();
2824  if (tok->next()->str() == "(")
2825  eraseTokens(tok, tok->next()->link());
2826  tok->deleteNext();
2827  ret = true;
2828  } else if (validTokenEnd(bounded, tok, backToken, 4) &&
2829  (Token::Match(tok->previous(), "[=[(,] 1 %oror% *|& %any% ,|]|)|;|=|%cop%") ||
2830  Token::Match(tok->previous(), "return|case 1 %oror% *|& %any% ,|:|;|=|%cop%"))) {
2831  tok->deleteNext();
2832  tok->deleteNext();
2833  if (tok->next()->str() == "(")
2834  eraseTokens(tok, tok->next()->link());
2835  tok->deleteNext();
2836  ret = true;
2837  }
2838  }
2839 
2840  if ((Token::Match(tok->tokAt(-2), "%any% * 1") &&
2841  validTokenStart(bounded, tok, frontToken, -2)) ||
2842  (Token::Match(tok->previous(), "%any% 1 *") &&
2843  validTokenStart(bounded, tok, frontToken, -1))) {
2844  tok = tok->previous();
2845  if (tok->str() == "*")
2846  tok = tok->previous();
2847  tok->deleteNext(2);
2848  ret = true;
2849  }
2850 
2851  // Remove parentheses around number..
2852  if (validTokenStart(bounded, tok, frontToken, -2) &&
2853  Token::Match(tok->tokAt(-2), "%op%|< ( %num% )") &&
2854  tok->strAt(-2) != ">") {
2855  tok = tok->previous();
2856  tok->deleteThis();
2857  tok->deleteNext();
2858  ret = true;
2859  }
2860 
2861  if (validTokenStart(bounded, tok, frontToken, -1) &&
2862  validTokenEnd(bounded, tok, backToken, 1) &&
2863  (Token::Match(tok->previous(), "( 0 [|+]") ||
2864  Token::Match(tok->previous(), "[|+-] 0 )"))) {
2865  tok = tok->previous();
2866  if (Token::Match(tok, "[|+-]"))
2867  tok = tok->previous();
2868  tok->deleteNext(2);
2869  ret = true;
2870  }
2871 
2872  if (validTokenEnd(bounded, tok, backToken, 2) &&
2873  Token::Match(tok, "%num% %comp% %num%") &&
2874  MathLib::isInt(tok->str()) &&
2875  MathLib::isInt(tok->strAt(2))) {
2876  if (validTokenStart(bounded, tok, frontToken, -1) &&
2877  Token::Match(tok->previous(), "(|&&|%oror%") &&
2878  Token::Match(tok->tokAt(3), ")|&&|%oror%|?")) {
2879  const MathLib::bigint op1(MathLib::toBigNumber(tok->str()));
2880  const std::string &cmp(tok->next()->str());
2881  const MathLib::bigint op2(MathLib::toBigNumber(tok->strAt(2)));
2882 
2883  std::string result;
2884 
2885  if (cmp == "==")
2886  result = (op1 == op2) ? "1" : "0";
2887  else if (cmp == "!=")
2888  result = (op1 != op2) ? "1" : "0";
2889  else if (cmp == "<=")
2890  result = (op1 <= op2) ? "1" : "0";
2891  else if (cmp == ">=")
2892  result = (op1 >= op2) ? "1" : "0";
2893  else if (cmp == "<")
2894  result = (op1 < op2) ? "1" : "0";
2895  else
2896  result = (op1 > op2) ? "1" : "0";
2897 
2898  tok->str(result);
2899  tok->deleteNext(2);
2900  ret = true;
2901  tok = tok->previous();
2902  }
2903  }
2904  }
2905  }
2906  return ret;
2907 }
2908 
2910  const Token * tok,
2911  std::vector<const Token *> & typeParametersInDeclaration)
2912 {
2913  assert(tok->strAt(-1) == "<");
2914 
2915  typeParametersInDeclaration.clear();
2916  const Token *end = tok->previous()->findClosingBracket();
2917  bool inDefaultValue = false;
2918  for (; tok && tok!= end; tok = tok->next()) {
2919  if (Token::simpleMatch(tok, "template <")) {
2920  const Token *closing = tok->next()->findClosingBracket();
2921  if (closing)
2922  tok = closing->next();
2923  } else if (tok->link() && Token::Match(tok, "{|(|["))
2924  tok = tok->link();
2925  else if (Token::Match(tok, "%name% ,|>|=")) {
2926  if (!inDefaultValue) {
2927  typeParametersInDeclaration.push_back(tok);
2928  if (tok->strAt(1) == "=")
2929  inDefaultValue = true;
2930  }
2931  } else if (inDefaultValue) {
2932  if (tok->str() == ",")
2933  inDefaultValue = false;
2934  else if (tok->str() == "<") {
2935  const Token *closing = tok->findClosingBracket();
2936  if (closing)
2937  tok = closing;
2938  }
2939  }
2940  }
2941 }
2942 
2944  const Token *templateDeclarationNameToken,
2945  const Token *templateInstantiationNameToken,
2946  const std::list<const Token *> & specializations)
2947 {
2948  // Is there a matching specialization?
2949  for (std::list<const Token *>::const_iterator it = specializations.cbegin(); it != specializations.cend(); ++it) {
2950  if (!Token::Match(*it, "%name% <"))
2951  continue;
2952  const Token *startToken = (*it);
2953  while (startToken->previous() && !Token::Match(startToken->previous(), "[;{}]"))
2954  startToken = startToken->previous();
2955  if (!Token::simpleMatch(startToken, "template <"))
2956  continue;
2957  // cppcheck-suppress shadowFunction - TODO: fix this
2958  std::vector<const Token *> templateParameters;
2960 
2961  const Token *instToken = templateInstantiationNameToken->tokAt(2);
2962  const Token *declToken = (*it)->tokAt(2);
2963  const Token * const endToken = (*it)->next()->findClosingBracket();
2964  if (!endToken)
2965  continue;
2966  while (declToken != endToken) {
2967  if (declToken->str() != instToken->str() ||
2968  declToken->isSigned() != instToken->isSigned() ||
2969  declToken->isUnsigned() != instToken->isUnsigned() ||
2970  declToken->isLong() != instToken->isLong()) {
2971  int nr = 0;
2972  while (nr < templateParameters.size() && templateParameters[nr]->str() != declToken->str())
2973  ++nr;
2974 
2975  if (nr == templateParameters.size())
2976  break;
2977  }
2978  declToken = declToken->next();
2979  instToken = instToken->next();
2980  }
2981 
2982  if (declToken && instToken && declToken == endToken && instToken->str() == ">") {
2983  // specialization matches.
2984  return templateDeclarationNameToken == *it;
2985  }
2986  }
2987 
2988  // No specialization matches. Return true if the declaration is not a specialization.
2989  return Token::Match(templateDeclarationNameToken, "%name% !!<") &&
2990  (templateDeclarationNameToken->str().find('<') == std::string::npos);
2991 }
2992 
2994  Token *tok2,
2995  std::list<std::string> &typeStringsUsedInTemplateInstantiation)
2996 {
2997  std::string typeForNewName;
2998  unsigned int indentlevel = 0;
2999  const Token * endToken = tok2->next()->findClosingBracket();
3000  for (Token *tok3 = tok2->tokAt(2); tok3 != endToken && (indentlevel > 0 || tok3->str() != ">"); tok3 = tok3->next()) {
3001  // #2721 - unhandled [ => bail out
3002  if (tok3->str() == "[" && !Token::Match(tok3->next(), "%num%| ]")) {
3003  typeForNewName.clear();
3004  break;
3005  }
3006  if (!tok3->next()) {
3007  typeForNewName.clear();
3008  break;
3009  }
3010  if (Token::Match(tok3->tokAt(-2), "<|,|:: %name% <") && (tok3->strAt(1) == ">" || templateParameters(tok3)))
3011  ++indentlevel;
3012  else if (indentlevel > 0 && Token::Match(tok3, "> ,|>|::"))
3013  --indentlevel;
3014  else if (indentlevel == 0 && Token::Match(tok3->previous(), "[<,]")) {
3015  mTypesUsedInTemplateInstantiation.emplace_back(tok3, "");
3016  }
3017  if (Token::Match(tok3, "(|["))
3018  ++indentlevel;
3019  else if (Token::Match(tok3, ")|]"))
3020  --indentlevel;
3021  const bool constconst = tok3->str() == "const" && tok3->strAt(1) == "const";
3022  if (!constconst) {
3023  if (tok3->isUnsigned())
3024  typeStringsUsedInTemplateInstantiation.emplace_back("unsigned");
3025  else if (tok3->isSigned())
3026  typeStringsUsedInTemplateInstantiation.emplace_back("signed");
3027  if (tok3->isLong())
3028  typeStringsUsedInTemplateInstantiation.emplace_back("long");
3029  typeStringsUsedInTemplateInstantiation.push_back(tok3->str());
3030  }
3031  // add additional type information
3032  if (!constconst && !Token::Match(tok3, "class|struct|enum")) {
3033  if (!typeForNewName.empty())
3034  typeForNewName += ' ';
3035  if (tok3->isUnsigned())
3036  typeForNewName += "unsigned ";
3037  else if (tok3->isSigned())
3038  typeForNewName += "signed ";
3039  if (tok3->isLong()) {
3040  typeForNewName += "long ";
3041  }
3042  typeForNewName += tok3->str();
3043  }
3044  }
3045 
3046  return typeForNewName;
3047 }
3048 
3050  const TokenAndName &templateDeclaration,
3051  const std::list<const Token *> &specializations,
3052  const std::time_t maxtime,
3053  std::set<std::string> &expandedtemplates)
3054 {
3055  // this variable is not used at the moment. The intention was to
3056  // allow continuous instantiations until all templates has been expanded
3057  //bool done = false;
3058 
3059  // Contains tokens such as "T"
3060  std::vector<const Token *> typeParametersInDeclaration;
3061  getTemplateParametersInDeclaration(templateDeclaration.token()->tokAt(2), typeParametersInDeclaration);
3062  const bool printDebug = mSettings.debugwarnings;
3063  const bool specialized = templateDeclaration.isSpecialization();
3064  const bool isfunc = templateDeclaration.isFunction();
3065  const bool isVar = templateDeclaration.isVariable();
3066 
3067  // locate template usage..
3068  std::string::size_type numberOfTemplateInstantiations = mTemplateInstantiations.size();
3069  unsigned int recursiveCount = 0;
3070 
3071  bool instantiated = false;
3072 
3073  for (const TokenAndName &instantiation : mTemplateInstantiations) {
3074  // skip deleted instantiations
3075  if (!instantiation.token())
3076  continue;
3077  if (numberOfTemplateInstantiations != mTemplateInstantiations.size()) {
3078  numberOfTemplateInstantiations = mTemplateInstantiations.size();
3079  ++recursiveCount;
3080  if (recursiveCount > mSettings.maxTemplateRecursion) {
3082  std::list<std::string> typeStringsUsedInTemplateInstantiation;
3083  const std::string typeForNewName = templateDeclaration.name() + "<" + getNewName(instantiation.token(), typeStringsUsedInTemplateInstantiation) + ">";
3084 
3085  const std::list<const Token *> callstack(1, instantiation.token());
3086  const ErrorMessage errmsg(callstack,
3087  &mTokenizer.list,
3089  "templateRecursion",
3090  "TemplateSimplifier: max template recursion ("
3091  + std::to_string(mSettings.maxTemplateRecursion)
3092  + ") reached for template '"+typeForNewName+"'. You might want to limit Cppcheck recursion.",
3094  mErrorLogger.reportErr(errmsg);
3095  }
3096 
3097  // bail out..
3098  break;
3099  }
3100  }
3101 
3102  // already simplified
3103  if (!Token::Match(instantiation.token(), "%name% <"))
3104  continue;
3105 
3106  if (!((instantiation.fullName() == templateDeclaration.fullName()) ||
3107  (instantiation.name() == templateDeclaration.name() &&
3108  instantiation.fullName() == templateDeclaration.scope()))) {
3109  // FIXME: fallback to not matching scopes until type deduction works
3110 
3111  // names must match
3112  if (instantiation.name() != templateDeclaration.name())
3113  continue;
3114 
3115  // scopes must match when present
3116  if (!instantiation.scope().empty() && !templateDeclaration.scope().empty())
3117  continue;
3118  }
3119 
3120  // make sure constructors and destructors don't match each other
3121  if (templateDeclaration.nameToken()->strAt(-1) == "~" && instantiation.token()->strAt(-1) != "~")
3122  continue;
3123 
3124  // template families should match
3125  if (!instantiation.isFunction() && templateDeclaration.isFunction()) {
3126  // there are exceptions
3127  if (!Token::simpleMatch(instantiation.token()->tokAt(-2), "decltype ("))
3128  continue;
3129  }
3130 
3131  if (templateDeclaration.isFunction() && instantiation.isFunction()) {
3132  std::vector<const Token*> declFuncArgs;
3133  getFunctionArguments(templateDeclaration.nameToken(), declFuncArgs);
3134  std::vector<const Token*> instFuncParams;
3135  getFunctionArguments(instantiation.token(), instFuncParams);
3136 
3137  if (declFuncArgs.size() != instFuncParams.size()) {
3138  // check for default arguments
3139  const Token* tok = templateDeclaration.nameToken()->tokAt(2);
3140  const Token* end = templateDeclaration.nameToken()->linkAt(1);
3141  size_t count = 0;
3142  for (; tok != end; tok = tok->next()) {
3143  if (tok->str() == "=")
3144  count++;
3145  }
3146 
3147  if (instFuncParams.size() < (declFuncArgs.size() - count) || instFuncParams.size() > declFuncArgs.size())
3148  continue;
3149  }
3150  }
3151 
3152  // A global function can't be called through a pointer.
3153  if (templateDeclaration.isFunction() && templateDeclaration.scope().empty() &&
3154  (instantiation.token()->strAt(-1) == "." ||
3155  Token::simpleMatch(instantiation.token()->tokAt(-2), ". template")))
3156  continue;
3157 
3158  if (!matchSpecialization(templateDeclaration.nameToken(), instantiation.token(), specializations))
3159  continue;
3160 
3161  Token * const tok2 = instantiation.token();
3162  if (!mTokenList.getFiles().empty())
3163  mErrorLogger.reportProgress(mTokenList.getFiles()[0], "TemplateSimplifier::simplifyTemplateInstantiations()", tok2->progressValue());
3164 
3165  if (maxtime > 0 && std::time(nullptr) > maxtime) {
3166  if (mSettings.debugwarnings) {
3168  ErrorMessage errmsg({std::move(loc)},
3169  emptyString,
3171  "Template instantiation maximum time exceeded",
3172  "templateMaxTime",
3174  mErrorLogger.reportErr(errmsg);
3175  }
3176  return false;
3177  }
3178 
3179  assert(mTokenList.validateToken(tok2)); // that assertion fails on examples from #6021
3180 
3181  const Token *startToken = tok2;
3182  while (Token::Match(startToken->tokAt(-2), ">|%name% :: %name%")) {
3183  if (startToken->strAt(-2) == ">") {
3184  const Token * tok3 = startToken->tokAt(-2)->findOpeningBracket();
3185  if (tok3)
3186  startToken = tok3->previous();
3187  else
3188  break;
3189  } else
3190  startToken = startToken->tokAt(-2);
3191  }
3192 
3193  if (Token::Match(startToken->previous(), ";|{|}|=|const") &&
3194  (!specialized && !instantiateMatch(tok2, typeParametersInDeclaration.size(), templateDeclaration.isVariadic(), isfunc ? "(" : isVar ? ";|%op%|(" : "*|&|::| %name%")))
3195  continue;
3196 
3197  // New type..
3199  std::list<std::string> typeStringsUsedInTemplateInstantiation;
3200  std::string typeForNewName = getNewName(tok2, typeStringsUsedInTemplateInstantiation);
3201 
3202  if ((typeForNewName.empty() && !templateDeclaration.isVariadic()) ||
3203  (!typeParametersInDeclaration.empty() && !instantiateMatch(tok2, typeParametersInDeclaration.size(), templateDeclaration.isVariadic(), nullptr))) {
3204  if (printDebug) {
3205  std::list<const Token *> callstack(1, tok2);
3206  mErrorLogger.reportErr(ErrorMessage(callstack, &mTokenList, Severity::debug, "templateInstantiation",
3207  "Failed to instantiate template \"" + instantiation.name() + "\". The checking continues anyway.", Certainty::normal));
3208  }
3209  if (typeForNewName.empty())
3210  continue;
3211  break;
3212  }
3213 
3214  // New classname/funcname..
3215  const std::string newName(templateDeclaration.name() + " < " + typeForNewName + " >");
3216  const std::string newFullName(templateDeclaration.scope() + (templateDeclaration.scope().empty() ? "" : " :: ") + newName);
3217 
3218  if (expandedtemplates.insert(newFullName).second) {
3219  expandTemplate(templateDeclaration, instantiation, typeParametersInDeclaration, newName, !specialized && !isVar);
3220  instantiated = true;
3221  mChanged = true;
3222  }
3223 
3224  // Replace all these template usages..
3225  replaceTemplateUsage(instantiation, typeStringsUsedInTemplateInstantiation, newName);
3226  }
3227 
3228  // process uninstantiated templates
3229  // TODO: remove the specialized check and handle all uninstantiated templates someday.
3230  if (!instantiated && specialized) {
3231  auto * tok2 = const_cast<Token *>(templateDeclaration.nameToken());
3232  if (!mTokenList.getFiles().empty())
3233  mErrorLogger.reportProgress(mTokenList.getFiles()[0], "TemplateSimplifier::simplifyTemplateInstantiations()", tok2->progressValue());
3234 
3235  if (maxtime > 0 && std::time(nullptr) > maxtime) {
3236  if (mSettings.debugwarnings) {
3238  ErrorMessage errmsg({std::move(loc)},
3239  emptyString,
3241  "Template instantiation maximum time exceeded",
3242  "templateMaxTime",
3244  mErrorLogger.reportErr(errmsg);
3245  }
3246  return false;
3247  }
3248 
3249  assert(mTokenList.validateToken(tok2)); // that assertion fails on examples from #6021
3250 
3251  Token *startToken = tok2;
3252  while (Token::Match(startToken->tokAt(-2), ">|%name% :: %name%")) {
3253  if (startToken->strAt(-2) == ">") {
3254  Token * tok3 = startToken->tokAt(-2)->findOpeningBracket();
3255  if (tok3)
3256  startToken = tok3->previous();
3257  else
3258  break;
3259  } else
3260  startToken = startToken->tokAt(-2);
3261  }
3262 
3263  // TODO: re-enable when specialized check is removed
3264  // if (Token::Match(startToken->previous(), ";|{|}|=|const") &&
3265  // (!specialized && !instantiateMatch(tok2, typeParametersInDeclaration.size(), isfunc ? "(" : isVar ? ";|%op%|(" : "*|&|::| %name%")))
3266  // return false;
3267 
3268  // already simplified
3269  if (!Token::Match(tok2, "%name% <"))
3270  return false;
3271 
3272  if (!matchSpecialization(templateDeclaration.nameToken(), tok2, specializations))
3273  return false;
3274 
3275  // New type..
3277  std::list<std::string> typeStringsUsedInTemplateInstantiation;
3278  std::string typeForNewName = getNewName(tok2, typeStringsUsedInTemplateInstantiation);
3279 
3280  if (typeForNewName.empty()) {
3281  if (printDebug) {
3282  std::list<const Token *> callstack(1, tok2);
3283  mErrorLogger.reportErr(ErrorMessage(callstack, &mTokenList, Severity::debug, "templateInstantiation",
3284  "Failed to instantiate template \"" + templateDeclaration.name() + "\". The checking continues anyway.", Certainty::normal));
3285  }
3286  return false;
3287  }
3288 
3289  // New classname/funcname..
3290  const std::string newName(templateDeclaration.name() + " < " + typeForNewName + " >");
3291  const std::string newFullName(templateDeclaration.scope() + (templateDeclaration.scope().empty() ? "" : " :: ") + newName);
3292 
3293  if (expandedtemplates.insert(newFullName).second) {
3294  expandTemplate(templateDeclaration, templateDeclaration, typeParametersInDeclaration, newName, !specialized && !isVar);
3295  instantiated = true;
3296  mChanged = true;
3297  }
3298 
3299  // Replace all these template usages..
3300  replaceTemplateUsage(templateDeclaration, typeStringsUsedInTemplateInstantiation, newName);
3301  }
3302 
3303  // Template has been instantiated .. then remove the template declaration
3304  return instantiated;
3305 }
3306 
3307 static bool matchTemplateParameters(const Token *nameTok, const std::list<std::string> &strings)
3308 {
3309  std::list<std::string>::const_iterator it = strings.cbegin();
3310  const Token *tok = nameTok->tokAt(2);
3311  const Token *end = nameTok->next()->findClosingBracket();
3312  if (!end)
3313  return false;
3314  while (tok && tok != end && it != strings.cend()) {
3315  if (tok->isUnsigned()) {
3316  if (*it != "unsigned")
3317  return false;
3318 
3319  ++it;
3320  if (it == strings.cend())
3321  return false;
3322  } else if (tok->isSigned()) {
3323  if (*it != "signed")
3324  return false;
3325 
3326  ++it;
3327  if (it == strings.cend())
3328  return false;
3329  }
3330  if (tok->isLong()) {
3331  if (*it != "long")
3332  return false;
3333 
3334  ++it;
3335  if (it == strings.cend())
3336  return false;
3337  }
3338  if (*it != tok->str())
3339  return false;
3340  tok = tok->next();
3341  ++it;
3342  }
3343  return it == strings.cend() && tok && tok->str() == ">";
3344 }
3345 
3347  const TokenAndName &instantiation,
3348  const std::list<std::string> &typeStringsUsedInTemplateInstantiation,
3349  const std::string &newName)
3350 {
3351  std::list<std::pair<Token *, Token *>> removeTokens;
3352  for (Token *nameTok = mTokenList.front(); nameTok; nameTok = nameTok->next()) {
3353  if (!Token::Match(nameTok, "%name% <") ||
3354  Token::Match(nameTok, "template|const_cast|dynamic_cast|reinterpret_cast|static_cast"))
3355  continue;
3356 
3357  std::set<TemplateSimplifier::TokenAndName*>* pointers = nameTok->templateSimplifierPointers();
3358 
3359  // check if instantiation matches token instantiation from pointer
3360  if (pointers && !pointers->empty()) {
3361  // check full name
3362  if (instantiation.fullName() != (*pointers->begin())->fullName()) {
3363  // FIXME: fallback to just matching name
3364  if (nameTok->str() != instantiation.name())
3365  continue;
3366  }
3367  }
3368  // no pointer available look at tokens directly
3369  else {
3370  // FIXME: fallback to just matching name
3371  if (nameTok->str() != instantiation.name())
3372  continue;
3373  }
3374 
3375  if (!matchTemplateParameters(nameTok, typeStringsUsedInTemplateInstantiation))
3376  continue;
3377 
3378  Token *tok2 = nameTok->next()->findClosingBracket();
3379 
3380  if (!tok2)
3381  break;
3382 
3383  const Token * const nameTok1 = nameTok;
3384  nameTok->str(newName);
3385 
3386  // matching template usage => replace tokens..
3387  // Foo < int > => Foo<int>
3388  for (const Token *tok = nameTok1->next(); tok != tok2; tok = tok->next()) {
3389  if (tok->isName() && tok->templateSimplifierPointers() && !tok->templateSimplifierPointers()->empty()) {
3390  std::list<TokenAndName>::iterator ti;
3391  for (ti = mTemplateInstantiations.begin(); ti != mTemplateInstantiations.end();) {
3392  if (ti->token() == tok) {
3393  ti = mTemplateInstantiations.erase(ti);
3394  break;
3395  }
3396  ++ti;
3397  }
3398  }
3399  }
3400  // Fix crash in #9007
3401  if (Token::simpleMatch(nameTok->previous(), ">"))
3402  mTemplateNamePos.erase(nameTok->previous());
3403  removeTokens.emplace_back(nameTok, tok2->next());
3404 
3405  nameTok = tok2;
3406  }
3407  while (!removeTokens.empty()) {
3408  eraseTokens(removeTokens.back().first, removeTokens.back().second);
3409  removeTokens.pop_back();
3410  }
3411 }
3412 
3413 static bool specMatch(
3416 {
3417  // make sure decl is really a declaration
3418  if (decl.isPartialSpecialization() || decl.isSpecialization() || decl.isAlias() || decl.isFriend())
3419  return false;
3420 
3421  if (!spec.isSameFamily(decl))
3422  return false;
3423 
3424  // make sure the scopes and names match
3425  if (spec.fullName() == decl.fullName()) {
3426  if (spec.isFunction()) {
3427  std::vector<const Token*> specArgs;
3428  std::vector<const Token*> declArgs;
3429  getFunctionArguments(spec.nameToken(), specArgs);
3430  getFunctionArguments(decl.nameToken(), declArgs);
3431 
3432  if (specArgs.size() == declArgs.size()) {
3433  // @todo make sure function parameters also match
3434  return true;
3435  }
3436  } else
3437  return true;
3438  }
3439 
3440  return false;
3441 }
3442 
3444 {
3445  // try to locate a matching declaration for each user defined specialization
3446  for (const auto& spec : mTemplateDeclarations) {
3447  if (spec.isSpecialization()) {
3448  auto it = std::find_if(mTemplateDeclarations.cbegin(), mTemplateDeclarations.cend(), [&](const TokenAndName& decl) {
3449  return specMatch(spec, decl);
3450  });
3451  if (it != mTemplateDeclarations.cend())
3452  mTemplateSpecializationMap[spec.token()] = it->token();
3453  else {
3454  it = std::find_if(mTemplateForwardDeclarations.cbegin(), mTemplateForwardDeclarations.cend(), [&](const TokenAndName& decl) {
3455  return specMatch(spec, decl);
3456  });
3457  if (it != mTemplateForwardDeclarations.cend())
3458  mTemplateSpecializationMap[spec.token()] = it->token();
3459  }
3460  }
3461  }
3462 }
3463 
3465 {
3466  // try to locate a matching declaration for each user defined partial specialization
3467  for (const auto& spec : mTemplateDeclarations) {
3468  if (spec.isPartialSpecialization()) {
3469  auto it = std::find_if(mTemplateDeclarations.cbegin(), mTemplateDeclarations.cend(), [&](const TokenAndName& decl) {
3470  return specMatch(spec, decl);
3471  });
3472  if (it != mTemplateDeclarations.cend())
3473  mTemplatePartialSpecializationMap[spec.token()] = it->token();
3474  else {
3475  it = std::find_if(mTemplateForwardDeclarations.cbegin(), mTemplateForwardDeclarations.cend(), [&](const TokenAndName& decl) {
3476  return specMatch(spec, decl);
3477  });
3478  if (it != mTemplateForwardDeclarations.cend())
3479  mTemplatePartialSpecializationMap[spec.token()] = it->token();
3480  }
3481  }
3482  }
3483 }
3484 
3486 {
3487  // try to locate a matching declaration for each forward declaration
3488  for (const auto & forwardDecl : mTemplateForwardDeclarations) {
3489  std::vector<const Token *> params1;
3490 
3491  getTemplateParametersInDeclaration(forwardDecl.token()->tokAt(2), params1);
3492 
3493  for (auto & decl : mTemplateDeclarations) {
3494  // skip partializations, type aliases and friends
3495  if (decl.isPartialSpecialization() || decl.isAlias() || decl.isFriend())
3496  continue;
3497 
3498  std::vector<const Token *> params2;
3499 
3500  getTemplateParametersInDeclaration(decl.token()->tokAt(2), params2);
3501 
3502  // make sure the number of arguments match
3503  if (params1.size() == params2.size()) {
3504  // make sure the scopes and names match
3505  if (forwardDecl.fullName() == decl.fullName()) {
3506  // save forward declaration for lookup later
3507  if ((decl.nameToken()->strAt(1) == "(" && forwardDecl.nameToken()->strAt(1) == "(") ||
3508  (decl.nameToken()->strAt(1) == "{" && forwardDecl.nameToken()->strAt(1) == ";")) {
3509  mTemplateForwardDeclarationsMap[decl.token()] = forwardDecl.token();
3510  }
3511 
3512  for (size_t k = 0; k < params1.size(); k++) {
3513  // copy default value to declaration if not present
3514  if (params1[k]->strAt(1) == "=" && params2[k]->strAt(1) != "=") {
3515  int level = 0;
3516  const Token *end = params1[k]->next();
3517  while (end && !(level == 0 && Token::Match(end, ",|>"))) {
3518  if (Token::Match(end, "{|(|<"))
3519  level++;
3520  else if (Token::Match(end, "}|)|>"))
3521  level--;
3522  end = end->next();
3523  }
3524  if (end)
3525  TokenList::copyTokens(const_cast<Token *>(params2[k]), params1[k]->next(), end->previous());
3526  }
3527  }
3528 
3529  // update parameter end pointer
3530  decl.paramEnd(decl.token()->next()->findClosingBracket());
3531  }
3532  }
3533  }
3534  }
3535 }
3536 
3537 void TemplateSimplifier::printOut(const TokenAndName &tokenAndName, const std::string &indent) const
3538 {
3539  std::cout << indent << "token: ";
3540  if (tokenAndName.token())
3541  std::cout << "\"" << tokenAndName.token()->str() << "\" " << mTokenList.fileLine(tokenAndName.token());
3542  else
3543  std::cout << "nullptr";
3544  std::cout << std::endl;
3545  std::cout << indent << "scope: \"" << tokenAndName.scope() << "\"" << std::endl;
3546  std::cout << indent << "name: \"" << tokenAndName.name() << "\"" << std::endl;
3547  std::cout << indent << "fullName: \"" << tokenAndName.fullName() << "\"" << std::endl;
3548  std::cout << indent << "nameToken: ";
3549  if (tokenAndName.nameToken())
3550  std::cout << "\"" << tokenAndName.nameToken()->str() << "\" " << mTokenList.fileLine(tokenAndName.nameToken());
3551  else
3552  std::cout << "nullptr";
3553  std::cout << std::endl;
3554  std::cout << indent << "paramEnd: ";
3555  if (tokenAndName.paramEnd())
3556  std::cout << "\"" << tokenAndName.paramEnd()->str() << "\" " << mTokenList.fileLine(tokenAndName.paramEnd());
3557  else
3558  std::cout << "nullptr";
3559  std::cout << std::endl;
3560  std::cout << indent << "flags: ";
3561  if (tokenAndName.isClass())
3562  std::cout << " isClass";
3563  if (tokenAndName.isFunction())
3564  std::cout << " isFunction";
3565  if (tokenAndName.isVariable())
3566  std::cout << " isVariable";
3567  if (tokenAndName.isAlias())
3568  std::cout << " isAlias";
3569  if (tokenAndName.isSpecialization())
3570  std::cout << " isSpecialization";
3571  if (tokenAndName.isPartialSpecialization())
3572  std::cout << " isPartialSpecialization";
3573  if (tokenAndName.isForwardDeclaration())
3574  std::cout << " isForwardDeclaration";
3575  if (tokenAndName.isVariadic())
3576  std::cout << " isVariadic";
3577  if (tokenAndName.isFriend())
3578  std::cout << " isFriend";
3579  std::cout << std::endl;
3580  if (tokenAndName.token() && !tokenAndName.paramEnd() && tokenAndName.token()->strAt(1) == "<") {
3581  const Token *end = tokenAndName.token()->next()->findClosingBracket();
3582  if (end) {
3583  const Token *start = tokenAndName.token()->next();
3584  std::cout << indent << "type: ";
3585  while (start && start != end) {
3586  if (start->isUnsigned())
3587  std::cout << "unsigned";
3588  else if (start->isSigned())
3589  std::cout << "signed";
3590  if (start->isLong())
3591  std::cout << "long";
3592  std::cout << start->str();
3593  start = start->next();
3594  }
3595  std::cout << end->str() << std::endl;
3596  }
3597  } else if (tokenAndName.isAlias() && tokenAndName.paramEnd()) {
3598  if (tokenAndName.aliasStartToken()) {
3599  std::cout << indent << "aliasStartToken: \"" << tokenAndName.aliasStartToken()->str() << "\" "
3600  << mTokenList.fileLine(tokenAndName.aliasStartToken()) << std::endl;
3601  }
3602  if (tokenAndName.aliasEndToken()) {
3603  std::cout << indent << "aliasEndToken: \"" << tokenAndName.aliasEndToken()->str() << "\" "
3604  << mTokenList.fileLine(tokenAndName.aliasEndToken()) << std::endl;
3605  }
3606  }
3607 }
3608 
3609 void TemplateSimplifier::printOut(const std::string & text) const
3610 {
3611  std::cout << std::endl;
3612  std::cout << text << std::endl;
3613  std::cout << std::endl;
3614  std::cout << "mTemplateDeclarations: " << mTemplateDeclarations.size() << std::endl;
3615  int count = 0;
3616  for (const auto & decl : mTemplateDeclarations) {
3617  std::cout << "mTemplateDeclarations[" << count++ << "]:" << std::endl;
3618  printOut(decl);
3619  }
3620  std::cout << "mTemplateForwardDeclarations: " << mTemplateForwardDeclarations.size() << std::endl;
3621  count = 0;
3622  for (const auto & decl : mTemplateForwardDeclarations) {
3623  std::cout << "mTemplateForwardDeclarations[" << count++ << "]:" << std::endl;
3624  printOut(decl);
3625  }
3626  std::cout << "mTemplateForwardDeclarationsMap: " << mTemplateForwardDeclarationsMap.size() << std::endl;
3627  unsigned int mapIndex = 0;
3628  for (const auto & mapItem : mTemplateForwardDeclarationsMap) {
3629  unsigned int declIndex = 0;
3630  for (const auto & decl : mTemplateDeclarations) {
3631  if (mapItem.first == decl.token()) {
3632  unsigned int forwardIndex = 0;
3633  for (const auto & forwardDecl : mTemplateForwardDeclarations) {
3634  if (mapItem.second == forwardDecl.token()) {
3635  std::cout << "mTemplateForwardDeclarationsMap[" << mapIndex << "]:" << std::endl;
3636  std::cout << " mTemplateDeclarations[" << declIndex
3637  << "] => mTemplateForwardDeclarations[" << forwardIndex << "]" << std::endl;
3638  break;
3639  }
3640  forwardIndex++;
3641  }
3642  break;
3643  }
3644  declIndex++;
3645  }
3646  mapIndex++;
3647  }
3648  std::cout << "mTemplateSpecializationMap: " << mTemplateSpecializationMap.size() << std::endl;
3649  for (const auto & mapItem : mTemplateSpecializationMap) {
3650  unsigned int decl1Index = 0;
3651  for (const auto & decl1 : mTemplateDeclarations) {
3652  if (decl1.isSpecialization() && mapItem.first == decl1.token()) {
3653  bool found = false;
3654  unsigned int decl2Index = 0;
3655  for (const auto & decl2 : mTemplateDeclarations) {
3656  if (mapItem.second == decl2.token()) {
3657  std::cout << "mTemplateSpecializationMap[" << mapIndex << "]:" << std::endl;
3658  std::cout << " mTemplateDeclarations[" << decl1Index
3659  << "] => mTemplateDeclarations[" << decl2Index << "]" << std::endl;
3660  found = true;
3661  break;
3662  }
3663  decl2Index++;
3664  }
3665  if (!found) {
3666  decl2Index = 0;
3667  for (const auto & decl2 : mTemplateForwardDeclarations) {
3668  if (mapItem.second == decl2.token()) {
3669  std::cout << "mTemplateSpecializationMap[" << mapIndex << "]:" << std::endl;
3670  std::cout << " mTemplateDeclarations[" << decl1Index
3671  << "] => mTemplateForwardDeclarations[" << decl2Index << "]" << std::endl;
3672  break;
3673  }
3674  decl2Index++;
3675  }
3676  }
3677  break;
3678  }
3679  decl1Index++;
3680  }
3681  mapIndex++;
3682  }
3683  std::cout << "mTemplatePartialSpecializationMap: " << mTemplatePartialSpecializationMap.size() << std::endl;
3684  for (const auto & mapItem : mTemplatePartialSpecializationMap) {
3685  unsigned int decl1Index = 0;
3686  for (const auto & decl1 : mTemplateDeclarations) {
3687  if (mapItem.first == decl1.token()) {
3688  bool found = false;
3689  unsigned int decl2Index = 0;
3690  for (const auto & decl2 : mTemplateDeclarations) {
3691  if (mapItem.second == decl2.token()) {
3692  std::cout << "mTemplatePartialSpecializationMap[" << mapIndex << "]:" << std::endl;
3693  std::cout << " mTemplateDeclarations[" << decl1Index
3694  << "] => mTemplateDeclarations[" << decl2Index << "]" << std::endl;
3695  found = true;
3696  break;
3697  }
3698  decl2Index++;
3699  }
3700  if (!found) {
3701  decl2Index = 0;
3702  for (const auto & decl2 : mTemplateForwardDeclarations) {
3703  if (mapItem.second == decl2.token()) {
3704  std::cout << "mTemplatePartialSpecializationMap[" << mapIndex << "]:" << std::endl;
3705  std::cout << " mTemplateDeclarations[" << decl1Index
3706  << "] => mTemplateForwardDeclarations[" << decl2Index << "]" << std::endl;
3707  break;
3708  }
3709  decl2Index++;
3710  }
3711  }
3712  break;
3713  }
3714  decl1Index++;
3715  }
3716  mapIndex++;
3717  }
3718  std::cout << "mTemplateInstantiations: " << mTemplateInstantiations.size() << std::endl;
3719  count = 0;
3720  for (const auto & decl : mTemplateInstantiations) {
3721  std::cout << "mTemplateInstantiations[" << count++ << "]:" << std::endl;
3722  printOut(decl);
3723  }
3724 }
3725 
3726 void TemplateSimplifier::simplifyTemplates(const std::time_t maxtime)
3727 {
3728  // convert "sizeof ..." to "sizeof..."
3729  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
3730  if (Token::simpleMatch(tok, "sizeof ...")) {
3731  tok->str("sizeof...");
3732  tok->deleteNext();
3733  }
3734  }
3735 
3736  // Remove "typename" unless used in template arguments or using type alias..
3737  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
3738  if (Token::Match(tok, "typename %name%") && !Token::Match(tok->tokAt(-3), "using %name% ="))
3739  tok->deleteThis();
3740 
3741  if (Token::simpleMatch(tok, "template <")) {
3742  tok = tok->next()->findClosingBracket();
3743  if (!tok)
3744  break;
3745  }
3746  }
3747 
3749  // Remove concepts/requires
3750  // TODO concepts are not removed yet
3751  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
3752  if (!Token::Match(tok, ")|>|>> requires %name%|("))
3753  continue;
3754  const Token* end = skipRequires(tok->next());
3755  if (end)
3756  Token::eraseTokens(tok, end);
3757  }
3758 
3759  // explicit(bool)
3760  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
3761  if (Token::simpleMatch(tok, "explicit (")) {
3762  const bool isFalse = Token::simpleMatch(tok->tokAt(2), "false )");
3763  Token::eraseTokens(tok, tok->linkAt(1)->next());
3764  if (isFalse)
3765  tok->deleteThis();
3766  }
3767  }
3768  }
3769 
3771 
3772  unsigned int passCount = 0;
3773  constexpr unsigned int passCountMax = 10;
3774  for (; passCount < passCountMax; ++passCount) {
3775  if (passCount) {
3776  // it may take more than one pass to simplify type aliases
3777  bool usingChanged = false;
3778  while (mTokenizer.simplifyUsing())
3779  usingChanged = true;
3780 
3781  if (!usingChanged && !mChanged)
3782  break;
3783 
3784  mChanged = usingChanged;
3785  mTemplateDeclarations.clear();
3790  mTemplateInstantiations.clear();
3791  mInstantiatedTemplates.clear();
3793  mTemplateNamePos.clear();
3794  }
3795 
3797 
3798  if (passCount == 0) {
3799  mDump.clear();
3800  for (const TokenAndName& t: mTemplateDeclarations)
3801  mDump += t.dump(mTokenizer.list.getFiles());
3803  mDump += t.dump(mTokenizer.list.getFiles());
3804  if (!mDump.empty())
3805  mDump = " <TemplateSimplifier>\n" + mDump + " </TemplateSimplifier>\n";
3806  }
3807 
3808  // Make sure there is something to simplify.
3809  if (mTemplateDeclarations.empty() && mTemplateForwardDeclarations.empty())
3810  return;
3811 
3813  std::string title("Template Simplifier pass " + std::to_string(passCount + 1));
3814  mTokenList.front()->printOut(title.c_str(), mTokenList.getFiles());
3815  }
3816 
3817  // Copy default argument values from forward declaration to declaration
3819 
3820  // Locate user defined specializations.
3822 
3823  // Locate user defined partial specializations.
3825 
3826  // Locate possible instantiations of templates..
3828 
3829  // Template arguments with default values
3831 
3833 
3835  printOut("### Template Simplifier pass " + std::to_string(passCount + 1) + " ###");
3836 
3837  // Keep track of the order the names appear so sort can preserve that order
3838  std::unordered_map<std::string, int> nameOrdinal;
3839  int ordinal = 0;
3840  for (const auto& decl : mTemplateDeclarations) {
3841  nameOrdinal.emplace(decl.fullName(), ordinal++);
3842  }
3843 
3844  auto score = [&](const Token* arg) {
3845  int i = 0;
3846  for (const Token* tok = arg; tok; tok = tok->next()) {
3847  if (tok->str() == ",")
3848  return i;
3849  if (tok->link() && Token::Match(tok, "(|{|["))
3850  tok = tok->link();
3851  else if (tok->str() == "<") {
3852  const Token* temp = tok->findClosingBracket();
3853  if (temp)
3854  tok = temp;
3855  } else if (Token::Match(tok, ")|;"))
3856  return i;
3857  else if (Token::simpleMatch(tok, "const"))
3858  i--;
3859  }
3860  return 0;
3861  };
3862  // Sort so const parameters come first in the list
3863  mTemplateDeclarations.sort([&](const TokenAndName& x, const TokenAndName& y) {
3864  if (x.fullName() != y.fullName())
3865  return nameOrdinal.at(x.fullName()) < nameOrdinal.at(y.fullName());
3866  if (x.isFunction() && y.isFunction()) {
3867  std::vector<const Token*> xargs;
3868  getFunctionArguments(x.nameToken(), xargs);
3869  std::vector<const Token*> yargs;
3870  getFunctionArguments(y.nameToken(), yargs);
3871  if (xargs.size() != yargs.size())
3872  return xargs.size() < yargs.size();
3874  return isConstMethod(x.nameToken());
3875  return std::lexicographical_compare(xargs.begin(),
3876  xargs.end(),
3877  yargs.begin(),
3878  yargs.end(),
3879  [&](const Token* xarg, const Token* yarg) {
3880  if (xarg != yarg)
3881  return score(xarg) < score(yarg);
3882  return false;
3883  });
3884  }
3885  return false;
3886  });
3887 
3888  std::set<std::string> expandedtemplates;
3889 
3890  for (std::list<TokenAndName>::const_reverse_iterator iter1 = mTemplateDeclarations.crbegin(); iter1 != mTemplateDeclarations.crend(); ++iter1) {
3891  if (iter1->isAlias() || iter1->isFriend())
3892  continue;
3893 
3894  // get specializations..
3895  std::list<const Token *> specializations;
3896  for (std::list<TokenAndName>::const_iterator iter2 = mTemplateDeclarations.cbegin(); iter2 != mTemplateDeclarations.cend(); ++iter2) {
3897  if (iter2->isAlias() || iter2->isFriend())
3898  continue;
3899 
3900  if (iter1->fullName() == iter2->fullName())
3901  specializations.push_back(iter2->nameToken());
3902  }
3903 
3904  const bool instantiated = simplifyTemplateInstantiations(
3905  *iter1,
3906  specializations,
3907  maxtime,
3908  expandedtemplates);
3909  if (instantiated) {
3910  mInstantiatedTemplates.push_back(*iter1);
3911  mTemplateNamePos.clear(); // positions might be invalid after instantiations
3912  }
3913  }
3914 
3915  for (std::list<TokenAndName>::const_iterator it = mInstantiatedTemplates.cbegin(); it != mInstantiatedTemplates.cend(); ++it) {
3916  auto decl = std::find_if(mTemplateDeclarations.begin(), mTemplateDeclarations.end(), [&it](const TokenAndName& decl) {
3917  return decl.token() == it->token();
3918  });
3919  if (decl != mTemplateDeclarations.end()) {
3920  if (it->isSpecialization()) {
3921  // delete the "template < >"
3922  Token * tok = it->token();
3923  tok->deleteNext(2);
3924  tok->deleteThis();
3925  } else {
3926  // remove forward declaration if found
3927  auto it1 = mTemplateForwardDeclarationsMap.find(it->token());
3928  if (it1 != mTemplateForwardDeclarationsMap.end())
3931  }
3932  mTemplateDeclarations.erase(decl);
3933  }
3934  }
3935 
3936  // remove out of line member functions
3937  while (!mMemberFunctionsToDelete.empty()) {
3938  const std::list<TokenAndName>::iterator it = std::find_if(mTemplateDeclarations.begin(),
3939  mTemplateDeclarations.end(),
3940  FindToken(mMemberFunctionsToDelete.cbegin()->token()));
3941  // multiple functions can share the same declaration so make sure it hasn't already been deleted
3942  if (it != mTemplateDeclarations.end()) {
3943  removeTemplate(it->token());
3944  mTemplateDeclarations.erase(it);
3945  } else {
3946  const std::list<TokenAndName>::iterator it1 = std::find_if(mTemplateForwardDeclarations.begin(),
3948  FindToken(mMemberFunctionsToDelete.cbegin()->token()));
3949  // multiple functions can share the same declaration so make sure it hasn't already been deleted
3950  if (it1 != mTemplateForwardDeclarations.end()) {
3951  removeTemplate(it1->token());
3952  mTemplateForwardDeclarations.erase(it1);
3953  }
3954  }
3956  }
3957 
3958  // remove explicit instantiations
3960  Token * start = j.token();
3961  if (start) {
3962  Token * end = start->next();
3963  while (end && end->str() != ";")
3964  end = end->next();
3965  if (start->previous())
3966  start = start->previous();
3967  if (end && end->next())
3968  end = end->next();
3969  eraseTokens(start, end);
3970  }
3971  }
3972  }
3973 
3974  if (passCount == passCountMax) {
3975  if (mSettings.debugwarnings) {
3976  const std::list<const Token*> locationList(1, mTokenList.front());
3977  const ErrorMessage errmsg(locationList, &mTokenizer.list,
3979  "debug",
3980  "TemplateSimplifier: pass count limit hit before simplifications were finished.",
3982  mErrorLogger.reportErr(errmsg);
3983  }
3984  }
3985 
3986  // Tweak uninstantiated C++17 fold expressions (... && args)
3988  bool simplify = false;
3989  for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
3990  if (tok->str() == "template")
3991  simplify = false;
3992  if (tok->str() == "{")
3993  simplify = true;
3994  if (!simplify || tok->str() != "(")
3995  continue;
3996  const Token *op = nullptr;
3997  const Token *args = nullptr;
3998  if (Token::Match(tok, "( ... %op%")) {
3999  op = tok->tokAt(2);
4000  args = tok->link()->previous();
4001  } else if (Token::Match(tok, "( %name% %op% ...")) {
4002  op = tok->tokAt(2);
4003  args = tok->link()->previous()->isName() ? nullptr : tok->next();
4004  } else if (Token::Match(tok->link()->tokAt(-3), "%op% ... )")) {
4005  op = tok->link()->tokAt(-2);
4006  args = tok->next();
4007  } else if (Token::Match(tok->link()->tokAt(-3), "... %op% %name% )")) {
4008  op = tok->link()->tokAt(-2);
4009  args = tok->next()->isName() ? nullptr : tok->link()->previous();
4010  } else {
4011  continue;
4012  }
4013 
4014  const std::string strop = op->str();
4015  const std::string strargs = (args && args->isName()) ? args->str() : "";
4016 
4017  Token::eraseTokens(tok, tok->link());
4018  tok->insertToken(")");
4019  if (!strargs.empty()) {
4020  tok->insertToken("...");
4021  tok->insertToken(strargs);
4022  }
4023  tok->insertToken("(");
4024  Token::createMutualLinks(tok->next(), tok->link()->previous());
4025  tok->insertToken("__cppcheck_fold_" + strop + "__");
4026  }
4027  }
4028 }
4029 
4031 {
4032  throw InternalError(tok, "syntax error", InternalError::SYNTAX);
4033 }
static bool match(const Token *tok, const std::string &rhs)
Definition: astutils.cpp:342
int numberOfArguments(const Token *ftok)
Determines the number of arguments - if token is a function call or macro.
Definition: astutils.cpp:3063
virtual void reportErr(const ErrorMessage &msg)=0
Information about found errors and warnings is directed here.
static std::string toxml(const std::string &str)
Convert XML-sensitive characters into XML entities.
virtual void reportProgress(const std::string &filename, const char stage[], const std::size_t value)
Report progress to client.
Definition: errorlogger.h:241
File name and line number.
Definition: errorlogger.h:55
Wrapper for error messages, provided by reportErr()
Definition: errorlogger.h:48
value class
Definition: mathlib.h:38
bool isInt() const
Definition: mathlib.h:50
bool isFloat() const
Definition: mathlib.h:53
static std::string divide(const std::string &first, const std::string &second)
Definition: mathlib.cpp:1103
long long bigint
Definition: mathlib.h:68
static std::string subtract(const std::string &first, const std::string &second)
Definition: mathlib.cpp:1078
static bigint toBigNumber(const std::string &str)
for conversion of numeric literals - for atoi-like conversions please use strToInt()
Definition: mathlib.cpp:368
static std::string calculate(const std::string &first, const std::string &second, char action)
Definition: mathlib.cpp:1153
static bool isFloat(const std::string &str)
Definition: mathlib.cpp:535
static std::string add(const std::string &first, const std::string &second)
Definition: mathlib.cpp:1056
static bool isNullValue(const std::string &str)
Does the string represent the numerical value of 0? In case leading or trailing white space is provid...
Definition: mathlib.cpp:1253
static bool isNegative(const std::string &str)
Definition: mathlib.cpp:636
static bool isInt(const std::string &str)
Definition: mathlib.cpp:1007
static std::string multiply(const std::string &first, const std::string &second)
Definition: mathlib.cpp:1126
static std::string getSuffix(const std::string &value)
Definition: mathlib.cpp:1012
bool debugtemplate
Is –debug-template given?
Definition: settings.h:180
bool debugnormal
Is –debug-normal given?
Definition: settings.h:174
int maxTemplateRecursion
max template recursion
Definition: settings.h:250
SimpleEnableGroup< Severity > severity
Definition: settings.h:358
bool debugwarnings
Is –debug-warnings given?
Definition: settings.h:183
Standards standards
Struct contains standards settings.
Definition: settings.h:366
bool isEnabled(T flag) const
Definition: settings.h:66
Token and its full scopename.
std::string dump(const std::vector< std::string > &fileNames) const
bool isSameFamily(const TemplateSimplifier::TokenAndName &decl) const
Is declaration the same family (class, function or variable).
const std::string & scope() const
bool isAliasToken(const Token *tok) const
Is token an alias token? template < ...
const std::string & name() const
TokenAndName(Token *token, std::string scope)
Constructor used for instantiations.
const std::string & fullName() const
const Token * aliasEndToken() const
Get alias end token.
const Token * aliasStartToken() const
Get alias start token.
static bool alreadyHasNamespace(const TokenAndName &templateDeclaration, const Token *tok)
Simplify templates : check if namespace already present.
void simplifyTemplateAliases()
simplify template aliases
static bool matchSpecialization(const Token *templateDeclarationNameToken, const Token *templateInstantiationNameToken, const std::list< const Token * > &specializations)
void getTemplateInstantiations()
Get template instantiations.
void simplifyTemplateArgs(Token *start, const Token *end, std::vector< newInstantiation > *newInst=nullptr)
Simplify template instantiation arguments.
std::list< TokenAndName > mTemplateDeclarations
void addNamespace(const TokenAndName &templateDeclaration, const Token *tok)
Simplify templates : add namespace to template name.
std::list< TokenAndName > mInstantiatedTemplates
std::vector< TokenAndName > mTypesUsedInTemplateInstantiation
static void deleteToken(Token *tok)
Delete specified token without invalidating pointer to following token.
static void getTemplateParametersInDeclaration(const Token *tok, std::vector< const Token * > &typeParametersInDeclaration)
TemplateParametersInDeclaration.
static bool getTemplateNamePositionTemplateClass(const Token *tok, int &namepos)
Get class template name position.
bool getTemplateDeclarations()
Get template declarations.
static bool instantiateMatch(const Token *instance, const std::size_t numberOfArguments, bool variadic, const char patternAfter[])
Match template declaration/instantiation.
bool simplifyTemplateInstantiations(const TokenAndName &templateDeclaration, const std::list< const Token * > &specializations, const std::time_t maxtime, std::set< std::string > &expandedtemplates)
Simplify templates : expand all instantiations for a template.
std::vector< TokenAndName > mExplicitInstantiationsToDelete
std::list< TokenAndName > mTemplateForwardDeclarations
static NORETURN void syntaxError(const Token *tok)
Syntax error.
void printOut(const TokenAndName &tokenAndName, const std::string &indent=" ") const
ErrorLogger & mErrorLogger
void simplifyTemplates(const std::time_t maxtime)
Simplify templates.
static Token * findTemplateDeclarationEnd(Token *tok)
Find last token of a template declaration.
static void eraseTokens(Token *begin, const Token *end)
void getSpecializations()
Try to locate a matching declaration for each user defined specialization.
void checkComplicatedSyntaxErrorsInTemplates()
std::unordered_map< const Token *, int > mTemplateNamePos
static bool removeTemplate(Token *tok, std::map< Token *, Token * > *forwardDecls=nullptr)
Remove a specific "template < ..." template class/function.
const Settings & mSettings
std::string getNewName(Token *tok2, std::list< std::string > &typeStringsUsedInTemplateInstantiation)
Get the new token name.
bool simplifyCalculations(Token *frontToken=nullptr, const Token *backToken=nullptr, bool isTemplate=true)
Simplify constant calculations such as "1+2" => "3".
void useDefaultArgumentValues()
simplify template instantiations (use default argument values)
void replaceTemplateUsage(const TokenAndName &instantiation, const std::list< std::string > &typeStringsUsedInTemplateInstantiation, const std::string &newName)
Replace all matching template usages 'Foo < int >' => 'Foo<int>'.
static unsigned int templateParameters(const Token *tok)
is the token pointing at a template parameters block < int , 3 > => yes
void expandTemplate(const TokenAndName &templateDeclaration, const TokenAndName &templateInstantiation, const std::vector< const Token * > &typeParametersInDeclaration, const std::string &newName, bool copy)
Expand a template.
static bool simplifyNumericCalculations(Token *tok, bool isTemplate=true)
Simplify constant calculations such as "1+2" => "3".
static bool getTemplateNamePositionTemplateVariable(const Token *tok, int &namepos)
Get variable template name position.
std::list< TokenAndName > mTemplateInstantiations
TemplateSimplifier(Tokenizer &tokenizer)
void addInstantiation(Token *token, const std::string &scope)
Add template instantiation.
std::map< Token *, Token * > mTemplateForwardDeclarationsMap
std::list< TokenAndName > mMemberFunctionsToDelete
static bool getTemplateNamePositionTemplateFunction(const Token *tok, int &namepos)
Get function template name position.
std::map< Token *, Token * > mTemplatePartialSpecializationMap
void fixForwardDeclaredDefaultArgumentValues()
Fix forward declared default argument values by copying them when they are not present in the declara...
int getTemplateNamePosition(const Token *tok)
Match template declaration/instantiation.
std::map< Token *, Token * > mTemplateSpecializationMap
void getPartialSpecializations()
Try to locate a matching declaration for each user defined partial specialization.
static Token * copyTokens(Token *dest, const Token *first, const Token *last, bool one_line=true)
Copy tokens.
Definition: tokenlist.cpp:264
std::string fileLine(const Token *tok) const
Get file:line for a given token.
const Token * back() const
get last token of list
Definition: tokenlist.h:128
bool validateToken(const Token *tok) const
Verify that the given token is an element of the tokenlist.
const std::vector< std::string > & getFiles() const
Get filenames (the sourcefile + the files it include).
Definition: tokenlist.h:141
void addtoken(const std::string &str, const nonneg int lineno, const nonneg int column, const nonneg int fileno, bool split=false)
Definition: tokenlist.cpp:145
const Token * front() const
get first token of list
Definition: tokenlist.h:119
The token list that the TokenList generates is a linked-list of this class.
Definition: token.h:150
void str(T &&s)
Definition: token.h:179
static bool Match(const Token *tok, const char pattern[], nonneg int varid=0)
Match given token (or list of tokens) to a pattern list.
Definition: token.cpp:688
void deleteThis()
Remove the contents for this token from the token list.
Definition: token.cpp:329
const std::string & originalName() const
Definition: token.h:1193
bool isName() const
Definition: token.h:361
void printOut(const char *title=nullptr) const
For debugging purposes, prints token and all tokens followed by it.
Definition: token.cpp:1257
static const Token * findmatch(const Token *const startTok, const char pattern[], const nonneg int varId=0)
Definition: token.cpp:1065
bool isUnsigned() const
Definition: token.h:424
bool isTemplateArg() const
Is current token a template argument?
Definition: token.h:748
void templateSimplifierPointer(TemplateSimplifier::TokenAndName *tokenAndName)
Definition: token.h:698
static void createMutualLinks(Token *begin, Token *end)
Links two elements against each other.
Definition: token.cpp:1248
nonneg int progressValue() const
Get progressValue (0 - 100)
Definition: token.h:1150
static nonneg int getStrLength(const Token *tok)
Definition: token.cpp:777
const std::string & strAt(int index) const
Definition: token.cpp:423
bool isNumber() const
Definition: token.h:371
bool isSigned() const
Definition: token.h:430
const Token * findClosingBracket() const
Returns the closing bracket of opening '<'.
Definition: token.cpp:917
bool isOp() const
Definition: token.h:380
void scopeInfo(std::shared_ptr< ScopeInfo2 > newScopeInfo)
Definition: token.cpp:2510
static const Token * findsimplematch(const Token *const startTok, const char(&pattern)[count])
Definition: token.h:763
const Token * tokAt(int index) const
Definition: token.cpp:393
Token * insertTokenBefore(const std::string &tokenStr, const std::string &originalNameStr=emptyString, const std::string &macroNameStr=emptyString)
Definition: token.h:857
void deleteNext(nonneg int count=1)
Unlink and delete the next 'count' tokens.
Definition: token.cpp:245
Token * insertToken(const std::string &tokenStr, const std::string &originalNameStr=emptyString, const std::string &macroNameStr=emptyString, bool prepend=false)
Insert new token after this token.
Definition: token.cpp:1105
Token::Type tokType() const
Definition: token.h:343
void scope(const Scope *s)
Associate this token with given scope.
Definition: token.h:1042
bool isLong() const
Definition: token.h:443
void link(Token *linkToToken)
Create link to given token.
Definition: token.h:1015
const Token * linkAt(int index) const
Definition: token.cpp:413
@ eNumber
Definition: token.h:162
@ eString
Definition: token.h:162
@ eChar
Definition: token.h:162
@ eBoolean
Definition: token.h:162
Token * previous()
Definition: token.h:862
bool isAssignmentOp() const
Definition: token.h:401
static void eraseTokens(Token *begin, const Token *end)
Delete tokens between begin and end.
Definition: token.cpp:1238
nonneg int linenr() const
Definition: token.h:816
bool isStandardType() const
Definition: token.h:449
const Token * nextArgumentBeforeCreateLinks2() const
Definition: token.cpp:879
Token * next()
Definition: token.h:830
const Token * findOpeningBracket() const
Definition: token.cpp:982
static bool simpleMatch(const Token *tok, const char(&pattern)[count])
Match given token (or list of tokens) to a pattern list.
Definition: token.h:252
nonneg int fileIndex() const
Definition: token.h:809
std::string getMacroName() const
Definition: token.h:755
void deletePrevious(nonneg int count=1)
Unlink and delete the previous 'count' tokens.
Definition: token.cpp:265
nonneg int column() const
Definition: token.h:823
The main purpose is to tokenize the source code.
Definition: tokenize.h:46
nonneg int sizeOfType(const Token *type) const
Calculates sizeof value for given type.
Definition: tokenize.cpp:192
void calculateScopes()
Definition: tokenize.cpp:4015
TokenList list
Token list: stores all tokens.
Definition: tokenize.h:590
static const Token * isFunctionHead(const Token *tok, const std::string &endsWith)
is token pointing at function head?
Definition: tokenize.cpp:97
bool simplifyUsing()
Definition: tokenize.cpp:2856
static const Token * startOfExecutableScope(const Token *tok)
Helper function to check for start of function execution scope.
Definition: tokenize.cpp:3926
#define REQUIRES(msg,...)
Definition: config.h:124
static const std::string emptyString
Definition: config.h:127
@ debug
Debug message.
@ information
Checking information.
static bool isFalse(const ValueFlow::Value &v)
Simple container to be thrown when internal error is detected.
Definition: errortypes.h:36
const Token * token
Definition: errortypes.h:42
enum Standards::cppstd_t cpp
newInstantiation(Token *t, std::string s)
static Token * skipTernaryOp(Token *tok, const Token *backToken)
static void getFunctionArguments(const Token *nameToken, std::vector< const Token * > &args)
static bool isConstMethod(const Token *nameToken)
static bool areAllParamsTypes(const std::vector< const Token * > &params)
static bool matchTemplateParameters(const Token *nameTok, const std::list< std::string > &strings)
static bool isLowerThanShift(const Token *lower)
static void invalidateForwardDecls(const Token *beg, const Token *end, std::map< Token *, Token * > *forwardDecls)
static bool validTokenStart(bool bounded, const Token *tok, const Token *frontToken, int offset)
static void invalidateInst(const Token *beg, const Token *end, std::vector< newInstantiation > *newInst)
static bool isLowerThanLogicalAnd(const Token *lower)
static bool isLowerEqualThanMulDiv(const Token *lower)
static Token * skipRequires(Token *tok)
static const Token * getFunctionToken(const Token *nameToken)
static bool validTokenEnd(bool bounded, const Token *tok, const Token *backToken, int offset)
static bool isLowerThanPlusMinus(const Token *lower)
static bool isLowerThanXor(const Token *lower)
static T * findTemplateDeclarationEndImpl(T *tok)
static bool isLowerThanAnd(const Token *lower)
static bool specMatch(const TemplateSimplifier::TokenAndName &spec, const TemplateSimplifier::TokenAndName &decl)
static bool isLowerThanOr(const Token *lower)
static bool isLowerThanMulDiv(const Token *lower)
static void indent(std::string &str, const nonneg int indent1, const nonneg int indent2)
Definition: token.cpp:1708
static const char * bool_to_string(bool b)
Definition: utils.h:345