LookupContext.cpp 69.1 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)
    {}
Orgad Shaneh's avatar
Orgad Shaneh committed
615
616
    void doInstantiate(LookupScopePrivate *lookupScope, LookupScopePrivate *instantiation);
    LookupScopePrivate *instantiate(LookupScopePrivate *lookupScope, LookupScopePrivate *origin);
617

Orgad Shaneh's avatar
Orgad Shaneh committed
618
private:
Orgad Shaneh's avatar
Orgad Shaneh committed
619
    ProcessedSet _alreadyConsideredInstantiations;
620
621
622
623
    Clone &_cloner;
    Subst &_subst;
};

624
LookupScopePrivate::LookupScopePrivate(LookupScope *q, CreateBindings *factory, LookupScope *parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
625
626
627
    : q(q)
    , _factory(factory)
    , _parent(parent ? parent->d : 0)
628
629
    , _scopeLookupCache(0)
    , _instantiationOrigin(0)
630
    , _rootClass(0)
631
    , _name(0)
632
    , _hasTypedefs(false)
633
{
634
    Q_ASSERT(factory);
635
636
}

637
LookupScopePrivate::~LookupScopePrivate()
638
639
640
641
{
    delete _scopeLookupCache;
}

642
LookupScopePrivate *LookupScopePrivate::allocateChild(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
643
{
644
    LookupScope *e = _factory->allocLookupScope(q, name);
Orgad Shaneh's avatar
Orgad Shaneh committed
645
646
647
648
649
    return e->d;
}

} // namespace Internal

650
651
LookupScope::LookupScope(CreateBindings *factory, LookupScope *parent)
    : d(new Internal::LookupScopePrivate(this, factory, parent))
Orgad Shaneh's avatar
Orgad Shaneh committed
652
653
654
{
}

655
LookupScope::~LookupScope()
Orgad Shaneh's avatar
Orgad Shaneh committed
656
657
658
659
{
    delete d;
}

660
LookupScope *LookupScope::instantiationOrigin() const
661
{
662
    if (Internal::LookupScopePrivate *i = d->_instantiationOrigin)
Orgad Shaneh's avatar
Orgad Shaneh committed
663
664
        return i->q;
    return 0;
665
666
}

667
LookupScope *LookupScope::parent() const
668
{
669
    if (Internal::LookupScopePrivate *p = d->_parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
670
671
        return p->q;
    return 0;
672
673
}

674
QList<LookupScope *> LookupScope::usings() const
675
{
676
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
677
    return d->_usings;
678
679
}

680
QList<Enum *> LookupScope::unscopedEnums() const
681
{
682
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
683
    return d->_enums;
684
685
}

686
QList<Symbol *> LookupScope::symbols() const
687
{
688
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
689
690
691
    return d->_symbols;
}

692
QList<LookupItem> LookupScope::find(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
693
694
695
696
{
    return d->lookup_helper(name, false);
}

697
QList<LookupItem> LookupScope::lookup(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
698
699
{
    return d->lookup_helper(name, true);
700
701
}

Orgad Shaneh's avatar
Orgad Shaneh committed
702
703
namespace Internal {

704
LookupScope *LookupScopePrivate::globalNamespace() const
705
{
706
    const LookupScopePrivate *e = this;
707
708
709
710
711
712
713
714

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

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

Orgad Shaneh's avatar
Orgad Shaneh committed
715
    return e ? e->q : 0;
716
717
}

718
QList<LookupItem> LookupScopePrivate::lookup_helper(const Name *name, bool searchInEnclosingScope)
719
{
720
    QList<LookupItem> result;
721

722
    if (name) {
723

Orgad Shaneh's avatar
Orgad Shaneh committed
724
725
726
        if (const QualifiedNameId *qName = name->asQualifiedNameId()) {
            if (! qName->base()) { // e.g. ::std::string
                result = globalNamespace()->find(qName->name());
727
            } else if (LookupScope *binding = q->lookupType(qName->base())) {
Orgad Shaneh's avatar
Orgad Shaneh committed
728
                result = binding->find(qName->name());
729

730
731
732
733
734
735
736
                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
737
                ProcessedSet processed;
738
                for (LookupScopePrivate *parentBinding = binding->d->_parent;
739
                        parentBinding && !match;
Orgad Shaneh's avatar
Orgad Shaneh committed
740
                        parentBinding = parentBinding->_parent) {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
741
742
743
                    if (processed.contains(parentBinding))
                        break;
                    processed.insert(parentBinding);
744
                    match = parentBinding->lookupInScope(fullName);
Nikolai Kosjar's avatar
Nikolai Kosjar committed
745
                }
746
747
748
749
750
751
752
753

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

755
756
            return result;
        }
757

Orgad Shaneh's avatar
Orgad Shaneh committed
758
759
        ProcessedSet processed;
        ProcessedSet processedOwnParents;
760
        LookupScopePrivate *binding = this;
761
        do {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
762
763
764
            if (processedOwnParents.contains(binding))
                break;
            processedOwnParents.insert(binding);
765
            lookup_helper(name, binding, &result, &processed);
766
767
768
            binding = binding->_parent;
        } while (searchInEnclosingScope && binding);
    }
769
770
771
772

    return result;
}

773
774
void LookupScopePrivate::lookup_helper(
        const Name *name, LookupScopePrivate *binding, QList<LookupItem> *result,
Orgad Shaneh's avatar
Orgad Shaneh committed
775
        ProcessedSet *processed)
776
{
Orgad Shaneh's avatar
Orgad Shaneh committed
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
    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);
799
800
801
                    }
                }
            }
Orgad Shaneh's avatar
Orgad Shaneh committed
802
            _factory->lookupInScope(name, scope, result, binding->q);
803
        }
Orgad Shaneh's avatar
Orgad Shaneh committed
804
    }
805

Orgad Shaneh's avatar
Orgad Shaneh committed
806
807
    foreach (Enum *e, binding->_enums)
        _factory->lookupInScope(name, e, result, binding->q);
808

809
    foreach (LookupScope *u, binding->_usings)
Orgad Shaneh's avatar
Orgad Shaneh committed
810
        lookup_helper(name, u->d, result, processed);
811

Orgad Shaneh's avatar
Orgad Shaneh committed
812
813
814
815
    Anonymouses::const_iterator cit = binding->_anonymouses.constBegin();
    Anonymouses::const_iterator citEnd = binding->_anonymouses.constEnd();
    for (; cit != citEnd; ++cit) {
        const AnonymousNameId *anonymousNameId = cit.key();
816
        LookupScopePrivate *a = cit.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
817
818
        if (!binding->_declaredOrTypedefedAnonymouses.contains(anonymousNameId))
            lookup_helper(name, a, result, processed);
819
820
821
    }
}

