Cppcheck
templatesimplifier.h
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 #ifndef templatesimplifierH
22 #define templatesimplifierH
23 //---------------------------------------------------------------------------
24 
25 #include "config.h"
26 
27 #include <ctime>
28 #include <list>
29 #include <map>
30 #include <set>
31 #include <string>
32 #include <unordered_map>
33 #include <vector>
34 
35 class ErrorLogger;
36 class Settings;
37 class Token;
38 class Tokenizer;
39 class TokenList;
40 struct newInstantiation;
41 
42 /// @addtogroup Core
43 /// @{
44 
45 /** @brief Simplify templates from the preprocessed and partially simplified code. */
47  friend class TestSimplifyTemplate;
48 
49 public:
50  explicit TemplateSimplifier(Tokenizer &tokenizer);
51 
52  const std::string& dump() const {
53  return mDump;
54  }
55 
56  /**
57  */
58  void checkComplicatedSyntaxErrorsInTemplates();
59 
60  /**
61  * is the token pointing at a template parameters block
62  * < int , 3 > => yes
63  * \param tok start token that must point at "<"
64  * \return number of parameters (invalid parameters => 0)
65  */
66  static unsigned int templateParameters(const Token *tok);
67 
68  /**
69  * Token and its full scopename
70  */
71  class TokenAndName {
73  std::string mScope;
74  std::string mName;
75  std::string mFullName;
76  const Token *mNameToken;
77  const Token *mParamEnd;
78  unsigned int mFlags;
79 
80  enum {
81  fIsClass = (1 << 0), // class template
82  fIsFunction = (1 << 1), // function template
83  fIsVariable = (1 << 2), // variable template
84  fIsAlias = (1 << 3), // alias template
85  fIsSpecialization = (1 << 4), // user specialized template
86  fIsPartialSpecialization = (1 << 5), // user partial specialized template
87  fIsForwardDeclaration = (1 << 6), // forward declaration
88  fIsVariadic = (1 << 7), // variadic template
89  fIsFriend = (1 << 8), // friend template
90  fFamilyMask = (fIsClass | fIsFunction | fIsVariable)
91  };
92 
93  void isClass(bool state) {
94  setFlag(fIsClass, state);
95  }
96  void isFunction(bool state) {
97  setFlag(fIsFunction, state);
98  }
99  void isVariable(bool state) {
100  setFlag(fIsVariable, state);
101  }
102  void isAlias(bool state) {
103  setFlag(fIsAlias, state);
104  }
105  void isSpecialization(bool state) {
106  setFlag(fIsSpecialization, state);
107  }
108  void isPartialSpecialization(bool state) {
109  setFlag(fIsPartialSpecialization, state);
110  }
111  void isForwardDeclaration(bool state) {
112  setFlag(fIsForwardDeclaration, state);
113  }
114  void isVariadic(bool state) {
115  setFlag(fIsVariadic, state);
116  }
117  void isFriend(bool state) {
118  setFlag(fIsFriend, state);
119  }
120 
121  /**
122  * Get specified flag state.
123  * @param flag flag to get state of
124  * @return true if flag set or false in flag not set
125  */
126  bool getFlag(unsigned int flag) const {
127  return ((mFlags & flag) != 0);
128  }
129 
130  /**
131  * Set specified flag state.
132  * @param flag flag to set state
133  * @param state new state of flag
134  */
135  void setFlag(unsigned int flag, bool state) {
136  mFlags = state ? mFlags | flag : mFlags & ~flag;
137  }
138 
139  public:
140  /**
141  * Constructor used for instantiations.
142  * \param token template instantiation name token "name<...>"
143  * \param scope full qualification of template(scope)
144  */
145  TokenAndName(Token *token, std::string scope);
146  /**
147  * Constructor used for declarations.
148  * \param token template declaration token "template < ... >"
149  * \param scope full qualification of template(scope)
150  * \param nameToken template name token "template < ... > class name"
151  * \param paramEnd template parameter end token ">"
152  */
153  TokenAndName(Token *token, std::string scope, const Token *nameToken, const Token *paramEnd);
154  TokenAndName(const TokenAndName& other);
155  ~TokenAndName();
156 
157  bool operator == (const TokenAndName & rhs) const {
158  return mToken == rhs.mToken && mScope == rhs.mScope && mName == rhs.mName && mFullName == rhs.mFullName &&
159  mNameToken == rhs.mNameToken && mParamEnd == rhs.mParamEnd && mFlags == rhs.mFlags;
160  }
161 
162  std::string dump(const std::vector<std::string>& fileNames) const;
163 
164  // TODO: do not return non-const pointer from const object
165  Token * token() const {
166  return mToken;
167  }
168  void token(Token * token) {
169  mToken = token;
170  }
171  const std::string & scope() const {
172  return mScope;
173  }
174  const std::string & name() const {
175  return mName;
176  }
177  const std::string & fullName() const {
178  return mFullName;
179  }
180  const Token * nameToken() const {
181  return mNameToken;
182  }
183  const Token * paramEnd() const {
184  return mParamEnd;
185  }
186  void paramEnd(const Token *end) {
187  mParamEnd = end;
188  }
189 
190  bool isClass() const {
191  return getFlag(fIsClass);
192  }
193  bool isFunction() const {
194  return getFlag(fIsFunction);
195  }
196  bool isVariable() const {
197  return getFlag(fIsVariable);
198  }
199  bool isAlias() const {
200  return getFlag(fIsAlias);
201  }
202  bool isSpecialization() const {
203  return getFlag(fIsSpecialization);
204  }
205  bool isPartialSpecialization() const {
206  return getFlag(fIsPartialSpecialization);
207  }
208  bool isForwardDeclaration() const {
209  return getFlag(fIsForwardDeclaration);
210  }
211  bool isVariadic() const {
212  return getFlag(fIsVariadic);
213  }
214  bool isFriend() const {
215  return getFlag(fIsFriend);
216  }
217 
218  /**
219  * Get alias start token.
220  * template < ... > using X = foo < ... >;
221  * ^
222  * @return alias start token
223  */
224  const Token * aliasStartToken() const;
225 
226  /**
227  * Get alias end token.
228  * template < ... > using X = foo < ... >;
229  * ^
230  * @return alias end token
231  */
232  const Token * aliasEndToken() const;
233 
234  /**
235  * Is token an alias token?
236  * template < ... > using X = foo < ... >;
237  * ^
238  * @param tok token to check
239  * @return true if alias token, false if not
240  */
241  bool isAliasToken(const Token *tok) const;
242 
243  /**
244  * Is declaration the same family (class, function or variable).
245  *
246  * @param decl declaration to compare to
247  * @return true if same family, false if different family
248  */
250  // Make sure a family flag is set and matches.
251  // This works because at most only one flag will be set.
252  return ((mFlags & fFamilyMask) && (decl.mFlags & fFamilyMask));
253  }
254  };
255 
256  /**
257  * Find last token of a template declaration.
258  * @param tok start token of declaration "template" or token after "template < ... >"
259  * @return last token of declaration or nullptr if syntax error
260  */
261  static Token *findTemplateDeclarationEnd(Token *tok);
262  static const Token *findTemplateDeclarationEnd(const Token *tok);
263 
264  /**
265  * Match template declaration/instantiation
266  * @param instance template instantiation
267  * @param numberOfArguments number of template arguments
268  * @param variadic last template argument is variadic
269  * @param patternAfter pattern that must match the tokens after the ">"
270  * @return match => true
271  */
272  static bool instantiateMatch(const Token *instance, const std::size_t numberOfArguments, bool variadic, const char patternAfter[]);
273 
274  /**
275  * Match template declaration/instantiation
276  * @param tok The ">" token e.g. before "class"
277  * @return -1 to bail out or positive integer to identity the position
278  * of the template name.
279  */
280  int getTemplateNamePosition(const Token *tok);
281 
282  /**
283  * Get class template name position
284  * @param tok The ">" token e.g. before "class"
285  * @param namepos return offset to name
286  * @return true if name found, false if not
287  * */
288  static bool getTemplateNamePositionTemplateClass(const Token *tok, int &namepos);
289 
290  /**
291  * Get function template name position
292  * @param tok The ">" token
293  * @param namepos return offset to name
294  * @return true if name found, false if not
295  * */
296  static bool getTemplateNamePositionTemplateFunction(const Token *tok, int &namepos);
297 
298  /**
299  * Get variable template name position
300  * @param tok The ">" token
301  * @param namepos return offset to name
302  * @return true if name found, false if not
303  * */
304  static bool getTemplateNamePositionTemplateVariable(const Token *tok, int &namepos);
305 
306  /**
307  * Simplify templates
308  * @param maxtime time when the simplification should be stopped
309  */
310  void simplifyTemplates(const std::time_t maxtime);
311 
312  /**
313  * Simplify constant calculations such as "1+2" => "3"
314  * @param tok start token
315  * @return true if modifications to token-list are done.
316  * false if no modifications are done.
317  */
318  static bool simplifyNumericCalculations(Token *tok, bool isTemplate = true);
319 
320  /**
321  * Simplify constant calculations such as "1+2" => "3".
322  * This also performs simple cleanup of parentheses etc.
323  * @return true if modifications to token-list are done.
324  * false if no modifications are done.
325  */
326  bool simplifyCalculations(Token* frontToken = nullptr, const Token *backToken = nullptr, bool isTemplate = true);
327 
328  /** Simplify template instantiation arguments.
329  * @param start first token of arguments
330  * @param end token following last argument token
331  */
332  void simplifyTemplateArgs(Token *start, const Token *end, std::vector<newInstantiation>* newInst = nullptr);
333 
334 private:
335  /**
336  * Get template declarations
337  * @return true if code has templates.
338  */
339  bool getTemplateDeclarations();
340 
341  /** Add template instantiation.
342  * @param token first token of instantiation
343  * @param scope scope of instantiation
344  */
345  void addInstantiation(Token *token, const std::string &scope);
346 
347  /**
348  * Get template instantiations
349  */
350  void getTemplateInstantiations();
351 
352  /**
353  * Fix forward declared default argument values by copying them
354  * when they are not present in the declaration.
355  */
356  void fixForwardDeclaredDefaultArgumentValues();
357 
358  /**
359  * simplify template instantiations (use default argument values)
360  */
361  void useDefaultArgumentValues();
362 
363  /**
364  * simplify template instantiations (use default argument values)
365  * @param declaration template declaration or forward declaration
366  */
367  void useDefaultArgumentValues(TokenAndName &declaration);
368 
369  /**
370  * Try to locate a matching declaration for each user defined
371  * specialization.
372  */
373  void getSpecializations();
374 
375  /**
376  * Try to locate a matching declaration for each user defined
377  * partial specialization.
378  */
379  void getPartialSpecializations();
380 
381  /**
382  * simplify template aliases
383  */
384  void simplifyTemplateAliases();
385 
386  /**
387  * Simplify templates : expand all instantiations for a template
388  * @todo It seems that inner templates should be instantiated recursively
389  * @param templateDeclaration template declaration
390  * @param specializations template specializations (list each template name token)
391  * @param maxtime time when the simplification will stop
392  * @param expandedtemplates all templates that has been expanded so far. The full names are stored.
393  * @return true if the template was instantiated
394  */
395  bool simplifyTemplateInstantiations(
396  const TokenAndName &templateDeclaration,
397  const std::list<const Token *> &specializations,
398  const std::time_t maxtime,
399  std::set<std::string> &expandedtemplates);
400 
401  /**
402  * Simplify templates : add namespace to template name
403  * @param templateDeclaration template declaration
404  * @param tok place to insert namespace
405  */
406  void addNamespace(const TokenAndName &templateDeclaration, const Token *tok);
407 
408  /**
409  * Simplify templates : check if namespace already present
410  * @param templateDeclaration template declaration
411  * @param tok place to start looking for namespace
412  * @return true if namespace already present
413  */
414  static bool alreadyHasNamespace(const TokenAndName &templateDeclaration, const Token *tok);
415 
416  /**
417  * Expand a template. Create "expanded" class/function at end of tokenlist.
418  * @param templateDeclaration Template declaration information
419  * @param templateInstantiation Full name of template
420  * @param typeParametersInDeclaration The type parameters of the template
421  * @param newName New name of class/function.
422  * @param copy copy or expand in place
423  */
424  void expandTemplate(
425  const TokenAndName &templateDeclaration,
426  const TokenAndName &templateInstantiation,
427  const std::vector<const Token *> &typeParametersInDeclaration,
428  const std::string &newName,
429  bool copy);
430 
431  /**
432  * Replace all matching template usages 'Foo < int >' => 'Foo<int>'
433  * @param instantiation Template instantiation information.
434  * @param typeStringsUsedInTemplateInstantiation template parameters. list of token strings.
435  * @param newName The new type name
436  */
437  void replaceTemplateUsage(const TokenAndName &instantiation,
438  const std::list<std::string> &typeStringsUsedInTemplateInstantiation,
439  const std::string &newName);
440 
441  /**
442  * @brief TemplateParametersInDeclaration
443  * @param tok template < typename T, typename S >
444  * ^ tok
445  * @param typeParametersInDeclaration template < typename T, typename S >
446  * ^ [0] ^ [1]
447  */
448  static void getTemplateParametersInDeclaration(
449  const Token * tok,
450  std::vector<const Token *> & typeParametersInDeclaration);
451 
452  /**
453  * Remove a specific "template < ..." template class/function
454  */
455  static bool removeTemplate(Token *tok, std::map<Token*, Token*>* forwardDecls = nullptr);
456 
457  /** Syntax error */
458  NORETURN static void syntaxError(const Token *tok);
459 
460  static bool matchSpecialization(
461  const Token *templateDeclarationNameToken,
462  const Token *templateInstantiationNameToken,
463  const std::list<const Token *> & specializations);
464 
465  /*
466  * Same as Token::eraseTokens() but tries to fix up lists with pointers to the deleted tokens.
467  * @param begin Tokens after this will be erased.
468  * @param end Tokens before this will be erased.
469  */
470  static void eraseTokens(Token *begin, const Token *end);
471 
472  /**
473  * Delete specified token without invalidating pointer to following token.
474  * tok will be invalidated.
475  * @param tok token to delete
476  */
477  static void deleteToken(Token *tok);
478 
479  /**
480  * Get the new token name.
481  * @param tok2 name token
482  * @param typeStringsUsedInTemplateInstantiation type strings use in template instantiation
483  * @return new token name
484  */
485  std::string getNewName(
486  Token *tok2,
487  std::list<std::string> &typeStringsUsedInTemplateInstantiation);
488 
489  void printOut(
490  const TokenAndName &tokenAndName,
491  const std::string &indent = " ") const;
492  void printOut(const std::string &text = emptyString) const;
493 
498  bool mChanged{};
499 
500  std::list<TokenAndName> mTemplateDeclarations;
501  std::list<TokenAndName> mTemplateForwardDeclarations;
502  std::map<Token *, Token *> mTemplateForwardDeclarationsMap;
503  std::map<Token *, Token *> mTemplateSpecializationMap;
504  std::map<Token *, Token *> mTemplatePartialSpecializationMap;
505  std::list<TokenAndName> mTemplateInstantiations;
506  std::list<TokenAndName> mInstantiatedTemplates;
507  std::list<TokenAndName> mMemberFunctionsToDelete;
508  std::vector<TokenAndName> mExplicitInstantiationsToDelete;
509  std::vector<TokenAndName> mTypesUsedInTemplateInstantiation;
510  std::unordered_map<const Token*, int> mTemplateNamePos;
511  std::string mDump;
512 };
513 
514 /// @}
515 //---------------------------------------------------------------------------
516 #endif // templatesimplifierH
int numberOfArguments(const Token *ftok)
Determines the number of arguments - if token is a function call or macro.
Definition: astutils.cpp:3063
This is an interface, which the class responsible of error logging should implement.
Definition: errorlogger.h:214
This is just a container for general settings so that we don't need to pass individual values to func...
Definition: settings.h:95
Token and its full scopename.
void setFlag(unsigned int flag, bool state)
Set specified flag state.
bool getFlag(unsigned int flag) const
Get specified flag state.
bool isSameFamily(const TemplateSimplifier::TokenAndName &decl) const
Is declaration the same family (class, function or variable).
const std::string & scope() const
const std::string & name() const
const std::string & fullName() const
Simplify templates from the preprocessed and partially simplified code.
std::list< TokenAndName > mTemplateDeclarations
std::list< TokenAndName > mInstantiatedTemplates
std::vector< TokenAndName > mTypesUsedInTemplateInstantiation
std::vector< TokenAndName > mExplicitInstantiationsToDelete
std::list< TokenAndName > mTemplateForwardDeclarations
ErrorLogger & mErrorLogger
std::unordered_map< const Token *, int > mTemplateNamePos
const Settings & mSettings
const std::string & dump() const
std::list< TokenAndName > mTemplateInstantiations
std::map< Token *, Token * > mTemplateForwardDeclarationsMap
std::list< TokenAndName > mMemberFunctionsToDelete
std::map< Token *, Token * > mTemplatePartialSpecializationMap
std::map< Token *, Token * > mTemplateSpecializationMap
The token list that the TokenList generates is a linked-list of this class.
Definition: token.h:150
The main purpose is to tokenize the source code.
Definition: tokenize.h:46
static const std::string emptyString
Definition: config.h:127
#define CPPCHECKLIB
Definition: config.h:35
#define NORETURN
Definition: config.h:80
bool operator==(const QErrorPathItem &i1, const QErrorPathItem &i2)
Definition: erroritem.cpp:32
static void indent(std::string &str, const nonneg int indent1, const nonneg int indent2)
Definition: token.cpp:1708