Coverage Report

Created: 2023-09-25 06:15

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