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