language/duchain/ducontext.cpp

   1 /* This  is part of KDevelop
   2     Copyright 2006 Hamish Rodda <rodda@kde.org>
   3
   4    This library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Library General Public
   6    License version 2 as published by the Free Software Foundation.
   7
   8    This library is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11    Library General Public License for more details.
  12
  13    You should have received a copy of the GNU Library General Public License
  14    along with this library; see the file COPYING.LIB.  If not, write to
  15    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  16    Boston, MA 02110-1301, USA.
  17 */
  18
  19 #include "ducontext.h"
  20
  21 #include <limits>
  22
  23 #include <QMutableLinkedListIterator>
  24 #include <QSet>
  25
  26 #include <ktexteditor/document.h>
  27 #include <ktexteditor/smartinterface.h>
  28
  29 #include "../editor/editorintegrator.h"
  30
  31 #include "ducontextdata.h"
  32 #include "declaration.h"
  33 #include "duchain.h"
  34 #include "duchainlock.h"
  35 #include "use.h"
  36 #include "identifier.h"
  37 #include "topducontext.h"
  38 #include "persistentsymboltable.h"
  39 #include "aliasdeclaration.h"
  40 #include "namespacealiasdeclaration.h"
  41 #include "abstractfunctiondeclaration.h"
  42 #include "indexedstring.h"
  43 #include "duchainregister.h"
  44 #include "topducontextdynamicdata.h"
  45 #include "arrayhelpers.h"
  46 #include "codemodel.h"
  47
  48 ///It is fine to use one global static mutex here
  49
  50 using namespace KTextEditor;
  51
  52 //Stored statically for performance-reasons
  53
  54 #ifndef NDEBUG
  55 #define ENSURE_CAN_WRITE_(x) {if(x->inDUChain()) { ENSURE_CHAIN_WRITE_LOCKED }}
  56 #define ENSURE_CAN_READ_(x) {if(x->inDUChain()) { ENSURE_CHAIN_READ_LOCKED }}
  57 #else
  58 #define ENSURE_CAN_WRITE_(x)
  59 #define ENSURE_CAN_READ_(x)
  60 #endif
  61
  62 namespace KDevelop
  63 {
  64 QMutex DUContextDynamicData::m_localDeclarationsMutex(QMutex::Recursive);
  65
  66 template<class Container>
  67 bool removeOneImport(Container& container, const DUContext* value) {
  68   for(int a = 0; a < container.size(); ++a) {
  69     if(container[a].context() == value) {
  70       removeFromArray(container, a);
  71       return true;
  72     }
  73   }
  74   return false;
  75 }
  76
  77 DEFINE_LIST_MEMBER_HASH(DUContextData, m_childContexts, LocalIndexedDUContext)
  78 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importers, IndexedDUContext)
  79 DEFINE_LIST_MEMBER_HASH(DUContextData, m_importedContexts, DUContext::Import)
  80 DEFINE_LIST_MEMBER_HASH(DUContextData, m_localDeclarations, LocalIndexedDeclaration)
  81 DEFINE_LIST_MEMBER_HASH(DUContextData, m_uses, Use)
  82
  83 REGISTER_DUCHAIN_ITEM(DUContext);
  84
  85 const Identifier globalImportIdentifier("{...import...}");
  86
  87 void DUContext::rebuildDynamicData(DUContext* parent, uint ownIndex) {
  88
  89   Q_ASSERT(!parent || ownIndex);
  90   m_dynamicData->m_topContext = parent ? parent->topContext() : static_cast<TopDUContext*>(this);
  91   m_dynamicData->m_indexInTopContext = ownIndex;
  92   m_dynamicData->m_parentContext = DUContextPointer(parent);
  93   m_dynamicData->m_context = this;
  94
  95   DUChainBase::rebuildDynamicData(parent, ownIndex);
  96 }
  97
  98 DUContextData::DUContextData()
  99   : m_inSymbolTable(false), m_anonymousInParent(false), m_propagateDeclarations(false)
 100 {
 101   initializeAppendedLists();
 102 }
 103
 104 DUContextData::~DUContextData() {
 105   freeAppendedLists();
 106 }
 107
 108 DUContextData::DUContextData(const DUContextData& rhs)  : DUChainBaseData(rhs), m_inSymbolTable(rhs.m_inSymbolTable), m_anonymousInParent(rhs.m_anonymousInParent), m_propagateDeclarations(rhs.m_propagateDeclarations) {
 109   initializeAppendedLists();
 110   copyListsFrom(rhs);
 111   m_scopeIdentifier = rhs.m_scopeIdentifier;
 112   m_contextType = rhs.m_contextType;
 113   m_owner = rhs.m_owner;
 114 }
 115
 116 DUContextDynamicData::DUContextDynamicData(DUContext* d)
 117   : m_topContext(0), m_hasLocalDeclarationsHash(false), m_indexInTopContext(0), m_context(d), m_rangesChanged(true)
 118 {
 119 }
 120
 121 void DUContextDynamicData::scopeIdentifier(bool includeClasses, QualifiedIdentifier& target) const {
 122   if (m_parentContext)
 123     m_parentContext->m_dynamicData->scopeIdentifier(includeClasses, target);
 124
 125   if (includeClasses || m_context->d_func()->m_contextType != DUContext::Class)
 126     target += m_context->d_func()->m_scopeIdentifier;
 127 }
 128
 129 bool DUContextDynamicData::isThisImportedBy(const DUContext* context) const {
 130   if( this == context->m_dynamicData )
 131     return true;
 132
 133   FOREACH_FUNCTION( IndexedDUContext ctx, m_context->d_func()->m_importers ) {
 134     if( IndexedTopDUContext(ctx.topContextIndex()).isLoaded() && ctx.context() && ctx.context()->m_dynamicData->isThisImportedBy(context) )
 135       return true;
 136   }
 137
 138   return false;
 139 }
 140
 141 IndexedDUContext::IndexedDUContext(uint topContext, uint contextIndex) : m_topContext(topContext), m_contextIndex(contextIndex) {
 142 }
 143
 144 IndexedDUContext::IndexedDUContext(DUContext* ctx) {
 145   if(ctx) {
 146     m_topContext = ctx->topContext()->ownIndex();
 147     m_contextIndex = ctx->m_dynamicData->m_indexInTopContext;
 148   }else{
 149     m_topContext = 0;
 150     m_contextIndex = 0;
 151   }
 152 }
 153
 154 IndexedTopDUContext IndexedDUContext::indexedTopContext() const {
 155   return IndexedTopDUContext(m_topContext);
 156 }
 157
 158 LocalIndexedDUContext::LocalIndexedDUContext(uint contextIndex) : m_contextIndex(contextIndex) {
 159 }
 160
 161 LocalIndexedDUContext::LocalIndexedDUContext(DUContext* ctx) {
 162   if(ctx) {
 163     m_contextIndex = ctx->m_dynamicData->m_indexInTopContext;
 164   }else{
 165     m_contextIndex = 0;
 166   }
 167 }
 168
 169 bool LocalIndexedDUContext::isLoaded(TopDUContext* top) const {
 170   if(!m_contextIndex)
 171     return false;
 172   else
 173     return top->m_dynamicData->isContextForIndexLoaded(m_contextIndex);
 174 }
 175
 176 DUContext* LocalIndexedDUContext::data(TopDUContext* top) const {
 177   if(!m_contextIndex)
 178     return 0;
 179   else
 180     return top->m_dynamicData->getContextForIndex(m_contextIndex);
 181 }
 182
 183 DUContext* IndexedDUContext::context() const {
 184   ENSURE_CHAIN_READ_LOCKED
 185   if(!m_topContext)
 186     return 0;
 187
 188   TopDUContext* ctx = DUChain::self()->chainForIndex(m_topContext);
 189   if(!ctx)
 190     return 0;
 191
 192   if(!m_contextIndex)
 193     return ctx;
 194
 195   return ctx->m_dynamicData->getContextForIndex(m_contextIndex);
 196 }
 197
 198 void DUContext::synchronizeUsesFromSmart() const
 199 {
 200   DUCHAIN_D(DUContext);
 201
 202   if(m_dynamicData->m_rangesForUses.isEmpty() || !m_dynamicData->m_rangesChanged)
 203     return;
 204
 205   Q_ASSERT(uint(m_dynamicData->m_rangesForUses.count()) == d->m_usesSize());
 206
 207   for(unsigned int a = 0; a < d->m_usesSize(); a++)
 208     if(m_dynamicData->m_rangesForUses[a]) ///@todo somehow signalize the change
 209       const_cast<Use&>(d->m_uses()[a]).m_range = SimpleRange(*m_dynamicData->m_rangesForUses[a]);
 210
 211   m_dynamicData->m_rangesChanged = false;
 212 }
 213
 214 void DUContext::synchronizeUsesToSmart() const
 215 {
 216   DUCHAIN_D(DUContext);
 217   if(m_dynamicData->m_rangesForUses.isEmpty())
 218     return;
 219   Q_ASSERT(uint(m_dynamicData->m_rangesForUses.count()) == d->m_usesSize());
 220
 221   // TODO: file close race? from here
 222   KTextEditor::SmartInterface *iface = qobject_cast<KTextEditor::SmartInterface*>( smartRange()->document() );
 223   Q_ASSERT(iface);
 224
 225   // TODO: file close race to here
 226   QMutexLocker l(iface->smartMutex());
 227
 228   for(unsigned int a = 0; a < d->m_usesSize(); a++) {
 229     if(a % 10 == 0) { //Unlock the smart-lock time by time, to increase responsiveness
 230       l.unlock();
 231       l.relock();
 232     }
 233     if(m_dynamicData->m_rangesForUses[a]) {
 234       m_dynamicData->m_rangesForUses[a]->start() = d->m_uses()[a].m_range.start.textCursor();
 235       m_dynamicData->m_rangesForUses[a]->end() = d->m_uses()[a].m_range.end.textCursor();
 236     }else{
 237       kDebug() << "bad smart-range";
 238     }
 239   }
 240 }
 241
 242 void DUContext::rangePositionChanged(KTextEditor::SmartRange* range)
 243 {
 244   if(range != smartRange())
 245     m_dynamicData->m_rangesChanged = true;
 246 }
 247
 248 void DUContext::rangeDeleted(KTextEditor::SmartRange* range)
 249 {
 250   if(range == smartRange()) {
 251     DocumentRangeObject::rangeDeleted(range);
 252   } else {
 253     range->removeWatcher(this);
 254     int index = m_dynamicData->m_rangesForUses.indexOf(range);
 255     if(index != -1) {
 256       d_func_dynamic()->m_usesList()[index].m_range = SimpleRange(*range);
 257       m_dynamicData->m_rangesForUses[index] = 0;
 258     }
 259
 260     if(m_dynamicData->m_rangesForUses.count(0) == m_dynamicData->m_rangesForUses.size())
 261       m_dynamicData->m_rangesForUses.clear();
 262   }
 263 }
 264
 265 void DUContextDynamicData::enableLocalDeclarationsHash(DUContext* ctx, const Identifier& currentIdentifier, Declaration* currentDecl)
 266 {
 267   m_hasLocalDeclarationsHash = true;
 268
 269   FOREACH_FUNCTION(LocalIndexedDeclaration indexedDecl, ctx->d_func()->m_localDeclarations) {
 270     Declaration* decl = indexedDecl.data(m_topContext);
 271     Q_ASSERT(decl);
 272     if(currentDecl != decl)
 273       m_localDeclarationsHash.insert( decl->identifier(), DeclarationPointer(decl) );
 274     else
 275       m_localDeclarationsHash.insert( currentIdentifier, DeclarationPointer(decl) );
 276   }
 277
 278   FOREACH_FUNCTION(LocalIndexedDUContext child, ctx->d_func()->m_childContexts) {
 279     DUContext* childCtx = child.data(m_topContext);
 280     Q_ASSERT(childCtx);
 281     if(childCtx->d_func()->m_propagateDeclarations)
 282       enableLocalDeclarationsHash(childCtx, currentIdentifier, currentDecl);
 283   }
 284 }
 285
 286 void DUContextDynamicData::disableLocalDeclarationsHash()
 287 {
 288   m_hasLocalDeclarationsHash = false;
 289   m_localDeclarationsHash.clear();
 290 }
 291
 292 bool DUContextDynamicData::needsLocalDeclarationsHash()
 293 {
 294   ///@todo Do this again, it brings a large performance boost
 295   //For now disable the hash, until we make sure that all declarations needed for the hash are loaded first
 296   //including those in propagating sub-contexts.
 297   //Then, also make sure that we create the declaration hash after loading if needed
 298   return false;
 299
 300   if(m_context->d_func()->m_localDeclarationsSize() > 15)
 301     return true;
 302
 303   uint propagatingChildContexts = 0;
 304
 305   FOREACH_FUNCTION(LocalIndexedDUContext child, m_context->d_func()->m_childContexts) {
 306     DUContext* childCtx = child.data(m_topContext);
 307     Q_ASSERT(childCtx);
 308     if(childCtx->d_func()->m_propagateDeclarations)
 309       ++propagatingChildContexts;
 310   }
 311
 312   return propagatingChildContexts > 4;
 313 }
 314
 315 void DUContextDynamicData::addDeclarationToHash(const Identifier& identifier, Declaration* declaration)
 316 {
 317   if(m_hasLocalDeclarationsHash)
 318     m_localDeclarationsHash.insert( identifier, DeclarationPointer(declaration) );
 319
 320   if( m_context->d_func()->m_propagateDeclarations && m_parentContext )
 321     m_parentContext->m_dynamicData->addDeclarationToHash(identifier, declaration);
 322
 323   if(!m_hasLocalDeclarationsHash && needsLocalDeclarationsHash())
 324     enableLocalDeclarationsHash(m_context, identifier, declaration);
 325 }
 326
 327 void DUContextDynamicData::removeDeclarationFromHash(const Identifier& identifier, Declaration* declaration)
 328 {
 329   if(m_hasLocalDeclarationsHash)
 330     m_localDeclarationsHash.remove( identifier, DeclarationPointer(declaration) );
 331
 332   if( m_context->d_func()->m_propagateDeclarations && m_parentContext )
 333     m_parentContext->m_dynamicData->removeDeclarationFromHash(identifier,  declaration);
 334
 335   if(m_hasLocalDeclarationsHash && !needsLocalDeclarationsHash())
 336       disableLocalDeclarationsHash();
 337 }
 338
 339 void DUContextDynamicData::addDeclaration( Declaration * newDeclaration )
 340 {
 341   // The definition may not have its identifier set when it's assigned... allow dupes here, TODO catch the error elsewhere
 342   {
 343     QMutexLocker lock(&m_localDeclarationsMutex);
 344
 345 //     m_localDeclarations.append(newDeclaration);
 346
 347   if(m_indexInTopContext < (0xffffffff/2)) {
 348     //If this context is not temporary, added declarations shouldn't be either
 349     Q_ASSERT(newDeclaration->ownIndex() < (0xffffffff/2));
 350   }
 351   if(m_indexInTopContext > (0xffffffff/2)) {
 352     //If this context is temporary, added declarations should be as well
 353     Q_ASSERT(newDeclaration->ownIndex() > (0xffffffff/2));
 354   }
 355
 356   SimpleCursor start = newDeclaration->range().start;
 357
 358   bool inserted = false;
 359   for (int i = m_context->d_func_dynamic()->m_localDeclarationsSize()-1; i >= 0; --i) {
 360     Declaration* child = m_context->d_func_dynamic()->m_localDeclarations()[i].data(m_topContext);
 361     Q_ASSERT(child);
 362     if(child == newDeclaration)
 363       return;
 364     if (start > child->range().start) {
 365       insertToArray(m_context->d_func_dynamic()->m_localDeclarationsList(), newDeclaration, i+1);
 366       inserted = true;
 367       break;
 368     }
 369   }
 370   if( !inserted )
 371     m_context->d_func_dynamic()->m_localDeclarationsList().append(newDeclaration);
 372
 373     addDeclarationToHash(newDeclaration->identifier(), newDeclaration);
 374   }
 375
 376   //DUChain::contextChanged(m_context, DUChainObserver::Addition, DUChainObserver::LocalDeclarations, newDeclaration);
 377 }
 378
 379 bool DUContextDynamicData::removeDeclaration(Declaration* declaration)
 380 {
 381   QMutexLocker lock(&m_localDeclarationsMutex);
 382
 383   if(!m_topContext->deleting()) //We can save a lot of time by just not caring about the hash while deleting
 384     removeDeclarationFromHash(declaration->identifier(), declaration);
 385
 386   if( removeOne(m_context->d_func_dynamic()->m_localDeclarationsList(), LocalIndexedDeclaration(declaration)) ) {
 387     //DUChain::contextChanged(m_context, DUChainObserver::Removal, DUChainObserver::LocalDeclarations, declaration);
 388     return true;
 389   }else {
 390     return false;
 391   }
 392 }
 393
 394 void DUContext::changingIdentifier( Declaration* decl, const Identifier& from, const Identifier& to ) {
 395   QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 396   m_dynamicData->removeDeclarationFromHash(from, decl);
 397   m_dynamicData->addDeclarationToHash(to, decl);
 398 }
 399
 400 void DUContextDynamicData::addChildContext( DUContext * context )
 401 {
 402   // Internal, don't need to assert a lock
 403   Q_ASSERT(!context->m_dynamicData->m_parentContext || context->m_dynamicData->m_parentContext.data()->m_dynamicData == this );
 404
 405   LocalIndexedDUContext indexed(context->m_dynamicData->m_indexInTopContext);
 406
 407   if(m_indexInTopContext < (0xffffffff/2)) {
 408     //If this context is not temporary, added declarations shouldn't be either
 409     Q_ASSERT(indexed.localIndex() < (0xffffffff/2));
 410   }
 411   if(m_indexInTopContext > (0xffffffff/2)) {
 412     //If this context is temporary, added declarations should be as well
 413     Q_ASSERT(indexed.localIndex() > (0xffffffff/2));
 414   }
 415
 416   bool inserted = false;
 417
 418   int childCount = m_context->d_func()->m_childContextsSize();
 419
 420   //Optimization: In most cases while parsing, the new child-context will be added to the end, so check if it is the case.
 421   if(m_context->d_func()->m_childContextsSize() != 0) {
 422     if(m_context->d_func()->m_childContexts()[childCount-1].data(m_topContext)->range().start <= context->range().start)
 423       goto insertAtEnd;
 424   }
 425
 426   for (int i = 0; i < childCount; ++i) {
 427     DUContext* child = m_context->d_func()->m_childContexts()[i].data(m_topContext);
 428     if (context == child)
 429       return;
 430     if (context->range().start < child->range().start) {
 431       insertToArray(m_context->d_func_dynamic()->m_childContextsList(), indexed, i);
 432       context->m_dynamicData->m_parentContext = m_context;
 433       inserted = true;
 434       break;
 435     }
 436   }
 437
 438   insertAtEnd:
 439   if( !inserted ) {
 440     m_context->d_func_dynamic()->m_childContextsList().append(indexed);
 441     context->m_dynamicData->m_parentContext = m_context;
 442   }
 443
 444   if(context->d_func()->m_propagateDeclarations) {
 445     QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 446     disableLocalDeclarationsHash();
 447     if(needsLocalDeclarationsHash())
 448       enableLocalDeclarationsHash(m_context);
 449   }
 450
 451   //DUChain::contextChanged(m_context, DUChainObserver::Addition, DUChainObserver::ChildContexts, context);
 452 }
 453
 454 bool DUContextDynamicData::removeChildContext( DUContext* context ) {
 455 //   ENSURE_CAN_WRITE
 456
 457   if( removeOne(m_context->d_func_dynamic()->m_childContextsList(), LocalIndexedDUContext(context)) )
 458     return true;
 459   else
 460     return false;
 461 }
 462
 463 void DUContextDynamicData::addImportedChildContext( DUContext * context )
 464 {
 465 //   ENSURE_CAN_WRITE
 466   Q_ASSERT(!arrayContains(m_context->d_func_dynamic()->m_importersList(), IndexedDUContext(context)));
 467
 468   m_context->d_func_dynamic()->m_importersList().append(context);
 469
 470   //DUChain::contextChanged(m_context, DUChainObserver::Addition, DUChainObserver::ImportedChildContexts, context);
 471 }
 472
 473 //Can also be called with a context that is not in the list
 474 void DUContextDynamicData::removeImportedChildContext( DUContext * context )
 475 {
 476 //   ENSURE_CAN_WRITE
 477   removeOne(m_context->d_func_dynamic()->m_importersList(), IndexedDUContext(context));
 478   //if( != 0 )
 479     //DUChain::contextChanged(m_context, DUChainObserver::Removal, DUChainObserver::ImportedChildContexts, context);
 480 }
 481
 482 int DUContext::depth() const
 483 {
 484   { if (!parentContext()) return 0; return parentContext()->depth() + 1; }
 485 }
 486
 487 DUContext::DUContext(DUContextData& data) : DUChainBase(data), m_dynamicData(new DUContextDynamicData(this)) {
 488 }
 489
 490
 491 DUContext::DUContext(const SimpleRange& range, DUContext* parent, bool anonymous)
 492   : DUChainBase(*new DUContextData(), range), m_dynamicData(new DUContextDynamicData(this))
 493 {
 494   d_func_dynamic()->setClassId(this);
 495   if(parent)
 496     m_dynamicData->m_topContext = parent->topContext();
 497   else
 498     m_dynamicData->m_topContext = static_cast<TopDUContext*>(this);
 499
 500   d_func_dynamic()->setClassId(this);
 501   DUCHAIN_D_DYNAMIC(DUContext);
 502   d->m_contextType = Other;
 503   m_dynamicData->m_parentContext = 0;
 504
 505   d->m_anonymousInParent = anonymous;
 506   d->m_inSymbolTable = false;
 507
 508   if (parent) {
 509     m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this, parent->isAnonymous() || anonymous);
 510     Q_ASSERT(m_dynamicData->m_indexInTopContext);
 511
 512     if( !anonymous )
 513       parent->m_dynamicData->addChildContext(this);
 514     else
 515       m_dynamicData->m_parentContext = parent;
 516   }
 517
 518   if(parent && !anonymous && parent->inSymbolTable())
 519     setInSymbolTable(true);
 520 }
 521
 522 bool DUContext::isAnonymous() const {
 523   return d_func()->m_anonymousInParent || (m_dynamicData->m_parentContext && m_dynamicData->m_parentContext->isAnonymous());
 524 }
 525
 526 DUContext::DUContext( DUContextData& dd, const SimpleRange& range, DUContext * parent, bool anonymous )
 527   : DUChainBase(dd, range), m_dynamicData(new DUContextDynamicData(this))
 528 {
 529   if(parent)
 530     m_dynamicData->m_topContext = parent->topContext();
 531   else
 532     m_dynamicData->m_topContext = static_cast<TopDUContext*>(this);
 533
 534   DUCHAIN_D_DYNAMIC(DUContext);
 535   d->m_contextType = Other;
 536   m_dynamicData->m_parentContext = 0;
 537   d->m_inSymbolTable = false;
 538   d->m_anonymousInParent = anonymous;
 539   if (parent) {
 540     m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this, parent->isAnonymous() || anonymous);
 541
 542     if( !anonymous )
 543       parent->m_dynamicData->addChildContext(this);
 544     else
 545       m_dynamicData->m_parentContext = parent;
 546   }
 547 }
 548
 549 DUContext::DUContext(DUContext& useDataFrom)
 550   : DUChainBase(useDataFrom), m_dynamicData(useDataFrom.m_dynamicData)
 551 {
 552 }
 553
 554 DUContext::~DUContext( )
 555 {
 556   ///@todo Don't create dynamic versions of the data while destroying!
 557   DUCHAIN_D_DYNAMIC(DUContext);
 558   TopDUContext* top = topContext();
 559
 560   if(!top->deleting() || !top->isOnDisk()) {
 561     QualifiedIdentifier id(scopeIdentifier(true));
 562     if(d->m_inSymbolTable && parentContext()) {
 563       PersistentSymbolTable::self().removeContext(id, this);
 564
 565       //We put namespaces into the code-model
 566       if(d->m_contextType == DUContext::Namespace)
 567         CodeModel::self().removeItem(url(), id);
 568     }
 569
 570     if(d->m_owner.declaration())
 571       d->m_owner.declaration()->setInternalContext(0);
 572
 573     while( d->m_importersSize() != 0 )
 574       d->m_importers()[0].data()->removeImportedParentContext(this);
 575
 576     while( d->m_importedContextsSize() != 0 )
 577       if( d->m_importedContexts()[0].context() )
 578         removeImportedParentContext(d->m_importedContexts()[0].context());
 579       else
 580         removeOneImport(d->m_importedContextsList(), 0);
 581   }
 582
 583   deleteChildContextsRecursively();
 584
 585   deleteUses();
 586
 587   deleteLocalDeclarations();
 588
 589   if (m_dynamicData->m_parentContext)
 590     m_dynamicData->m_parentContext->m_dynamicData->removeChildContext(this);
 591   //DUChain::contextChanged(this, DUChainObserver::Deletion, DUChainObserver::NotApplicable);
 592
 593   if(top)
 594     top->m_dynamicData->clearContextIndex(this);
 595 }
 596
 597 QVector< DUContext * > DUContext::childContexts( ) const
 598 {
 599   ENSURE_CAN_READ
 600
 601   QVector< DUContext * > ret;
 602   FOREACH_FUNCTION(LocalIndexedDUContext ctx, d_func()->m_childContexts)
 603     ret << ctx.data(topContext());
 604   return ret;
 605 }
 606
 607 Declaration* DUContext::owner() const {
 608   ENSURE_CAN_READ
 609   return d_func()->m_owner.declaration();
 610 }
 611
 612 void DUContext::setOwner(Declaration* owner) {
 613   ENSURE_CAN_WRITE
 614   DUCHAIN_D_DYNAMIC(DUContext);
 615   if( owner == d->m_owner.declaration() )
 616     return;
 617
 618   Declaration* oldOwner = d->m_owner.declaration();
 619
 620   d->m_owner = owner;
 621
 622   //Q_ASSERT(!oldOwner || oldOwner->internalContext() == this);
 623   if( oldOwner && oldOwner->internalContext() == this )
 624     oldOwner->setInternalContext(0);
 625
 626
 627   //The context set as internal context should always be the last opened context
 628   if( owner )
 629     owner->setInternalContext(this);
 630 }
 631
 632 DUContext* DUContext::parentContext( ) const
 633 {
 634   //ENSURE_CAN_READ Commented out for performance reasons
 635
 636   return m_dynamicData->m_parentContext.data();
 637 }
 638
 639 void DUContext::setPropagateDeclarations(bool propagate)
 640 {
 641   ENSURE_CAN_WRITE
 642   DUCHAIN_D_DYNAMIC(DUContext);
 643   QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 644
 645   m_dynamicData->m_parentContext->m_dynamicData->disableLocalDeclarationsHash();
 646
 647   d->m_propagateDeclarations = propagate;
 648
 649   if(m_dynamicData->m_parentContext->m_dynamicData->needsLocalDeclarationsHash())
 650     m_dynamicData->m_parentContext->m_dynamicData->enableLocalDeclarationsHash(m_dynamicData->m_parentContext.data());
 651 }
 652
 653 bool DUContext::isPropagateDeclarations() const
 654 {
 655   return d_func()->m_propagateDeclarations;
 656 }
 657
 658 QList<Declaration*> DUContext::findLocalDeclarations( const Identifier& identifier, const SimpleCursor & position, const TopDUContext* topContext, const AbstractType::Ptr& dataType, SearchFlags flags ) const
 659 {
 660   ENSURE_CAN_READ
 661
 662   DeclarationList ret;
 663   findLocalDeclarationsInternal(identifier, position.isValid() ? position : range().end, dataType, ret, topContext ? topContext : this->topContext(), flags);
 664   return arrayToList(ret);
 665 }
 666
 667 void DUContext::findLocalDeclarationsInternal( const Identifier& identifier, const SimpleCursor & position, const AbstractType::Ptr& dataType, DeclarationList& ret, const TopDUContext* /*source*/, SearchFlags flags ) const
 668 {
 669   IndexedIdentifier indexedIdentifier(identifier);
 670   {
 671      QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 672
 673      struct Checker {
 674        Checker(SearchFlags flags, const AbstractType::Ptr& dataType, const SimpleCursor & position, DUContext::ContextType ownType) : m_flags(flags), m_dataType(dataType), m_position(position), m_ownType(ownType) {
 675        }
 676
 677        Declaration* check(Declaration* declaration) {
 678           if( declaration->kind() == Declaration::Alias ) {
 679             //Apply alias declarations
 680             AliasDeclaration* alias = static_cast<AliasDeclaration*>(declaration);
 681             if(alias->aliasedDeclaration().isValid()) {
 682               declaration = alias->aliasedDeclaration().declaration();
 683             } else {
 684               kDebug() << "lost aliased declaration";
 685             }
 686           }
 687
 688           if( declaration->kind() == Declaration::NamespaceAlias )
 689             return 0;
 690
 691           if((m_flags & OnlyFunctions) && !declaration->isFunctionDeclaration())
 692             return 0;
 693
 694           if (!m_dataType || m_dataType == declaration->abstractType())
 695             if (m_ownType == Class || m_ownType == Template || m_position > declaration->range().start || !m_position.isValid()) ///@todo This is C++-specific
 696               return declaration;
 697           return 0;
 698        }
 699
 700        SearchFlags m_flags;
 701        const AbstractType::Ptr& m_dataType;
 702        const SimpleCursor& m_position;
 703        DUContext::ContextType m_ownType;
 704      };
 705
 706      Checker checker(flags, dataType, position, type());
 707
 708      if(!m_dynamicData->m_hasLocalDeclarationsHash) {
 709        //Use a special hash that contains all declarations visible in this context
 710       DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
 711       while(it) {
 712         Declaration* declaration = *it;
 713         if(declaration->indexedIdentifier() == indexedIdentifier) {
 714           Declaration* checked = checker.check(declaration);
 715           if(checked)
 716               ret.append(checked);
 717         }
 718         ++it;
 719       }
 720      }else if(d_func()->m_inSymbolTable) {
 721        //This context is in the symbol table, use the symbol-table to speed up the search
 722        QualifiedIdentifier id(scopeIdentifier(true) + identifier);
 723
 724        TopDUContext* top = topContext();
 725
 726        uint count;
 727        const IndexedDeclaration* declarations;
 728        PersistentSymbolTable::self().declarations(id, count, declarations);
 729        for(uint a = 0; a < count; ++a) {
 730          if(declarations[a].topContextIndex() == top->ownIndex()) {
 731            Declaration* decl = LocalIndexedDeclaration(declarations[a].localIndex()).data(top);
 732            if(decl) {
 733              Declaration* checked = checker.check(decl);
 734              if(checked)
 735                ret.append(checked);
 736            }
 737          }
 738        }
 739      }else{
 740        //Iterate through all declarations
 741       QHash<Identifier, DeclarationPointer>::const_iterator it = m_dynamicData->m_localDeclarationsHash.find(identifier);
 742       QHash<Identifier, DeclarationPointer>::const_iterator end = m_dynamicData->m_localDeclarationsHash.end();
 743
 744       for( ; it != end && it.key() == identifier; ++it ) {
 745         Declaration* declaration = (*it).data();
 746
 747         if( !declaration ) {
 748           //This should never happen, but let's see
 749           kDebug(9505) << "DUContext::findLocalDeclarationsInternal: Invalid declaration in local-declaration-hash";
 750           continue;
 751         }
 752
 753         Declaration* checked = checker.check(declaration);
 754         if(checked)
 755             ret.append(checked);
 756       }
 757     }
 758   }
 759 }
 760
 761 bool DUContext::foundEnough( const DeclarationList& ret ) const {
 762   if( !ret.isEmpty() )
 763     return true;
 764   else
 765     return false;
 766 }
 767
 768 bool DUContext::findDeclarationsInternal( const SearchItem::PtrList & baseIdentifiers, const SimpleCursor & position, const AbstractType::Ptr& dataType, DeclarationList& ret, const TopDUContext* source, SearchFlags flags ) const
 769 {
 770   DUCHAIN_D(DUContext);
 771   if( d_func()->m_contextType != Namespace ) { //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.
 772     for(int a = 0; a < baseIdentifiers.size(); ++a)
 773       if(!baseIdentifiers[a]->isExplicitlyGlobal && baseIdentifiers[a]->next.isEmpty()) //It makes no sense searching locally for qualified identifiers
 774         findLocalDeclarationsInternal(baseIdentifiers[a]->identifier, position, dataType, ret, source, flags);
 775
 776     if( foundEnough(ret) )
 777       return true;
 778   }
 779
 780   ///Step 1: Apply namespace-aliases and -imports
 781   SearchItem::PtrList aliasedIdentifiers;
 782   //Because of namespace-imports and aliases, this identifier may need to be searched under multiple names
 783   if( d_func()->m_contextType == Namespace )
 784     applyAliases(baseIdentifiers, aliasedIdentifiers, position, false);
 785   else
 786     aliasedIdentifiers = baseIdentifiers;
 787
 788
 789   if( d->m_importedContextsSize() != 0 ) {
 790     ///Step 2: Give identifiers that are not marked as explicitly-global to imported contexts(explicitly global ones are treatead in TopDUContext)
 791     SearchItem::PtrList nonGlobalIdentifiers;
 792     FOREACH_ARRAY( const SearchItem::Ptr& identifier, aliasedIdentifiers )
 793       if( !identifier->isExplicitlyGlobal )
 794         nonGlobalIdentifiers << identifier;
 795
 796     if( !nonGlobalIdentifiers.isEmpty() ) {
 797       for(int import = d->m_importedContextsSize()-1; import >= 0; --import ) {
 798         DUContext* context = d->m_importedContexts()[import].context();
 799
 800         while( !context && import > 0 ) {
 801           --import;
 802         }
 803
 804         if(context == this) {
 805           kDebug() << "resolved self as import:" << scopeIdentifier(true);
 806           continue;
 807         }
 808
 809         if( !context )
 810           break;
 811
 812         if( position.isValid() && d->m_importedContexts()[import].position.isValid() && position < d->m_importedContexts()[import].position )
 813           continue;
 814
 815         if( !context->findDeclarationsInternal(nonGlobalIdentifiers,  url() == context->url() ? position : context->range().end, dataType, ret, source, flags | InImportedParentContext) )
 816           return false;
 817       }
 818     }
 819   }
 820
 821   if( foundEnough(ret) )
 822     return true;
 823
 824   ///Step 3: Continue search in parent-context
 825   if (!(flags & DontSearchInParent) && shouldSearchInParent(flags) && m_dynamicData->m_parentContext) {
 826     applyUpwardsAliases(aliasedIdentifiers);
 827     return m_dynamicData->m_parentContext->findDeclarationsInternal(aliasedIdentifiers, url() == m_dynamicData->m_parentContext->url() ? position : m_dynamicData->m_parentContext->range().end, dataType, ret, source, flags);
 828   }
 829   return true;
 830 }
 831
 832 QList<Declaration*> DUContext::findDeclarations( const QualifiedIdentifier & identifier, const SimpleCursor & position, const AbstractType::Ptr& dataType, const TopDUContext* topContext, SearchFlags flags) const
 833 {
 834   ENSURE_CAN_READ
 835
 836   DeclarationList ret;
 837   SearchItem::PtrList identifiers;
 838   identifiers << SearchItem::Ptr(new SearchItem(identifier));
 839
 840   findDeclarationsInternal(identifiers, position.isValid() ? position : range().end, dataType, ret, topContext ? topContext : this->topContext(), flags);
 841
 842   return arrayToList(ret);
 843 }
 844
 845 bool DUContext::imports(const DUContext* origin, const SimpleCursor& /*position*/ ) const
 846 {
 847   ENSURE_CAN_READ
 848
 849   return origin->m_dynamicData->isThisImportedBy(this);
 850 }
 851
 852
 853 void DUContext::addImportedParentContext( DUContext * context, const SimpleCursor& position, bool anonymous, bool /*temporary*/ )
 854 {
 855   ENSURE_CAN_WRITE
 856   DUCHAIN_D_DYNAMIC(DUContext);
 857
 858   if(context == this) {
 859     kDebug(9007) << "Tried to import self";
 860     return;
 861   }
 862
 863   for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
 864     if(d->m_importedContexts()[a].context() == context) {
 865       d->m_importedContextsList()[a].position = position;
 866       return;
 867     }
 868   }
 869
 870   if( !anonymous ) {
 871     ENSURE_CAN_WRITE_(context)
 872     context->m_dynamicData->addImportedChildContext(this);
 873   }
 874
 875   ///Do not sort the imported contexts by their own line-number, it makes no sense.
 876   ///Contexts added first, aka template-contexts, should stay in first place, so they are searched first.
 877
 878   d->m_importedContextsList().append(Import(context, position));
 879
 880   //DUChain::contextChanged(this, DUChainObserver::Addition, DUChainObserver::ImportedParentContexts, context);
 881 }
 882
 883 void DUContext::removeImportedParentContext( DUContext * context )
 884 {
 885   ENSURE_CAN_WRITE
 886   DUCHAIN_D_DYNAMIC(DUContext);
 887
 888   for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a) {
 889     if(d->m_importedContexts()[a].context() == context) {
 890       removeFromArray(d->m_importedContextsList(), a);
 891       break;
 892     }
 893   }
 894
 895   if( !context )
 896     return;
 897
 898   context->m_dynamicData->removeImportedChildContext(this);
 899
 900   //DUChain::contextChanged(this, DUChainObserver::Removal, DUChainObserver::ImportedParentContexts, context);
 901 }
 902
 903 QVector<DUContext*> DUContext::importers() const
 904 {
 905   ENSURE_CAN_READ
 906
 907   QVector<DUContext*> ret;
 908   FOREACH_FUNCTION(IndexedDUContext ctx, d_func()->m_importers)
 909     ret << ctx.context();
 910
 911   return ret;
 912 }
 913
 914 DUContext * DUContext::findContext( const SimpleCursor& position, DUContext* parent) const
 915 {
 916   ENSURE_CAN_READ
 917
 918   if (!parent)
 919     parent = const_cast<DUContext*>(this);
 920
 921   FOREACH_FUNCTION(LocalIndexedDUContext context, parent->d_func()->m_childContexts)
 922     if (context.data(topContext())->range().contains(position)) {
 923       DUContext* ret = findContext(position, context.data(topContext()));
 924       if (!ret)
 925         ret = context.data(topContext());
 926
 927       return ret;
 928     }
 929
 930   return 0;
 931 }
 932
 933 bool DUContext::parentContextOf(DUContext* context) const
 934 {
 935   if (this == context)
 936     return true;
 937
 938   FOREACH_FUNCTION(LocalIndexedDUContext child, d_func()->m_childContexts) {
 939     if (child.data(topContext())->parentContextOf(context))
 940       return true;
 941   }
 942
 943   return false;
 944 }
 945
 946 QList<Declaration*> DUContext::allLocalDeclarations(const Identifier& identifier) const
 947 {
 948   IndexedIdentifier indexedIdentifier(identifier);
 949
 950   ENSURE_CAN_READ
 951   QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 952
 953   QList<Declaration*> ret;
 954
 955   if(m_dynamicData->m_hasLocalDeclarationsHash) {
 956     QHash<Identifier, DeclarationPointer>::const_iterator it = m_dynamicData->m_localDeclarationsHash.find(identifier);
 957     QHash<Identifier, DeclarationPointer>::const_iterator end = m_dynamicData->m_localDeclarationsHash.end();
 958
 959     for( ; it != end && it.key() == identifier; ++it )
 960       ret << (*it).data();
 961   }else{
 962     DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
 963     while(it) {
 964       Declaration* decl = *it;
 965       if(decl->indexedIdentifier() == indexedIdentifier)
 966         ret << decl;
 967       ++it;
 968     }
 969   }
 970   return ret;
 971 }
 972
 973 QList< QPair<Declaration*, int> > DUContext::allDeclarations(const SimpleCursor& position, const TopDUContext* topContext, bool searchInParents) const
 974 {
 975   ENSURE_CAN_READ
 976
 977   QList< QPair<Declaration*, int> > ret;
 978
 979   QHash<const DUContext*, bool> hadContexts;
 980   // Iterate back up the chain
 981   mergeDeclarationsInternal(ret, position, hadContexts, topContext ? topContext : this->topContext(), searchInParents);
 982
 983   return ret;
 984 }
 985
 986 QVector<Declaration*> DUContext::localDeclarations() const
 987 {
 988   ENSURE_CAN_READ
 989
 990   QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
 991   QVector<Declaration*> ret;
 992   FOREACH_FUNCTION(LocalIndexedDeclaration decl, d_func()->m_localDeclarations) {
 993     ret << decl.data(topContext());
 994     Q_ASSERT(ret.back()->context() == this);
 995     ret.back()->identifier().isEmpty();
 996   }
 997
 998   return ret;
 999 }
