LookupContext.cpp 73.9 KB
Newer Older
hjk's avatar
hjk committed
1
/****************************************************************************
2
**
Eike Ziller's avatar
Eike Ziller committed
3
4
** Copyright (C) 2015 The Qt Company Ltd.
** Contact: http://www.qt.io/licensing
5
**
hjk's avatar
hjk committed
6
** This file is part of Qt Creator.
7
**
hjk's avatar
hjk committed
8
9
10
11
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
Eike Ziller's avatar
Eike Ziller committed
12
13
** a written agreement between you and The Qt Company.  For licensing terms and
** conditions see http://www.qt.io/terms-conditions.  For further information
Eike Ziller's avatar
Eike Ziller committed
14
** use the contact form at http://www.qt.io/contact-us.
15
16
**
** GNU Lesser General Public License Usage
hjk's avatar
hjk committed
17
** Alternatively, this file may be used under the terms of the GNU Lesser
Eike Ziller's avatar
Eike Ziller committed
18
19
20
21
22
23
** General Public License version 2.1 or version 3 as published by the Free
** Software Foundation and appearing in the file LICENSE.LGPLv21 and
** LICENSE.LGPLv3 included in the packaging of this file.  Please review the
** following information to ensure the GNU Lesser General Public License
** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
hjk's avatar
hjk committed
24
**
Eike Ziller's avatar
Eike Ziller committed
25
26
** In addition, as a special exception, The Qt Company gives you certain additional
** rights.  These rights are described in The Qt Company LGPL Exception
con's avatar
con committed
27
28
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
hjk's avatar
hjk committed
29
****************************************************************************/
30
31

#include "LookupContext.h"
32

33
34
#include "ResolveExpression.h"
#include "Overview.h"
35
#include "CppRewriter.h"
36
#include "TypeResolver.h"
37

38
39
40
41
42
43
#include <cplusplus/CoreTypes.h>
#include <cplusplus/Symbols.h>
#include <cplusplus/Literals.h>
#include <cplusplus/Names.h>
#include <cplusplus/Scope.h>
#include <cplusplus/Control.h>
44

45
46
47
#include <QStack>
#include <QHash>
#include <QVarLengthArray>
hjk's avatar
hjk committed
48
#include <QDebug>
49

50
static const bool debug = ! qgetenv("QTC_LOOKUPCONTEXT_DEBUG").isEmpty();
51

