LookupContext.cpp 69.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

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

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

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

51
52
namespace CPlusPlus {

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

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

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

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

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

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

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

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

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

102
        if (id == otherId || (id && id->match(otherId)))
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
            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;
}

122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
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;
}
}

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

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

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

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

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

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

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

205
206
207
208
209
210
211
212
213
214
215
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());
}
216

217
const Name *LookupContext::minimalName(Symbol *symbol, LookupScope *target, Control *control)
218
{
219
220
221
222
223
224
    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);
225
        else
226
227
228
229
230
231
232
233
234
235
            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;
            }
        }
236
237
    }

238
    return n;
239
240
}

241
QList<LookupItem> LookupContext::lookupByUsing(const Name *name,
242
                                               LookupScope *bindingScope) const
243
244
245
{
    QList<LookupItem> candidates;
    // if it is a nameId there can be a using declaration for it
246
    if (name->isNameId() || name->isTemplateNameId()) {
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
        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);
                                    }
                                }
267
                            }
268
269
270
271
272
                        }
                    }
                }
            }
        }
273
    } else if (const QualifiedNameId *q = name->asQualifiedNameId()) {
274
275
        foreach (Symbol *s, bindingScope->symbols()) {
            if (Scope *scope = s->asScope()) {
276
                LookupScope *base = lookupType(q->base(), scope);
277
278
279
280
281
282
                if (base)
                    candidates = lookupByUsing(q->name(), base);
                if (!candidates.isEmpty())
                    return candidates;
            }
        }
283
284
285
286
    }
    return candidates;
}

287

288
289
290
291
292
293
294
295
296
297
298
299
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; }

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

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

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

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

    return 0;
}

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

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

    if (! name)
        return candidates;

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

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

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

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

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

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

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

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

426
427
428
429
430
431
432
433
            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;
            }
434
435

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return candidates;
}

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

    return binding;
}

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

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

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

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

    void flush();

537
    LookupScope *globalNamespace() const;
Orgad Shaneh's avatar
Orgad Shaneh committed
538
539
540

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

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

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

    void addTodo(Symbol *symbol);
    void addSymbol(Symbol *symbol);
    void addUnscopedEnum(Enum *e);
549
550
    void addUsing(LookupScope *u);
    void addNestedType(const Name *alias, LookupScope *e);
Orgad Shaneh's avatar
Orgad Shaneh committed
551
552
553

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

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

558
559
    LookupScope *lookupType_helper(const Name *name, ProcessedSet *processed,
                                   bool searchInEnclosingScope, LookupScopePrivate *origin);
Orgad Shaneh's avatar
Orgad Shaneh committed
560

561
562
    LookupScope *findBlock_helper(Block *block, ProcessedSet *processed,
                                  bool searchInEnclosingScope);
Orgad Shaneh's avatar
Orgad Shaneh committed
563

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

566
567
    LookupScopePrivate *findSpecialization(const TemplateNameId *templId,
                                           const TemplateNameIdTable &specializations);
Orgad Shaneh's avatar
Orgad Shaneh committed
568

569
    LookupScope *q;
Orgad Shaneh's avatar
Orgad Shaneh committed
570
571

    CreateBindings *_factory;
572
    LookupScopePrivate *_parent;
Orgad Shaneh's avatar
Orgad Shaneh committed
573
    QList<Symbol *> _symbols;
574
575
576
    QList<LookupScope *> _usings;
    Table _nestedScopes;
    QHash<Block *, LookupScope *> _blocks;
Orgad Shaneh's avatar
Orgad Shaneh committed
577
578
579
580
    QList<Enum *> _enums;
    QList<Symbol *> _todo;
    QSharedPointer<Control> _control;
    TemplateNameIdTable _specializations;
581
    QMap<const TemplateNameId *, LookupScopePrivate *> _instantiations;
Orgad Shaneh's avatar
Orgad Shaneh committed
582
583
584
585
586
587
588
    Anonymouses _anonymouses;
    QSet<const AnonymousNameId *> _declaredOrTypedefedAnonymouses;

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

    // it's an instantiation.
    const TemplateNameId *_templateId;
589
    LookupScopePrivate *_instantiationOrigin;