1000
1001 void DUContext::mergeDeclarationsInternal(QList< QPair<Declaration*, int> >& definitions, const SimpleCursor& position, QHash<const DUContext*, bool>& hadContexts, const TopDUContext* source, bool searchInParents, int currentDepth) const
1002 {
1003   DUCHAIN_D(DUContext);
1004   if(hadContexts.contains(this))
1005     return;
1006   hadContexts[this] = true;
1007
1008   if( (type() == DUContext::Namespace || type() == DUContext::Global) && currentDepth < 1000 )
1009     currentDepth += 1000;
1010
1011   {
1012     QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
1013     DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData);
1014     while(it) {
1015       Declaration* decl = *it;
1016
1017       if ( decl && (!position.isValid() || decl->range().start <= position) )
1018         definitions << qMakePair(decl, currentDepth);
1019       ++it;
1020     }
1021   }
1022
1023   for(int a = d->m_importedContextsSize()-1; a >= 0; --a) {
1024     const Import* import(&d->m_importedContexts()[a]);
1025     DUContext* context = import->context();
1026     while( !context && a > 0 ) {
1027       --a;
1028       import = &d->m_importedContexts()[a];
1029       context = import->context();
1030     }
1031     if( !context )
1032       break;
1033
1034     if(context == this) {
1035       kDebug() << "resolved self as import:" << scopeIdentifier(true);
1036       continue;
1037     }
1038
1039
1040     if( position.isValid() && import->position.isValid() && position < import->position )
1041       continue;
1042
1043     context->mergeDeclarationsInternal(definitions, SimpleCursor::invalid(), hadContexts, source, false, currentDepth+1);
1044   }
1045
1046   if (searchInParents && parentContext())                            ///Only respect the position if the parent-context is not a class(@todo this is language-dependent)
1047     parentContext()->mergeDeclarationsInternal(definitions, parentContext()->type() == DUContext::Class ? parentContext()->range().end : position, hadContexts, source, true, currentDepth+1);
1048 }
1049
1050 void DUContext::deleteLocalDeclarations()
1051 {
1052   ENSURE_CAN_WRITE
1053   KDevVarLengthArray<LocalIndexedDeclaration> declarations;
1054   {
1055     QMutexLocker lock(&DUContextDynamicData::m_localDeclarationsMutex);
1056     FOREACH_FUNCTION(const LocalIndexedDeclaration& decl, d_func()->m_localDeclarations)
1057       declarations.append(decl);
1058   }
1059
1060   TopDUContext* top = topContext();
1061   //If we are deleting something that is not stored to disk, we need to create + delete the declarations,
1062   //so their destructor unregisters from the persistent symbol table and from TopDUContextDynamicData
1063   FOREACH_ARRAY(LocalIndexedDeclaration decl, declarations)
1064     if(decl.isLoaded(top) || !top->deleting() || !top->isOnDisk())
1065       delete decl.data(top);
1066 }
1067
1068 void DUContext::deleteChildContextsRecursively()
1069 {
1070   ENSURE_CAN_WRITE
1071   DUCHAIN_D_DYNAMIC(DUContext);
1072   QVector<LocalIndexedDUContext> children;
1073   FOREACH_FUNCTION(LocalIndexedDUContext ctx, d->m_childContexts)
1074     children << ctx;
1075
1076   TopDUContext* top = topContext();
1077   //If we are deleting a context that is already stored to disk, we don't need to load not yet loaded child-contexts.
1078   //Else we need to, so the declarations are unregistered from symbol-table and from TopDUContextDynamicData in their destructor
1079   foreach(LocalIndexedDUContext ctx, children)
1080     if(ctx.isLoaded(top) || !top->deleting() || !top->isOnDisk())
1081       delete ctx.data(top);
1082 }
1083
1084 QVector< Declaration * > DUContext::clearLocalDeclarations( )
1085 {
1086   QVector< Declaration * > ret = localDeclarations();
1087   foreach (Declaration* dec, ret)
1088     dec->setContext(0);
1089   return ret;
1090 }
1091
1092 QualifiedIdentifier DUContext::scopeIdentifier(bool includeClasses) const
1093 {
1094   ENSURE_CAN_READ
1095
1096   QualifiedIdentifier ret;
1097   m_dynamicData->scopeIdentifier(includeClasses, ret);
1098
1099   return ret;
1100 }
1101
1102 bool DUContext::equalScopeIdentifier(const DUContext* rhs) const
1103 {
1104   ENSURE_CAN_READ
1105
1106   const DUContext* left = this;
1107   const DUContext* right = rhs;
1108
1109   while(left || right) {
1110     if(!left || !right)
1111       return false;
1112
1113     if(!(left->d_func()->m_scopeIdentifier == right->d_func()->m_scopeIdentifier))
1114       return false;
1115
1116     left = left->parentContext();
1117     right = right->parentContext();
1118   }
1119
1120   return true;
1121 }
1122
1123 void DUContext::setLocalScopeIdentifier(const QualifiedIdentifier & identifier)
1124 {
1125   ENSURE_CAN_WRITE
1126   //Q_ASSERT(d_func()->m_childContexts.isEmpty() && d_func()->m_localDeclarations.isEmpty());
1127   bool wasInSymbolTable = inSymbolTable();
1128   setInSymbolTable(false);
1129   d_func_dynamic()->m_scopeIdentifier = identifier;
1130   setInSymbolTable(wasInSymbolTable);
1131   //DUChain::contextChanged(this, DUChainObserver::Change, DUChainObserver::Identifier);
1132 }
1133
1134 const QualifiedIdentifier DUContext::localScopeIdentifier() const
1135 {
1136   //ENSURE_CAN_READ Commented out for performance reasons
1137
1138   return d_func()->m_scopeIdentifier;
1139 }
1140
1141 DUContext::ContextType DUContext::type() const
1142 {
1143   //ENSURE_CAN_READ This is disabled, because type() is called very often while searching, and it costs us performance
1144
1145   return d_func()->m_contextType;
1146 }
1147
1148 void DUContext::setType(ContextType type)
1149 {
1150   ENSURE_CAN_WRITE
1151
1152   bool wasNamespaceInCodeModel = d_func()->m_inSymbolTable && d_func()->m_contextType == DUContext::Namespace && d_func()->m_scopeIdentifier.isValid();
1153
1154   d_func_dynamic()->m_contextType = type;
1155
1156   bool shouldBeNamespaceInCodeModel = d_func()->m_inSymbolTable && d_func()->m_contextType == DUContext::Namespace && d_func()->m_scopeIdentifier.isValid();
1157
1158   if(wasNamespaceInCodeModel && shouldBeNamespaceInCodeModel) {
1159     //We're fine
1160   }else if(!wasNamespaceInCodeModel && shouldBeNamespaceInCodeModel) {
1161     //Add
1162     QualifiedIdentifier id(scopeIdentifier(true));
1163     CodeModel::self().addItem(url(), id, CodeModelItem::Namespace);
1164   }else if(wasNamespaceInCodeModel && !shouldBeNamespaceInCodeModel) {
1165     //Remove
1166     QualifiedIdentifier id(scopeIdentifier(true));
1167     CodeModel::self().removeItem(url(), id);
1168   }
1169
1170   //DUChain::contextChanged(this, DUChainObserver::Change, DUChainObserver::ContextType);
1171 }
1172
1173 QList<Declaration*> DUContext::findDeclarations(const Identifier& identifier, const SimpleCursor& position, const TopDUContext* topContext, SearchFlags flags) const
1174 {
1175   ENSURE_CAN_READ
1176
1177   DeclarationList ret;
1178   SearchItem::PtrList identifiers;
1179   identifiers << SearchItem::Ptr(new SearchItem(QualifiedIdentifier(identifier)));
1180   findDeclarationsInternal(identifiers, position.isValid() ? position : range().end, AbstractType::Ptr(), ret, topContext ? topContext : this->topContext(), flags);
1181   return arrayToList(ret);
1182 }
1183
1184 void DUContext::deleteUse(int index)
1185 {
1186   ENSURE_CAN_WRITE
1187   DUCHAIN_D_DYNAMIC(DUContext);
1188   removeFromArray(d->m_usesList(), index);
1189
1190   if(!m_dynamicData->m_rangesForUses.isEmpty()) {
1191     if(m_dynamicData->m_rangesForUses[index]) {
1192       EditorIntegrator editor;
1193       editor.setCurrentUrl(url(), (bool)smartRange());
1194       LockedSmartInterface iface = editor.smart();
1195       if (iface) {
1196         m_dynamicData->m_rangesForUses[index]->removeWatcher(this);
1197         EditorIntegrator::releaseRange(m_dynamicData->m_rangesForUses[index]);
1198       }
1199     }
1200     m_dynamicData->m_rangesForUses.remove(index);
1201   }
1202 }
1203
1204 void DUContext::deleteUses()
1205 {
1206   ENSURE_CAN_WRITE
1207   DUCHAIN_D_DYNAMIC(DUContext);
1208
1209   d->m_usesList().clear();
1210
1211   clearUseSmartRanges();
1212 }
1213
1214 bool DUContext::inDUChain() const {
1215   if( d_func()->m_anonymousInParent )
1216     return false;
1217
1218   TopDUContext* top = topContext();
1219   return top && top->inDuChain();
1220 }
1221
1222 DUContext* DUContext::specialize(uint /*specialization*/, const TopDUContext* /*topContext*/, int /*upDistance*/) {
1223   return this;
1224 }
1225
1226 SimpleCursor DUContext::importPosition(const DUContext* target) const
1227 {
1228   ENSURE_CAN_READ
1229   DUCHAIN_D(DUContext);
1230   for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a)
1231     if(d->m_importedContexts()[a].context() == target)
1232       return d->m_importedContexts()[a].position;
1233   return SimpleCursor::invalid();
1234 }
1235
1236 QVector<DUContext::Import> DUContext::importedParentContexts() const
1237 {
1238   ENSURE_CAN_READ
1239   QVector<DUContext::Import> ret;
1240   FOREACH_FUNCTION(const DUContext::Import& import, d_func()->m_importedContexts)
1241     ret << import;
1242   return ret;
1243 }
1244
1245 QList<DUContext*> DUContext::findContexts(ContextType contextType, const QualifiedIdentifier& identifier, const SimpleCursor& position, SearchFlags flags) const
1246 {
1247   ENSURE_CAN_READ
1248
1249   QList<DUContext*> ret;
1250   SearchItem::PtrList identifiers;
1251   identifiers << SearchItem::Ptr(new SearchItem(identifier));
1252
1253   findContextsInternal(contextType, identifiers, position.isValid() ? position : range().end, ret, flags);
1254   return ret;
1255 }
1256
1257 void DUContext::applyAliases(const SearchItem::PtrList& baseIdentifiers, SearchItem::PtrList& identifiers, const SimpleCursor& position, bool canBeNamespace) const {
1258
1259   QList<Declaration*> imports = allLocalDeclarations(globalImportIdentifier);
1260
1261   FOREACH_ARRAY( const SearchItem::Ptr& identifier, baseIdentifiers ) {
1262     bool addUnmodified = true;
1263
1264     if( !identifier->isExplicitlyGlobal ) {
1265
1266       if( !imports.isEmpty() )
1267       {
1268         //We have namespace-imports.
1269         foreach( Declaration* importDecl, imports )
1270         {
1271           if( importDecl->range().end > position )
1272             continue;
1273           //Search for the identifier with the import-identifier prepended
1274           Q_ASSERT(dynamic_cast<NamespaceAliasDeclaration*>(importDecl));
1275           NamespaceAliasDeclaration* alias = static_cast<NamespaceAliasDeclaration*>(importDecl);
1276           identifiers.append( SearchItem::Ptr( new SearchItem( alias->importIdentifier(), identifier ) ) ) ;
1277         }
1278       }
1279
1280       if( !identifier->isEmpty() && (identifier->hasNext() || canBeNamespace) ) {
1281         QList<Declaration*> aliases = allLocalDeclarations(identifier->identifier);
1282         if(!aliases.isEmpty()) {
1283           //The first part of the identifier has been found as a namespace-alias.
1284           //In c++, we only need the first alias. However, just to be correct, follow them all for now.
1285           foreach( Declaration* aliasDecl, aliases )
1286           {
1287             if( aliasDecl->range().end > position )
1288               continue;
1289             if(!dynamic_cast<NamespaceAliasDeclaration*>(aliasDecl))
1290               continue;
1291
1292             addUnmodified = false; //The un-modified identifier can be ignored, because it will be replaced with the resolved alias
1293             NamespaceAliasDeclaration* alias = static_cast<NamespaceAliasDeclaration*>(aliasDecl);
1294
1295             //Create an identifier where namespace-alias part is replaced with the alias target
1296             identifiers.append( SearchItem::Ptr( new SearchItem( alias->importIdentifier(), identifier->next ) ) ) ;
1297           }
1298         }
1299       }
1300     }
1301
1302     if( addUnmodified )
1303         identifiers.append(identifier);
1304   }
1305 }
1306
1307 void DUContext::applyUpwardsAliases(SearchItem::PtrList& identifiers) const {
1308
1309   if(type() == Namespace) {
1310     QualifiedIdentifier localId = d_func()->m_scopeIdentifier;
1311     if(localId.isEmpty())
1312       return;
1313
1314     //Make sure we search for the items in all namespaces of the same name, by duplicating each one with the namespace-identifier prepended.
1315     //We do this by prepending items to the current identifiers that equal the local scope identifier.
1316     SearchItem::Ptr newItem( new SearchItem(localId) );
1317
1318     //This will exclude explictly global identifiers
1319     newItem->addToEachNode( identifiers );
1320
1321     if(!newItem->next.isEmpty()) {
1322       //Prepend the full scope before newItem
1323       DUContext* parent = m_dynamicData->m_parentContext.data();
1324       while(parent) {
1325         newItem = SearchItem::Ptr( new SearchItem(parent->d_func()->m_scopeIdentifier, newItem) );
1326         parent = parent->m_dynamicData->m_parentContext.data();
1327       }
1328
1329       newItem->isExplicitlyGlobal = true;
1330       insertToArray(identifiers, newItem, 0);
1331     }
1332   }
1333 }
1334
1335 void DUContext::findContextsInternal(ContextType contextType, const SearchItem::PtrList& baseIdentifiers, const SimpleCursor& position, QList<DUContext*>& ret, SearchFlags flags) const
1336 {
1337   DUCHAIN_D(DUContext);
1338   if (contextType == type()) {
1339     FOREACH_ARRAY( const SearchItem::Ptr& identifier, baseIdentifiers )
1340       if (identifier->match(scopeIdentifier(true)) && (!parentContext() || !identifier->isExplicitlyGlobal) )
1341         ret.append(const_cast<DUContext*>(this));
1342   }
1343   ///@todo This doesn't seem quite correct: Local Contexts aren't found anywhere
1344   ///Step 1: Apply namespace-aliases and -imports
1345   SearchItem::PtrList aliasedIdentifiers;
1346   //Because of namespace-imports and aliases, this identifier may need to be searched as under multiple names
1347   applyAliases(baseIdentifiers, aliasedIdentifiers, position, contextType == Namespace);
1348
1349   if( d->m_importedContextsSize() != 0 ) {
1350     ///Step 2: Give identifiers that are not marked as explicitly-global to imported contexts(explicitly global ones are treatead in TopDUContext)
1351     SearchItem::PtrList nonGlobalIdentifiers;
1352     FOREACH_ARRAY( const SearchItem::Ptr& identifier, aliasedIdentifiers )
1353       if( !identifier->isExplicitlyGlobal )
1354         nonGlobalIdentifiers << identifier;
1355
1356     if( !nonGlobalIdentifiers.isEmpty() ) {
1357       for(int a = d->m_importedContextsSize()-1; a >= 0; --a) {
1358
1359         DUContext* context = d->m_importedContexts()[a].context();
1360
1361         while( !context && a > 0 ) {
1362           --a;
1363           context = d->m_importedContexts()[a].context();
1364         }
1365
1366         if(context == this) {
1367           kDebug() << "resolved self as import:" << scopeIdentifier(true);
1368           continue;
1369         }
1370
1371         if( !context )
1372           break;
1373
1374         context->findContextsInternal(contextType, nonGlobalIdentifiers, url() == context->url() ? position : context->range().end, ret, flags | InImportedParentContext);
1375       }
1376     }
1377   }
1378
1379   ///Step 3: Continue search in parent
1380   if ( !(flags & DontSearchInParent) && shouldSearchInParent(flags) && parentContext()) {
1381     applyUpwardsAliases(aliasedIdentifiers);
1382     parentContext()->findContextsInternal(contextType, aliasedIdentifiers, url() == parentContext()->url() ? position : parentContext()->range().end, ret, flags);
1383   }
1384 }
1385
1386 bool DUContext::shouldSearchInParent(SearchFlags flags) const
1387 {
1388   return !(flags & InImportedParentContext);
1389 }
1390
1391 const Use* DUContext::uses() const
1392 {
1393   ENSURE_CAN_READ
1394
1395   synchronizeUsesFromSmart();
1396   return d_func()->m_uses();
1397 }
1398
1399 int DUContext::usesCount() const
1400 {
1401   return d_func()->m_usesSize();
1402 }
1403
1404 int DUContext::createUse(int declarationIndex, const SimpleRange& range, KTextEditor::SmartRange* smartRange, int insertBefore)
1405 {
1406   DUCHAIN_D_DYNAMIC(DUContext);
1407   ENSURE_CAN_WRITE
1408
1409   if(insertBefore == -1) {
1410     //Find position where to insert
1411     unsigned int a = 0;
1412     for(; a < d->m_usesSize() && range.start > d->m_uses()[a].m_range.start; ++a) { ///@todo do binary search
1413     }
1414     insertBefore = a;
1415   }
1416
1417   insertToArray(d->m_usesList(), Use(range, declarationIndex), insertBefore);
1418   if(smartRange) {
1419     Q_ASSERT(uint(m_dynamicData->m_rangesForUses.size()) == d->m_usesSize()-1);
1420     m_dynamicData->m_rangesForUses.insert(insertBefore, smartRange);
1421     smartRange->addWatcher(this);
1422 //     smartRange->setWantsDirectChanges(true);
1423
1424     d->m_usesList()[insertBefore].m_range = SimpleRange(*smartRange);
1425   }else{
1426     // This can happen eg. when a document is closed during its parsing, and has no ill effects.
1427     //Q_ASSERT(m_dynamicData->m_rangesForUses.isEmpty());
1428   }
1429
1430   return insertBefore;
1431 }
1432
1433 KTextEditor::SmartRange* DUContext::useSmartRange(int useIndex)
1434 {
1435   ENSURE_CAN_READ
1436   if(m_dynamicData->m_rangesForUses.isEmpty())
1437     return 0;
1438   else{
1439     if(useIndex >= 0 && useIndex < m_dynamicData->m_rangesForUses.size())
1440       return m_dynamicData->m_rangesForUses.at(useIndex);
1441     else
1442       return 0;
1443   }
1444 }
1445
1446
1447 void DUContext::setUseSmartRange(int useIndex, KTextEditor::SmartRange* range)
1448 {
1449   ENSURE_CAN_WRITE
1450   if(m_dynamicData->m_rangesForUses.isEmpty())
1451       m_dynamicData->m_rangesForUses.insert(0, d_func()->m_usesSize(), 0);
1452
1453   Q_ASSERT(uint(m_dynamicData->m_rangesForUses.size()) == d_func()->m_usesSize());
1454
1455   if(m_dynamicData->m_rangesForUses[useIndex]) {
1456     EditorIntegrator editor;
1457     editor.setCurrentUrl(url(), (bool)range);
1458     LockedSmartInterface iface = editor.smart();
1459     if (iface) {
1460       m_dynamicData->m_rangesForUses[useIndex]->removeWatcher(this);
1461       EditorIntegrator::releaseRange(m_dynamicData->m_rangesForUses[useIndex]);
1462     }
1463   }
1464
1465   m_dynamicData->m_rangesForUses[useIndex] = range;
1466   d_func_dynamic()->m_usesList()[useIndex].m_range = SimpleRange(*range);
1467   range->addWatcher(this);
1468 //   range->setWantsDirectChanges(true);
1469 }
1470
1471 void DUContext::clearUseSmartRanges()
1472 {
1473   ENSURE_CAN_WRITE
1474
1475   if (!m_dynamicData->m_rangesForUses.isEmpty()) {
1476     EditorIntegrator editor;
1477     editor.setCurrentUrl(url(), (bool)smartRange());
1478     LockedSmartInterface iface = editor.smart();
1479     if (iface) {
1480       foreach (SmartRange* range, m_dynamicData->m_rangesForUses) {
1481         range->removeWatcher(this);
1482         EditorIntegrator::releaseRange(range);
1483       }
1484     }
1485
1486     m_dynamicData->m_rangesForUses.clear();
1487   }
1488 }
1489
1490 void DUContext::setUseDeclaration(int useNumber, int declarationIndex)
1491 {
1492   ENSURE_CAN_WRITE
1493   d_func_dynamic()->m_usesList()[useNumber].m_declarationIndex = declarationIndex;
1494 }
1495
1496
1497 DUContext * DUContext::findContextAt(const SimpleCursor & position) const
1498 {
1499   ENSURE_CAN_READ
1500
1501   if (!range().contains(position))
1502     return 0;
1503
1504   FOREACH_FUNCTION(LocalIndexedDUContext child, d_func()->m_childContexts)
1505     if (DUContext* specific = child.data(topContext())->findContextAt(position))
1506       return specific;
1507
1508   return const_cast<DUContext*>(this);
1509 }
1510
1511 DUContext* DUContext::findContextIncluding(const SimpleRange& range) const
1512 {
1513   ENSURE_CAN_READ
1514
1515   if (!this->range().contains(range))
1516     return 0;
1517
1518   FOREACH_FUNCTION(LocalIndexedDUContext child, d_func()->m_childContexts)
1519     if (DUContext* specific = child.data(topContext())->findContextIncluding(range))
1520       return specific;
1521
1522   return const_cast<DUContext*>(this);
1523 }
1524
1525 int DUContext::findUseAt(const SimpleCursor & position) const
1526 {
1527   ENSURE_CAN_READ
1528
1529   synchronizeUsesFromSmart();
1530
1531   if (!range().contains(position))
1532     return -1;
1533
1534   for(unsigned int a = 0; a < d_func()->m_usesSize(); ++a)
1535     if (d_func()->m_uses()[a].m_range.contains(position))
1536       return a;
1537
1538   return -1;
1539 }
1540
1541 bool DUContext::inSymbolTable() const
1542 {
1543   return d_func()->m_inSymbolTable;
1544 }
1545
1546 void DUContext::setInSymbolTable(bool inSymbolTable)
1547 {
1548     if(parentContext()) {
1549       if(!d_func()->m_inSymbolTable && inSymbolTable) {
1550         QualifiedIdentifier id(scopeIdentifier(true));
1551         PersistentSymbolTable::self().addContext(id, this);
1552
1553         if(d_func()->m_contextType == DUContext::Namespace)
1554           CodeModel::self().addItem(url(), id, CodeModelItem::Namespace);
1555       }else if(d_func()->m_inSymbolTable && !inSymbolTable) {
1556         QualifiedIdentifier id(scopeIdentifier(true));
1557         PersistentSymbolTable::self().removeContext(id, this);
1558
1559         if(d_func()->m_contextType == DUContext::Namespace)
1560           CodeModel::self().removeItem(url(), id);
1561       }
1562     }
1563
1564   d_func_dynamic()->m_inSymbolTable = inSymbolTable;
1565 }
1566
1567 // kate: indent-width 2;
1568
1569 void DUContext::clearImportedParentContexts()
1570 {
1571   ENSURE_CAN_WRITE
1572   DUCHAIN_D_DYNAMIC(DUContext);
1573
1574   while(d->m_importedContextsSize())
1575     removeImportedParentContext(d->m_importedContexts()[0].context());
1576 }
1577
1578 void DUContext::cleanIfNotEncountered(const QSet<DUChainBase*>& encountered)
1579 {
1580   ENSURE_CAN_WRITE
1581
1582   foreach (Declaration* dec, localDeclarations())
1583     if (!encountered.contains(dec))
1584       delete dec;
1585
1586   FOREACH_FUNCTION(LocalIndexedDUContext childContext, d_func()->m_childContexts)
1587     if (!encountered.contains(childContext.data(topContext())))
1588       delete childContext.data(topContext());
1589 }
1590
1591 TopDUContext* DUContext::topContext() const
1592 {
1593   return m_dynamicData->m_topContext;
1594 }
1595
1596 QWidget* DUContext::createNavigationWidget(Declaration* /*decl*/, TopDUContext* /*topContext*/, const QString& /*htmlPrefix*/, const QString& /*htmlSuffix*/) const
1597 {
1598   return 0;
1599 }
1600
1601 void DUContext::squeeze()
1602 {
1603   if(!m_dynamicData->m_rangesForUses.isEmpty())
1604     m_dynamicData->m_rangesForUses.squeeze();
1605
1606   FOREACH_FUNCTION(LocalIndexedDUContext child, d_func()->m_childContexts)
1607     child.data(topContext())->squeeze();
1608 }
1609
1610 QList<SimpleRange> allUses(DUContext* context, int declarationIndex, bool noEmptyUses)
1611 {
1612   QList<SimpleRange> ret;
1613   for(int a = 0; a < context->usesCount(); ++a)
1614     if(context->uses()[a].m_declarationIndex == declarationIndex)
1615       if(!noEmptyUses || !context->uses()[a].m_range.isEmpty())
1616         ret << context->uses()[a].m_range;
1617
1618   foreach(DUContext* child, context->childContexts())
1619     ret += allUses(child, declarationIndex, noEmptyUses);
1620
1621   return ret;
1622 }
1623
1624 QList<KTextEditor::SmartRange*> allSmartUses(DUContext* context, int declarationIndex)
1625 {
1626   QList<KTextEditor::SmartRange*> ret;
1627
1628   const Use* uses(context->uses());
1629
1630   for(int a = 0; a < context->usesCount(); ++a)
1631     if(uses[a].m_declarationIndex == declarationIndex) {
1632       KTextEditor::SmartRange* range = context->useSmartRange(a);
1633       if(range)
1634         ret << range;
1635     }
1636
1637   foreach(DUContext* child, context->childContexts())
1638     ret += allSmartUses(child, declarationIndex);
1639
1640   return ret;
1641 }
1642
1643 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, Ptr nextItem, int start) : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false) {
1644   if(!id.isEmpty()) {
1645     if(id.count() > start)
1646       identifier = id.at(start);
1647
1648     if(id.count() > start+1)
1649       addNext(Ptr( new SearchItem(id, nextItem, start+1) ));
1650     else if(nextItem)
1651       next.append(nextItem);
1652   }else if(nextItem) {
1653     ///If there is no prefix, just copy nextItem
1654     isExplicitlyGlobal = nextItem->isExplicitlyGlobal;
1655     identifier = nextItem->identifier;
1656     next = nextItem->next;
1657   }
1658 }
1659
1660 DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const PtrList& nextItems, int start) : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false) {
1661   if(id.count() > start)
1662     identifier = id.at(start);
1663
1664   if(id.count() > start+1)
1665     addNext(Ptr( new SearchItem(id, nextItems, start+1) ));
1666   else
1667     next = nextItems;
1668 }
1669
1670 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, Identifier id, const PtrList& nextItems) : isExplicitlyGlobal(explicitlyGlobal), identifier(id), next(nextItems) {
1671 }
1672
1673 DUContext::SearchItem::SearchItem(bool explicitlyGlobal, Identifier id, Ptr nextItem) : isExplicitlyGlobal(explicitlyGlobal), identifier(id) {
1674   next.append(nextItem);
1675 }
1676
1677 bool DUContext::SearchItem::match(const QualifiedIdentifier& id, int offset) const {
1678   if(id.isEmpty()) {
1679     if(identifier.isEmpty() && next.isEmpty())
1680       return true;
1681     else
1682       return false;
1683   }
1684
1685   if(id.at(offset) != identifier) //The identifier is different
1686     return false;
1687
1688   if(offset == id.count()-1) {
1689     if(next.isEmpty())
1690       return true; //match
1691     else
1692       return false; //id is too short
1693   }
1694
1695   for(int a = 0; a < next.size(); ++a)
1696     if(next[a]->match(id, offset+1))
1697       return true;
1698
1699   return false;
1700 }
1701
1702 bool DUContext::SearchItem::isEmpty() const {
1703   return identifier.isEmpty();
1704 }
1705
1706 bool DUContext::SearchItem::hasNext() const {
1707   return !next.isEmpty();
1708 }
1709
1710 QList<QualifiedIdentifier> DUContext::SearchItem::toList(const QualifiedIdentifier& prefix) const {
1711   QList<QualifiedIdentifier> ret;
1712
1713   QualifiedIdentifier id = prefix;
1714   if(id.isEmpty())
1715   id.setExplicitlyGlobal(isExplicitlyGlobal);
1716   if(!identifier.isEmpty())
1717     id.push(identifier);
1718
1719   if(next.isEmpty()) {
1720     ret << id;
1721   } else {
1722     for(int a = 0; a < next.size(); ++a)
1723       ret += next[a]->toList(id);
1724   }
1725   return ret;
1726 }
1727
1728
1729 void DUContext::SearchItem::addNext(SearchItem::Ptr other) {
1730   next.append(other);
1731 }
1732
1733 void DUContext::SearchItem::addToEachNode(SearchItem::Ptr other) {
1734   if(other->isExplicitlyGlobal)
1735     return;
1736
1737   next.append(other);
1738   for(int a = 0; a < next.size()-1; ++a)
1739     next[a]->addToEachNode(other);
1740 }
1741
1742 void DUContext::SearchItem::addToEachNode(SearchItem::PtrList other) {
1743   int added = 0;
1744   FOREACH_ARRAY(SearchItem::Ptr o, other) {
1745     if(!o->isExplicitlyGlobal) {
1746       next.append(o);
1747       ++added;
1748     }
1749   }
1750
1751   for(int a = 0; a < next.size()-added; ++a)
1752     next[a]->addToEachNode(other);
1753 }
1754
1755 DUContext::Import::Import(DUContext* _context, const SimpleCursor& _position) : position(_position) {
1756   if(_context && _context->owner() && _context->owner()->specialization()) {
1757     m_declaration = _context->owner()->id(true);
1758   }else{
1759     m_context = _context;
1760   }
1761 }
1762 DUContext* DUContext::Import::context() const {
1763   if(m_declaration.isValid()) {
1764     Declaration* decl = m_declaration.getDeclaration(0);
1765     if(decl)
1766       return decl->internalContext();
1767     else
1768       return 0;
1769   }else{
1770     return m_context.data();
1771   }
1772 }
1773
1774 }
1775
1776 // kate: space-indent on; indent-width 2; tab-width 4; replace-tabs on; auto-insert-doxygen on