Cppcheck
tokenlist.cpp
Go to the documentation of this file.
1 /*
2  * Cppcheck - A tool for static C/C++ code analysis
3  * Copyright (C) 2007-2024 Cppcheck team.
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 //---------------------------------------------------------------------------
20 
21 #include "tokenlist.h"
22 
23 #include "astutils.h"
24 #include "errorlogger.h"
25 #include "errortypes.h"
26 #include "keywords.h"
27 #include "library.h"
28 #include "path.h"
29 #include "platform.h"
30 #include "settings.h"
31 #include "standards.h"
32 #include "token.h"
33 
34 #include <cctype>
35 #include <exception>
36 #include <functional>
37 #include <utility>
38 #include <set>
39 #include <stack>
40 #include <unordered_set>
41 
42 #include <simplecpp.h>
43 
44 //#define N_ASSERT_LANG
45 
46 #ifndef N_ASSERT_LANG
47 #include <cassert>
48 #define ASSERT_LANG(x) assert(x)
49 #else
50 #define ASSERT_LANG(x)
51 #endif
52 
53 // How many compileExpression recursions are allowed?
54 // For practical code this could be endless. But in some special torture test
55 // there needs to be a limit.
56 static constexpr int AST_MAX_DEPTH = 150;
57 
58 
59 TokenList::TokenList(const Settings* settings)
60  : mTokensFrontBack(*this)
61  , mSettings(settings)
62 {
63  if (mSettings && (mSettings->enforcedLang != Standards::Language::None)) {
64  mLang = mSettings->enforcedLang;
65  }
66 }
67 
68 TokenList::~TokenList()
69 {
70  deallocateTokens();
71 }
72 
73 //---------------------------------------------------------------------------
74 
75 const std::string& TokenList::getSourceFilePath() const
76 {
77  if (getFiles().empty()) {
78  return emptyString;
79  }
80  return getFiles()[0];
81 }
82 
83 //---------------------------------------------------------------------------
84 
85 // Deallocate lists..
86 void TokenList::deallocateTokens()
87 {
88  deleteTokens(mTokensFrontBack.front);
89  mTokensFrontBack.front = nullptr;
90  mTokensFrontBack.back = nullptr;
91  mFiles.clear();
92 }
93 
94 void TokenList::determineCppC()
95 {
96  // only try to determine if it wasn't enforced
97  if (mLang == Standards::Language::None) {
98  ASSERT_LANG(!getSourceFilePath().empty());
99  mLang = Path::identify(getSourceFilePath());
100  // TODO: cannot enable assert as this might occur for unknown extensions
101  //ASSERT_LANG(mLang != Standards::Language::None);
102  if (mLang == Standards::Language::None) {
103  // TODO: should default to C instead like we do for headers
104  // default to C++
105  mLang = Standards::Language::CPP;
106  }
107  }
108 }
109 
110 int TokenList::appendFileIfNew(std::string fileName)
111 {
112  // Has this file been tokenized already?
113  for (int i = 0; i < mFiles.size(); ++i)
114  if (Path::sameFileName(mFiles[i], fileName))
115  return i;
116 
117  // The "mFiles" vector remembers what files have been tokenized..
118  mFiles.push_back(std::move(fileName));
119 
120  // Update mIsC and mIsCpp properties
121  if (mFiles.size() == 1) { // Update only useful if first file added to _files
122  determineCppC();
123  }
124  return mFiles.size() - 1;
125 }
126 
127 void TokenList::clangSetOrigFiles()
128 {
129  mOrigFiles = mFiles;
130 }
131 
132 void TokenList::deleteTokens(Token *tok)
133 {
134  while (tok) {
135  Token *next = tok->next();
136  delete tok;
137  tok = next;
138  }
139 }
140 
141 //---------------------------------------------------------------------------
142 // add a token.
143 //---------------------------------------------------------------------------
144 
145 void TokenList::addtoken(const std::string& str, const nonneg int lineno, const nonneg int column, const nonneg int fileno, bool split)
146 {
147  if (str.empty())
148  return;
149 
150  // If token contains # characters, split it up
151  if (split) {
152  size_t begin = 0;
153  size_t end = 0;
154  while ((end = str.find("##", begin)) != std::string::npos) {
155  addtoken(str.substr(begin, end - begin), lineno, fileno, false);
156  addtoken("##", lineno, column, fileno, false);
157  begin = end+2;
158  }
159  if (begin != 0) {
160  addtoken(str.substr(begin), lineno, column, fileno, false);
161  return;
162  }
163  }
164 
165  if (mTokensFrontBack.back) {
166  mTokensFrontBack.back->insertToken(str);
167  } else {
168  mTokensFrontBack.front = new Token(mTokensFrontBack);
169  mTokensFrontBack.back = mTokensFrontBack.front;
170  mTokensFrontBack.back->str(str);
171  }
172 
173  mTokensFrontBack.back->linenr(lineno);
174  mTokensFrontBack.back->column(column);
175  mTokensFrontBack.back->fileIndex(fileno);
176 }
177 
178 void TokenList::addtoken(const std::string& str, const Token *locationTok)
179 {
180  if (str.empty())
181  return;
182 
183  if (mTokensFrontBack.back) {
184  mTokensFrontBack.back->insertToken(str);
185  } else {
186  mTokensFrontBack.front = new Token(mTokensFrontBack);
187  mTokensFrontBack.back = mTokensFrontBack.front;
188  mTokensFrontBack.back->str(str);
189  }
190 
191  mTokensFrontBack.back->linenr(locationTok->linenr());
192  mTokensFrontBack.back->column(locationTok->column());
193  mTokensFrontBack.back->fileIndex(locationTok->fileIndex());
194 }
195 
196 void TokenList::addtoken(const Token * tok, const nonneg int lineno, const nonneg int column, const nonneg int fileno)
197 {
198  if (tok == nullptr)
199  return;
200 
201  if (mTokensFrontBack.back) {
202  mTokensFrontBack.back->insertToken(tok->str(), tok->originalName());
203  } else {
204  mTokensFrontBack.front = new Token(mTokensFrontBack);
205  mTokensFrontBack.back = mTokensFrontBack.front;
206  mTokensFrontBack.back->str(tok->str());
207  if (!tok->originalName().empty())
208  mTokensFrontBack.back->originalName(tok->originalName());
209  }
210 
211  mTokensFrontBack.back->linenr(lineno);
212  mTokensFrontBack.back->column(column);
213  mTokensFrontBack.back->fileIndex(fileno);
214  mTokensFrontBack.back->flags(tok->flags());
215 }
216 
217 void TokenList::addtoken(const Token *tok, const Token *locationTok)
218 {
219  if (tok == nullptr || locationTok == nullptr)
220  return;
221 
222  if (mTokensFrontBack.back) {
223  mTokensFrontBack.back->insertToken(tok->str(), tok->originalName());
224  } else {
225  mTokensFrontBack.front = new Token(mTokensFrontBack);
226  mTokensFrontBack.back = mTokensFrontBack.front;
227  mTokensFrontBack.back->str(tok->str());
228  if (!tok->originalName().empty())
229  mTokensFrontBack.back->originalName(tok->originalName());
230  }
231 
232  mTokensFrontBack.back->flags(tok->flags());
233  mTokensFrontBack.back->linenr(locationTok->linenr());
234  mTokensFrontBack.back->column(locationTok->column());
235  mTokensFrontBack.back->fileIndex(locationTok->fileIndex());
236 }
237 
238 void TokenList::addtoken(const Token *tok)
239 {
240  if (tok == nullptr)
241  return;
242 
243  if (mTokensFrontBack.back) {
244  mTokensFrontBack.back->insertToken(tok->str(), tok->originalName(), tok->getMacroName());
245  } else {
246  mTokensFrontBack.front = new Token(mTokensFrontBack);
247  mTokensFrontBack.back = mTokensFrontBack.front;
248  mTokensFrontBack.back->str(tok->str());
249  mTokensFrontBack.back->originalName(tok->originalName());
250  mTokensFrontBack.back->setMacroName(tok->getMacroName());
251  }
252 
253  mTokensFrontBack.back->flags(tok->flags());
254  mTokensFrontBack.back->linenr(tok->linenr());
255  mTokensFrontBack.back->column(tok->column());
256  mTokensFrontBack.back->fileIndex(tok->fileIndex());
257 }
258 
259 
260 //---------------------------------------------------------------------------
261 // copyTokens - Copy and insert tokens
262 //---------------------------------------------------------------------------
263 
264 Token *TokenList::copyTokens(Token *dest, const Token *first, const Token *last, bool one_line)
265 {
266  std::stack<Token *> links;
267  Token *tok2 = dest;
268  int linenr = dest->linenr();
269  const int commonFileIndex = dest->fileIndex();
270  for (const Token *tok = first; tok != last->next(); tok = tok->next()) {
271  tok2->insertToken(tok->str());
272  tok2 = tok2->next();
273  tok2->fileIndex(commonFileIndex);
274  tok2->linenr(linenr);
275  tok2->tokType(tok->tokType());
276  tok2->flags(tok->flags());
277  tok2->varId(tok->varId());
278  tok2->setTokenDebug(tok->getTokenDebug());
279 
280  // Check for links and fix them up
281  if (Token::Match(tok2, "(|[|{"))
282  links.push(tok2);
283  else if (Token::Match(tok2, ")|]|}")) {
284  if (links.empty())
285  return tok2;
286 
287  Token * link = links.top();
288 
289  tok2->link(link);
290  link->link(tok2);
291 
292  links.pop();
293  }
294  if (!one_line && tok->next())
295  linenr += tok->next()->linenr() - tok->linenr();
296  }
297  return tok2;
298 }
299 
300 //---------------------------------------------------------------------------
301 // InsertTokens - Copy and insert tokens
302 //---------------------------------------------------------------------------
303 
304 void TokenList::insertTokens(Token *dest, const Token *src, nonneg int n)
305 {
306  std::stack<Token *> link;
307 
308  while (n > 0) {
309  dest->insertToken(src->str(), src->originalName());
310  dest = dest->next();
311 
312  // Set links
313  if (Token::Match(dest, "(|[|{"))
314  link.push(dest);
315  else if (!link.empty() && Token::Match(dest, ")|]|}")) {
316  Token::createMutualLinks(dest, link.top());
317  link.pop();
318  }
319 
320  dest->fileIndex(src->fileIndex());
321  dest->linenr(src->linenr());
322  dest->column(src->column());
323  dest->varId(src->varId());
324  dest->tokType(src->tokType());
325  dest->flags(src->flags());
326  dest->setMacroName(src->getMacroName());
327  src = src->next();
328  --n;
329  }
330 }
331 
332 //---------------------------------------------------------------------------
333 // Tokenize - tokenizes a given file.
334 //---------------------------------------------------------------------------
335 
336 bool TokenList::createTokens(std::istream &code, const std::string& file0)
337 {
338  ASSERT_LANG(!file0.empty());
339 
340  appendFileIfNew(file0);
341 
342  return createTokensInternal(code, file0);
343 }
344 
345 //---------------------------------------------------------------------------
346 
347 bool TokenList::createTokens(std::istream &code, Standards::Language lang)
348 {
349  ASSERT_LANG(lang != Standards::Language::None);
350  if (mLang == Standards::Language::None) {
351  mLang = lang;
352  } else {
353  ASSERT_LANG(lang == mLang);
354  }
355 
356  return createTokensInternal(code, "");
357 }
358 
359 //---------------------------------------------------------------------------
360 
361 bool TokenList::createTokensInternal(std::istream &code, const std::string& file0)
362 {
363  simplecpp::OutputList outputList;
364  simplecpp::TokenList tokens(code, mFiles, file0, &outputList);
365 
366  createTokens(std::move(tokens));
367 
368  return outputList.empty();
369 }
370 
371 //---------------------------------------------------------------------------
372 
373 // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
374 void TokenList::createTokens(simplecpp::TokenList&& tokenList)
375 {
376  // tokenList.cfront() might be NULL if the file contained nothing to tokenize so we need to check the files instead
377  if (!tokenList.getFiles().empty()) {
378  // this is a copy
379  // TODO: this points to mFiles when called from createTokens(std::istream &, const std::string&)
380  mOrigFiles = mFiles = tokenList.getFiles();
381  }
382  else
383  mFiles.clear();
384 
385  determineCppC();
386 
387  for (const simplecpp::Token *tok = tokenList.cfront(); tok;) {
388 
389  // TODO: move from TokenList
390  std::string str = tok->str();
391 
392  // Float literal
393  if (str.size() > 1 && str[0] == '.' && std::isdigit(str[1]))
394  str = '0' + str;
395 
396  if (mTokensFrontBack.back) {
397  mTokensFrontBack.back->insertToken(str);
398  } else {
399  mTokensFrontBack.front = new Token(mTokensFrontBack);
400  mTokensFrontBack.back = mTokensFrontBack.front;
401  mTokensFrontBack.back->str(str);
402  }
403 
404  mTokensFrontBack.back->fileIndex(tok->location.fileIndex);
405  mTokensFrontBack.back->linenr(tok->location.line);
406  mTokensFrontBack.back->column(tok->location.col);
407  mTokensFrontBack.back->setMacroName(tok->macro);
408 
409  tok = tok->next;
410  if (tok)
411  tokenList.deleteToken(tok->previous);
412  }
413 
414  if (mSettings && mSettings->relativePaths) {
415  for (std::string & mFile : mFiles)
416  mFile = Path::getRelativePath(mFile, mSettings->basePaths);
417  }
418 
419  Token::assignProgressValues(mTokensFrontBack.front);
420 }
421 
422 //---------------------------------------------------------------------------
423 
424 std::size_t TokenList::calculateHash() const
425 {
426  std::string hashData;
427  for (const Token* tok = front(); tok; tok = tok->next()) {
428  hashData += std::to_string(tok->flags());
429  hashData += std::to_string(tok->varId());
430  hashData += std::to_string(tok->tokType());
431  hashData += tok->str();
432  hashData += tok->originalName();
433  }
434  return (std::hash<std::string>{})(hashData);
435 }
436 
437 
438 //---------------------------------------------------------------------------
439 
440 namespace {
441  struct AST_state {
442  std::stack<Token*> op;
443  int depth{};
444  int inArrayAssignment{};
445  bool cpp;
446  int assign{};
447  bool inCase{}; // true from case to :
448  bool stopAtColon{}; // help to properly parse ternary operators
449  const Token* functionCallEndPar{};
450  explicit AST_state(bool cpp) : cpp(cpp) {}
451  };
452 }
453 
454 static Token* skipDecl(Token* tok, std::vector<Token*>* inner = nullptr)
455 {
456  auto isDecltypeFuncParam = [](const Token* tok) -> bool {
457  if (!Token::simpleMatch(tok, ")"))
458  return false;
459  tok = tok->next();
460  while (Token::Match(tok, "*|&|&&|const"))
461  tok = tok->next();
462  if (Token::simpleMatch(tok, "("))
463  tok = tok->link()->next();
464  return Token::Match(tok, "%name%| ,|)");
465  };
466 
467  if (!Token::Match(tok->previous(), "( %name%"))
468  return tok;
469  Token *vartok = tok;
470  while (Token::Match(vartok, "%name%|*|&|::|<")) {
471  if (vartok->str() == "<") {
472  if (vartok->link())
473  vartok = vartok->link();
474  else
475  return tok;
476  } else if (Token::Match(vartok, "%var% [:=(]")) {
477  return vartok;
478  } else if (Token::Match(vartok, "decltype|typeof (") && !isDecltypeFuncParam(tok->linkAt(1))) {
479  if (inner)
480  inner->push_back(vartok->tokAt(2));
481  return vartok->linkAt(1)->next();
482  }
483  vartok = vartok->next();
484  }
485  return tok;
486 }
487 
488 static bool iscast(const Token *tok, bool cpp)
489 {
490  if (!Token::Match(tok, "( ::| %name%"))
491  return false;
492 
493  if (Token::simpleMatch(tok->link(), ") ( )"))
494  return false;
495 
496  if (Token::Match(tok->link(), ") %assign%|,|..."))
497  return false;
498 
499  if (tok->previous() && tok->previous()->isName() && tok->previous()->str() != "return" &&
500  (!cpp || !Token::Match(tok->previous(), "delete|throw")))
501  return false;
502 
503  if (Token::simpleMatch(tok->previous(), ">") && tok->previous()->link())
504  return false;
505 
506  if (Token::Match(tok, "( (| typeof (") && Token::Match(tok->link(), ") %num%"))
507  return true;
508 
509  if (Token::Match(tok->link(), ") }|)|]|;"))
510  return false;
511 
512  if (Token::Match(tok->link(), ") %cop%") && !Token::Match(tok->link(), ") [&*+-~!]"))
513  return false;
514 
515  if (Token::Match(tok->previous(), "= ( %name% ) {") && tok->next()->varId() == 0)
516  return true;
517 
518  bool type = false;
519  for (const Token *tok2 = tok->next(); tok2; tok2 = tok2->next()) {
520  if (tok2->varId() != 0)
521  return false;
522  if (cpp && !type && tok2->str() == "new")
523  return false;
524 
525  while (tok2->link() && Token::Match(tok2, "(|[|<"))
526  tok2 = tok2->link()->next();
527 
528  if (tok2->str() == ")") {
529  if (Token::simpleMatch(tok2, ") (") && Token::simpleMatch(tok2->linkAt(1), ") ."))
530  return true;
531  if (Token::simpleMatch(tok2, ") {") && !type) {
532  const Token *tok3 = tok2->linkAt(1);
533  while (tok3 != tok2 && Token::Match(tok3, "[{}]"))
534  tok3 = tok3->previous();
535  return tok3->str() != ";";
536  }
537  const bool res = type || tok2->strAt(-1) == "*" || Token::simpleMatch(tok2, ") ~") ||
538  (Token::Match(tok2, ") %any%") &&
539  (!tok2->next()->isOp() || Token::Match(tok2->next(), "!|~|++|--")) &&
540  !Token::Match(tok2->next(), "[[]);,?:.]"));
541  return res;
542  }
543 
544  if (Token::Match(tok2, "&|&& )"))
545  return true;
546 
547  if (!Token::Match(tok2, "%name%|*|::"))
548  return false;
549 
550  if (tok2->isStandardType() && (tok2->next()->str() != "(" || Token::Match(tok2->next(), "( * *| )")))
551  type = true;
552  }
553 
554  return false;
555 }
556 
557 // int(1), int*(2), ..
558 static Token * findCppTypeInitPar(Token *tok)
559 {
560  if (!tok || !Token::Match(tok->previous(), "[,()] %name%"))
561  return nullptr;
562  bool istype = false;
563  while (Token::Match(tok, "%name%|::|<")) {
564  if (tok->str() == "<") {
565  tok = tok->link();
566  if (!tok)
567  return nullptr;
568  }
569  istype |= tok->isStandardType();
570  tok = tok->next();
571  }
572  if (!istype)
573  return nullptr;
574  if (!Token::Match(tok, "[*&]"))
575  return nullptr;
576  while (Token::Match(tok, "[*&]"))
577  tok = tok->next();
578  return (tok && tok->str() == "(") ? tok : nullptr;
579 }
580 
581 // X{} X<Y>{} etc
582 static bool iscpp11init_impl(const Token * const tok);
583 static bool iscpp11init(const Token * const tok)
584 {
585  if (tok->isCpp11init() == TokenImpl::Cpp11init::UNKNOWN)
586  tok->setCpp11init(iscpp11init_impl(tok));
587  return tok->isCpp11init() == TokenImpl::Cpp11init::CPP11INIT;
588 }
589 
590 static bool iscpp11init_impl(const Token * const tok)
591 {
592  if (Token::simpleMatch(tok, "{") && Token::simpleMatch(tok->link()->previous(), "; }"))
593  return false;
594  const Token *nameToken = tok;
595  while (nameToken && nameToken->str() == "{") {
596  if (nameToken->isCpp11init() != TokenImpl::Cpp11init::UNKNOWN)
597  return nameToken->isCpp11init() == TokenImpl::Cpp11init::CPP11INIT;
598  nameToken = nameToken->previous();
599  if (nameToken && nameToken->str() == "," && Token::simpleMatch(nameToken->previous(), "} ,"))
600  nameToken = nameToken->linkAt(-1);
601  }
602  if (!nameToken)
603  return false;
604  if (nameToken->str() == ")" && Token::simpleMatch(nameToken->link()->previous(), "decltype (") &&
605  !Token::simpleMatch(nameToken->link()->tokAt(-2), "."))
606  nameToken = nameToken->link()->previous();
607  if (Token::simpleMatch(nameToken, ", {"))
608  return true;
609  if (nameToken->str() == ">" && nameToken->link())
610  nameToken = nameToken->link()->previous();
611  if (Token::Match(nameToken, "]|*")) {
612  const Token* newTok = nameToken->link() ? nameToken->link()->previous() : nameToken->previous();
613  while (Token::Match(newTok, "%type%|::|*") && !newTok->isKeyword())
614  newTok = newTok->previous();
615  if (Token::simpleMatch(newTok, "new"))
616  return true;
617  }
618 
619  auto isCaseStmt = [](const Token* colonTok) {
620  if (!Token::Match(colonTok->tokAt(-1), "%name%|%num%|%char%|) :"))
621  return false;
622  if (const Token* castTok = colonTok->linkAt(-1)) {
623  if (Token::simpleMatch(castTok->astParent(), "case"))
624  return true;
625  }
626  const Token* caseTok = colonTok->tokAt(-2);
627  while (caseTok && Token::Match(caseTok->tokAt(-1), "::|%name%"))
628  caseTok = caseTok->tokAt(-1);
629  return Token::simpleMatch(caseTok, "case");
630  };
631 
632  const Token *endtok = nullptr;
633  if (Token::Match(nameToken, "%name%|return|: {") && !isCaseStmt(nameToken) &&
634  (!Token::simpleMatch(nameToken->tokAt(2), "[") || findLambdaEndScope(nameToken->tokAt(2))))
635  endtok = nameToken->linkAt(1);
636  else if (Token::Match(nameToken,"%name% <") && Token::simpleMatch(nameToken->linkAt(1),"> {"))
637  endtok = nameToken->linkAt(1)->linkAt(1);
638  else if (Token::Match(nameToken->previous(), "%name%|> ( {"))
639  endtok = nameToken->linkAt(1);
640  else if (Token::simpleMatch(nameToken, "decltype") && nameToken->linkAt(1))
641  endtok = nameToken->linkAt(1)->linkAt(1);
642  else
643  return false;
644  if (Token::Match(nameToken, "else|try|do|const|constexpr|override|volatile|&|&&"))
645  return false;
646  if (Token::simpleMatch(nameToken->previous(), ". void {") && nameToken->previous()->originalName() == "->")
647  return false; // trailing return type. The only function body that can contain no semicolon is a void function.
648  if (Token::simpleMatch(nameToken->previous(), "namespace") || Token::simpleMatch(nameToken, "namespace") /*anonymous namespace*/)
649  return false;
650  if (precedes(nameToken->next(), endtok) && !Token::Match(nameToken, "return|:")) {
651  // If there is semicolon between {..} this is not a initlist
652  for (const Token *tok2 = nameToken->next(); tok2 != endtok; tok2 = tok2->next()) {
653  if (tok2->str() == ";")
654  return false;
655  const Token * lambdaEnd = findLambdaEndScope(tok2);
656  if (lambdaEnd)
657  tok2 = lambdaEnd;
658  }
659  }
660  // There is no initialisation for example here: 'class Fred {};'
661  if (!Token::simpleMatch(endtok, "} ;"))
662  return true;
663  const Token *prev = nameToken;
664  while (Token::Match(prev, "%name%|::|:|<|>|(|)|,|%num%|%cop%|...")) {
665  if (Token::Match(prev, "class|struct|union|enum"))
666  return false;
667 
668  prev = prev->previous();
669  }
670  return true;
671 }
672 
673 static bool isQualifier(const Token* tok)
674 {
675  while (Token::Match(tok, "&|&&|*"))
676  tok = tok->next();
677  return Token::Match(tok, "{|;");
678 }
679 
680 static void compileUnaryOp(Token *&tok, AST_state& state, void (*f)(Token *&tok, AST_state& state))
681 {
682  Token *unaryop = tok;
683  if (f) {
684  tok = tok->next();
685  state.depth++;
686  if (state.depth > AST_MAX_DEPTH)
687  throw InternalError(tok, "maximum AST depth exceeded", InternalError::AST);
688  if (tok)
689  f(tok, state);
690  state.depth--;
691  }
692 
693  if (!state.op.empty() && (!precedes(state.op.top(), unaryop) || unaryop->isIncDecOp() || Token::Match(unaryop, "[({[]"))) { // nullary functions, empty lists/arrays
694  unaryop->astOperand1(state.op.top());
695  state.op.pop();
696  }
697  state.op.push(unaryop);
698 }
699 
700 static void compileBinOp(Token *&tok, AST_state& state, void (*f)(Token *&tok, AST_state& state))
701 {
702  Token *binop = tok;
703  if (f) {
704  tok = tok->next();
705  if (Token::Match(binop, "::|. ~"))
706  tok = tok->next();
707  state.depth++;
708  if (tok && state.depth <= AST_MAX_DEPTH)
709  f(tok, state);
710  if (state.depth > AST_MAX_DEPTH)
711  throw InternalError(tok, "maximum AST depth exceeded", InternalError::AST);
712  state.depth--;
713  }
714 
715  // TODO: Should we check if op is empty.
716  // * Is it better to add assertion that it isn't?
717  // * Write debug warning if it's empty?
718  if (!state.op.empty()) {
719  binop->astOperand2(state.op.top());
720  state.op.pop();
721  }
722  if (!state.op.empty()) {
723  binop->astOperand1(state.op.top());
724  state.op.pop();
725  }
726  state.op.push(binop);
727 }
728 
729 static void compileExpression(Token *&tok, AST_state& state);
730 
731 static void compileTerm(Token *&tok, AST_state& state)
732 {
733  if (!tok)
734  return;
735  if (Token::Match(tok, "L %str%|%char%"))
736  tok = tok->next();
737  if (state.inArrayAssignment && Token::Match(tok->previous(), "[{,] . %name%")) { // Jump over . in C style struct initialization
738  state.op.push(tok);
739  tok->astOperand1(tok->next());
740  tok = tok->tokAt(2);
741  }
742  if (state.inArrayAssignment && Token::Match(tok->previous(), "[{,] [ %num%|%name% ]")) {
743  state.op.push(tok);
744  tok->astOperand1(tok->next());
745  tok = tok->tokAt(3);
746  }
747  if (tok->isLiteral()) {
748  state.op.push(tok);
749  do {
750  tok = tok->next();
751  } while (Token::Match(tok, "%name%|%str%"));
752  } else if (tok->isName()) {
753  if (Token::Match(tok, "return|case") || (state.cpp && (tok->str() == "throw"))) {
754  if (tok->str() == "case")
755  state.inCase = true;
756  const bool tokIsReturn = tok->str() == "return";
757  const bool stopAtColon = state.stopAtColon;
758  state.stopAtColon=true;
759  compileUnaryOp(tok, state, compileExpression);
760  state.stopAtColon=stopAtColon;
761  if (tokIsReturn)
762  state.op.pop();
763  if (state.inCase && Token::simpleMatch(tok, ": ;")) {
764  state.inCase = false;
765  tok = tok->next();
766  }
767  } else if (Token::Match(tok, "sizeof !!(")) {
768  compileUnaryOp(tok, state, compileExpression);
769  state.op.pop();
770  } else if (state.cpp && findCppTypeInitPar(tok)) { // int(0), int*(123), ..
771  tok = findCppTypeInitPar(tok);
772  state.op.push(tok);
773  tok = tok->tokAt(2);
774  } else if (state.cpp && iscpp11init(tok)) { // X{} X<Y>{} etc
775  state.op.push(tok);
776  tok = tok->next();
777  if (tok->str() == "<")
778  tok = tok->link()->next();
779 
780  if (Token::Match(tok, "{ . %name% =|{")) {
781  const Token* end = tok->link();
782  const int inArrayAssignment = state.inArrayAssignment;
783  state.inArrayAssignment = 1;
784  compileBinOp(tok, state, compileExpression);
785  state.inArrayAssignment = inArrayAssignment;
786  if (tok == end)
787  tok = tok->next();
788  else
789  throw InternalError(tok, "Syntax error. Unexpected tokens in designated initializer.", InternalError::AST);
790  }
791  } else if (!state.cpp || !Token::Match(tok, "new|delete %name%|*|&|::|(|[")) {
792  std::vector<Token*> inner;
793  tok = skipDecl(tok, &inner);
794  for (Token* tok3 : inner) {
795  AST_state state1(state.cpp);
796  compileExpression(tok3, state1);
797  }
798  bool repeat = true;
799  while (repeat) {
800  repeat = false;
801  if (Token::Match(tok->next(), "%name%")) {
802  tok = tok->next();
803  repeat = true;
804  }
805  if (Token::simpleMatch(tok->next(), "<") && Token::Match(tok->linkAt(1), "> %name%")) {
806  tok = tok->next()->link()->next();
807  repeat = true;
808  }
809  }
810  state.op.push(tok);
811  if (Token::Match(tok, "%name% <") && tok->linkAt(1))
812  tok = tok->linkAt(1);
813  else if (Token::Match(tok, "%name% ...") || (state.op.size() == 1 && state.depth == 0 && Token::Match(tok->tokAt(-3), "!!& ) ( %name% ) =")))
814  tok = tok->next();
815  tok = tok->next();
816  if (Token::Match(tok, "%str%")) {
817  while (Token::Match(tok, "%name%|%str%"))
818  tok = tok->next();
819  }
820  if (Token::Match(tok, "%name% %assign%"))
821  tok = tok->next();
822  }
823  } else if (tok->str() == "{") {
824  const Token *prev = tok->previous();
825  if (Token::simpleMatch(prev, ") {") && iscast(prev->link(), state.cpp))
826  prev = prev->link()->previous();
827  if (Token::simpleMatch(tok->link(),"} [")) {
828  tok = tok->next();
829  } else if ((state.cpp && iscpp11init(tok)) || Token::simpleMatch(tok->previous(), "] {")) {
830  Token *const end = tok->link();
831  if (state.op.empty() || Token::Match(tok->previous(), "[{,]") || Token::Match(tok->tokAt(-2), "%name% (")) {
832  if (Token::Match(tok, "{ . %name% =|{")) {
833  const int inArrayAssignment = state.inArrayAssignment;
834  state.inArrayAssignment = 1;
835  compileBinOp(tok, state, compileExpression);
836  state.inArrayAssignment = inArrayAssignment;
837  } else if (Token::simpleMatch(tok, "{ }")) {
838  state.op.push(tok);
839  tok = tok->next();
840  } else {
841  compileUnaryOp(tok, state, compileExpression);
842  if (precedes(tok,end)) // typically for something like `MACRO(x, { if (c) { ... } })`, where end is the last curly, and tok is the open curly for the if
843  tok = end;
844  }
845  } else
846  compileBinOp(tok, state, compileExpression);
847  if (tok != end)
848  throw InternalError(tok, "Syntax error. Unexpected tokens in initializer.", InternalError::AST);
849  if (tok->next())
850  tok = tok->next();
851  } else if (state.cpp && Token::Match(tok->tokAt(-2), "%name% ( {") && !Token::findsimplematch(tok, ";", tok->link())) {
852  if (Token::simpleMatch(tok, "{ }"))
853  tok = tok->tokAt(2);
854  else {
855  Token *tok1 = tok;
856  state.inArrayAssignment++;
857  compileUnaryOp(tok, state, compileExpression);
858  state.inArrayAssignment--;
859  tok = tok1->link()->next();
860  }
861  } else if (!state.inArrayAssignment && !Token::simpleMatch(prev, "=")) {
862  state.op.push(tok);
863  tok = tok->link()->next();
864  } else {
865  if (tok->link() != tok->next()) {
866  state.inArrayAssignment++;
867  compileUnaryOp(tok, state, compileExpression);
868  if (Token::Match(tok, "} [,};]") && state.inArrayAssignment > 0) {
869  tok = tok->next();
870  state.inArrayAssignment--;
871  }
872  } else {
873  state.op.push(tok);
874  tok = tok->tokAt(2);
875  }
876  }
877  }
878 }
879 
880 static void compileScope(Token *&tok, AST_state& state)
881 {
882  compileTerm(tok, state);
883  while (tok) {
884  if (tok->str() == "::") {
885  const Token *lastOp = state.op.empty() ? nullptr : state.op.top();
886  if (Token::Match(lastOp, ":: %name%"))
887  lastOp = lastOp->next();
888  if (Token::Match(lastOp, "%name%") &&
889  (lastOp->next() == tok || (Token::Match(lastOp, "%name% <") && lastOp->linkAt(1) && tok == lastOp->linkAt(1)->next())))
890  compileBinOp(tok, state, compileTerm);
891  else
892  compileUnaryOp(tok, state, compileTerm);
893  } else break;
894  }
895 }
896 
897 static bool isPrefixUnary(const Token* tok, bool cpp)
898 {
899  if (cpp && Token::simpleMatch(tok->previous(), "* [") && Token::simpleMatch(tok->link(), "] {")) {
900  for (const Token* prev = tok->previous(); Token::Match(prev, "%name%|::|*|&|>|>>"); prev = prev->previous()) {
901  if (Token::Match(prev, ">|>>")) {
902  if (!prev->link())
903  break;
904  prev = prev->link();
905  }
906  if (prev->str() == "new")
907  return false;
908  }
909  }
910  if (!tok->previous()
911  || ((Token::Match(tok->previous(), "(|[|{|%op%|;|?|:|,|.|return|::") || (cpp && tok->strAt(-1) == "throw"))
912  && (tok->previous()->tokType() != Token::eIncDecOp || tok->tokType() == Token::eIncDecOp)))
913  return true;
914 
915  if (tok->previous()->str() == "}") {
916  const Token* parent = tok->linkAt(-1)->tokAt(-1);
917  return !Token::Match(parent, "%type%") || parent->isKeyword();
918  }
919 
920  if (tok->str() == "*" && tok->previous()->tokType() == Token::eIncDecOp && isPrefixUnary(tok->previous(), cpp))
921  return true;
922 
923  return tok->strAt(-1) == ")" && iscast(tok->linkAt(-1), cpp);
924 }
925 
926 static void compilePrecedence2(Token *&tok, AST_state& state)
927 {
928  auto doCompileScope = [&](const Token* tok) -> bool {
929  const bool isStartOfCpp11Init = state.cpp && tok && tok->str() == "{" && iscpp11init(tok);
930  if (isStartOfCpp11Init || Token::simpleMatch(tok, "(")) {
931  tok = tok->previous();
932  while (Token::simpleMatch(tok, "*"))
933  tok = tok->previous();
934  while (tok && Token::Match(tok->previous(), ":: %type%"))
935  tok = tok->tokAt(-2);
936  if (tok && !tok->isKeyword())
937  tok = tok->previous();
938  return !Token::Match(tok, "new ::| %type%");
939  }
940  return !findLambdaEndTokenWithoutAST(tok);
941  };
942 
943  bool isNew = true;
944  if (doCompileScope(tok)) {
945  compileScope(tok, state);
946  isNew = false;
947  }
948  while (tok) {
949  if (tok->tokType() == Token::eIncDecOp && !isPrefixUnary(tok, state.cpp)) {
950  compileUnaryOp(tok, state, compileScope);
951  } else if (tok->str() == "...") {
952  if (!Token::simpleMatch(tok->previous(), ")"))
953  state.op.push(tok);
954  tok = tok->next();
955  break;
956  } else if (tok->str() == "." && tok->strAt(1) != "*") {
957  if (tok->strAt(1) == ".") {
958  state.op.push(tok);
959  tok = tok->tokAt(3);
960  break;
961  }
962  compileBinOp(tok, state, compileScope);
963  } else if (tok->str() == "[") {
964  if (state.cpp && isPrefixUnary(tok, /*cpp*/ true) && Token::Match(tok->link(), "] (|{|<")) { // Lambda
965  // What we do here:
966  // - Nest the round bracket under the square bracket.
967  // - Nest what follows the lambda (if anything) with the lambda opening [
968  // - Compile the content of the lambda function as separate tree (this is done later)
969  // this must be consistent with isLambdaCaptureList
970  Token* const squareBracket = tok;
971  // Parse arguments in the capture list
972  if (tok->strAt(1) != "]") {
973  Token* tok2 = tok->next();
974  AST_state state2(state.cpp);
975  compileExpression(tok2, state2);
976  if (!state2.op.empty()) {
977  squareBracket->astOperand2(state2.op.top());
978  }
979  }
980 
981  const bool hasTemplateArg = Token::simpleMatch(squareBracket->link(), "] <") &&
982  Token::simpleMatch(squareBracket->link()->next()->link(), "> (");
983  if (Token::simpleMatch(squareBracket->link(), "] (") || hasTemplateArg) {
984  Token* const roundBracket = hasTemplateArg ? squareBracket->link()->next()->link()->next() : squareBracket->link()->next();
985  Token* curlyBracket = roundBracket->link()->next();
986  while (Token::Match(curlyBracket, "mutable|const|constexpr|consteval"))
987  curlyBracket = curlyBracket->next();
988  if (Token::simpleMatch(curlyBracket, "noexcept")) {
989  if (Token::simpleMatch(curlyBracket->next(), "("))
990  curlyBracket = curlyBracket->linkAt(1)->next();
991  else
992  curlyBracket = curlyBracket->next();
993  }
994  if (curlyBracket && curlyBracket->originalName() == "->")
995  curlyBracket = findTypeEnd(curlyBracket->next());
996  if (curlyBracket && curlyBracket->str() == "{") {
997  squareBracket->astOperand1(roundBracket);
998  roundBracket->astOperand1(curlyBracket);
999  state.op.push(squareBracket);
1000  tok = curlyBracket->link()->next();
1001  continue;
1002  }
1003  } else {
1004  Token* const curlyBracket = squareBracket->link()->next();
1005  squareBracket->astOperand1(curlyBracket);
1006  state.op.push(squareBracket);
1007  tok = curlyBracket->link() ? curlyBracket->link()->next() : nullptr;
1008  continue;
1009  }
1010  }
1011 
1012  Token* const tok2 = tok;
1013  if (tok->strAt(1) != "]") {
1014  compileBinOp(tok, state, compileExpression);
1015  if (Token::Match(tok2->previous(), "%type%|* [") && Token::Match(tok, "] { !!}")) {
1016  tok = tok->next();
1017  Token* const tok3 = tok;
1018  compileBinOp(tok, state, compileExpression);
1019  if (tok != tok3->link())
1020  throw InternalError(tok, "Syntax error in {..}", InternalError::AST);
1021  tok = tok->next();
1022  continue;
1023  }
1024  }
1025  else
1026  compileUnaryOp(tok, state, compileExpression);
1027  tok = tok2->link()->next();
1028  } else if (Token::simpleMatch(tok, "( {") && Token::simpleMatch(tok->linkAt(1)->previous(), "; } )") && !Token::Match(tok->previous(), "%name% (")) {
1029  state.op.push(tok->next());
1030  tok = tok->link()->next();
1031  continue;
1032  } else if (tok->str() == "(" && (!iscast(tok, state.cpp) || Token::Match(tok->previous(), "if|while|for|switch|catch"))) {
1033  Token* tok2 = tok;
1034  tok = tok->next();
1035  const bool opPrevTopSquare = !state.op.empty() && state.op.top() && state.op.top()->str() == "[";
1036  const std::size_t oldOpSize = state.op.size();
1037  compileExpression(tok, state);
1038  tok = tok2;
1039  if ((oldOpSize > 0 && (isNew || Token::simpleMatch(tok->previous(), "} (")))
1040  || (tok->previous() && tok->previous()->isName() && !Token::Match(tok->previous(), "return|case") && (!state.cpp || !Token::Match(tok->previous(), "throw|delete")))
1041  || (tok->strAt(-1) == "]" && (!state.cpp || !Token::Match(tok->linkAt(-1)->previous(), "new|delete")))
1042  || (tok->strAt(-1) == ">" && tok->linkAt(-1))
1043  || (tok->strAt(-1) == ")" && !iscast(tok->linkAt(-1), state.cpp)) // Don't treat brackets to clarify precedence as function calls
1044  || (tok->strAt(-1) == "}" && opPrevTopSquare)) {
1045  const bool operandInside = oldOpSize < state.op.size();
1046  if (operandInside)
1047  compileBinOp(tok, state, nullptr);
1048  else
1049  compileUnaryOp(tok, state, nullptr);
1050  }
1051  tok = tok->link()->next();
1052  if (Token::simpleMatch(tok, "::"))
1053  compileBinOp(tok, state, compileTerm);
1054  } else if (iscast(tok, state.cpp) && Token::simpleMatch(tok->link(), ") {") && Token::simpleMatch(tok->link()->linkAt(1), "} [")) {
1055  Token *cast = tok;
1056  tok = tok->link()->next();
1057  Token *tok1 = tok;
1058  compileUnaryOp(tok, state, compileExpression);
1059  cast->astOperand1(tok1);
1060  tok = tok1->link()->next();
1061  } else if (state.cpp && tok->str() == "{" && iscpp11init(tok)) {
1062  Token* end = tok->link();
1063  if (Token::simpleMatch(tok, "{ }"))
1064  {
1065  compileUnaryOp(tok, state, nullptr);
1066  tok = tok->next();
1067  }
1068  else
1069  {
1070  compileBinOp(tok, state, compileExpression);
1071  }
1072  if (tok == end)
1073  tok = end->next();
1074  else
1075  throw InternalError(tok, "Syntax error. Unexpected tokens in initializer.", InternalError::AST);
1076  } else break;
1077  }
1078 }
1079 
1080 static void compilePrecedence3(Token *&tok, AST_state& state)
1081 {
1082  compilePrecedence2(tok, state);
1083  while (tok) {
1084  if ((Token::Match(tok, "[+-!~*&]") || tok->tokType() == Token::eIncDecOp) &&
1085  isPrefixUnary(tok, state.cpp)) {
1086  if (Token::Match(tok, "* [*,)]")) {
1087  Token* tok2 = tok->next();
1088  while (tok2->next() && tok2->str() == "*")
1089  tok2 = tok2->next();
1090  if (Token::Match(tok2, "[>),]")) {
1091  tok = tok2;
1092  continue;
1093  }
1094  }
1095  compileUnaryOp(tok, state, compilePrecedence3);
1096  } else if (tok->str() == "(" && iscast(tok, state.cpp)) {
1097  Token* castTok = tok;
1098  castTok->isCast(true);
1099  tok = tok->link()->next();
1100  const int inArrayAssignment = state.inArrayAssignment;
1101  if (tok && tok->str() == "{")
1102  state.inArrayAssignment = 1;
1103  compilePrecedence3(tok, state);
1104  state.inArrayAssignment = inArrayAssignment;
1105  compileUnaryOp(castTok, state, nullptr);
1106  } else if (state.cpp && Token::Match(tok, "new %name%|::|(")) {
1107  Token* newtok = tok;
1108  tok = tok->next();
1109  bool innertype = false;
1110  if (tok->str() == "(") {
1111  if (Token::Match(tok, "( &| %name%") && Token::Match(tok->link(), ") ( %type%") && Token::simpleMatch(tok->link()->linkAt(1), ") ("))
1112  tok = tok->link()->next();
1113  if (Token::Match(tok->link(), ") ::| %type%")) {
1114  if (Token::Match(tok, "( !!)")) {
1115  Token *innerTok = tok->next();
1116  AST_state innerState(true);
1117  compileExpression(innerTok, innerState);
1118  }
1119  tok = tok->link()->next();
1120  } else if (Token::Match(tok, "( %type%") && Token::Match(tok->link(), ") [();,[]")) {
1121  tok = tok->next();
1122  innertype = true;
1123  } else if (Token::Match(tok, "( &| %name%") && Token::simpleMatch(tok->link(), ") (")) {
1124  tok = tok->next();
1125  innertype = true;
1126  } else {
1127  /* bad code */
1128  continue;
1129  }
1130  }
1131 
1132  Token* leftToken = tok;
1133  if (Token::simpleMatch(tok, "::")) {
1134  tok->astOperand1(tok->next());
1135  tok = tok->next();
1136  }
1137  else {
1138  while (Token::Match(tok->next(), ":: %name%")) {
1139  Token* scopeToken = tok->next(); //The ::
1140  scopeToken->astOperand1(leftToken);
1141  scopeToken->astOperand2(scopeToken->next());
1142  leftToken = scopeToken;
1143  tok = scopeToken->next();
1144  }
1145  }
1146 
1147  state.op.push(tok);
1148  while (Token::Match(tok, "%name%|*|&|<|::")) {
1149  if (tok->link())
1150  tok = tok->link();
1151  tok = tok->next();
1152  }
1153  if (Token::Match(tok, "( const| %type% ) (")) {
1154  state.op.push(tok->next());
1155  tok = tok->link()->next();
1156  compileBinOp(tok, state, compilePrecedence2);
1157  } else if (Token::Match(tok, "(|{|["))
1158  compilePrecedence2(tok, state);
1159  else if (innertype && Token::simpleMatch(tok, ") [")) {
1160  tok = tok->next();
1161  compilePrecedence2(tok, state);
1162  }
1163  compileUnaryOp(newtok, state, nullptr);
1164  if (Token::simpleMatch(newtok->previous(), ":: new")) {
1165  newtok->previous()->astOperand1(newtok);
1166  state.op.pop();
1167  }
1168  if (innertype && Token::simpleMatch(tok, ") ,"))
1169  tok = tok->next();
1170  } else if (state.cpp && Token::Match(tok, "delete %name%|*|&|::|(|[")) {
1171  Token* tok2 = tok;
1172  tok = tok->next();
1173  if (tok && tok->str() == "[")
1174  tok = tok->link()->next();
1175  compilePrecedence3(tok, state);
1176  compileUnaryOp(tok2, state, nullptr);
1177  if (Token::simpleMatch(tok2->previous(), ":: delete")) {
1178  tok2->previous()->astOperand1(tok2);
1179  state.op.pop();
1180  }
1181  }
1182  // TODO: Handle sizeof
1183  else break;
1184  }
1185 }
1186 
1187 static void compilePointerToElem(Token *&tok, AST_state& state)
1188 {
1189  compilePrecedence3(tok, state);
1190  while (tok) {
1191  if (Token::simpleMatch(tok, ". *")) {
1192  compileBinOp(tok, state, compilePrecedence3);
1193  } else break;
1194  }
1195 }
1196 
1197 static void compileMulDiv(Token *&tok, AST_state& state)
1198 {
1199  compilePointerToElem(tok, state);
1200  while (tok) {
1201  if (Token::Match(tok, "[/%]") || (tok->str() == "*" && !tok->astOperand1() && !isQualifier(tok))) {
1202  if (Token::Match(tok, "* [*,)]")) {
1203  Token* tok2 = tok->next();
1204  while (tok2->next() && tok2->str() == "*")
1205  tok2 = tok2->next();
1206  if (Token::Match(tok2, "[>),]")) {
1207  tok = tok2;
1208  break;
1209  }
1210  }
1211  compileBinOp(tok, state, compilePointerToElem);
1212  } else break;
1213  }
1214 }
1215 
1216 static void compileAddSub(Token *&tok, AST_state& state)
1217 {
1218  compileMulDiv(tok, state);
1219  while (tok) {
1220  if (Token::Match(tok, "+|-") && !tok->astOperand1()) {
1221  compileBinOp(tok, state, compileMulDiv);
1222  } else break;
1223  }
1224 }
1225 
1226 static void compileShift(Token *&tok, AST_state& state)
1227 {
1228  compileAddSub(tok, state);
1229  while (tok) {
1230  if (Token::Match(tok, "<<|>>")) {
1231  compileBinOp(tok, state, compileAddSub);
1232  } else break;
1233  }
1234 }
1235 
1236 static void compileThreewayComp(Token *&tok, AST_state& state)
1237 {
1238  compileShift(tok, state);
1239  while (tok) {
1240  if (tok->str() == "<=>") {
1241  compileBinOp(tok, state, compileShift);
1242  } else break;
1243  }
1244 }
1245 
1246 static void compileRelComp(Token *&tok, AST_state& state)
1247 {
1248  compileThreewayComp(tok, state);
1249  while (tok) {
1250  if (Token::Match(tok, "<|<=|>=|>") && !tok->link()) {
1251  compileBinOp(tok, state, compileThreewayComp);
1252  } else break;
1253  }
1254 }
1255 
1256 static void compileEqComp(Token *&tok, AST_state& state)
1257 {
1258  compileRelComp(tok, state);
1259  while (tok) {
1260  if (Token::Match(tok, "==|!=")) {
1261  compileBinOp(tok, state, compileRelComp);
1262  } else break;
1263  }
1264 }
1265 
1266 static void compileAnd(Token *&tok, AST_state& state)
1267 {
1268  compileEqComp(tok, state);
1269  while (tok) {
1270  if (tok->str() == "&" && !tok->astOperand1() && !isQualifier(tok)) {
1271  Token* tok2 = tok->next();
1272  if (!tok2)
1273  break;
1274  if (tok2->str() == "&")
1275  tok2 = tok2->next();
1276  if (state.cpp && Token::Match(tok2, ",|)")) {
1277  tok = tok2;
1278  break; // rValue reference
1279  }
1280  compileBinOp(tok, state, compileEqComp);
1281  } else break;
1282  }
1283 }
1284 
1285 static void compileXor(Token *&tok, AST_state& state)
1286 {
1287  compileAnd(tok, state);
1288  while (tok) {
1289  if (tok->str() == "^") {
1290  compileBinOp(tok, state, compileAnd);
1291  } else break;
1292  }
1293 }
1294 
1295 static void compileOr(Token *&tok, AST_state& state)
1296 {
1297  compileXor(tok, state);
1298  while (tok) {
1299  if (tok->str() == "|") {
1300  compileBinOp(tok, state, compileXor);
1301  } else break;
1302  }
1303 }
1304 
1305 static void compileLogicAnd(Token *&tok, AST_state& state)
1306 {
1307  compileOr(tok, state);
1308  while (tok) {
1309  if (tok->str() == "&&" && !isQualifier(tok)) {
1310  if (!tok->astOperand1()) {
1311  Token* tok2 = tok->next();
1312  if (!tok2)
1313  break;
1314  if (state.cpp && Token::Match(tok2, ",|)")) {
1315  tok = tok2;
1316  break; // rValue reference
1317  }
1318  }
1319  compileBinOp(tok, state, compileOr);
1320  } else break;
1321  }
1322 }
1323 
1324 static void compileLogicOr(Token *&tok, AST_state& state)
1325 {
1326  compileLogicAnd(tok, state);
1327  while (tok) {
1328  if (tok->str() == "||") {
1329  compileBinOp(tok, state, compileLogicAnd);
1330  } else break;
1331  }
1332 }
1333 
1334 static void compileAssignTernary(Token *&tok, AST_state& state)
1335 {
1336  compileLogicOr(tok, state);
1337  while (tok) {
1338  if (tok->isAssignmentOp()) {
1339  state.assign++;
1340  const Token *tok1 = tok->next();
1341  compileBinOp(tok, state, compileAssignTernary);
1342  if (Token::simpleMatch(tok1, "{") && tok == tok1->link() && tok->next())
1343  tok = tok->next();
1344  if (state.assign > 0)
1345  state.assign--;
1346  } else if (tok->str() == "?") {
1347  // http://en.cppreference.com/w/cpp/language/operator_precedence says about ternary operator:
1348  // "The expression in the middle of the conditional operator (between ? and :) is parsed as if parenthesized: its precedence relative to ?: is ignored."
1349  // Hence, we rely on Tokenizer::prepareTernaryOpForAST() to add such parentheses where necessary.
1350  const bool stopAtColon = state.stopAtColon;
1351  state.stopAtColon = false;
1352  if (tok->strAt(1) == ":") {
1353  state.op.push(nullptr);
1354  }
1355  const int assign = state.assign;
1356  state.assign = 0;
1357  compileBinOp(tok, state, compileAssignTernary);
1358  state.assign = assign;
1359  state.stopAtColon = stopAtColon;
1360  } else if (tok->str() == ":") {
1361  if (state.depth == 1U && state.inCase) {
1362  state.inCase = false;
1363  tok = tok->next();
1364  break;
1365  }
1366  if (state.stopAtColon)
1367  break;
1368  if (state.assign > 0)
1369  break;
1370  compileBinOp(tok, state, compileAssignTernary);
1371  } else break;
1372  }
1373 }
1374 
1375 static void compileComma(Token *&tok, AST_state& state)
1376 {
1377  compileAssignTernary(tok, state);
1378  while (tok) {
1379  if (tok->str() == ",") {
1380  if (Token::simpleMatch(tok, ", }"))
1381  tok = tok->next();
1382  else
1383  compileBinOp(tok, state, compileAssignTernary);
1384  } else if (tok->str() == ";" && state.functionCallEndPar && tok->index() < state.functionCallEndPar->index()) {
1385  compileBinOp(tok, state, compileAssignTernary);
1386  } else break;
1387  }
1388 }
1389 
1390 static void compileExpression(Token *&tok, AST_state& state)
1391 {
1392  if (state.depth > AST_MAX_DEPTH)
1393  throw InternalError(tok, "maximum AST depth exceeded", InternalError::AST); // ticket #5592
1394  if (tok)
1395  compileComma(tok, state);
1396 }
1397 
1398 const Token* isLambdaCaptureList(const Token * tok)
1399 {
1400  // a lambda expression '[x](y){}' is compiled as:
1401  // [
1402  // `-( <<-- optional
1403  // `-{
1404  // see compilePrecedence2
1405  if (!Token::simpleMatch(tok, "["))
1406  return nullptr;
1407  if (!Token::Match(tok->link(), "] (|{"))
1408  return nullptr;
1409  if (Token::simpleMatch(tok->astOperand1(), "{") && tok->astOperand1() == tok->link()->next())
1410  return tok->astOperand1();
1411  if (!tok->astOperand1() || tok->astOperand1()->str() != "(")
1412  return nullptr;
1413  const Token * params = tok->astOperand1();
1414  if (!Token::simpleMatch(params->astOperand1(), "{"))
1415  return nullptr;
1416  return params->astOperand1();
1417 }
1418 
1419 const Token* findLambdaEndTokenWithoutAST(const Token* tok) {
1420  if (!(Token::simpleMatch(tok, "[") && tok->link()))
1421  return nullptr;
1422  tok = tok->link()->next();
1423  if (Token::simpleMatch(tok, "(") && tok->link())
1424  tok = tok->link()->next();
1425  if (Token::simpleMatch(tok, ".")) { // trailing return type
1426  tok = tok->next();
1427  while (Token::Match(tok, "%type%|%name%|::|&|&&|*|<|(")) {
1428  if (tok->link())
1429  tok = tok->link()->next();
1430  else
1431  tok = tok->next();
1432  }
1433  }
1434  if (!(Token::simpleMatch(tok, "{") && tok->link()))
1435  return nullptr;
1436  return tok->link()->next();
1437 }
1438 
1439 static Token * createAstAtToken(Token *tok);
1440 
1441 // Compile inner expressions inside inner ({..}) and lambda bodies
1442 static void createAstAtTokenInner(Token * const tok1, const Token *endToken, bool cpp)
1443 {
1444  for (Token* tok = tok1; precedes(tok, endToken); tok = tok ? tok->next() : nullptr) {
1445  if (tok->str() == "{" && !iscpp11init(tok)) {
1446  const Token * const endToken2 = tok->link();
1447  bool hasAst = false;
1448  for (const Token *inner = tok->next(); inner != endToken2; inner = inner->next()) {
1449  if (inner->astOperand1()) {
1450  hasAst = true;
1451  break;
1452  }
1453  if (tok->isConstOp())
1454  break;
1455  if (inner->str() == "{")
1456  inner = inner->link();
1457  }
1458  if (!hasAst) {
1459  for (; tok && tok != endToken && tok != endToken2; tok = tok ? tok->next() : nullptr)
1460  tok = createAstAtToken(tok);
1461  }
1462  } else if (cpp && tok->str() == "[") {
1463  if (isLambdaCaptureList(tok)) {
1464  tok = tok->astOperand1();
1465  if (tok->str() == "(")
1466  tok = tok->astOperand1();
1467  const Token * const endToken2 = tok->link();
1468  tok = tok->next();
1469  for (; tok && tok != endToken && tok != endToken2; tok = tok ? tok->next() : nullptr)
1470  tok = createAstAtToken(tok);
1471  }
1472  }
1473  else if (Token::simpleMatch(tok, "( * ) [")) {
1474  bool hasAst = false;
1475  for (const Token* tok2 = tok->linkAt(3); tok2 != tok; tok2 = tok2->previous()) {
1476  if (tok2->astParent() || tok2->astOperand1() || tok2->astOperand2()) {
1477  hasAst = true;
1478  break;
1479  }
1480  }
1481  if (!hasAst) {
1482  Token *const startTok = tok = tok->tokAt(4);
1483  const Token* const endtok = startTok->linkAt(-1);
1484  AST_state state(cpp);
1485  compileExpression(tok, state);
1486  createAstAtTokenInner(startTok, endtok, cpp);
1487  }
1488  }
1489  }
1490 }
1491 
1492 static Token * findAstTop(Token *tok1, const Token *tok2)
1493 {
1494  for (Token *tok = tok1; tok && (tok != tok2); tok = tok->next()) {
1495  if (tok->astParent() || tok->astOperand1() || tok->astOperand2()) {
1496  while (tok->astParent() && tok->astParent()->index() >= tok1->index() && tok->astParent()->index() <= tok2->index())
1497  tok = tok->astParent();
1498  return tok;
1499  }
1500  if (Token::simpleMatch(tok, "( {"))
1501  tok = tok->link();
1502  }
1503  for (Token *tok = tok1; tok && (tok != tok2); tok = tok->next()) {
1504  if (tok->isName() || tok->isNumber())
1505  return tok;
1506  if (Token::simpleMatch(tok, "( {"))
1507  tok = tok->link();
1508  }
1509  return nullptr;
1510 }
1511 
1512 static Token * createAstAtToken(Token *tok)
1513 {
1514  const bool cpp = tok->isCpp();
1515  // skip function pointer declaration
1516  if (Token::Match(tok, "%type% %type%") && !Token::Match(tok, "return|throw|new|delete")) {
1517  Token* tok2 = tok->tokAt(2);
1518  // skip type tokens and qualifiers etc
1519  while (Token::Match(tok2, "%type%|*|&"))
1520  tok2 = tok2->next();
1521  if (Token::Match(tok2, "%var% [;,)]"))
1522  return tok2;
1523  }
1524  if (Token::Match(tok, "%type%") && !Token::Match(tok, "return|throw|if|while|new|delete")) {
1525  bool isStandardTypeOrQualifier = false;
1526  Token* type = tok;
1527  while (Token::Match(type, "%type%|*|&|<")) {
1528  if (type->isName() && (type->isStandardType() || Token::Match(type, "const|mutable|static|volatile")))
1529  isStandardTypeOrQualifier = true;
1530  if (type->str() == "<") {
1531  if (type->link())
1532  type = type->link();
1533  else
1534  break;
1535  }
1536  type = type->next();
1537  }
1538  if (isStandardTypeOrQualifier && Token::Match(type, "%var% [;,)]"))
1539  return type;
1540  if (Token::Match(type, "( * *| %var%") &&
1541  Token::Match(type->link()->previous(), "%var%|] ) (") &&
1542  Token::Match(type->link()->linkAt(1), ") [;,)]"))
1543  return type->link()->linkAt(1)->next();
1544  }
1545 
1546  if (Token::simpleMatch(tok, "for (")) {
1547  if (cpp && Token::Match(tok, "for ( const| auto &|&&| [")) {
1548  Token *decl = Token::findsimplematch(tok, "[");
1549  if (Token::simpleMatch(decl->link(), "] :")) {
1550  AST_state state1(cpp);
1551  while (decl->str() != "]") {
1552  if (Token::Match(decl, "%name% ,|]")) {
1553  state1.op.push(decl);
1554  } else if (decl->str() == ",") {
1555  if (!state1.op.empty()) {
1556  decl->astOperand1(state1.op.top());
1557  state1.op.pop();
1558  }
1559  if (!state1.op.empty()) {
1560  state1.op.top()->astOperand2(decl);
1561  state1.op.pop();
1562  }
1563  state1.op.push(decl);
1564  }
1565  decl = decl->next();
1566  }
1567  if (state1.op.size() > 1) {
1568  Token *lastName = state1.op.top();
1569  state1.op.pop();
1570  state1.op.top()->astOperand2(lastName);
1571  }
1572  decl = decl->next();
1573 
1574  Token *colon = decl;
1575  compileExpression(decl, state1);
1576 
1577  tok->next()->astOperand1(tok);
1578  tok->next()->astOperand2(colon);
1579 
1580  return decl;
1581  }
1582  }
1583 
1584  std::vector<Token*> inner;
1585  Token* tok2 = skipDecl(tok->tokAt(2), &inner);
1586  for (Token* tok3 : inner) {
1587  AST_state state1(cpp);
1588  compileExpression(tok3, state1);
1589  }
1590  Token *init1 = nullptr;
1591  Token * const endPar = tok->next()->link();
1592  if (tok2 == tok->tokAt(2) && Token::Match(tok2, "%op%|(")) {
1593  init1 = tok2;
1594  AST_state state1(cpp);
1595  compileExpression(tok2, state1);
1596  if (Token::Match(init1, "( !!{")) {
1597  for (Token *tok3 = init1; tok3 && tok3 != tok3->link(); tok3 = tok3->next()) {
1598  if (tok3->astParent()) {
1599  while (tok3->astParent())
1600  tok3 = tok3->astParent();
1601  init1 = tok3;
1602  break;
1603  }
1604  if (!Token::Match(tok3, "%op%|(|["))
1605  init1 = tok3;
1606  }
1607  }
1608  } else {
1609  while (tok2 && tok2 != endPar && tok2->str() != ";") {
1610  if (tok2->str() == "<" && tok2->link()) {
1611  tok2 = tok2->link();
1612  } else if (Token::Match(tok2, "%name% )| %op%|(|[|.|:|::") || Token::Match(tok2->previous(), "[(;{}] %cop%|(")) {
1613  init1 = tok2;
1614  AST_state state1(cpp);
1615  compileExpression(tok2, state1);
1616  if (Token::Match(tok2, ";|)"))
1617  break;
1618  init1 = nullptr;
1619  }
1620  if (!tok2) // #7109 invalid code
1621  return nullptr;
1622  tok2 = tok2->next();
1623  }
1624  }
1625  if (!tok2 || tok2->str() != ";") {
1626  if (tok2 == endPar && init1) {
1627  createAstAtTokenInner(init1->next(), endPar, cpp);
1628  tok->next()->astOperand2(init1);
1629  tok->next()->astOperand1(tok);
1630  }
1631  return tok2;
1632  }
1633 
1634  Token * const init = init1 ? init1 : tok2;
1635 
1636  Token * const semicolon1 = tok2;
1637  tok2 = tok2->next();
1638  AST_state state2(cpp);
1639  compileExpression(tok2, state2);
1640 
1641  Token * const semicolon2 = tok2;
1642  if (!semicolon2)
1643  return nullptr; // invalid code #7235
1644 
1645  if (semicolon2->str() == ";") {
1646  tok2 = tok2->next();
1647  AST_state state3(cpp);
1648  if (Token::simpleMatch(tok2, "( {")) {
1649  state3.op.push(tok2->next());
1650  tok2 = tok2->link()->next();
1651  }
1652  compileExpression(tok2, state3);
1653 
1654  tok2 = findAstTop(semicolon1->next(), semicolon2);
1655  if (tok2)
1656  semicolon2->astOperand1(tok2);
1657  tok2 = findAstTop(semicolon2->next(), endPar);
1658  if (tok2)
1659  semicolon2->astOperand2(tok2);
1660  else if (!state3.op.empty())
1661  semicolon2->astOperand2(state3.op.top());
1662  semicolon1->astOperand2(semicolon2);
1663  } else {
1664  if (!cpp || state2.op.empty() || !Token::simpleMatch(state2.op.top(), ":"))
1665  throw InternalError(tok, "syntax error", InternalError::SYNTAX);
1666 
1667  semicolon1->astOperand2(state2.op.top());
1668  }
1669 
1670  if (init != semicolon1)
1671  semicolon1->astOperand1(init->astTop());
1672  tok->next()->astOperand1(tok);
1673  tok->next()->astOperand2(semicolon1);
1674 
1675  createAstAtTokenInner(endPar->link(), endPar, cpp);
1676 
1677  return endPar;
1678  }
1679 
1680  if (Token::simpleMatch(tok, "( {"))
1681  return tok;
1682 
1683  if (Token::Match(tok, "%type% <") && tok->linkAt(1) && !Token::Match(tok->linkAt(1), "> [({]"))
1684  return tok->linkAt(1);
1685 
1686  if (cpp && !tok->isKeyword() && Token::Match(tok, "%type% ::|<|%name%")) {
1687  Token *tok2 = tok;
1688  while (true) {
1689  if (Token::Match(tok2, "%name%|> :: %name%"))
1690  tok2 = tok2->tokAt(2);
1691  else if (Token::Match(tok2, "%name% <") && tok2->linkAt(1))
1692  tok2 = tok2->linkAt(1);
1693  else
1694  break;
1695  }
1696  if (Token::Match(tok2, "%name%|> %name% {") && tok2->next()->varId() && iscpp11init(tok2->tokAt(2))) {
1697  Token *const tok1 = tok = tok2->next();
1698  AST_state state(cpp);
1699  compileExpression(tok, state);
1700  createAstAtTokenInner(tok1->next(), tok1->linkAt(1), cpp);
1701  return tok;
1702  }
1703  }
1704 
1705  if (Token::Match(tok, "%type% %name%|*|&|::") && !Token::Match(tok, "return|new")) {
1706  int typecount = 0;
1707  Token *typetok = tok;
1708  while (Token::Match(typetok, "%type%|::|*|&")) {
1709  if (typetok->isName() && !Token::simpleMatch(typetok->previous(), "::"))
1710  typecount++;
1711  typetok = typetok->next();
1712  }
1713  if (Token::Match(typetok, "%var% =") && typetok->varId())
1714  tok = typetok;
1715 
1716  // Do not create AST for function declaration
1717  if (typetok &&
1718  typecount >= 2 &&
1719  !Token::Match(tok, "return|throw") &&
1720  Token::Match(typetok->previous(), "%name% ( !!*") &&
1721  typetok->previous()->varId() == 0 &&
1722  !typetok->previous()->isKeyword() &&
1723  (Token::Match(typetok->link(), ") const|;|{") || Token::Match(typetok->link(), ") const| = delete ;")))
1724  return typetok;
1725  }
1726 
1727  if (Token::Match(tok, "return|case") ||
1728  (cpp && tok->str() == "throw") ||
1729  !tok->previous() ||
1730  Token::Match(tok, "%name% %op%|(|[|.|::|<|?|;") ||
1731  (cpp && Token::Match(tok, "%name% {") && iscpp11init(tok->next())) ||
1732  Token::Match(tok->previous(), "[;{}] %cop%|++|--|( !!{") ||
1733  Token::Match(tok->previous(), "[;{}] %num%|%str%|%char%") ||
1734  Token::Match(tok->previous(), "[;{}] delete new")) {
1735  if (cpp && (Token::Match(tok->tokAt(-2), "[;{}] new|delete %name%") || Token::Match(tok->tokAt(-3), "[;{}] :: new|delete %name%")))
1736  tok = tok->previous();
1737 
1738  Token * const tok1 = tok;
1739  AST_state state(cpp);
1740  if (Token::Match(tok, "%name% ("))
1741  state.functionCallEndPar = tok->linkAt(1);
1742  if (Token::simpleMatch(tok->tokAt(-1), "::") && (!tok->tokAt(-2) || !tok->tokAt(-2)->isName()))
1743  tok = tok->tokAt(-1);
1744  compileExpression(tok, state);
1745  Token * const endToken = tok;
1746  if (endToken == tok1 || !endToken)
1747  return tok1;
1748 
1749  createAstAtTokenInner(tok1->next(), endToken, cpp);
1750 
1751  return endToken->previous();
1752  }
1753 
1754  if (cpp && tok->str() == "{" && iscpp11init(tok)) {
1755  Token * const tok1 = tok;
1756  AST_state state(cpp);
1757  compileExpression(tok, state);
1758  Token* const endToken = tok;
1759  if (endToken == tok1 || !endToken)
1760  return tok1;
1761 
1762  createAstAtTokenInner(tok1->next(), endToken, cpp);
1763  return endToken->previous();
1764  }
1765 
1766  return tok;
1767 }
1768 
1769 void TokenList::createAst() const
1770 {
1771  for (Token *tok = mTokensFrontBack.front; tok; tok = tok ? tok->next() : nullptr) {
1772  Token* const nextTok = createAstAtToken(tok);
1773  if (precedes(nextTok, tok))
1774  throw InternalError(tok, "Syntax Error: Infinite loop when creating AST.", InternalError::AST);
1775  tok = nextTok;
1776  }
1777 }
1778 
1779 namespace {
1780  struct OnException {
1781  std::function<void()> f;
1782 
1783  ~OnException() {
1784 #ifndef _MSC_VER
1785  if (std::uncaught_exception())
1786  f();
1787 #endif
1788  }
1789  };
1790 }
1791 
1792 void TokenList::validateAst(bool print) const
1793 {
1794  OnException oe{[&] {
1795  if (print)
1796  mTokensFrontBack.front->printOut();
1797  }};
1798  // Check for some known issues in AST to avoid crash/hang later on
1799  std::set<const Token*> safeAstTokens; // list of "safe" AST tokens without endless recursion
1800  for (const Token *tok = mTokensFrontBack.front; tok; tok = tok->next()) {
1801  // Syntax error if binary operator only has 1 operand
1802  if ((tok->isAssignmentOp() || tok->isComparisonOp() || Token::Match(tok,"[|^/%]")) && tok->astOperand1() && !tok->astOperand2())
1803  throw InternalError(tok, "Syntax Error: AST broken, binary operator has only one operand.", InternalError::AST);
1804 
1805  // Syntax error if we encounter "?" with operand2 that is not ":"
1806  if (tok->str() == "?") {
1807  if (!tok->astOperand1() || !tok->astOperand2())
1808  throw InternalError(tok, "AST broken, ternary operator missing operand(s)", InternalError::AST);
1809  if (tok->astOperand2()->str() != ":")
1810  throw InternalError(tok, "Syntax Error: AST broken, ternary operator lacks ':'.", InternalError::AST);
1811  }
1812 
1813  // Check for endless recursion
1814  const Token* parent = tok->astParent();
1815  if (parent) {
1816  std::set<const Token*> astTokens; // list of ancestors
1817  astTokens.insert(tok);
1818  do {
1819  if (safeAstTokens.find(parent) != safeAstTokens.end())
1820  break;
1821  if (astTokens.find(parent) != astTokens.end())
1822  throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::AST);
1823  astTokens.insert(parent);
1824  } while ((parent = parent->astParent()) != nullptr);
1825  safeAstTokens.insert(astTokens.cbegin(), astTokens.cend());
1826  } else if (tok->str() == ";") {
1827  safeAstTokens.clear();
1828  } else {
1829  safeAstTokens.insert(tok);
1830  }
1831 
1832  // Don't check templates
1833  if (tok->str() == "<" && tok->link()) {
1834  tok = tok->link();
1835  continue;
1836  }
1837  if (tok->isCast()) {
1838  if (!tok->astOperand2() && precedes(tok->astOperand1(), tok))
1839  throw InternalError(tok, "AST broken: '" + tok->str() + "' has improper operand.", InternalError::AST);
1840  if (tok->astOperand1() && tok->link()) { // skip casts (not part of the AST)
1841  tok = tok->link();
1842  continue;
1843  }
1844  }
1845 
1846  if (findLambdaEndToken(tok)) { // skip lambda captures
1847  tok = tok->link();
1848  continue;
1849  }
1850 
1851  // Check binary operators
1852  if (Token::Match(tok, "%or%|%oror%|%assign%|%comp%")) {
1853  // Skip pure virtual functions
1854  if (Token::simpleMatch(tok->previous(), ") = 0"))
1855  continue;
1856  // Skip operator definitions
1857  if (Token::simpleMatch(tok->previous(), "operator"))
1858  continue;
1859  // Skip incomplete code
1860  if (!tok->astOperand1() && !tok->astOperand2() && !tok->astParent())
1861  continue;
1862  // Skip lambda assignment and/or initializer
1863  if (Token::Match(tok, "= {|^|["))
1864  continue;
1865  // FIXME: Workaround broken AST assignment in type aliases
1866  if (Token::Match(tok->previous(), "%name% = %name%"))
1867  continue;
1868  if (!tok->astOperand1() || !tok->astOperand2())
1869  throw InternalError(tok, "Syntax Error: AST broken, binary operator '" + tok->str() + "' doesn't have two operands.", InternalError::AST);
1870  }
1871 
1872  // Check control blocks and asserts
1873  if (Token::Match(tok->previous(), "if|while|for|switch|assert|ASSERT (")) {
1874  if (!tok->astOperand1() || !tok->astOperand2())
1875  throw InternalError(tok,
1876  "Syntax Error: AST broken, '" + tok->previous()->str() +
1877  "' doesn't have two operands.",
1878  InternalError::AST);
1879  }
1880 
1881  // Check member access
1882  if (Token::Match(tok, "%var% .")) {
1883  if (!tok->astParent()) {
1884  throw InternalError(
1885  tok, "Syntax Error: AST broken, '" + tok->str() + "' doesn't have a parent.", InternalError::AST);
1886  }
1887  if (!tok->next()->astOperand1() || !tok->next()->astOperand2()) {
1888  const std::string& op =
1889  tok->next()->originalName().empty() ? tok->next()->str() : tok->next()->originalName();
1890  throw InternalError(
1891  tok, "Syntax Error: AST broken, '" + op + "' doesn't have two operands.", InternalError::AST);
1892  }
1893  }
1894  }
1895 }
1896 
1897 std::string TokenList::getOrigFile(const Token *tok) const
1898 {
1899  return mOrigFiles.at(tok->fileIndex());
1900 }
1901 
1902 const std::string& TokenList::file(const Token *tok) const
1903 {
1904  return mFiles.at(tok->fileIndex());
1905 }
1906 
1907 std::string TokenList::fileLine(const Token *tok) const
1908 {
1909  return ErrorMessage::FileLocation(tok, this).stringify();
1910 }
1911 
1912 bool TokenList::validateToken(const Token* tok) const
1913 {
1914  if (!tok)
1915  return true;
1916  for (const Token *t = mTokensFrontBack.front; t; t = t->next()) {
1917  if (tok==t)
1918  return true;
1919  }
1920  return false;
1921 }
1922 
1923 void TokenList::simplifyPlatformTypes()
1924 {
1925  if (!mSettings)
1926  return;
1927 
1928  const bool isCPP11 = isCPP() && (mSettings->standards.cpp >= Standards::CPP11);
1929 
1930  enum { isLongLong, isLong, isInt } type;
1931 
1932  /** @todo This assumes a flat address space. Not true for segmented address space (FAR *). */
1933 
1934  if (mSettings->platform.sizeof_size_t == mSettings->platform.sizeof_long)
1935  type = isLong;
1936  else if (mSettings->platform.sizeof_size_t == mSettings->platform.sizeof_long_long)
1937  type = isLongLong;
1938  else if (mSettings->platform.sizeof_size_t == mSettings->platform.sizeof_int)
1939  type = isInt;
1940  else
1941  return;
1942 
1943  for (Token *tok = front(); tok; tok = tok->next()) {
1944  // pre-check to reduce unneeded match calls
1945  if (!Token::Match(tok, "std| ::| %type%"))
1946  continue;
1947  bool isUnsigned;
1948  if (Token::Match(tok, "std| ::| size_t|uintptr_t|uintmax_t")) {
1949  if (isCPP11 && tok->strAt(-1) == "using" && tok->strAt(1) == "=")
1950  continue;
1951  isUnsigned = true;
1952  } else if (Token::Match(tok, "std| ::| ssize_t|ptrdiff_t|intptr_t|intmax_t")) {
1953  if (isCPP11 && tok->strAt(-1) == "using" && tok->strAt(1) == "=")
1954  continue;
1955  isUnsigned = false;
1956  } else
1957  continue;
1958 
1959  bool inStd = false;
1960  if (tok->str() == "::") {
1961  tok->deleteThis();
1962  } else if (tok->str() == "std") {
1963  if (tok->next()->str() != "::")
1964  continue;
1965  inStd = true;
1966  tok->deleteNext();
1967  tok->deleteThis();
1968  }
1969 
1970  if (inStd)
1971  tok->originalName("std::" + tok->str());
1972  else
1973  tok->originalName(tok->str());
1974  if (isUnsigned)
1975  tok->isUnsigned(true);
1976 
1977  switch (type) {
1978  case isLongLong:
1979  tok->isLong(true);
1980  tok->str("long");
1981  break;
1982  case isLong:
1983  tok->str("long");
1984  break;
1985  case isInt:
1986  tok->str("int");
1987  break;
1988  }
1989  }
1990 
1991  const std::string platform_type(mSettings->platform.toString());
1992 
1993  for (Token *tok = front(); tok; tok = tok->next()) {
1994  if (tok->tokType() != Token::eType && tok->tokType() != Token::eName)
1995  continue;
1996 
1997  const Library::PlatformType * const platformtype = mSettings->library.platform_type(tok->str(), platform_type);
1998 
1999  if (platformtype) {
2000  // check for namespace
2001  if (tok->strAt(-1) == "::") {
2002  const Token * tok1 = tok->tokAt(-2);
2003  // skip when non-global namespace defined
2004  if (tok1 && tok1->tokType() == Token::eName)
2005  continue;
2006  tok = tok->previous();
2007  tok->deleteThis();
2008  }
2009  tok->originalName(tok->str());
2010  Token *typeToken;
2011  if (platformtype->mConstPtr) {
2012  tok->str("const");
2013  tok->isSimplifiedTypedef(true);
2014  tok->insertToken("*")->isSimplifiedTypedef(true);
2015  tok->insertToken(platformtype->mType)->isSimplifiedTypedef(true);
2016  typeToken = tok;
2017  } else if (platformtype->mPointer) {
2018  tok->str(platformtype->mType);
2019  tok->isSimplifiedTypedef(true);
2020  typeToken = tok;
2021  tok->insertToken("*")->isSimplifiedTypedef(true);
2022  } else if (platformtype->mPtrPtr) {
2023  tok->str(platformtype->mType);
2024  tok->isSimplifiedTypedef(true);
2025  typeToken = tok;
2026  tok->insertToken("*")->isSimplifiedTypedef(true);
2027  tok->insertToken("*")->isSimplifiedTypedef(true);
2028  } else {
2029  tok->str(platformtype->mType);
2030  tok->isSimplifiedTypedef(true);
2031  typeToken = tok;
2032  }
2033  if (platformtype->mSigned)
2034  typeToken->isSigned(true);
2035  if (platformtype->mUnsigned)
2036  typeToken->isUnsigned(true);
2037  if (platformtype->mLong)
2038  typeToken->isLong(true);
2039  }
2040  }
2041 }
2042 
2043 void TokenList::simplifyStdType()
2044 {
2045  auto isVarDeclC = [](const Token* tok) -> bool {
2046  if (!Token::simpleMatch(tok, "}"))
2047  return false;
2048  tok = tok->link()->previous();
2049  while (Token::Match(tok, "%name%")) {
2050  if (Token::Match(tok, "struct|union|enum"))
2051  return true;
2052  tok = tok->previous();
2053  }
2054  return false;
2055  };
2056 
2057  for (Token *tok = front(); tok; tok = tok->next()) {
2058 
2059  if (isC() && Token::Match(tok, "const|extern *|&|%name%") && (!tok->previous() || Token::Match(tok->previous(), "[;{}]"))) {
2060  if (Token::Match(tok->next(), "%name% !!;"))
2061  continue;
2062  if (isVarDeclC(tok->previous()))
2063  continue;
2064 
2065  tok->insertToken("int");
2066  tok->next()->isImplicitInt(true);
2067  continue;
2068  }
2069 
2070  if (Token::Match(tok, "char|short|int|long|unsigned|signed|double|float") || (isC() && (!mSettings || (mSettings->standards.c >= Standards::C99)) && Token::Match(tok, "complex|_Complex"))) {
2071  bool isFloat= false;
2072  bool isSigned = false;
2073  bool isUnsigned = false;
2074  bool isComplex = false;
2075  int countLong = 0;
2076  Token* typeSpec = nullptr;
2077 
2078  Token* tok2 = tok;
2079  for (; tok2->next(); tok2 = tok2->next()) {
2080  if (tok2->str() == "long") {
2081  countLong++;
2082  if (!isFloat)
2083  typeSpec = tok2;
2084  } else if (tok2->str() == "short") {
2085  typeSpec = tok2;
2086  } else if (tok2->str() == "unsigned")
2087  isUnsigned = true;
2088  else if (tok2->str() == "signed")
2089  isSigned = true;
2090  else if (Token::Match(tok2, "float|double")) {
2091  isFloat = true;
2092  typeSpec = tok2;
2093  } else if (isC() && (!mSettings || (mSettings->standards.c >= Standards::C99)) && Token::Match(tok2, "complex|_Complex"))
2094  isComplex = !isFloat || tok2->str() == "_Complex" || Token::Match(tok2->next(), "*|&|%name%"); // Ensure that "complex" is not the variables name
2095  else if (Token::Match(tok2, "char|int")) {
2096  if (!typeSpec)
2097  typeSpec = tok2;
2098  } else
2099  break;
2100  }
2101 
2102  if (!typeSpec) { // unsigned i; or similar declaration
2103  if (!isComplex) { // Ensure that "complex" is not the variables name
2104  tok->str("int");
2105  tok->isSigned(isSigned);
2106  tok->isUnsigned(isUnsigned);
2107  tok->isImplicitInt(true);
2108  }
2109  } else {
2110  typeSpec->isLong(typeSpec->isLong() || (isFloat && countLong == 1) || countLong > 1);
2111  typeSpec->isComplex(typeSpec->isComplex() || (isFloat && isComplex));
2112  typeSpec->isSigned(typeSpec->isSigned() || isSigned);
2113  typeSpec->isUnsigned(typeSpec->isUnsigned() || isUnsigned);
2114 
2115  // Remove specifiers
2116  const Token* tok3 = tok->previous();
2117  tok2 = tok2->previous();
2118  while (tok3 != tok2) {
2119  if (tok2 != typeSpec &&
2120  (isComplex || !Token::Match(tok2, "complex|_Complex"))) // Ensure that "complex" is not the variables name
2121  tok2->deleteThis();
2122  tok2 = tok2->previous();
2123  }
2124  }
2125  }
2126  }
2127 }
2128 
2129 bool TokenList::isKeyword(const std::string &str) const
2130 {
2131  if (isCPP()) {
2132  // TODO: integrate into keywords?
2133  // types and literals are not handled as keywords
2134  static const std::unordered_set<std::string> cpp_types = {"bool", "false", "true"};
2135  if (cpp_types.find(str) != cpp_types.end())
2136  return false;
2137 
2138  if (mSettings) {
2139  const auto &cpp_keywords = Keywords::getAll(mSettings->standards.cpp);
2140  return cpp_keywords.find(str) != cpp_keywords.end();
2141  }
2142 
2143  static const auto& latest_cpp_keywords = Keywords::getAll(Standards::cppstd_t::CPPLatest);
2144  return latest_cpp_keywords.find(str) != latest_cpp_keywords.end();
2145  }
2146 
2147  // TODO: integrate into Keywords?
2148  // types are not handled as keywords
2149  static const std::unordered_set<std::string> c_types = {"char", "double", "float", "int", "long", "short"};
2150  if (c_types.find(str) != c_types.end())
2151  return false;
2152 
2153  if (mSettings) {
2154  const auto &c_keywords = Keywords::getAll(mSettings->standards.c);
2155  return c_keywords.find(str) != c_keywords.end();
2156  }
2157 
2158  static const auto& latest_c_keywords = Keywords::getAll(Standards::cstd_t::CLatest);
2159  return latest_c_keywords.find(str) != latest_c_keywords.end();
2160 }
2161 
2162 bool TokenList::isC() const
2163 {
2164  ASSERT_LANG(mLang != Standards::Language::None);
2165 
2166  // TODO: remove the fallback
2167  if (mLang == Standards::Language::None)
2168  return false; // treat as C++ by default
2169 
2170  return mLang == Standards::Language::C;
2171 }
2172 
2173 bool TokenList::isCPP() const
2174 {
2175  ASSERT_LANG(mLang != Standards::Language::None);
2176 
2177  // TODO: remove the fallback
2178  if (mLang == Standards::Language::None)
2179  return true; // treat as C++ by default
2180 
2181  return mLang == Standards::Language::CPP;
2182 }
2183 
2184 void TokenList::setLang(Standards::Language lang)
2185 {
2186  ASSERT_LANG(lang != Standards::Language::None);
2187  ASSERT_LANG(mLang == Standards::Language::None);
2188 
2189  mLang = lang;
2190 }
precedes
bool precedes(const Token *tok1, const Token *tok2)
If tok2 comes after tok1.
Definition: astutils.cpp:994
findLambdaEndToken
const Token * findLambdaEndToken(const Token *first)
find lambda function end token
Definition: astutils.cpp:3195
ErrorMessage::FileLocation
File name and line number.
Definition: errorlogger.h:55
ErrorMessage::FileLocation::stringify
std::string stringify() const
Definition: errorlogger.cpp:738
Keywords::getAll
static const std::unordered_set< std::string > & getAll(Standards::cstd_t cStd)
Definition: keywords.cpp:152
Library::platform_type
const PlatformType * platform_type(const std::string &name, const std::string &platform) const
Definition: library.h:485
Path::identify
static Standards::Language identify(const std::string &path, bool *header=nullptr)
Identify the language based on the file extension.
Definition: path.cpp:248
Path::sameFileName
static bool sameFileName(const std::string &fname1, const std::string &fname2)
Compare filenames to see if they are the same.
Definition: path.cpp:98
Path::getRelativePath
static std::string getRelativePath(const std::string &absolutePath, const std::vector< std::string > &basePaths)
Create a relative path from an absolute one, if absolute path is inside the basePaths.
Definition: path.cpp:181
Platform::sizeof_long_long
std::size_t sizeof_long_long
Definition: platform.h:96
Platform::sizeof_int
std::size_t sizeof_int
Definition: platform.h:94
Platform::sizeof_size_t
std::size_t sizeof_size_t
Definition: platform.h:101
Platform::toString
const char * toString() const
Definition: platform.h:148
Platform::sizeof_long
std::size_t sizeof_long
Definition: platform.h:95
Settings
This is just a container for general settings so that we don't need to pass individual values to func...
Definition: settings.h:95
Settings::basePaths
std::vector< std::string > basePaths
Paths used as base for conversion to relative paths.
Definition: settings.h:118
Settings::enforcedLang
Standards::Language enforcedLang
Name of the language that is enforced.
Definition: settings.h:190
Settings::relativePaths
bool relativePaths
Use relative paths in output.
Definition: settings.h:285
Settings::library
Library library
Library.
Definition: settings.h:237
Settings::platform
Platform platform
Definition: settings.h:255
Settings::standards
Standards standards
Struct contains standards settings.
Definition: settings.h:366
TokenList::isC
bool isC() const
TokenList::copyTokens
static Token * copyTokens(Token *dest, const Token *first, const Token *last, bool one_line=true)
Copy tokens.
Definition: tokenlist.cpp:264
TokenList::clangSetOrigFiles
void clangSetOrigFiles()
Definition: tokenlist.cpp:127
TokenList::mTokensFrontBack
TokensFrontBack mTokensFrontBack
Token list.
Definition: tokenlist.h:209
TokenList::fileLine
std::string fileLine(const Token *tok) const
Get file:line for a given token.
TokenList::deallocateTokens
void deallocateTokens()
Deallocate list.
Definition: tokenlist.cpp:86
TokenList::createAst
void createAst() const
Create abstract syntax tree.
TokenList::deleteTokens
static void deleteTokens(Token *tok)
Delete all tokens in given token list.
Definition: tokenlist.cpp:132
TokenList::TokenList
TokenList(const Settings *settings)
Definition: tokenlist.cpp:59
TokenList::simplifyPlatformTypes
void simplifyPlatformTypes()
Convert platform dependent types to standard types.
TokenList::validateToken
bool validateToken(const Token *tok) const
Verify that the given token is an element of the tokenlist.
TokenList::isKeyword
bool isKeyword(const std::string &str) const
TokenList::getSourceFilePath
const std::string & getSourceFilePath() const
Definition: tokenlist.cpp:75
TokenList::calculateHash
std::size_t calculateHash() const
Calculates a hash of the token list used to compare multiple token lists with each other as quickly a...
Definition: tokenlist.cpp:424
TokenList::setLang
void setLang(Standards::Language lang)
TokenList::file
const std::string & file(const Token *tok) const
get filename for given token
TokenList::insertTokens
static void insertTokens(Token *dest, const Token *src, nonneg int n)
Definition: tokenlist.cpp:304
TokenList::determineCppC
void determineCppC()
Definition: tokenlist.cpp:94
TokenList::isCPP
bool isCPP() const
TokenList::simplifyStdType
void simplifyStdType()
Collapse compound standard types into a single token.
TokenList::createTokensInternal
bool createTokensInternal(std::istream &code, const std::string &file0)
Definition: tokenlist.cpp:361
TokenList::getFiles
const std::vector< std::string > & getFiles() const
Get filenames (the sourcefile + the files it include).
Definition: tokenlist.h:141
TokenList::addtoken
void addtoken(const std::string &str, const nonneg int lineno, const nonneg int column, const nonneg int fileno, bool split=false)
Definition: tokenlist.cpp:145
TokenList::front
const Token * front() const
get first token of list
Definition: tokenlist.h:119
TokenList::createTokens
bool createTokens(std::istream &code, const std::string &file0)
Create tokens from code.
Definition: tokenlist.cpp:336
TokenList::mOrigFiles
std::vector< std::string > mOrigFiles
Original filenames for the tokenized source code (source + included)
Definition: tokenlist.h:215
TokenList::appendFileIfNew
int appendFileIfNew(std::string fileName)
append file name if seen the first time; return its index in any case
Definition: tokenlist.cpp:110
TokenList::mLang
Standards::Language mLang
File is known to be C/C++ code.
Definition: tokenlist.h:221
TokenList::mFiles
std::vector< std::string > mFiles
filenames for the tokenized source code (source + included)
Definition: tokenlist.h:212
TokenList::getOrigFile
std::string getOrigFile(const Token *tok) const
TokenList::mSettings
const Settings *const mSettings
settings
Definition: tokenlist.h:218
TokenList::validateAst
void validateAst(bool print) const
Check abstract syntax tree.
Token
The token list that the TokenList generates is a linked-list of this class.
Definition: token.h:150
Token::str
void str(T &&s)
Definition: token.h:179
Token::index
nonneg int index() const
Definition: token.h:1247
Token::astTop
Token * astTop()
Definition: token.h:1416
Token::Match
static bool Match(const Token *tok, const char pattern[], nonneg int varid=0)
Match given token (or list of tokens) to a pattern list.
Definition: token.cpp:688
Token::deleteThis
void deleteThis()
Remove the contents for this token from the token list.
Definition: token.cpp:329
Token::isKeyword
bool isKeyword() const
Definition: token.h:358
Token::setMacroName
void setMacroName(std::string name)
Definition: token.h:758
Token::originalName
const std::string & originalName() const
Definition: token.h:1193
Token::isName
bool isName() const
Definition: token.h:361
Token::printOut
void printOut(const char *title=nullptr) const
For debugging purposes, prints token and all tokens followed by it.
Definition: token.cpp:1257
Token::flags
uint64_t flags() const
Definition: token.h:418
Token::isCpp11init
TokenImpl::Cpp11init isCpp11init() const
Definition: token.h:1471
Token::isUnsigned
bool isUnsigned() const
Definition: token.h:424
Token::isSimplifiedTypedef
bool isSimplifiedTypedef() const
Definition: token.h:580
Token::setTokenDebug
void setTokenDebug(TokenDebug td)
Definition: token.h:1478
Token::createMutualLinks
static void createMutualLinks(Token *begin, Token *end)
Links two elements against each other.
Definition: token.cpp:1248
Token::isCpp
bool isCpp() const
Definition: token.cpp:2718
Token::isImplicitInt
bool isImplicitInt() const
Definition: token.h:622
Token::strAt
const std::string & strAt(int index) const
Definition: token.cpp:423
Token::assignProgressValues
static void assignProgressValues(Token *tok)
Calculate progress values for all tokens.
Definition: token.cpp:2307
Token::astOperand1
void astOperand1(Token *tok)
Definition: token.cpp:1456
Token::varId
nonneg int varId() const
Definition: token.h:870
Token::isSigned
bool isSigned() const
Definition: token.h:430
Token::isCast
bool isCast() const
Definition: token.h:458
Token::isIncDecOp
bool isIncDecOp() const
Definition: token.h:407
Token::isLiteral
bool isLiteral() const
Definition: token.h:368
Token::setCpp11init
void setCpp11init(bool cpp11init) const
Definition: token.h:1468
Token::findsimplematch
static const Token * findsimplematch(const Token *const startTok, const char(&pattern)[count])
Definition: token.h:763
Token::tokAt
const Token * tokAt(int index) const
Definition: token.cpp:393
Token::deleteNext
void deleteNext(nonneg int count=1)
Unlink and delete the next 'count' tokens.
Definition: token.cpp:245
Token::isConstOp
bool isConstOp() const
Definition: token.h:385
Token::insertToken
Token * insertToken(const std::string &tokenStr, const std::string &originalNameStr=emptyString, const std::string &macroNameStr=emptyString, bool prepend=false)
Insert new token after this token.
Definition: token.cpp:1105
Token::tokType
Token::Type tokType() const
Definition: token.h:343
Token::astOperand2
void astOperand2(Token *tok)
Definition: token.cpp:1468
Token::isLong
bool isLong() const
Definition: token.h:443
Token::link
void link(Token *linkToToken)
Create link to given token.
Definition: token.h:1015
Token::linkAt
const Token * linkAt(int index) const
Definition: token.cpp:413
Token::eName
@ eName
Definition: token.h:161
Token::eType
@ eType
Definition: token.h:161
Token::eIncDecOp
@ eIncDecOp
Definition: token.h:163
Token::previous
Token * previous()
Definition: token.h:862
Token::isComplex
bool isComplex() const
Definition: token.h:555
Token::isAssignmentOp
bool isAssignmentOp() const
Definition: token.h:401
Token::linenr
nonneg int linenr() const
Definition: token.h:816
Token::isStandardType
bool isStandardType() const
Definition: token.h:449
Token::isComparisonOp
bool isComparisonOp() const
Definition: token.h:398
Token::next
Token * next()
Definition: token.h:830
Token::simpleMatch
static bool simpleMatch(const Token *tok, const char(&pattern)[count])
Match given token (or list of tokens) to a pattern list.
Definition: token.h:252
Token::fileIndex
nonneg int fileIndex() const
Definition: token.h:809
Token::getMacroName
std::string getMacroName() const
Definition: token.h:755
Token::column
nonneg int column() const
Definition: token.h:823
Token::astParent
void astParent(Token *tok)
Definition: token.cpp:1437
emptyString
static const std::string emptyString
Definition: config.h:127
nonneg
#define nonneg
Definition: config.h:138
split
static std::vector< std::string > split(const std::string &str, const std::string &sep=" ")
Definition: cppcheck.cpp:113
findTypeEnd
Token * findTypeEnd(Token *tok)
Definition: token.cpp:2674
findLambdaEndScope
Token * findLambdaEndScope(Token *tok)
Definition: token.cpp:2686
InternalError
Simple container to be thrown when internal error is detected.
Definition: errortypes.h:36
Library::PlatformType::mType
std::string mType
Definition: library.h:468
Standards::c
enum Standards::cstd_t c
Standards::cpp
enum Standards::cppstd_t cpp
TokensFrontBack::back
Token * back
Definition: tokenlist.h:49
TokensFrontBack::front
Token * front
Definition: tokenlist.h:48
ASSERT_LANG
#define ASSERT_LANG(x)
Definition: tokenlist.cpp:48
skipDecl
static Token * skipDecl(Token *tok, std::vector< Token * > *inner=nullptr)
Definition: tokenlist.cpp:454
AST_MAX_DEPTH
static constexpr int AST_MAX_DEPTH
Definition: tokenlist.cpp:56
iscast
static bool iscast(const Token *tok, bool cpp)
Definition: tokenlist.cpp:488
findLambdaEndTokenWithoutAST
const Token * findLambdaEndTokenWithoutAST(const Token *tok)
isLambdaCaptureList
const Token * isLambdaCaptureList(const Token *tok)
Generated on Tue May 14 2024 11:53:16 for Cppcheck by doxygen 1.9.1