Orgad Shaneh's avatar
Orgad Shaneh committed
590
591
592
593
594
595
596
597
598

    AlreadyConsideredClassContainer<Class> _alreadyConsideredClasses;
    AlreadyConsideredClassContainer<TemplateNameId> _alreadyConsideredTemplates;

    Class *_rootClass;
    const Name *_name; // For debug
};

class Instantiator
599
600
{
public:
Nikolai Kosjar's avatar
Nikolai Kosjar committed
601
602
    Instantiator(Clone &cloner, Subst &subst)
        : _cloner(cloner)
603
604
        , _subst(subst)
    {}
605
    void instantiate(LookupScopePrivate *lookupScope, LookupScopePrivate *instantiation);
606
private:
607
    bool isInstantiationNeeded(LookupScopePrivate *lookupScope) const;
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
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

    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:
        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;
    };
678

Orgad Shaneh's avatar
Orgad Shaneh committed
679
    ProcessedSet _alreadyConsideredInstantiations;
680
681
682
683
    Clone &_cloner;
    Subst &_subst;
};

684
685
static bool isNestedInstantiationEnclosingTemplate(LookupScopePrivate *nestedInstantiation,
                                                   LookupScopePrivate *enclosingInstantiation)
Orgad Shaneh's avatar
Orgad Shaneh committed
686
687
688
689
690
691
692
693
694
695
696
697
{
    ProcessedSet processed;
    while (enclosingInstantiation && !processed.contains(enclosingInstantiation)) {
        processed.insert(enclosingInstantiation);
        if (enclosingInstantiation == nestedInstantiation)
            return false;
        enclosingInstantiation = enclosingInstantiation->_parent;
    }

    return true;
}