Orgad Shaneh's avatar
Orgad Shaneh committed
822
823
}

Roberto Raggi's avatar
Roberto Raggi committed
824
void CreateBindings::lookupInScope(const Name *name, Scope *scope,
825
                                   QList<LookupItem> *result,
826
                                   LookupScope *binding)
827
828
829
830
831
{
    if (! name) {
        return;

    } else if (const OperatorNameId *op = name->asOperatorNameId()) {
Roberto Raggi's avatar
Roberto Raggi committed
832
        for (Symbol *s = scope->find(op->kind()); s; s = s->next()) {
833
834
            if (! s->name())
                continue;
835
836
            else if (s->isFriend())
                continue;
837
            else if (! s->name()->match(op))
838
                continue;
839

840
841
842
843
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
            result->append(item);
844
845
846
        }

    } else if (const Identifier *id = name->identifier()) {
Roberto Raggi's avatar
Roberto Raggi committed
847
        for (Symbol *s = scope->find(id); s; s = s->next()) {
848
849
            if (s->isFriend())
                continue; // skip friends
850
851
            else if (s->isUsingNamespaceDirective())
                continue; // skip using namespace directives
852
            else if (! id->match(s->identifier()))
853
                continue;
854
            else if (s->name() && s->name()->isQualifiedNameId())
Roberto Raggi's avatar
Roberto Raggi committed
855
                continue; // skip qualified ids.
856

857
858
859
            if (Q_UNLIKELY(debug)) {
                Overview oo;
                qDebug() << "Found" << id->chars() << "in"
Orgad Shaneh's avatar
Orgad Shaneh committed
860
                         << (binding ? oo(binding->d->_name) : QString::fromLatin1("<null>"));
861
            }
862

863
864
865
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
866

867
            if (s->asNamespaceAlias() && binding) {
868
                LookupScope *targetNamespaceBinding = binding->lookupType(name);
869
870
                //there can be many namespace definitions
                if (targetNamespaceBinding && targetNamespaceBinding->symbols().size() > 0) {
871
872
873
874
875
                    Symbol *resolvedSymbol = targetNamespaceBinding->symbols().first();
                    item.setType(resolvedSymbol->type()); // override the type
                }
            }

876
            // instantiate function template
Orgad Shaneh's avatar
Orgad Shaneh committed
877
878
            if (const TemplateNameId *instantiation = name->asTemplateNameId()) {
                if (Template *specialization = s->asTemplate()) {
Orgad Shaneh's avatar
Orgad Shaneh committed
879
                    if (Symbol *decl = specialization->declaration()) {
880
                        if (decl->isFunction() || decl->isDeclaration()) {
881
882
                            Clone cloner(_control.data());
                            Subst subst(_control.data());
883
                            initializeSubst(cloner, subst, binding, specialization, instantiation);
Orgad Shaneh's avatar
Orgad Shaneh committed
884
                            Symbol *instantiatedFunctionTemplate = cloner.symbol(decl, &subst);
Orgad Shaneh's avatar
Orgad Shaneh committed
885
886
887
888
                            item.setType(instantiatedFunctionTemplate->type()); // override the type
                        }
                    }
                }
889
890
            }

891
            result->append(item);
892
893
894
895
        }
    }
}

