1 /*
2     SPDX-FileCopyrightText: 2006 Hamish Rodda <rodda@kde.org>
3     SPDX-FileCopyrightText: 2007-2009 David Nolden <david.nolden.kdevelop@art-master.de>
4 
5     SPDX-License-Identifier: LGPL-2.0-only
6 */
7 
8 #include "ducontext.h"
9 
10 #include <limits>
11 #include <algorithm>
12 
13 #include <QSet>
14 
15 #include "ducontextdata.h"
16 #include "declaration.h"
17 #include "duchain.h"
18 #include "duchainlock.h"
19 #include "use.h"
20 #include "identifier.h"
21 #include "topducontext.h"
22 #include "persistentsymboltable.h"
23 #include "aliasdeclaration.h"
24 #include "namespacealiasdeclaration.h"
25 #include "abstractfunctiondeclaration.h"
26 #include "duchainregister.h"
27 #include "topducontextdynamicdata.h"
28 #include "importers.h"
29 #include "uses.h"
30 #include "navigation/abstractdeclarationnavigationcontext.h"
31 #include "navigation/abstractnavigationwidget.h"
32 #include "ducontextdynamicdata.h"
33 #include <debug.h>
34 
35 // maximum depth for DUContext::findDeclarationsInternal searches
36 const uint maxParentDepth = 20;
37 
38 using namespace KTextEditor;
39 
40 #ifndef NDEBUG
41 #define ENSURE_CAN_WRITE_(x) {if (x->inDUChain()) { ENSURE_CHAIN_WRITE_LOCKED }}
42 #define ENSURE_CAN_READ_(x) {if (x->inDUChain()) { ENSURE_CHAIN_READ_LOCKED }}
43 #else
44 #define ENSURE_CAN_WRITE_(x)
45 #define ENSURE_CAN_READ_(x)
46 #endif
47 
operator <<(QDebug dbg,const KDevelop::DUContext::Import & import)48 QDebug operator<<(QDebug dbg, const KDevelop::DUContext::Import& import)
49 {
50     QDebugStateSaver saver(dbg);
51     dbg.nospace() << "Import(" << import.indexedContext().data() << ')';
52     return dbg;
53 }
54 
55 namespace KDevelop {
56 DEFINE_LIST_MEMBER_HASH(DUContextData, m_childContexts, LocalIndexedDUContext)
57 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importers, IndexedDUContext)
58 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importedContexts, DUContext::Import)
59 DEFINE_LIST_MEMBER_HASH(DUContextData, m_localDeclarations, LocalIndexedDeclaration)
60 DEFINE_LIST_MEMBER_HASH(DUContextData, m_uses, Use)
61 
62 REGISTER_DUCHAIN_ITEM(DUContext);
63 
~DUChainVisitor()64 DUChainVisitor::~DUChainVisitor()
65 {
66 }
67 
68 /**
69  * We leak here, to prevent a possible crash during destruction, as the destructor
70  * of Identifier is not safe to be called after the duchain has been destroyed
71  */
globalImportIdentifier()72 const Identifier& globalImportIdentifier()
73 {
74     static const Identifier globalImportIdentifierObject(QStringLiteral("{...import...}"));
75     return globalImportIdentifierObject;
76 }
77 
globalAliasIdentifier()78 const Identifier& globalAliasIdentifier()
79 {
80     static const Identifier globalAliasIdentifierObject(QStringLiteral("{...alias...}"));
81     return globalAliasIdentifierObject;
82 }
83 
globalIndexedImportIdentifier()84 const IndexedIdentifier& globalIndexedImportIdentifier()
85 {
86     static const IndexedIdentifier id(globalImportIdentifier());
87     return id;
88 }
89 
globalIndexedAliasIdentifier()90 const IndexedIdentifier& globalIndexedAliasIdentifier()
91 {
92     static const IndexedIdentifier id(globalAliasIdentifier());
93     return id;
94 }
95 
rebuildDynamicData(DUContext * parent,uint ownIndex)96 void DUContext::rebuildDynamicData(DUContext* parent, uint ownIndex)
97 {
98     Q_ASSERT(!parent || ownIndex);
99     m_dynamicData->m_topContext = parent ? parent->topContext() : static_cast<TopDUContext*>(this);
100     m_dynamicData->m_indexInTopContext = ownIndex;
101     m_dynamicData->m_parentContext = DUContextPointer(parent);
102     m_dynamicData->m_context = this;
103 
104     m_dynamicData->m_childContexts.clear();
105     m_dynamicData->m_childContexts.reserve(d_func()->m_childContextsSize());
106     FOREACH_FUNCTION(const LocalIndexedDUContext &ctx, d_func()->m_childContexts) {
107         m_dynamicData->m_childContexts << ctx.data(m_dynamicData->m_topContext);
108     }
109 
110     m_dynamicData->m_localDeclarations.clear();
111     m_dynamicData->m_localDeclarations.reserve(d_func()->m_localDeclarationsSize());
112     FOREACH_FUNCTION(const LocalIndexedDeclaration &idx, d_func()->m_localDeclarations) {
113         auto declaration = idx.data(m_dynamicData->m_topContext);
114         if (!declaration) {
115             qCWarning(LANGUAGE) << "child declaration number" << idx.localIndex() << "of" <<
116                 d_func_dynamic()->m_localDeclarationsSize() << "is invalid";
117             continue;
118         }
119         m_dynamicData->m_localDeclarations << declaration;
120     }
121 
122     DUChainBase::rebuildDynamicData(parent, ownIndex);
123 }
124 
DUContextData()125 DUContextData::DUContextData()
126     : m_inSymbolTable(false)
127     , m_anonymousInParent(false)
128     , m_propagateDeclarations(false)
129 {
130     initializeAppendedLists();
131 }
132 
~DUContextData()133 DUContextData::~DUContextData()
134 {
135     freeAppendedLists();
136 }
137 
DUContextData(const DUContextData & rhs)138 DUContextData::DUContextData(const DUContextData& rhs)
139     : DUChainBaseData(rhs)
140     , m_inSymbolTable(rhs.m_inSymbolTable)
141     , m_anonymousInParent(rhs.m_anonymousInParent)
142     , m_propagateDeclarations(rhs.m_propagateDeclarations)
143 {
144     initializeAppendedLists();
145     copyListsFrom(rhs);
146     m_scopeIdentifier = rhs.m_scopeIdentifier;
147     m_contextType = rhs.m_contextType;
148     m_owner = rhs.m_owner;
149 }
150 
DUContextDynamicData(DUContext * d)151 DUContextDynamicData::DUContextDynamicData(DUContext* d)
152     : m_topContext(nullptr)
153     , m_indexInTopContext(0)
154     , m_context(d)
155 {
156 }
157 
scopeIdentifier(bool includeClasses,QualifiedIdentifier & target) const158 void DUContextDynamicData::scopeIdentifier(bool includeClasses, QualifiedIdentifier& target) const
159 {
160     if (m_parentContext)
161         m_parentContext->m_dynamicData->scopeIdentifier(includeClasses, target);
162 
163     if (includeClasses || d_func()->m_contextType != DUContext::Class)
164         target += d_func()->m_scopeIdentifier;
165 }
166 
imports(const DUContext * context,const TopDUContext * source,QSet<const DUContextDynamicData * > * recursionGuard) const167 bool DUContextDynamicData::imports(const DUContext* context, const TopDUContext* source,
168                                    QSet<const DUContextDynamicData*>* recursionGuard) const
169 {
170     if (this == context->m_dynamicData)
171         return true;
172 
173     if (recursionGuard->contains(this)) {
174         return false;
175     }
176     recursionGuard->insert(this);
177 
178     FOREACH_FUNCTION(const DUContext::Import& ctx, d_func()->m_importedContexts) {
179         DUContext* import = ctx.context(source);
180         if (import == context || (import && import->m_dynamicData->imports(context, source, recursionGuard)))
181             return true;
182     }
183 
184     return false;
185 }
186 
isContextTemporary(uint index)187 inline bool isContextTemporary(uint index)
188 {
189     return index > (0xffffffff / 2);
190 }
191 
addDeclaration(Declaration * newDeclaration)192 void DUContextDynamicData::addDeclaration(Declaration* newDeclaration)
193 {
194     // The definition may not have its identifier set when it's assigned...
195     // allow dupes here, TODO catch the error elsewhere
196 
197     //If this context is temporary, added declarations should be as well, and viceversa
198     Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(newDeclaration->ownIndex()));
199 
200     CursorInRevision start = newDeclaration->range().start;
201 
202     bool inserted = false;
203     ///@todo Do binary search to find the position
204     for (int i = m_localDeclarations.size() - 1; i >= 0; --i) {
205         Declaration* child = m_localDeclarations[i];
206         Q_ASSERT(d_func()->m_localDeclarations()[i].data(m_topContext) == child);
207         if (child == newDeclaration)
208             return;
209         //TODO: All declarations in a macro will have the same empty range, and just get appended
210         //that may not be Good Enough in complex cases.
211         if (start >= child->range().start) {
212             m_localDeclarations.insert(i + 1, newDeclaration);
213             d_func_dynamic()->m_localDeclarationsList().insert(i + 1, newDeclaration);
214             Q_ASSERT(d_func()->m_localDeclarations()[i + 1].data(m_topContext) == newDeclaration);
215 
216             inserted = true;
217             break;
218         }
219     }
220 
221     if (!inserted) {
222         // We haven't found any child that is before this one, so prepend it
223         m_localDeclarations.insert(0, newDeclaration);
224         d_func_dynamic()->m_localDeclarationsList().insert(0, newDeclaration);
225         Q_ASSERT(d_func()->m_localDeclarations()[0].data(m_topContext) == newDeclaration);
226     }
227 }
228 
removeDeclaration(Declaration * declaration)229 bool DUContextDynamicData::removeDeclaration(Declaration* declaration)
230 {
231     const int idx = m_localDeclarations.indexOf(declaration);
232     if (idx != -1) {
233         Q_ASSERT(d_func()->m_localDeclarations()[idx].data(m_topContext) == declaration);
234         m_localDeclarations.remove(idx);
235         d_func_dynamic()->m_localDeclarationsList().remove(idx);
236         return true;
237     } else {
238         Q_ASSERT(d_func_dynamic()->m_localDeclarationsList().indexOf(LocalIndexedDeclaration(declaration)) == -1);
239         return false;
240     }
241 }
242 
addChildContext(DUContext * context)243 void DUContextDynamicData::addChildContext(DUContext* context)
244 {
245     // Internal, don't need to assert a lock
246     Q_ASSERT(!context->m_dynamicData->m_parentContext
247              || context->m_dynamicData->m_parentContext.data()->m_dynamicData == this);
248 
249     LocalIndexedDUContext indexed(context->m_dynamicData->m_indexInTopContext);
250 
251     //If this context is temporary, added declarations should be as well, and viceversa
252     Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(indexed.localIndex()));
253 
254     bool inserted = false;
255 
256     int childCount = m_childContexts.size();
257 
258     for (int i = childCount - 1; i >= 0; --i) {///@todo Do binary search to find the position
259         DUContext* child = m_childContexts[i];
260         Q_ASSERT(d_func_dynamic()->m_childContexts()[i] == LocalIndexedDUContext(child));
261         if (context == child)
262             return;
263         if (context->range().start >= child->range().start) {
264             m_childContexts.insert(i + 1, context);
265             d_func_dynamic()->m_childContextsList().insert(i + 1, indexed);
266             context->m_dynamicData->m_parentContext = m_context;
267             inserted = true;
268             break;
269         }
270     }
271 
272     if (!inserted) {
273         m_childContexts.insert(0, context);
274         d_func_dynamic()->m_childContextsList().insert(0, indexed);
275         context->m_dynamicData->m_parentContext = m_context;
276     }
277 }
278 
removeChildContext(DUContext * context)279 bool DUContextDynamicData::removeChildContext(DUContext* context)
280 {
281 //   ENSURE_CAN_WRITE
282 
283     const int idx = m_childContexts.indexOf(context);
284     if (idx != -1) {
285         m_childContexts.remove(idx);
286         Q_ASSERT(d_func()->m_childContexts()[idx] == LocalIndexedDUContext(context));
287         d_func_dynamic()->m_childContextsList().remove(idx);
288         return true;
289     } else {
290         Q_ASSERT(d_func_dynamic()->m_childContextsList().indexOf(LocalIndexedDUContext(context)) == -1);
291         return false;
292     }
293 }
294 
addImportedChildContext(DUContext * context)295 void DUContextDynamicData::addImportedChildContext(DUContext* context)
296 {
297 //   ENSURE_CAN_WRITE
298     DUContext::Import import(m_context, context);
299 
300     if (import.isDirect()) {
301         //Direct importers are registered directly within the data
302         if (d_func_dynamic()->m_importersList().contains(IndexedDUContext(context))) {
303             qCDebug(LANGUAGE) << m_context->scopeIdentifier(true).toString() << "importer added multiple times:" <<
304                 context->scopeIdentifier(true).toString();
305             return;
306         }
307 
308         d_func_dynamic()->m_importersList().append(context);
309     } else {
310         //Indirect importers are registered separately
311         Importers::self().addImporter(import.indirectDeclarationId(), IndexedDUContext(context));
312     }
313 }
314 
315 //Can also be called with a context that is not in the list
removeImportedChildContext(DUContext * context)316 void DUContextDynamicData::removeImportedChildContext(DUContext* context)
317 {
318 //   ENSURE_CAN_WRITE
319     DUContext::Import import(m_context, context);
320 
321     if (import.isDirect()) {
322         d_func_dynamic()->m_importersList().removeOne(IndexedDUContext(context));
323     } else {
324         //Indirect importers are registered separately
325         Importers::self().removeImporter(import.indirectDeclarationId(), IndexedDUContext(context));
326     }
327 }
328 
depth() const329 int DUContext::depth() const
330 {
331     if (!parentContext()) {
332         return 0;
333     }
334 
335     return parentContext()->depth() + 1;
336 }
337 
DUContext(DUContextData & data)338 DUContext::DUContext(DUContextData& data)
339     : DUChainBase(data)
340     , m_dynamicData(new DUContextDynamicData(this))
341 {
342 }
343 
DUContext(const RangeInRevision & range,DUContext * parent,bool anonymous)344 DUContext::DUContext(const RangeInRevision& range, DUContext* parent, bool anonymous)
345     : DUChainBase(*new DUContextData(), range)
346     , m_dynamicData(new DUContextDynamicData(this))
347 {
348     d_func_dynamic()->setClassId(this);
349     if (parent)
350         m_dynamicData->m_topContext = parent->topContext();
351 
352     d_func_dynamic()->setClassId(this);
353     DUCHAIN_D_DYNAMIC(DUContext);
354     d->m_contextType = Other;
355     m_dynamicData->m_parentContext = nullptr;
356 
357     d->m_anonymousInParent = anonymous;
358     d->m_inSymbolTable = false;
359 
360     if (parent) {
361         m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this,
362                                                                                                        parent->isAnonymous() ||
363                                                                                                        anonymous);
364         Q_ASSERT(m_dynamicData->m_indexInTopContext);
365 
366         if (!anonymous)
367             parent->m_dynamicData->addChildContext(this);
368         else
369             m_dynamicData->m_parentContext = parent;
370     }
371 
372     if (parent && !anonymous && parent->inSymbolTable())
373         setInSymbolTable(true);
374 }
375 
isAnonymous() const376 bool DUContext::isAnonymous() const
377 {
378     return d_func()->m_anonymousInParent ||
379            (m_dynamicData->m_parentContext && m_dynamicData->m_parentContext->isAnonymous());
380 }
381 
initFromTopContext()382 void DUContext::initFromTopContext()
383 {
384     Q_ASSERT(dynamic_cast<TopDUContext*>(this));
385     m_dynamicData->m_topContext = static_cast<TopDUContext*>(this);
386 }
387 
DUContext(DUContextData & dd,const RangeInRevision & range,DUContext * parent,bool anonymous)388 DUContext::DUContext(DUContextData& dd, const RangeInRevision& range, DUContext* parent, bool anonymous)
389     : DUChainBase(dd, range)
390     , m_dynamicData(new DUContextDynamicData(this))
391 {
392     if (parent)
393         m_dynamicData->m_topContext = parent->topContext();
394     // else initTopContext must be called, doing a static_cast here is UB
395 
396     DUCHAIN_D_DYNAMIC(DUContext);
397     d->m_contextType = Other;
398     m_dynamicData->m_parentContext = nullptr;
399     d->m_inSymbolTable = false;
400     d->m_anonymousInParent = anonymous;
401     if (parent) {
402         m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this,
403                                                                                                        parent->isAnonymous() ||
404                                                                                                        anonymous);
405 
406         if (!anonymous)
407             parent->m_dynamicData->addChildContext(this);
408         else
409             m_dynamicData->m_parentContext = parent;
410     }
411 }
412 
DUContext(DUContext & useDataFrom)413 DUContext::DUContext(DUContext& useDataFrom)
414     : DUChainBase(useDataFrom)
415     , m_dynamicData(useDataFrom.m_dynamicData)
416 {
417 }
418 
~DUContext()419 DUContext::~DUContext()
420 {
421     TopDUContext* top = topContext();
422 
423     if (top != this) {
424         const auto doCleanup = !top->deleting() || !top->isOnDisk();
425 
426         if (doCleanup) {
427             DUCHAIN_D_DYNAMIC(DUContext);
428 
429             if (d->m_owner.declaration())
430                 d->m_owner.declaration()->setInternalContext(nullptr);
431 
432             while (d->m_importersSize() != 0) {
433                 if (d->m_importers()[0].data())
434                     d->m_importers()[0].data()->removeImportedParentContext(this);
435                 else {
436                     qCDebug(LANGUAGE) << "importer disappeared";
437                     d->m_importersList().removeOne(d->m_importers()[0]);
438                 }
439             }
440 
441             clearImportedParentContexts();
442         }
443 
444         deleteChildContextsRecursively();
445 
446         if (doCleanup)
447             deleteUses();
448 
449         deleteLocalDeclarations();
450 
451         //If the top-context is being delete, we don't need to spend time rebuilding the inner structure.
452         //That's expensive, especially when the data is not dynamic.
453         if (doCleanup && m_dynamicData->m_parentContext) {
454             m_dynamicData->m_parentContext->m_dynamicData->removeChildContext(this);
455         }
456 
457         top->m_dynamicData->clearContextIndex(this);
458 
459         Q_ASSERT(d_func()->isDynamic() ==
460                 (doCleanup ||
461                 top->m_dynamicData->isTemporaryContextIndex(m_dynamicData->m_indexInTopContext)));
462     }
463 
464     delete m_dynamicData;
465 }
466 
childContexts() const467 QVector<DUContext*> DUContext::childContexts() const
468 {
469     ENSURE_CAN_READ
470 
471     return m_dynamicData->m_childContexts;
472 }
473 
owner() const474 Declaration* DUContext::owner() const
475 {
476     ENSURE_CAN_READ
477     return d_func()->m_owner.declaration();
478 }
479 
setOwner(Declaration * owner)480 void DUContext::setOwner(Declaration* owner)
481 {
482     ENSURE_CAN_WRITE
483         DUCHAIN_D_DYNAMIC(DUContext);
484     if (owner == d->m_owner.declaration())
485         return;
486 
487     Declaration* oldOwner = d->m_owner.declaration();
488 
489     d->m_owner = owner;
490 
491     //Q_ASSERT(!oldOwner || oldOwner->internalContext() == this);
492     if (oldOwner && oldOwner->internalContext() == this)
493         oldOwner->setInternalContext(nullptr);
494 
495     //The context set as internal context should always be the last opened context
496     if (owner)
497         owner->setInternalContext(this);
498 }
499 
parentContext() const500 DUContext* DUContext::parentContext() const
501 {
502     //ENSURE_CAN_READ Commented out for performance reasons
503 
504     return m_dynamicData->m_parentContext.data();
505 }
506 
setPropagateDeclarations(bool propagate)507 void DUContext::setPropagateDeclarations(bool propagate)
508 {
509     ENSURE_CAN_WRITE
510         DUCHAIN_D_DYNAMIC(DUContext);
511 
512     if (propagate == d->m_propagateDeclarations)
513         return;
514 
515     d->m_propagateDeclarations = propagate;
516 }
517 
isPropagateDeclarations() const518 bool DUContext::isPropagateDeclarations() const
519 {
520     return d_func()->m_propagateDeclarations;
521 }
522 
findLocalDeclarations(const IndexedIdentifier & identifier,const CursorInRevision & position,const TopDUContext * topContext,const AbstractType::Ptr & dataType,SearchFlags flags) const523 QList<Declaration*> DUContext::findLocalDeclarations(const IndexedIdentifier& identifier,
524                                                      const CursorInRevision& position,
525                                                      const TopDUContext* topContext,
526                                                      const AbstractType::Ptr& dataType,
527                                                      SearchFlags flags) const
528 {
529     ENSURE_CAN_READ
530 
531     DeclarationList ret;
532     findLocalDeclarationsInternal(identifier,
533                                   position.isValid() ? position : range().end, dataType, ret,
534                                   topContext ? topContext : this->topContext(), flags);
535     return ret;
536 }
537 
findLocalDeclarations(const Identifier & identifier,const CursorInRevision & position,const TopDUContext * topContext,const AbstractType::Ptr & dataType,SearchFlags flags) const538 QList<Declaration*> DUContext::findLocalDeclarations(const Identifier& identifier,
539                                                      const CursorInRevision& position,
540                                                      const TopDUContext* topContext,
541                                                      const AbstractType::Ptr& dataType,
542                                                      SearchFlags flags) const
543 {
544     return findLocalDeclarations(IndexedIdentifier(identifier), position, topContext, dataType, flags);
545 }
546 
547 namespace {
contextIsChildOrEqual(const DUContext * childContext,const DUContext * context)548 bool contextIsChildOrEqual(const DUContext* childContext, const DUContext* context)
549 {
550     if (childContext == context)
551         return true;
552 
553     if (childContext->parentContext())
554         return contextIsChildOrEqual(childContext->parentContext(), context);
555     else
556         return false;
557 }
558 
559 struct Checker
560 {
CheckerKDevelop::__anon3d1413480111::Checker561     Checker(DUContext::SearchFlags flags, const AbstractType::Ptr& dataType,
562             const CursorInRevision& position, DUContext::ContextType ownType)
563         : m_flags(flags)
564         , m_dataType(dataType)
565         , m_position(position)
566         , m_ownType(ownType)
567     {
568     }
569 
checkKDevelop::__anon3d1413480111::Checker570     Declaration* check(Declaration* declaration) const
571     {
572         ///@todo This is C++-specific
573         if (m_ownType != DUContext::Class && m_ownType != DUContext::Template
574             && m_position.isValid() && m_position <= declaration->range().start) {
575             return nullptr;
576         }
577 
578         if (declaration->kind() == Declaration::Alias && !(m_flags & DUContext::DontResolveAliases)) {
579             //Apply alias declarations
580             auto* alias = static_cast<AliasDeclaration*>(declaration);
581             if (alias->aliasedDeclaration().isValid()) {
582                 declaration = alias->aliasedDeclaration().declaration();
583             } else {
584                 qCDebug(LANGUAGE) << "lost aliased declaration";
585             }
586         }
587 
588         if (declaration->kind() == Declaration::NamespaceAlias && !(m_flags & DUContext::NoFiltering)) {
589             return nullptr;
590         }
591 
592         if (( m_flags& DUContext::OnlyFunctions ) && !declaration->isFunctionDeclaration()) {
593             return nullptr;
594         }
595 
596         if (m_dataType && m_dataType->indexed() != declaration->indexedType()) {
597             return nullptr;
598         }
599 
600         return declaration;
601     }
602 
603     DUContext::SearchFlags m_flags;
604     const AbstractType::Ptr m_dataType;
605     const CursorInRevision m_position;
606     DUContext::ContextType m_ownType;
607 };
608 }
609 
findLocalDeclarationsInternal(const Identifier & identifier,const CursorInRevision & position,const AbstractType::Ptr & dataType,DeclarationList & ret,const TopDUContext * source,SearchFlags flags) const610 void DUContext::findLocalDeclarationsInternal(const Identifier& identifier, const CursorInRevision& position,
611                                               const AbstractType::Ptr& dataType, DeclarationList& ret,
612                                               const TopDUContext* source, SearchFlags flags) const
613 {
614     findLocalDeclarationsInternal(IndexedIdentifier(identifier), position, dataType, ret, source, flags);
615 }
616 
findLocalDeclarationsInternal(const IndexedIdentifier & identifier,const CursorInRevision & position,const AbstractType::Ptr & dataType,DeclarationList & ret,const TopDUContext *,SearchFlags flags) const617 void DUContext::findLocalDeclarationsInternal(const IndexedIdentifier& identifier,
618                                               const CursorInRevision& position,
619                                               const AbstractType::Ptr& dataType,
620                                               DeclarationList& ret, const TopDUContext* /*source*/,
621                                               SearchFlags flags) const
622 {
623     Checker checker(flags, dataType, position, type());
624 
625     DUCHAIN_D(DUContext);
626     if (d->m_inSymbolTable && !d->m_scopeIdentifier.isEmpty() && !identifier.isEmpty()) {
627         //This context is in the symbol table, use the symbol-table to speed up the search
628         QualifiedIdentifier id(scopeIdentifier(true) + identifier);
629 
630         TopDUContext* top = topContext();
631 
632         uint count;
633         const IndexedDeclaration* declarations;
634         PersistentSymbolTable::self().declarations(id, count, declarations);
635         for (uint a = 0; a < count; ++a) {
636             ///@todo Eventually do efficient iteration-free filtering
637             if (declarations[a].topContextIndex() == top->ownIndex()) {
638                 Declaration* decl = declarations[a].declaration();
639                 if (decl && contextIsChildOrEqual(decl->context(), this)) {
640                     Declaration* checked = checker.check(decl);
641                     if (checked) {
642                         ret.append(checked);
643                     }
644                 }
645             }
646         }
647     } else {
648         //Iterate through all declarations
649         DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
650         while (it) {
651             Declaration* declaration = *it;
652             if (declaration && declaration->indexedIdentifier() == identifier) {
653                 Declaration* checked = checker.check(declaration);
654                 if (checked)
655                     ret.append(checked);
656             }
657             ++it;
658         }
659     }
660 }
661 
foundEnough(const DeclarationList & ret,SearchFlags flags) const662 bool DUContext::foundEnough(const DeclarationList& ret, SearchFlags flags) const
663 {
664     if (!ret.isEmpty() && !(flags & DUContext::NoFiltering))
665         return true;
666     else
667         return false;
668 }
669 
findDeclarationsInternal(const SearchItem::PtrList & baseIdentifiers,const CursorInRevision & position,const AbstractType::Ptr & dataType,DeclarationList & ret,const TopDUContext * source,SearchFlags flags,uint depth) const670 bool DUContext::findDeclarationsInternal(const SearchItem::PtrList& baseIdentifiers,
671                                          const CursorInRevision& position,
672                                          const AbstractType::Ptr& dataType,
673                                          DeclarationList& ret, const TopDUContext* source,
674                                          SearchFlags flags, uint depth) const
675 {
676     if (depth > maxParentDepth) {
677         qCDebug(LANGUAGE) << "maximum depth reached in" << scopeIdentifier(true);
678         return false;
679     }
680 
681     DUCHAIN_D(DUContext);
682     if (d->m_contextType != Namespace) {
683         // 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.
684         for (auto& baseIdentifier : baseIdentifiers) {
685             if (!baseIdentifier->isExplicitlyGlobal && baseIdentifier->next.isEmpty()) {
686                 // It makes no sense searching locally for qualified identifiers
687                 findLocalDeclarationsInternal(baseIdentifier->identifier, position, dataType, ret, source, flags);
688             }
689         }
690 
691         if (foundEnough(ret, flags)) {
692             return true;
693         }
694     }
695 
696     ///Step 1: Apply namespace-aliases and -imports
697     SearchItem::PtrList aliasedIdentifiers;
698     //Because of namespace-imports and aliases, this identifier may need to be searched under multiple names
699     applyAliases(baseIdentifiers, aliasedIdentifiers, position, false,
700                  type() != DUContext::Namespace && type() != DUContext::Global);
701 
702     if (d->m_importedContextsSize() != 0) {
703         ///Step 2: Give identifiers that are not marked as explicitly-global to imported contexts(explicitly global ones are treatead in TopDUContext)
704         SearchItem::PtrList nonGlobalIdentifiers;
705         for (const SearchItem::Ptr& identifier : qAsConst(aliasedIdentifiers)) {
706             if (!identifier->isExplicitlyGlobal) {
707                 nonGlobalIdentifiers << identifier;
708             }
709         }
710 
711         if (!nonGlobalIdentifiers.isEmpty()) {
712             const auto& url = this->url();
713             for (int import = d->m_importedContextsSize() - 1; import >= 0; --import) {
714                 if (position.isValid() && d->m_importedContexts()[import].position.isValid() &&
715                     position < d->m_importedContexts()[import].position) {
716                     continue;
717                 }
718 
719                 DUContext* context = d->m_importedContexts()[import].context(source);
720 
721                 if (!context) {
722                     continue;
723                 } else if (context == this) {
724                     qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true);
725                     continue;
726                 }
727 
728                 if (!context->findDeclarationsInternal(nonGlobalIdentifiers,
729                                                        url == context->url() ? position : context->range().end,
730                                                        dataType, ret, source, flags | InImportedParentContext,
731                                                        depth + 1)) {
732                     return false;
733                 }
734             }
735         }
736     }
737 
738     if (foundEnough(ret, flags)) {
739         return true;
740     }
741 
742     ///Step 3: Continue search in parent-context
743     if (!(flags & DontSearchInParent) && shouldSearchInParent(flags) && m_dynamicData->m_parentContext) {
744         applyUpwardsAliases(aliasedIdentifiers, source);
745         return m_dynamicData->m_parentContext->findDeclarationsInternal(aliasedIdentifiers,
746                                                                         url() == m_dynamicData->m_parentContext->url() ? position : m_dynamicData->m_parentContext->range().end,
747                                                                         dataType, ret, source, flags, depth);
748     }
749     return true;
750 }
751 
fullyApplyAliases(const QualifiedIdentifier & id,const TopDUContext * source) const752 QVector<QualifiedIdentifier> DUContext::fullyApplyAliases(const QualifiedIdentifier& id,
753                                                           const TopDUContext* source) const
754 {
755     ENSURE_CAN_READ
756 
757     if (!source)
758         source = topContext();
759 
760     SearchItem::PtrList identifiers;
761     identifiers << SearchItem::Ptr(new SearchItem(id));
762 
763     const DUContext* current = this;
764     while (current) {
765         SearchItem::PtrList aliasedIdentifiers;
766         current->applyAliases(identifiers, aliasedIdentifiers, CursorInRevision::invalid(), true, false);
767         current->applyUpwardsAliases(identifiers, source);
768 
769         current = current->parentContext();
770     }
771 
772     QVector<QualifiedIdentifier> ret;
773     for (const SearchItem::Ptr& item : qAsConst(identifiers)) {
774         ret += item->toList();
775     }
776 
777     return ret;
778 }
779 
findDeclarations(const QualifiedIdentifier & identifier,const CursorInRevision & position,const AbstractType::Ptr & dataType,const TopDUContext * topContext,SearchFlags flags) const780 QList<Declaration*> DUContext::findDeclarations(const QualifiedIdentifier& identifier,
781                                                 const CursorInRevision& position,
782                                                 const AbstractType::Ptr& dataType,
783                                                 const TopDUContext* topContext, SearchFlags flags) const
784 {
785     ENSURE_CAN_READ
786 
787     DeclarationList ret;
788     // optimize: we don't want to allocate the top node always
789     // so create it on stack but ref it so its not deleted by the smart pointer
790     SearchItem item(identifier);
791     item.ref.ref();
792 
793     SearchItem::PtrList identifiers{SearchItem::Ptr(&item)};
794 
795     findDeclarationsInternal(identifiers,
796                              position.isValid() ? position : range().end, dataType, ret,
797                              topContext ? topContext : this->topContext(), flags, 0);
798 
799     return ret;
800 }
801 
imports(const DUContext * origin,const CursorInRevision &) const802 bool DUContext::imports(const DUContext* origin, const CursorInRevision& /*position*/) const
803 {
804     ENSURE_CAN_READ
805 
806     QSet<const DUContextDynamicData*> recursionGuard;
807     recursionGuard.reserve(8);
808     return m_dynamicData->imports(origin, topContext(), &recursionGuard);
809 }
810 
addIndirectImport(const DUContext::Import & import)811 bool DUContext::addIndirectImport(const DUContext::Import& import)
812 {
813     ENSURE_CAN_WRITE
814         DUCHAIN_D_DYNAMIC(DUContext);
815 
816     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
817         if (d->m_importedContexts()[a] == import) {
818             d->m_importedContextsList()[a].position = import.position;
819             return true;
820         }
821     }
822 
823     ///Do not sort the imported contexts by their own line-number, it makes no sense.
824     ///Contexts added first, aka template-contexts, should stay in first place, so they are searched first.
825 
826     d->m_importedContextsList().append(import);
827     return false;
828 }
829 
addImportedParentContext(DUContext * context,const CursorInRevision & position,bool anonymous,bool)830 void DUContext::addImportedParentContext(DUContext* context, const CursorInRevision& position, bool anonymous,
831                                          bool /*temporary*/)
832 {
833     ENSURE_CAN_WRITE
834 
835     if (context == this) {
836         qCDebug(LANGUAGE) << "Tried to import self";
837         return;
838     }
839     if (!context) {
840         qCDebug(LANGUAGE) << "Tried to import invalid context";
841         return;
842     }
843 
844     Import import(context, this, position);
845     if (addIndirectImport(import))
846         return;
847 
848     if (!anonymous) {
849         ENSURE_CAN_WRITE_(context)
850         context->m_dynamicData->addImportedChildContext(this);
851     }
852 }
853 
removeImportedParentContext(DUContext * context)854 void DUContext::removeImportedParentContext(DUContext* context)
855 {
856     ENSURE_CAN_WRITE
857         DUCHAIN_D_DYNAMIC(DUContext);
858 
859     Import import(context, this, CursorInRevision::invalid());
860 
861     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
862         if (d->m_importedContexts()[a] == import) {
863             d->m_importedContextsList().remove(a);
864             break;
865         }
866     }
867 
868     if (!context)
869         return;
870 
871     context->m_dynamicData->removeImportedChildContext(this);
872 }
873 
indexedImporters() const874 KDevVarLengthArray<IndexedDUContext> DUContext::indexedImporters() const
875 {
876     KDevVarLengthArray<IndexedDUContext> ret;
877     if (owner())
878         ret = Importers::self().importers(owner()->id()); //Add indirect importers to the list
879 
880     FOREACH_FUNCTION(const IndexedDUContext &ctx, d_func()->m_importers)
881     ret.append(ctx);
882 
883     return ret;
884 }
885 
importers() const886 QVector<DUContext*> DUContext::importers() const
887 {
888     ENSURE_CAN_READ
889 
890     QVector<DUContext*> ret;
891     ret.reserve(d_func()->m_importersSize());
892     FOREACH_FUNCTION(const IndexedDUContext &ctx, d_func()->m_importers)
893     ret << ctx.context();
894 
895     if (owner()) {
896         //Add indirect importers to the list
897         const KDevVarLengthArray<IndexedDUContext> indirect = Importers::self().importers(owner()->id());
898         ret.reserve(ret.size() + indirect.size());
899         for (const IndexedDUContext ctx : indirect) {
900             ret << ctx.context();
901         }
902     }
903 
904     return ret;
905 }
906 
findContext(const CursorInRevision & position,DUContext * parent) const907 DUContext* DUContext::findContext(const CursorInRevision& position, DUContext* parent) const
908 {
909     ENSURE_CAN_READ
910 
911     if (!parent)
912         parent = const_cast<DUContext*>(this);
913 
914     for (DUContext* context : qAsConst(parent->m_dynamicData->m_childContexts)) {
915         if (context->range().contains(position)) {
916             DUContext* ret = findContext(position, context);
917             if (!ret) {
918                 ret = context;
919             }
920 
921             return ret;
922         }
923     }
924 
925     return nullptr;
926 }
927 
parentContextOf(DUContext * context) const928 bool DUContext::parentContextOf(DUContext* context) const
929 {
930     if (this == context)
931         return true;
932 
933     const auto& childContexts = m_dynamicData->m_childContexts;
934     return std::any_of(childContexts.begin(), childContexts.end(), [&](DUContext* child) {
935         return child->parentContextOf(context);
936     });
937 }
938 
allDeclarations(const CursorInRevision & position,const TopDUContext * topContext,bool searchInParents) const939 QVector<QPair<Declaration*, int>> DUContext::allDeclarations(const CursorInRevision& position,
940                                                              const TopDUContext* topContext,
941                                                              bool searchInParents) const
942 {
943     ENSURE_CAN_READ
944 
945     QVector<QPair<Declaration*, int>> ret;
946 
947     QHash<const DUContext*, bool> hadContexts;
948     // Iterate back up the chain
949     mergeDeclarationsInternal(ret, position, hadContexts, topContext ? topContext : this->topContext(),
950                               searchInParents);
951 
952     return ret;
953 }
954 
localDeclarations(const TopDUContext * source) const955 QVector<Declaration*> DUContext::localDeclarations(const TopDUContext* source) const
956 {
957     ENSURE_CAN_READ
958     // TODO: remove this parameter once we kill old-cpp
959         Q_UNUSED(source);
960     return m_dynamicData->m_localDeclarations;
961 }
962 
mergeDeclarationsInternal(QVector<QPair<Declaration *,int>> & definitions,const CursorInRevision & position,QHash<const DUContext *,bool> & hadContexts,const TopDUContext * source,bool searchInParents,int currentDepth) const963 void DUContext::mergeDeclarationsInternal(QVector<QPair<Declaration*, int>>& definitions,
964                                           const CursorInRevision& position,
965                                           QHash<const DUContext*, bool>& hadContexts,
966                                           const TopDUContext* source,
967                                           bool searchInParents, int currentDepth) const
968 {
969     ENSURE_CAN_READ
970 
971     if ((currentDepth > 300 && currentDepth < 1000) || currentDepth > 1300) {
972         qCDebug(LANGUAGE) << "too much depth";
973         return;
974     }
975     DUCHAIN_D(DUContext);
976 
977     if (hadContexts.contains(this) && !searchInParents)
978         return;
979 
980     if (!hadContexts.contains(this)) {
981         hadContexts[this] = true;
982 
983         if ((type() == DUContext::Namespace || type() == DUContext::Global) && currentDepth < 1000)
984             currentDepth += 1000;
985 
986         {
987             DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
988             while (it) {
989                 Declaration* decl = *it;
990 
991                 if (decl && (!position.isValid() || decl->range().start <= position))
992                     definitions << qMakePair(decl, currentDepth);
993                 ++it;
994             }
995         }
996 
997         for (int a = d->m_importedContextsSize() - 1; a >= 0; --a) {
998             const Import* import(&d->m_importedContexts()[a]);
999             DUContext* context = import->context(source);
1000             while (!context && a > 0) {
1001                 --a;
1002                 import = &d->m_importedContexts()[a];
1003                 context = import->context(source);
1004             }
1005             if (!context)
1006                 break;
1007 
1008             if (context == this) {
1009                 qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true);
1010                 continue;
1011             }
1012 
1013             if (position.isValid() && import->position.isValid() && position < import->position)
1014                 continue;
1015 
1016             context->mergeDeclarationsInternal(definitions,
1017                                                CursorInRevision::invalid(), hadContexts, source,
1018                                                searchInParents && context->shouldSearchInParent(
1019                                                    InImportedParentContext) &&  context->parentContext()->type() == DUContext::Helper,
1020                                                currentDepth + 1);
1021         }
1022     }
1023 
1024     ///Only respect the position if the parent-context is not a class(@todo this is language-dependent)
1025     if (parentContext() && searchInParents)
1026         parentContext()->mergeDeclarationsInternal(definitions,
1027                                                    parentContext()->type() == DUContext::Class ? parentContext()->range().end : position, hadContexts, source, searchInParents,
1028                                                    currentDepth + 1);
1029 }
1030 
deleteLocalDeclarations()1031 void DUContext::deleteLocalDeclarations()
1032 {
1033     ENSURE_CAN_WRITE
1034     // It may happen that the deletion of one declaration triggers the deletion of another one
1035     // Therefore we copy the list of indexed declarations and work on those. Indexed declarations
1036     // will return zero for already deleted declarations.
1037     KDevVarLengthArray<LocalIndexedDeclaration> indexedLocal;
1038     if (d_func()->m_localDeclarations()) {
1039         indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize());
1040     }
1041     const auto currentLocalDeclarations = m_dynamicData->m_localDeclarations;
1042     for (const LocalIndexedDeclaration& indexed : currentLocalDeclarations) {
1043         delete indexed.data(topContext());
1044     }
1045 
1046     m_dynamicData->m_localDeclarations.clear();
1047 }
1048 
deleteChildContextsRecursively()1049 void DUContext::deleteChildContextsRecursively()
1050 {
1051     ENSURE_CAN_WRITE
1052 
1053     // note: operate on copy here because child ctx deletion changes m_dynamicData->m_childContexts
1054     const auto currentChildContexts = m_dynamicData->m_childContexts;
1055     qDeleteAll(currentChildContexts);
1056 
1057     m_dynamicData->m_childContexts.clear();
1058 }
1059 
clearLocalDeclarations()1060 QVector<Declaration*> DUContext::clearLocalDeclarations()
1061 {
1062     auto copy = m_dynamicData->m_localDeclarations;
1063     for (Declaration* dec : qAsConst(copy)) {
1064         dec->setContext(nullptr);
1065     }
1066 
1067     return copy;
1068 }
1069 
scopeIdentifier(bool includeClasses) const1070 QualifiedIdentifier DUContext::scopeIdentifier(bool includeClasses) const
1071 {
1072     ENSURE_CAN_READ
1073 
1074     QualifiedIdentifier ret;
1075     m_dynamicData->scopeIdentifier(includeClasses, ret);
1076 
1077     return ret;
1078 }
1079 
equalScopeIdentifier(const DUContext * rhs) const1080 bool DUContext::equalScopeIdentifier(const DUContext* rhs) const
1081 {
1082     ENSURE_CAN_READ
1083 
1084     const DUContext* left = this;
1085     const DUContext* right = rhs;
1086 
1087     while (left || right) {
1088         if (!left || !right)
1089             return false;
1090 
1091         if (!(left->d_func()->m_scopeIdentifier == right->d_func()->m_scopeIdentifier))
1092             return false;
1093 
1094         left = left->parentContext();
1095         right = right->parentContext();
1096     }
1097 
1098     return true;
1099 }
1100 
setLocalScopeIdentifier(const QualifiedIdentifier & identifier)1101 void DUContext::setLocalScopeIdentifier(const QualifiedIdentifier& identifier)
1102 {
1103     ENSURE_CAN_WRITE
1104     bool wasInSymbolTable = inSymbolTable();
1105     setInSymbolTable(false);
1106     d_func_dynamic()->m_scopeIdentifier = identifier;
1107     setInSymbolTable(wasInSymbolTable);
1108 }
1109 
localScopeIdentifier() const1110 QualifiedIdentifier DUContext::localScopeIdentifier() const
1111 {
1112     //ENSURE_CAN_READ Commented out for performance reasons
1113 
1114     return d_func()->m_scopeIdentifier;
1115 }
1116 
indexedLocalScopeIdentifier() const1117 IndexedQualifiedIdentifier DUContext::indexedLocalScopeIdentifier() const
1118 {
1119     return d_func()->m_scopeIdentifier;
1120 }
1121 
type() const1122 DUContext::ContextType DUContext::type() const
1123 {
1124     //ENSURE_CAN_READ This is disabled, because type() is called very often while searching, and it costs us performance
1125 
1126     return d_func()->m_contextType;
1127 }
1128 
setType(ContextType type)1129 void DUContext::setType(ContextType type)
1130 {
1131     ENSURE_CAN_WRITE
1132 
1133         d_func_dynamic()->m_contextType = type;
1134 }
1135 
findDeclarations(const Identifier & identifier,const CursorInRevision & position,const TopDUContext * topContext,SearchFlags flags) const1136 QList<Declaration*> DUContext::findDeclarations(const Identifier& identifier, const CursorInRevision& position,
1137                                                 const TopDUContext* topContext, SearchFlags flags) const
1138 {
1139     return findDeclarations(IndexedIdentifier(identifier), position, topContext, flags);
1140 }
1141 
findDeclarations(const IndexedIdentifier & identifier,const CursorInRevision & position,const TopDUContext * topContext,SearchFlags flags) const1142 QList<Declaration*> DUContext::findDeclarations(const IndexedIdentifier& identifier, const CursorInRevision& position,
1143                                                 const TopDUContext* topContext, SearchFlags flags) const
1144 {
1145     ENSURE_CAN_READ
1146 
1147     DeclarationList ret;
1148     SearchItem::PtrList identifiers;
1149     identifiers << SearchItem::Ptr(new SearchItem(false, identifier, SearchItem::PtrList()));
1150     findDeclarationsInternal(identifiers, position.isValid() ? position : range().end,
1151                              AbstractType::Ptr(), ret, topContext ? topContext : this->topContext(), flags, 0);
1152     return ret;
1153 }
1154 
deleteUse(int index)1155 void DUContext::deleteUse(int index)
1156 {
1157     ENSURE_CAN_WRITE
1158         DUCHAIN_D_DYNAMIC(DUContext);
1159     d->m_usesList().remove(index);
1160 }
1161 
deleteUses()1162 void DUContext::deleteUses()
1163 {
1164     ENSURE_CAN_WRITE
1165 
1166         DUCHAIN_D_DYNAMIC(DUContext);
1167     d->m_usesList().clear();
1168 }
1169 
deleteUsesRecursively()1170 void DUContext::deleteUsesRecursively()
1171 {
1172     deleteUses();
1173 
1174     for (DUContext* childContext : qAsConst(m_dynamicData->m_childContexts)) {
1175         childContext->deleteUsesRecursively();
1176     }
1177 }
1178 
inDUChain() const1179 bool DUContext::inDUChain() const
1180 {
1181     if (d_func()->m_anonymousInParent || !m_dynamicData->m_parentContext)
1182         return false;
1183 
1184     TopDUContext* top = topContext();
1185     return top && top->inDUChain();
1186 }
1187 
specialize(const IndexedInstantiationInformation &,const TopDUContext * topContext,int)1188 DUContext* DUContext::specialize(const IndexedInstantiationInformation& /*specialization*/,
1189                                  const TopDUContext* topContext, int /*upDistance*/)
1190 {
1191     if (!topContext)
1192         return nullptr;
1193     return this;
1194 }
1195 
importPosition(const DUContext * target) const1196 CursorInRevision DUContext::importPosition(const DUContext* target) const
1197 {
1198     ENSURE_CAN_READ
1199         DUCHAIN_D(DUContext);
1200     Import import(const_cast<DUContext*>(target), this, CursorInRevision::invalid());
1201     for (unsigned int a = 0; a < d->m_importedContextsSize(); ++a)
1202         if (d->m_importedContexts()[a] == import)
1203             return d->m_importedContexts()[a].position;
1204 
1205     return CursorInRevision::invalid();
1206 }
1207 
importedParentContexts() const1208 QVector<DUContext::Import> DUContext::importedParentContexts() const
1209 {
1210     ENSURE_CAN_READ
1211     QVector<DUContext::Import> ret;
1212     ret.reserve(d_func()->m_importedContextsSize());
1213     FOREACH_FUNCTION(const DUContext::Import& import, d_func()->m_importedContexts)
1214     ret << import;
1215     return ret;
1216 }
1217 
applyAliases(const SearchItem::PtrList & baseIdentifiers,SearchItem::PtrList & identifiers,const CursorInRevision & position,bool canBeNamespace,bool onlyImports) const1218 void DUContext::applyAliases(const SearchItem::PtrList& baseIdentifiers, SearchItem::PtrList& identifiers,
1219                              const CursorInRevision& position, bool canBeNamespace, bool onlyImports) const
1220 {
1221     DeclarationList imports;
1222     findLocalDeclarationsInternal(globalIndexedImportIdentifier(), position, AbstractType::Ptr(), imports,
1223                                   topContext(), DUContext::NoFiltering);
1224 
1225     if (imports.isEmpty() && onlyImports) {
1226         identifiers = baseIdentifiers;
1227         return;
1228     }
1229 
1230     for (const SearchItem::Ptr& identifier : baseIdentifiers) {
1231         bool addUnmodified = true;
1232 
1233         if (!identifier->isExplicitlyGlobal) {
1234             if (!imports.isEmpty()) {
1235                 //We have namespace-imports.
1236                 for (Declaration* importDecl : qAsConst(imports)) {
1237                     //Search for the identifier with the import-identifier prepended
1238                     if (dynamic_cast<NamespaceAliasDeclaration*>(importDecl)) {
1239                         auto* alias = static_cast<NamespaceAliasDeclaration*>(importDecl);
1240                         identifiers.append(SearchItem::Ptr(new SearchItem(alias->importIdentifier(), identifier)));
1241                     } else {
1242                         qCDebug(LANGUAGE) << "Declaration with namespace alias identifier has the wrong type" <<
1243                             importDecl->url().str() << importDecl->range().castToSimpleRange();
1244                     }
1245                 }
1246             }
1247 
1248             if (!identifier->isEmpty() && (identifier->hasNext() || canBeNamespace)) {
1249                 DeclarationList aliases;
1250                 findLocalDeclarationsInternal(identifier->identifier, position,
1251                                               AbstractType::Ptr(), imports, nullptr, DUContext::NoFiltering);
1252 
1253                 if (!aliases.isEmpty()) {
1254                     //The first part of the identifier has been found as a namespace-alias.
1255                     //In c++, we only need the first alias. However, just to be correct, follow them all for now.
1256                     for (Declaration* aliasDecl : qAsConst(aliases)) {
1257                         if (!dynamic_cast<NamespaceAliasDeclaration*>(aliasDecl))
1258                             continue;
1259 
1260                         addUnmodified = false; //The un-modified identifier can be ignored, because it will be replaced with the resolved alias
1261                         auto* alias = static_cast<NamespaceAliasDeclaration*>(aliasDecl);
1262 
1263                         //Create an identifier where namespace-alias part is replaced with the alias target
1264                         identifiers.append(SearchItem::Ptr(new SearchItem(alias->importIdentifier(),
1265                                                                           identifier->next)));
1266                     }
1267                 }
1268             }
1269         }
1270 
1271         if (addUnmodified)
1272             identifiers.append(identifier);
1273     }
1274 }
1275 
applyUpwardsAliases(SearchItem::PtrList & identifiers,const TopDUContext *) const1276 void DUContext::applyUpwardsAliases(SearchItem::PtrList& identifiers, const TopDUContext* /*source*/) const
1277 {
1278     if (type() == Namespace) {
1279         if (d_func()->m_scopeIdentifier.isEmpty())
1280             return;
1281 
1282         //Make sure we search for the items in all namespaces of the same name, by duplicating each one with the namespace-identifier prepended.
1283         //We do this by prepending items to the current identifiers that equal the local scope identifier.
1284         SearchItem::Ptr newItem(new SearchItem(d_func()->m_scopeIdentifier.identifier()));
1285 
1286         //This will exclude explicitly global identifiers
1287         newItem->addToEachNode(identifiers);
1288 
1289         if (!newItem->next.isEmpty()) {
1290             //Prepend the full scope before newItem
1291             DUContext* parent = m_dynamicData->m_parentContext.data();
1292             while (parent) {
1293                 newItem = SearchItem::Ptr(new SearchItem(parent->d_func()->m_scopeIdentifier, newItem));
1294                 parent = parent->m_dynamicData->m_parentContext.data();
1295             }
1296 
1297             newItem->isExplicitlyGlobal = true;
1298             identifiers.insert(0, newItem);
1299         }
1300     }
1301 }
1302 
shouldSearchInParent(SearchFlags flags) const1303 bool DUContext::shouldSearchInParent(SearchFlags flags) const
1304 {
1305     return (parentContext() && parentContext()->type() == DUContext::Helper && (flags & InImportedParentContext))
1306            || !(flags & InImportedParentContext);
1307 }
1308 
uses() const1309 const Use* DUContext::uses() const
1310 {
1311     ENSURE_CAN_READ
1312 
1313     return d_func()->m_uses();
1314 }
1315 
declarationHasUses(Declaration * decl)1316 bool DUContext::declarationHasUses(Declaration* decl)
1317 {
1318     return DUChain::uses()->hasUses(decl->id());
1319 }
1320 
usesCount() const1321 int DUContext::usesCount() const
1322 {
1323     return d_func()->m_usesSize();
1324 }
1325 
usesRangeLessThan(const Use & left,const Use & right)1326 bool usesRangeLessThan(const Use& left, const Use& right)
1327 {
1328     return left.m_range.start < right.m_range.start;
1329 }
1330 
createUse(int declarationIndex,const RangeInRevision & range,int insertBefore)1331 int DUContext::createUse(int declarationIndex, const RangeInRevision& range, int insertBefore)
1332 {
1333     DUCHAIN_D_DYNAMIC(DUContext);
1334     ENSURE_CAN_WRITE
1335 
1336     Use use(range, declarationIndex);
1337     if (insertBefore == -1) {
1338         //Find position where to insert
1339         const unsigned int size = d->m_usesSize();
1340         const Use* uses = d->m_uses();
1341         const Use* lowerBound = std::lower_bound(uses, uses + size, use, usesRangeLessThan);
1342         insertBefore = lowerBound - uses;
1343         // comment out to test this:
1344         /*
1345            unsigned int a = 0;
1346            for(; a < size && range.start > uses[a].m_range.start; ++a) {
1347            }
1348            Q_ASSERT(a == insertBefore);
1349          */
1350     }
1351 
1352     d->m_usesList().insert(insertBefore, use);
1353 
1354     return insertBefore;
1355 }
1356 
changeUseRange(int useIndex,const RangeInRevision & range)1357 void DUContext::changeUseRange(int useIndex, const RangeInRevision& range)
1358 {
1359     ENSURE_CAN_WRITE
1360         d_func_dynamic()->m_usesList()[useIndex].m_range = range;
1361 }
1362 
setUseDeclaration(int useNumber,int declarationIndex)1363 void DUContext::setUseDeclaration(int useNumber, int declarationIndex)
1364 {
1365     ENSURE_CAN_WRITE
1366         d_func_dynamic()->m_usesList()[useNumber].m_declarationIndex = declarationIndex;
1367 }
1368 
findContextAt(const CursorInRevision & position,bool includeRightBorder) const1369 DUContext* DUContext::findContextAt(const CursorInRevision& position, bool includeRightBorder) const
1370 {
1371     ENSURE_CAN_READ
1372 
1373 //   qCDebug(LANGUAGE) << "searching" << position << "in:" << scopeIdentifier(true).toString() << range() << includeRightBorder;
1374 
1375     if (!range().contains(position) && (!includeRightBorder || range().end != position)) {
1376 //     qCDebug(LANGUAGE) << "mismatch";
1377         return nullptr;
1378     }
1379 
1380     const auto childContexts = m_dynamicData->m_childContexts;
1381     for (int a = childContexts.size() - 1; a >= 0; --a) {
1382         if (DUContext* specific = childContexts[a]->findContextAt(position, includeRightBorder)) {
1383             return specific;
1384         }
1385     }
1386 
1387     return const_cast<DUContext*>(this);
1388 }
1389 
findDeclarationAt(const CursorInRevision & position) const1390 Declaration* DUContext::findDeclarationAt(const CursorInRevision& position) const
1391 {
1392     ENSURE_CAN_READ
1393 
1394     if (!range().contains(position))
1395         return nullptr;
1396 
1397     for (Declaration* child : qAsConst(m_dynamicData->m_localDeclarations)) {
1398         if (child->range().contains(position)) {
1399             return child;
1400         }
1401     }
1402 
1403     return nullptr;
1404 }
1405 
findContextIncluding(const RangeInRevision & range) const1406 DUContext* DUContext::findContextIncluding(const RangeInRevision& range) const
1407 {
1408     ENSURE_CAN_READ
1409 
1410     if (!this->range().contains(range))
1411         return nullptr;
1412 
1413     for (DUContext* child : qAsConst(m_dynamicData->m_childContexts)) {
1414         if (DUContext* specific = child->findContextIncluding(range)) {
1415             return specific;
1416         }
1417     }
1418 
1419     return const_cast<DUContext*>(this);
1420 }
1421 
findUseAt(const CursorInRevision & position) const1422 int DUContext::findUseAt(const CursorInRevision& position) const
1423 {
1424     ENSURE_CAN_READ
1425 
1426     if (!range().contains(position))
1427         return -1;
1428 
1429     for (unsigned int a = 0; a < d_func()->m_usesSize(); ++a)
1430         if (d_func()->m_uses()[a].m_range.contains(position))
1431             return a;
1432 
1433     return -1;
1434 }
1435 
inSymbolTable() const1436 bool DUContext::inSymbolTable() const
1437 {
1438     return d_func()->m_inSymbolTable;
1439 }
1440 
setInSymbolTable(bool inSymbolTable)1441 void DUContext::setInSymbolTable(bool inSymbolTable)
1442 {
1443     d_func_dynamic()->m_inSymbolTable = inSymbolTable;
1444 }
1445 
clearImportedParentContexts()1446 void DUContext::clearImportedParentContexts()
1447 {
1448     ENSURE_CAN_WRITE
1449         DUCHAIN_D_DYNAMIC(DUContext);
1450 
1451     while (d->m_importedContextsSize() != 0) {
1452         DUContext* ctx = d->m_importedContexts()[0].context(nullptr, false);
1453         if (ctx)
1454             ctx->m_dynamicData->removeImportedChildContext(this);
1455 
1456         d->m_importedContextsList().removeOne(d->m_importedContexts()[0]);
1457     }
1458 }
1459 
cleanIfNotEncountered(const QSet<DUChainBase * > & encountered)1460 void DUContext::cleanIfNotEncountered(const QSet<DUChainBase*>& encountered)
1461 {
1462     ENSURE_CAN_WRITE
1463 
1464     // It may happen that the deletion of one declaration triggers the deletion of another one
1465     // Therefore we copy the list of indexed declarations and work on those. Indexed declarations
1466     // will return zero for already deleted declarations.
1467     KDevVarLengthArray<LocalIndexedDeclaration> indexedLocal;
1468     if (d_func()->m_localDeclarations()) {
1469         indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize());
1470     }
1471     const auto currentLocalDeclarations = m_dynamicData->m_localDeclarations;
1472     for (const LocalIndexedDeclaration& indexed : currentLocalDeclarations) {
1473         auto dec = indexed.data(topContext());
1474         if (dec && !encountered.contains(dec) && (!dec->isAutoDeclaration() || !dec->hasUses())) {
1475             delete dec;
1476         }
1477     }
1478 
1479     const auto currentChildContexts = m_dynamicData->m_childContexts;
1480     for (DUContext* childContext : currentChildContexts) {
1481         if (!encountered.contains(childContext)) {
1482             delete childContext;
1483         }
1484     }
1485 }
1486 
topContext() const1487 TopDUContext* DUContext::topContext() const
1488 {
1489     return m_dynamicData->m_topContext;
1490 }
1491 
createNavigationWidget(Declaration * decl,TopDUContext * topContext,AbstractNavigationWidget::DisplayHints hints) const1492 AbstractNavigationWidget* DUContext::createNavigationWidget(Declaration* decl, TopDUContext* topContext,
1493                                                             AbstractNavigationWidget::DisplayHints hints) const
1494 {
1495     if (decl) {
1496         auto* widget = new AbstractNavigationWidget;
1497         widget->setDisplayHints(hints);
1498         auto* context = new AbstractDeclarationNavigationContext(DeclarationPointer(decl),
1499                                                                  TopDUContextPointer(topContext));
1500         widget->setContext(NavigationContextPointer(context));
1501         return widget;
1502     } else {
1503         return nullptr;
1504     }
1505 }
1506 
allUses(DUContext * context,int declarationIndex,bool noEmptyUses)1507 QVector<RangeInRevision> allUses(DUContext* context, int declarationIndex, bool noEmptyUses)
1508 {
1509     QVector<RangeInRevision> ret;
1510     for (int a = 0; a < context->usesCount(); ++a)
1511         if (context->uses()[a].m_declarationIndex == declarationIndex)
1512             if (!noEmptyUses || !context->uses()[a].m_range.isEmpty())
1513                 ret << context->uses()[a].m_range;
1514 
1515     const auto childContexts = context->childContexts();
1516     for (DUContext* child : childContexts) {
1517         ret += allUses(child, declarationIndex, noEmptyUses);
1518     }
1519 
1520     return ret;
1521 }
1522 
SearchItem(const QualifiedIdentifier & id,const Ptr & nextItem,int start)1523 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const Ptr& nextItem, int start)
1524     : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false)
1525 {
1526     if (!id.isEmpty()) {
1527         if (id.count() > start)
1528             identifier = id.indexedAt(start);
1529 
1530         if (id.count() > start + 1)
1531             addNext(Ptr(new SearchItem(id, nextItem, start + 1)));
1532         else if (nextItem)
1533             next.append(nextItem);
1534     } else if (nextItem) {
1535         ///If there is no prefix, just copy nextItem
1536         isExplicitlyGlobal = nextItem->isExplicitlyGlobal;
1537         identifier = nextItem->identifier;
1538         next = nextItem->next;
1539     }
1540 }
1541 
SearchItem(const QualifiedIdentifier & id,const PtrList & nextItems,int start)1542 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const PtrList& nextItems, int start)
1543     : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false)
1544 {
1545     if (id.count() > start)
1546         identifier = id.indexedAt(start);
1547 
1548     if (id.count() > start + 1)
1549         addNext(Ptr(new SearchItem(id, nextItems, start + 1)));
1550     else
1551         next = nextItems;
1552 }
1553 
SearchItem(bool explicitlyGlobal,const IndexedIdentifier & id,const PtrList & nextItems)1554 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const PtrList& nextItems)
1555     : isExplicitlyGlobal(explicitlyGlobal)
1556     , identifier(id)
1557     , next(nextItems)
1558 {
1559 }
1560 
SearchItem(bool explicitlyGlobal,const IndexedIdentifier & id,const Ptr & nextItem)1561 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const Ptr& nextItem)
1562     : isExplicitlyGlobal(explicitlyGlobal)
1563     , identifier(id)
1564 {
1565     next.append(nextItem);
1566 }
1567 
match(const QualifiedIdentifier & id,int offset) const1568 bool DUContext::SearchItem::match(const QualifiedIdentifier& id, int offset) const
1569 {
1570     if (id.isEmpty()) {
1571         if (identifier.isEmpty() && next.isEmpty())
1572             return true;
1573         else
1574             return false;
1575     }
1576 
1577     if (id.at(offset) != identifier) //The identifier is different
1578         return false;
1579 
1580     if (offset == id.count() - 1) {
1581         if (next.isEmpty())
1582             return true; //match
1583         else
1584             return false; //id is too short
1585     }
1586 
1587     for (int a = 0; a < next.size(); ++a)
1588         if (next[a]->match(id, offset + 1))
1589             return true;
1590 
1591     return false;
1592 }
1593 
isEmpty() const1594 bool DUContext::SearchItem::isEmpty() const
1595 {
1596     return identifier.isEmpty();
1597 }
1598 
hasNext() const1599 bool DUContext::SearchItem::hasNext() const
1600 {
1601     return !next.isEmpty();
1602 }
1603 
toList(const QualifiedIdentifier & prefix) const1604 QVector<QualifiedIdentifier> DUContext::SearchItem::toList(const QualifiedIdentifier& prefix) const
1605 {
1606     QVector<QualifiedIdentifier> ret;
1607 
1608     QualifiedIdentifier id = prefix;
1609     if (id.isEmpty())
1610         id.setExplicitlyGlobal(isExplicitlyGlobal);
1611     if (!identifier.isEmpty())
1612         id.push(identifier);
1613 
1614     if (next.isEmpty()) {
1615         ret << id;
1616     } else {
1617         for (int a = 0; a < next.size(); ++a)
1618             ret += next[a]->toList(id);
1619     }
1620     return ret;
1621 }
1622 
addNext(const SearchItem::Ptr & other)1623 void DUContext::SearchItem::addNext(const SearchItem::Ptr& other)
1624 {
1625     next.append(other);
1626 }
1627 
addToEachNode(const SearchItem::Ptr & other)1628 void DUContext::SearchItem::addToEachNode(const SearchItem::Ptr& other)
1629 {
1630     if (other->isExplicitlyGlobal)
1631         return;
1632 
1633     next.append(other);
1634     for (int a = 0; a < next.size() - 1; ++a)
1635         next[a]->addToEachNode(other);
1636 }
1637 
addToEachNode(const SearchItem::PtrList & other)1638 void DUContext::SearchItem::addToEachNode(const SearchItem::PtrList& other)
1639 {
1640     int added = 0;
1641     for (const SearchItem::Ptr& o : other) {
1642         if (!o->isExplicitlyGlobal) {
1643             next.append(o);
1644             ++added;
1645         }
1646     }
1647 
1648     for (int a = 0; a < next.size() - added; ++a)
1649         next[a]->addToEachNode(other);
1650 }
1651 
Import(DUContext * _context,const DUContext * importer,const CursorInRevision & _position)1652 DUContext::Import::Import(DUContext* _context, const DUContext* importer, const CursorInRevision& _position)
1653     : position(_position)
1654 {
1655     if (_context && _context->owner() &&
1656         (_context->owner()->specialization().index() ||
1657          (importer && importer->topContext() != _context->topContext()))) {
1658         m_declaration = _context->owner()->id();
1659     } else {
1660         m_context = _context;
1661     }
1662 }
1663 
Import(const DeclarationId & id,const CursorInRevision & _position)1664 DUContext::Import::Import(const DeclarationId& id, const CursorInRevision& _position)
1665     : position(_position)
1666     , m_declaration(id)
1667 {
1668 }
1669 
context(const TopDUContext * topContext,bool instantiateIfRequired) const1670 DUContext* DUContext::Import::context(const TopDUContext* topContext, bool instantiateIfRequired) const
1671 {
1672     if (m_declaration.isValid()) {
1673         Declaration* decl = m_declaration.declaration(topContext, instantiateIfRequired);
1674         //This first case rests on the assumption that no context will ever import a function's expression context
1675         //More accurately, that no specialized or cross-topContext imports will, but if the former assumption fails the latter will too
1676         if (auto* functionDecl = dynamic_cast<AbstractFunctionDeclaration*>(decl)) {
1677             if (functionDecl->internalFunctionContext()) {
1678                 return functionDecl->internalFunctionContext();
1679             } else {
1680                 qCWarning(LANGUAGE) << "Import of function declaration without internal function context encountered!";
1681             }
1682         }
1683         if (decl)
1684             return decl->logicalInternalContext(topContext);
1685         else
1686             return nullptr;
1687     } else {
1688         return m_context.data();
1689     }
1690 }
1691 
isDirect() const1692 bool DUContext::Import::isDirect() const
1693 {
1694     return m_context.isValid();
1695 }
1696 
visit(DUChainVisitor & visitor)1697 void DUContext::visit(DUChainVisitor& visitor)
1698 {
1699     ENSURE_CAN_READ
1700 
1701     visitor.visit(this);
1702 
1703     for (Declaration* decl : qAsConst(m_dynamicData->m_localDeclarations)) {
1704         visitor.visit(decl);
1705     }
1706 
1707     for (DUContext* childContext : qAsConst(m_dynamicData->m_childContexts)) {
1708         childContext->visit(visitor);
1709     }
1710 }
1711 
sortByRange(const DUChainBase * lhs,const DUChainBase * rhs)1712 static bool sortByRange(const DUChainBase* lhs, const DUChainBase* rhs)
1713 {
1714     return lhs->range() < rhs->range();
1715 }
1716 
resortLocalDeclarations()1717 void DUContext::resortLocalDeclarations()
1718 {
1719     ENSURE_CAN_WRITE
1720 
1721     std::sort(m_dynamicData->m_localDeclarations.begin(), m_dynamicData->m_localDeclarations.end(), sortByRange);
1722 
1723     auto top = topContext();
1724     auto& declarations = d_func_dynamic()->m_localDeclarationsList();
1725     std::sort(declarations.begin(), declarations.end(),
1726               [top](const LocalIndexedDeclaration& lhs, const LocalIndexedDeclaration& rhs) {
1727             return lhs.data(top)->range() < rhs.data(top)->range();
1728         });
1729 }
1730 
resortChildContexts()1731 void DUContext::resortChildContexts()
1732 {
1733     ENSURE_CAN_WRITE
1734 
1735     std::sort(m_dynamicData->m_childContexts.begin(), m_dynamicData->m_childContexts.end(), sortByRange);
1736 
1737     auto top = topContext();
1738     auto& contexts = d_func_dynamic()->m_childContextsList();
1739     std::sort(contexts.begin(), contexts.end(),
1740               [top](const LocalIndexedDUContext& lhs, const LocalIndexedDUContext& rhs) {
1741             return lhs.data(top)->range() < rhs.data(top)->range();
1742         });
1743 }
1744 }
1745