diff --git a/language/duchain/ducontext.cpp b/language/duchain/ducontext.cpp index b122cc7ec7..8945957456 100644 --- a/language/duchain/ducontext.cpp +++ b/language/duchain/ducontext.cpp @@ -1,1706 +1,1706 @@ /* This is part of KDevelop Copyright 2006 Hamish Rodda Copyright 2007-2009 David Nolden This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License version 2 as published by the Free Software Foundation. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "ducontext.h" #include #include #include #include #include #include "ducontextdata.h" #include "declaration.h" #include "duchain.h" #include "duchainlock.h" #include "use.h" #include "identifier.h" #include "topducontext.h" #include "persistentsymboltable.h" #include "aliasdeclaration.h" #include "namespacealiasdeclaration.h" #include "abstractfunctiondeclaration.h" #include "duchainregister.h" #include "topducontextdynamicdata.h" #include "importers.h" #include "uses.h" #include "navigation/abstractdeclarationnavigationcontext.h" #include "navigation/abstractnavigationwidget.h" #include "ducontextdynamicdata.h" #include "util/debug.h" // maximum depth for DUContext::findDeclarationsInternal searches const uint maxParentDepth = 20; using namespace KTextEditor; #ifndef NDEBUG #define ENSURE_CAN_WRITE_(x) {if(x->inDUChain()) { ENSURE_CHAIN_WRITE_LOCKED }} #define ENSURE_CAN_READ_(x) {if(x->inDUChain()) { ENSURE_CHAIN_READ_LOCKED }} #else #define ENSURE_CAN_WRITE_(x) #define ENSURE_CAN_READ_(x) #endif QDebug operator<<(QDebug dbg, const KDevelop::DUContext::Import& import) { QDebugStateSaver saver(dbg); dbg.nospace() << "Import(" << import.indexedContext().data() << ')'; return dbg; } namespace KDevelop { DEFINE_LIST_MEMBER_HASH(DUContextData, m_childContexts, LocalIndexedDUContext) DEFINE_LIST_MEMBER_HASH(DUContextData, m_importers, IndexedDUContext) DEFINE_LIST_MEMBER_HASH(DUContextData, m_importedContexts, DUContext::Import) DEFINE_LIST_MEMBER_HASH(DUContextData, m_localDeclarations, LocalIndexedDeclaration) DEFINE_LIST_MEMBER_HASH(DUContextData, m_uses, Use) REGISTER_DUCHAIN_ITEM(DUContext); DUChainVisitor::~DUChainVisitor() { } /** * We leak here, to prevent a possible crash during destruction, as the destructor * of Identifier is not safe to be called after the duchain has been destroyed */ const Identifier& globalImportIdentifier() { static const Identifier globalImportIdentifierObject(QStringLiteral("{...import...}")); return globalImportIdentifierObject; } const Identifier& globalAliasIdentifier() { static const Identifier globalAliasIdentifierObject(QStringLiteral("{...alias...}")); return globalAliasIdentifierObject; } const IndexedIdentifier& globalIndexedImportIdentifier() { static const IndexedIdentifier id(globalImportIdentifier()); return id; } const IndexedIdentifier& globalIndexedAliasIdentifier() { static const IndexedIdentifier id(globalAliasIdentifier()); return id; } void DUContext::rebuildDynamicData(DUContext* parent, uint ownIndex) { Q_ASSERT(!parent || ownIndex); m_dynamicData->m_topContext = parent ? parent->topContext() : static_cast(this); m_dynamicData->m_indexInTopContext = ownIndex; m_dynamicData->m_parentContext = DUContextPointer(parent); m_dynamicData->m_context = this; m_dynamicData->m_childContexts.clear(); m_dynamicData->m_childContexts.reserve(d_func()->m_childContextsSize()); FOREACH_FUNCTION(const LocalIndexedDUContext& ctx, d_func()->m_childContexts) { m_dynamicData->m_childContexts << ctx.data(m_dynamicData->m_topContext); } m_dynamicData->m_localDeclarations.clear(); m_dynamicData->m_localDeclarations.reserve(d_func()->m_localDeclarationsSize()); FOREACH_FUNCTION(const LocalIndexedDeclaration& idx, d_func()->m_localDeclarations) { auto declaration = idx.data(m_dynamicData->m_topContext); if (!declaration) { qCWarning(LANGUAGE) << "child declaration number" << idx.localIndex() << "of" << d_func_dynamic()->m_localDeclarationsSize() << "is invalid"; continue; } m_dynamicData->m_localDeclarations << declaration; } DUChainBase::rebuildDynamicData(parent, ownIndex); } DUContextData::DUContextData() : m_inSymbolTable(false) , m_anonymousInParent(false) , m_propagateDeclarations(false) { initializeAppendedLists(); } DUContextData::~DUContextData() { freeAppendedLists(); } DUContextData::DUContextData(const DUContextData& rhs) : DUChainBaseData(rhs) , m_inSymbolTable(rhs.m_inSymbolTable) , m_anonymousInParent(rhs.m_anonymousInParent) , m_propagateDeclarations(rhs.m_propagateDeclarations) { initializeAppendedLists(); copyListsFrom(rhs); m_scopeIdentifier = rhs.m_scopeIdentifier; m_contextType = rhs.m_contextType; m_owner = rhs.m_owner; } DUContextDynamicData::DUContextDynamicData(DUContext* d) : m_topContext(0) , m_indexInTopContext(0) , m_context(d) { } void DUContextDynamicData::scopeIdentifier(bool includeClasses, QualifiedIdentifier& target) const { if (m_parentContext) m_parentContext->m_dynamicData->scopeIdentifier(includeClasses, target); if (includeClasses || d_func()->m_contextType != DUContext::Class) target += d_func()->m_scopeIdentifier; } bool DUContextDynamicData::imports(const DUContext* context, const TopDUContext* source, QSet* recursionGuard) const { if( this == context->m_dynamicData ) return true; if (recursionGuard->contains(this)) { return false; } recursionGuard->insert(this); FOREACH_FUNCTION( const DUContext::Import& ctx, d_func()->m_importedContexts ) { DUContext* import = ctx.context(source); if(import == context || (import && import->m_dynamicData->imports(context, source, recursionGuard))) return true; } return false; } inline bool isContextTemporary(uint index) { return index > (0xffffffff/2); } void DUContextDynamicData::addDeclaration( Declaration * newDeclaration ) { // The definition may not have its identifier set when it's assigned... // allow dupes here, TODO catch the error elsewhere //If this context is temporary, added declarations should be as well, and viceversa Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(newDeclaration->ownIndex())); CursorInRevision start = newDeclaration->range().start; bool inserted = false; ///@todo Do binary search to find the position for (int i = m_localDeclarations.size() - 1; i >= 0; --i) { Declaration* child = m_localDeclarations[i]; Q_ASSERT(d_func()->m_localDeclarations()[i].data(m_topContext) == child); if(child == newDeclaration) return; //TODO: All declarations in a macro will have the same empty range, and just get appended //that may not be Good Enough in complex cases. if (start >= child->range().start) { m_localDeclarations.insert(i + 1, newDeclaration); d_func_dynamic()->m_localDeclarationsList().insert(i+1, newDeclaration); Q_ASSERT(d_func()->m_localDeclarations()[i+1].data(m_topContext) == newDeclaration); inserted = true; break; } } if (!inserted) { // We haven't found any child that is before this one, so prepend it m_localDeclarations.insert(0, newDeclaration); d_func_dynamic()->m_localDeclarationsList().insert(0, newDeclaration); Q_ASSERT(d_func()->m_localDeclarations()[0].data(m_topContext) == newDeclaration); } } bool DUContextDynamicData::removeDeclaration(Declaration* declaration) { const int idx = m_localDeclarations.indexOf(declaration); if (idx != -1) { Q_ASSERT(d_func()->m_localDeclarations()[idx].data(m_topContext) == declaration); m_localDeclarations.remove(idx); d_func_dynamic()->m_localDeclarationsList().remove(idx); return true; } else { Q_ASSERT(d_func_dynamic()->m_localDeclarationsList().indexOf(LocalIndexedDeclaration(declaration)) == -1); return false; } } void DUContextDynamicData::addChildContext( DUContext * context ) { // Internal, don't need to assert a lock Q_ASSERT(!context->m_dynamicData->m_parentContext || context->m_dynamicData->m_parentContext.data()->m_dynamicData == this ); LocalIndexedDUContext indexed(context->m_dynamicData->m_indexInTopContext); //If this context is temporary, added declarations should be as well, and viceversa Q_ASSERT(isContextTemporary(m_indexInTopContext) == isContextTemporary(indexed.localIndex())); bool inserted = false; int childCount = m_childContexts.size(); for (int i = childCount-1; i >= 0; --i) {///@todo Do binary search to find the position DUContext* child = m_childContexts[i]; Q_ASSERT(d_func_dynamic()->m_childContexts()[i] == LocalIndexedDUContext(child)); if (context == child) return; if (context->range().start >= child->range().start) { m_childContexts.insert(i+1, context); d_func_dynamic()->m_childContextsList().insert(i+1, indexed); context->m_dynamicData->m_parentContext = m_context; inserted = true; break; } } if( !inserted ) { m_childContexts.insert(0, context); d_func_dynamic()->m_childContextsList().insert(0, indexed); context->m_dynamicData->m_parentContext = m_context; } } bool DUContextDynamicData::removeChildContext( DUContext* context ) { // ENSURE_CAN_WRITE const int idx = m_childContexts.indexOf(context); if (idx != -1) { m_childContexts.remove(idx); Q_ASSERT(d_func()->m_childContexts()[idx] == LocalIndexedDUContext(context)); d_func_dynamic()->m_childContextsList().remove(idx); return true; } else { Q_ASSERT(d_func_dynamic()->m_childContextsList().indexOf(LocalIndexedDUContext(context)) == -1); return false; } } void DUContextDynamicData::addImportedChildContext( DUContext * context ) { // ENSURE_CAN_WRITE DUContext::Import import(m_context, context); if(import.isDirect()) { //Direct importers are registered directly within the data if(d_func_dynamic()->m_importersList().contains(IndexedDUContext(context))) { qCDebug(LANGUAGE) << m_context->scopeIdentifier(true).toString() << "importer added multiple times:" << context->scopeIdentifier(true).toString(); return; } d_func_dynamic()->m_importersList().append(context); }else{ //Indirect importers are registered separately Importers::self().addImporter(import.indirectDeclarationId(), IndexedDUContext(context)); } } //Can also be called with a context that is not in the list void DUContextDynamicData::removeImportedChildContext( DUContext * context ) { // ENSURE_CAN_WRITE DUContext::Import import(m_context, context); if(import.isDirect()) { d_func_dynamic()->m_importersList().removeOne(IndexedDUContext(context)); }else{ //Indirect importers are registered separately Importers::self().removeImporter(import.indirectDeclarationId(), IndexedDUContext(context)); } } int DUContext::depth() const { { if (!parentContext()) return 0; return parentContext()->depth() + 1; } } DUContext::DUContext(DUContextData& data) : DUChainBase(data) , m_dynamicData(new DUContextDynamicData(this)) { } DUContext::DUContext(const RangeInRevision& range, DUContext* parent, bool anonymous) : DUChainBase(*new DUContextData(), range) , m_dynamicData(new DUContextDynamicData(this)) { d_func_dynamic()->setClassId(this); if(parent) m_dynamicData->m_topContext = parent->topContext(); else m_dynamicData->m_topContext = static_cast(this); d_func_dynamic()->setClassId(this); DUCHAIN_D_DYNAMIC(DUContext); d->m_contextType = Other; m_dynamicData->m_parentContext = 0; d->m_anonymousInParent = anonymous; d->m_inSymbolTable = false; if (parent) { m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this, parent->isAnonymous() || anonymous); Q_ASSERT(m_dynamicData->m_indexInTopContext); if( !anonymous ) parent->m_dynamicData->addChildContext(this); else m_dynamicData->m_parentContext = parent; } if(parent && !anonymous && parent->inSymbolTable()) setInSymbolTable(true); } bool DUContext::isAnonymous() const { return d_func()->m_anonymousInParent || (m_dynamicData->m_parentContext && m_dynamicData->m_parentContext->isAnonymous()); } DUContext::DUContext( DUContextData& dd, const RangeInRevision& range, DUContext * parent, bool anonymous ) : DUChainBase(dd, range) , m_dynamicData(new DUContextDynamicData(this)) { if(parent) m_dynamicData->m_topContext = parent->topContext(); else m_dynamicData->m_topContext = static_cast(this); DUCHAIN_D_DYNAMIC(DUContext); d->m_contextType = Other; m_dynamicData->m_parentContext = 0; d->m_inSymbolTable = false; d->m_anonymousInParent = anonymous; if (parent) { m_dynamicData->m_indexInTopContext = parent->topContext()->m_dynamicData->allocateContextIndex(this, parent->isAnonymous() || anonymous); if( !anonymous ) parent->m_dynamicData->addChildContext(this); else m_dynamicData->m_parentContext = parent; } } DUContext::DUContext(DUContext& useDataFrom) : DUChainBase(useDataFrom) , m_dynamicData(useDataFrom.m_dynamicData) { } DUContext::~DUContext( ) { TopDUContext* top = topContext(); if(!top->deleting() || !top->isOnDisk()) { DUCHAIN_D_DYNAMIC(DUContext); if(d->m_owner.declaration()) d->m_owner.declaration()->setInternalContext(0); while( d->m_importersSize() != 0 ) { if(d->m_importers()[0].data()) d->m_importers()[0].data()->removeImportedParentContext(this); else { qCDebug(LANGUAGE) << "importer disappeared"; d->m_importersList().removeOne(d->m_importers()[0]); } } clearImportedParentContexts(); } deleteChildContextsRecursively(); if(!topContext()->deleting() || !topContext()->isOnDisk()) deleteUses(); deleteLocalDeclarations(); //If the top-context is being delete, we don't need to spend time rebuilding the inner structure. //That's expensive, especially when the data is not dynamic. if(!top->deleting() || !top->isOnDisk()) { if (m_dynamicData->m_parentContext) m_dynamicData->m_parentContext->m_dynamicData->removeChildContext(this); } top->m_dynamicData->clearContextIndex(this); Q_ASSERT(d_func()->isDynamic() == (!top->deleting() || !top->isOnDisk() || top->m_dynamicData->isTemporaryContextIndex(m_dynamicData->m_indexInTopContext))); delete m_dynamicData; } QVector< DUContext * > DUContext::childContexts( ) const { ENSURE_CAN_READ return m_dynamicData->m_childContexts; } Declaration* DUContext::owner() const { ENSURE_CAN_READ return d_func()->m_owner.declaration(); } void DUContext::setOwner(Declaration* owner) { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); if( owner == d->m_owner.declaration() ) return; Declaration* oldOwner = d->m_owner.declaration(); d->m_owner = owner; //Q_ASSERT(!oldOwner || oldOwner->internalContext() == this); if( oldOwner && oldOwner->internalContext() == this ) oldOwner->setInternalContext(0); //The context set as internal context should always be the last opened context if( owner ) owner->setInternalContext(this); } DUContext* DUContext::parentContext( ) const { //ENSURE_CAN_READ Commented out for performance reasons return m_dynamicData->m_parentContext.data(); } void DUContext::setPropagateDeclarations(bool propagate) { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); if(propagate == d->m_propagateDeclarations) return; d->m_propagateDeclarations = propagate; } bool DUContext::isPropagateDeclarations() const { return d_func()->m_propagateDeclarations; } QList DUContext::findLocalDeclarations( const IndexedIdentifier& identifier, const CursorInRevision& position, const TopDUContext* topContext, const AbstractType::Ptr& dataType, SearchFlags flags ) const { ENSURE_CAN_READ DeclarationList ret; findLocalDeclarationsInternal(identifier, position.isValid() ? position : range().end, dataType, ret, topContext ? topContext : this->topContext(), flags); return ret; } QList DUContext::findLocalDeclarations( const Identifier& identifier, const CursorInRevision& position, const TopDUContext* topContext, const AbstractType::Ptr& dataType, SearchFlags flags ) const { return findLocalDeclarations(IndexedIdentifier(identifier), position, topContext, dataType, flags); } namespace { bool contextIsChildOrEqual(const DUContext* childContext, const DUContext* context) { if(childContext == context) return true; if(childContext->parentContext()) return contextIsChildOrEqual(childContext->parentContext(), context); else return false; } struct Checker { Checker(DUContext::SearchFlags flags, const AbstractType::Ptr& dataType, const CursorInRevision & position, DUContext::ContextType ownType) : m_flags(flags) , m_dataType(dataType) , m_position(position) , m_ownType(ownType) { } Declaration* check(Declaration* declaration) const { ///@todo This is C++-specific if (m_ownType != DUContext::Class && m_ownType != DUContext::Template && m_position.isValid() && m_position <= declaration->range().start) { return nullptr; } if (declaration->kind() == Declaration::Alias && !(m_flags & DUContext::DontResolveAliases)) { //Apply alias declarations AliasDeclaration* alias = static_cast(declaration); if (alias->aliasedDeclaration().isValid()) { declaration = alias->aliasedDeclaration().declaration(); } else { qCDebug(LANGUAGE) << "lost aliased declaration"; } } if (declaration->kind() == Declaration::NamespaceAlias && !(m_flags & DUContext::NoFiltering)) { return nullptr; } if ((m_flags & DUContext::OnlyFunctions) && !declaration->isFunctionDeclaration()) { return nullptr; } if (m_dataType && m_dataType->indexed() != declaration->indexedType()) { return nullptr; } return declaration; } DUContext::SearchFlags m_flags; const AbstractType::Ptr m_dataType; const CursorInRevision m_position; DUContext::ContextType m_ownType; }; } void DUContext::findLocalDeclarationsInternal(const Identifier& identifier, const CursorInRevision& position, const AbstractType::Ptr& dataType, DeclarationList& ret, const TopDUContext* source, SearchFlags flags) const { return findLocalDeclarationsInternal(IndexedIdentifier(identifier), position, dataType, ret, source, flags); } void DUContext::findLocalDeclarationsInternal( const IndexedIdentifier& identifier, const CursorInRevision & position, const AbstractType::Ptr& dataType, DeclarationList& ret, const TopDUContext* /*source*/, SearchFlags flags ) const { Checker checker(flags, dataType, position, type()); DUCHAIN_D(DUContext); if (d->m_inSymbolTable && !d->m_scopeIdentifier.isEmpty() && !identifier.isEmpty()) { //This context is in the symbol table, use the symbol-table to speed up the search QualifiedIdentifier id(scopeIdentifier(true) + identifier); TopDUContext* top = topContext(); uint count; const IndexedDeclaration* declarations; PersistentSymbolTable::self().declarations(id, count, declarations); for (uint a = 0; a < count; ++a) { ///@todo Eventually do efficient iteration-free filtering if (declarations[a].topContextIndex() == top->ownIndex()) { Declaration* decl = declarations[a].declaration(); if (decl && contextIsChildOrEqual(decl->context(), this)) { Declaration* checked = checker.check(decl); if (checked) { ret.append(checked); } } } } } else { //Iterate through all declarations DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData); while (it) { Declaration* declaration = *it; if (declaration && declaration->indexedIdentifier() == identifier) { Declaration* checked = checker.check(declaration); if (checked) ret.append(checked); } ++it; } } } bool DUContext::foundEnough( const DeclarationList& ret, SearchFlags flags ) const { if( !ret.isEmpty() && !(flags & DUContext::NoFiltering)) return true; else return false; } bool DUContext::findDeclarationsInternal( const SearchItem::PtrList & baseIdentifiers, const CursorInRevision & position, const AbstractType::Ptr& dataType, DeclarationList& ret, const TopDUContext* source, SearchFlags flags, uint depth ) const { if (depth > maxParentDepth) { qCDebug(LANGUAGE) << "maximum depth reached in" << scopeIdentifier(true); return false; } DUCHAIN_D(DUContext); if (d->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. for (int a = 0; a < baseIdentifiers.size(); ++a) { if (!baseIdentifiers[a]->isExplicitlyGlobal && baseIdentifiers[a]->next.isEmpty()) { // It makes no sense searching locally for qualified identifiers findLocalDeclarationsInternal(baseIdentifiers[a]->identifier, position, dataType, ret, source, flags); } } if (foundEnough(ret, flags)) { return true; } } ///Step 1: Apply namespace-aliases and -imports SearchItem::PtrList aliasedIdentifiers; //Because of namespace-imports and aliases, this identifier may need to be searched under multiple names applyAliases(baseIdentifiers, aliasedIdentifiers, position, false, type() != DUContext::Namespace && type() != DUContext::Global); if (d->m_importedContextsSize() != 0) { ///Step 2: Give identifiers that are not marked as explicitly-global to imported contexts(explicitly global ones are treatead in TopDUContext) SearchItem::PtrList nonGlobalIdentifiers; foreach (const SearchItem::Ptr& identifier, aliasedIdentifiers) { if (!identifier->isExplicitlyGlobal) { nonGlobalIdentifiers << identifier; } } if (!nonGlobalIdentifiers.isEmpty()) { const auto& url = this->url(); for(int import = d->m_importedContextsSize()-1; import >= 0; --import ) { if (position.isValid() && d->m_importedContexts()[import].position.isValid() && position < d->m_importedContexts()[import].position) { continue; } DUContext* context = d->m_importedContexts()[import].context(source); if (!context) { continue; } else if (context == this) { qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true); continue; } if (!context->findDeclarationsInternal(nonGlobalIdentifiers, url == context->url() ? position : context->range().end, dataType, ret, source, flags | InImportedParentContext, depth+1)) { return false; } } } } if (foundEnough(ret, flags)) { return true; } ///Step 3: Continue search in parent-context if (!(flags & DontSearchInParent) && shouldSearchInParent(flags) && m_dynamicData->m_parentContext) { applyUpwardsAliases(aliasedIdentifiers, source); return m_dynamicData->m_parentContext->findDeclarationsInternal(aliasedIdentifiers, url() == m_dynamicData->m_parentContext->url() ? position : m_dynamicData->m_parentContext->range().end, dataType, ret, source, flags, depth); } return true; } QList< QualifiedIdentifier > DUContext::fullyApplyAliases(const QualifiedIdentifier& id, const TopDUContext* source) const { ENSURE_CAN_READ if(!source) source = topContext(); SearchItem::PtrList identifiers; identifiers << SearchItem::Ptr(new SearchItem(id)); const DUContext* current = this; while(current) { SearchItem::PtrList aliasedIdentifiers; current->applyAliases(identifiers, aliasedIdentifiers, CursorInRevision::invalid(), true, false); current->applyUpwardsAliases(identifiers, source); current = current->parentContext(); } QList ret; foreach (const SearchItem::Ptr& item, identifiers) ret += item->toList(); return ret; } QList DUContext::findDeclarations( const QualifiedIdentifier & identifier, const CursorInRevision & position, const AbstractType::Ptr& dataType, const TopDUContext* topContext, SearchFlags flags) const { ENSURE_CAN_READ DeclarationList ret; SearchItem::PtrList identifiers; // optimize: we don't want to allocate the top node always // so create it on stack but ref it so its not deleted by the smart pointer SearchItem item(identifier); item.ref.ref(); identifiers << SearchItem::Ptr(&item); findDeclarationsInternal(identifiers, position.isValid() ? position : range().end, dataType, ret, topContext ? topContext : this->topContext(), flags, 0); return ret; } bool DUContext::imports(const DUContext* origin, const CursorInRevision& /*position*/ ) const { ENSURE_CAN_READ QSet recursionGuard; recursionGuard.reserve(8); return m_dynamicData->imports(origin, topContext(), &recursionGuard); } bool DUContext::addIndirectImport(const DUContext::Import& import) { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a) { if(d->m_importedContexts()[a] == import) { d->m_importedContextsList()[a].position = import.position; return true; } } ///Do not sort the imported contexts by their own line-number, it makes no sense. ///Contexts added first, aka template-contexts, should stay in first place, so they are searched first. d->m_importedContextsList().append(import); return false; } void DUContext::addImportedParentContext( DUContext * context, const CursorInRevision& position, bool anonymous, bool /*temporary*/ ) { ENSURE_CAN_WRITE if(context == this) { qCDebug(LANGUAGE) << "Tried to import self"; return; } if(!context) { qCDebug(LANGUAGE) << "Tried to import invalid context"; return; } Import import(context, this, position); if(addIndirectImport(import)) return; if( !anonymous ) { ENSURE_CAN_WRITE_(context) context->m_dynamicData->addImportedChildContext(this); } } void DUContext::removeImportedParentContext( DUContext * context ) { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); Import import(context, this, CursorInRevision::invalid()); for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a) { if(d->m_importedContexts()[a] == import) { d->m_importedContextsList().remove(a); break; } } if( !context ) return; context->m_dynamicData->removeImportedChildContext(this); } KDevVarLengthArray DUContext::indexedImporters() const { KDevVarLengthArray ret; if(owner()) ret = Importers::self().importers(owner()->id()); //Add indirect importers to the list FOREACH_FUNCTION(const IndexedDUContext& ctx, d_func()->m_importers) ret.append(ctx); return ret; } QVector DUContext::importers() const { ENSURE_CAN_READ QVector ret; FOREACH_FUNCTION(const IndexedDUContext& ctx, d_func()->m_importers) ret << ctx.context(); if(owner()) { //Add indirect importers to the list KDevVarLengthArray indirect = Importers::self().importers(owner()->id()); foreach (const IndexedDUContext ctx, indirect) { ret << ctx.context(); } } return ret; } DUContext * DUContext::findContext( const CursorInRevision& position, DUContext* parent) const { ENSURE_CAN_READ if (!parent) parent = const_cast(this); foreach (DUContext* context, parent->m_dynamicData->m_childContexts) { if (context->range().contains(position)) { DUContext* ret = findContext(position, context); if (!ret) { ret = context; } return ret; } } return 0; } bool DUContext::parentContextOf(DUContext* context) const { if (this == context) return true; foreach (DUContext* child, m_dynamicData->m_childContexts) { if (child->parentContextOf(context)) { return true; } } return false; } QList< QPair > DUContext::allDeclarations(const CursorInRevision& position, const TopDUContext* topContext, bool searchInParents) const { ENSURE_CAN_READ QList< QPair > ret; QHash hadContexts; // Iterate back up the chain mergeDeclarationsInternal(ret, position, hadContexts, topContext ? topContext : this->topContext(), searchInParents); return ret; } QVector DUContext::localDeclarations(const TopDUContext* source) const { ENSURE_CAN_READ // TODO: remove this parameter once we kill old-cpp Q_UNUSED(source); return m_dynamicData->m_localDeclarations; } void DUContext::mergeDeclarationsInternal(QList< QPair >& definitions, const CursorInRevision& position, QHash& hadContexts, const TopDUContext* source, bool searchInParents, int currentDepth) const { ENSURE_CAN_READ if((currentDepth > 300 && currentDepth < 1000) || currentDepth > 1300) { qCDebug(LANGUAGE) << "too much depth"; return; } DUCHAIN_D(DUContext); if(hadContexts.contains(this) && !searchInParents) return; if(!hadContexts.contains(this)) { hadContexts[this] = true; if( (type() == DUContext::Namespace || type() == DUContext::Global) && currentDepth < 1000 ) currentDepth += 1000; { DUContextDynamicData::VisibleDeclarationIterator it(m_dynamicData); while(it) { Declaration* decl = *it; if ( decl && (!position.isValid() || decl->range().start <= position) ) definitions << qMakePair(decl, currentDepth); ++it; } } for(int a = d->m_importedContextsSize()-1; a >= 0; --a) { const Import* import(&d->m_importedContexts()[a]); DUContext* context = import->context(source); while( !context && a > 0 ) { --a; import = &d->m_importedContexts()[a]; context = import->context(source); } if( !context ) break; if(context == this) { qCDebug(LANGUAGE) << "resolved self as import:" << scopeIdentifier(true); continue; } if( position.isValid() && import->position.isValid() && position < import->position ) continue; context->mergeDeclarationsInternal(definitions, CursorInRevision::invalid(), hadContexts, source, searchInParents && context->shouldSearchInParent(InImportedParentContext) && context->parentContext()->type() == DUContext::Helper, currentDepth+1); } } ///Only respect the position if the parent-context is not a class(@todo this is language-dependent) if (parentContext() && searchInParents ) parentContext()->mergeDeclarationsInternal(definitions, parentContext()->type() == DUContext::Class ? parentContext()->range().end : position, hadContexts, source, searchInParents, currentDepth+1); } void DUContext::deleteLocalDeclarations() { ENSURE_CAN_WRITE // It may happen that the deletion of one declaration triggers the deletion of another one // Therefore we copy the list of indexed declarations and work on those. Indexed declarations // will return zero for already deleted declarations. KDevVarLengthArray indexedLocal; if (d_func()->m_localDeclarations()) { indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize()); } foreach (const LocalIndexedDeclaration& indexed, m_dynamicData->m_localDeclarations) { delete indexed.data(topContext()); } m_dynamicData->m_localDeclarations.clear(); } void DUContext::deleteChildContextsRecursively() { ENSURE_CAN_WRITE // note: don't use qDeleteAll here because child ctx deletion changes m_dynamicData->m_childContexts // also note: foreach iterates on a copy, so this is safe foreach (DUContext* ctx, m_dynamicData->m_childContexts) { delete ctx; } m_dynamicData->m_childContexts.clear(); } QVector DUContext::clearLocalDeclarations( ) { auto copy = m_dynamicData->m_localDeclarations; foreach (Declaration* dec, copy) { dec->setContext(0); } return copy; } QualifiedIdentifier DUContext::scopeIdentifier(bool includeClasses) const { ENSURE_CAN_READ QualifiedIdentifier ret; m_dynamicData->scopeIdentifier(includeClasses, ret); return ret; } bool DUContext::equalScopeIdentifier(const DUContext* rhs) const { ENSURE_CAN_READ const DUContext* left = this; const DUContext* right = rhs; while(left || right) { if(!left || !right) return false; if(!(left->d_func()->m_scopeIdentifier == right->d_func()->m_scopeIdentifier)) return false; left = left->parentContext(); right = right->parentContext(); } return true; } void DUContext::setLocalScopeIdentifier(const QualifiedIdentifier & identifier) { ENSURE_CAN_WRITE bool wasInSymbolTable = inSymbolTable(); setInSymbolTable(false); d_func_dynamic()->m_scopeIdentifier = identifier; setInSymbolTable(wasInSymbolTable); } QualifiedIdentifier DUContext::localScopeIdentifier() const { //ENSURE_CAN_READ Commented out for performance reasons return d_func()->m_scopeIdentifier; } IndexedQualifiedIdentifier DUContext::indexedLocalScopeIdentifier() const { return d_func()->m_scopeIdentifier; } DUContext::ContextType DUContext::type() const { //ENSURE_CAN_READ This is disabled, because type() is called very often while searching, and it costs us performance return d_func()->m_contextType; } void DUContext::setType(ContextType type) { ENSURE_CAN_WRITE d_func_dynamic()->m_contextType = type; } QList DUContext::findDeclarations(const Identifier& identifier, const CursorInRevision& position, const TopDUContext* topContext, SearchFlags flags) const { return findDeclarations(IndexedIdentifier(identifier), position, topContext, flags); } QList DUContext::findDeclarations(const IndexedIdentifier& identifier, const CursorInRevision& position, const TopDUContext* topContext, SearchFlags flags) const { ENSURE_CAN_READ DeclarationList ret; SearchItem::PtrList identifiers; identifiers << SearchItem::Ptr(new SearchItem(false, identifier, SearchItem::PtrList())); findDeclarationsInternal(identifiers, position.isValid() ? position : range().end, AbstractType::Ptr(), ret, topContext ? topContext : this->topContext(), flags, 0); return ret; } void DUContext::deleteUse(int index) { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); d->m_usesList().remove(index); } void DUContext::deleteUses() { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); d->m_usesList().clear(); } void DUContext::deleteUsesRecursively() { deleteUses(); foreach (DUContext* childContext, m_dynamicData->m_childContexts) { childContext->deleteUsesRecursively(); } } bool DUContext::inDUChain() const { if( d_func()->m_anonymousInParent || !m_dynamicData->m_parentContext) return false; TopDUContext* top = topContext(); return top && top->inDUChain(); } DUContext* DUContext::specialize(const IndexedInstantiationInformation& /*specialization*/, const TopDUContext* topContext, int /*upDistance*/) { if(!topContext) return 0; return this; } CursorInRevision DUContext::importPosition(const DUContext* target) const { ENSURE_CAN_READ DUCHAIN_D(DUContext); Import import(const_cast(target), this, CursorInRevision::invalid()); for(unsigned int a = 0; a < d->m_importedContextsSize(); ++a) if(d->m_importedContexts()[a] == import) return d->m_importedContexts()[a].position; - return CursorInRevision::invalid(); + return CursorInRevision::invalid(); } QVector DUContext::importedParentContexts() const { ENSURE_CAN_READ QVector ret; ret.reserve(d_func()->m_importedContextsSize()); FOREACH_FUNCTION(const DUContext::Import& import, d_func()->m_importedContexts) ret << import; return ret; } void DUContext::applyAliases(const SearchItem::PtrList& baseIdentifiers, SearchItem::PtrList& identifiers, const CursorInRevision& position, bool canBeNamespace, bool onlyImports) const { DeclarationList imports; findLocalDeclarationsInternal(globalIndexedImportIdentifier(), position, AbstractType::Ptr(), imports, topContext(), DUContext::NoFiltering); if(imports.isEmpty() && onlyImports) { identifiers = baseIdentifiers; return; } for ( const SearchItem::Ptr& identifier : baseIdentifiers ) { bool addUnmodified = true; if( !identifier->isExplicitlyGlobal ) { if( !imports.isEmpty() ) { //We have namespace-imports. foreach ( Declaration* importDecl, imports ) { //Search for the identifier with the import-identifier prepended if(dynamic_cast(importDecl)) { NamespaceAliasDeclaration* alias = static_cast(importDecl); identifiers.append( SearchItem::Ptr( new SearchItem( alias->importIdentifier(), identifier ) ) ) ; }else{ qCDebug(LANGUAGE) << "Declaration with namespace alias identifier has the wrong type" << importDecl->url().str() << importDecl->range().castToSimpleRange(); } } } if( !identifier->isEmpty() && (identifier->hasNext() || canBeNamespace) ) { DeclarationList aliases; findLocalDeclarationsInternal(identifier->identifier, position, AbstractType::Ptr(), imports, 0, DUContext::NoFiltering); if(!aliases.isEmpty()) { //The first part of the identifier has been found as a namespace-alias. //In c++, we only need the first alias. However, just to be correct, follow them all for now. foreach ( Declaration* aliasDecl, aliases ) { if(!dynamic_cast(aliasDecl)) continue; addUnmodified = false; //The un-modified identifier can be ignored, because it will be replaced with the resolved alias NamespaceAliasDeclaration* alias = static_cast(aliasDecl); //Create an identifier where namespace-alias part is replaced with the alias target identifiers.append( SearchItem::Ptr( new SearchItem( alias->importIdentifier(), identifier->next ) ) ) ; } } } } if( addUnmodified ) identifiers.append(identifier); } } void DUContext::applyUpwardsAliases(SearchItem::PtrList& identifiers, const TopDUContext* /*source*/) const { if(type() == Namespace) { if(d_func()->m_scopeIdentifier.isEmpty()) return; //Make sure we search for the items in all namespaces of the same name, by duplicating each one with the namespace-identifier prepended. //We do this by prepending items to the current identifiers that equal the local scope identifier. SearchItem::Ptr newItem( new SearchItem(d_func()->m_scopeIdentifier.identifier()) ); //This will exclude explictly global identifiers newItem->addToEachNode( identifiers ); if(!newItem->next.isEmpty()) { //Prepend the full scope before newItem DUContext* parent = m_dynamicData->m_parentContext.data(); while(parent) { newItem = SearchItem::Ptr( new SearchItem(parent->d_func()->m_scopeIdentifier, newItem) ); parent = parent->m_dynamicData->m_parentContext.data(); } newItem->isExplicitlyGlobal = true; identifiers.insert(0, newItem); } } } bool DUContext::shouldSearchInParent(SearchFlags flags) const { return (parentContext() && parentContext()->type() == DUContext::Helper && (flags & InImportedParentContext)) || !(flags & InImportedParentContext); } const Use* DUContext::uses() const { ENSURE_CAN_READ return d_func()->m_uses(); } bool DUContext::declarationHasUses(Declaration* decl) { return DUChain::uses()->hasUses(decl->id()); } int DUContext::usesCount() const { return d_func()->m_usesSize(); } bool usesRangeLessThan(const Use& left, const Use& right) { return left.m_range.start < right.m_range.start; } int DUContext::createUse(int declarationIndex, const RangeInRevision& range, int insertBefore) { DUCHAIN_D_DYNAMIC(DUContext); ENSURE_CAN_WRITE Use use(range, declarationIndex); if(insertBefore == -1) { //Find position where to insert const unsigned int size = d->m_usesSize(); const Use* uses = d->m_uses(); const Use* lowerBound = std::lower_bound(uses, uses + size, use, usesRangeLessThan); insertBefore = lowerBound - uses; // comment out to test this: /* unsigned int a = 0; for(; a < size && range.start > uses[a].m_range.start; ++a) { } Q_ASSERT(a == insertBefore); */ } d->m_usesList().insert(insertBefore, use); return insertBefore; } void DUContext::changeUseRange(int useIndex, const RangeInRevision& range) { ENSURE_CAN_WRITE d_func_dynamic()->m_usesList()[useIndex].m_range = range; } void DUContext::setUseDeclaration(int useNumber, int declarationIndex) { ENSURE_CAN_WRITE d_func_dynamic()->m_usesList()[useNumber].m_declarationIndex = declarationIndex; } DUContext * DUContext::findContextAt(const CursorInRevision & position, bool includeRightBorder) const { ENSURE_CAN_READ // qCDebug(LANGUAGE) << "searchign" << position << "in:" << scopeIdentifier(true).toString() << range() << includeRightBorder; if (!range().contains(position) && (!includeRightBorder || range().end != position)) { // qCDebug(LANGUAGE) << "mismatch"; return 0; } const auto childContexts = m_dynamicData->m_childContexts; for(int a = childContexts.size() - 1; a >= 0; --a) { if (DUContext* specific = childContexts[a]->findContextAt(position, includeRightBorder)) { return specific; } } return const_cast(this); } Declaration * DUContext::findDeclarationAt(const CursorInRevision & position) const { ENSURE_CAN_READ if (!range().contains(position)) return 0; foreach (Declaration* child, m_dynamicData->m_localDeclarations) { if (child->range().contains(position)) { return child; } } return 0; } DUContext* DUContext::findContextIncluding(const RangeInRevision& range) const { ENSURE_CAN_READ if (!this->range().contains(range)) return 0; foreach (DUContext* child, m_dynamicData->m_childContexts) { if (DUContext* specific = child->findContextIncluding(range)) { return specific; } } return const_cast(this); } int DUContext::findUseAt(const CursorInRevision & position) const { ENSURE_CAN_READ if (!range().contains(position)) return -1; for(unsigned int a = 0; a < d_func()->m_usesSize(); ++a) if (d_func()->m_uses()[a].m_range.contains(position)) return a; return -1; } bool DUContext::inSymbolTable() const { return d_func()->m_inSymbolTable; } void DUContext::setInSymbolTable(bool inSymbolTable) { d_func_dynamic()->m_inSymbolTable = inSymbolTable; } void DUContext::clearImportedParentContexts() { ENSURE_CAN_WRITE DUCHAIN_D_DYNAMIC(DUContext); while( d->m_importedContextsSize() != 0 ) { DUContext* ctx = d->m_importedContexts()[0].context(0, false); if(ctx) ctx->m_dynamicData->removeImportedChildContext(this); d->m_importedContextsList().removeOne(d->m_importedContexts()[0]); } } void DUContext::cleanIfNotEncountered(const QSet& encountered) { ENSURE_CAN_WRITE // It may happen that the deletion of one declaration triggers the deletion of another one // Therefore we copy the list of indexed declarations and work on those. Indexed declarations // will return zero for already deleted declarations. KDevVarLengthArray indexedLocal; if (d_func()->m_localDeclarations()) { indexedLocal.append(d_func()->m_localDeclarations(), d_func()->m_localDeclarationsSize()); } foreach (const LocalIndexedDeclaration& indexed, m_dynamicData->m_localDeclarations) { auto dec = indexed.data(topContext()); if (dec && !encountered.contains(dec) && (!dec->isAutoDeclaration() || !dec->hasUses())) { delete dec; } } foreach (DUContext* childContext, m_dynamicData->m_childContexts) { if (!encountered.contains(childContext)) { delete childContext; } } } TopDUContext* DUContext::topContext() const { return m_dynamicData->m_topContext; } QWidget* DUContext::createNavigationWidget(Declaration* decl, TopDUContext* topContext, const QString& htmlPrefix, const QString& htmlSuffix) const { if (decl) { AbstractNavigationWidget* widget = new AbstractNavigationWidget; AbstractDeclarationNavigationContext* context = new AbstractDeclarationNavigationContext(DeclarationPointer(decl), TopDUContextPointer(topContext)); context->setPrefixSuffix(htmlPrefix, htmlSuffix); widget->setContext(NavigationContextPointer(context)); return widget; } else { return 0; } } QList allUses(DUContext* context, int declarationIndex, bool noEmptyUses) { QList ret; for(int a = 0; a < context->usesCount(); ++a) if(context->uses()[a].m_declarationIndex == declarationIndex) if(!noEmptyUses || !context->uses()[a].m_range.isEmpty()) ret << context->uses()[a].m_range; foreach(DUContext* child, context->childContexts()) ret += allUses(child, declarationIndex, noEmptyUses); return ret; } DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const Ptr& nextItem, int start) : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false) { if(!id.isEmpty()) { if(id.count() > start) identifier = id.indexedAt(start); if(id.count() > start+1) addNext(Ptr( new SearchItem(id, nextItem, start+1) )); else if(nextItem) next.append(nextItem); }else if(nextItem) { ///If there is no prefix, just copy nextItem isExplicitlyGlobal = nextItem->isExplicitlyGlobal; identifier = nextItem->identifier; next = nextItem->next; } } DUContext::SearchItem::SearchItem(const QualifiedIdentifier& id, const PtrList& nextItems, int start) : isExplicitlyGlobal(start == 0 ? id.explicitlyGlobal() : false) { if(id.count() > start) identifier = id.indexedAt(start); if(id.count() > start+1) addNext(Ptr( new SearchItem(id, nextItems, start+1) )); else next = nextItems; } DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const PtrList& nextItems) : isExplicitlyGlobal(explicitlyGlobal) , identifier(id) , next(nextItems) { } DUContext::SearchItem::SearchItem(bool explicitlyGlobal, const IndexedIdentifier& id, const Ptr& nextItem) : isExplicitlyGlobal(explicitlyGlobal) , identifier(id) { next.append(nextItem); } bool DUContext::SearchItem::match(const QualifiedIdentifier& id, int offset) const { if(id.isEmpty()) { if(identifier.isEmpty() && next.isEmpty()) return true; else return false; } if(id.at(offset) != identifier) //The identifier is different return false; if(offset == id.count()-1) { if(next.isEmpty()) return true; //match else return false; //id is too short } for(int a = 0; a < next.size(); ++a) if(next[a]->match(id, offset+1)) return true; return false; } bool DUContext::SearchItem::isEmpty() const { return identifier.isEmpty(); } bool DUContext::SearchItem::hasNext() const { return !next.isEmpty(); } QList DUContext::SearchItem::toList(const QualifiedIdentifier& prefix) const { QList ret; QualifiedIdentifier id = prefix; if(id.isEmpty()) id.setExplicitlyGlobal(isExplicitlyGlobal); if(!identifier.isEmpty()) id.push(identifier); if(next.isEmpty()) { ret << id; } else { for(int a = 0; a < next.size(); ++a) ret += next[a]->toList(id); } return ret; } void DUContext::SearchItem::addNext(const SearchItem::Ptr& other) { next.append(other); } void DUContext::SearchItem::addToEachNode(const SearchItem::Ptr& other) { if(other->isExplicitlyGlobal) return; next.append(other); for(int a = 0; a < next.size()-1; ++a) next[a]->addToEachNode(other); } void DUContext::SearchItem::addToEachNode(const SearchItem::PtrList& other) { int added = 0; for (const SearchItem::Ptr& o : other) { if(!o->isExplicitlyGlobal) { next.append(o); ++added; } } for(int a = 0; a < next.size()-added; ++a) next[a]->addToEachNode(other); } DUContext::Import::Import(DUContext* _context, const DUContext* importer, const CursorInRevision& _position) : position(_position) { if(_context && _context->owner() && (_context->owner()->specialization().index() || (importer && importer->topContext() != _context->topContext()))) { m_declaration = _context->owner()->id(); }else{ m_context = _context; } } DUContext::Import::Import(const DeclarationId& id, const CursorInRevision& _position) : position(_position) { m_declaration = id; } DUContext* DUContext::Import::context(const TopDUContext* topContext, bool instantiateIfRequired) const { if(m_declaration.isValid()) { Declaration* decl = m_declaration.getDeclaration(topContext, instantiateIfRequired); //This first case rests on the assumption that no context will ever import a function's expression context //More accurately, that no specialized or cross-topContext imports will, but if the former assumption fails the latter will too if (AbstractFunctionDeclaration *functionDecl = dynamic_cast(decl)) { if (functionDecl->internalFunctionContext()) { return functionDecl->internalFunctionContext(); } else { qCWarning(LANGUAGE) << "Import of function declaration without internal function context encountered!"; } } if(decl) return decl->logicalInternalContext(topContext); else return 0; }else{ return m_context.data(); } } bool DUContext::Import::isDirect() const { return m_context.isValid(); } void DUContext::visit(DUChainVisitor& visitor) { ENSURE_CAN_READ visitor.visit(this); foreach (Declaration* decl, m_dynamicData->m_localDeclarations) { visitor.visit(decl); } foreach (DUContext* childContext, m_dynamicData->m_childContexts) { childContext->visit(visitor); } } static bool sortByRange(const DUChainBase* lhs, const DUChainBase* rhs) { return lhs->range() < rhs->range(); } void DUContext::resortLocalDeclarations() { ENSURE_CAN_WRITE std::sort(m_dynamicData->m_localDeclarations.begin(), m_dynamicData->m_localDeclarations.end(), sortByRange); auto top = topContext(); auto& declarations = d_func_dynamic()->m_localDeclarationsList(); std::sort(declarations.begin(), declarations.end(), [top] (const LocalIndexedDeclaration& lhs, const LocalIndexedDeclaration& rhs) { return lhs.data(top)->range() < rhs.data(top)->range(); }); } void DUContext::resortChildContexts() { ENSURE_CAN_WRITE std::sort(m_dynamicData->m_childContexts.begin(), m_dynamicData->m_childContexts.end(), sortByRange); auto top = topContext(); auto& contexts = d_func_dynamic()->m_childContextsList(); std::sort(contexts.begin(), contexts.end(), [top] (const LocalIndexedDUContext& lhs, const LocalIndexedDUContext& rhs) { return lhs.data(top)->range() < rhs.data(top)->range(); }); } } diff --git a/language/util/setrepository.cpp b/language/util/setrepository.cpp index dca8ddd1aa..c5ee81726c 100644 --- a/language/util/setrepository.cpp +++ b/language/util/setrepository.cpp @@ -1,1122 +1,1122 @@ /*************************************************************************** Copyright 2007 David Nolden ***************************************************************************/ /*************************************************************************** * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * ***************************************************************************/ #include "setrepository.h" #include "util/debug.h" #include #include #include #include #include #include #include #include #include //#define DEBUG #ifdef DEBUG #define ifDebug(X) X #else #define ifDebug(x) #undef Q_ASSERT #define Q_ASSERT(x) #endif #ifndef DEBUG #define CHECK_SPLIT_POSITION(Node) #else #define CHECK_SPLIT_POSITION(node) Q_ASSERT(!(node).leftNode || (getLeftNode(&node)->end() <= splitPositionForRange((node).start, (node).end) && getRightNode(&node)->start() >= splitPositionForRange((node).start, (node).end))) #endif namespace Utils { /** * To achieve a maximum re-usage of nodes, we make sure that sub-nodes of a node always split at specific boundaries. * For each range we can compute a position where that range should be split into its child-nodes. * When creating a new node with 2 sub-nodes, we re-create those child-nodes if their boundaries don't represent those split-positions. * * We pick the split-positions deterministically, they are in order of priority: * ((1<<31)*n, n = [0,...] * ((1<<30)*n, n = [0,...] * ((1<<29)*n, n = [0,...] * ((1<<...)*n, n = [0,...] * ... * */ typedef BasicSetRepository::Index Index; ///The returned split position shall be the end of the first sub-range, and the start of the second ///@param splitBit should be initialized with 31, unless you know better. The value can then be used on while computing child split positions. ///In the end, it will contain the bit used to split the range. It will also contain zero if no split-position exists(length 1) uint splitPositionForRange(uint start, uint end, uchar& splitBit) { if(end-start == 1) { splitBit = 0; return 0; } while(true) { uint position = ((end-1) >> splitBit) << splitBit; //Round to the split-position in this interval that is smaller than end if(position > start && position < end) return position; Q_ASSERT(splitBit != 0); --splitBit; } return 0; } uint splitPositionForRange(uint start, uint end) { uchar splitBit = 31; return splitPositionForRange(start, end, splitBit); } class SetNodeDataRequest; #define getLeftNode(node) repository.itemFromIndex(node->leftNode()) #define getRightNode(node) repository.itemFromIndex(node->rightNode()) #define nodeFromIndex(index) repository.itemFromIndex(index) struct SetRepositoryAlgorithms { SetRepositoryAlgorithms(SetDataRepository& _repository, BasicSetRepository* _setRepository) : repository(_repository), setRepository(_setRepository) { } ///Expensive Index count(const SetNodeData* node) const; void localCheck(const SetNodeData* node); void check(uint node); void check(const SetNodeData* node); QString shortLabel(const SetNodeData& node) const; uint set_union(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit = 31); uint createSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left = 0, const SetNodeData* right = 0); uint computeSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left, const SetNodeData* right, uchar splitBit); uint set_intersect(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit = 31); bool set_contains(const SetNodeData* node, Index index); uint set_subtract(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit = 31); //Required both nodes to be split correctly bool set_equals(const SetNodeData* lhs, const SetNodeData* rhs); QString dumpDotGraph(uint node) const; ///Finds or inserts the given ranges into the repository, and returns the set-index that represents them uint setForIndices(std::vector::const_iterator begin, std::vector::const_iterator end, uchar splitBit = 31) { Q_ASSERT(begin != end); uint startIndex = *begin; uint endIndex = *(end-1)+1; if(endIndex == startIndex+1) { SetNodeData data(startIndex, endIndex); return repository.index( SetNodeDataRequest(&data, repository, setRepository) ); } uint split = splitPositionForRange(startIndex, endIndex, splitBit); Q_ASSERT(split); std::vector::const_iterator splitIterator = std::lower_bound(begin, end, split); Q_ASSERT(*splitIterator >= split); Q_ASSERT(splitIterator > begin); Q_ASSERT(*(splitIterator-1) < split); return createSetFromNodes(setForIndices(begin, splitIterator, splitBit), setForIndices(splitIterator, end, splitBit)); } private: QString dumpDotGraphInternal(uint node, bool master=false) const; SetDataRepository& repository; BasicSetRepository* setRepository; }; void SetNodeDataRequest::destroy(SetNodeData* data, KDevelop::AbstractItemRepository& _repository) { SetDataRepository& repository(static_cast(_repository)); if(repository.setRepository->delayedDeletion()) { if(data->leftNode()){ SetDataRepositoryBase::MyDynamicItem left = repository.dynamicItemFromIndex(data->leftNode()); SetDataRepositoryBase::MyDynamicItem right = repository.dynamicItemFromIndex(data->rightNode()); Q_ASSERT(left->m_refCount > 0); --left->m_refCount; Q_ASSERT(right->m_refCount > 0); --right->m_refCount; }else { //Deleting a leaf Q_ASSERT(data->end() - data->start() == 1); repository.setRepository->itemRemovedFromSets(data->start()); } } } SetNodeDataRequest::SetNodeDataRequest(const SetNodeData* _data, SetDataRepository& _repository, BasicSetRepository* _setRepository) : data(*_data), m_hash(_data->hash()), repository(_repository), setRepository(_setRepository), m_created(false) { ifDebug( SetRepositoryAlgorithms alg(repository); alg.check(_data) ); } SetNodeDataRequest::~SetNodeDataRequest() { //Eventually increase the reference-count of direct children if(m_created) { if(data.leftNode()) ++repository.dynamicItemFromIndex(data.leftNode())->m_refCount; if(data.rightNode()) ++repository.dynamicItemFromIndex(data.rightNode())->m_refCount; } } //Should create an item where the information of the requested item is permanently stored. The pointer //@param item equals an allocated range with the size of itemSize(). void SetNodeDataRequest::createItem(SetNodeData* item) const { Q_ASSERT((data.rightNode() && data.leftNode()) || (!data.rightNode() && !data.leftNode())); m_created = true; *item = data; Q_ASSERT((item->rightNode() && item->leftNode()) || (!item->rightNode() && !item->leftNode())); #ifdef DEBUG //Make sure we split at the correct split position if(item->hasSlaves()) { uint split = splitPositionForRange(data.start, data.end); const SetNodeData* left = repository.itemFromIndex(item->leftNode()); const SetNodeData* right = repository.itemFromIndex(item->rightNode()); Q_ASSERT(split >= left->end() && split <= right->start()); } #endif if(!data.leftNode() && setRepository) { for(uint a = item->start(); a < item->end(); ++a) setRepository->itemAddedToSets(a); } } bool SetNodeDataRequest::equals(const SetNodeData* item) const { Q_ASSERT((item->rightNode() && item->leftNode()) || (!item->rightNode() && !item->leftNode())); //Just compare child nodes, since data must be correctly split, this is perfectly ok //Since this happens in very tight loops, we don't call an additional function here, but just do the check. return item->leftNode() == data.leftNode() && item->rightNode() == data.rightNode() && item->start() == data.start() && item->end() == data.end(); } class BasicSetRepository::Private { public: Private(QString _name) : name(_name) { } ~Private() { } QString name; private: }; Set::Set() : m_tree(0), m_repository(0) { } Set::~Set() { } unsigned int Set::count() const { if(!m_repository || !m_tree) return 0; QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); return alg.count(m_repository->dataRepository.itemFromIndex(m_tree)); } Set::Set(uint treeNode, BasicSetRepository* repository) : m_tree(treeNode), m_repository(repository) { } Set::Set(const Set& rhs) { m_repository = rhs.m_repository; m_tree = rhs.m_tree; } Set& Set::operator=(const Set& rhs) { m_repository = rhs.m_repository; m_tree = rhs.m_tree; return *this; } QString Set::dumpDotGraph() const { if(!m_repository || !m_tree) return QString(); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); return alg.dumpDotGraph(m_tree); } Index SetRepositoryAlgorithms::count(const SetNodeData* node) const { if(node->leftNode() && node->rightNode()) return count(getLeftNode(node)) + count(getRightNode(node)); else return node->end() - node->start(); } void SetRepositoryAlgorithms::localCheck(const SetNodeData* ifDebug(node) ) { // Q_ASSERT(node->start() > 0); Q_ASSERT(node->start() < node->end()); Q_ASSERT((node->leftNode() && node->rightNode()) || (!node->leftNode() && !node->rightNode())); Q_ASSERT(!node->leftNode() || (getLeftNode(node())->start() == node->start() && getRightNode(node)->end() == node->end())); Q_ASSERT(!node->leftNode() || (getLeftNode(node())->end() <= getRightNode(node)->start())); } void SetRepositoryAlgorithms::check(uint node) { if(!node) return; check(nodeFromIndex(node)); } void SetRepositoryAlgorithms::check(const SetNodeData* node) { localCheck(node); if(node->leftNode()) check(getLeftNode(node)); if(node->rightNode()) check(getRightNode(node)); // CHECK_SPLIT_POSITION(*node); Re-enable this } QString SetRepositoryAlgorithms::shortLabel(const SetNodeData& node) const { return QStringLiteral("n%1_%2").arg(node.start()).arg(node.end()); } QString SetRepositoryAlgorithms::dumpDotGraphInternal(uint nodeIndex, bool master) const { if(!nodeIndex) return QStringLiteral("empty node"); const SetNodeData& node(*repository.itemFromIndex(nodeIndex)); QString color = QStringLiteral("blue"); if(master) color = QStringLiteral("red"); QString label = QStringLiteral("%1 -> %2").arg(node.start()).arg(node.end()); if(!node.contiguous()) label += QLatin1String(", with gaps"); QString ret = QStringLiteral("%1[label=\"%2\", color=\"%3\"];\n").arg(shortLabel(node), label, color); if(node.leftNode()) { const SetNodeData& left(*repository.itemFromIndex(node.leftNode())); const SetNodeData& right(*repository.itemFromIndex(node.rightNode())); Q_ASSERT(node.rightNode()); ret += QStringLiteral("%1 -> %2;\n").arg(shortLabel(node), shortLabel(left)); ret += QStringLiteral("%1 -> %2;\n").arg(shortLabel(node), shortLabel(right)); ret += dumpDotGraphInternal(node.leftNode()); ret += dumpDotGraphInternal(node.rightNode()); } return ret; } QString SetRepositoryAlgorithms::dumpDotGraph(uint nodeIndex) const { QString ret = QStringLiteral("digraph Repository {\n"); ret += dumpDotGraphInternal(nodeIndex, true); ret += QLatin1String("}\n"); return ret; } const int nodeStackAlloc = 500; class Set::Iterator::IteratorPrivate { public: IteratorPrivate() : nodeStackSize(0), currentIndex(0), repository(0) { nodeStackData.resize(nodeStackAlloc); nodeStack = nodeStackData.data(); } IteratorPrivate(const IteratorPrivate& rhs) : nodeStackData(rhs.nodeStackData), nodeStackSize(rhs.nodeStackSize), currentIndex(rhs.currentIndex), repository(rhs.repository) { nodeStack = nodeStackData.data(); } void resizeNodeStack() { nodeStackData.resize(nodeStackSize + 1); nodeStack = nodeStackData.data(); } KDevVarLengthArray nodeStackData; const SetNodeData** nodeStack; int nodeStackSize; Index currentIndex; BasicSetRepository* repository; /** * Pushes the noed on top of the stack, changes currentIndex, and goes as deep as necessary for iteration. * */ void startAtNode(const SetNodeData* node) { Q_ASSERT(node->start() != node->end()); currentIndex = node->start(); do { nodeStack[nodeStackSize++] = node; if(nodeStackSize >= nodeStackAlloc) resizeNodeStack(); if(node->contiguous()) break; //We need no finer granularity, because the range is contiguous node = Set::Iterator::getDataRepository(repository).itemFromIndex(node->leftNode()); } while(node); Q_ASSERT(currentIndex >= nodeStack[0]->start()); } }; std::set Set::stdSet() const { Set::Iterator it = iterator(); std::set ret; while(it) { Q_ASSERT(ret.find(*it) == ret.end()); ret.insert(*it); ++it; } return ret; } Set::Iterator::Iterator(const Iterator& rhs) : d(new IteratorPrivate(*rhs.d)) { } Set::Iterator& Set::Iterator::operator=(const Iterator& rhs) { delete d; d = new IteratorPrivate(*rhs.d); return *this; } Set::Iterator::Iterator() : d(new IteratorPrivate) { } Set::Iterator::~Iterator() { delete d; } Set::Iterator::operator bool() const { return d->nodeStackSize; } Set::Iterator& Set::Iterator::operator++() { Q_ASSERT(d->nodeStackSize); if(d->repository->m_mutex) d->repository->m_mutex->lock(); ++d->currentIndex; //const SetNodeData** currentNode = &d->nodeStack[d->nodeStackSize - 1]; if(d->currentIndex >= d->nodeStack[d->nodeStackSize - 1]->end()) { //Advance to the next node while(d->nodeStackSize && d->currentIndex >= d->nodeStack[d->nodeStackSize - 1]->end()) { --d->nodeStackSize; } if(!d->nodeStackSize) { //ready }else{ //++d->nodeStackSize; //We were iterating the left slave of the node, now continue with the right. ifDebug( const SetNodeData& left = *d->repository->dataRepository.itemFromIndex(d->nodeStack[d->nodeStackSize - 1]->leftNode()); Q_ASSERT(left.end == d->currentIndex); ) const SetNodeData& right = *d->repository->dataRepository.itemFromIndex(d->nodeStack[d->nodeStackSize - 1]->rightNode()); d->startAtNode(&right); } } Q_ASSERT(d->nodeStackSize == 0 || d->currentIndex < d->nodeStack[0]->end()); if(d->repository->m_mutex) d->repository->m_mutex->unlock(); return *this; } BasicSetRepository::Index Set::Iterator::operator*() const { return d->currentIndex; } Set::Iterator Set::iterator() const { if(!m_tree || !m_repository) return Iterator(); QMutexLocker lock(m_repository->m_mutex); Iterator ret; ret.d->repository = m_repository; if(m_tree) ret.d->startAtNode(m_repository->dataRepository.itemFromIndex(m_tree)); return ret; } //Creates a set item with the given children., they must be valid, and they must be split around their split-position. uint SetRepositoryAlgorithms::createSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left, const SetNodeData* right) { if(!left) left = nodeFromIndex(leftNode); if(!right) right = nodeFromIndex(rightNode); Q_ASSERT(left->end() <= right->start()); SetNodeData set(left->start(), right->end(), leftNode, rightNode); Q_ASSERT(set.start() < set.end()); uint ret = repository.index(SetNodeDataRequest(&set, repository, setRepository)); Q_ASSERT(set.leftNode() >= 0x10000); Q_ASSERT(set.rightNode() >= 0x10000); Q_ASSERT(ret == repository.findIndex(SetNodeDataRequest(&set, repository, setRepository))); ifDebug( check(ret) ); return ret; } //Constructs a set node from the given two sub-nodes. Those must be valid, they must not intersect, and they must have a correct split-hierarchy. //The do not need to be split around their computed split-position. uint SetRepositoryAlgorithms::computeSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left, const SetNodeData* right, uchar splitBit) { Q_ASSERT(left->end() <= right->start()); uint splitPosition = splitPositionForRange(left->start(), right->end(), splitBit); Q_ASSERT(splitPosition); if(splitPosition < left->end()) { //The split-position intersects the left node uint leftLeftNode = left->leftNode(); uint leftRightNode = left->rightNode(); const SetNodeData* leftLeft = this->getLeftNode(left); const SetNodeData* leftRight = this->getRightNode(left); Q_ASSERT(splitPosition >= leftLeft->end() && splitPosition <= leftRight->start()); //Create a new set from leftLeft, and from leftRight + right. That set will have the correct split-position. uint newRightNode = computeSetFromNodes(leftRightNode, rightNode, leftRight, right, splitBit); return createSetFromNodes(leftLeftNode, newRightNode, leftLeft); }else if(splitPosition > right->start()) { //The split-position intersects the right node uint rightLeftNode = right->leftNode(); uint rightRightNode = right->rightNode(); const SetNodeData* rightLeft = this->getLeftNode(right); const SetNodeData* rightRight = this->getRightNode(right); Q_ASSERT(splitPosition >= rightLeft->end() && splitPosition <= rightRight->start()); //Create a new set from left + rightLeft, and from rightRight. That set will have the correct split-position. uint newLeftNode = computeSetFromNodes(leftNode, rightLeftNode, left, rightLeft, splitBit); return createSetFromNodes(newLeftNode, rightRightNode, 0, rightRight); }else{ return createSetFromNodes(leftNode, rightNode, left, right); } } uint SetRepositoryAlgorithms::set_union(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit) { if(firstNode == secondNode) return firstNode; uint firstStart = first->start(), secondEnd = second->end(); if(firstStart >= secondEnd) return computeSetFromNodes(secondNode, firstNode, second, first, splitBit); uint firstEnd = first->end(), secondStart = second->start(); if(secondStart >= firstEnd) return computeSetFromNodes(firstNode, secondNode, first, second, splitBit); //The ranges of first and second do intersect uint newStart = firstStart < secondStart ? firstStart : secondStart; uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd; //Compute the split-position for the resulting merged node uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit); //Since the ranges overlap, we can be sure that either first or second contain splitPosition. //The node that contains it, will also be split by it. if(splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart && splitPosition < secondEnd) { //The split-position intersect with both first and second. Continue the union on both sides of the split-position, and merge it. uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); return createSetFromNodes( set_union(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit), set_union(firstRightNode, secondRightNode, firstRight, secondRight, splitBit) ); }else if(splitPosition > firstStart && splitPosition < firstEnd) { uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); //splitPosition does not intersect second. That means that second is completely on one side of it. //So we only need to union that side of first with second. if(secondEnd <= splitPosition) { return createSetFromNodes( set_union(firstLeftNode, secondNode, firstLeft, second, splitBit), firstRightNode, 0, firstRight ); }else{ Q_ASSERT(secondStart >= splitPosition); return createSetFromNodes( firstLeftNode, set_union(firstRightNode, secondNode, firstRight, second, splitBit), firstLeft ); } }else if(splitPosition > secondStart && splitPosition < secondEnd) { uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); if(firstEnd <= splitPosition) { return createSetFromNodes( set_union(secondLeftNode, firstNode, secondLeft, first, splitBit), secondRightNode, 0, secondRight ); }else{ Q_ASSERT(firstStart >= splitPosition); return createSetFromNodes( secondLeftNode, set_union(secondRightNode, firstNode, secondRight, first, splitBit), secondLeft ); } }else{ //We would have stopped earlier of first and second don't intersect ifDebug( uint test = repository.findIndex(SetNodeDataRequest(first, repository, setRepository)); qCDebug(LANGUAGE) << "found index:" << test; ) Q_ASSERT(0); return 0; } } bool SetRepositoryAlgorithms::set_equals(const SetNodeData* lhs, const SetNodeData* rhs) { if(lhs->leftNode() != rhs->leftNode() || lhs->rightNode() != rhs->rightNode()) return false; else return true; } uint SetRepositoryAlgorithms::set_intersect(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit) { if(firstNode == secondNode) return firstNode; if(first->start() >= second->end()) return 0; if(second->start() >= first->end()) return 0; //The ranges of first and second do intersect uint firstStart = first->start(), firstEnd = first->end(), secondStart = second->start(), secondEnd = second->end(); uint newStart = firstStart < secondStart ? firstStart : secondStart; uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd; //Compute the split-position for the resulting merged node uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit); //Since the ranges overlap, we can be sure that either first or second contain splitPosition. //The node that contains it, will also be split by it. if(splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart && splitPosition < secondEnd) { //The split-position intersect with both first and second. Continue the intersection on both sides uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); uint newLeftNode = set_intersect(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit); uint newRightNode = set_intersect(firstRightNode, secondRightNode, firstRight, secondRight, splitBit); if(newLeftNode && newRightNode) return createSetFromNodes( newLeftNode, newRightNode ); else if(newLeftNode) return newLeftNode; else return newRightNode; }else if(splitPosition > firstStart && splitPosition < firstEnd) { uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); //splitPosition does not intersect second. That means that second is completely on one side of it. //So we can completely ignore the other side of first. if(secondEnd <= splitPosition) { return set_intersect(firstLeftNode, secondNode, firstLeft, second, splitBit); }else{ Q_ASSERT(secondStart >= splitPosition); return set_intersect(firstRightNode, secondNode, firstRight, second, splitBit); } }else if(splitPosition > secondStart && splitPosition < secondEnd) { uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); if(firstEnd <= splitPosition) { return set_intersect(secondLeftNode, firstNode, secondLeft, first, splitBit); }else{ Q_ASSERT(firstStart >= splitPosition); return set_intersect(secondRightNode, firstNode, secondRight, first, splitBit); } }else{ //We would have stopped earlier of first and second don't intersect Q_ASSERT(0); return 0; } Q_ASSERT(0); } bool SetRepositoryAlgorithms::set_contains(const SetNodeData* node, Index index) { while(true) { if(node->start() > index || node->end() <= index) return false; if(node->contiguous()) return true; const SetNodeData* leftNode = nodeFromIndex(node->leftNode()); if(index < leftNode->end()) node = leftNode; else { const SetNodeData* rightNode = nodeFromIndex(node->rightNode()); node = rightNode; } } return false; } uint SetRepositoryAlgorithms::set_subtract(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second, uchar splitBit) { if(firstNode == secondNode) return 0; if(first->start() >= second->end() || second->start() >= first->end()) return firstNode; //The ranges of first and second do intersect uint firstStart = first->start(), firstEnd = first->end(), secondStart = second->start(), secondEnd = second->end(); uint newStart = firstStart < secondStart ? firstStart : secondStart; uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd; //Compute the split-position for the resulting merged node uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit); //Since the ranges overlap, we can be sure that either first or second contain splitPosition. //The node that contains it, will also be split by it. if(splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart && splitPosition < secondEnd) { //The split-position intersect with both first and second. Continue the subtract on both sides of the split-position, and merge it. uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); uint newLeftNode = set_subtract(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit); uint newRightNode = set_subtract(firstRightNode, secondRightNode, firstRight, secondRight, splitBit); if(newLeftNode && newRightNode) return createSetFromNodes(newLeftNode, newRightNode); else if(newLeftNode) return newLeftNode; else return newRightNode; }else if(splitPosition > firstStart && splitPosition < firstEnd) { // Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start()); uint firstLeftNode = first->leftNode(); uint firstRightNode = first->rightNode(); const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode); const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode); //splitPosition does not intersect second. That means that second is completely on one side of it. //So we only need to subtract that side of first with second. uint newLeftNode = firstLeftNode, newRightNode = firstRightNode; if(secondEnd <= splitPosition) { newLeftNode = set_subtract(firstLeftNode, secondNode, firstLeft, second, splitBit); }else{ Q_ASSERT(secondStart >= splitPosition); newRightNode = set_subtract(firstRightNode, secondNode, firstRight, second, splitBit); } if(newLeftNode && newRightNode) return createSetFromNodes(newLeftNode, newRightNode); else if(newLeftNode) return newLeftNode; else return newRightNode; }else if(splitPosition > secondStart && splitPosition < secondEnd) { uint secondLeftNode = second->leftNode(); uint secondRightNode = second->rightNode(); const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode); const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode); Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start()); if(firstEnd <= splitPosition) { return set_subtract(firstNode, secondLeftNode, first, secondLeft, splitBit); }else{ Q_ASSERT(firstStart >= splitPosition); return set_subtract(firstNode, secondRightNode, first, secondRight, splitBit); } }else{ //We would have stopped earlier of first and second don't intersect Q_ASSERT(0); return 0; } Q_ASSERT(0); } Set BasicSetRepository::createSetFromIndices(const std::vector& indices) { QMutexLocker lock(m_mutex); if(indices.empty()) return Set(); SetRepositoryAlgorithms alg(dataRepository, this); return Set(alg.setForIndices(indices.begin(), indices.end()), this); } Set BasicSetRepository::createSet(Index i) { QMutexLocker lock(m_mutex); SetNodeData data(i, i+1); return Set(dataRepository.index( SetNodeDataRequest(&data, dataRepository, this) ), this); } Set BasicSetRepository::createSet(const std::set& indices) { if(indices.empty()) return Set(); QMutexLocker lock(m_mutex); std::vector indicesVector; indicesVector.reserve(indices.size()); for( std::set::const_iterator it = indices.begin(); it != indices.end(); ++it ) indicesVector.push_back(*it); return createSetFromIndices(indicesVector); } BasicSetRepository::BasicSetRepository(QString name, KDevelop::ItemRepositoryRegistry* registry, bool delayedDeletion) : d(new Private(name)), dataRepository(this, name, registry), m_mutex(0), m_delayedDeletion(delayedDeletion) { m_mutex = dataRepository.mutex(); } struct StatisticsVisitor { StatisticsVisitor(const SetDataRepository& _rep) : nodeCount(0), badSplitNodeCount(0), zeroRefCountNodes(0), rep(_rep) { } bool operator() (const SetNodeData* item) { if(item->m_refCount == 0) ++zeroRefCountNodes; ++nodeCount; uint split = splitPositionForRange(item->start(), item->end()); if(item->hasSlaves()) if(split < rep.itemFromIndex(item->leftNode())->end() || split > rep.itemFromIndex(item->rightNode())->start()) ++badSplitNodeCount; return true; } uint nodeCount; uint badSplitNodeCount; uint zeroRefCountNodes; const SetDataRepository& rep; }; void BasicSetRepository::printStatistics() const { StatisticsVisitor stats(dataRepository); dataRepository.visitAllItems(stats); qCDebug(LANGUAGE) << "count of nodes:" << stats.nodeCount << "count of nodes with bad split:" << stats.badSplitNodeCount << "count of nodes with zero reference-count:" << stats.zeroRefCountNodes; } BasicSetRepository::~BasicSetRepository() { delete d; } void BasicSetRepository::itemRemovedFromSets(uint /*index*/) { } void BasicSetRepository::itemAddedToSets(uint /*index*/) { } ////////////Set convenience functions////////////////// bool Set::contains(Index index) const { if(!m_tree || !m_repository) return false; QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); return alg.set_contains(m_repository->dataRepository.itemFromIndex(m_tree), index); } Set Set::operator +(const Set& first) const { if(!first.m_tree) return *this; else if(!m_tree || !m_repository) return first; Q_ASSERT(m_repository == first.m_repository); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); uint retNode = alg.set_union(m_tree, first.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(first.m_tree)); ifDebug(alg.check(retNode)); return Set(retNode, m_repository); } Set& Set::operator +=(const Set& first) { if(!first.m_tree) return *this; else if(!m_tree || !m_repository) { m_tree = first.m_tree; m_repository = first.m_repository; return *this; } QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); m_tree = alg.set_union(m_tree, first.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(first.m_tree)); ifDebug(alg.check(m_tree)); return *this; } Set Set::operator &(const Set& first) const { if(!first.m_tree || !m_tree) return Set(); Q_ASSERT(m_repository); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); Set ret( alg.set_intersect(m_tree, first.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(first.m_tree)), m_repository ); ifDebug(alg.check(ret.m_tree)); return ret; } Set& Set::operator &=(const Set& first) { if(!first.m_tree || !m_tree) { m_tree = 0; return *this; } Q_ASSERT(m_repository); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); m_tree = alg.set_intersect(m_tree, first.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(first.m_tree)); ifDebug(alg.check(m_tree)); return *this; } Set Set::operator -(const Set& rhs) const { if(!m_tree || !rhs.m_tree) return *this; Q_ASSERT(m_repository); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); Set ret( alg.set_subtract(m_tree, rhs.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(rhs.m_tree)), m_repository ); ifDebug( alg.check(ret.m_tree) ); return ret; } Set& Set::operator -=(const Set& rhs) { if(!m_tree || !rhs.m_tree) return *this; Q_ASSERT(m_repository); QMutexLocker lock(m_repository->m_mutex); SetRepositoryAlgorithms alg(m_repository->dataRepository, m_repository); m_tree = alg.set_subtract(m_tree, rhs.m_tree, m_repository->dataRepository.itemFromIndex(m_tree), m_repository->dataRepository.itemFromIndex(rhs.m_tree)); ifDebug(alg.check(m_tree)); return *this; } BasicSetRepository* Set::repository() const { return m_repository; } void Set::staticRef() { if(!m_tree) return; - QMutexLocker lock(m_repository->m_mutex); - SetNodeData* data = m_repository->dataRepository.dynamicItemFromIndexSimple(m_tree); - ++data->m_refCount; + QMutexLocker lock(m_repository->m_mutex); + SetNodeData* data = m_repository->dataRepository.dynamicItemFromIndexSimple(m_tree); + ++data->m_refCount; } ///Mutex must be locked void Set::unrefNode(uint current) { SetNodeData* data = m_repository->dataRepository.dynamicItemFromIndexSimple(current); Q_ASSERT(data->m_refCount); --data->m_refCount; if(!m_repository->delayedDeletion()) { if(data->m_refCount == 0) { if(data->leftNode()){ Q_ASSERT(data->rightNode()); unrefNode(data->rightNode()); unrefNode(data->leftNode()); }else { //Deleting a leaf Q_ASSERT(data->end() - data->start() == 1); m_repository->itemRemovedFromSets(data->start()); } m_repository->dataRepository.deleteItem(current); } } } ///Decrease the static reference-count of this set by one. This set must have a reference-count > 1. ///If this set reaches the reference-count zero, it will be deleted, and all sub-nodes that also reach the reference-count zero ///will be deleted as well. @warning Either protect ALL your sets by using reference-counting, or don't use it at all. void Set::staticUnref() { if(!m_tree) return; - QMutexLocker lock(m_repository->m_mutex); + QMutexLocker lock(m_repository->m_mutex); - unrefNode(m_tree); + unrefNode(m_tree); } StringSetRepository::StringSetRepository(QString name) : Utils::BasicSetRepository(name) { } void StringSetRepository::itemRemovedFromSets(uint index) { ///Call the IndexedString destructor with enabled reference-counting KDevelop::IndexedString string = KDevelop::IndexedString::fromIndex(index); KDevelop::enableDUChainReferenceCounting(&string, sizeof(KDevelop::IndexedString)); string.~IndexedString(); //Call destructor with enabled reference-counting KDevelop::disableDUChainReferenceCounting(&string); } void StringSetRepository::itemAddedToSets(uint index) { ///Call the IndexedString constructor with enabled reference-counting KDevelop::IndexedString string = KDevelop::IndexedString::fromIndex(index); char data[sizeof(KDevelop::IndexedString)]; KDevelop::enableDUChainReferenceCounting(data, sizeof(KDevelop::IndexedString)); new (data) KDevelop::IndexedString(string); //Call constructor with enabled reference-counting KDevelop::disableDUChainReferenceCounting(data); } } diff --git a/plugins/appwizard/projectvcspage.cpp b/plugins/appwizard/projectvcspage.cpp index 82a378ca44..308359cc05 100644 --- a/plugins/appwizard/projectvcspage.cpp +++ b/plugins/appwizard/projectvcspage.cpp @@ -1,154 +1,154 @@ /*************************************************************************** * This file is part of KDevelop * * Copyright 2007 Andreas Pakulat * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU Library General Public License as * * published by the Free Software Foundation; either version 2 of the * * License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU Library General Public * * License along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "projectvcspage.h" #include "ui_projectvcspage.h" #include #include #include #include #include #include #include using namespace KDevelop; ProjectVcsPage::ProjectVcsPage( KDevelop::IPluginController* controller, QWidget * parent ) : AppWizardPageWidget( parent ), m_ui( new Ui::ProjectVcsPage ) { m_ui->setupUi( this ); QList vcsplugins = controller->allPluginsForExtension ( QStringLiteral("org.kdevelop.IBasicVersionControl") ); int idx = 1; m_ui->vcsImportOptions->insertWidget( 0, new QWidget(this) ); m_ui->vcsTypes->insertItem( 0, i18nc("No Version Control Support chosen", "None") ); foreach( KDevelop::IPlugin* plugin, vcsplugins ) { KDevelop::IBasicVersionControl* iface = plugin->extension(); if( iface ) { KDevelop::VcsImportMetadataWidget* widget = iface->createImportMetadataWidget( m_ui->vcsImportOptions ); if( widget ) { widget->setSourceLocationEditable( false ); widget->setUseSourceDirForDestination( true ); m_ui->vcsTypes->insertItem( idx, iface->name() ); importWidgets.push_back( widget ); vcsPlugins.push_back( qMakePair( controller->pluginInfo( plugin ).pluginId(), iface->name() ) ); m_ui->vcsImportOptions->insertWidget( idx, widget ); idx++; } } } connect( m_ui->vcsTypes, static_cast(&KComboBox::activated), m_ui->vcsImportOptions, &QStackedWidget::setCurrentIndex ); connect( m_ui->vcsTypes, static_cast(&KComboBox::activated), this, &ProjectVcsPage::vcsTypeChanged ); validateData(); } void ProjectVcsPage::vcsTypeChanged( int idx ) { validateData(); int widgetidx = idx - 1; disconnect( this, static_cast(nullptr), this, &ProjectVcsPage::validateData ); if ( widgetidx < 0 || widgetidx >= importWidgets.size()) return; connect( importWidgets[widgetidx], &VcsImportMetadataWidget::changed, this, &ProjectVcsPage::validateData ); } void ProjectVcsPage::validateData() { if( shouldContinue() ) { emit valid(); } else { emit invalid(); } } ProjectVcsPage::~ProjectVcsPage( ) { delete m_ui; } void ProjectVcsPage::setSourceLocation( const QUrl& s ) { foreach(KDevelop::VcsImportMetadataWidget* widget, importWidgets) { widget->setSourceLocation( KDevelop::VcsLocation( s ) ); } } QString ProjectVcsPage::pluginName() const { int idx = m_ui->vcsTypes->currentIndex() - 1; if ( idx < 0 || idx >= vcsPlugins.size()) return QString(); // FIXME: Two return statements return vcsPlugins[idx].first; } QString ProjectVcsPage::commitMessage() const { int idx = m_ui->vcsTypes->currentIndex() - 1; if ( idx < 0 || idx >= importWidgets.size()) return QString(); - return importWidgets[idx]->message(); + return importWidgets[idx]->message(); } QUrl ProjectVcsPage::source() const { int idx = m_ui->vcsTypes->currentIndex() - 1; if ( idx < 0 || idx >= importWidgets.size()) return QUrl(); return importWidgets[idx]->source(); } KDevelop::VcsLocation ProjectVcsPage::destination() const { int idx = m_ui->vcsTypes->currentIndex() - 1; if ( idx < 0 || idx >= importWidgets.size()) return KDevelop::VcsLocation(); return importWidgets[idx]->destination(); } bool ProjectVcsPage::shouldContinue() { int idx = m_ui->vcsTypes->currentIndex() - 1; if ( idx < 0 || idx >= importWidgets.size()) return true; KDevelop::VcsImportMetadataWidget* widget = importWidgets[idx]; return widget->hasValidData(); } diff --git a/plugins/contextbrowser/contextbrowser.cpp b/plugins/contextbrowser/contextbrowser.cpp index eb86eb3eaf..f8ab2aa9f4 100644 --- a/plugins/contextbrowser/contextbrowser.cpp +++ b/plugins/contextbrowser/contextbrowser.cpp @@ -1,1347 +1,1347 @@ /* * This file is part of KDevelop * * Copyright 2007 David Nolden * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this program; if not, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "contextbrowser.h" #include "contextbrowserview.h" #include "browsemanager.h" #include "debug.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include Q_LOGGING_CATEGORY(PLUGIN_CONTEXTBROWSER, "kdevplatform.plugins.contextbrowser") using KTextEditor::Attribute; using KTextEditor::View; // Helper that follows the QObject::parent() chain, and returns the highest widget that has no parent. QWidget* masterWidget(QWidget* w) { while(w && w->parent() && qobject_cast(w->parent())) w = qobject_cast(w->parent()); return w; } namespace { const unsigned int highlightingTimeout = 150; const float highlightingZDepth = -5000; const int maxHistoryLength = 30; // Helper that determines the context to use for highlighting at a specific position DUContext* contextForHighlightingAt(const KTextEditor::Cursor& position, TopDUContext* topContext) { DUContext* ctx = topContext->findContextAt(topContext->transformToLocalRevision(position)); while(ctx && ctx->parentContext() && (ctx->type() == DUContext::Template || ctx->type() == DUContext::Helper || ctx->localScopeIdentifier().isEmpty())) { ctx = ctx->parentContext(); } return ctx; } ///Duchain must be locked DUContext* getContextAt(const QUrl& url, KTextEditor::Cursor cursor) { TopDUContext* topContext = DUChainUtils::standardContextForUrl(url); if (!topContext) return 0; return contextForHighlightingAt(KTextEditor::Cursor(cursor), topContext); } DeclarationPointer cursorDeclaration() { KTextEditor::View* view = ICore::self()->documentController()->activeTextDocumentView(); if (!view) { return DeclarationPointer(); } DUChainReadLocker lock; Declaration *decl = DUChainUtils::declarationForDefinition(DUChainUtils::itemUnderCursor(view->document()->url(), KTextEditor::Cursor(view->cursorPosition()))); return DeclarationPointer(decl); } } class ContextBrowserViewFactory: public KDevelop::IToolViewFactory { public: ContextBrowserViewFactory(ContextBrowserPlugin *plugin): m_plugin(plugin) {} QWidget* create(QWidget *parent = 0) override { ContextBrowserView* ret = new ContextBrowserView(m_plugin, parent); return ret; } Qt::DockWidgetArea defaultPosition() override { return Qt::BottomDockWidgetArea; } QString id() const override { return QStringLiteral("org.kdevelop.ContextBrowser"); } private: ContextBrowserPlugin *m_plugin; }; KXMLGUIClient* ContextBrowserPlugin::createGUIForMainWindow( Sublime::MainWindow* window ) { KXMLGUIClient* ret = KDevelop::IPlugin::createGUIForMainWindow( window ); m_browseManager = new BrowseManager(this); connect(ICore::self()->documentController(), &IDocumentController::documentJumpPerformed, this, &ContextBrowserPlugin::documentJumpPerformed); m_previousButton = new QToolButton(); m_previousButton->setToolTip(i18n("Go back in context history")); m_previousButton->setPopupMode(QToolButton::MenuButtonPopup); m_previousButton->setIcon(QIcon::fromTheme(QStringLiteral("go-previous"))); m_previousButton->setEnabled(false); m_previousButton->setFocusPolicy(Qt::NoFocus); m_previousMenu = new QMenu(); m_previousButton->setMenu(m_previousMenu); connect(m_previousButton.data(), &QToolButton::clicked, this, &ContextBrowserPlugin::historyPrevious); connect(m_previousMenu.data(), &QMenu::aboutToShow, this, &ContextBrowserPlugin::previousMenuAboutToShow); m_nextButton = new QToolButton(); m_nextButton->setToolTip(i18n("Go forward in context history")); m_nextButton->setPopupMode(QToolButton::MenuButtonPopup); m_nextButton->setIcon(QIcon::fromTheme(QStringLiteral("go-next"))); m_nextButton->setEnabled(false); m_nextButton->setFocusPolicy(Qt::NoFocus); m_nextMenu = new QMenu(); m_nextButton->setMenu(m_nextMenu); connect(m_nextButton.data(), &QToolButton::clicked, this, &ContextBrowserPlugin::historyNext); connect(m_nextMenu.data(), &QMenu::aboutToShow, this, &ContextBrowserPlugin::nextMenuAboutToShow); IQuickOpen* quickOpen = KDevelop::ICore::self()->pluginController()->extensionForPlugin(QStringLiteral("org.kdevelop.IQuickOpen")); if(quickOpen) { m_outlineLine = quickOpen->createQuickOpenLine(QStringList(), QStringList() << i18n("Outline"), IQuickOpen::Outline); m_outlineLine->setDefaultText(i18n("Outline...")); m_outlineLine->setToolTip(i18n("Navigate outline of active document, click to browse.")); } connect(m_browseManager, &BrowseManager::startDelayedBrowsing, this, &ContextBrowserPlugin::startDelayedBrowsing); connect(m_browseManager, &BrowseManager::stopDelayedBrowsing, this, &ContextBrowserPlugin::stopDelayedBrowsing); m_toolbarWidget = toolbarWidgetForMainWindow(window); m_toolbarWidgetLayout = new QHBoxLayout; m_toolbarWidgetLayout->setSizeConstraint(QLayout::SetMaximumSize); m_previousButton->setSizePolicy(QSizePolicy::Fixed, QSizePolicy::Fixed); m_nextButton->setSizePolicy(QSizePolicy::Fixed, QSizePolicy::Fixed); m_toolbarWidgetLayout->setMargin(0); m_toolbarWidgetLayout->addWidget(m_previousButton); if (m_outlineLine) { m_toolbarWidgetLayout->addWidget(m_outlineLine); m_outlineLine->setMaximumWidth(600); connect(ICore::self()->documentController(), &IDocumentController::documentClosed, m_outlineLine.data(), &IQuickOpenLine::clear); } m_toolbarWidgetLayout->addWidget(m_nextButton); if(m_toolbarWidget->children().isEmpty()) m_toolbarWidget->setLayout(m_toolbarWidgetLayout); connect(ICore::self()->documentController(), &IDocumentController::documentActivated, this, &ContextBrowserPlugin::documentActivated); return ret; } void ContextBrowserPlugin::createActionsForMainWindow(Sublime::MainWindow* window, QString& xmlFile, KActionCollection& actions) { xmlFile = QStringLiteral("kdevcontextbrowser.rc") ; QAction* previousContext = actions.addAction(QStringLiteral("previous_context")); previousContext->setText( i18n("&Previous Visited Context") ); previousContext->setIcon( QIcon::fromTheme(QStringLiteral("go-previous-context") ) ); actions.setDefaultShortcut( previousContext, Qt::META | Qt::Key_Left ); QObject::connect(previousContext, &QAction::triggered, this, &ContextBrowserPlugin::previousContextShortcut); QAction* nextContext = actions.addAction(QStringLiteral("next_context")); nextContext->setText( i18n("&Next Visited Context") ); nextContext->setIcon( QIcon::fromTheme(QStringLiteral("go-next-context") ) ); actions.setDefaultShortcut( nextContext, Qt::META | Qt::Key_Right ); QObject::connect(nextContext, &QAction::triggered, this, &ContextBrowserPlugin::nextContextShortcut); QAction* previousUse = actions.addAction(QStringLiteral("previous_use")); previousUse->setText( i18n("&Previous Use") ); previousUse->setIcon( QIcon::fromTheme(QStringLiteral("go-previous-use")) ); actions.setDefaultShortcut( previousUse, Qt::META | Qt::SHIFT | Qt::Key_Left ); QObject::connect(previousUse, &QAction::triggered, this, &ContextBrowserPlugin::previousUseShortcut); QAction* nextUse = actions.addAction(QStringLiteral("next_use")); nextUse->setText( i18n("&Next Use") ); nextUse->setIcon( QIcon::fromTheme(QStringLiteral("go-next-use")) ); actions.setDefaultShortcut( nextUse, Qt::META | Qt::SHIFT | Qt::Key_Right ); QObject::connect(nextUse, &QAction::triggered, this, &ContextBrowserPlugin::nextUseShortcut); QWidgetAction* outline = new QWidgetAction(this); outline->setText(i18n("Context Browser")); QWidget* w = toolbarWidgetForMainWindow(window); w->setHidden(false); outline->setDefaultWidget(w); actions.addAction(QStringLiteral("outline_line"), outline); // Add to the actioncollection so one can set global shortcuts for the action actions.addAction(QStringLiteral("find_uses"), m_findUses); } void ContextBrowserPlugin::nextContextShortcut() { // TODO: cleanup historyNext(); } void ContextBrowserPlugin::previousContextShortcut() { // TODO: cleanup historyPrevious(); } K_PLUGIN_FACTORY_WITH_JSON(ContextBrowserFactory, "kdevcontextbrowser.json", registerPlugin();) ContextBrowserPlugin::ContextBrowserPlugin(QObject *parent, const QVariantList&) : KDevelop::IPlugin(QStringLiteral("kdevcontextbrowser"), parent) , m_viewFactory(new ContextBrowserViewFactory(this)) , m_nextHistoryIndex(0) , m_textHintProvider(this) { KDEV_USE_EXTENSION_INTERFACE( IContextBrowser ) core()->uiController()->addToolView(i18n("Code Browser"), m_viewFactory); connect( core()->documentController(), &IDocumentController::textDocumentCreated, this, &ContextBrowserPlugin::textDocumentCreated ); connect( DUChain::self(), &DUChain::updateReady, this, &ContextBrowserPlugin::updateReady); connect( DUChain::self(), &DUChain::declarationSelected, this, &ContextBrowserPlugin::declarationSelectedInUI ); m_updateTimer = new QTimer(this); m_updateTimer->setSingleShot(true); connect( m_updateTimer, &QTimer::timeout, this, &ContextBrowserPlugin::updateViews ); //Needed global action for the context-menu extensions m_findUses = new QAction(i18n("Find Uses"), this); connect(m_findUses, &QAction::triggered, this, &ContextBrowserPlugin::findUses); } ContextBrowserPlugin::~ContextBrowserPlugin() { ///TODO: QObject inheritance should suffice? delete m_nextMenu; delete m_previousMenu; delete m_toolbarWidgetLayout; delete m_previousButton; delete m_outlineLine; delete m_nextButton; } void ContextBrowserPlugin::unload() { core()->uiController()->removeToolView(m_viewFactory); } KDevelop::ContextMenuExtension ContextBrowserPlugin::contextMenuExtension(KDevelop::Context* context) { KDevelop::ContextMenuExtension menuExt = KDevelop::IPlugin::contextMenuExtension( context ); KDevelop::DeclarationContext *codeContext = dynamic_cast(context); if (!codeContext) return menuExt; DUChainReadLocker lock(DUChain::lock()); if(!codeContext->declaration().data()) return menuExt; qRegisterMetaType("KDevelop::IndexedDeclaration"); menuExt.addAction(KDevelop::ContextMenuExtension::ExtensionGroup, m_findUses); return menuExt; } void ContextBrowserPlugin::showUses(const DeclarationPointer& declaration) { QMetaObject::invokeMethod(this, "showUsesDelayed", Qt::QueuedConnection, Q_ARG(KDevelop::DeclarationPointer, declaration)); } void ContextBrowserPlugin::showUsesDelayed(const DeclarationPointer& declaration) { DUChainReadLocker lock; Declaration* decl = declaration.data(); if(!decl) { return; } QWidget* toolView = ICore::self()->uiController()->findToolView(i18n("Code Browser"), m_viewFactory, KDevelop::IUiController::CreateAndRaise); if(!toolView) { return; } ContextBrowserView* view = dynamic_cast(toolView); Q_ASSERT(view); view->allowLockedUpdate(); view->setDeclaration(decl, decl->topContext(), true); //We may get deleted while the call to acceptLink, so make sure we don't crash in that case QPointer widget = dynamic_cast(view->navigationWidget()); if(widget && widget->context()) { NavigationContextPointer nextContext = widget->context()->execute( NavigationAction(declaration, KDevelop::NavigationAction::ShowUses)); if(widget) { widget->setContext( nextContext ); } } } void ContextBrowserPlugin::findUses() { showUses(cursorDeclaration()); } ContextBrowserHintProvider::ContextBrowserHintProvider(ContextBrowserPlugin* plugin) : m_plugin(plugin) { } QString ContextBrowserHintProvider::textHint(View* view, const KTextEditor::Cursor& cursor) { m_plugin->m_mouseHoverCursor = KTextEditor::Cursor(cursor); if(!view) { qWarning() << "could not cast to view"; }else{ m_plugin->m_mouseHoverDocument = view->document()->url(); m_plugin->m_updateViews << view; } m_plugin->m_updateTimer->start(1); // triggers updateViews() m_plugin->showToolTip(view, cursor); return QString(); } void ContextBrowserPlugin::stopDelayedBrowsing() { hideToolTip(); } void ContextBrowserPlugin::startDelayedBrowsing(KTextEditor::View* view) { if(!m_currentToolTip) { showToolTip(view, view->cursorPosition()); } } void ContextBrowserPlugin::hideToolTip() { if(m_currentToolTip) { m_currentToolTip->deleteLater(); m_currentToolTip = 0; m_currentNavigationWidget = 0; } } void ContextBrowserPlugin::showToolTip(KTextEditor::View* view, KTextEditor::Cursor position) { ContextBrowserView* contextView = browserViewForWidget(view); if(contextView && contextView->isVisible() && !contextView->isLocked()) return; // If the context-browser view is visible, it will care about updating by itself QUrl viewUrl = view->document()->url(); auto languages = ICore::self()->languageController()->languagesForUrl(viewUrl); QWidget* navigationWidget = 0; { DUChainReadLocker lock(DUChain::lock()); foreach (const auto language, languages) { auto widget = language->specialLanguageObjectNavigationWidget(viewUrl, KTextEditor::Cursor(position)); navigationWidget = qobject_cast(widget); if(navigationWidget) break; } if(!navigationWidget) { Declaration* decl = DUChainUtils::declarationForDefinition( DUChainUtils::itemUnderCursor(viewUrl, KTextEditor::Cursor(position)) ); if (decl && decl->kind() == Declaration::Alias) { AliasDeclaration* alias = dynamic_cast(decl); Q_ASSERT(alias); DUChainReadLocker lock; decl = alias->aliasedDeclaration().declaration(); } if(decl) { if(m_currentToolTipDeclaration == IndexedDeclaration(decl) && m_currentToolTip) return; m_currentToolTipDeclaration = IndexedDeclaration(decl); navigationWidget = decl->context()->createNavigationWidget(decl, DUChainUtils::standardContextForUrl(viewUrl)); } } } if(navigationWidget) { // If we have an invisible context-view, assign the tooltip navigation-widget to it. // If the user makes the context-view visible, it will instantly contain the correct widget. if(contextView && !contextView->isLocked()) contextView->setNavigationWidget(navigationWidget); if(m_currentToolTip) { m_currentToolTip->deleteLater(); m_currentToolTip = 0; m_currentNavigationWidget = 0; } KDevelop::NavigationToolTip* tooltip = new KDevelop::NavigationToolTip(view, view->mapToGlobal(view->cursorToCoordinate(position)) + QPoint(20, 40), navigationWidget); KTextEditor::Range itemRange; { DUChainReadLocker lock; itemRange = DUChainUtils::itemRangeUnderCursor(viewUrl, KTextEditor::Cursor(position)); } tooltip->setHandleRect(KTextEditorHelpers::getItemBoundingRect(view, itemRange)); tooltip->resize( navigationWidget->sizeHint() + QSize(10, 10) ); qCDebug(PLUGIN_CONTEXTBROWSER) << "tooltip size" << tooltip->size(); m_currentToolTip = tooltip; m_currentNavigationWidget = navigationWidget; ActiveToolTip::showToolTip(tooltip); if ( ! navigationWidget->property("DoNotCloseOnCursorMove").toBool() ) { connect(view, &View::cursorPositionChanged, this, &ContextBrowserPlugin::hideToolTip, Qt::UniqueConnection); } else { disconnect(view, &View::cursorPositionChanged, this, &ContextBrowserPlugin::hideToolTip); } }else{ qCDebug(PLUGIN_CONTEXTBROWSER) << "not showing tooltip, no navigation-widget"; } } void ContextBrowserPlugin::clearMouseHover() { m_mouseHoverCursor = KTextEditor::Cursor::invalid(); m_mouseHoverDocument.clear(); } Attribute::Ptr highlightedUseAttribute() { static Attribute::Ptr standardAttribute = Attribute::Ptr(); if( !standardAttribute ) { standardAttribute= Attribute::Ptr( new Attribute() ); standardAttribute->setBackgroundFillWhitespace(true); // mixing (255, 255, 0, 100) with white yields this: standardAttribute->setBackground(QColor(251, 250, 150)); // force a foreground color to overwrite default Kate highlighting, i.e. of Q_OBJECT or similar // foreground color could change, hence apply it everytime standardAttribute->setForeground(QColor(0, 0, 0, 255)); //Don't use alpha here, as kate uses the alpha only to blend with the document background color } return standardAttribute; } Attribute::Ptr highlightedSpecialObjectAttribute() { static Attribute::Ptr standardAttribute = Attribute::Ptr(); if( !standardAttribute ) { standardAttribute = Attribute::Ptr( new Attribute() ); standardAttribute->setBackgroundFillWhitespace(true); // mixing (90, 255, 0, 100) with white yields this: standardAttribute->setBackground(QColor(190, 255, 155)); // force a foreground color to overwrite default Kate highlighting, i.e. of Q_OBJECT or similar // foreground color could change, hence apply it everytime standardAttribute->setForeground(QColor(0, 0, 0, 255)); //Don't use alpha here, as kate uses the alpha only to blend with the document background color } return standardAttribute; } void ContextBrowserPlugin::addHighlight( View* view, KDevelop::Declaration* decl ) { if( !view || !decl ) { qCDebug(PLUGIN_CONTEXTBROWSER) << "invalid view/declaration"; return; } ViewHighlights& highlights(m_highlightedRanges[view]); KDevelop::DUChainReadLocker lock; // Highlight the declaration highlights.highlights << decl->createRangeMoving(); highlights.highlights.back()->setAttribute(highlightedUseAttribute()); highlights.highlights.back()->setZDepth(highlightingZDepth); // Highlight uses { QMap< IndexedString, QList< KTextEditor::Range > > currentRevisionUses = decl->usesCurrentRevision(); for(QMap< IndexedString, QList< KTextEditor::Range > >::iterator fileIt = currentRevisionUses.begin(); fileIt != currentRevisionUses.end(); ++fileIt) { for(QList< KTextEditor::Range >::const_iterator useIt = (*fileIt).constBegin(); useIt != (*fileIt).constEnd(); ++useIt) { highlights.highlights << PersistentMovingRange::Ptr(new PersistentMovingRange(*useIt, fileIt.key())); highlights.highlights.back()->setAttribute(highlightedUseAttribute()); highlights.highlights.back()->setZDepth(highlightingZDepth); } } } if( FunctionDefinition* def = FunctionDefinition::definition(decl) ) { highlights.highlights << def->createRangeMoving(); highlights.highlights.back()->setAttribute(highlightedUseAttribute()); highlights.highlights.back()->setZDepth(highlightingZDepth); } } Declaration* ContextBrowserPlugin::findDeclaration(View* view, const KTextEditor::Cursor& position, bool mouseHighlight) { Q_UNUSED(mouseHighlight); Declaration* foundDeclaration = 0; if(m_useDeclaration.data()) { foundDeclaration = m_useDeclaration.data(); }else{ //If we haven't found a special language object, search for a use/declaration and eventually highlight it foundDeclaration = DUChainUtils::declarationForDefinition( DUChainUtils::itemUnderCursor(view->document()->url(), position) ); if (foundDeclaration && foundDeclaration->kind() == Declaration::Alias) { AliasDeclaration* alias = dynamic_cast(foundDeclaration); Q_ASSERT(alias); DUChainReadLocker lock; foundDeclaration = alias->aliasedDeclaration().declaration(); } } return foundDeclaration; } ContextBrowserView* ContextBrowserPlugin::browserViewForWidget(QWidget* widget) { foreach(ContextBrowserView* contextView, m_views) { if(masterWidget(contextView) == masterWidget(widget)) { return contextView; } } return 0; } void ContextBrowserPlugin::updateForView(View* view) { bool allowHighlight = true; if(view->selection()) { // If something is selected, we unhighlight everything, so that we don't conflict with the // kate plugin that highlights occurrences of the selected string, and also to reduce the // overall amount of concurrent highlighting. allowHighlight = false; } if(m_highlightedRanges[view].keep) { m_highlightedRanges[view].keep = false; return; } // Clear all highlighting m_highlightedRanges.clear(); // Re-highlight ViewHighlights& highlights = m_highlightedRanges[view]; QUrl url = view->document()->url(); IDocument* activeDoc = core()->documentController()->activeDocument(); bool mouseHighlight = (url == m_mouseHoverDocument) && (m_mouseHoverCursor.isValid()); bool shouldUpdateBrowser = (mouseHighlight || (view == ICore::self()->documentController()->activeTextDocumentView() && activeDoc && activeDoc->textDocument() == view->document())); KTextEditor::Cursor highlightPosition; if (mouseHighlight) highlightPosition = m_mouseHoverCursor; else highlightPosition = KTextEditor::Cursor(view->cursorPosition()); ///Pick a language ILanguageSupport* language = nullptr; if(ICore::self()->languageController()->languagesForUrl(url).isEmpty()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "found no language for document" << url; return; }else{ language = ICore::self()->languageController()->languagesForUrl(url).front(); } ///Check whether there is a special language object to highlight (for example a macro) KTextEditor::Range specialRange = language->specialLanguageObjectRange(url, highlightPosition); ContextBrowserView* updateBrowserView = shouldUpdateBrowser ? browserViewForWidget(view) : 0; if(specialRange.isValid()) { // Highlight a special language object if(allowHighlight) { highlights.highlights << PersistentMovingRange::Ptr(new PersistentMovingRange(specialRange, IndexedString(url))); highlights.highlights.back()->setAttribute(highlightedSpecialObjectAttribute()); highlights.highlights.back()->setZDepth(highlightingZDepth); } if(updateBrowserView) updateBrowserView->setSpecialNavigationWidget(language->specialLanguageObjectNavigationWidget(url, highlightPosition)); }else{ KDevelop::DUChainReadLocker lock( DUChain::lock(), 100 ); if(!lock.locked()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "Failed to lock du-chain in time"; return; } TopDUContext* topContext = DUChainUtils::standardContextForUrl(view->document()->url()); if (!topContext) return; DUContext* ctx = contextForHighlightingAt(highlightPosition, topContext); if (!ctx) return; //Only update the history if this context is around the text cursor if(core()->documentController()->activeDocument() && highlightPosition == KTextEditor::Cursor(view->cursorPosition()) && view->document() == core()->documentController()->activeDocument()->textDocument()) { updateHistory(ctx, highlightPosition); } Declaration* foundDeclaration = findDeclaration(view, highlightPosition, mouseHighlight); if( foundDeclaration ) { m_lastHighlightedDeclaration = highlights.declaration = IndexedDeclaration(foundDeclaration); if(allowHighlight) addHighlight( view, foundDeclaration ); if(updateBrowserView) updateBrowserView->setDeclaration(foundDeclaration, topContext); }else{ if(updateBrowserView) updateBrowserView->setContext(ctx); } } } void ContextBrowserPlugin::updateViews() { foreach( View* view, m_updateViews ) { updateForView(view); } m_updateViews.clear(); m_useDeclaration = IndexedDeclaration(); } void ContextBrowserPlugin::declarationSelectedInUI(const DeclarationPointer& decl) { m_useDeclaration = IndexedDeclaration(decl.data()); KTextEditor::View* view = core()->documentController()->activeTextDocumentView(); if(view) m_updateViews << view; if(!m_updateViews.isEmpty()) m_updateTimer->start(highlightingTimeout); // triggers updateViews() } void ContextBrowserPlugin::updateReady(const IndexedString& file, const ReferencedTopDUContext& /*topContext*/) { const auto url = file.toUrl(); for(QMap< View*, ViewHighlights >::iterator it = m_highlightedRanges.begin(); it != m_highlightedRanges.end(); ++it) { if(it.key()->document()->url() == url) { if(!m_updateViews.contains(it.key())) { qCDebug(PLUGIN_CONTEXTBROWSER) << "adding view for update"; m_updateViews << it.key(); // Don't change the highlighted declaration after finished parse-jobs (*it).keep = true; } } } if(!m_updateViews.isEmpty()) m_updateTimer->start(highlightingTimeout); } void ContextBrowserPlugin::textDocumentCreated( KDevelop::IDocument* document ) { Q_ASSERT(document->textDocument()); connect( document->textDocument(), &KTextEditor::Document::viewCreated, this, &ContextBrowserPlugin::viewCreated ); foreach( View* view, document->textDocument()->views() ) viewCreated( document->textDocument(), view ); } void ContextBrowserPlugin::documentActivated( IDocument* doc ) { if (m_outlineLine) m_outlineLine->clear(); if (View* view = doc->activeTextView()) { cursorPositionChanged(view, view->cursorPosition()); } } void ContextBrowserPlugin::viewDestroyed( QObject* obj ) { m_highlightedRanges.remove(static_cast(obj)); m_updateViews.remove(static_cast(obj)); } void ContextBrowserPlugin::selectionChanged( View* view ) { clearMouseHover(); m_updateViews.insert(view); m_updateTimer->start(highlightingTimeout/2); // triggers updateViews() } void ContextBrowserPlugin::cursorPositionChanged( View* view, const KTextEditor::Cursor& newPosition ) { if(view->document() == m_lastInsertionDocument && newPosition == m_lastInsertionPos) { //Do not update the highlighting while typing m_lastInsertionDocument = 0; m_lastInsertionPos = KTextEditor::Cursor(); if(m_highlightedRanges.contains(view)) m_highlightedRanges[view].keep = true; }else{ if(m_highlightedRanges.contains(view)) m_highlightedRanges[view].keep = false; } clearMouseHover(); m_updateViews.insert(view); m_updateTimer->start(highlightingTimeout/2); // triggers updateViews() } void ContextBrowserPlugin::textInserted(KTextEditor::Document* doc, const KTextEditor::Cursor& cursor, const QString& text) { m_lastInsertionDocument = doc; m_lastInsertionPos = cursor + KTextEditor::Cursor(0, text.size()); } void ContextBrowserPlugin::viewCreated( KTextEditor::Document* , View* v ) { disconnect( v, &View::cursorPositionChanged, this, &ContextBrowserPlugin::cursorPositionChanged ); ///Just to make sure that multiple connections don't happen connect( v, &View::cursorPositionChanged, this, &ContextBrowserPlugin::cursorPositionChanged ); connect( v, &View::destroyed, this, &ContextBrowserPlugin::viewDestroyed ); disconnect( v->document(), &KTextEditor::Document::textInserted, this, &ContextBrowserPlugin::textInserted); connect(v->document(), &KTextEditor::Document::textInserted, this, &ContextBrowserPlugin::textInserted); disconnect(v, &View::selectionChanged, this, &ContextBrowserPlugin::selectionChanged); KTextEditor::TextHintInterface *iface = dynamic_cast(v); if( !iface ) return; iface->setTextHintDelay(highlightingTimeout); iface->registerTextHintProvider(&m_textHintProvider); } void ContextBrowserPlugin::registerToolView(ContextBrowserView* view) { m_views << view; } void ContextBrowserPlugin::previousUseShortcut() { switchUse(false); } void ContextBrowserPlugin::nextUseShortcut() { switchUse(true); } KTextEditor::Range cursorToRange(KTextEditor::Cursor cursor) { return KTextEditor::Range(cursor, cursor); } void ContextBrowserPlugin::switchUse(bool forward) { View* view = core()->documentController()->activeTextDocumentView(); if(view) { KTextEditor::Document* doc = view->document(); KDevelop::DUChainReadLocker lock( DUChain::lock() ); KDevelop::TopDUContext* chosen = DUChainUtils::standardContextForUrl(doc->url()); if( chosen ) { KTextEditor::Cursor cCurrent(view->cursorPosition()); KDevelop::CursorInRevision c = chosen->transformToLocalRevision(cCurrent); Declaration* decl = 0; //If we have a locked declaration, use that for jumping foreach(ContextBrowserView* view, m_views) { decl = view->lockedDeclaration().data(); ///@todo Somehow match the correct context-browser view if there is multiple if(decl) break; } if(!decl) //Try finding a declaration under the cursor decl = DUChainUtils::itemUnderCursor(doc->url(), cCurrent); if (decl && decl->kind() == Declaration::Alias) { AliasDeclaration* alias = dynamic_cast(decl); Q_ASSERT(alias); DUChainReadLocker lock; decl = alias->aliasedDeclaration().declaration(); } if(decl) { Declaration* target = 0; if(forward) //Try jumping from definition to declaration target = DUChainUtils::declarationForDefinition(decl, chosen); else if(decl->url().toUrl() == doc->url() && decl->range().contains(c)) //Try jumping from declaration to definition target = FunctionDefinition::definition(decl); - if(target && target != decl) { - KTextEditor::Cursor jumpTo = target->rangeInCurrentRevision().start(); - QUrl document = target->url().toUrl(); - lock.unlock(); - core()->documentController()->openDocument( document, cursorToRange(jumpTo) ); - return; - }else{ - //Always work with the declaration instead of the definition - decl = DUChainUtils::declarationForDefinition(decl, chosen); - } + if(target && target != decl) { + KTextEditor::Cursor jumpTo = target->rangeInCurrentRevision().start(); + QUrl document = target->url().toUrl(); + lock.unlock(); + core()->documentController()->openDocument( document, cursorToRange(jumpTo) ); + return; + }else{ + //Always work with the declaration instead of the definition + decl = DUChainUtils::declarationForDefinition(decl, chosen); + } } if(!decl) { //Pick the last use we have highlighted decl = m_lastHighlightedDeclaration.data(); } if(decl) { KDevVarLengthArray usingFiles = DUChain::uses()->uses(decl->id()); if(DUChainUtils::contextHasUse(decl->topContext(), decl) && usingFiles.indexOf(decl->topContext()) == -1) usingFiles.insert(0, decl->topContext()); if(decl->range().contains(c) && decl->url() == chosen->url()) { //The cursor is directly on the declaration. Jump to the first or last use. if(!usingFiles.isEmpty()) { TopDUContext* top = (forward ? usingFiles[0] : usingFiles.back()).data(); if(top) { QList useRanges = allUses(top, decl, true); std::sort(useRanges.begin(), useRanges.end()); if(!useRanges.isEmpty()) { QUrl url = top->url().toUrl(); KTextEditor::Range selectUse = chosen->transformFromLocalRevision(forward ? useRanges.first() : useRanges.back()); lock.unlock(); core()->documentController()->openDocument(url, cursorToRange(selectUse.start())); } } } return; } //Check whether we are within a use QList localUses = allUses(chosen, decl, true); std::sort(localUses.begin(), localUses.end()); for(int a = 0; a < localUses.size(); ++a) { int nextUse = (forward ? a+1 : a-1); bool pick = localUses[a].contains(c); if(!pick && forward && a+1 < localUses.size() && localUses[a].end <= c && localUses[a+1].start > c) { //Special case: We aren't on a use, but we are jumping forward, and are behind this and the next use pick = true; } if(!pick && !forward && a-1 >= 0 && c < localUses[a].start && c >= localUses[a-1].end) { //Special case: We aren't on a use, but we are jumping backward, and are in front of this use, but behind the previous one pick = true; } if(!pick && a == 0 && c < localUses[a].start) { if(!forward) { //Will automatically jump to previous file }else{ nextUse = 0; //We are before the first use, so jump to it. } pick = true; } if(!pick && a == localUses.size()-1 && c >= localUses[a].end) { if(forward) { //Will automatically jump to next file }else{ //We are behind the last use, but moving backward. So pick the last use. nextUse = a; } pick = true; } if(pick) { //Make sure we end up behind the use if(nextUse != a) while(forward && nextUse < localUses.size() && (localUses[nextUse].start <= localUses[a].end || localUses[nextUse].isEmpty())) ++nextUse; //Make sure we end up before the use if(nextUse != a) while(!forward && nextUse >= 0 && (localUses[nextUse].start >= localUses[a].start || localUses[nextUse].isEmpty())) --nextUse; //Jump to the next use qCDebug(PLUGIN_CONTEXTBROWSER) << "count of uses:" << localUses.size() << "nextUse" << nextUse; if(nextUse < 0 || nextUse == localUses.size()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "jumping to next file"; //Jump to the first use in the next using top-context int indexInFiles = usingFiles.indexOf(chosen); if(indexInFiles != -1) { int nextFile = (forward ? indexInFiles+1 : indexInFiles-1); qCDebug(PLUGIN_CONTEXTBROWSER) << "current file" << indexInFiles << "nextFile" << nextFile; if(nextFile < 0 || nextFile >= usingFiles.size()) { //Open the declaration, or the definition if(nextFile >= usingFiles.size()) { Declaration* definition = FunctionDefinition::definition(decl); if(definition) decl = definition; } QUrl u = decl->url().toUrl(); KTextEditor::Range range = decl->rangeInCurrentRevision(); range.setEnd(range.start()); lock.unlock(); core()->documentController()->openDocument(u, range); return; }else{ TopDUContext* nextTop = usingFiles[nextFile].data(); QUrl u = nextTop->url().toUrl(); QList nextTopUses = allUses(nextTop, decl, true); std::sort(nextTopUses.begin(), nextTopUses.end()); if(!nextTopUses.isEmpty()) { KTextEditor::Range range = chosen->transformFromLocalRevision(forward ? nextTopUses.front() : nextTopUses.back()); range.setEnd(range.start()); lock.unlock(); core()->documentController()->openDocument(u, range); } return; } }else{ qCDebug(PLUGIN_CONTEXTBROWSER) << "not found own file in use list"; } }else{ QUrl url = chosen->url().toUrl(); KTextEditor::Range range = chosen->transformFromLocalRevision(localUses[nextUse]); range.setEnd(range.start()); lock.unlock(); core()->documentController()->openDocument(url, range); return; } } } } } } } void ContextBrowserPlugin::unRegisterToolView(ContextBrowserView* view) { m_views.removeAll(view); } // history browsing QWidget* ContextBrowserPlugin::toolbarWidgetForMainWindow( Sublime::MainWindow* window ) { //TODO: support multiple windows (if that ever gets revived) if (!m_toolbarWidget) { m_toolbarWidget = new QWidget(window); } return m_toolbarWidget; } void ContextBrowserPlugin::documentJumpPerformed( KDevelop::IDocument* newDocument, const KTextEditor::Cursor& newCursor, KDevelop::IDocument* previousDocument, const KTextEditor::Cursor& previousCursor) { DUChainReadLocker lock(DUChain::lock()); /*TODO: support multiple windows if that ever gets revived if(newDocument && newDocument->textDocument() && newDocument->textDocument()->activeView() && masterWidget(newDocument->textDocument()->activeView()) != masterWidget(this)) return; */ if(previousDocument && previousCursor.isValid()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "updating jump source"; DUContext* context = getContextAt(previousDocument->url(), previousCursor); if(context) { updateHistory(context, KTextEditor::Cursor(previousCursor), true); }else{ //We just want this place in the history m_history.resize(m_nextHistoryIndex); // discard forward history m_history.append(HistoryEntry(DocumentCursor(IndexedString(previousDocument->url()), KTextEditor::Cursor(previousCursor)))); ++m_nextHistoryIndex; } } qCDebug(PLUGIN_CONTEXTBROWSER) << "new doc: " << newDocument << " new cursor: " << newCursor; if(newDocument && newCursor.isValid()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "updating jump target"; DUContext* context = getContextAt(newDocument->url(), newCursor); if(context) { updateHistory(context, KTextEditor::Cursor(newCursor), true); }else{ //We just want this place in the history m_history.resize(m_nextHistoryIndex); // discard forward history m_history.append(HistoryEntry(DocumentCursor(IndexedString(newDocument->url()), KTextEditor::Cursor(newCursor)))); ++m_nextHistoryIndex; if (m_outlineLine) m_outlineLine->clear(); } } } void ContextBrowserPlugin::updateButtonState() { m_nextButton->setEnabled( m_nextHistoryIndex < m_history.size() ); m_previousButton->setEnabled( m_nextHistoryIndex >= 2 ); } void ContextBrowserPlugin::historyNext() { if(m_nextHistoryIndex >= m_history.size()) { return; } openDocument(m_nextHistoryIndex); // opening the document at given position // will update the widget for us ++m_nextHistoryIndex; updateButtonState(); } void ContextBrowserPlugin::openDocument(int historyIndex) { Q_ASSERT_X(historyIndex >= 0, "openDocument", "negative history index"); Q_ASSERT_X(historyIndex < m_history.size(), "openDocument", "history index out of range"); DocumentCursor c = m_history[historyIndex].computePosition(); if (c.isValid() && !c.document.str().isEmpty()) { disconnect(ICore::self()->documentController(), &IDocumentController::documentJumpPerformed, this, &ContextBrowserPlugin::documentJumpPerformed); ICore::self()->documentController()->openDocument(c.document.toUrl(), c); connect(ICore::self()->documentController(), &IDocumentController::documentJumpPerformed, this, &ContextBrowserPlugin::documentJumpPerformed); KDevelop::DUChainReadLocker lock( KDevelop::DUChain::lock() ); updateDeclarationListBox(m_history[historyIndex].context.data()); } } void ContextBrowserPlugin::historyPrevious() { if(m_nextHistoryIndex < 2) { return; } --m_nextHistoryIndex; openDocument(m_nextHistoryIndex-1); // opening the document at given position // will update the widget for us updateButtonState(); } QString ContextBrowserPlugin::actionTextFor(int historyIndex) const { const HistoryEntry& entry = m_history.at(historyIndex); QString actionText = entry.context.data() ? entry.context.data()->scopeIdentifier(true).toString() : QString(); if(actionText.isEmpty()) actionText = entry.alternativeString; if(actionText.isEmpty()) actionText = QStringLiteral(""); actionText += QLatin1String(" @ "); QString fileName = entry.absoluteCursorPosition.document.toUrl().fileName(); actionText += QStringLiteral("%1:%2").arg(fileName).arg(entry.absoluteCursorPosition.line()+1); return actionText; } /* inline QDebug operator<<(QDebug debug, const ContextBrowserPlugin::HistoryEntry &he) { DocumentCursor c = he.computePosition(); debug << "\n\tHistoryEntry " << c.line << " " << c.document.str(); return debug; } */ void ContextBrowserPlugin::nextMenuAboutToShow() { QList indices; for(int a = m_nextHistoryIndex; a < m_history.size(); ++a) { indices << a; } fillHistoryPopup(m_nextMenu, indices); } void ContextBrowserPlugin::previousMenuAboutToShow() { QList indices; for(int a = m_nextHistoryIndex-2; a >= 0; --a) { indices << a; } fillHistoryPopup(m_previousMenu, indices); } void ContextBrowserPlugin::fillHistoryPopup(QMenu* menu, const QList& historyIndices) { menu->clear(); KDevelop::DUChainReadLocker lock( KDevelop::DUChain::lock() ); foreach(int index, historyIndices) { QAction* action = new QAction(actionTextFor(index), menu); action->setData(index); menu->addAction(action); connect(action, &QAction::triggered, this, &ContextBrowserPlugin::actionTriggered); } } bool ContextBrowserPlugin::isPreviousEntry(KDevelop::DUContext* context, const KTextEditor::Cursor& /*position*/) const { if (m_nextHistoryIndex == 0) return false; Q_ASSERT(m_nextHistoryIndex <= m_history.count()); const HistoryEntry& he = m_history.at(m_nextHistoryIndex-1); KDevelop::DUChainReadLocker lock( KDevelop::DUChain::lock() ); // is this necessary?? Q_ASSERT(context); return IndexedDUContext(context) == he.context; } void ContextBrowserPlugin::updateHistory(KDevelop::DUContext* context, const KTextEditor::Cursor& position, bool force) { qCDebug(PLUGIN_CONTEXTBROWSER) << "updating history"; if(m_outlineLine && m_outlineLine->isVisible()) updateDeclarationListBox(context); if(!context || (!context->owner() && !force)) { return; //Only add history-entries for contexts that have owners, which in practice should be functions and classes //This keeps the history cleaner } if (isPreviousEntry(context, position)) { if(m_nextHistoryIndex) { HistoryEntry& he = m_history[m_nextHistoryIndex-1]; he.setCursorPosition(position); } return; } else { // Append new history entry m_history.resize(m_nextHistoryIndex); // discard forward history m_history.append(HistoryEntry(IndexedDUContext(context), position)); ++m_nextHistoryIndex; updateButtonState(); if(m_history.size() > (maxHistoryLength + 5)) { m_history = m_history.mid(m_history.size() - maxHistoryLength); m_nextHistoryIndex = m_history.size(); } } } void ContextBrowserPlugin::updateDeclarationListBox(DUContext* context) { if(!context || !context->owner()) { qCDebug(PLUGIN_CONTEXTBROWSER) << "not updating box"; m_listUrl = IndexedString(); ///@todo Compute the context in the document here if (m_outlineLine) m_outlineLine->clear(); return; } Declaration* decl = context->owner(); m_listUrl = context->url(); Declaration* specialDecl = SpecializationStore::self().applySpecialization(decl, decl->topContext()); FunctionType::Ptr function = specialDecl->type(); QString text = specialDecl->qualifiedIdentifier().toString(); if(function) text += function->partToString(KDevelop::FunctionType::SignatureArguments); if(m_outlineLine && !m_outlineLine->hasFocus()) { m_outlineLine->setText(text); m_outlineLine->setCursorPosition(0); } qCDebug(PLUGIN_CONTEXTBROWSER) << "updated" << text; } void ContextBrowserPlugin::actionTriggered() { QAction* action = qobject_cast(sender()); Q_ASSERT(action); Q_ASSERT(action->data().type() == QVariant::Int); int historyPosition = action->data().toInt(); // qCDebug(PLUGIN_CONTEXTBROWSER) << "history pos" << historyPosition << m_history.size() << m_history; if(historyPosition >= 0 && historyPosition < m_history.size()) { m_nextHistoryIndex = historyPosition + 1; openDocument(historyPosition); updateButtonState(); } } void ContextBrowserPlugin::doNavigate(NavigationActionType action) { KTextEditor::View* view = qobject_cast(sender()); if(!view) { qWarning() << "sender is not a view"; return; } KTextEditor::CodeCompletionInterface* iface = qobject_cast(view); if(!iface || iface->isCompletionActive()) return; // If code completion is active, the actions should be handled by the completion widget QWidget* widget = m_currentNavigationWidget.data(); if(!widget || !widget->isVisible()) { ContextBrowserView* contextView = browserViewForWidget(view); if(contextView) widget = contextView->navigationWidget(); } if(widget) { AbstractNavigationWidget* navWidget = qobject_cast(widget); if (navWidget) { switch(action) { case Accept: navWidget->accept(); break; case Back: navWidget->back(); break; case Left: navWidget->previous(); break; case Right: navWidget->next(); break; case Up: navWidget->up(); break; case Down: navWidget->down(); break; } } } } void ContextBrowserPlugin::navigateAccept() { doNavigate(Accept); } void ContextBrowserPlugin::navigateBack() { doNavigate(Back); } void ContextBrowserPlugin::navigateDown() { doNavigate(Down); } void ContextBrowserPlugin::navigateLeft() { doNavigate(Left); } void ContextBrowserPlugin::navigateRight() { doNavigate(Right); } void ContextBrowserPlugin::navigateUp() { doNavigate(Up); } //BEGIN HistoryEntry ContextBrowserPlugin::HistoryEntry::HistoryEntry(KDevelop::DocumentCursor pos) : absoluteCursorPosition(pos) { } ContextBrowserPlugin::HistoryEntry::HistoryEntry(IndexedDUContext ctx, const KTextEditor::Cursor& cursorPosition) : context(ctx) { //Use a position relative to the context setCursorPosition(cursorPosition); if(ctx.data()) alternativeString = ctx.data()->scopeIdentifier(true).toString(); if(!alternativeString.isEmpty()) alternativeString += i18n("(changed)"); //This is used when the context was deleted in between } DocumentCursor ContextBrowserPlugin::HistoryEntry::computePosition() const { KDevelop::DUChainReadLocker lock( KDevelop::DUChain::lock() ); DocumentCursor ret; if(context.data()) { ret = DocumentCursor(context.data()->url(), relativeCursorPosition); ret.setLine(ret.line() + context.data()->range().start.line); }else{ ret = absoluteCursorPosition; } return ret; } void ContextBrowserPlugin::HistoryEntry::setCursorPosition(const KTextEditor::Cursor& cursorPosition) { KDevelop::DUChainReadLocker lock( KDevelop::DUChain::lock() ); if(context.data()) { absoluteCursorPosition = DocumentCursor(context.data()->url(), cursorPosition); relativeCursorPosition = cursorPosition; relativeCursorPosition.setLine(relativeCursorPosition.line() - context.data()->range().start.line); } } // kate: space-indent on; indent-width 2; tab-width 4; replace-tabs on; auto-insert-doxygen on #include "contextbrowser.moc"