896
LookupScope *LookupScope::lookupType(const Name *name)
897
898
899
900
{
    if (! name)
        return 0;

Orgad Shaneh's avatar
Orgad Shaneh committed
901
902
    ProcessedSet processed;
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ true, d);
903
904
}

905
LookupScope *LookupScope::lookupType(const Name *name, Block *block)
906
{
Orgad Shaneh's avatar
Orgad Shaneh committed
907
    d->flush();
908

909
    QHash<Block *, LookupScope *>::const_iterator citBlock = d->_blocks.constFind(block);
Orgad Shaneh's avatar
Orgad Shaneh committed
910
    if (citBlock != d->_blocks.constEnd()) {
911
        LookupScope *nestedBlock = citBlock.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
912
        ProcessedSet processed;
913
        if (LookupScope *foundInNestedBlock
Orgad Shaneh's avatar
Orgad Shaneh committed
914
915
916
                = nestedBlock->d->lookupType_helper(name,
                                                    &processed,
                                                    /*searchInEnclosingScope = */ true,
917
                                                    nestedBlock->d)) {
918
919
920
921
            return foundInNestedBlock;
        }
    }

Orgad Shaneh's avatar
Orgad Shaneh committed
922
    for (citBlock = d->_blocks.constBegin(); citBlock != d->_blocks.constEnd(); ++citBlock) {
923
        if (LookupScope *foundNestedBlock = citBlock.value()->lookupType(name, block))
924
925
926
927
928
929
            return foundNestedBlock;
    }

    return 0;
}

930
LookupScope *LookupScope::findType(const Name *name)
931
{
Orgad Shaneh's avatar
Orgad Shaneh committed
932
    ProcessedSet processed;
933
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ true, d);
934
935
}

Orgad Shaneh's avatar