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