language/duchain/ducontext.cpp

0001 /*
0002     SPDX-FileCopyrightText: 2006 Hamish Rodda <rodda@kde.org>
0003     SPDX-FileCopyrightText: 2007-2009 David Nolden <david.nolden.kdevelop@art-master.de>
0004
0005     SPDX-License-Identifier: LGPL-2.0-only
0006 */
0007
0008 #include "ducontext.h"
0009
0010 #include <limits>
0011 #include <algorithm>
0012
0013 #include <QSet>
0014
0015 #include "ducontextdata.h"
0016 #include "declaration.h"
0017 #include "duchain.h"
0018 #include "duchainlock.h"
0019 #include "use.h"
0020 #include "identifier.h"
0021 #include "topducontext.h"
0022 #include "persistentsymboltable.h"
0023 #include "aliasdeclaration.h"
0024 #include "namespacealiasdeclaration.h"
0025 #include "abstractfunctiondeclaration.h"
0026 #include "duchainregister.h"
0027 #include "topducontextdynamicdata.h"
0028 #include "importers.h"
0029 #include "uses.h"
0030 #include "navigation/abstractdeclarationnavigationcontext.h"
0031 #include "navigation/abstractnavigationwidget.h"
0032 #include "ducontextdynamicdata.h"
0033 #include <debug.h>
0034
0035 // maximum depth for DUContext::findDeclarationsInternal searches
0036 const uint maxParentDepth = 20;
0037
0038 using namespace KTextEditor;
0039
0040 #ifndef NDEBUG
0041 #define ENSURE_CAN_WRITE_(x) {if (x->inDUChain()) { ENSURE_CHAIN_WRITE_LOCKED }}
0042 #define ENSURE_CAN_READ_(x) {if (x->inDUChain()) { ENSURE_CHAIN_READ_LOCKED }}
0043 #else
0044 #define ENSURE_CAN_WRITE_(x)
0045 #define ENSURE_CAN_READ_(x)
0046 #endif
0047
0048 QDebug operator<<(QDebug dbg, const KDevelop::DUContext::Import& import)
0049 {
0050     QDebugStateSaver saver(dbg);
0051     dbg.nospace() << "Import(" << import.indexedContext().data() << ')';
0052     return dbg;
0053 }
0054
0055 namespace KDevelop {
0056 DEFINE_LIST_MEMBER_HASH(DUContextData, m_childContexts, LocalIndexedDUContext)
0057 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importers, IndexedDUContext)
0058 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importedContexts, DUContext::Import)
0059 DEFINE_LIST_MEMBER_HASH(DUContextData, m_localDeclarations, LocalIndexedDeclaration)
0060 DEFINE_LIST_MEMBER_HASH(DUContextData, m_uses, Use)
0061
0062 REGISTER_DUCHAIN_ITEM(DUContext);
0063
0064 DUChainVisitor::~DUChainVisitor()
0065 {
0066 }
0067
0068 /**
0069  * We leak here, to prevent a possible crash during destruction, as the destructor
0070  * of Identifier is not safe to be called after the duchain has been destroyed
0071  */
0072 const Identifier& globalImportIdentifier()
0073 {
0074     static const Identifier globalImportIdentifierObject(QStringLiteral("{...import...}"));
0075     return globalImportIdentifierObject;
0076 }
0077
0078 const Identifier& globalAliasIdentifier()
0079 {
0080     static const Identifier globalAliasIdentifierObject(QStringLiteral("{...alias...}"));
0081     return globalAliasIdentifierObject;
0082 }
0083
0084 const IndexedIdentifier& globalIndexedImportIdentifier()
0085 {
0086     static const IndexedIdentifier id(globalImportIdentifier());
0087     return id;
0088 }
0089
0090 const IndexedIdentifier& globalIndexedAliasIdentifier()
0091 {
0092     static const IndexedIdentifier id(globalAliasIdentifier());
0093     return id;
0094 }
0095
0096 void DUContext::rebuildDynamicData(DUContext* parent, uint ownIndex)
0097 {
0098     Q_ASSERT(!parent || ownIndex);
0099     m_dynamicData->m_topContext = parent ? parent->topContext() : static_cast<TopDUContext*>(this);
0100     m_dynamicData->m_indexInTopContext = ownIndex;
0101     m_dynamicData->m_parentContext = DUContextPointer(parent);
0102     m_dynamicData->m_context = this;
0103
0104     m_dynamicData->m_childContexts.clear();
0105     m_dynamicData->m_childContexts.reserve(d_func()->m_childContextsSize());
0106     FOREACH_FUNCTION(const LocalIndexedDUContext &ctx, d_func()->m_childContexts) {
0107         m_dynamicData->m_childContexts << ctx.data(m_dynamicData->m_topContext);
0108     }
0109
0110     m_dynamicData->m_localDeclarations.clear();
0111     m_dynamicData->m_localDeclarations.reserve(d_func()->m_localDeclarationsSize());
0112     FOREACH_FUNCTION(const LocalIndexedDeclaration &idx, d_func()->m_localDeclarations) {
0113         auto declaration = idx.data(m_dynamicData->m_topContext);
0114         if (!declaration) {
0115             qCWarning(LANGUAGE) << "child declaration number" << idx.localIndex() << "of" <<
0116                 d_func_dynamic()->m_localDeclarationsSize() << "is invalid";
0117             continue;
0118         }
0119         m_dynamicData->m_localDeclarations << declaration;
0120     }
0121
0122     DUChainBase::rebuildDynamicData(parent, ownIndex);
0123 }
0124
0125 DUContextData::DUContextData()
0126     : m_inSymbolTable(false)
0127     , m_anonymousInParent(false)
0128     , m_propagateDeclarations(false)
0129 {
0130     initializeAppendedLists();
0131 }
0132
0133 DUContextData::~DUContextData()
0134 {
0135     freeAppendedLists();
0136 }
0137
0138 DUContextData::DUContextData(const DUContextData& rhs)
0139     : DUChainBaseData(rhs)
0140     , m_inSymbolTable(rhs.m_inSymbolTable)
0141     , m_anonymousInParent(rhs.m_anonymousInParent)
0142     , m_propagateDeclarations(rhs.m_propagateDeclarations)
0143 {
0144     initializeAppendedLists();
0145     copyListsFrom(rhs);
0146     m_scopeIdentifier = rhs.m_scopeIdentifier;
0147     m_contextType = rhs.m_contextType;
0148     m_owner = rhs.m_owner;
0149 }
0150
0151 DUContextDynamicData::DUContextDynamicData(DUContext* d)
0152     : m_topContext(nullptr)
0153     , m_indexInTopContext(0)
0154     , m_context(d)
0155 {
0156 }
0157
0158 void DUContextDynamicData::scopeIdentifier(bool includeClasses, QualifiedIdentifier& target) const
0159 {
0160     if (m_parentContext)
0161         m_parentContext->m_dynamicData->scopeIdentifier(includeClasses, target);
0162
0163     if (includeClasses || d_func()->m_contextType != DUContext::Class)
0164         target += d_func()->m_scopeIdentifier;
0165 }
0166
0167 bool DUContextDynamicData::imports(const DUContext* context, const TopDUContext* source,
0168                                    QSet<const DUContextDynamicData*>* recursionGuard) const
0169 {
0170     if (this == context->m_dynamicData)
0171         return true;
0172
0173     if (recursionGuard->contains(this)) {
0174         return false;
0175     }
0176     recursionGuard->insert(this);
0177
0178     FOREACH_FUNCTION(const DUContext::Import& ctx, d_func()->m_importedContexts) {
0179         DUContext* import = ctx.context(source);
0180         if (import == context || (import && import->m_dynamicData->imports(context, source, recursionGuard)))
0181             return true;
0182     }
0183
0184     return false;
0185 }
0186
0187 inline bool isContextTemporary(uint index)
0188 {
0189     return index > (0xffffffff / 2);
0190 }
0191
0192 void DUContextDynamicData::addDeclaration(Declaration* newDeclaration)
0193 {
0194     // The definition may not have its identifier set when it's assigned...
0195     // allow dupes here, TODO catch the error elsewhere
0196
0197     //If this context is temporary, added declarations should be as well, and viceversa
0198     Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(newDeclaration->ownIndex()));
0199
0200     CursorInRevision start = newDeclaration->range().start;
0201
0202     bool inserted = false;
0203     ///@todo Do binary search to find the position
0204     for (int i = m_localDeclarations.size() - 1; i >= 0; --i) {
0205         Declaration* child = m_localDeclarations[i];
0206         Q_ASSERT(d_func()->m_localDeclarations()[i].data(m_topContext) == child);
0207         if (child == newDeclaration)
0208             return;
0209         //TODO: All declarations in a macro will have the same empty range, and just get appended
0210         //that may not be Good Enough in complex cases.
0211         if (start >= child->range().start) {
0212             m_localDeclarations.insert(i + 1, newDeclaration);
0213             d_func_dynamic()->m_localDeclarationsList().insert(i + 1, newDeclaration);
0214             Q_ASSERT(d_func()->m_localDeclarations()[i + 1].data(m_topContext) == newDeclaration);
0215
0216             inserted = true;
0217             break;
0218         }
0219     }
0220
0221     if (!inserted) {
0222         // We haven't found any child that is before this one, so prepend it
0223         m_localDeclarations.insert(0, newDeclaration);
0224         d_func_dynamic()->m_localDeclarationsList().insert(0, newDeclaration);
0225         Q_ASSERT(d_func()->m_localDeclarations()[0].data(m_topContext) == newDeclaration);
0226     }
0227 }
0228
0229 bool DUContextDynamicData::removeDeclaration(Declaration* declaration)
0230 {
0231     const int idx = m_localDeclarations.indexOf(declaration);
0232     if (idx != -1) {
0233         Q_ASSERT(d_func()->m_localDeclarations()[idx].data(m_topContext) == declaration);
0234         m_localDeclarations.remove(idx);
0235         d_func_dynamic()->m_localDeclarationsList().remove(idx);
0236         return true;
0237     } else {
0238         Q_ASSERT(d_func_dynamic()->m_localDeclarationsList().indexOf(LocalIndexedDeclaration(declaration)) == -1);
0239         return false;
0240     }
0241 }
0242
0243 void DUContextDynamicData::addChildContext(DUContext* context)
0244 {
0245     // Internal, don't need to assert a lock
0246     Q_ASSERT(!context->m_dynamicData->m_parentContext
0247              || context->m_dynamicData->m_parentContext.data()->m_dynamicData == this);
0248
0249     LocalIndexedDUContext indexed(context->m_dynamicData->m_indexInTopContext);
0250
0251     //If this context is temporary, added declarations should be as well, and viceversa
0252     Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(indexed.localIndex()));
0253
0254     bool inserted = false;
0255
0256     int childCount = m_childContexts.size();
0257
0258     for (int i = childCount - 1; i >= 0; --i) {///@todo Do binary search to find the position
0259         DUContext* child = m_childContexts[i];
0260         Q_ASSERT(d_func_dynamic()->m_childContexts()[i] == LocalIndexedDUContext(child));
0261         if (context == child)
0262             return;
0263         if (context->range().start >= child->range().start) {
0264             m_childContexts.insert(i + 1, context);
0265             d_func_dynamic()->m_childContextsList().insert(i + 1, indexed);
0266             context->m_dynamicData->m_parentContext = m_context;
0267             inserted = true;
0268             break;
0269         }
0270     }
0271
0272     if (!inserted) {
0273         m_childContexts.insert(0, context);
0274         d_func_dynamic()->m_childContextsList().insert(0, indexed);
0275         context->m_dynamicData->m_parentContext = m_context;
0276     }
0277 }
0278
0279 bool DUContextDynamicData::removeChildContext(DUContext* context)
0280 {
0281 //   ENSURE_CAN_WRITE
0282
0283     const int idx = m_childContexts.indexOf(context);
0284     if (idx != -1) {
0285         m_childContexts.remove(idx);
0286         Q_ASSERT(d_func()->m_childContexts()[idx] == LocalIndexedDUContext(context));
0287         d_func_dynamic()->m_childContextsList().remove(idx);
0288         return true;
0289     } else {
0290         Q_ASSERT(d_func_dynamic()->m_childContextsList().indexOf(LocalIndexedDUContext(context)) == -1);
0291         return false;
0292     }
0293 }
0294
0295 void DUContextDynamicData::addImportedChildContext(DUContext* context)
0296 {
0297 //   ENSURE_CAN_WRITE
0298     DUContext::Import import(m_context, context);
0299
0300     if (import.isDirect()) {
0301         //Direct importers are registered directly within the data
0302         if (d_func_dynamic()->m_importersList().contains(IndexedDUContext(context))) {
0303             qCDebug(LANGUAGE) << m_context->scopeIdentifier(true).toString() << "importer added multiple times:" <<
0304                 context->scopeIdentifier(true).toString();
0305             return;
0306         }
0307
0308         d_func_dynamic()->m_importersList().append(context);
0309     } else {
0310         //Indirect importers are registered separately
0311         Importers::self().addImporter(import.indirectDeclarationId(), IndexedDUContext(context));
0312     }
0313 }
0314
0315 //Can also be called with a context that is not in the list
0316 void DUContextDynamicData::removeImportedChildContext(DUContext* context)
0317 {
0318 //   ENSURE_CAN_WRITE
0319     DUContext::Import import(m_context, context);
0320
0321     if (import.isDirect()) {
0322         d_func_dynamic()->m_importersList().removeOne(IndexedDUContext(context));
0323     } else {
0324         //Indirect importers are registered separately
0325         Importers::self().removeImporter(import.indirectDeclarationId(), IndexedDUContext(context));
0326     }
0327 }
0328
0329 int DUContext::depth() const
0330 {
0331     if (!parentContext()) {
0332         return 0;
0333     }
0334
0335     return parentContext()->depth() + 1;
0336 }
0337
0338 DUContext::DUContext(DUContextData& data)
0339     : DUChainBase(data)
0340     , m_dynamicData(new DUContextDynamicData(this))
0341 {
0342 }
0343
0344 DUContext::DUContext(const RangeInRevision& range, DUContext* parent, bool anonymous)
0345     : DUChainBase(*new DUContextData(), range)
0346     , m_dynamicData(new DUContextDynamicData(this))
0347 {
0348     d_func_dynamic()->setClassId(this);
0349     if (parent)
0350         m_dynamicData->m_topContext = parent->topContext();
0351
0352     d_func_dynamic()->setClassId(this);
0353     DUCHAIN_D_DYNAMIC(DUContext);
0354     d->m_contextType = Other;
0355     m_dynamicData->m_parentContext = nullptr;
0356
0357     d->m_anonymousInParent = anonymous;
0358     d->m_inSymbolTable = false;
0359
0360     if (parent) {
0361         m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this,
0362                                                                                                        parent->isAnonymous() ||
0363                                                                                                        anonymous);
0364         Q_ASSERT(m_dynamicData->m_indexInTopContext);
0365
0366         if (!anonymous)
0367             parent->m_dynamicData->addChildContext(this);
0368         else
0369             m_dynamicData->m_parentContext = parent;
0370     }
0371
0372     if (parent && !anonymous && parent->inSymbolTable())
0373         setInSymbolTable(true);
0374 }
0375
0376 bool DUContext::isAnonymous() const
0377 {
0378     return d_func()->m_anonymousInParent ||
0379            (m_dynamicData->m_parentContext && m_dynamicData->m_parentContext->isAnonymous());
0380 }
0381
0382 void DUContext::initFromTopContext()
0383 {
0384     Q_ASSERT(dynamic_cast<TopDUContext*>(this));
0385     m_dynamicData->m_topContext = static_cast<TopDUContext*>(this);
0386 }
0387
0388 DUContext::DUContext(DUContextData& dd, const RangeInRevision& range, DUContext* parent, bool anonymous)
0389     : DUChainBase(dd, range)
0390     , m_dynamicData(new DUContextDynamicData(this))
0391 {
0392     if (parent)
0393         m_dynamicData->m_topContext = parent->topContext();
0394     // else initTopContext must be called, doing a static_cast here is UB
0395
0396     DUCHAIN_D_DYNAMIC(DUContext);
0397     d->m_contextType = Other;
0398     m_dynamicData->m_parentContext = nullptr;
0399     d->m_inSymbolTable = false;
0400     d->m_anonymousInParent = anonymous;
0401     if (parent) {
0402         m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this,
0403                                                                                                        parent->isAnonymous() ||
0404                                                                                                        anonymous);
0405
0406         if (!anonymous)
0407             parent->m_dynamicData->addChildContext(this);
0408         else
0409             m_dynamicData->m_parentContext = parent;
0410     }
0411 }
0412
0413 DUContext::DUContext(DUContext& useDataFrom)
0414     : DUChainBase(useDataFrom)
0415     , m_dynamicData(useDataFrom.m_dynamicData)
0416 {
0417 }
0418
0419 DUContext::~DUContext()
0420 {
0421     TopDUContext* top = topContext();
0422
0423     if (top != this) {
0424         const auto doCleanup = !top->deleting() || !top->isOnDisk();
0425
0426         if (doCleanup) {
0427             DUCHAIN_D_DYNAMIC(DUContext);
0428
0429             if (d->m_owner.declaration())
0430                 d->m_owner.declaration()->setInternalContext(nullptr);
0431
0432             while (d->m_importersSize() != 0) {
0433                 if (d->m_importers()[0].data())
0434                     d->m_importers()[0].data()->removeImportedParentContext(this);
0435                 else {
0436                     qCDebug(LANGUAGE) << "importer disappeared";
0437                     d->m_importersList().removeOne(d->m_importers()[0]);
0438                 }
0439             }
0440
0441             clearImportedParentContexts();
0442         }
0443
0444         deleteChildContextsRecursively();
0445
0446         if (doCleanup)
0447             deleteUses();
0448
0449         deleteLocalDeclarations();
0450
0451         //If the top-context is being delete, we don't need to spend time rebuilding the inner structure.
0452         //That's expensive, especially when the data is not dynamic.
0453         if (doCleanup && m_dynamicData->m_parentContext) {
0454             m_dynamicData->m_parentContext->m_dynamicData->removeChildContext(this);
0455         }
0456
0457         top->m_dynamicData->clearContextIndex(this);
0458
0459         Q_ASSERT(d_func()->isDynamic() ==
0460                 (doCleanup ||
0461                 top->m_dynamicData->isTemporaryContextIndex(m_dynamicData->m_indexInTopContext)));
0462     }
0463
0464     delete m_dynamicData;
0465 }
0466
0467 QVector<DUContext*> DUContext::childContexts() const
0468 {
0469     ENSURE_CAN_READ
0470
0471     return m_dynamicData->m_childContexts;
0472 }
0473
0474 Declaration* DUContext::owner() const
0475 {
0476     ENSURE_CAN_READ
0477     return d_func()->m_owner.declaration();
0478 }
0479
0480 void DUContext::setOwner(Declaration* owner)
0481 {
0482     ENSURE_CAN_WRITE
0483         DUCHAIN_D_DYNAMIC(DUContext);
0484     if (owner == d->m_owner.declaration())
0485         return;
0486
0487     Declaration* oldOwner = d->m_owner.declaration();
0488
0489     d->m_owner = owner;
0490
0491     //Q_ASSERT(!oldOwner || oldOwner->internalContext() == this);
0492     if (oldOwner && oldOwner->internalContext() == this)
0493         oldOwner->setInternalContext(nullptr);
0494
0495     //The context set as internal context should always be the last opened context
0496     if (owner)
0497         owner->setInternalContext(this);
0498 }
0499
0500 DUContext* DUContext::parentContext() const
0501 {
0502     //ENSURE_CAN_READ Commented out for performance reasons
0503
0504     return m_dynamicData->m_parentContext.data();
0505 }
0506
0507 void DUContext::setPropagateDeclarations(bool propagate)
0508 {
0509     ENSURE_CAN_WRITE
0510         DUCHAIN_D_DYNAMIC(DUContext);
0511
0512     if (propagate == d->m_propagateDeclarations)
0513         return;
0514
0515     d->m_propagateDeclarations = propagate;
0516 }
0517
0518 bool DUContext::isPropagateDeclarations() const
0519 {
0520     return d_func()->m_propagateDeclarations;
0521 }
0522
0523 QList<Declaration*> DUContext::findLocalDeclarations(const IndexedIdentifier& identifier,
0524                                                      const CursorInRevision& position,
0525                                                      const TopDUContext* topContext,
0526                                                      const AbstractType::Ptr& dataType,
0527                                                      SearchFlags flags) const
0528 {
0529     ENSURE_CAN_READ
0530
0531     DeclarationList ret;
0532     findLocalDeclarationsInternal(identifier,
0533                                   position.isValid() ? position : range().end, dataType, ret,
0534                                   topContext ? topContext : this->topContext(), flags);
0535     return ret;
0536 }
0537
0538 QList<Declaration*> DUContext::findLocalDeclarations(const Identifier& identifier,
0539                                                      const CursorInRevision& position,
0540                                                      const TopDUContext* topContext,
0541                                                      const AbstractType::Ptr& dataType,
0542                                                      SearchFlags flags) const
0543 {
0544     return findLocalDeclarations(IndexedIdentifier(identifier), position, topContext, dataType, flags);
0545 }
0546
0547 namespace {
0548 bool contextIsChildOrEqual(const DUContext* childContext, const DUContext* context)
0549 {
0550     if (childContext == context)
0551         return true;
0552
0553     if (childContext->parentContext())
0554         return contextIsChildOrEqual(childContext->parentContext(), context);
0555     else
0556         return false;
0557 }
0558
0559 struct Checker
0560 {
0561     Checker(DUContext::SearchFlags flags, const AbstractType::Ptr& dataType,
0562             const CursorInRevision& position, DUContext::ContextType ownType)
0563         : m_flags(flags)
0564         , m_dataType(dataType)
0565         , m_position(position)
0566         , m_ownType(ownType)
0567     {
0568     }
0569
0570     Declaration* check(Declaration* declaration) const
0571     {
0572         ///@todo This is C++-specific
0573         if (m_ownType != DUContext::Class && m_ownType != DUContext::Template
0574             && m_position.isValid() && m_position <= declaration->range().start) {
0575             return nullptr;
0576         }
0577
0578         if (declaration->kind() == Declaration::Alias && !(m_flags & DUContext::DontResolveAliases)) {
0579             //Apply alias declarations
0580             auto* alias = static_cast<AliasDeclaration*>(declaration);
0581             if (alias->aliasedDeclaration().isValid()) {
0582                 declaration = alias->aliasedDeclaration().declaration();
0583             } else {
0584                 qCDebug(LANGUAGE) << "lost aliased declaration";
0585             }
0586         }
0587
0588         if (declaration->kind() == Declaration::NamespaceAlias && !(m_flags & DUContext::NoFiltering)) {
0589             return nullptr;
0590         }
0591
0592         if (( m_flags& DUContext::OnlyFunctions ) && !declaration->isFunctionDeclaration()) {
0593             return nullptr;
0594         }
0595
0596         if (m_dataType && m_dataType->indexed() != declaration->indexedType()) {
0597             return nullptr;
0598         }
0599
0600         return declaration;
0601     }
0602
0603     DUContext::SearchFlags m_flags;
0604     const AbstractType::Ptr m_dataType;
0605     const CursorInRevision m_position;
0606     DUContext::ContextType m_ownType;
0607 };
0608 }
0609
0610 void DUContext::findLocalDeclarationsInternal(const Identifier& identifier, const CursorInRevision& position,
0611                                               const AbstractType::Ptr& dataType, DeclarationList& ret,
0612                                               const TopDUContext* source, SearchFlags flags) const
0613 {
0614     findLocalDeclarationsInternal(IndexedIdentifier(identifier), position, dataType, ret, source, flags);
0615 }
0616
0617 void DUContext::findLocalDeclarationsInternal(const IndexedIdentifier& identifier,
0618                                               const CursorInRevision& position,
0619                                               const AbstractType::Ptr& dataType,
0620                                               DeclarationList& ret, const TopDUContext* /*source*/,
0621                                               SearchFlags flags) const
0622 {
0623     Checker checker(flags, dataType, position, type());
0624
0625     DUCHAIN_D(DUContext);
0626     if (d->m_inSymbolTable && !d->m_scopeIdentifier.isEmpty() && !identifier.isEmpty()) {
0627         //This context is in the symbol table, use the symbol-table to speed up the search
0628         QualifiedIdentifier id(scopeIdentifier(true) + identifier);
0629
0630         TopDUContext* top = topContext();
0631
0632         PersistentSymbolTable::self().visitDeclarations(id, [&](const IndexedDeclaration& indexedDecl) {
0633             ///@todo Eventually do efficient iteration-free filtering
0634             if (indexedDecl.topContextIndex() == top->ownIndex()) {
0635                 Declaration* decl = indexedDecl.declaration();
0636                 if (decl && contextIsChildOrEqual(decl->context(), this)) {
0637                     Declaration* checked = checker.check(decl);
0638                     if (checked) {
0639                         ret.append(checked);
0640                     }
0641                 }
0642             }
0643             return PersistentSymbolTable::VisitorState::Continue;
0644         });
0645     } else {
0646         //Iterate through all declarations
0647         DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
0648         while (it) {
0649             Declaration* declaration = *it;
0650             if (declaration && declaration->indexedIdentifier() == identifier) {
0651                 Declaration* checked = checker.check(declaration);
0652                 if (checked)
0653                     ret.append(checked);
0654             }
0655             ++it;
0656         }
0657     }
0658 }
0659
0660 bool DUContext::foundEnough(const DeclarationList& ret, SearchFlags flags) const
0661 {
0662     if (!ret.isEmpty() && !(flags & DUContext::NoFiltering))
0663         return true;
0664     else
0665         return false;
0666 }
0667
0668 bool DUContext::findDeclarationsInternal(const SearchItem::PtrList& baseIdentifiers,
0669                                          const CursorInRevision& position,
0670                                          const AbstractType::Ptr& dataType,
0671                                          DeclarationList& ret, const TopDUContext* source,
0672                                          SearchFlags flags, uint depth) const
0673 {
0674     if (depth > maxParentDepth) {
0675         qCDebug(LANGUAGE) << "maximum depth reached in" << scopeIdentifier(true);
0676         return false;
0677     }
0678
0679     DUCHAIN_D(DUContext);
0680     if (d->m_contextType != Namespace) {
0681         // If we're in a namespace, delay all the searching into the top-context, because only that has the overview to pick the correct declarations.
0682         for (auto& baseIdentifier : baseIdentifiers) {
0683             if (!baseIdentifier->isExplicitlyGlobal && baseIdentifier->next.isEmpty()) {
0684                 // It makes no sense searching locally for qualified identifiers
0685                 findLocalDeclarationsInternal(baseIdentifier->identifier, position, dataType, ret, source, flags);
0686             }
0687         }
0688
0689         if (foundEnough(ret, flags)) {
0690             return true;
0691         }
0692     }
0693
0694     ///Step 1: Apply namespace-aliases and -imports
0695     SearchItem::PtrList aliasedIdentifiers;
0696     //Because of namespace-imports and aliases, this identifier may need to be searched under multiple names
0697     applyAliases(baseIdentifiers, aliasedIdentifiers, position, false,
0698                  type() != DUContext::Namespace && type() != DUContext::Global);
0699
0700     if (d->m_importedContextsSize() != 0) {
0701         ///Step 2: Give identifiers that are not marked as explicitly-global to imported contexts(explicitly global ones are treatead in TopDUContext)
0702         SearchItem::PtrList nonGlobalIdentifiers;
0703         for (const SearchItem::Ptr& identifier : qAsConst(aliasedIdentifiers)) {
0704             if (!identifier->isExplicitlyGlobal) {
0705                 nonGlobalIdentifiers << identifier;
0706             }
0707         }
0708
0709         if (!nonGlobalIdentifiers.isEmpty()) {
0710             const auto& url = this->url();
0711             for (int import = d->m_importedContextsSize() - 1; import >= 0; --import) {
0712                 if (position.isValid() && d->m_importedContexts()[import].position.isValid() &&
0713                     position < d->m_importedContexts()[import].position) {
0714                     continue;
0715                 }
0716
0717                 DUContext* context = d->m_importedContexts()[import].context(source);
0718
0719                 if (!context) {
0720                     continue;
0721                 } else if (context == this) {
0722                     qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true);
0723                     continue;
0724                 }
0725
0726                 if (!context->findDeclarationsInternal(nonGlobalIdentifiers,
0727                                                        url == context->url() ? position : context->range().end,
0728                                                        dataType, ret, source, flags | InImportedParentContext,
0729                                                        depth + 1)) {
0730                     return false;
0731                 }
0732             }
0733         }
0734     }
0735
0736     if (foundEnough(ret, flags)) {
0737         return true;
0738     }
0739
0740     ///Step 3: Continue search in parent-context
0741     if (!(flags & DontSearchInParent) && shouldSearchInParent(flags) && m_dynamicData->m_parentContext) {
0742         applyUpwardsAliases(aliasedIdentifiers, source);
0743         return m_dynamicData->m_parentContext->findDeclarationsInternal(aliasedIdentifiers,
0744                                                                         url() == m_dynamicData->m_parentContext->url() ? position : m_dynamicData->m_parentContext->range().end,
0745                                                                         dataType, ret, source, flags, depth);
0746     }
0747     return true;
0748 }
0749
0750 QVector<QualifiedIdentifier> DUContext::fullyApplyAliases(const QualifiedIdentifier& id,
0751                                                           const TopDUContext* source) const
0752 {
0753     ENSURE_CAN_READ
0754
0755     if (!source)
0756         source = topContext();
0757
0758     SearchItem::PtrList identifiers;
0759     identifiers << SearchItem::Ptr(new SearchItem(id));
0760
0761     const DUContext* current = this;
0762     while (current) {
0763         SearchItem::PtrList aliasedIdentifiers;
0764         current->applyAliases(identifiers, aliasedIdentifiers, CursorInRevision::invalid(), true, false);
0765         current->applyUpwardsAliases(identifiers, source);
0766
0767         current = current->parentContext();
0768     }
0769
0770     QVector<QualifiedIdentifier> ret;
0771     for (const SearchItem::Ptr& item : qAsConst(identifiers)) {
0772         ret += item->toList();
0773     }
0774
0775     return ret;
0776 }
0777
0778 QList<Declaration*> DUContext::findDeclarations(const QualifiedIdentifier& identifier,
0779                                                 const CursorInRevision& position,
0780                                                 const AbstractType::Ptr& dataType,
0781                                                 const TopDUContext* topContext, SearchFlags flags) const
0782 {
0783     ENSURE_CAN_READ
0784
0785     DeclarationList ret;
0786     // optimize: we don't want to allocate the top node always
0787     // so create it on stack but ref it so its not deleted by the smart pointer
0788     SearchItem item(identifier);
0789     item.ref.ref();
0790
0791     SearchItem::PtrList identifiers{SearchItem::Ptr(&item)};
0792
0793     findDeclarationsInternal(identifiers,
0794                              position.isValid() ? position : range().end, dataType, ret,
0795                              topContext ? topContext : this->topContext(), flags, 0);
0796
0797     return ret;
0798 }
0799
0800 bool DUContext::imports(const DUContext* origin, const CursorInRevision& /*position*/) const
0801 {
0802     ENSURE_CAN_READ
0803
0804     QSet<const DUContextDynamicData*> recursionGuard;
0805     recursionGuard.reserve(8);
0806     return m_dynamicData->imports(origin, topContext(), &recursionGuard);
0807 }
0808
0809 bool DUContext::addIndirectImport(const DUContext::Import& import)
0810 {
0811     ENSURE_CAN_WRITE
0812         DUCHAIN_D_DYNAMIC(DUContext);
0813
0814     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
0815         if (d->m_importedContexts()[a] == import) {
0816             d->m_importedContextsList()[a].position = import.position;
0817             return true;
0818         }
0819     }
0820
0821     ///Do not sort the imported contexts by their own line-number, it makes no sense.
0822     ///Contexts added first, aka template-contexts, should stay in first place, so they are searched first.
0823
0824     d->m_importedContextsList().append(import);
0825     return false;
0826 }
0827
0828 void DUContext::addImportedParentContext(DUContext* context, const CursorInRevision& position, bool anonymous,
0829                                          bool /*temporary*/)
0830 {
0831     ENSURE_CAN_WRITE
0832
0833     if (context == this) {
0834         qCDebug(LANGUAGE) << "Tried to import self";
0835         return;
0836     }
0837     if (!context) {
0838         qCDebug(LANGUAGE) << "Tried to import invalid context";
0839         return;
0840     }
0841
0842     Import import(context, this, position);
0843     if (addIndirectImport(import))
0844         return;
0845
0846     if (!anonymous) {
0847         ENSURE_CAN_WRITE_(context)
0848         context->m_dynamicData->addImportedChildContext(this);
0849     }
0850 }
0851
0852 void DUContext::removeImportedParentContext(DUContext* context)
0853 {
0854     ENSURE_CAN_WRITE
0855         DUCHAIN_D_DYNAMIC(DUContext);
0856
0857     Import import(context, this, CursorInRevision::invalid());
0858
0859     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
0860         if (d->m_importedContexts()[a] == import) {
0861             d->m_importedContextsList().remove(a);
0862             break;
0863         }
0864     }
0865
0866     if (!context)
0867         return;
0868
0869     context->m_dynamicData->removeImportedChildContext(this);
0870 }
0871
0872 KDevVarLengthArray<IndexedDUContext> DUContext::indexedImporters() const
0873 {
0874     KDevVarLengthArray<IndexedDUContext> ret;
0875     if (owner())
0876         ret = Importers::self().importers(owner()->id()); //Add indirect importers to the list
0877
0878     FOREACH_FUNCTION(const IndexedDUContext &ctx, d_func()->m_importers)
0879     ret.append(ctx);
0880
0881     return ret;
0882 }
0883
0884 QVector<DUContext*> DUContext::importers() const
0885 {
0886     ENSURE_CAN_READ
0887
0888     QVector<DUContext*> ret;
0889     ret.reserve(d_func()->m_importersSize());
0890     FOREACH_FUNCTION(const IndexedDUContext &ctx, d_func()->m_importers)
0891     ret << ctx.context();
0892
0893     if (owner()) {
0894         //Add indirect importers to the list
0895         const KDevVarLengthArray<IndexedDUContext> indirect = Importers::self().importers(owner()->id());
0896         ret.reserve(ret.size() + indirect.size());
0897         for (const IndexedDUContext ctx : indirect) {
0898             ret << ctx.context();
0899         }
0900     }
0901
0902     return ret;
0903 }
0904
0905 DUContext* DUContext::findContext(const CursorInRevision& position, DUContext* parent) const
0906 {
0907     ENSURE_CAN_READ
0908
0909     if (!parent)
0910         parent = const_cast<DUContext*>(this);
0911
0912     for (DUContext* context : qAsConst(parent->m_dynamicData->m_childContexts)) {
0913         if (context->range().contains(position)) {
0914             DUContext* ret = findContext(position, context);
0915             if (!ret) {
0916                 ret = context;
0917             }
0918
0919             return ret;
0920         }
0921     }
0922
0923     return nullptr;
0924 }
0925
0926 bool DUContext::parentContextOf(DUContext* context) const
0927 {
0928     if (this == context)
0929         return true;
0930
0931     const auto& childContexts = m_dynamicData->m_childContexts;
0932     return std::any_of(childContexts.begin(), childContexts.end(), [&](DUContext* child) {
0933         return child->parentContextOf(context);
0934     });
0935 }
0936
0937 QVector<QPair<Declaration*, int>> DUContext::allDeclarations(const CursorInRevision& position,
0938                                                              const TopDUContext* topContext,
0939                                                              bool searchInParents) const
0940 {
0941     ENSURE_CAN_READ
0942
0943     QVector<QPair<Declaration*, int>> ret;
0944
0945     QHash<const DUContext*, bool> hadContexts;
0946     // Iterate back up the chain
0947     mergeDeclarationsInternal(ret, position, hadContexts, topContext ? topContext : this->topContext(),
0948                               searchInParents);
0949
0950     return ret;
0951 }
0952
0953 QVector<Declaration*> DUContext::localDeclarations(const TopDUContext* source) const
0954 {
0955     ENSURE_CAN_READ
0956     // TODO: remove this parameter once we kill old-cpp
0957         Q_UNUSED(source);
0958     return m_dynamicData->m_localDeclarations;
0959 }
0960
0961 void DUContext::mergeDeclarationsInternal(QVector<QPair<Declaration*, int>>& definitions,
0962                                           const CursorInRevision& position,
0963                                           QHash<const DUContext*, bool>& hadContexts,
0964                                           const TopDUContext* source,
0965                                           bool searchInParents, int currentDepth) const
0966 {
0967     ENSURE_CAN_READ
0968
0969     if ((currentDepth > 300 && currentDepth < 1000) || currentDepth > 1300) {
0970         qCDebug(LANGUAGE) << "too much depth";
0971         return;
0972     }
0973     DUCHAIN_D(DUContext);
0974
0975     if (hadContexts.contains(this) && !searchInParents)
0976         return;
0977
0978     if (!hadContexts.contains(this)) {
0979         hadContexts[this] = true;
0980
0981         if ((type() == DUContext::Namespace || type() == DUContext::Global) && currentDepth < 1000)
0982             currentDepth += 1000;
0983
0984         {
0985             DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
0986             while (it) {
0987                 Declaration* decl = *it;
0988
0989                 if (decl && (!position.isValid() || decl->range().start <= position))
0990                     definitions << qMakePair(decl, currentDepth);
0991                 ++it;
0992             }
0993         }
0994
0995         for (int a = d->m_importedContextsSize() - 1; a >= 0; --a) {
0996             const Import* import(&d->m_importedContexts()[a]);
0997             DUContext* context = import->context(source);
0998             while (!context && a > 0) {
0999                 --a;
1000                 import = &d->m_importedContexts()[a];
1001                 context = import->context(source);
1002             }
1003             if (!context)
1004                 break;
1005
1006             if (context == this) {
1007                 qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true);
1008                 continue;
1009             }
1010
1011             if (position.isValid() && import->position.isValid() && position < import->position)
1012                 continue;
1013
1014             context->mergeDeclarationsInternal(definitions,
1015                                                CursorInRevision::invalid(), hadContexts, source,
1016                                                searchInParents && context->shouldSearchInParent(
1017                                                    InImportedParentContext) &&  context->parentContext()->type() == DUContext::Helper,
1018                                                currentDepth + 1);
1019         }
1020     }
1021
1022     ///Only respect the position if the parent-context is not a class(@todo this is language-dependent)
1023     if (parentContext() && searchInParents)
1024         parentContext()->mergeDeclarationsInternal(definitions,
1025                                                    parentContext()->type() == DUContext::Class ? parentContext()->range().end : position, hadContexts, source, searchInParents,
1026                                                    currentDepth + 1);
1027 }
1028
1029 void DUContext::deleteLocalDeclarations()
1030 {
1031     ENSURE_CAN_WRITE
1032     // It may happen that the deletion of one declaration triggers the deletion of another one
1033     // Therefore we copy the list of indexed declarations and work on those. Indexed declarations
1034     // will return zero for already deleted declarations.
1035     KDevVarLengthArray<LocalIndexedDeclaration> indexedLocal;
1036     if (d_func()->m_localDeclarations()) {
1037         indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize());
1038     }
1039     for (const LocalIndexedDeclaration& indexed : indexedLocal) {
1040         delete indexed.data(topContext());
1041     }
1042
1043     m_dynamicData->m_localDeclarations.clear();
1044 }
1045
1046 void DUContext::deleteChildContextsRecursively()
1047 {
1048     ENSURE_CAN_WRITE
1049
1050     // note: operate on copy here because child ctx deletion changes m_dynamicData->m_childContexts
1051     const auto currentChildContexts = m_dynamicData->m_childContexts;
1052     qDeleteAll(currentChildContexts);
1053
1054     m_dynamicData->m_childContexts.clear();
1055 }
1056
1057 QVector<Declaration*> DUContext::clearLocalDeclarations()
1058 {
1059     auto copy = m_dynamicData->m_localDeclarations;
1060     for (Declaration* dec : qAsConst(copy)) {
1061         dec->setContext(nullptr);
1062     }
1063
1064     return copy;
1065 }
1066
1067 QualifiedIdentifier DUContext::scopeIdentifier(bool includeClasses) const
1068 {
1069     ENSURE_CAN_READ
1070
1071     QualifiedIdentifier ret;
1072     m_dynamicData->scopeIdentifier(includeClasses, ret);
1073
1074     return ret;
1075 }
1076
1077 bool DUContext::equalScopeIdentifier(const DUContext* rhs) const
1078 {
1079     ENSURE_CAN_READ
1080
1081     const DUContext* left = this;
1082     const DUContext* right = rhs;
1083
1084     while (left || right) {
1085         if (!left || !right)
1086             return false;
1087
1088         if (!(left->d_func()->m_scopeIdentifier == right->d_func()->m_scopeIdentifier))
1089             return false;
1090
1091         left = left->parentContext();
1092         right = right->parentContext();
1093     }
1094
1095     return true;
1096 }
1097
1098 void DUContext::setLocalScopeIdentifier(const QualifiedIdentifier& identifier)
1099 {
1100     ENSURE_CAN_WRITE
1101     bool wasInSymbolTable = inSymbolTable();
1102     setInSymbolTable(false);
1103     d_func_dynamic()->m_scopeIdentifier = identifier;
1104     setInSymbolTable(wasInSymbolTable);
1105 }
1106
1107 QualifiedIdentifier DUContext::localScopeIdentifier() const
1108 {
1109     //ENSURE_CAN_READ Commented out for performance reasons
1110
1111     return d_func()->m_scopeIdentifier;
1112 }
1113
1114 IndexedQualifiedIdentifier DUContext::indexedLocalScopeIdentifier() const
1115 {
1116     return d_func()->m_scopeIdentifier;
1117 }
1118
1119 DUContext::ContextType DUContext::type() const
1120 {
1121     //ENSURE_CAN_READ This is disabled, because type() is called very often while searching, and it costs us performance
1122
1123     return d_func()->m_contextType;
1124 }
1125
1126 void DUContext::setType(ContextType type)
1127 {
1128     ENSURE_CAN_WRITE
1129
1130         d_func_dynamic()->m_contextType = type;
1131 }
1132
1133 QList<Declaration*> DUContext::findDeclarations(const Identifier& identifier, const CursorInRevision& position,
1134                                                 const TopDUContext* topContext, SearchFlags flags) const
1135 {
1136     return findDeclarations(IndexedIdentifier(identifier), position, topContext, flags);
1137 }
1138
1139 QList<Declaration*> DUContext::findDeclarations(const IndexedIdentifier& identifier, const CursorInRevision& position,
1140                                                 const TopDUContext* topContext, SearchFlags flags) const
1141 {
1142     ENSURE_CAN_READ
1143
1144     DeclarationList ret;
1145     SearchItem::PtrList identifiers;
1146     identifiers << SearchItem::Ptr(new SearchItem(false, identifier, SearchItem::PtrList()));
1147     findDeclarationsInternal(identifiers, position.isValid() ? position : range().end,
1148                              AbstractType::Ptr(), ret, topContext ? topContext : this->topContext(), flags, 0);
1149     return ret;
1150 }
1151
1152 void DUContext::deleteUse(int index)
1153 {
1154     ENSURE_CAN_WRITE
1155         DUCHAIN_D_DYNAMIC(DUContext);
1156     d->m_usesList().remove(index);
1157 }
1158
1159 void DUContext::deleteUses()
1160 {
1161     ENSURE_CAN_WRITE
1162
1163         DUCHAIN_D_DYNAMIC(DUContext);
1164     d->m_usesList().clear();
1165 }
1166
1167 void DUContext::deleteUsesRecursively()
1168 {
1169     deleteUses();
1170
1171     for (DUContext* childContext : qAsConst(m_dynamicData->m_childContexts)) {
1172         childContext->deleteUsesRecursively();
1173     }
1174 }
1175
1176 bool DUContext::inDUChain() const
1177 {
1178     if (d_func()->m_anonymousInParent || !m_dynamicData->m_parentContext)
1179         return false;
1180
1181     TopDUContext* top = topContext();
1182     return top && top->inDUChain();
1183 }
1184
1185 DUContext* DUContext::specialize(const IndexedInstantiationInformation& /*specialization*/,
1186                                  const TopDUContext* topContext, int /*upDistance*/)
1187 {
1188     if (!topContext)
1189         return nullptr;
1190     return this;
1191 }
1192
1193 CursorInRevision DUContext::importPosition(const DUContext* target) const
1194 {
1195     ENSURE_CAN_READ
1196         DUCHAIN_D(DUContext);
1197     Import import(const_cast<DUContext*>(target), this, CursorInRevision::invalid());
1198     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a)
1199         if (d->m_importedContexts()[a] == import)
1200             return d->m_importedContexts()[a].position;
1201
1202     return CursorInRevision::invalid();
1203 }
1204
1205 QVector<DUContext::Import> DUContext::importedParentContexts() const
1206 {
1207     ENSURE_CAN_READ
1208     QVector<DUContext::Import> ret;
1209     ret.reserve(d_func()->m_importedContextsSize());
1210     FOREACH_FUNCTION(const DUContext::Import& import, d_func()->m_importedContexts)
1211     ret << import;
1212     return ret;
1213 }
1214
1215 void DUContext::applyAliases(const SearchItem::PtrList& baseIdentifiers, SearchItem::PtrList& identifiers,
1216                              const CursorInRevision& position, bool canBeNamespace, bool onlyImports) const
1217 {
1218     DeclarationList imports;
1219     findLocalDeclarationsInternal(globalIndexedImportIdentifier(), position, AbstractType::Ptr(), imports,
1220                                   topContext(), DUContext::NoFiltering);
1221
1222     if (imports.isEmpty() && onlyImports) {
1223         identifiers = baseIdentifiers;
1224         return;
1225     }
1226
1227     for (const SearchItem::Ptr& identifier : baseIdentifiers) {
1228         bool addUnmodified = true;
1229
1230         if (!identifier->isExplicitlyGlobal) {
1231             if (!imports.isEmpty()) {
1232                 //We have namespace-imports.
1233                 for (Declaration* importDecl : qAsConst(imports)) {
1234                     //Search for the identifier with the import-identifier prepended
1235                     if (dynamic_cast<NamespaceAliasDeclaration*>(importDecl)) {
1236                         auto* alias = static_cast<NamespaceAliasDeclaration*>(importDecl);
1237                         identifiers.append(SearchItem::Ptr(new SearchItem(alias->importIdentifier(), identifier)));
1238                     } else {
1239                         qCDebug(LANGUAGE) << "Declaration with namespace alias identifier has the wrong type" <<
1240                             importDecl->url().str() << importDecl->range().castToSimpleRange();
1241                     }
1242                 }
1243             }
1244
1245             if (!identifier->isEmpty() && (identifier->hasNext() || canBeNamespace)) {
1246                 DeclarationList aliases;
1247                 findLocalDeclarationsInternal(identifier->identifier, position,
1248                                               AbstractType::Ptr(), imports, nullptr, DUContext::NoFiltering);
1249
1250                 if (!aliases.isEmpty()) {
1251                     //The first part of the identifier has been found as a namespace-alias.
1252                     //In c++, we only need the first alias. However, just to be correct, follow them all for now.
1253                     for (Declaration* aliasDecl : qAsConst(aliases)) {
1254                         if (!dynamic_cast<NamespaceAliasDeclaration*>(aliasDecl))
1255                             continue;
1256
1257                         addUnmodified = false; //The un-modified identifier can be ignored, because it will be replaced with the resolved alias
1258                         auto* alias = static_cast<NamespaceAliasDeclaration*>(aliasDecl);
1259
1260                         //Create an identifier where namespace-alias part is replaced with the alias target
1261                         identifiers.append(SearchItem::Ptr(new SearchItem(alias->importIdentifier(),
1262                                                                           identifier->next)));
1263                     }
1264                 }
1265             }
1266         }
1267
1268         if (addUnmodified)
1269             identifiers.append(identifier);
1270     }
1271 }
1272
1273 void DUContext::applyUpwardsAliases(SearchItem::PtrList& identifiers, const TopDUContext* /*source*/) const
1274 {
1275     if (type() == Namespace) {
1276         if (d_func()->m_scopeIdentifier.isEmpty())
1277             return;
1278
1279         //Make sure we search for the items in all namespaces of the same name, by duplicating each one with the namespace-identifier prepended.
1280         //We do this by prepending items to the current identifiers that equal the local scope identifier.
1281         SearchItem::Ptr newItem(new SearchItem(d_func()->m_scopeIdentifier.identifier()));
1282
1283         //This will exclude explicitly global identifiers
1284         newItem->addToEachNode(identifiers);
1285
1286         if (!newItem->next.isEmpty()) {
1287             //Prepend the full scope before newItem
1288             DUContext* parent = m_dynamicData->m_parentContext.data();
1289             while (parent) {
1290                 newItem = SearchItem::Ptr(new SearchItem(parent->d_func()->m_scopeIdentifier, newItem));
1291                 parent = parent->m_dynamicData->m_parentContext.data();
1292             }
1293
1294             newItem->isExplicitlyGlobal = true;
1295             identifiers.insert(0, newItem);
1296         }
1297     }
1298 }
1299
1300 bool DUContext::shouldSearchInParent(SearchFlags flags) const
1301 {
1302     return (parentContext() && parentContext()->type() == DUContext::Helper && (flags & InImportedParentContext))
1303            || !(flags & InImportedParentContext);
1304 }
1305
1306 const Use* DUContext::uses() const
1307 {
1308     ENSURE_CAN_READ
1309
1310     return d_func()->m_uses();
1311 }
1312
1313 bool DUContext::declarationHasUses(Declaration* decl)
1314 {
1315     return DUChain::uses()->hasUses(decl->id());
1316 }
1317
1318 int DUContext::usesCount() const
1319 {
1320     return d_func()->m_usesSize();
1321 }
1322
1323 bool usesRangeLessThan(const Use& left, const Use& right)
1324 {
1325     return left.m_range.start < right.m_range.start;
1326 }
1327
1328 int DUContext::createUse(int declarationIndex, const RangeInRevision& range, int insertBefore)
1329 {
1330     DUCHAIN_D_DYNAMIC(DUContext);
1331     ENSURE_CAN_WRITE
1332
1333     Use use(range, declarationIndex);
1334     if (insertBefore == -1) {
1335         //Find position where to insert
1336         const unsigned int size = d->m_usesSize();
1337         const Use* uses = d->m_uses();
1338         const Use* lowerBound = std::lower_bound(uses, uses + size, use, usesRangeLessThan);
1339         insertBefore = lowerBound - uses;
1340         // comment out to test this:
1341         /*
1342            unsigned int a = 0;
1343            for(; a < size && range.start > uses[a].m_range.start; ++a) {
1344            }
1345            Q_ASSERT(a == insertBefore);
1346          */
1347     }
1348
1349     d->m_usesList().insert(insertBefore, use);
1350
1351     return insertBefore;
1352 }
1353
1354 void DUContext::changeUseRange(int useIndex, const RangeInRevision& range)
1355 {
1356     ENSURE_CAN_WRITE
1357         d_func_dynamic()->m_usesList()[useIndex].m_range = range;
1358 }
1359
1360 void DUContext::setUseDeclaration(int useNumber, int declarationIndex)
1361 {
1362     ENSURE_CAN_WRITE
1363         d_func_dynamic()->m_usesList()[useNumber].m_declarationIndex = declarationIndex;
1364 }
1365
1366 DUContext* DUContext::findContextAt(const CursorInRevision& position, bool includeRightBorder) const
1367 {
1368     ENSURE_CAN_READ
1369
1370 //   qCDebug(LANGUAGE) << "searching" << position << "in:" << scopeIdentifier(true).toString() << range() << includeRightBorder;
1371
1372     if (!range().contains(position) && (!includeRightBorder || range().end != position)) {
1373 //     qCDebug(LANGUAGE) << "mismatch";
1374         return nullptr;
1375     }
1376
1377     const auto childContexts = m_dynamicData->m_childContexts;
1378     for (int a = childContexts.size() - 1; a >= 0; --a) {
1379         if (DUContext* specific = childContexts[a]->findContextAt(position, includeRightBorder)) {
1380             return specific;
1381         }
1382     }
1383
1384     return const_cast<DUContext*>(this);
1385 }
1386
1387 Declaration* DUContext::findDeclarationAt(const CursorInRevision& position) const
1388 {
1389     ENSURE_CAN_READ
1390
1391     if (!range().contains(position))
1392         return nullptr;
1393
1394     for (Declaration* child : qAsConst(m_dynamicData->m_localDeclarations)) {
1395         if (child->range().contains(position)) {
1396             return child;
1397         }
1398     }
1399
1400     return nullptr;
1401 }
1402
1403 DUContext* DUContext::findContextIncluding(const RangeInRevision& range) const
1404 {
1405     ENSURE_CAN_READ
1406
1407     if (!this->range().contains(range))
1408         return nullptr;
1409
1410     for (DUContext* child : qAsConst(m_dynamicData->m_childContexts)) {
1411         if (DUContext* specific = child->findContextIncluding(range)) {
1412             return specific;
1413         }
1414     }
1415
1416     return const_cast<DUContext*>(this);
1417 }
1418
1419 int DUContext::findUseAt(const CursorInRevision& position) const
1420 {
1421     ENSURE_CAN_READ
1422
1423     if (!range().contains(position))
1424         return -1;
1425
1426     for (unsigned int a = 0; a < d_func()->m_usesSize(); ++a)
1427         if (d_func()->m_uses()[a].m_range.contains(position))
1428             return a;
1429
1430     return -1;
1431 }
1432
1433 bool DUContext::inSymbolTable() const
1434 {
1435     return d_func()->m_inSymbolTable;
1436 }
1437
1438 void DUContext::setInSymbolTable(bool inSymbolTable)
1439 {
1440     d_func_dynamic()->m_inSymbolTable = inSymbolTable;
1441 }
1442
1443 void DUContext::clearImportedParentContexts()
1444 {
1445     ENSURE_CAN_WRITE
1446         DUCHAIN_D_DYNAMIC(DUContext);
1447
1448     while (d->m_importedContextsSize() != 0) {
1449         DUContext* ctx = d->m_importedContexts()[0].context(nullptr, false);
1450         if (ctx)
1451             ctx->m_dynamicData->removeImportedChildContext(this);
1452
1453         d->m_importedContextsList().removeOne(d->m_importedContexts()[0]);
1454     }
1455 }
1456
1457 void DUContext::cleanIfNotEncountered(const QSet<DUChainBase*>& encountered)
1458 {
1459     ENSURE_CAN_WRITE
1460
1461     // It may happen that the deletion of one declaration triggers the deletion of another one
1462     // Therefore we copy the list of indexed declarations and work on those. Indexed declarations
1463     // will return zero for already deleted declarations.
1464     KDevVarLengthArray<LocalIndexedDeclaration> indexedLocal;
1465     if (d_func()->m_localDeclarations()) {
1466         indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize());
1467     }
1468     for (const LocalIndexedDeclaration& indexed : indexedLocal) {
1469         auto dec = indexed.data(topContext());
1470         if (dec && !encountered.contains(dec) && (!dec->isAutoDeclaration() || !dec->hasUses())) {
1471             delete dec;
1472         }
1473     }
1474
1475     const auto currentChildContexts = m_dynamicData->m_childContexts;
1476     for (DUContext* childContext : currentChildContexts) {
1477         if (!encountered.contains(childContext)) {
1478             delete childContext;
1479         }
1480     }
1481 }
1482
1483 TopDUContext* DUContext::topContext() const
1484 {
1485     return m_dynamicData->m_topContext;
1486 }
1487
1488 AbstractNavigationWidget* DUContext::createNavigationWidget(Declaration* decl, TopDUContext* topContext,
1489                                                             AbstractNavigationWidget::DisplayHints hints) const
1490 {
1491     if (decl) {
1492         auto* widget = new AbstractNavigationWidget;
1493         widget->setDisplayHints(hints);
1494         auto* context = new AbstractDeclarationNavigationContext(DeclarationPointer(decl),
1495                                                                  TopDUContextPointer(topContext));
1496         widget->setContext(NavigationContextPointer(context));
1497         return widget;
1498     } else {
1499         return nullptr;
1500     }
1501 }
1502
1503 QVector<RangeInRevision> allUses(DUContext* context, int declarationIndex, bool noEmptyUses)
1504 {
1505     QVector<RangeInRevision> ret;
1506     for (int a = 0; a < context->usesCount(); ++a)
1507         if (context->uses()[a].m_declarationIndex == declarationIndex)
1508             if (!noEmptyUses || !context->uses()[a].m_range.isEmpty())
1509                 ret << context->uses()[a].m_range;
1510
1511     const auto childContexts = context->childContexts();
1512     for (DUContext* child : childContexts) {
1513         ret += allUses(child, declarationIndex, noEmptyUses);
1514     }
1515
1516     return ret;
1517 }
1518
1519 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const Ptr& nextItem, int start)
1520     : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false)
1521 {
1522     if (!id.isEmpty()) {
1523         if (id.count() > start)
1524             identifier = id.indexedAt(start);
1525
1526         if (id.count() > start + 1)
1527             addNext(Ptr(new SearchItem(id, nextItem, start + 1)));
1528         else if (nextItem)
1529             next.append(nextItem);
1530     } else if (nextItem) {
1531         ///If there is no prefix, just copy nextItem
1532         isExplicitlyGlobal = nextItem->isExplicitlyGlobal;
1533         identifier = nextItem->identifier;
1534         next = nextItem->next;
1535     }
1536 }
1537
1538 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const PtrList& nextItems, int start)
1539     : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false)
1540 {
1541     if (id.count() > start)
1542         identifier = id.indexedAt(start);
1543
1544     if (id.count() > start + 1)
1545         addNext(Ptr(new SearchItem(id, nextItems, start + 1)));
1546     else
1547         next = nextItems;
1548 }
1549
1550 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const PtrList& nextItems)
1551     : isExplicitlyGlobal(explicitlyGlobal)
1552     , identifier(id)
1553     , next(nextItems)
1554 {
1555 }
1556
1557 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const Ptr& nextItem)
1558     : isExplicitlyGlobal(explicitlyGlobal)
1559     , identifier(id)
1560 {
1561     next.append(nextItem);
1562 }
1563
1564 bool DUContext::SearchItem::match(const QualifiedIdentifier& id, int offset) const
1565 {
1566     if (id.isEmpty()) {
1567         if (identifier.isEmpty() && next.isEmpty())
1568             return true;
1569         else
1570             return false;
1571     }
1572
1573     if (id.at(offset) != identifier) //The identifier is different
1574         return false;
1575
1576     if (offset == id.count() - 1) {
1577         if (next.isEmpty())
1578             return true; //match
1579         else
1580             return false; //id is too short
1581     }
1582
1583     for (int a = 0; a < next.size(); ++a)
1584         if (next[a]->match(id, offset + 1))
1585             return true;
1586
1587     return false;
1588 }
1589
1590 bool DUContext::SearchItem::isEmpty() const
1591 {
1592     return identifier.isEmpty();
1593 }
1594
1595 bool DUContext::SearchItem::hasNext() const
1596 {
1597     return !next.isEmpty();
1598 }
1599
1600 QVector<QualifiedIdentifier> DUContext::SearchItem::toList(const QualifiedIdentifier& prefix) const
1601 {
1602     QVector<QualifiedIdentifier> ret;
1603
1604     QualifiedIdentifier id = prefix;
1605     if (id.isEmpty())
1606         id.setExplicitlyGlobal(isExplicitlyGlobal);
1607     if (!identifier.isEmpty())
1608         id.push(identifier);
1609
1610     if (next.isEmpty()) {
1611         ret << id;
1612     } else {
1613         for (int a = 0; a < next.size(); ++a)
1614             ret += next[a]->toList(id);
1615     }
1616     return ret;
1617 }
1618
1619 void DUContext::SearchItem::addNext(const SearchItem::Ptr& other)
1620 {
1621     next.append(other);
1622 }
1623
1624 void DUContext::SearchItem::addToEachNode(const SearchItem::Ptr& other)
1625 {
1626     if (other->isExplicitlyGlobal)
1627         return;
1628
1629     next.append(other);
1630     for (int a = 0; a < next.size() - 1; ++a)
1631         next[a]->addToEachNode(other);
1632 }
1633
1634 void DUContext::SearchItem::addToEachNode(const SearchItem::PtrList& other)
1635 {
1636     int added = 0;
1637     for (const SearchItem::Ptr& o : other) {
1638         if (!o->isExplicitlyGlobal) {
1639             next.append(o);
1640             ++added;
1641         }
1642     }
1643
1644     for (int a = 0; a < next.size() - added; ++a)
1645         next[a]->addToEachNode(other);
1646 }
1647
1648 DUContext::Import::Import(DUContext* _context, const DUContext* importer, const CursorInRevision& _position)
1649     : position(_position)
1650 {
1651     if (_context && _context->owner() &&
1652         (_context->owner()->specialization().index() ||
1653          (importer && importer->topContext() != _context->topContext()))) {
1654         m_declaration = _context->owner()->id();
1655     } else {
1656         m_context = _context;
1657     }
1658 }
1659
1660 DUContext::Import::Import(const DeclarationId& id, const CursorInRevision& _position)
1661     : position(_position)
1662     , m_declaration(id)
1663 {
1664 }
1665
1666 DUContext* DUContext::Import::context(const TopDUContext* topContext, bool instantiateIfRequired) const
1667 {
1668     if (m_declaration.isValid()) {
1669         Declaration* decl = m_declaration.declaration(topContext, instantiateIfRequired);
1670         //This first case rests on the assumption that no context will ever import a function's expression context
1671         //More accurately, that no specialized or cross-topContext imports will, but if the former assumption fails the latter will too
1672         if (auto* functionDecl = dynamic_cast<AbstractFunctionDeclaration*>(decl)) {
1673             if (functionDecl->internalFunctionContext()) {
1674                 return functionDecl->internalFunctionContext();
1675             } else {
1676                 qCWarning(LANGUAGE) << "Import of function declaration without internal function context encountered!";
1677             }
1678         }
1679         if (decl)
1680             return decl->logicalInternalContext(topContext);
1681         else
1682             return nullptr;
1683     } else {
1684         return m_context.data();
1685     }
1686 }
1687
1688 bool DUContext::Import::isDirect() const
1689 {
1690     return m_context.isValid();
1691 }
1692
1693 void DUContext::visit(DUChainVisitor& visitor)
1694 {
1695     ENSURE_CAN_READ
1696
1697     visitor.visit(this);
1698
1699     for (Declaration* decl : qAsConst(m_dynamicData->m_localDeclarations)) {
1700         visitor.visit(decl);
1701     }
1702
1703     for (DUContext* childContext : qAsConst(m_dynamicData->m_childContexts)) {
1704         childContext->visit(visitor);
1705     }
1706 }
1707
1708 static bool sortByRange(const DUChainBase* lhs, const DUChainBase* rhs)
1709 {
1710     return lhs->range() < rhs->range();
1711 }
1712
1713 void DUContext::resortLocalDeclarations()
1714 {
1715     ENSURE_CAN_WRITE
1716
1717     std::sort(m_dynamicData->m_localDeclarations.begin(), m_dynamicData->m_localDeclarations.end(), sortByRange);
1718
1719     auto top = topContext();
1720     auto& declarations = d_func_dynamic()->m_localDeclarationsList();
1721     std::sort(declarations.begin(), declarations.end(),
1722               [top](const LocalIndexedDeclaration& lhs, const LocalIndexedDeclaration& rhs) {
1723             return lhs.data(top)->range() < rhs.data(top)->range();
1724         });
1725 }
1726
1727 void DUContext::resortChildContexts()
1728 {
1729     ENSURE_CAN_WRITE
1730
1731     std::sort(m_dynamicData->m_childContexts.begin(), m_dynamicData->m_childContexts.end(), sortByRange);
1732
1733     auto top = topContext();
1734     auto& contexts = d_func_dynamic()->m_childContextsList();
1735     std::sort(contexts.begin(), contexts.end(),
1736               [top](const LocalIndexedDUContext& lhs, const LocalIndexedDUContext& rhs) {
1737             return lhs.data(top)->range() < rhs.data(top)->range();
1738         });
1739 }
1740 }