LookupContext.cpp 71.8 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
165
                             const Snapshot &snapshot,
                             QSharedPointer<CreateBindings> 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 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
    void instantiate(LookupScopePrivate *lookupScope, LookupScopePrivate *instantiation);
616
private:
617
    bool isInstantiationNeeded(LookupScopePrivate *lookupScope) const;
618
619
620
621
622
623
624
625
626
627
628

    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:
629
630
631
        using TypeVisitor::visit;
        using NameVisitor::visit;

632
633
634
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
        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;
    };
691

Orgad Shaneh's avatar
Orgad Shaneh committed
692
    ProcessedSet _alreadyConsideredInstantiations;
693
694
695
696
    Clone &_cloner;
    Subst &_subst;
};

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

    return true;
}

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

724
LookupScopePrivate::~LookupScopePrivate()
725
726
727
728
{
    delete _scopeLookupCache;
}

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

} // namespace Internal

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

742
LookupScope::~LookupScope()
Orgad Shaneh's avatar
Orgad Shaneh committed
743
744
745
746
{
    delete d;
}

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

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

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

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

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

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

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

Orgad Shaneh's avatar
Orgad Shaneh committed
789
790
namespace Internal {

791
LookupScope *LookupScopePrivate::globalNamespace() const
792
{
793
    const LookupScopePrivate *e = this;
794
795
796
797
798
799
800
801

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

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

Orgad Shaneh's avatar
Orgad Shaneh committed
802
    return e ? e->q : 0;
803
804
}

805
QList<LookupItem> LookupScopePrivate::lookup_helper(const Name *name, bool searchInEnclosingScope)
806
{
807
    QList<LookupItem> result;
808

809
    if (name) {
810

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

817
818
819
820
821
822
823
                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
824
                ProcessedSet processed;
825
                for (LookupScopePrivate *parentBinding = binding->d->_parent;
826
                        parentBinding && !match;
Orgad Shaneh's avatar
Orgad Shaneh committed
827
                        parentBinding = parentBinding->_parent) {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
828
829
830
                    if (processed.contains(parentBinding))
                        break;
                    processed.insert(parentBinding);
831
                    match = parentBinding->lookupInScope(fullName);
Nikolai Kosjar's avatar
Nikolai Kosjar committed
832
                }
833
834
835
836
837
838
839
840

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

842
843
            return result;
        }
844

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

    return result;
}

860
861
void LookupScopePrivate::lookup_helper(
        const Name *name, LookupScopePrivate *binding, QList<LookupItem> *result,
Orgad Shaneh's avatar
Orgad Shaneh committed
862
        ProcessedSet *processed)
863
{
Orgad Shaneh's avatar
Orgad Shaneh committed
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
    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);
886
887
888
                    }
                }
            }
Orgad Shaneh's avatar
Orgad Shaneh committed
889
            _factory->lookupInScope(name, scope, result, binding->q);
890
        }
Orgad Shaneh's avatar
Orgad Shaneh committed
891
    }
892

Orgad Shaneh's avatar
Orgad Shaneh committed
893
894
    foreach (Enum *e, binding->_enums)
        _factory->lookupInScope(name, e, result, binding->q);
895

896
    foreach (LookupScope *u, binding->_usings)
Orgad Shaneh's avatar
Orgad Shaneh committed
897
        lookup_helper(name, u->d, result, processed);
898

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

Orgad Shaneh's avatar
Orgad Shaneh committed
909
910
}

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

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

927
928
929
930
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
            result->append(item);
931
932
933
        }

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

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

950
951
952
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
953

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

963
964
965
966
967
968
969
970
971
972
            // instantiate function template
            if (name->isTemplateNameId() && s->isTemplate() && s->asTemplate()->declaration()
                    && s->asTemplate()->declaration()->isFunction()) {
                const TemplateNameId *instantiation = name->asTemplateNameId();
                Template *specialization = s->asTemplate();
                Symbol *instantiatedFunctionTemplate = instantiateTemplateFunction(instantiation,
                                                                                   specialization);
                item.setType(instantiatedFunctionTemplate->type()); // override the type.
            }

973
            result->append(item);
974
975
976
977
        }
    }
}

978
LookupScope *LookupScope::lookupType(const Name *name)
979
980
981
982
{
    if (! name)
        return 0;

Orgad Shaneh's avatar
Orgad Shaneh committed
983
984
    ProcessedSet processed;
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ true, d);
985
986
}

987
LookupScope *LookupScope::lookupType(const Name *name, Block *block)
988
{
Orgad Shaneh's avatar
Orgad Shaneh committed
989
    d->flush();
990

991
    QHash<Block *, LookupScope *>::const_iterator citBlock = d->_blocks.constFind(block);
Orgad Shaneh's avatar
Orgad Shaneh committed
992
    if (citBlock != d->_blocks.constEnd()) {
993
        LookupScope *nestedBlock = citBlock.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
994
        ProcessedSet processed;