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

#include "LookupContext.h"
32

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

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

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

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

52 53
namespace CPlusPlus {

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

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

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

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

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

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

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

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

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

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

    return false;
}

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

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

    return true;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

239
    return n;
240 241
}

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

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

288

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

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

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

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

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

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

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

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

    return 0;
}

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

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

    if (! name)
        return candidates;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return candidates;
}

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

    return binding;
}

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

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

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

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

    void flush();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        Subst &_subst;
        bool _found;
    };
694

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

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

    return true;
}

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

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

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

} // namespace Internal

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

812
    if (name) {
813

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

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

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

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

845 846
            return result;
        }
847

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

    return result;
}

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

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

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


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

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

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

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

Orgad Shaneh's avatar
Orgad Shaneh committed
912 913
}

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

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