698
LookupScopePrivate::LookupScopePrivate(LookupScope *q, CreateBindings *factory, LookupScope *parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
699
700
701
    : q(q)
    , _factory(factory)
    , _parent(parent ? parent->d : 0)
702
703
    , _scopeLookupCache(0)
    , _instantiationOrigin(0)
704
    , _rootClass(0)
705
    , _name(0)
706
{
707
    Q_ASSERT(factory);
708
709
}

710
LookupScopePrivate::~LookupScopePrivate()
711
712
713
714
{
    delete _scopeLookupCache;
}

715
LookupScopePrivate *LookupScopePrivate::allocateChild(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
716
{
717
    LookupScope *e = _factory->allocLookupScope(q, name);
Orgad Shaneh's avatar
Orgad Shaneh committed
718
719
720
721
722
    return e->d;
}

} // namespace Internal

723
724
LookupScope::LookupScope(CreateBindings *factory, LookupScope *parent)
    : d(new Internal::LookupScopePrivate(this, factory, parent))
Orgad Shaneh's avatar
Orgad Shaneh committed
725
726
727
{
}

728
LookupScope::~LookupScope()
Orgad Shaneh's avatar
Orgad Shaneh committed
729
730
731
732
{
    delete d;
}

733
LookupScope *LookupScope::instantiationOrigin() const
734
{
735
    if (Internal::LookupScopePrivate *i = d->_instantiationOrigin)
Orgad Shaneh's avatar
Orgad Shaneh committed
736
737
        return i->q;
    return 0;
738
739
}

740
LookupScope *LookupScope::parent() const
741
{
742
    if (Internal::LookupScopePrivate *p = d->_parent)
Orgad Shaneh's avatar
Orgad Shaneh committed
743
744
        return p->q;
    return 0;
745
746
}

747
QList<LookupScope *> LookupScope::usings() const
748
{
749
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
750
    return d->_usings;
751
752
}

753
QList<Enum *> LookupScope::unscopedEnums() const
754
{
755
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
756
    return d->_enums;
757
758
}

759
QList<Symbol *> LookupScope::symbols() const
760
{
761
    const_cast<LookupScope *>(this)->d->flush();
Orgad Shaneh's avatar
Orgad Shaneh committed
762
763
764
    return d->_symbols;
}

765
QList<LookupItem> LookupScope::find(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
766
767
768
769
{
    return d->lookup_helper(name, false);
}

770
QList<LookupItem> LookupScope::lookup(const Name *name)
Orgad Shaneh's avatar
Orgad Shaneh committed
771
772
{
    return d->lookup_helper(name, true);
773
774
}

Orgad Shaneh's avatar
Orgad Shaneh committed
775
776
namespace Internal {

777
LookupScope *LookupScopePrivate::globalNamespace() const
778
{
779
    const LookupScopePrivate *e = this;
780
781
782
783
784
785
786
787

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

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

Orgad Shaneh's avatar
Orgad Shaneh committed
788
    return e ? e->q : 0;
789
790
}

791
QList<LookupItem> LookupScopePrivate::lookup_helper(const Name *name, bool searchInEnclosingScope)
792
{
793
    QList<LookupItem> result;
794

795
    if (name) {
796

Orgad Shaneh's avatar
Orgad Shaneh committed
797
798
799
        if (const QualifiedNameId *qName = name->asQualifiedNameId()) {
            if (! qName->base()) { // e.g. ::std::string
                result = globalNamespace()->find(qName->name());
800
            } else if (LookupScope *binding = q->lookupType(qName->base())) {
Orgad Shaneh's avatar
Orgad Shaneh committed
801
                result = binding->find(qName->name());
802

803
804
805
806
807
808
809
                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
810
                ProcessedSet processed;
811
                for (LookupScopePrivate *parentBinding = binding->d->_parent;
812
                        parentBinding && !match;
Orgad Shaneh's avatar
Orgad Shaneh committed
813
                        parentBinding = parentBinding->_parent) {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
814
815
816
                    if (processed.contains(parentBinding))
                        break;
                    processed.insert(parentBinding);
817
                    match = parentBinding->lookupInScope(fullName);
Nikolai Kosjar's avatar
Nikolai Kosjar committed
818
                }
819
820
821
822
823
824
825
826

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

828
829
            return result;
        }
830

Orgad Shaneh's avatar
Orgad Shaneh committed
831
832
        ProcessedSet processed;
        ProcessedSet processedOwnParents;
833
        LookupScopePrivate *binding = this;
834
        do {
Nikolai Kosjar's avatar
Nikolai Kosjar committed
835
836
837
            if (processedOwnParents.contains(binding))
                break;
            processedOwnParents.insert(binding);
838
            lookup_helper(name, binding, &result, &processed);
839
840
841
            binding = binding->_parent;
        } while (searchInEnclosingScope && binding);
    }
842
843
844
845

    return result;
}

846
847
void LookupScopePrivate::lookup_helper(
        const Name *name, LookupScopePrivate *binding, QList<LookupItem> *result,
Orgad Shaneh's avatar
Orgad Shaneh committed
848
        ProcessedSet *processed)
849
{
Orgad Shaneh's avatar
Orgad Shaneh committed
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
    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);
872
873
874
                    }
                }
            }
Orgad Shaneh's avatar
Orgad Shaneh committed
875
            _factory->lookupInScope(name, scope, result, binding->q);
876
        }
Orgad Shaneh's avatar
Orgad Shaneh committed
877
    }
878

Orgad Shaneh's avatar
Orgad Shaneh committed
879
880
    foreach (Enum *e, binding->_enums)
        _factory->lookupInScope(name, e, result, binding->q);
881

882
    foreach (LookupScope *u, binding->_usings)
Orgad Shaneh's avatar
Orgad Shaneh committed
883
        lookup_helper(name, u->d, result, processed);
884

Orgad Shaneh's avatar
Orgad Shaneh committed
885
886
887
888
    Anonymouses::const_iterator cit = binding->_anonymouses.constBegin();
    Anonymouses::const_iterator citEnd = binding->_anonymouses.constEnd();
    for (; cit != citEnd; ++cit) {
        const AnonymousNameId *anonymousNameId = cit.key();
889
        LookupScopePrivate *a = cit.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
890
891
        if (!binding->_declaredOrTypedefedAnonymouses.contains(anonymousNameId))
            lookup_helper(name, a, result, processed);
892
893
894
    }
}

Orgad Shaneh's avatar
Orgad Shaneh committed
895
896
}

Roberto Raggi's avatar
Roberto Raggi committed
897
void CreateBindings::lookupInScope(const Name *name, Scope *scope,
898
                                   QList<LookupItem> *result,
899
                                   LookupScope *binding)