52
53
namespace CPlusPlus {

54
typedef QSet<Internal::LookupScopePrivate *> ProcessedSet;
Orgad Shaneh's avatar
Orgad Shaneh committed
55

56
static void addNames(const Name *name, QList<const Name *> *names, bool addAllNames = false)
57
58
59
{
    if (! name)
        return;
60
    if (const QualifiedNameId *q = name->asQualifiedNameId()) {
61
        addNames(q->base(), names);
62
        addNames(q->name(), names, addAllNames);
63
    } else if (addAllNames || name->isNameId() || name->isTemplateNameId() || name->isAnonymousNameId()) {
64
        names->append(name);
65
66
67
    }
}

68
static void path_helper(Symbol *symbol, QList<const Name *> *names)
69
70
71
72
{
    if (! symbol)
        return;

73
    path_helper(symbol->enclosingScope(), names);
74

75
76
    if (symbol->name()) {
        if (symbol->isClass() || symbol->isNamespace()) {
77
            addNames(symbol->name(), names);
78

79
        } else if (symbol->isObjCClass() || symbol->isObjCBaseClass() || symbol->isObjCProtocol()
80
81
                || symbol->isObjCForwardClassDeclaration() || symbol->isObjCForwardProtocolDeclaration()
                || symbol->isForwardClassDeclaration()) {
82
83
            addNames(symbol->name(), names);

84
        } else if (symbol->isFunction()) {
85
86
            if (const QualifiedNameId *q = symbol->name()->asQualifiedNameId())
                addNames(q->base(), names);
87
88
89
        } else if (Enum *e = symbol->asEnum()) {
            if (e->isScoped())
                addNames(symbol->name(), names);
90
91
92
93
        }
    }
}

94
static inline bool compareName(const Name *name, const Name *other)
95
96
97
98
{
    if (name == other)
        return true;

99
    if (name && other) {
100
101
102
        const Identifier *id = name->identifier();
        const Identifier *otherId = other->identifier();

103
        if (id == otherId || (id && id->match(otherId)))
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
            return true;
    }

    return false;
}

bool compareFullyQualifiedName(const QList<const Name *> &path, const QList<const Name *> &other)
{
    if (path.length() != other.length())
        return false;

    for (int i = 0; i < path.length(); ++i) {
        if (! compareName(path.at(i), other.at(i)))
            return false;
    }

    return true;
}

123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
namespace Internal {

bool operator==(const FullyQualifiedName &left, const FullyQualifiedName &right)
{
    return compareFullyQualifiedName(left.fqn, right.fqn);
}

uint qHash(const FullyQualifiedName &fullyQualifiedName)
{
    uint h = 0;
    for (int i = 0; i < fullyQualifiedName.fqn.size(); ++i) {
        if (const Name *n = fullyQualifiedName.fqn.at(i)) {
            if (const Identifier *id = n->identifier()) {
                h <<= 1;
                h += id->hashCode();
            }
        }
    }
    return h;
}
}

145
146
147
148
/////////////////////////////////////////////////////////////////////
// LookupContext
/////////////////////////////////////////////////////////////////////
LookupContext::LookupContext()
149
    : m_expandTemplates(false)
150
151
152
153
{ }

LookupContext::LookupContext(Document::Ptr thisDocument,
                             const Snapshot &snapshot)
154
155
156
    : _expressionDocument(Document::create(QLatin1String("<LookupContext>")))
    , _thisDocument(thisDocument)
    , _snapshot(snapshot)
157
    , _bindings(new CreateBindings(thisDocument, snapshot))
158
    , m_expandTemplates(false)
159
160
161
162
163
{
}

LookupContext::LookupContext(Document::Ptr expressionDocument,
                             Document::Ptr thisDocument,
164
                             const Snapshot &snapshot,
165
                             CreateBindings::Ptr bindings)
166
167
168
    : _expressionDocument(expressionDocument)
    , _thisDocument(thisDocument)
    , _snapshot(snapshot)
169
    , _bindings(bindings)
170
    , m_expandTemplates(false)
171
172
173
174
{
}

LookupContext::LookupContext(const LookupContext &other)
175
176
177
178
179
    : _expressionDocument(other._expressionDocument)
    , _thisDocument(other._thisDocument)
    , _snapshot(other._snapshot)
    , _bindings(other._bindings)
    , m_expandTemplates(other.m_expandTemplates)
180
181
{ }

182
LookupContext &LookupContext::operator=(const LookupContext &other)
183
184
185
186
187
{
    _expressionDocument = other._expressionDocument;
    _thisDocument = other._thisDocument;
    _snapshot = other._snapshot;
    _bindings = other._bindings;
188
    m_expandTemplates = other.m_expandTemplates;
189
190
191
    return *this;
}

192
QList<const Name *> LookupContext::fullyQualifiedName(Symbol *symbol)
193
{
194
    QList<const Name *> qualifiedName = path(symbol->enclosingScope());
195
196
197
198
199
    addNames(symbol->name(), &qualifiedName, /*add all names*/ true);
    return qualifiedName;
}

QList<const Name *> LookupContext::path(Symbol *symbol)
200
201
{
    QList<const Name *> names;
202
    path_helper(symbol, &names);
203
204
205
    return names;
}

206
207
208
209
210
211
212
213
214
215
216
static bool symbolIdentical(Symbol *s1, Symbol *s2)
{
    if (!s1 || !s2)
        return false;
    if (s1->line() != s2->line())
        return false;
    if (s1->column() != s2->column())
        return false;

    return QByteArray(s1->fileName()) == QByteArray(s2->fileName());
}
217

218
const Name *LookupContext::minimalName(Symbol *symbol, LookupScope *target, Control *control)
219
{
220
221
222
223
224
225
    const Name *n = 0;
    QList<const Name *> names = LookupContext::fullyQualifiedName(symbol);

    for (int i = names.size() - 1; i >= 0; --i) {
        if (! n)
            n = names.at(i);
226
        else
227
228
229
230
231
232
233
234
235
236
            n = control->qualifiedNameId(names.at(i), n);

        // once we're qualified enough to get the same symbol, break
        if (target) {
            const QList<LookupItem> tresults = target->lookup(n);
            foreach (const LookupItem &tr, tresults) {
                if (symbolIdentical(tr.declaration(), symbol))
                    return n;
            }
        }
237
238
    }

239
    return n;
240
241
}

242
QList<LookupItem> LookupContext::lookupByUsing(const Name *name,
243
                                               LookupScope *bindingScope) const
244
245
246
{
    QList<LookupItem> candidates;
    // if it is a nameId there can be a using declaration for it
247
    if (name->isNameId() || name->isTemplateNameId()) {
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
        foreach (Symbol *s, bindingScope->symbols()) {
            if (Scope *scope = s->asScope()) {
                for (unsigned i = 0, count = scope->memberCount(); i < count; ++i) {
                    if (UsingDeclaration *u = scope->memberAt(i)->asUsingDeclaration()) {
                        if (const Name *usingDeclarationName = u->name()) {
                            if (const QualifiedNameId *q
                                    = usingDeclarationName->asQualifiedNameId()) {
                                if (q->name() && q->identifier() && name->identifier()
                                        && q->name()->identifier()->match(name->identifier())) {
                                    candidates = bindings()->globalNamespace()->find(q);

                                    // if it is not a global scope(scope of scope is not equal 0)
                                    // then add current using declaration as a candidate
                                    if (scope->enclosingScope()) {
                                        LookupItem item;
                                        item.setDeclaration(u);
                                        item.setScope(scope);
                                        candidates.append(item);
                                    }
                                }
268
                            }
269
270
271
272
273
                        }
                    }
                }
            }
        }
274
    } else if (const QualifiedNameId *q = name->asQualifiedNameId()) {
275
276
        foreach (Symbol *s, bindingScope->symbols()) {
            if (Scope *scope = s->asScope()) {
277
                LookupScope *base = lookupType(q->base(), scope);
278
279
280
281
282
283
                if (base)
                    candidates = lookupByUsing(q->name(), base);
                if (!candidates.isEmpty())
                    return candidates;
            }
        }
284
285
286
287
    }
    return candidates;
}

288

289
290
291
292
293
294
295
296
297
298
299
300
Document::Ptr LookupContext::expressionDocument() const
{ return _expressionDocument; }

Document::Ptr LookupContext::thisDocument() const
{ return _thisDocument; }

Document::Ptr LookupContext::document(const QString &fileName) const
{ return _snapshot.document(fileName); }

Snapshot LookupContext::snapshot() const
{ return _snapshot; }

301
LookupScope *LookupContext::globalNamespace() const
302
303
304
305
{
    return bindings()->globalNamespace();
}

306
307
308
LookupScope *LookupContext::lookupType(const Name *name, Scope *scope,
                                       LookupScope *enclosingBinding,
                                       QSet<const Declaration *> typedefsBeingResolved) const
309
{
310
    if (! scope || ! name) {
311
312
313
        return 0;
    } else if (Block *block = scope->asBlock()) {
        for (unsigned i = 0; i < block->memberCount(); ++i) {
314
315
            Symbol *m = block->memberAt(i);
            if (UsingNamespaceDirective *u = m->asUsingNamespaceDirective()) {
316
317
                if (LookupScope *uu = lookupType(u->name(), scope->enclosingNamespace())) {
                    if (LookupScope *r = uu->lookupType(name))
318
319
                        return r;
                }
320
            } else if (Declaration *d = m->asDeclaration()) {
321
                if (d->name() && d->name()->match(name->asNameId())) {
322
                    if (d->isTypedef() && d->type()) {
323
324
325
326
                        if (Q_UNLIKELY(debug)) {
                            Overview oo;
                            qDebug() << "Looks like" << oo(name) << "is a typedef for" << oo(d->type());
                        }
327
328
329
330
331
332
333
334
                        if (const NamedType *namedTy = d->type()->asNamedType()) {
                            // Stop on recursive typedef declarations
                            if (typedefsBeingResolved.contains(d))
                                return 0;
                            return lookupType(namedTy->name(), scope, 0,
                                              QSet<const Declaration *>(typedefsBeingResolved)
                                                << d);
                        }
335
336
                    }
                }
337
338
            } else if (UsingDeclaration *ud = m->asUsingDeclaration()) {
                if (name->isNameId()) {
339
340
                    if (const Name *usingDeclarationName = ud->name()) {
                        if (const QualifiedNameId *q = usingDeclarationName->asQualifiedNameId()) {
341
                            if (q->name() && q->name()->match(name))
342
                                return bindings()->globalNamespace()->lookupType(q);
343
344
345
                        }
                    }
                }
346
347
            }
        }
348
349
        // try to find it in block (rare case but has priority before enclosing scope)
        // e.g.: void foo() { struct S {};  S s; }
350
351
352
        if (LookupScope *b = bindings()->lookupType(scope, enclosingBinding)) {
            if (LookupScope *lookupScopeNestedInNestedBlock = b->lookupType(name, block))
                return lookupScopeNestedInNestedBlock;
353
354
355
        }

        // try to find type in enclosing scope(typical case)
356
        if (LookupScope *found = lookupType(name, scope->enclosingScope()))
357
358
            return found;

359
    } else if (LookupScope *b = bindings()->lookupType(scope, enclosingBinding)) {
360
        return b->lookupType(name);
361
362
    } else if (Class *scopeAsClass = scope->asClass()) {
        if (scopeAsClass->enclosingScope()->isBlock()) {
363
            if (LookupScope *b = lookupType(scopeAsClass->name(),
364
                                                 scopeAsClass->enclosingScope(),
365
                                                 enclosingBinding,
366
367
368
369
                                                 typedefsBeingResolved)) {
                return b->lookupType(name);
            }
        }
370
    }
371
372
373
374

    return 0;
}

375
LookupScope *LookupContext::lookupType(Symbol *symbol, LookupScope *enclosingBinding) const
376
{
377
    return bindings()->lookupType(symbol, enclosingBinding);
378
379
}

380
QList<LookupItem> LookupContext::lookup(const Name *name, Scope *scope) const
381
{
382
    QList<LookupItem> candidates;
383
384
385
386

    if (! name)
        return candidates;

387
    for (; scope; scope = scope->enclosingScope()) {
388
        if (name->identifier() != 0 && scope->isBlock()) {
389
            bindings()->lookupInScope(name, scope, &candidates);
390

391
392
393
394
395
396
397
398
            if (! candidates.isEmpty()) {
                // it's a local.
                //for qualified it can be outside of the local scope
                if (name->isQualifiedNameId())
                    continue;
                else
                    break;
            }
399

400
401
            for (unsigned i = 0; i < scope->memberCount(); ++i) {
                if (UsingNamespaceDirective *u = scope->memberAt(i)->asUsingNamespaceDirective()) {
402
                    if (LookupScope *uu = lookupType(u->name(), scope->enclosingNamespace())) {
403
                        candidates = uu->find(name);
404

405
406
                        if (! candidates.isEmpty())
                            return candidates;
407
408
409
410
                    }
                }
            }

411
412
            if (LookupScope *bindingScope = bindings()->lookupType(scope)) {
                if (LookupScope *bindingBlock = bindingScope->findBlock(scope->asBlock())) {
413
414
415
                    candidates = lookupByUsing(name, bindingBlock);
                    if (! candidates.isEmpty())
                        return candidates;
416

417
                    candidates = bindingBlock->find(name);
418
419
420
421
422
423

                    if (! candidates.isEmpty())
                        return candidates;
                }
            }

Roberto Raggi's avatar
Roberto Raggi committed
424
        } else if (Function *fun = scope->asFunction()) {
425
            bindings()->lookupInScope(name, fun, &candidates);
426

427
428
429
430
431
432
433
434
            if (! candidates.isEmpty()) {
                // it's an argument or a template parameter.
                //for qualified it can be outside of the local scope
                if (name->isQualifiedNameId())
                    continue;
                else
                    break;
            }
435
436

            if (fun->name() && fun->name()->isQualifiedNameId()) {
437
                if (LookupScope *binding = bindings()->lookupType(fun)) {
Roberto Raggi's avatar
Roberto Raggi committed
438
                    candidates = binding->find(name);
439

440
441
442
443
                    // try find this name in parent class
                    while (candidates.isEmpty() && (binding = binding->parent()))
                        candidates = binding->find(name);

444
445
446
                    if (! candidates.isEmpty())
                        return candidates;
                }
447
448
            }

449
            // continue, and look at the enclosing scope.
450

Roberto Raggi's avatar
Roberto Raggi committed
451
        } else if (ObjCMethod *method = scope->asObjCMethod()) {
452
            bindings()->lookupInScope(name, method, &candidates);
453

454
455
456
            if (! candidates.isEmpty())
                break; // it's a formal argument.

457
        } else if (Template *templ = scope->asTemplate()) {
458
            bindings()->lookupInScope(name, templ, &candidates);
459

460
461
462
463
464
465
466
467
            if (! candidates.isEmpty()) {
                // it's a template parameter.
                //for qualified it can be outside of the local scope
                if (name->isQualifiedNameId())
                    continue;
                else
                    break;
            }
468

469
470
471
        } else if (scope->asNamespace()
                   || scope->asClass()
                   || (scope->asEnum() && scope->asEnum()->isScoped())) {
472

473
            if (LookupScope *bindingScope = bindings()->lookupType(scope)) {
474
                candidates = bindingScope->find(name);
475

476
477
478
479
480
481
482
                if (! candidates.isEmpty())
                    return candidates;

                candidates = lookupByUsing(name, bindingScope);
                if (!candidates.isEmpty())
                    return candidates;
            }
Roberto Raggi's avatar
Roberto Raggi committed
483

484
485
            // the scope can be defined inside a block, try to find it
            if (Block *block = scope->enclosingBlock()) {
486
487
488
                if (LookupScope *b = bindings()->lookupType(block)) {
                    if (LookupScope *lookupScopeNestedInNestedBlock = b->lookupType(scope->name(), block))
                        candidates = lookupScopeNestedInNestedBlock->find(name);
489
490
491
492
493
494
                }
            }

            if (! candidates.isEmpty())
                return candidates;

Roberto Raggi's avatar
Roberto Raggi committed
495
        } else if (scope->isObjCClass() || scope->isObjCProtocol()) {
496
            if (LookupScope *binding = bindings()->lookupType(scope))
Roberto Raggi's avatar
Roberto Raggi committed
497
498
499
500
                candidates = binding->find(name);

                if (! candidates.isEmpty())
                    return candidates;
501
502
503
504
505
506
        }
    }

    return candidates;
}

507
LookupScope *LookupContext::lookupParent(Symbol *symbol) const
508
{
509
    QList<const Name *> fqName = path(symbol);
510
    LookupScope *binding = globalNamespace();
511
512
513
514
515
516
517
518
519
    foreach (const Name *name, fqName) {
        binding = binding->findType(name);
        if (!binding)
            return 0;
    }

    return binding;
}

Orgad Shaneh's avatar
Orgad Shaneh committed
520
521
namespace Internal {

522
class LookupScopePrivate
Orgad Shaneh's avatar
Orgad Shaneh committed
523
524
{
public:
525
526
    LookupScopePrivate(LookupScope *q, CreateBindings *factory, LookupScope *parent);
    ~LookupScopePrivate();
Orgad Shaneh's avatar
Orgad Shaneh committed
527

528
    typedef std::map<const Name *, LookupScopePrivate *, Name::Compare> Table;
529
    typedef std::map<const Name *, Declaration *, Name::Compare> TypedefTable;
Orgad Shaneh's avatar
Orgad Shaneh committed
530
    typedef std::map<const TemplateNameId *,
531
                     LookupScopePrivate *,
Orgad Shaneh's avatar
Orgad Shaneh committed
532
                     TemplateNameId::Compare> TemplateNameIdTable;
533
    typedef QHash<const AnonymousNameId *, LookupScopePrivate *> Anonymouses;
Orgad Shaneh's avatar
Orgad Shaneh committed
534

535
    LookupScopePrivate *allocateChild(const Name *name);
Orgad Shaneh's avatar
Orgad Shaneh committed
536
537
538

    void flush();

539
    LookupScope *globalNamespace() const;
Orgad Shaneh's avatar
Orgad Shaneh committed
540
541
542

    Symbol *lookupInScope(const QList<const Name *> &fullName);

543
    LookupScope *findOrCreateType(const Name *name, LookupScopePrivate *origin = 0,
Orgad Shaneh's avatar
Orgad Shaneh committed
544
545
                                       Class *clazz = 0);

546
    LookupScopePrivate *findOrCreateNestedAnonymousType(const AnonymousNameId *anonymousNameId);
Orgad Shaneh's avatar
Orgad Shaneh committed
547
548
549
550

    void addTodo(Symbol *symbol);
    void addSymbol(Symbol *symbol);
    void addUnscopedEnum(Enum *e);
551
    void addTypedef(const Name *identifier, Declaration *d);
552
553
    void addUsing(LookupScope *u);
    void addNestedType(const Name *alias, LookupScope *e);
Orgad Shaneh's avatar
Orgad Shaneh committed
554
555
556

    QList<LookupItem> lookup_helper(const Name *name, bool searchInEnclosingScope);

557
    void lookup_helper(const Name *name, LookupScopePrivate *binding,
Orgad Shaneh's avatar
Orgad Shaneh committed
558
559
560
                       QList<LookupItem> *result,
                       ProcessedSet *processed);

561
562
    LookupScope *lookupType_helper(const Name *name, ProcessedSet *processed,
                                   bool searchInEnclosingScope, LookupScopePrivate *origin);
Orgad Shaneh's avatar
Orgad Shaneh committed
563

564
565
    LookupScope *findBlock_helper(Block *block, ProcessedSet *processed,
                                  bool searchInEnclosingScope);
Orgad Shaneh's avatar
Orgad Shaneh committed
566

567
568
569
private:
    LookupScopePrivate *findNestedType(const Name *name, LookupScopePrivate *origin);

570
    LookupScopePrivate *nestedType(const Name *name, LookupScopePrivate *origin);
Orgad Shaneh's avatar
Orgad Shaneh committed
571

572
    LookupScopePrivate *findSpecialization(const Template *baseTemplate, const TemplateNameId *templId,
573
574
                                           const TemplateNameIdTable &specializations,
                                           LookupScopePrivate *origin);
Orgad Shaneh's avatar
Orgad Shaneh committed
575

576
public:
577
    LookupScope *q;
Orgad Shaneh's avatar
Orgad Shaneh committed
578
579

    CreateBindings *_factory;
580
    LookupScopePrivate *_parent;
Orgad Shaneh's avatar
Orgad Shaneh committed
581
    QList<Symbol *> _symbols;
582
583
    QList<LookupScope *> _usings;
    Table _nestedScopes;
584
    TypedefTable _typedefs;
585
    QHash<Block *, LookupScope *> _blocks;
Orgad Shaneh's avatar
Orgad Shaneh committed
586
587
588
589
    QList<Enum *> _enums;
    QList<Symbol *> _todo;
    QSharedPointer<Control> _control;
    TemplateNameIdTable _specializations;
590
    QMap<const TemplateNameId *, LookupScopePrivate *> _instantiations;
Orgad Shaneh's avatar
Orgad Shaneh committed
591
592
593
594
595
596
    Anonymouses _anonymouses;
    QSet<const AnonymousNameId *> _declaredOrTypedefedAnonymouses;

    QHash<Internal::FullyQualifiedName, Symbol *> *_scopeLookupCache;

    // it's an instantiation.
597
    LookupScopePrivate *_instantiationOrigin;
Orgad Shaneh's avatar
Orgad Shaneh committed
598
599
600

    AlreadyConsideredClassContainer<Class> _alreadyConsideredClasses;
    AlreadyConsideredClassContainer<TemplateNameId> _alreadyConsideredTemplates;
601
    QSet<const Declaration *> _alreadyConsideredTypedefs;
Orgad Shaneh's avatar
Orgad Shaneh committed
602
603

    Class *_rootClass;
604
    const Name *_name;
605
    bool _hasTypedefs;
Orgad Shaneh's avatar
Orgad Shaneh committed
606
607
608
};

class Instantiator
609
610
{
public:
Nikolai Kosjar's avatar
Nikolai Kosjar committed
611
612
    Instantiator(Clone &cloner, Subst &subst)
        : _cloner(cloner)
613
614
        , _subst(subst)
    {}
615
616
617
618
    void instantiate(LookupScopePrivate *lookupScope,
                                LookupScopePrivate *instantiation,
                                bool includeSymbols);
    LookupScopePrivate *maybeInstantiate(LookupScopePrivate *lookupScope);
619
private:
620
    bool isInstantiationNeeded(LookupScopePrivate *lookupScope) const;
621
622
623
624
625
626
627
628
629
630
631

    struct TemplateFinder : public TypeVisitor, public NameVisitor
    {
    public:
        TemplateFinder(Subst &subst) : _subst(subst), _found(false) {}

        inline void accept(Type *type) { TypeVisitor::accept(type); }
        inline void accept(const Name *name) { NameVisitor::accept(name); }

        bool found() const { return _found; }
    private:
632
633
634
        using TypeVisitor::visit;
        using NameVisitor::visit;

635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
        void visit(PointerType *type) override { accept(type->elementType().type()); }
        void visit(ReferenceType *type) override { accept(type->elementType().type()); }
        void visit(NamedType *type) override { accept(type->name()); }

        void visit(Function *type) override
        {
            accept(type->returnType().type());
            if (_found)
                return;
            for (int i = 0, total = type->argumentCount(); i < total; ++i) {
                accept(type->argumentAt(i)->type().type());
                if (_found)
                    return;
            }
        }

        void visit(Class *type) override
        {
            for (int i = 0, total = type->memberCount(); i < total; ++i) {
                accept(type->memberAt(i)->type().type());
                if (_found)
                    return;
            }
        }

        void visit(const Identifier *name) override
        {
            if (_subst.contains(name))
                _found = true;
        }

        void visit(const TemplateNameId *name) override
        {
            if (const Identifier *identifier = name->identifier())
                visit(identifier);
            if (_found)
                return;
            for (unsigned i = 0, total = name->templateArgumentCount(); i < total; ++i) {
                accept(name->templateArgumentAt(i).type());
                if (_found)
                    return;
            }
        }

        void visit(const ConversionNameId *name) override
        {
            accept(name->type().type());
        }

        void visit(const QualifiedNameId *name) override
        {
            accept(name->base());
            if (!_found)
                accept(name->name());
        }

        Subst &_subst;
        bool _found;
    };
694

Orgad Shaneh's avatar
Orgad Shaneh committed
695
    ProcessedSet _alreadyConsideredInstantiations;
696
697
698
699
    Clone &_cloner;
    Subst &_subst;
};

700
701
static bool isNestedInstantiationEnclosingTemplate(LookupScopePrivate *nestedInstantiation,
                                                   LookupScopePrivate *enclosingInstantiation)
Orgad Shaneh's avatar
Orgad Shaneh committed
702
703
704
705
706
707
708
709
710
711
712
713
{
    ProcessedSet processed;
    while (enclosingInstantiation && !processed.contains(enclosingInstantiation)) {
        processed.insert(enclosingInstantiation);
        if (enclosingInstantiation == nestedInstantiation)
            return false;
        enclosingInstantiation = enclosingInstantiation->_parent;
    }

    return true;
}

714
LookupScopePrivate::LookupScopePrivate(LookupScope *q, CreateBindings *factory, LookupScope *parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
715
716
717
    : q(q)
    , _factory(factory)
    , _parent(parent ? parent->d : 0)
718
719
    , _scopeLookupCache(0)
    , _instantiationOrigin(0)
720
    , _rootClass(0)
721
    , _name(0)
722
    , _hasTypedefs(false)
723
{
724
    Q_ASSERT(factory);
725
726
}

727
LookupScopePrivate::~LookupScopePrivate()
728
729
730
731
{
    delete _scopeLookupCache;
}

732
LookupScopePrivate *LookupScopePrivate::allocateChild(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
733
{
734
    LookupScope *e = _factory->allocLookupScope(q, name);
Orgad Shaneh's avatar
Orgad Shaneh committed
735
736
737
738
739
    return e->d;
}

} // namespace Internal

740
741
LookupScope::LookupScope(CreateBindings *factory, LookupScope *parent)
    : d(new Internal::LookupScopePrivate(this, factory, parent))
Orgad Shaneh's avatar
Orgad Shaneh committed
742
743
744
{
}

745
LookupScope::~LookupScope()
Orgad Shaneh's avatar
Orgad Shaneh committed
746
747
748
749
{
    delete d;
}

750
LookupScope *LookupScope::instantiationOrigin() const
751
{
752
    if (Internal::LookupScopePrivate *i = d->_instantiationOrigin)
Orgad Shaneh's avatar
Orgad Shaneh committed
753
754
        return i->q;
    return 0;
755
756
}

757
LookupScope *LookupScope::parent() const
758
{
759
    if (Internal::LookupScopePrivate *p = d->_parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
760
761
        return p->q;
    return 0;
762
763
}

764
QList<LookupScope *> LookupScope::usings() const
765
{
766
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
767
    return d->_usings;
768
769
}

770
QList<Enum *> LookupScope::unscopedEnums() const
771
{
772
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
773
    return d->_enums;
774
775
}

776
QList<Symbol *> LookupScope::symbols() const
777
{
778
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
779
780
781
    return d->_symbols;
}

782
QList<LookupItem> LookupScope::find(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
783
784
785
786
{
    return d->lookup_helper(name, false);
}

787
QList<LookupItem> LookupScope::lookup(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
788
789
{
    return d->lookup_helper(name, true);
790
791
}

Orgad Shaneh's avatar
Orgad Shaneh committed
792
793
namespace Internal {

794
LookupScope *LookupScopePrivate::globalNamespace() const
795
{
796
    const LookupScopePrivate *e = this;
797
798
799
800
801
802
803
804

    do {
        if (! e->_parent)
            break;

        e = e->_parent;
    } while (e);

Orgad Shaneh's avatar
Orgad Shaneh committed
805
    return e ? e->q : 0;
806
807
}

808
QList<LookupItem> LookupScopePrivate::lookup_helper(const Name *name, bool searchInEnclosingScope)
809
{
810
    QList<LookupItem> result;
811

812
    if (name) {
813

Orgad Shaneh's avatar
Orgad Shaneh committed
814
815
816
        if (const QualifiedNameId *qName = name->asQualifiedNameId()) {
            if (! qName->base()) { // e.g. ::std::string
                result = globalNamespace()->find(qName->name());
817
            } else if (LookupScope *binding = q->lookupType(qName->base())) {
Orgad Shaneh's avatar
Orgad Shaneh committed
818
                result = binding->find(qName->name());
819

820
821
822
823
824
825
826
                QList<const Name *> fullName;
                addNames(name, &fullName);

                // It's also possible that there are matches in the parent binding through
                // a qualified name. For instance, a nested class which is forward declared
                // in the class but defined outside it - we should capture both.
                Symbol *match = 0;
Orgad Shaneh's avatar
Orgad Shaneh committed
827
                ProcessedSet processed;
828
                for (LookupScopePrivate *parentBinding = binding->d->_parent;
829
                        parentBinding && !match;
Orgad Shaneh's avatar
Orgad Shaneh committed
830
                        parentBinding = parentBinding->_parent) {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
831
832
833
                    if (processed.contains(parentBinding))
                        break;
                    processed.insert(parentBinding);
834
                    match = parentBinding->lookupInScope(fullName);
Nikolai Kosjar's avatar
Nikolai Kosjar committed
835
                }
836
837
838
839
840
841
842
843

                if (match) {
                    LookupItem item;
                    item.setDeclaration(match);
                    item.setBinding(binding);
                    result.append(item);
                }
            }
844

845
846
            return result;
        }
847

Orgad Shaneh's avatar
Orgad Shaneh committed
848
849
        ProcessedSet processed;
        ProcessedSet processedOwnParents;
850
        LookupScopePrivate *binding = this;
851
        do {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
852
853
854
            if (processedOwnParents.contains(binding))
                break;
            processedOwnParents.insert(binding);
855
            lookup_helper(name, binding, &result, &processed);
856
857
858
            binding = binding->_parent;
        } while (searchInEnclosingScope && binding);
    }
859
860
861
862

    return result;
}

863
864
void LookupScopePrivate::lookup_helper(
        const Name *name, LookupScopePrivate *binding, QList<LookupItem> *result,
Orgad Shaneh's avatar
Orgad Shaneh committed
865
        ProcessedSet *processed)
866
{
Orgad Shaneh's avatar
Orgad Shaneh committed
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
    if (!binding || processed->contains(binding))
        return;
    processed->insert(binding);

    binding->flush();
    const Identifier *nameId = name->identifier();

    foreach (Symbol *s, binding->_symbols) {
        if (s->isFriend())
            continue;
        else if (s->isUsingNamespaceDirective())
            continue;


        if (Scope *scope = s->asScope()) {
            if (Class *klass = scope->asClass()) {
                if (const Identifier *id = klass->identifier()) {
                    if (nameId && nameId->match(id)) {
                        LookupItem item;
                        item.setDeclaration(klass);
                        item.setBinding(binding->q);
                        result->append(item);
889
890
891
                    }
                }
            }
Orgad Shaneh's avatar
Orgad Shaneh committed
892
            _factory->lookupInScope(name, scope, result, binding->q);
893
        }
Orgad Shaneh's avatar
Orgad Shaneh committed
894
    }
895

Orgad Shaneh's avatar
Orgad Shaneh committed
896
897
    foreach (Enum *e, binding->_enums)
        _factory->lookupInScope(name, e, result, binding->q);
898

899
    foreach (LookupScope *u, binding->_usings)
Orgad Shaneh's avatar
Orgad Shaneh committed
900
        lookup_helper(name, u->d, result, processed);
901

Orgad Shaneh's avatar
Orgad Shaneh committed
902
903
904
905
    Anonymouses::const_iterator cit = binding->_anonymouses.constBegin();
    Anonymouses::const_iterator citEnd = binding->_anonymouses.constEnd();
    for (; cit != citEnd; ++cit) {
        const AnonymousNameId *anonymousNameId = cit.key();
906
        LookupScopePrivate *a = cit.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
907
908
        if (!binding->_declaredOrTypedefedAnonymouses.contains(anonymousNameId))
            lookup_helper(name, a, result, processed);
909
910
911
    }
}

Orgad Shaneh's avatar
Orgad Shaneh committed
912
913
}

Roberto Raggi's avatar
Roberto Raggi committed
914
void CreateBindings::lookupInScope(const Name *name, Scope *scope,
915
                                   QList<LookupItem> *result,
916
                                   LookupScope *binding)
917
918
919
920
921
{
    if (! name) {
        return;

    } else if (const OperatorNameId *op = name->asOperatorNameId()) {
Roberto Raggi's avatar
Roberto Raggi committed
922
        for (Symbol *s = scope->find(op->kind()); s; s = s->next()) {
923
924
            if (! s->name())
                continue;
925
926
            else if (s->isFriend())
                continue;
927
            else if (! s->name()->match(op))
928
                continue;
929

930
931
932
933
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
            result->append(item);
934
935
936
        }

    } else if (const Identifier *id = name->identifier()) {
Roberto Raggi's avatar
Roberto Raggi committed
937
        for (Symbol *s = scope->find(id); s; s = s->next()) {
938
939
            if (s->isFriend())
                continue; // skip friends
940
941
            else if (s->isUsingNamespaceDirective())
                continue; // skip using namespace directives
942
            else if (! id->match(s->identifier()))
943
                continue;
944
            else if (s->name() && s->name()->isQualifiedNameId())
Roberto Raggi's avatar
Roberto Raggi committed
945
                continue; // skip qualified ids.
946

947
948
949
            if (Q_UNLIKELY(debug)) {
                Overview oo;
                qDebug() << "Found" << id->chars() << "in"
Orgad Shaneh's avatar
Orgad Shaneh committed
950
                         << (binding ? oo(binding->d->_name) : QString::fromLatin1("<null>"));
951
            }
952

953
954
955
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
956

957
            if (s->asNamespaceAlias() && binding) {
958
                LookupScope *targetNamespaceBinding = binding->lookupType(name);
959
960
                //there can be many namespace definitions
                if (targetNamespaceBinding && targetNamespaceBinding->symbols().size() > 0) {
961
962
963
964
965
                    Symbol *resolvedSymbol = targetNamespaceBinding->symbols().first();
                    item.setType(resolvedSymbol->type()); // override the type
                }
            }

966
            // instantiate function template
Orgad Shaneh's avatar
Orgad Shaneh committed
967
968
969
            if (const TemplateNameId *instantiation = name->asTemplateNameId()) {
                if (Template *specialization = s->asTemplate()) {
                    if (const Symbol *decl = specialization->declaration()) {
970
                        if (decl->isFunction() || decl->isDeclaration()) {
971
972
                            Clone cloner(_control.data());
                            Subst subst(_control.data());
973
                            initializeSubst(cloner, subst, binding, specialization, instantiation);
Orgad Shaneh's avatar
Orgad Shaneh committed
974
                            Symbol *instantiatedFunctionTemplate =
975
                                    cloner.symbol(specialization->declaration(), &subst);
Orgad Shaneh's avatar
Orgad Shaneh committed
976
977
978
979
                            item.setType(instantiatedFunctionTemplate->type()); // override the type
                        }
                    }
                }
980
981
            }

982
            result->append(item);
983
984
985
986
        }
    }
}

987
LookupScope *LookupScope::lookupType(const Name *name)
988
989
990
991
{
    if (! name)
        return 0;

Orgad Shaneh's avatar
Orgad Shaneh committed
992
993
    ProcessedSet processed;
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ true, d);