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 //---------------------------------------------------------------------------
20 #include "tokenlist.h"
21
22 #include "astutils.h"
23 #include "errorlogger.h"
24 #include "library.h"
25 #include "path.h"
26 #include "settings.h"
27 #include "standards.h"
28 #include "token.h"
29
30 #include <exception>
31 #include <simplecpp.h>
32 #include <cctype>
33 #include <cstring>
34 #include <set>
35 #include <stack>
36
37 // How many compileExpression recursions are allowed?
38 // For practical code this could be endless. But in some special torture test
39 // there needs to be a limit.
40 static const int AST_MAX_DEPTH = 100;
41
42
TokenList(const Settings * settings)43 TokenList::TokenList(const Settings* settings) :
44 mTokensFrontBack(),
45 mSettings(settings),
46 mIsC(false),
47 mIsCpp(false)
48 {
49 mTokensFrontBack.list = this;
50 mKeywords.insert("auto");
51 mKeywords.insert("break");
52 mKeywords.insert("case");
53 //mKeywords.insert("char"); // type
54 mKeywords.insert("const");
55 mKeywords.insert("continue");
56 mKeywords.insert("default");
57 mKeywords.insert("do");
58 //mKeywords.insert("double"); // type
59 mKeywords.insert("else");
60 mKeywords.insert("enum");
61 mKeywords.insert("extern");
62 //mKeywords.insert("float"); // type
63 mKeywords.insert("for");
64 mKeywords.insert("goto");
65 mKeywords.insert("if");
66 mKeywords.insert("inline");
67 //mKeywords.insert("int"); // type
68 //mKeywords.insert("long"); // type
69 mKeywords.insert("register");
70 mKeywords.insert("restrict");
71 mKeywords.insert("return");
72 //mKeywords.insert("short"); // type
73 mKeywords.insert("signed");
74 mKeywords.insert("sizeof");
75 mKeywords.insert("static");
76 mKeywords.insert("struct");
77 mKeywords.insert("switch");
78 mKeywords.insert("typedef");
79 mKeywords.insert("union");
80 mKeywords.insert("unsigned");
81 mKeywords.insert("void");
82 mKeywords.insert("volatile");
83 mKeywords.insert("while");
84 }
85
~TokenList()86 TokenList::~TokenList()
87 {
88 deallocateTokens();
89 }
90
91 //---------------------------------------------------------------------------
92
getSourceFilePath() const93 const std::string& TokenList::getSourceFilePath() const
94 {
95 if (getFiles().empty()) {
96 return emptyString;
97 }
98 return getFiles()[0];
99 }
100
101 //---------------------------------------------------------------------------
102
103 // Deallocate lists..
deallocateTokens()104 void TokenList::deallocateTokens()
105 {
106 deleteTokens(mTokensFrontBack.front);
107 mTokensFrontBack.front = nullptr;
108 mTokensFrontBack.back = nullptr;
109 mFiles.clear();
110 }
111
determineCppC()112 void TokenList::determineCppC()
113 {
114 if (!mSettings) {
115 mIsC = Path::isC(getSourceFilePath());
116 mIsCpp = Path::isCPP(getSourceFilePath());
117 } else {
118 mIsC = mSettings->enforcedLang == Settings::C || (mSettings->enforcedLang == Settings::None && Path::isC(getSourceFilePath()));
119 mIsCpp = mSettings->enforcedLang == Settings::CPP || (mSettings->enforcedLang == Settings::None && Path::isCPP(getSourceFilePath()));
120 }
121
122 if (mIsCpp) {
123 //mKeywords.insert("bool"); // type
124 mKeywords.insert("catch");
125 mKeywords.insert("class");
126 mKeywords.insert("constexpr");
127 mKeywords.insert("const_cast");
128 mKeywords.insert("decltype");
129 mKeywords.insert("delete");
130 mKeywords.insert("dynamic_cast");
131 mKeywords.insert("explicit");
132 mKeywords.insert("export");
133 //mKeywords.insert("false"); // literal
134 mKeywords.insert("friend");
135 mKeywords.insert("mutable");
136 mKeywords.insert("namespace");
137 mKeywords.insert("new");
138 mKeywords.insert("operator");
139 mKeywords.insert("private");
140 mKeywords.insert("protected");
141 mKeywords.insert("public");
142 mKeywords.insert("reinterpret_cast");
143 mKeywords.insert("static_cast");
144 mKeywords.insert("template");
145 mKeywords.insert("this");
146 mKeywords.insert("throw");
147 //mKeywords.insert("true"); // literal
148 mKeywords.insert("try");
149 mKeywords.insert("typeid");
150 mKeywords.insert("typename");
151 mKeywords.insert("typeof");
152 mKeywords.insert("using");
153 mKeywords.insert("virtual");
154 //mKeywords.insert("wchar_t"); // type
155 }
156 }
157
appendFileIfNew(const std::string & fileName)158 int TokenList::appendFileIfNew(const std::string &fileName)
159 {
160 // Has this file been tokenized already?
161 for (int i = 0; i < mFiles.size(); ++i)
162 if (Path::sameFileName(mFiles[i], fileName))
163 return i;
164
165 // The "mFiles" vector remembers what files have been tokenized..
166 mFiles.push_back(fileName);
167
168 // Update mIsC and mIsCpp properties
169 if (mFiles.size() == 1) { // Update only useful if first file added to _files
170 determineCppC();
171 }
172 return mFiles.size() - 1;
173 }
174
clangSetOrigFiles()175 void TokenList::clangSetOrigFiles()
176 {
177 mOrigFiles = mFiles;
178 }
179
deleteTokens(Token * tok)180 void TokenList::deleteTokens(Token *tok)
181 {
182 while (tok) {
183 Token *next = tok->next();
184 delete tok;
185 tok = next;
186 }
187 }
188
189 //---------------------------------------------------------------------------
190 // add a token.
191 //---------------------------------------------------------------------------
192
addtoken(std::string str,const nonneg int lineno,const nonneg int column,const nonneg int fileno,bool split)193 void TokenList::addtoken(std::string str, const nonneg int lineno, const nonneg int column, const nonneg int fileno, bool split)
194 {
195 if (str.empty())
196 return;
197
198 // If token contains # characters, split it up
199 if (split) {
200 size_t begin = 0;
201 size_t end = 0;
202 while ((end = str.find("##", begin)) != std::string::npos) {
203 addtoken(str.substr(begin, end - begin), lineno, fileno, false);
204 addtoken("##", lineno, column, fileno, false);
205 begin = end+2;
206 }
207 if (begin != 0) {
208 addtoken(str.substr(begin), lineno, column, fileno, false);
209 return;
210 }
211 }
212
213 if (mTokensFrontBack.back) {
214 mTokensFrontBack.back->insertToken(str);
215 } else {
216 mTokensFrontBack.front = new Token(&mTokensFrontBack);
217 mTokensFrontBack.back = mTokensFrontBack.front;
218 mTokensFrontBack.back->str(str);
219 }
220
221 mTokensFrontBack.back->linenr(lineno);
222 mTokensFrontBack.back->column(column);
223 mTokensFrontBack.back->fileIndex(fileno);
224 }
225
addtoken(std::string str,const Token * locationTok)226 void TokenList::addtoken(std::string str, const Token *locationTok)
227 {
228 if (str.empty())
229 return;
230
231 if (mTokensFrontBack.back) {
232 mTokensFrontBack.back->insertToken(str);
233 } else {
234 mTokensFrontBack.front = new Token(&mTokensFrontBack);
235 mTokensFrontBack.back = mTokensFrontBack.front;
236 mTokensFrontBack.back->str(str);
237 }
238
239 mTokensFrontBack.back->linenr(locationTok->linenr());
240 mTokensFrontBack.back->column(locationTok->column());
241 mTokensFrontBack.back->fileIndex(locationTok->fileIndex());
242 }
243
addtoken(const Token * tok,const nonneg int lineno,const nonneg int column,const nonneg int fileno)244 void TokenList::addtoken(const Token * tok, const nonneg int lineno, const nonneg int column, const nonneg int fileno)
245 {
246 if (tok == nullptr)
247 return;
248
249 if (mTokensFrontBack.back) {
250 mTokensFrontBack.back->insertToken(tok->str(), tok->originalName());
251 } else {
252 mTokensFrontBack.front = new Token(&mTokensFrontBack);
253 mTokensFrontBack.back = mTokensFrontBack.front;
254 mTokensFrontBack.back->str(tok->str());
255 if (!tok->originalName().empty())
256 mTokensFrontBack.back->originalName(tok->originalName());
257 }
258
259 mTokensFrontBack.back->linenr(lineno);
260 mTokensFrontBack.back->column(column);
261 mTokensFrontBack.back->fileIndex(fileno);
262 mTokensFrontBack.back->flags(tok->flags());
263 }
264
addtoken(const Token * tok,const Token * locationTok)265 void TokenList::addtoken(const Token *tok, const Token *locationTok)
266 {
267 if (tok == nullptr || locationTok == nullptr)
268 return;
269
270 if (mTokensFrontBack.back) {
271 mTokensFrontBack.back->insertToken(tok->str(), tok->originalName());
272 } else {
273 mTokensFrontBack.front = new Token(&mTokensFrontBack);
274 mTokensFrontBack.back = mTokensFrontBack.front;
275 mTokensFrontBack.back->str(tok->str());
276 if (!tok->originalName().empty())
277 mTokensFrontBack.back->originalName(tok->originalName());
278 }
279
280 mTokensFrontBack.back->flags(tok->flags());
281 mTokensFrontBack.back->linenr(locationTok->linenr());
282 mTokensFrontBack.back->column(locationTok->column());
283 mTokensFrontBack.back->fileIndex(locationTok->fileIndex());
284 }
285
addtoken(const Token * tok)286 void TokenList::addtoken(const Token *tok)
287 {
288 if (tok == nullptr)
289 return;
290
291 if (mTokensFrontBack.back) {
292 mTokensFrontBack.back->insertToken(tok->str(), tok->originalName());
293 } else {
294 mTokensFrontBack.front = new Token(&mTokensFrontBack);
295 mTokensFrontBack.back = mTokensFrontBack.front;
296 mTokensFrontBack.back->str(tok->str());
297 if (!tok->originalName().empty())
298 mTokensFrontBack.back->originalName(tok->originalName());
299 }
300
301 mTokensFrontBack.back->flags(tok->flags());
302 mTokensFrontBack.back->linenr(tok->linenr());
303 mTokensFrontBack.back->column(tok->column());
304 mTokensFrontBack.back->fileIndex(tok->fileIndex());
305 }
306
307
308 //---------------------------------------------------------------------------
309 // copyTokens - Copy and insert tokens
310 //---------------------------------------------------------------------------
311
copyTokens(Token * dest,const Token * first,const Token * last,bool one_line)312 Token *TokenList::copyTokens(Token *dest, const Token *first, const Token *last, bool one_line)
313 {
314 std::stack<Token *> links;
315 Token *tok2 = dest;
316 int linenr = dest->linenr();
317 const int commonFileIndex = dest->fileIndex();
318 for (const Token *tok = first; tok != last->next(); tok = tok->next()) {
319 tok2->insertToken(tok->str());
320 tok2 = tok2->next();
321 tok2->fileIndex(commonFileIndex);
322 tok2->linenr(linenr);
323 tok2->tokType(tok->tokType());
324 tok2->flags(tok->flags());
325 tok2->varId(tok->varId());
326
327 // Check for links and fix them up
328 if (Token::Match(tok2, "(|[|{"))
329 links.push(tok2);
330 else if (Token::Match(tok2, ")|]|}")) {
331 if (links.empty())
332 return tok2;
333
334 Token * link = links.top();
335
336 tok2->link(link);
337 link->link(tok2);
338
339 links.pop();
340 }
341 if (!one_line && tok->next())
342 linenr += tok->next()->linenr() - tok->linenr();
343 }
344 return tok2;
345 }
346
347 //---------------------------------------------------------------------------
348 // InsertTokens - Copy and insert tokens
349 //---------------------------------------------------------------------------
350
insertTokens(Token * dest,const Token * src,nonneg int n)351 void TokenList::insertTokens(Token *dest, const Token *src, nonneg int n)
352 {
353 std::stack<Token *> link;
354
355 while (n > 0) {
356 dest->insertToken(src->str(), src->originalName());
357 dest = dest->next();
358
359 // Set links
360 if (Token::Match(dest, "(|[|{"))
361 link.push(dest);
362 else if (!link.empty() && Token::Match(dest, ")|]|}")) {
363 Token::createMutualLinks(dest, link.top());
364 link.pop();
365 }
366
367 dest->fileIndex(src->fileIndex());
368 dest->linenr(src->linenr());
369 dest->column(src->column());
370 dest->varId(src->varId());
371 dest->tokType(src->tokType());
372 dest->flags(src->flags());
373 src = src->next();
374 --n;
375 }
376 }
377
378 //---------------------------------------------------------------------------
379 // Tokenize - tokenizes a given file.
380 //---------------------------------------------------------------------------
381
createTokens(std::istream & code,const std::string & file0)382 bool TokenList::createTokens(std::istream &code, const std::string& file0)
383 {
384 appendFileIfNew(file0);
385
386 simplecpp::OutputList outputList;
387 simplecpp::TokenList tokens(code, mFiles, file0, &outputList);
388
389 createTokens(std::move(tokens));
390
391 return outputList.empty();
392 }
393
394 //---------------------------------------------------------------------------
395
createTokens(simplecpp::TokenList && tokenList)396 void TokenList::createTokens(simplecpp::TokenList&& tokenList)
397 {
398 if (tokenList.cfront())
399 mOrigFiles = mFiles = tokenList.cfront()->location.files;
400 else
401 mFiles.clear();
402
403 determineCppC();
404
405 for (const simplecpp::Token *tok = tokenList.cfront(); tok;) {
406
407 std::string str = tok->str();
408
409 // Float literal
410 if (str.size() > 1 && str[0] == '.' && std::isdigit(str[1]))
411 str = '0' + str;
412
413 if (mTokensFrontBack.back) {
414 mTokensFrontBack.back->insertToken(str);
415 } else {
416 mTokensFrontBack.front = new Token(&mTokensFrontBack);
417 mTokensFrontBack.back = mTokensFrontBack.front;
418 mTokensFrontBack.back->str(str);
419 }
420
421 mTokensFrontBack.back->fileIndex(tok->location.fileIndex);
422 mTokensFrontBack.back->linenr(tok->location.line);
423 mTokensFrontBack.back->column(tok->location.col);
424 mTokensFrontBack.back->isExpandedMacro(!tok->macro.empty());
425
426 tok = tok->next;
427 if (tok)
428 tokenList.deleteToken(tok->previous);
429 }
430
431 if (mSettings && mSettings->relativePaths) {
432 for (std::string & mFile : mFiles)
433 mFile = Path::getRelativePath(mFile, mSettings->basePaths);
434 }
435
436 Token::assignProgressValues(mTokensFrontBack.front);
437 }
438
439 //---------------------------------------------------------------------------
440
calculateChecksum() const441 unsigned long long TokenList::calculateChecksum() const
442 {
443 unsigned long long checksum = 0;
444 for (const Token* tok = front(); tok; tok = tok->next()) {
445 const unsigned int subchecksum1 = tok->flags() + tok->varId() + tok->tokType();
446 unsigned int subchecksum2 = 0;
447 for (char i : tok->str())
448 subchecksum2 += (unsigned int)i;
449 if (!tok->originalName().empty()) {
450 for (char i : tok->originalName())
451 subchecksum2 += (unsigned int) i;
452 }
453
454 checksum ^= ((static_cast<unsigned long long>(subchecksum1) << 32) | subchecksum2);
455
456 const bool bit1 = (checksum & 1) != 0;
457 checksum >>= 1;
458 if (bit1)
459 checksum |= (1ULL << 63);
460 }
461 return checksum;
462 }
463
464
465 //---------------------------------------------------------------------------
466
467 struct AST_state {
468 std::stack<Token*> op;
469 int depth;
470 int inArrayAssignment;
471 bool cpp;
472 int assign;
473 bool inCase; // true from case to :
474 bool stopAtColon; // help to properly parse ternary operators
475 const Token *functionCallEndPar;
AST_stateAST_state476 explicit AST_state(bool cpp) : depth(0), inArrayAssignment(0), cpp(cpp), assign(0), inCase(false),stopAtColon(false), functionCallEndPar(nullptr) {}
477 };
478
skipDecl(Token * tok)479 static Token * skipDecl(Token *tok)
480 {
481 if (!Token::Match(tok->previous(), "( %name%"))
482 return tok;
483 Token *vartok = tok;
484 while (Token::Match(vartok, "%name%|*|&|::|<")) {
485 if (vartok->str() == "<") {
486 if (vartok->link())
487 vartok = vartok->link();
488 else
489 return tok;
490 } else if (Token::Match(vartok, "%var% [:=(]")) {
491 return vartok;
492 } else if (Token::simpleMatch(vartok, "decltype (") && !Token::Match(tok->linkAt(1), ") [,)]")) {
493 return vartok->linkAt(1)->next();
494 }
495 vartok = vartok->next();
496 }
497 return tok;
498 }
499
iscast(const Token * tok,bool cpp)500 static bool iscast(const Token *tok, bool cpp)
501 {
502 if (!Token::Match(tok, "( ::| %name%"))
503 return false;
504
505 if (Token::simpleMatch(tok->link(), ") ( )"))
506 return false;
507
508 if (tok->previous() && tok->previous()->isName() && tok->previous()->str() != "return" &&
509 (!cpp || tok->previous()->str() != "throw"))
510 return false;
511
512 if (Token::simpleMatch(tok->previous(), ">") && tok->previous()->link())
513 return false;
514
515 if (Token::Match(tok, "( (| typeof (") && Token::Match(tok->link(), ") %num%"))
516 return true;
517
518 if (Token::Match(tok->link(), ") }|)|]|;"))
519 return false;
520
521 if (Token::Match(tok->link(), ") %cop%") && !Token::Match(tok->link(), ") [&*+-~!]"))
522 return false;
523
524 if (Token::Match(tok->previous(), "= ( %name% ) {") && tok->next()->varId() == 0)
525 return true;
526
527 bool type = false;
528 for (const Token *tok2 = tok->next(); tok2; tok2 = tok2->next()) {
529 if (tok2->varId() != 0)
530 return false;
531
532 while (tok2->link() && Token::Match(tok2, "(|[|<"))
533 tok2 = tok2->link()->next();
534
535 if (tok2->str() == ")") {
536 if (Token::simpleMatch(tok2, ") (") && Token::simpleMatch(tok2->linkAt(1), ") ."))
537 return true;
538 if (Token::simpleMatch(tok2, ") {") && !type) {
539 const Token *tok3 = tok2->linkAt(1);
540 while (tok3 != tok2 && Token::Match(tok3, "[{}]"))
541 tok3 = tok3->previous();
542 return tok3 != tok2 && tok3->str() != ";";
543 }
544 return type || tok2->strAt(-1) == "*" || Token::simpleMatch(tok2, ") ~") ||
545 (Token::Match(tok2, ") %any%") &&
546 !tok2->next()->isOp() &&
547 !Token::Match(tok2->next(), "[[]);,?:.]"));
548 }
549
550 if (Token::Match(tok2, "&|&& )"))
551 return true;
552
553 if (!Token::Match(tok2, "%name%|*|::"))
554 return false;
555
556 if (tok2->isStandardType() && (tok2->next()->str() != "(" || Token::Match(tok2->next(), "( * *| )")))
557 type = true;
558 }
559
560 return false;
561 }
562
563 // int(1), int*(2), ..
findCppTypeInitPar(Token * tok)564 static Token * findCppTypeInitPar(Token *tok)
565 {
566 if (!tok || !Token::Match(tok->previous(), "[,()] %name%"))
567 return nullptr;
568 bool istype = false;
569 while (Token::Match(tok, "%name%|::|<")) {
570 if (tok->str() == "<") {
571 tok = tok->link();
572 if (!tok)
573 return nullptr;
574 }
575 istype |= tok->isStandardType();
576 tok = tok->next();
577 }
578 if (!istype)
579 return nullptr;
580 if (!Token::Match(tok, "[*&]"))
581 return nullptr;
582 while (Token::Match(tok, "[*&]"))
583 tok = tok->next();
584 return (tok && tok->str() == "(") ? tok : nullptr;
585 }
586
587 // X{} X<Y>{} etc
588 static bool iscpp11init_impl(const Token * const tok);
iscpp11init(const Token * const tok)589 static bool iscpp11init(const Token * const tok)
590 {
591 if (tok->isCpp11init() == TokenImpl::Cpp11init::UNKNOWN)
592 tok->setCpp11init(iscpp11init_impl(tok));
593 return tok->isCpp11init() == TokenImpl::Cpp11init::CPP11INIT;
594 }
595
iscpp11init_impl(const Token * const tok)596 static bool iscpp11init_impl(const Token * const tok)
597 {
598 if (Token::simpleMatch(tok, "{") && Token::simpleMatch(tok->link()->previous(), "; }"))
599 return false;
600 const Token *nameToken = tok;
601 while (nameToken && nameToken->str() == "{") {
602 if (nameToken->isCpp11init() != TokenImpl::Cpp11init::UNKNOWN)
603 return nameToken->isCpp11init() == TokenImpl::Cpp11init::CPP11INIT;
604 nameToken = nameToken->previous();
605 if (nameToken && nameToken->str() == "," && Token::simpleMatch(nameToken->previous(), "} ,"))
606 nameToken = nameToken->linkAt(-1);
607 }
608 if (!nameToken)
609 return false;
610 if (nameToken->str() == ")" && Token::simpleMatch(nameToken->link()->previous(), "decltype ("))
611 return true;
612 if (nameToken->str() == ">" && nameToken->link())
613 nameToken = nameToken->link()->previous();
614
615 const Token *endtok = nullptr;
616 if (Token::Match(nameToken, "%name%|return {") && (!Token::simpleMatch(nameToken->tokAt(2), "[") || findLambdaEndScope(nameToken->tokAt(2))))
617 endtok = nameToken->linkAt(1);
618 else if (Token::Match(nameToken,"%name% <") && Token::simpleMatch(nameToken->linkAt(1),"> {"))
619 endtok = nameToken->linkAt(1)->linkAt(1);
620 else if (Token::Match(nameToken->previous(), "%name% ( {"))
621 endtok = nameToken->linkAt(1);
622 else
623 return false;
624 if (Token::Match(nameToken, "else|try|do|const|constexpr|override|volatile|&|&&"))
625 return false;
626 if (Token::simpleMatch(nameToken->previous(), "namespace"))
627 return false;
628 if (Token::Match(nameToken, "%any% {")) {
629 // If there is semicolon between {..} this is not a initlist
630 for (const Token *tok2 = nameToken->next(); tok2 != endtok; tok2 = tok2->next()) {
631 if (tok2->str() == ";")
632 return false;
633 const Token * lambdaEnd = findLambdaEndScope(tok2);
634 if (lambdaEnd)
635 tok2 = lambdaEnd;
636 }
637 }
638 // There is no initialisation for example here: 'class Fred {};'
639 if (!Token::simpleMatch(endtok, "} ;"))
640 return true;
641 const Token *prev = nameToken;
642 while (Token::Match(prev, "%name%|::|:|<|>")) {
643 if (Token::Match(prev, "class|struct"))
644 return false;
645
646 prev = prev->previous();
647 }
648 return true;
649 }
650
isQualifier(const Token * tok)651 static bool isQualifier(const Token* tok)
652 {
653 while (Token::Match(tok, "&|&&|*"))
654 tok = tok->next();
655 if (!Token::Match(tok, "{|;"))
656 return false;
657 return true;
658 }
659
compileUnaryOp(Token * & tok,AST_state & state,void (* f)(Token * & tok,AST_state & state))660 static void compileUnaryOp(Token *&tok, AST_state& state, void (*f)(Token *&tok, AST_state& state))
661 {
662 Token *unaryop = tok;
663 if (f) {
664 tok = tok->next();
665 state.depth++;
666 if (state.depth > AST_MAX_DEPTH)
667 throw InternalError(tok, "maximum AST depth exceeded", InternalError::AST);
668 if (tok)
669 f(tok, state);
670 state.depth--;
671 }
672
673 if (!state.op.empty()) {
674 unaryop->astOperand1(state.op.top());
675 state.op.pop();
676 }
677 state.op.push(unaryop);
678 }
679
compileBinOp(Token * & tok,AST_state & state,void (* f)(Token * & tok,AST_state & state))680 static void compileBinOp(Token *&tok, AST_state& state, void (*f)(Token *&tok, AST_state& state))
681 {
682 Token *binop = tok;
683 if (f) {
684 tok = tok->next();
685 if (Token::Match(binop, "::|. ~"))
686 tok = tok->next();
687 state.depth++;
688 if (tok && state.depth <= AST_MAX_DEPTH)
689 f(tok, state);
690 state.depth--;
691 }
692
693 // TODO: Should we check if op is empty.
694 // * Is it better to add assertion that it isn't?
695 // * Write debug warning if it's empty?
696 if (!state.op.empty()) {
697 binop->astOperand2(state.op.top());
698 state.op.pop();
699 }
700 if (!state.op.empty()) {
701 binop->astOperand1(state.op.top());
702 state.op.pop();
703 }
704 state.op.push(binop);
705 }
706
707 static void compileExpression(Token *&tok, AST_state& state);
708
compileTerm(Token * & tok,AST_state & state)709 static void compileTerm(Token *&tok, AST_state& state)
710 {
711 if (!tok)
712 return;
713 if (Token::Match(tok, "L %str%|%char%"))
714 tok = tok->next();
715 if (state.inArrayAssignment && Token::Match(tok->previous(), "[{,] . %name%")) { // Jump over . in C style struct initialization
716 state.op.push(tok);
717 tok->astOperand1(tok->next());
718 tok = tok->tokAt(2);
719 }
720 if (state.inArrayAssignment && Token::Match(tok->previous(), "[{,] [ %num%|%name% ]")) {
721 state.op.push(tok);
722 tok->astOperand1(tok->next());
723 tok = tok->tokAt(3);
724 }
725 if (tok->isLiteral()) {
726 state.op.push(tok);
727 do {
728 tok = tok->next();
729 } while (Token::Match(tok, "%name%|%str%"));
730 } else if (tok->isName()) {
731 if (Token::Match(tok, "return|case") || (state.cpp && tok->str() == "throw")) {
732 if (tok->str() == "case")
733 state.inCase = true;
734 const bool tokIsReturn = tok->str() == "return";
735 const bool stopAtColon = state.stopAtColon;
736 state.stopAtColon=true;
737 compileUnaryOp(tok, state, compileExpression);
738 state.stopAtColon=stopAtColon;
739 if (tokIsReturn)
740 state.op.pop();
741 if (state.inCase && Token::simpleMatch(tok, ": ;")) {
742 state.inCase = false;
743 tok = tok->next();
744 }
745 } else if (Token::Match(tok, "sizeof !!(")) {
746 compileUnaryOp(tok, state, compileExpression);
747 state.op.pop();
748 } else if (state.cpp && findCppTypeInitPar(tok)) { // int(0), int*(123), ..
749 tok = findCppTypeInitPar(tok);
750 state.op.push(tok);
751 tok = tok->tokAt(2);
752 } else if (state.cpp && iscpp11init(tok)) { // X{} X<Y>{} etc
753 state.op.push(tok);
754 tok = tok->next();
755 if (tok->str() == "<")
756 tok = tok->link()->next();
757
758 if (Token::Match(tok, "{ . %name% =|{")) {
759 const int inArrayAssignment = state.inArrayAssignment;
760 state.inArrayAssignment = 1;
761 compileBinOp(tok, state, compileExpression);
762 state.inArrayAssignment = inArrayAssignment;
763 } else if (Token::simpleMatch(tok, "{ }")) {
764 tok->astOperand1(state.op.top());
765 state.op.pop();
766 state.op.push(tok);
767 tok = tok->tokAt(2);
768 }
769 } else if (!state.cpp || !Token::Match(tok, "new|delete %name%|*|&|::|(|[")) {
770 tok = skipDecl(tok);
771 bool repeat = true;
772 while (repeat) {
773 repeat = false;
774 if (Token::Match(tok->next(), "%name%")) {
775 tok = tok->next();
776 repeat = true;
777 }
778 if (Token::simpleMatch(tok->next(), "<") && Token::Match(tok->linkAt(1), "> %name%")) {
779 tok = tok->next()->link()->next();
780 repeat = true;
781 }
782 }
783 state.op.push(tok);
784 if (Token::Match(tok, "%name% <") && tok->linkAt(1))
785 tok = tok->linkAt(1);
786 else if (Token::Match(tok, "%name% ..."))
787 tok = tok->next();
788 tok = tok->next();
789 if (Token::Match(tok, "%str%")) {
790 while (Token::Match(tok, "%name%|%str%"))
791 tok = tok->next();
792 }
793 if (Token::Match(tok, "%name% %assign%"))
794 tok = tok->next();
795 }
796 } else if (tok->str() == "{") {
797 const Token *prev = tok->previous();
798 if (Token::simpleMatch(prev, ") {") && iscast(prev->link(), state.cpp))
799 prev = prev->link()->previous();
800 if (Token::simpleMatch(tok->link(),"} [")) {
801 tok = tok->next();
802 } else if (state.cpp && iscpp11init(tok)) {
803 if (state.op.empty() || Token::Match(tok->previous(), "[{,]") || Token::Match(tok->tokAt(-2), "%name% (")) {
804 if (Token::Match(tok, "{ !!}")) {
805 Token *const end = tok->link();
806 compileUnaryOp(tok, state, compileExpression);
807 if (precedes(tok,end))
808 tok = end;
809 } else {
810 state.op.push(tok);
811 tok = tok->tokAt(2);
812 }
813 } else
814 compileBinOp(tok, state, compileExpression);
815 if (Token::Match(tok, "} ,|:"))
816 tok = tok->next();
817 } else if (state.cpp && Token::Match(tok->tokAt(-2), "%name% ( {") && !Token::findsimplematch(tok, ";", tok->link())) {
818 if (Token::simpleMatch(tok, "{ }"))
819 tok = tok->tokAt(2);
820 else {
821 Token *tok1 = tok;
822 state.inArrayAssignment++;
823 compileUnaryOp(tok, state, compileExpression);
824 state.inArrayAssignment--;
825 tok = tok1->link()->next();
826 }
827 } else if (!state.inArrayAssignment && !Token::simpleMatch(prev, "=")) {
828 state.op.push(tok);
829 tok = tok->link()->next();
830 } else {
831 if (tok->link() != tok->next()) {
832 state.inArrayAssignment++;
833 compileUnaryOp(tok, state, compileExpression);
834 if (Token::Match(tok, "} [,};]") && state.inArrayAssignment > 0) {
835 tok = tok->next();
836 state.inArrayAssignment--;
837 }
838 } else {
839 state.op.push(tok);
840 tok = tok->tokAt(2);
841 }
842 }
843 }
844 }
845
compileScope(Token * & tok,AST_state & state)846 static void compileScope(Token *&tok, AST_state& state)
847 {
848 compileTerm(tok, state);
849 while (tok) {
850 if (tok->str() == "::") {
851 const Token *lastOp = state.op.empty() ? nullptr : state.op.top();
852 if (Token::Match(lastOp, ":: %name%"))
853 lastOp = lastOp->next();
854 if (Token::Match(lastOp, "%name%") &&
855 (lastOp->next() == tok || (Token::Match(lastOp, "%name% <") && lastOp->linkAt(1) && tok == lastOp->linkAt(1)->next())))
856 compileBinOp(tok, state, compileTerm);
857 else
858 compileUnaryOp(tok, state, compileTerm);
859 } else break;
860 }
861 }
862
isPrefixUnary(const Token * tok,bool cpp)863 static bool isPrefixUnary(const Token* tok, bool cpp)
864 {
865 if (!tok->previous()
866 || ((Token::Match(tok->previous(), "(|[|{|%op%|;|}|?|:|,|.|return|::") || (cpp && tok->strAt(-1) == "throw"))
867 && (tok->previous()->tokType() != Token::eIncDecOp || tok->tokType() == Token::eIncDecOp)))
868 return true;
869
870 if (tok->str() == "*" && tok->previous()->tokType() == Token::eIncDecOp && isPrefixUnary(tok->previous(), cpp))
871 return true;
872
873 return tok->strAt(-1) == ")" && iscast(tok->linkAt(-1), cpp);
874 }
875
compilePrecedence2(Token * & tok,AST_state & state)876 static void compilePrecedence2(Token *&tok, AST_state& state)
877 {
878 compileScope(tok, state);
879 while (tok) {
880 if (tok->tokType() == Token::eIncDecOp && !isPrefixUnary(tok, state.cpp)) {
881 compileUnaryOp(tok, state, compileScope);
882 } else if (tok->str() == "...") {
883 state.op.push(tok);
884 tok = tok->next();
885 break;
886 } else if (tok->str() == "." && tok->strAt(1) != "*") {
887 if (tok->strAt(1) == ".") {
888 state.op.push(tok);
889 tok = tok->tokAt(3);
890 break;
891 }
892 compileBinOp(tok, state, compileScope);
893 } else if (tok->str() == "[") {
894 if (state.cpp && isPrefixUnary(tok, state.cpp) && Token::Match(tok->link(), "] (|{")) { // Lambda
895 // What we do here:
896 // - Nest the round bracket under the square bracket.
897 // - Nest what follows the lambda (if anything) with the lambda opening [
898 // - Compile the content of the lambda function as separate tree (this is done later)
899 // this must be consistent with isLambdaCaptureList
900 Token* const squareBracket = tok;
901 // Parse arguments in the capture list
902 if (tok->strAt(1) != "]") {
903 Token* tok2 = tok->next();
904 AST_state state2(state.cpp);
905 compileExpression(tok2, state2);
906 if (!state2.op.empty()) {
907 squareBracket->astOperand2(state2.op.top());
908 }
909 }
910
911 if (Token::simpleMatch(squareBracket->link(), "] (")) {
912 Token* const roundBracket = squareBracket->link()->next();
913 Token* curlyBracket = roundBracket->link()->next();
914 while (Token::Match(curlyBracket, "mutable|const|constexpr"))
915 curlyBracket = curlyBracket->next();
916 if (Token::simpleMatch(curlyBracket, "noexcept ("))
917 curlyBracket = curlyBracket->linkAt(1)->next();
918 if (curlyBracket && curlyBracket->originalName() == "->")
919 curlyBracket = findTypeEnd(curlyBracket->next());
920 if (curlyBracket && curlyBracket->str() == "{") {
921 squareBracket->astOperand1(roundBracket);
922 roundBracket->astOperand1(curlyBracket);
923 state.op.push(squareBracket);
924 tok = curlyBracket->link()->next();
925 continue;
926 }
927 } else {
928 Token* const curlyBracket = squareBracket->link()->next();
929 squareBracket->astOperand1(curlyBracket);
930 state.op.push(squareBracket);
931 tok = curlyBracket->link()->next();
932 continue;
933 }
934 }
935
936 const Token* const tok2 = tok;
937 if (tok->strAt(1) != "]")
938 compileBinOp(tok, state, compileExpression);
939 else
940 compileUnaryOp(tok, state, compileExpression);
941 tok = tok2->link()->next();
942 } else if (tok->str() == "(" && (!iscast(tok, state.cpp) || Token::Match(tok->previous(), "if|while|for|switch|catch"))) {
943 Token* tok2 = tok;
944 tok = tok->next();
945 const bool opPrevTopSquare = !state.op.empty() && state.op.top() && state.op.top()->str() == "[";
946 const std::size_t oldOpSize = state.op.size();
947 compileExpression(tok, state);
948 tok = tok2;
949 if ((oldOpSize > 0 && Token::simpleMatch(tok->previous(), "} ("))
950 || (tok->previous() && tok->previous()->isName() && !Token::Match(tok->previous(), "return|case") && (!state.cpp || !Token::Match(tok->previous(), "throw|delete")))
951 || (tok->strAt(-1) == "]" && (!state.cpp || !Token::Match(tok->linkAt(-1)->previous(), "new|delete")))
952 || (tok->strAt(-1) == ">" && tok->linkAt(-1))
953 || (tok->strAt(-1) == ")" && !iscast(tok->linkAt(-1), state.cpp)) // Don't treat brackets to clarify precedence as function calls
954 || (tok->strAt(-1) == "}" && opPrevTopSquare)) {
955 const bool operandInside = oldOpSize < state.op.size();
956 if (operandInside)
957 compileBinOp(tok, state, nullptr);
958 else
959 compileUnaryOp(tok, state, nullptr);
960 }
961 tok = tok->link()->next();
962 } else if (iscast(tok, state.cpp) && Token::simpleMatch(tok->link(), ") {") && Token::simpleMatch(tok->link()->linkAt(1), "} [")) {
963 Token *cast = tok;
964 tok = tok->link()->next();
965 Token *tok1 = tok;
966 compileUnaryOp(tok, state, compileExpression);
967 cast->astOperand1(tok1);
968 tok = tok1->link()->next();
969 } else if (state.cpp && tok->str() == "{" && iscpp11init(tok)) {
970 if (Token::simpleMatch(tok, "{ }"))
971 compileUnaryOp(tok, state, compileExpression);
972 else
973 compileBinOp(tok, state, compileExpression);
974 while (Token::simpleMatch(tok, "}"))
975 tok = tok->next();
976 } else break;
977 }
978 }
979
compilePrecedence3(Token * & tok,AST_state & state)980 static void compilePrecedence3(Token *&tok, AST_state& state)
981 {
982 compilePrecedence2(tok, state);
983 while (tok) {
984 if ((Token::Match(tok, "[+-!~*&]") || tok->tokType() == Token::eIncDecOp) &&
985 isPrefixUnary(tok, state.cpp)) {
986 if (Token::Match(tok, "* [*,)]")) {
987 Token* tok2 = tok->next();
988 while (tok2->next() && tok2->str() == "*")
989 tok2 = tok2->next();
990 if (Token::Match(tok2, "[>),]")) {
991 tok = tok2;
992 continue;
993 }
994 }
995 compileUnaryOp(tok, state, compilePrecedence3);
996 } else if (tok->str() == "(" && iscast(tok, state.cpp)) {
997 Token* castTok = tok;
998 castTok->isCast(true);
999 tok = tok->link()->next();
1000 const int inArrayAssignment = state.inArrayAssignment;
1001 if (tok && tok->str() == "{")
1002 state.inArrayAssignment = 1;
1003 compilePrecedence3(tok, state);
1004 state.inArrayAssignment = inArrayAssignment;
1005 compileUnaryOp(castTok, state, nullptr);
1006 } else if (state.cpp && Token::Match(tok, "new %name%|::|(")) {
1007 Token* newtok = tok;
1008 tok = tok->next();
1009 bool innertype = false;
1010 if (tok->str() == "(") {
1011 if (Token::Match(tok, "( &| %name%") && Token::Match(tok->link(), ") ( %type%") && Token::simpleMatch(tok->link()->linkAt(1), ") ("))
1012 tok = tok->link()->next();
1013 if (Token::Match(tok->link(), ") ::| %type%")) {
1014 if (Token::Match(tok, "( !!)")) {
1015 Token *innerTok = tok->next();
1016 AST_state innerState(true);
1017 compileExpression(innerTok, innerState);
1018 }
1019 tok = tok->link()->next();
1020 } else if (Token::Match(tok, "( %type%") && Token::Match(tok->link(), ") [();,[]")) {
1021 tok = tok->next();
1022 innertype = true;
1023 } else if (Token::Match(tok, "( &| %name%") && Token::simpleMatch(tok->link(), ") (")) {
1024 tok = tok->next();
1025 innertype = true;
1026 } else {
1027 /* bad code */
1028 continue;
1029 }
1030 }
1031
1032 Token* leftToken = tok;
1033 while (Token::Match(tok->next(), ":: %name%")) {
1034 Token* scopeToken = tok->next(); //The ::
1035 scopeToken->astOperand1(leftToken);
1036 scopeToken->astOperand2(scopeToken->next());
1037 leftToken = scopeToken;
1038 tok = scopeToken->next();
1039 }
1040
1041 state.op.push(tok);
1042 while (Token::Match(tok, "%name%|*|&|<|::")) {
1043 if (tok->link())
1044 tok = tok->link();
1045 tok = tok->next();
1046 }
1047 if (Token::Match(tok, "( const| %type% ) (")) {
1048 state.op.push(tok->next());
1049 tok = tok->link()->next();
1050 compileBinOp(tok, state, compilePrecedence2);
1051 } else if (tok && (tok->str() == "[" || tok->str() == "(" || tok->str() == "{"))
1052 compilePrecedence2(tok, state);
1053 else if (innertype && Token::simpleMatch(tok, ") [")) {
1054 tok = tok->next();
1055 compilePrecedence2(tok, state);
1056 }
1057 compileUnaryOp(newtok, state, nullptr);
1058 if (innertype && Token::simpleMatch(tok, ") ,"))
1059 tok = tok->next();
1060 } else if (state.cpp && Token::Match(tok, "delete %name%|*|&|::|(|[")) {
1061 Token* tok2 = tok;
1062 tok = tok->next();
1063 if (tok && tok->str() == "[")
1064 tok = tok->link()->next();
1065 compilePrecedence3(tok, state);
1066 compileUnaryOp(tok2, state, nullptr);
1067 }
1068 // TODO: Handle sizeof
1069 else break;
1070 }
1071 }
1072
compilePointerToElem(Token * & tok,AST_state & state)1073 static void compilePointerToElem(Token *&tok, AST_state& state)
1074 {
1075 compilePrecedence3(tok, state);
1076 while (tok) {
1077 if (Token::simpleMatch(tok, ". *")) {
1078 compileBinOp(tok, state, compilePrecedence3);
1079 } else break;
1080 }
1081 }
1082
compileMulDiv(Token * & tok,AST_state & state)1083 static void compileMulDiv(Token *&tok, AST_state& state)
1084 {
1085 compilePointerToElem(tok, state);
1086 while (tok) {
1087 if (Token::Match(tok, "[/%]") || (tok->str() == "*" && !tok->astOperand1() && !isQualifier(tok))) {
1088 if (Token::Match(tok, "* [*,)]")) {
1089 Token* tok2 = tok->next();
1090 while (tok2->next() && tok2->str() == "*")
1091 tok2 = tok2->next();
1092 if (Token::Match(tok2, "[>),]")) {
1093 tok = tok2;
1094 break;
1095 }
1096 }
1097 compileBinOp(tok, state, compilePointerToElem);
1098 } else break;
1099 }
1100 }
1101
compileAddSub(Token * & tok,AST_state & state)1102 static void compileAddSub(Token *&tok, AST_state& state)
1103 {
1104 compileMulDiv(tok, state);
1105 while (tok) {
1106 if (Token::Match(tok, "+|-") && !tok->astOperand1()) {
1107 compileBinOp(tok, state, compileMulDiv);
1108 } else break;
1109 }
1110 }
1111
compileShift(Token * & tok,AST_state & state)1112 static void compileShift(Token *&tok, AST_state& state)
1113 {
1114 compileAddSub(tok, state);
1115 while (tok) {
1116 if (Token::Match(tok, "<<|>>")) {
1117 compileBinOp(tok, state, compileAddSub);
1118 } else break;
1119 }
1120 }
1121
compileThreewayComp(Token * & tok,AST_state & state)1122 static void compileThreewayComp(Token *&tok, AST_state& state)
1123 {
1124 compileShift(tok, state);
1125 while (tok) {
1126 if (tok->str() == "<=>") {
1127 compileBinOp(tok, state, compileShift);
1128 } else break;
1129 }
1130 }
1131
compileRelComp(Token * & tok,AST_state & state)1132 static void compileRelComp(Token *&tok, AST_state& state)
1133 {
1134 compileThreewayComp(tok, state);
1135 while (tok) {
1136 if (Token::Match(tok, "<|<=|>=|>") && !tok->link()) {
1137 compileBinOp(tok, state, compileThreewayComp);
1138 } else break;
1139 }
1140 }
1141
compileEqComp(Token * & tok,AST_state & state)1142 static void compileEqComp(Token *&tok, AST_state& state)
1143 {
1144 compileRelComp(tok, state);
1145 while (tok) {
1146 if (Token::Match(tok, "==|!=")) {
1147 compileBinOp(tok, state, compileRelComp);
1148 } else break;
1149 }
1150 }
1151
compileAnd(Token * & tok,AST_state & state)1152 static void compileAnd(Token *&tok, AST_state& state)
1153 {
1154 compileEqComp(tok, state);
1155 while (tok) {
1156 if (tok->str() == "&" && !tok->astOperand1() && !isQualifier(tok)) {
1157 Token* tok2 = tok->next();
1158 if (!tok2)
1159 break;
1160 if (tok2->str() == "&")
1161 tok2 = tok2->next();
1162 if (state.cpp && Token::Match(tok2, ",|)")) {
1163 tok = tok2;
1164 break; // rValue reference
1165 }
1166 compileBinOp(tok, state, compileEqComp);
1167 } else break;
1168 }
1169 }
1170
compileXor(Token * & tok,AST_state & state)1171 static void compileXor(Token *&tok, AST_state& state)
1172 {
1173 compileAnd(tok, state);
1174 while (tok) {
1175 if (tok->str() == "^") {
1176 compileBinOp(tok, state, compileAnd);
1177 } else break;
1178 }
1179 }
1180
compileOr(Token * & tok,AST_state & state)1181 static void compileOr(Token *&tok, AST_state& state)
1182 {
1183 compileXor(tok, state);
1184 while (tok) {
1185 if (tok->str() == "|") {
1186 compileBinOp(tok, state, compileXor);
1187 } else break;
1188 }
1189 }
1190
compileLogicAnd(Token * & tok,AST_state & state)1191 static void compileLogicAnd(Token *&tok, AST_state& state)
1192 {
1193 compileOr(tok, state);
1194 while (tok) {
1195 if (tok->str() == "&&" && !isQualifier(tok)) {
1196 if (!tok->astOperand1()) {
1197 Token* tok2 = tok->next();
1198 if (!tok2)
1199 break;
1200 if (state.cpp && Token::Match(tok2, ",|)")) {
1201 tok = tok2;
1202 break; // rValue reference
1203 }
1204 }
1205 compileBinOp(tok, state, compileOr);
1206 } else break;
1207 }
1208 }
1209
compileLogicOr(Token * & tok,AST_state & state)1210 static void compileLogicOr(Token *&tok, AST_state& state)
1211 {
1212 compileLogicAnd(tok, state);
1213 while (tok) {
1214 if (tok->str() == "||") {
1215 compileBinOp(tok, state, compileLogicAnd);
1216 } else break;
1217 }
1218 }
1219
compileAssignTernary(Token * & tok,AST_state & state)1220 static void compileAssignTernary(Token *&tok, AST_state& state)
1221 {
1222 compileLogicOr(tok, state);
1223 while (tok) {
1224 if (tok->isAssignmentOp()) {
1225 state.assign++;
1226 const Token *tok1 = tok->next();
1227 compileBinOp(tok, state, compileAssignTernary);
1228 if (Token::simpleMatch(tok1, "{") && tok == tok1->link() && tok->next())
1229 tok = tok->next();
1230 if (state.assign > 0)
1231 state.assign--;
1232 } else if (tok->str() == "?") {
1233 // http://en.cppreference.com/w/cpp/language/operator_precedence says about ternary operator:
1234 // "The expression in the middle of the conditional operator (between ? and :) is parsed as if parenthesized: its precedence relative to ?: is ignored."
1235 // Hence, we rely on Tokenizer::prepareTernaryOpForAST() to add such parentheses where necessary.
1236 const bool stopAtColon = state.stopAtColon;
1237 state.stopAtColon = false;
1238 if (tok->strAt(1) == ":") {
1239 state.op.push(nullptr);
1240 }
1241 const int assign = state.assign;
1242 state.assign = 0;
1243 compileBinOp(tok, state, compileAssignTernary);
1244 state.assign = assign;
1245 state.stopAtColon = stopAtColon;
1246 } else if (tok->str() == ":") {
1247 if (state.depth == 1U && state.inCase) {
1248 state.inCase = false;
1249 tok = tok->next();
1250 break;
1251 }
1252 if (state.stopAtColon)
1253 break;
1254 if (state.assign > 0)
1255 break;
1256 compileBinOp(tok, state, compileAssignTernary);
1257 } else break;
1258 }
1259 }
1260
compileComma(Token * & tok,AST_state & state)1261 static void compileComma(Token *&tok, AST_state& state)
1262 {
1263 compileAssignTernary(tok, state);
1264 while (tok) {
1265 if (tok->str() == ",") {
1266 if (Token::simpleMatch(tok, ", }"))
1267 tok = tok->next();
1268 else
1269 compileBinOp(tok, state, compileAssignTernary);
1270 } else if (tok->str() == ";" && state.functionCallEndPar && tok->index() < state.functionCallEndPar->index()) {
1271 compileBinOp(tok, state, compileAssignTernary);
1272 } else break;
1273 }
1274 }
1275
compileExpression(Token * & tok,AST_state & state)1276 static void compileExpression(Token *&tok, AST_state& state)
1277 {
1278 if (state.depth > AST_MAX_DEPTH)
1279 throw InternalError(tok, "maximum AST depth exceeded", InternalError::AST); // ticket #5592
1280 if (tok)
1281 compileComma(tok, state);
1282 }
1283
isLambdaCaptureList(const Token * tok)1284 static bool isLambdaCaptureList(const Token * tok)
1285 {
1286 // a lambda expression '[x](y){}' is compiled as:
1287 // [
1288 // `-( <<-- optional
1289 // `-{
1290 // see compilePrecedence2
1291 if (tok->str() != "[")
1292 return false;
1293 if (!Token::Match(tok->link(), "] (|{"))
1294 return false;
1295 if (Token::simpleMatch(tok->astOperand1(), "{") && tok->astOperand1() == tok->link()->next())
1296 return true;
1297 if (!tok->astOperand1() || tok->astOperand1()->str() != "(")
1298 return false;
1299 const Token * params = tok->astOperand1();
1300 if (!params->astOperand1() || params->astOperand1()->str() != "{")
1301 return false;
1302 return true;
1303 }
1304
1305 static Token * createAstAtToken(Token *tok, bool cpp);
1306
1307 // Compile inner expressions inside inner ({..}) and lambda bodies
createAstAtTokenInner(Token * const tok1,const Token * endToken,bool cpp)1308 static void createAstAtTokenInner(Token * const tok1, const Token *endToken, bool cpp)
1309 {
1310 for (Token* tok = tok1; precedes(tok, endToken); tok = tok ? tok->next() : nullptr) {
1311 if (tok->str() == "{" && !iscpp11init(tok)) {
1312 const Token * const endToken2 = tok->link();
1313 bool hasAst = false;
1314 for (const Token *inner = tok->next(); inner != endToken2; inner = inner->next()) {
1315 if (inner->astOperand1()) {
1316 hasAst = true;
1317 break;
1318 }
1319 if (tok->isConstOp())
1320 break;
1321 if (inner->str() == "{")
1322 inner = inner->link();
1323 }
1324 if (!hasAst) {
1325 for (; tok && tok != endToken && tok != endToken2; tok = tok ? tok->next() : nullptr)
1326 tok = createAstAtToken(tok, cpp);
1327 }
1328 } else if (cpp && tok->str() == "[") {
1329 if (isLambdaCaptureList(tok)) {
1330 tok = tok->astOperand1();
1331 if (tok->str() == "(")
1332 tok = tok->astOperand1();
1333 const Token * const endToken2 = tok->link();
1334 tok = tok->next();
1335 for (; tok && tok != endToken && tok != endToken2; tok = tok ? tok->next() : nullptr)
1336 tok = createAstAtToken(tok, cpp);
1337 }
1338 }
1339 }
1340 }
1341
findAstTop(Token * tok1,Token * tok2)1342 static Token * findAstTop(Token *tok1, Token *tok2)
1343 {
1344 for (Token *tok = tok1; tok && (tok != tok2); tok = tok->next()) {
1345 if (tok->astParent() || tok->astOperand1() || tok->astOperand2()) {
1346 while (tok->astParent() && tok->astParent()->index() >= tok1->index() && tok->astParent()->index() <= tok2->index())
1347 tok = tok->astParent();
1348 return tok;
1349 }
1350 if (Token::simpleMatch(tok, "( {"))
1351 tok = tok->link();
1352 }
1353 for (Token *tok = tok1; tok && (tok != tok2); tok = tok->next()) {
1354 if (tok->isName() || tok->isNumber())
1355 return tok;
1356 if (Token::simpleMatch(tok, "( {"))
1357 tok = tok->link();
1358 }
1359 return nullptr;
1360 }
1361
createAstAtToken(Token * tok,bool cpp)1362 static Token * createAstAtToken(Token *tok, bool cpp)
1363 {
1364 if (Token::simpleMatch(tok, "for (")) {
1365 if (cpp && Token::Match(tok, "for ( const| auto &|&&| [")) {
1366 Token *decl = Token::findsimplematch(tok, "[");
1367 if (Token::simpleMatch(decl->link(), "] :")) {
1368 AST_state state1(cpp);
1369 while (decl->str() != "]") {
1370 if (Token::Match(decl, "%name% ,|]")) {
1371 state1.op.push(decl);
1372 } else if (decl->str() == ",") {
1373 if (!state1.op.empty()) {
1374 decl->astOperand1(state1.op.top());
1375 state1.op.pop();
1376 }
1377 if (!state1.op.empty()) {
1378 state1.op.top()->astOperand2(decl);
1379 state1.op.pop();
1380 }
1381 state1.op.push(decl);
1382 }
1383 decl = decl->next();
1384 }
1385 if (state1.op.size() > 1) {
1386 Token *lastName = state1.op.top();
1387 state1.op.pop();
1388 state1.op.top()->astOperand2(lastName);
1389 }
1390 decl = decl->next();
1391
1392 Token *colon = decl;
1393 compileExpression(decl, state1);
1394
1395 tok->next()->astOperand1(tok);
1396 tok->next()->astOperand2(colon);
1397
1398 return decl;
1399 }
1400 }
1401
1402 Token *tok2 = skipDecl(tok->tokAt(2));
1403 Token *init1 = nullptr;
1404 Token * const endPar = tok->next()->link();
1405 if (tok2 == tok->tokAt(2) && Token::Match(tok2, "%op%|(")) {
1406 init1 = tok2;
1407 AST_state state1(cpp);
1408 compileExpression(tok2, state1);
1409 if (Token::Match(init1, "( !!{")) {
1410 for (Token *tok3 = init1; tok3 != tok3->link(); tok3 = tok3->next()) {
1411 if (tok3->astParent()) {
1412 while (tok3->astParent())
1413 tok3 = tok3->astParent();
1414 init1 = tok3;
1415 break;
1416 }
1417 if (!Token::Match(tok3, "%op%|(|["))
1418 init1 = tok3;
1419 }
1420 }
1421 } else {
1422 while (tok2 && tok2 != endPar && tok2->str() != ";") {
1423 if (tok2->str() == "<" && tok2->link()) {
1424 tok2 = tok2->link();
1425 } else if (Token::Match(tok2, "%name% %op%|(|[|.|:|::") || Token::Match(tok2->previous(), "[(;{}] %cop%|(")) {
1426 init1 = tok2;
1427 AST_state state1(cpp);
1428 compileExpression(tok2, state1);
1429 if (Token::Match(tok2, ";|)"))
1430 break;
1431 init1 = nullptr;
1432 }
1433 if (!tok2) // #7109 invalid code
1434 return nullptr;
1435 tok2 = tok2->next();
1436 }
1437 }
1438 if (!tok2 || tok2->str() != ";") {
1439 if (tok2 == endPar && init1) {
1440 tok->next()->astOperand2(init1);
1441 tok->next()->astOperand1(tok);
1442 }
1443 return tok2;
1444 }
1445
1446 Token * const init = init1 ? init1 : tok2;
1447
1448 Token * const semicolon1 = tok2;
1449 tok2 = tok2->next();
1450 AST_state state2(cpp);
1451 compileExpression(tok2, state2);
1452
1453 Token * const semicolon2 = tok2;
1454 if (!semicolon2)
1455 return nullptr; // invalid code #7235
1456
1457 if (semicolon2->str() == ";") {
1458 tok2 = tok2->next();
1459 AST_state state3(cpp);
1460 if (Token::simpleMatch(tok2, "( {")) {
1461 state3.op.push(tok2->next());
1462 tok2 = tok2->link()->next();
1463 }
1464 compileExpression(tok2, state3);
1465
1466 tok2 = findAstTop(semicolon1->next(), semicolon2);
1467 if (tok2)
1468 semicolon2->astOperand1(tok2);
1469 tok2 = findAstTop(semicolon2->next(), endPar);
1470 if (tok2)
1471 semicolon2->astOperand2(tok2);
1472 else if (!state3.op.empty())
1473 semicolon2->astOperand2(state3.op.top());
1474 semicolon1->astOperand2(semicolon2);
1475 } else {
1476 if (!cpp || !Token::simpleMatch(state2.op.top(), ":"))
1477 throw InternalError(tok, "syntax error", InternalError::SYNTAX);
1478
1479 semicolon1->astOperand2(state2.op.top());
1480 }
1481
1482 if (init != semicolon1)
1483 semicolon1->astOperand1(init->astTop());
1484 tok->next()->astOperand1(tok);
1485 tok->next()->astOperand2(semicolon1);
1486
1487 createAstAtTokenInner(endPar->link(), endPar, cpp);
1488
1489 return endPar;
1490 }
1491
1492 if (Token::simpleMatch(tok, "( {"))
1493 return tok;
1494
1495 if (Token::Match(tok, "%type% <") && tok->linkAt(1) && !Token::Match(tok->linkAt(1), "> [({]"))
1496 return tok->linkAt(1);
1497
1498 if (cpp && Token::Match(tok, "%type% ::|<|%name%")) {
1499 Token *tok2 = tok;
1500 while (true) {
1501 if (Token::Match(tok2, "%name%|> :: %name%"))
1502 tok2 = tok2->tokAt(2);
1503 else if (Token::Match(tok2, "%name% <") && tok2->linkAt(1))
1504 tok2 = tok2->linkAt(1);
1505 else
1506 break;
1507 }
1508 if (Token::Match(tok2, "%name%|> %name% {") && tok2->next()->varId() && iscpp11init(tok2->tokAt(2))) {
1509 Token *const tok1 = tok = tok2->next();
1510 AST_state state(cpp);
1511 compileExpression(tok, state);
1512 createAstAtTokenInner(tok1->next(), tok1->linkAt(1), cpp);
1513 return tok;
1514 }
1515 }
1516
1517 if (Token::Match(tok, "%type% %name%|*|&|::") && tok->str() != "return") {
1518 int typecount = 0;
1519 Token *typetok = tok;
1520 while (Token::Match(typetok, "%type%|::|*|&")) {
1521 if (typetok->isName() && !Token::simpleMatch(typetok->previous(), "::"))
1522 typecount++;
1523 typetok = typetok->next();
1524 }
1525 if (Token::Match(typetok, "%var% =") && typetok->varId())
1526 tok = typetok;
1527
1528 // Do not create AST for function declaration
1529 if (typetok &&
1530 typecount >= 2 &&
1531 !Token::Match(tok, "return|throw") &&
1532 Token::Match(typetok->previous(), "%name% (") &&
1533 typetok->previous()->varId() == 0 &&
1534 !typetok->previous()->isKeyword() &&
1535 Token::Match(typetok->link(), ") const|;|{"))
1536 return typetok;
1537 }
1538
1539 if (Token::Match(tok, "return|case") ||
1540 (cpp && tok->str() == "throw") ||
1541 !tok->previous() ||
1542 Token::Match(tok, "%name% %op%|(|[|.|::|<|?|;") ||
1543 (cpp && Token::Match(tok, "%name% {") && iscpp11init(tok->next())) ||
1544 Token::Match(tok->previous(), "[;{}] %cop%|++|--|( !!{") ||
1545 Token::Match(tok->previous(), "[;{}] %num%|%str%|%char%")) {
1546 if (cpp && (Token::Match(tok->tokAt(-2), "[;{}] new|delete %name%") || Token::Match(tok->tokAt(-3), "[;{}] :: new|delete %name%")))
1547 tok = tok->previous();
1548
1549 Token * const tok1 = tok;
1550 AST_state state(cpp);
1551 if (Token::Match(tok, "%name% ("))
1552 state.functionCallEndPar = tok->linkAt(1);
1553 compileExpression(tok, state);
1554 const Token * const endToken = tok;
1555 if (endToken == tok1 || !endToken)
1556 return tok1;
1557
1558 createAstAtTokenInner(tok1->next(), endToken, cpp);
1559
1560 return endToken->previous();
1561 }
1562
1563 if (cpp && tok->str() == "{" && iscpp11init(tok)) {
1564 Token * const tok1 = tok;
1565 AST_state state(cpp);
1566 compileExpression(tok, state);
1567 const Token * const endToken = tok;
1568 if (endToken == tok1 || !endToken)
1569 return tok1;
1570
1571 createAstAtTokenInner(tok1->next(), endToken, cpp);
1572 return endToken->previous();
1573 }
1574
1575 return tok;
1576 }
1577
createAst() const1578 void TokenList::createAst() const
1579 {
1580 for (Token *tok = mTokensFrontBack.front; tok; tok = tok ? tok->next() : nullptr) {
1581 tok = createAstAtToken(tok, isCPP());
1582 }
1583 }
1584
1585 struct OnException {
1586 std::function<void()> f;
1587
~OnExceptionOnException1588 ~OnException() {
1589 #ifndef _MSC_VER
1590 if (std::uncaught_exception())
1591 f();
1592 #endif
1593 }
1594 };
1595
validateAst() const1596 void TokenList::validateAst() const
1597 {
1598 OnException oe{[&] {
1599 if (mSettings->debugnormal)
1600 mTokensFrontBack.front->printOut();
1601 }};
1602 // Check for some known issues in AST to avoid crash/hang later on
1603 std::set<const Token*> safeAstTokens; // list of "safe" AST tokens without endless recursion
1604 for (const Token *tok = mTokensFrontBack.front; tok; tok = tok->next()) {
1605 // Syntax error if binary operator only has 1 operand
1606 if ((tok->isAssignmentOp() || tok->isComparisonOp() || Token::Match(tok,"[|^/%]")) && tok->astOperand1() && !tok->astOperand2())
1607 throw InternalError(tok, "Syntax Error: AST broken, binary operator has only one operand.", InternalError::AST);
1608
1609 // Syntax error if we encounter "?" with operand2 that is not ":"
1610 if (tok->str() == "?") {
1611 if (!tok->astOperand1() || !tok->astOperand2())
1612 throw InternalError(tok, "AST broken, ternary operator missing operand(s)", InternalError::AST);
1613 else if (tok->astOperand2()->str() != ":")
1614 throw InternalError(tok, "Syntax Error: AST broken, ternary operator lacks ':'.", InternalError::AST);
1615 }
1616
1617 // Check for endless recursion
1618 const Token* parent = tok->astParent();
1619 if (parent) {
1620 std::set<const Token*> astTokens; // list of ancestors
1621 astTokens.insert(tok);
1622 do {
1623 if (safeAstTokens.find(parent) != safeAstTokens.end())
1624 break;
1625 if (astTokens.find(parent) != astTokens.end())
1626 throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::AST);
1627 astTokens.insert(parent);
1628 } while ((parent = parent->astParent()) != nullptr);
1629 safeAstTokens.insert(astTokens.begin(), astTokens.end());
1630 } else if (tok->str() == ";") {
1631 safeAstTokens.clear();
1632 } else {
1633 safeAstTokens.insert(tok);
1634 }
1635
1636 // Don't check templates
1637 if (tok->str() == "<" && tok->link()) {
1638 tok = tok->link();
1639 continue;
1640 }
1641
1642 // Check binary operators
1643 if (Token::Match(tok, "%or%|%oror%|%assign%|%comp%")) {
1644 // Skip lambda captures
1645 if (Token::Match(tok, "= ,|]"))
1646 continue;
1647 // Skip pure virtual functions
1648 if (Token::simpleMatch(tok->previous(), ") = 0"))
1649 continue;
1650 // Skip operator definitions
1651 if (Token::simpleMatch(tok->previous(), "operator"))
1652 continue;
1653 // Skip incomplete code
1654 if (!tok->astOperand1() && !tok->astOperand2() && !tok->astParent())
1655 continue;
1656 // Skip lambda assignment and/or initializer
1657 if (Token::Match(tok, "= {|^|["))
1658 continue;
1659 // FIXME: Workaround broken AST assignment in type aliases
1660 if (Token::Match(tok->previous(), "%name% = %name%"))
1661 continue;
1662 if (!tok->astOperand1() || !tok->astOperand2())
1663 throw InternalError(tok, "Syntax Error: AST broken, binary operator '" + tok->str() + "' doesn't have two operands.", InternalError::AST);
1664 }
1665
1666 // Check control blocks and asserts
1667 if (Token::Match(tok->previous(), "if|while|for|switch|assert|ASSERT (")) {
1668 if (!tok->astOperand1() || !tok->astOperand2())
1669 throw InternalError(tok,
1670 "Syntax Error: AST broken, '" + tok->previous()->str() +
1671 "' doesn't have two operands.",
1672 InternalError::AST);
1673 }
1674 }
1675 }
1676
getOrigFile(const Token * tok) const1677 std::string TokenList::getOrigFile(const Token *tok) const
1678 {
1679 return mOrigFiles.at(tok->fileIndex());
1680 }
1681
file(const Token * tok) const1682 const std::string& TokenList::file(const Token *tok) const
1683 {
1684 return mFiles.at(tok->fileIndex());
1685 }
1686
fileLine(const Token * tok) const1687 std::string TokenList::fileLine(const Token *tok) const
1688 {
1689 return ErrorMessage::FileLocation(tok, this).stringify();
1690 }
1691
validateToken(const Token * tok) const1692 bool TokenList::validateToken(const Token* tok) const
1693 {
1694 if (!tok)
1695 return true;
1696 for (const Token *t = mTokensFrontBack.front; t; t = t->next()) {
1697 if (tok==t)
1698 return true;
1699 }
1700 return false;
1701 }
1702
simplifyPlatformTypes()1703 void TokenList::simplifyPlatformTypes()
1704 {
1705 const bool isCPP11 = mSettings->standards.cpp >= Standards::CPP11;
1706
1707 enum { isLongLong, isLong, isInt } type;
1708
1709 /** @todo This assumes a flat address space. Not true for segmented address space (FAR *). */
1710
1711 if (mSettings->sizeof_size_t == mSettings->sizeof_long)
1712 type = isLong;
1713 else if (mSettings->sizeof_size_t == mSettings->sizeof_long_long)
1714 type = isLongLong;
1715 else if (mSettings->sizeof_size_t == mSettings->sizeof_int)
1716 type = isInt;
1717 else
1718 return;
1719
1720 for (Token *tok = front(); tok; tok = tok->next()) {
1721 // pre-check to reduce unneeded match calls
1722 if (!Token::Match(tok, "std| ::| %type%"))
1723 continue;
1724 bool isUnsigned;
1725 if (Token::Match(tok, "std| ::| size_t|uintptr_t|uintmax_t")) {
1726 if (isCPP11 && tok->strAt(-1) == "using" && tok->strAt(1) == "=")
1727 continue;
1728 isUnsigned = true;
1729 } else if (Token::Match(tok, "std| ::| ssize_t|ptrdiff_t|intptr_t|intmax_t")) {
1730 if (isCPP11 && tok->strAt(-1) == "using" && tok->strAt(1) == "=")
1731 continue;
1732 isUnsigned = false;
1733 } else
1734 continue;
1735
1736 bool inStd = false;
1737 if (tok->str() == "::") {
1738 tok->deleteThis();
1739 } else if (tok->str() == "std") {
1740 if (tok->next()->str() != "::")
1741 continue;
1742 inStd = true;
1743 tok->deleteNext();
1744 tok->deleteThis();
1745 }
1746
1747 if (inStd)
1748 tok->originalName("std::" + tok->str());
1749 else
1750 tok->originalName(tok->str());
1751 if (isUnsigned)
1752 tok->isUnsigned(true);
1753
1754 switch (type) {
1755 case isLongLong:
1756 tok->isLong(true);
1757 tok->str("long");
1758 break;
1759 case isLong:
1760 tok->str("long");
1761 break;
1762 case isInt:
1763 tok->str("int");
1764 break;
1765 }
1766 }
1767
1768 const std::string platform_type(mSettings->platformString());
1769
1770 for (Token *tok = front(); tok; tok = tok->next()) {
1771 if (tok->tokType() != Token::eType && tok->tokType() != Token::eName)
1772 continue;
1773
1774 const Library::PlatformType * const platformtype = mSettings->library.platform_type(tok->str(), platform_type);
1775
1776 if (platformtype) {
1777 // check for namespace
1778 if (tok->strAt(-1) == "::") {
1779 const Token * tok1 = tok->tokAt(-2);
1780 // skip when non-global namespace defined
1781 if (tok1 && tok1->tokType() == Token::eName)
1782 continue;
1783 tok = tok->previous();
1784 tok->deleteThis();
1785 }
1786 Token *typeToken;
1787 if (platformtype->mConstPtr) {
1788 tok->str("const");
1789 tok->insertToken("*");
1790 tok->insertToken(platformtype->mType);
1791 typeToken = tok;
1792 } else if (platformtype->mPointer) {
1793 tok->str(platformtype->mType);
1794 typeToken = tok;
1795 tok->insertToken("*");
1796 } else if (platformtype->mPtrPtr) {
1797 tok->str(platformtype->mType);
1798 typeToken = tok;
1799 tok->insertToken("*");
1800 tok->insertToken("*");
1801 } else {
1802 tok->originalName(tok->str());
1803 tok->str(platformtype->mType);
1804 typeToken = tok;
1805 }
1806 if (platformtype->mSigned)
1807 typeToken->isSigned(true);
1808 if (platformtype->mUnsigned)
1809 typeToken->isUnsigned(true);
1810 if (platformtype->mLong)
1811 typeToken->isLong(true);
1812 }
1813 }
1814 }
1815
simplifyStdType()1816 void TokenList::simplifyStdType()
1817 {
1818 for (Token *tok = front(); tok; tok = tok->next()) {
1819
1820 if (Token::Match(tok, "const|extern *|&|%name%") && (!tok->previous() || Token::Match(tok->previous(), "[;{}]"))) {
1821 if (Token::Match(tok->next(), "%name% !!;"))
1822 continue;
1823
1824 tok->insertToken("int");
1825 tok->next()->isImplicitInt(true);
1826 continue;
1827 }
1828
1829 if (Token::Match(tok, "char|short|int|long|unsigned|signed|double|float") || (mSettings->standards.c >= Standards::C99 && Token::Match(tok, "complex|_Complex"))) {
1830 bool isFloat= false;
1831 bool isSigned = false;
1832 bool isUnsigned = false;
1833 bool isComplex = false;
1834 int countLong = 0;
1835 Token* typeSpec = nullptr;
1836
1837 Token* tok2 = tok;
1838 for (; tok2->next(); tok2 = tok2->next()) {
1839 if (tok2->str() == "long") {
1840 countLong++;
1841 if (!isFloat)
1842 typeSpec = tok2;
1843 } else if (tok2->str() == "short") {
1844 typeSpec = tok2;
1845 } else if (tok2->str() == "unsigned")
1846 isUnsigned = true;
1847 else if (tok2->str() == "signed")
1848 isSigned = true;
1849 else if (Token::Match(tok2, "float|double")) {
1850 isFloat = true;
1851 typeSpec = tok2;
1852 } else if (mSettings->standards.c >= Standards::C99 && Token::Match(tok2, "complex|_Complex"))
1853 isComplex = !isFloat || tok2->str() == "_Complex" || Token::Match(tok2->next(), "*|&|%name%"); // Ensure that "complex" is not the variables name
1854 else if (Token::Match(tok2, "char|int")) {
1855 if (!typeSpec)
1856 typeSpec = tok2;
1857 } else
1858 break;
1859 }
1860
1861 if (!typeSpec) { // unsigned i; or similar declaration
1862 if (!isComplex) { // Ensure that "complex" is not the variables name
1863 tok->str("int");
1864 tok->isSigned(isSigned);
1865 tok->isUnsigned(isUnsigned);
1866 tok->isImplicitInt(true);
1867 }
1868 } else {
1869 typeSpec->isLong(typeSpec->isLong() || (isFloat && countLong == 1) || countLong > 1);
1870 typeSpec->isComplex(typeSpec->isComplex() || (isFloat && isComplex));
1871 typeSpec->isSigned(typeSpec->isSigned() || isSigned);
1872 typeSpec->isUnsigned(typeSpec->isUnsigned() || isUnsigned);
1873
1874 // Remove specifiers
1875 const Token* tok3 = tok->previous();
1876 tok2 = tok2->previous();
1877 while (tok3 != tok2) {
1878 if (tok2 != typeSpec &&
1879 (isComplex || !Token::Match(tok2, "complex|_Complex"))) // Ensure that "complex" is not the variables name
1880 tok2->deleteThis();
1881 tok2 = tok2->previous();
1882 }
1883 }
1884 }
1885 }
1886 }
1887
isKeyword(const std::string & str) const1888 bool TokenList::isKeyword(const std::string &str) const
1889 {
1890 return mKeywords.find(str) != mKeywords.end();
1891 }
1892