900
901
902
903
904
{
    if (! name) {
        return;

    } else if (const OperatorNameId *op = name->asOperatorNameId()) {
Roberto Raggi's avatar
Roberto Raggi committed
905
        for (Symbol *s = scope->find(op->kind()); s; s = s->next()) {
906
907
            if (! s->name())
                continue;
908
909
            else if (s->isFriend())
                continue;
910
            else if (! s->name()->match(op))
911
                continue;
912

913
914
915
916
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
            result->append(item);
917
918
919
        }

    } else if (const Identifier *id = name->identifier()) {
Roberto Raggi's avatar
Roberto Raggi committed
920
        for (Symbol *s = scope->find(id); s; s = s->next()) {
921
922
            if (s->isFriend())
                continue; // skip friends
923
924
            else if (s->isUsingNamespaceDirective())
                continue; // skip using namespace directives
925
            else if (! id->match(s->identifier()))
926
                continue;
927
            else if (s->name() && s->name()->isQualifiedNameId())
Roberto Raggi's avatar
Roberto Raggi committed
928
                continue; // skip qualified ids.
929

930
931
932
            if (Q_UNLIKELY(debug)) {
                Overview oo;
                qDebug() << "Found" << id->chars() << "in"
Orgad Shaneh's avatar
Orgad Shaneh committed
933
                         << (binding ? oo(binding->d->_name) : QString::fromLatin1("<null>"));
934
            }
935

936
937
938
            LookupItem item;
            item.setDeclaration(s);
            item.setBinding(binding);
939

940
            if (s->asNamespaceAlias() && binding) {
941
                LookupScope *targetNamespaceBinding = binding->lookupType(name);
942
943
                //there can be many namespace definitions
                if (targetNamespaceBinding && targetNamespaceBinding->symbols().size() > 0) {
944
945
946
947
948
                    Symbol *resolvedSymbol = targetNamespaceBinding->symbols().first();
                    item.setType(resolvedSymbol->type()); // override the type
                }
            }

949
950
951
952
953
954
955
956
957
958
            // 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.
            }

959
            result->append(item);
960
961
962
963
        }
    }
}

964
LookupScope *LookupScope::lookupType(const Name *name)
965
966
967
968
{
    if (! name)
        return 0;

Orgad Shaneh's avatar
Orgad Shaneh committed
969
970
    ProcessedSet processed;
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ true, d);
971
972
}

973
LookupScope *LookupScope::lookupType(const Name *name, Block *block)
974
{
Orgad Shaneh's avatar
Orgad Shaneh committed
975
    d->flush();
976

977
    QHash<Block *, LookupScope *>::const_iterator citBlock = d->_blocks.constFind(block);
Orgad Shaneh's avatar
Orgad Shaneh committed
978
    if (citBlock != d->_blocks.constEnd()) {
979
        LookupScope *nestedBlock = citBlock.value();
Orgad Shaneh's avatar
Orgad Shaneh committed
980
        ProcessedSet processed;
981
        if (LookupScope *foundInNestedBlock
Orgad Shaneh's avatar
Orgad Shaneh committed
982
983
984
985
                = nestedBlock->d->lookupType_helper(name,
                                                    &processed,
                                                    /*searchInEnclosingScope = */ true,
                                                    d)) {
986
987
988
989
            return foundInNestedBlock;
        }
    }

Orgad Shaneh's avatar
Orgad Shaneh committed
990
    for (citBlock = d->_blocks.constBegin(); citBlock != d->_blocks.constEnd(); ++citBlock) {
991
        if (LookupScope *foundNestedBlock = citBlock.value()->lookupType(name, block))
992
993
994
995
996
997
            return foundNestedBlock;
    }

    return 0;
}

998
LookupScope *LookupScope::findType(const Name *name)
999
{
Orgad Shaneh's avatar
Orgad Shaneh committed
1000
1001
    ProcessedSet processed;
    return d->lookupType_helper(name, &processed, /*searchInEnclosingScope =*/ false, d);
1002
1003
}

1004
LookupScope *Internal::LookupScopePrivate::findBlock_helper(
Orgad Shaneh's avatar
Orgad Shaneh committed
1005
        Block *block, ProcessedSet *processed, bool searchInEnclosingScope)
1006
{