diff --git a/kdevplatform/language/duchain/codemodel.cpp b/kdevplatform/language/duchain/codemodel.cpp index 75f3009a6d..e44cc70bc9 100644 --- a/kdevplatform/language/duchain/codemodel.cpp +++ b/kdevplatform/language/duchain/codemodel.cpp @@ -1,395 +1,397 @@ /* This file is part of KDevelop Copyright 2008 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 "codemodel.h" #include "appendedlist.h" #include #include #include "identifier.h" #include #include #include #define ifDebug(x) namespace KDevelop { class CodeModelItemHandler { public: static int leftChild(const CodeModelItem& m_data) { return ( int )m_data.referenceCount; } static void setLeftChild(CodeModelItem& m_data, int child) { m_data.referenceCount = ( uint )child; } static int rightChild(const CodeModelItem& m_data) { return ( int )m_data.uKind; } static void setRightChild(CodeModelItem& m_data, int child) { m_data.uKind = ( uint )child; } //Copies this item into the given one static void copyTo(const CodeModelItem& m_data, CodeModelItem& data) { data = m_data; } static void createFreeItem(CodeModelItem& data) { data = CodeModelItem(); data.referenceCount = (uint) - 1; data.uKind = (uint) - 1; } static bool isFree(const CodeModelItem& m_data) { return !m_data.id.isValid(); } static const CodeModelItem& data(const CodeModelItem& m_data) { return m_data; } static bool equals(const CodeModelItem& m_data, const CodeModelItem& rhs) { return m_data.id == rhs.id; } }; DEFINE_LIST_MEMBER_HASH(CodeModelRepositoryItem, items, CodeModelItem) class CodeModelRepositoryItem { public: CodeModelRepositoryItem() { initializeAppendedLists(); } CodeModelRepositoryItem(const CodeModelRepositoryItem& rhs, bool dynamic = true) : file(rhs.file) , centralFreeItem(rhs.centralFreeItem) { initializeAppendedLists(dynamic); copyListsFrom(rhs); } ~CodeModelRepositoryItem() { freeAppendedLists(); } + CodeModelRepositoryItem& operator=(const CodeModelRepositoryItem& rhs) = delete; + unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return file.index(); } uint itemSize() const { return dynamicSize(); } uint classSize() const { return sizeof(CodeModelRepositoryItem); } IndexedString file; int centralFreeItem = -1; START_APPENDED_LISTS(CodeModelRepositoryItem); APPENDED_LIST_FIRST(CodeModelRepositoryItem, CodeModelItem, items); END_APPENDED_LISTS(CodeModelRepositoryItem, items); }; class CodeModelRequestItem { public: CodeModelRequestItem(const CodeModelRepositoryItem& item) : m_item(item) { } enum { AverageSize = 30 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_item.hash(); } uint itemSize() const { return m_item.itemSize(); } void createItem(CodeModelRepositoryItem* item) const { Q_ASSERT(shouldDoDUChainReferenceCounting(item)); Q_ASSERT(shouldDoDUChainReferenceCounting((( char* )item) + (itemSize() - 1))); new (item) CodeModelRepositoryItem(m_item, false); } static void destroy(CodeModelRepositoryItem* item, KDevelop::AbstractItemRepository&) { Q_ASSERT(shouldDoDUChainReferenceCounting(item)); // Q_ASSERT(shouldDoDUChainReferenceCounting(((char*)item) + (itemSize()-1))); item->~CodeModelRepositoryItem(); } static bool persistent(const CodeModelRepositoryItem* item) { Q_UNUSED(item); return true; } bool equals(const CodeModelRepositoryItem* item) const { return m_item.file == item->file; } const CodeModelRepositoryItem& m_item; }; class CodeModelPrivate { public: CodeModelPrivate() : m_repository(QStringLiteral("Code Model")) { } //Maps declaration-ids to items // mutable as things like findIndex are not const mutable ItemRepository m_repository; }; CodeModel::CodeModel() : d_ptr(new CodeModelPrivate()) { } CodeModel::~CodeModel() = default; void CodeModel::addItem(const IndexedString& file, const IndexedQualifiedIdentifier& id, CodeModelItem::Kind kind) { Q_D(CodeModel); ifDebug(qCDebug(LANGUAGE) << "addItem" << file.str() << id.identifier().toString() << id.index; ) if (!id.isValid()) return; CodeModelRepositoryItem item; item.file = file; CodeModelRequestItem request(item); uint index = d->m_repository.findIndex(item); CodeModelItem newItem; newItem.id = id; newItem.kind = kind; newItem.referenceCount = 1; if (index) { const CodeModelRepositoryItem* oldItem = d->m_repository.itemFromIndex(index); EmbeddedTreeAlgorithms alg(oldItem->items(), oldItem->itemsSize(), oldItem->centralFreeItem); int listIndex = alg.indexOf(newItem); QMutexLocker lock(d->m_repository.mutex()); DynamicItem editableItem = d->m_repository.dynamicItemFromIndex(index); CodeModelItem* items = const_cast(editableItem->items()); if (listIndex != -1) { //Only update the reference-count ++items[listIndex].referenceCount; items[listIndex].kind = kind; return; } else { //Add the item to the list EmbeddedTreeAddItem add(items, editableItem->itemsSize(), editableItem->centralFreeItem, newItem); if (add.newItemCount() != editableItem->itemsSize()) { //The data needs to be transferred into a bigger list. That list is within "item". item.itemsList().resize(add.newItemCount()); add.transferData(item.itemsList().data(), item.itemsList().size(), &item.centralFreeItem); d->m_repository.deleteItem(index); } else { //We're fine: The item fits into the existing list. return; } } } else { //We're creating a new index item.itemsList().append(newItem); } Q_ASSERT(!d->m_repository.findIndex(request)); //This inserts the changed item volatile uint newIndex = d->m_repository.index(request); Q_UNUSED(newIndex); ifDebug(qCDebug(LANGUAGE) << "new index" << newIndex; ) Q_ASSERT(d->m_repository.findIndex(request)); } void CodeModel::updateItem(const IndexedString& file, const IndexedQualifiedIdentifier& id, CodeModelItem::Kind kind) { Q_D(CodeModel); ifDebug(qCDebug(LANGUAGE) << file.str() << id.identifier().toString() << kind; ) if (!id.isValid()) return; CodeModelRepositoryItem item; item.file = file; CodeModelRequestItem request(item); CodeModelItem newItem; newItem.id = id; newItem.kind = kind; newItem.referenceCount = 1; uint index = d->m_repository.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item QMutexLocker lock(d->m_repository.mutex()); DynamicItem oldItem = d->m_repository.dynamicItemFromIndex(index); EmbeddedTreeAlgorithms alg(oldItem->items(), oldItem->itemsSize(), oldItem->centralFreeItem); int listIndex = alg.indexOf(newItem); Q_ASSERT(listIndex != -1); CodeModelItem* items = const_cast(oldItem->items()); Q_ASSERT(items[listIndex].id == id); items[listIndex].kind = kind; return; } Q_ASSERT(0); //The updated item as not in the symbol table! } void CodeModel::removeItem(const IndexedString& file, const IndexedQualifiedIdentifier& id) //void CodeModel::removeDeclaration(const QualifiedIdentifier& id, const IndexedDeclaration& declaration) { Q_D(CodeModel); if (!id.isValid()) return; ifDebug(qCDebug(LANGUAGE) << "removeItem" << file.str() << id.identifier().toString(); ) CodeModelRepositoryItem item; item.file = file; CodeModelRequestItem request(item); uint index = d->m_repository.findIndex(item); if (index) { CodeModelItem searchItem; searchItem.id = id; QMutexLocker lock(d->m_repository.mutex()); DynamicItem oldItem = d->m_repository.dynamicItemFromIndex(index); EmbeddedTreeAlgorithms alg(oldItem->items(), oldItem->itemsSize(), oldItem->centralFreeItem); int listIndex = alg.indexOf(searchItem); if (listIndex == -1) return; CodeModelItem* items = const_cast(oldItem->items()); --items[listIndex].referenceCount; if (oldItem->items()[listIndex].referenceCount) return; //Nothing to remove, there's still a reference-count left //We have reduced the reference-count to zero, so remove the item from the list EmbeddedTreeRemoveItem remove(items, oldItem->itemsSize(), oldItem->centralFreeItem, searchItem); uint newItemCount = remove.newItemCount(); if (newItemCount != oldItem->itemsSize()) { if (newItemCount == 0) { //Has become empty, delete the item d->m_repository.deleteItem(index); return; } else { //Make smaller item.itemsList().resize(newItemCount); remove.transferData(item.itemsList().data(), item.itemsSize(), &item.centralFreeItem); //Delete the old list d->m_repository.deleteItem(index); //Add the new list d->m_repository.index(request); return; } } } } void CodeModel::items(const IndexedString& file, uint& count, const CodeModelItem*& items) const { Q_D(const CodeModel); ifDebug(qCDebug(LANGUAGE) << "items" << file.str(); ) CodeModelRepositoryItem item; item.file = file; CodeModelRequestItem request(item); uint index = d->m_repository.findIndex(item); if (index) { const CodeModelRepositoryItem* repositoryItem = d->m_repository.itemFromIndex(index); ifDebug(qCDebug(LANGUAGE) << "found index" << index << repositoryItem->itemsSize(); ) count = repositoryItem->itemsSize(); items = repositoryItem->items(); } else { ifDebug(qCDebug(LANGUAGE) << "found no index"; ) count = 0; items = nullptr; } } CodeModel& CodeModel::self() { static CodeModel ret; return ret; } } diff --git a/kdevplatform/language/duchain/definitions.cpp b/kdevplatform/language/duchain/definitions.cpp index 7c2e6bccf1..b2be4a5a55 100644 --- a/kdevplatform/language/duchain/definitions.cpp +++ b/kdevplatform/language/duchain/definitions.cpp @@ -1,250 +1,252 @@ /* This file is part of KDevelop Copyright 2008 David Nolden Copyright 2014 Kevin Funk 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 "definitions.h" #include "appendedlist.h" #include "declaration.h" #include "declarationid.h" #include "duchainpointer.h" #include #include "serialization/itemrepository.h" namespace KDevelop { DEFINE_LIST_MEMBER_HASH(DefinitionsItem, definitions, IndexedDeclaration) class DefinitionsItem { public: DefinitionsItem() { initializeAppendedLists(); } DefinitionsItem(const DefinitionsItem& rhs, bool dynamic = true) : declaration(rhs.declaration) { initializeAppendedLists(dynamic); copyListsFrom(rhs); } ~DefinitionsItem() { freeAppendedLists(); } + DefinitionsItem& operator=(const DefinitionsItem& rhs) = delete; + unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return declaration.hash(); } unsigned int itemSize() const { return dynamicSize(); } uint classSize() const { return sizeof(DefinitionsItem); } DeclarationId declaration; START_APPENDED_LISTS(DefinitionsItem); APPENDED_LIST_FIRST(DefinitionsItem, IndexedDeclaration, definitions); END_APPENDED_LISTS(DefinitionsItem, definitions); }; class DefinitionsRequestItem { public: DefinitionsRequestItem(const DefinitionsItem& item) : m_item(item) { } enum { AverageSize = 30 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_item.hash(); } uint itemSize() const { return m_item.itemSize(); } void createItem(DefinitionsItem* item) const { new (item) DefinitionsItem(m_item, false); } static void destroy(DefinitionsItem* item, KDevelop::AbstractItemRepository&) { item->~DefinitionsItem(); } static bool persistent(const DefinitionsItem*) { return true; } bool equals(const DefinitionsItem* item) const { return m_item.declaration == item->declaration; } const DefinitionsItem& m_item; }; class DefinitionsVisitor { public: DefinitionsVisitor(Definitions* _definitions, const QTextStream& _out) : definitions(_definitions) , out(_out) { } bool operator()(const DefinitionsItem* item) { QDebug qout(out.device()); auto id = item->declaration; const auto allDefinitions = definitions->definitions(id); qout << "Definitions for" << id.qualifiedIdentifier() << endl; for (const IndexedDeclaration& decl : allDefinitions) { if (decl.data()) { qout << " " << decl.data()->qualifiedIdentifier() << "in" << decl.data()->url().byteArray() << "at" << decl.data()->rangeInCurrentRevision() << endl; } } return true; } private: const Definitions* definitions; const QTextStream& out; }; class DefinitionsPrivate { public: DefinitionsPrivate() : m_definitions(QStringLiteral("Definition Map")) { } //Maps declaration-ids to definitions // mutable as things like findIndex are not const mutable ItemRepository m_definitions; }; Definitions::Definitions() : d_ptr(new DefinitionsPrivate()) { } Definitions::~Definitions() = default; void Definitions::addDefinition(const DeclarationId& id, const IndexedDeclaration& definition) { Q_D(Definitions); DefinitionsItem item; item.declaration = id; item.definitionsList().append(definition); DefinitionsRequestItem request(item); uint index = d->m_definitions.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const DefinitionsItem* oldItem = d->m_definitions.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->definitionsSize(); ++a) { if (oldItem->definitions()[a] == definition) return; //Already there item.definitionsList().append(oldItem->definitions()[a]); } d->m_definitions.deleteItem(index); } //This inserts the changed item d->m_definitions.index(request); } void Definitions::removeDefinition(const DeclarationId& id, const IndexedDeclaration& definition) { Q_D(Definitions); DefinitionsItem item; item.declaration = id; DefinitionsRequestItem request(item); uint index = d->m_definitions.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const DefinitionsItem* oldItem = d->m_definitions.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->definitionsSize(); ++a) if (!(oldItem->definitions()[a] == definition)) item.definitionsList().append(oldItem->definitions()[a]); d->m_definitions.deleteItem(index); Q_ASSERT(d->m_definitions.findIndex(item) == 0); //This inserts the changed item if (item.definitionsSize() != 0) d->m_definitions.index(request); } } KDevVarLengthArray Definitions::definitions(const DeclarationId& id) const { Q_D(const Definitions); KDevVarLengthArray ret; DefinitionsItem item; item.declaration = id; DefinitionsRequestItem request(item); uint index = d->m_definitions.findIndex(item); if (index) { const DefinitionsItem* repositoryItem = d->m_definitions.itemFromIndex(index); FOREACH_FUNCTION(const IndexedDeclaration &decl, repositoryItem->definitions) ret.append(decl); } return ret; } void Definitions::dump(const QTextStream& out) { Q_D(Definitions); QMutexLocker lock(d->m_definitions.mutex()); DefinitionsVisitor v(this, out); d->m_definitions.visitAllItems(v); } } diff --git a/kdevplatform/language/duchain/duchain.cpp b/kdevplatform/language/duchain/duchain.cpp index 8cacabc95b..f902248e8c 100644 --- a/kdevplatform/language/duchain/duchain.cpp +++ b/kdevplatform/language/duchain/duchain.cpp @@ -1,1878 +1,1880 @@ /* This is part of KDevelop Copyright 2006-2008 Hamish Rodda Copyright 2007-2008 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 "duchain.h" #include "duchainlock.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "../interfaces/ilanguagesupport.h" #include "../interfaces/icodehighlighting.h" #include "../backgroundparser/backgroundparser.h" #include #include "language-features.h" #include "topducontext.h" #include "topducontextdata.h" #include "topducontextdynamicdata.h" #include "parsingenvironment.h" #include "declaration.h" #include "definitions.h" #include "duchainutils.h" #include "use.h" #include "uses.h" #include "abstractfunctiondeclaration.h" #include "duchainregister.h" #include "persistentsymboltable.h" #include "serialization/itemrepository.h" #include "waitforupdate.h" #include "importers.h" #if HAVE_MALLOC_TRIM #include "malloc.h" #endif namespace { //Additional "soft" cleanup steps that are done before the actual cleanup. //During "soft" cleanup, the consistency is not guaranteed. The repository is //marked to be updating during soft cleanup, so if kdevelop crashes, it will be cleared. //The big advantage of the soft cleanup steps is, that the duchain is always only locked for //short times, which leads to no lockup in the UI. const int SOFT_CLEANUP_STEPS = 1; // seconds to wait before trying to cleanup the DUChain const uint cleanupEverySeconds = 200; ///Approximate maximum count of top-contexts that are checked during final cleanup const uint maxFinalCleanupCheckContexts = 2000; const uint minimumFinalCleanupCheckContextsPercentage = 10; //Check at least n% of all top-contexts during cleanup //Set to true as soon as the duchain is deleted } namespace KDevelop { bool DUChain::m_deleted = false; ///Must be locked through KDevelop::SpinLock before using chainsByIndex ///This lock should be locked only for very short times QMutex DUChain::chainsByIndexLock; std::vector DUChain::chainsByIndex; //This thing is not actually used, but it's needed for compiling DEFINE_LIST_MEMBER_HASH(EnvironmentInformationListItem, items, uint) //An entry for the item-repository that holds some meta-data. Behind this entry, the actual ParsingEnvironmentFileData is stored. class EnvironmentInformationItem { public: EnvironmentInformationItem(uint topContext, uint size) : m_topContext(topContext) , m_size(size) { } ~EnvironmentInformationItem() { } + EnvironmentInformationItem& operator=(const EnvironmentInformationItem& rhs) = delete; + unsigned int hash() const { return m_topContext; } unsigned int itemSize() const { return sizeof(*this) + m_size; } uint m_topContext; uint m_size;//Size of the data behind, that holds the actual item }; struct ItemRepositoryIndexHash { uint operator()(unsigned int __x) const { return 173 * (__x >> 2) + 11 * (__x >> 16); } }; class EnvironmentInformationRequest { public: ///This constructor should only be used for lookup EnvironmentInformationRequest(uint topContextIndex) : m_file(nullptr) , m_index(topContextIndex) { } EnvironmentInformationRequest(const ParsingEnvironmentFile* file) : m_file(file) , m_index(file->indexedTopContext().index()) { } enum { AverageSize = 32 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_index; } uint itemSize() const { return sizeof(EnvironmentInformationItem) + DUChainItemSystem::self().dynamicSize(*m_file->d_func()); } void createItem(EnvironmentInformationItem* item) const { new (item) EnvironmentInformationItem(m_index, DUChainItemSystem::self().dynamicSize(*m_file->d_func())); Q_ASSERT(m_file->d_func()->m_dynamic); DUChainBaseData* data = reinterpret_cast(reinterpret_cast(item) + sizeof(EnvironmentInformationItem)); DUChainItemSystem::self().copy(*m_file->d_func(), *data, true); Q_ASSERT(data->m_range == m_file->d_func()->m_range); Q_ASSERT(data->classId == m_file->d_func()->classId); Q_ASSERT(data->m_dynamic == false); } static void destroy(EnvironmentInformationItem* item, KDevelop::AbstractItemRepository&) { item->~EnvironmentInformationItem(); //We don't need to call the destructor, because that's done in DUChainBase::makeDynamic() //We just need to make sure that every environment-file is dynamic when it's deleted // DUChainItemSystem::self().callDestructor((DUChainBaseData*)(((char*)item) + sizeof(EnvironmentInformationItem))); } static bool persistent(const EnvironmentInformationItem*) { //Cleanup done separately return true; } bool equals(const EnvironmentInformationItem* item) const { return m_index == item->m_topContext; } const ParsingEnvironmentFile* m_file; uint m_index; }; ///A list of environment-information/top-contexts mapped to a file-name class EnvironmentInformationListItem { public: EnvironmentInformationListItem() { initializeAppendedLists(true); } EnvironmentInformationListItem(const EnvironmentInformationListItem& rhs, bool dynamic = true) { initializeAppendedLists(dynamic); m_file = rhs.m_file; copyListsFrom(rhs); } ~EnvironmentInformationListItem() { freeAppendedLists(); } EnvironmentInformationListItem& operator=(const EnvironmentInformationListItem& rhs) = delete; unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return m_file.hash(); } unsigned short int itemSize() const { return dynamicSize(); } IndexedString m_file; uint classSize() const { return sizeof(*this); } START_APPENDED_LISTS(EnvironmentInformationListItem); ///Contains the index of each contained environment-item APPENDED_LIST_FIRST(EnvironmentInformationListItem, uint, items); END_APPENDED_LISTS(EnvironmentInformationListItem, items); }; class EnvironmentInformationListRequest { public: ///This constructor should only be used for lookup EnvironmentInformationListRequest(const IndexedString& file) : m_file(file) , m_item(nullptr) { } ///This is used to actually construct the information in the repository EnvironmentInformationListRequest(const IndexedString& file, const EnvironmentInformationListItem& item) : m_file( file) , m_item(&item) { } enum { AverageSize = 160 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_file.hash(); } uint itemSize() const { return m_item->itemSize(); } void createItem(EnvironmentInformationListItem* item) const { Q_ASSERT(m_item->m_file == m_file); new (item) EnvironmentInformationListItem(*m_item, false); } static void destroy(EnvironmentInformationListItem* item, KDevelop::AbstractItemRepository&) { item->~EnvironmentInformationListItem(); } static bool persistent(const EnvironmentInformationListItem*) { //Cleanup is done separately return true; } bool equals(const EnvironmentInformationListItem* item) const { return m_file == item->m_file; } IndexedString m_file; const EnvironmentInformationListItem* m_item; }; class DUChainPrivate; static DUChainPrivate* duChainPrivateSelf = nullptr; class DUChainPrivate { class CleanupThread : public QThread { public: explicit CleanupThread(DUChainPrivate* data) : m_data(data) { } void stopThread() { quit(); wait(); } private: void run() override { QTimer timer; connect(&timer, &QTimer::timeout, &timer, [this]() { Q_ASSERT(QThread::currentThread() == this); //Just to make sure the cache is cleared periodically ModificationRevisionSet::clearCache(); m_data->doMoreCleanup(SOFT_CLEANUP_STEPS, TryLock); }); timer.start(cleanupEverySeconds * 1000); exec(); } DUChainPrivate* m_data; }; public: DUChainPrivate() : m_chainsMutex(QMutex::Recursive) , m_cleanupMutex(QMutex::Recursive) , instance(nullptr) , m_cleanupDisabled(false) , m_destroyed(false) , m_environmentListInfo(QStringLiteral("Environment Lists")) , m_environmentInfo(QStringLiteral("Environment Information")) { #if defined(TEST_NO_CLEANUP) m_cleanupDisabled = true; #endif duChainPrivateSelf = this; qRegisterMetaType("KDevelop::DUChainBasePointer"); qRegisterMetaType("KDevelop::DUContextPointer"); qRegisterMetaType("KDevelop::TopDUContextPointer"); qRegisterMetaType("KDevelop::DeclarationPointer"); qRegisterMetaType("KDevelop::FunctionDeclarationPointer"); qRegisterMetaType("KDevelop::IndexedString"); qRegisterMetaType("KDevelop::IndexedTopDUContext"); qRegisterMetaType("KDevelop::ReferencedTopDUContext"); instance = new DUChain(); m_cleanup = new CleanupThread(this); m_cleanup->start(); DUChain::m_deleted = false; ///Loading of some static data: { ///@todo Solve this more duchain-like QFile f(globalItemRepositoryRegistry().path() + QLatin1String("/parsing_environment_data")); bool opened = f.open(QIODevice::ReadOnly); ///FIXME: ugh, so ugly ParsingEnvironmentFile::m_staticData = reinterpret_cast(new char[sizeof(StaticParsingEnvironmentData)]); if (opened) { qCDebug(LANGUAGE) << "reading parsing-environment static data"; //Read f.read(( char* )ParsingEnvironmentFile::m_staticData, sizeof(StaticParsingEnvironmentData)); } else { qCDebug(LANGUAGE) << "creating new parsing-environment static data"; //Initialize new (ParsingEnvironmentFile::m_staticData) StaticParsingEnvironmentData(); } } ///Read in the list of available top-context indices { QFile f(globalItemRepositoryRegistry().path() + QLatin1String("/available_top_context_indices")); bool opened = f.open(QIODevice::ReadOnly); if (opened) { Q_ASSERT((f.size() % sizeof(uint)) == 0); m_availableTopContextIndices.resize(f.size() / ( int )sizeof(uint)); f.read(( char* )m_availableTopContextIndices.data(), f.size()); } } } ~DUChainPrivate() { qCDebug(LANGUAGE) << "Destroying"; DUChain::m_deleted = true; m_cleanup->stopThread(); delete m_cleanup; delete instance; } void clear() { if (!m_cleanupDisabled) doMoreCleanup(); DUChainWriteLocker writeLock(DUChain::lock()); QMutexLocker l(&m_chainsMutex); const auto currentChainsByUrl = m_chainsByUrl; for (TopDUContext* top : currentChainsByUrl) { removeDocumentChainFromMemory(top); } m_indexEnvironmentInformations.clear(); m_fileEnvironmentInformations.clear(); Q_ASSERT(m_fileEnvironmentInformations.isEmpty()); Q_ASSERT(m_chainsByUrl.isEmpty()); } ///DUChain must be write-locked ///Also removes from the environment-manager if the top-context is not on disk void removeDocumentChainFromMemory(TopDUContext* context) { QMutexLocker l(&m_chainsMutex); { QMutexLocker l(&m_referenceCountsMutex); auto countIt = m_referenceCounts.constFind(context); if (countIt != m_referenceCounts.constEnd()) { //This happens during shutdown, since everything is unloaded qCDebug(LANGUAGE) << "removed a top-context that was reference-counted:" << context->url().str() << context->ownIndex(); m_referenceCounts.erase(countIt); } } uint index = context->ownIndex(); // qCDebug(LANGUAGE) << "duchain: removing document" << context->url().str(); Q_ASSERT(hasChainForIndex(index)); Q_ASSERT(m_chainsByUrl.contains(context->url(), context)); m_chainsByUrl.remove(context->url(), context); if (!context->isOnDisk()) instance->removeFromEnvironmentManager(context); l.unlock(); //DUChain is write-locked, so we can do whatever we want on the top-context, including deleting it context->deleteSelf(); l.relock(); Q_ASSERT(hasChainForIndex(index)); QMutexLocker lock(&DUChain::chainsByIndexLock); DUChain::chainsByIndex[index] = nullptr; } ///Must be locked before accessing content of this class. ///Should be released during expensive disk-operations and such. QMutex m_chainsMutex; QMutex m_cleanupMutex; CleanupThread* m_cleanup; DUChain* instance; DUChainLock lock; QMultiMap m_chainsByUrl; //Must be locked before accessing m_referenceCounts QMutex m_referenceCountsMutex; QHash m_referenceCounts; Definitions m_definitions; Uses m_uses; QSet m_loading; bool m_cleanupDisabled; //List of available top-context indices, protected by m_chainsMutex QVector m_availableTopContextIndices; ///Used to keep alive the top-context that belong to documents loaded in the editor QSet m_openDocumentContexts; bool m_destroyed; ///The item must not be stored yet ///m_chainsMutex should not be locked, since this can trigger I/O void addEnvironmentInformation(ParsingEnvironmentFilePointer info) { Q_ASSERT(!findInformation(info->indexedTopContext().index())); Q_ASSERT(m_environmentInfo.findIndex(info->indexedTopContext().index()) == 0); QMutexLocker lock(&m_chainsMutex); m_fileEnvironmentInformations.insert(info->url(), info); m_indexEnvironmentInformations.insert(info->indexedTopContext().index(), info); Q_ASSERT(info->d_func()->classId); } ///The item must be managed currently ///m_chainsMutex does not need to be locked void removeEnvironmentInformation(ParsingEnvironmentFilePointer info) { info->makeDynamic(); //By doing this, we make sure the data is actually being destroyed in the destructor bool removed = false; bool removed2 = false; { QMutexLocker lock(&m_chainsMutex); removed = m_fileEnvironmentInformations.remove(info->url(), info); removed2 = m_indexEnvironmentInformations.remove(info->indexedTopContext().index()); } { //Remove it from the environment information lists if it was there QMutexLocker lock(m_environmentListInfo.mutex()); uint index = m_environmentListInfo.findIndex(info->url()); if (index) { EnvironmentInformationListItem item(*m_environmentListInfo.itemFromIndex(index)); if (item.itemsList().removeOne(info->indexedTopContext().index())) { m_environmentListInfo.deleteItem(index); if (!item.itemsList().isEmpty()) m_environmentListInfo.index(EnvironmentInformationListRequest(info->url(), item)); } } } QMutexLocker lock(m_environmentInfo.mutex()); uint index = m_environmentInfo.findIndex(info->indexedTopContext().index()); if (index) { m_environmentInfo.deleteItem(index); } Q_UNUSED(removed); Q_UNUSED(removed2); Q_ASSERT(index || (removed && removed2)); Q_ASSERT(!findInformation(info->indexedTopContext().index())); } ///m_chainsMutex should _not_ be locked, because this may trigger I/O QList getEnvironmentInformation(const IndexedString& url) { QList ret; uint listIndex = m_environmentListInfo.findIndex(url); if (listIndex) { KDevVarLengthArray topContextIndices; { //First store all the possible indices into the KDevVarLengthArray, so we can unlock the mutex before processing them. QMutexLocker lock(m_environmentListInfo.mutex()); //Lock the mutex to make sure the item isn't changed while it's being iterated const EnvironmentInformationListItem* item = m_environmentListInfo.itemFromIndex(listIndex); FOREACH_FUNCTION(uint topContextIndex, item->items) topContextIndices << topContextIndex; } //Process the indices in a separate step after copying them from the array, so we don't need m_environmentListInfo.mutex locked, //and can call loadInformation(..) safely, which else might lead to a deadlock. for (uint topContextIndex : qAsConst(topContextIndices)) { QExplicitlySharedDataPointer p = ParsingEnvironmentFilePointer(loadInformation(topContextIndex)); if (p) { ret << p; } else { qCDebug(LANGUAGE) << "Failed to load environment-information for" << TopDUContextDynamicData::loadUrl(topContextIndex).str(); } } } QMutexLocker l(&m_chainsMutex); //Add those information that have not been added to the stored lists yet const auto files = m_fileEnvironmentInformations.values(url); for (const ParsingEnvironmentFilePointer& file : files) { if (!ret.contains(file)) ret << file; } return ret; } ///Must be called _without_ the chainsByIndex spin-lock locked static inline bool hasChainForIndex(uint index) { QMutexLocker lock(&DUChain::chainsByIndexLock); return (DUChain::chainsByIndex.size() > index) && DUChain::chainsByIndex[index]; } ///Must be called _without_ the chainsByIndex spin-lock locked. Returns the top-context if it is loaded. static inline TopDUContext* readChainForIndex(uint index) { QMutexLocker lock(&DUChain::chainsByIndexLock); if (DUChain::chainsByIndex.size() > index) return DUChain::chainsByIndex[index]; else return nullptr; } ///Makes sure that the chain with the given index is loaded ///@warning m_chainsMutex must NOT be locked when this is called void loadChain(uint index, QSet& loaded) { QMutexLocker l(&m_chainsMutex); if (!hasChainForIndex(index)) { if (m_loading.contains(index)) { //It's probably being loaded by another thread. So wait until the load is ready while (m_loading.contains(index)) { l.unlock(); qCDebug(LANGUAGE) << "waiting for another thread to load index" << index; QThread::usleep(50000); l.relock(); } loaded.insert(index); return; } m_loading.insert(index); loaded.insert(index); l.unlock(); qCDebug(LANGUAGE) << "loading top-context" << index; TopDUContext* chain = TopDUContextDynamicData::load(index); if (chain) { chain->setParsingEnvironmentFile(loadInformation(chain->ownIndex())); if (!chain->usingImportsCache()) { //Eventually also load all the imported chains, so the import-structure is built const auto importedParentContexts = chain->DUContext::importedParentContexts(); for (const DUContext::Import& import : importedParentContexts) { if (!loaded.contains(import.topContextIndex())) { loadChain(import.topContextIndex(), loaded); } } } chain->rebuildDynamicImportStructure(); chain->setInDuChain(true); instance->addDocumentChain(chain); } l.relock(); m_loading.remove(index); } } ///Stores all environment-information ///Also makes sure that all information that stays is referenced, so it stays alive. ///@param atomic If this is false, the write-lock will be released time by time void storeAllInformation(bool atomic, DUChainWriteLocker& locker) { uint cnt = 0; QList urls; { QMutexLocker lock(&m_chainsMutex); urls += m_fileEnvironmentInformations.keys(); } for (const IndexedString& url : qAsConst(urls)) { QList check; { QMutexLocker lock(&m_chainsMutex); check = m_fileEnvironmentInformations.values(url); } for (const ParsingEnvironmentFilePointer& file : qAsConst(check)) { EnvironmentInformationRequest req(file.data()); QMutexLocker lock(m_environmentInfo.mutex()); uint index = m_environmentInfo.findIndex(req); if (file->d_func()->isDynamic()) { //This item has been changed, or isn't in the repository yet //Eventually remove an old entry if (index) m_environmentInfo.deleteItem(index); //Add the new entry to the item repository index = m_environmentInfo.index(req); Q_ASSERT(index); EnvironmentInformationItem* item = const_cast(m_environmentInfo.itemFromIndex(index)); DUChainBaseData* theData = reinterpret_cast(reinterpret_cast(item) + sizeof(EnvironmentInformationItem)); Q_ASSERT(theData->m_range == file->d_func()->m_range); Q_ASSERT(theData->m_dynamic == false); Q_ASSERT(theData->classId == file->d_func()->classId); file->setData(theData); ++cnt; } else { m_environmentInfo.itemFromIndex(index); //Prevent unloading of the data, by accessing the item } } ///We must not release the lock while holding a reference to a ParsingEnvironmentFilePointer, else we may miss the deletion of an ///information, and will get crashes. if (!atomic && (cnt % 100 == 0)) { //Release the lock on a regular basis locker.unlock(); locker.lock(); } storeInformationList(url); //Access the data in the repository, so the bucket isn't unloaded uint index = m_environmentListInfo.findIndex(EnvironmentInformationListRequest(url)); if (index) { m_environmentListInfo.itemFromIndex(index); } else { QMutexLocker lock(&m_chainsMutex); qCDebug(LANGUAGE) << "Did not find stored item for" << url.str() << "count:" << m_fileEnvironmentInformations.values(url); } if (!atomic) { locker.unlock(); locker.lock(); } } } QMutex& cleanupMutex() { return m_cleanupMutex; } /// defines how we interact with the ongoing language parse jobs enum LockFlag { /// no locking required, only used when we locked previously NoLock = 0, /// lock all parse jobs and block until we succeeded. required at shutdown BlockingLock = 1, /// only try to lock and abort on failure, good for the intermittent cleanups TryLock = 2, }; ///@param retries When this is nonzero, then doMoreCleanup will do the specified amount of cycles ///doing the cleanup without permanently locking the du-chain. During these steps the consistency ///of the disk-storage is not guaranteed, but only few changes will be done during these steps, ///so the final step where the duchain is permanently locked is much faster. void doMoreCleanup(int retries = 0, LockFlag lockFlag = BlockingLock) { if (m_cleanupDisabled) return; //This mutex makes sure that there's never 2 threads at he same time trying to clean up QMutexLocker lockCleanupMutex(&cleanupMutex()); if (m_destroyed || m_cleanupDisabled) return; Q_ASSERT(!instance->lock()->currentThreadHasReadLock() && !instance->lock()->currentThreadHasWriteLock()); DUChainWriteLocker writeLock(instance->lock()); //This is used to stop all parsing before starting to do the cleanup. This way less happens during the //soft cleanups, and we have a good chance that during the "hard" cleanup only few data has to be written. QList locked; if (lockFlag != NoLock) { QList languages; if (ICore* core = ICore::self()) if (ILanguageController* lc = core->languageController()) languages = lc->loadedLanguages(); writeLock.unlock(); //Here we wait for all parsing-threads to stop their processing for (const auto language : qAsConst(languages)) { if (lockFlag == TryLock) { if (!language->parseLock()->tryLockForWrite()) { qCDebug(LANGUAGE) << "Aborting cleanup because language plugin is still parsing:" << language->name(); // some language is still parsing, don't interfere with the cleanup for (auto* lock : qAsConst(locked)) { lock->unlock(); } return; } } else { language->parseLock()->lockForWrite(); } locked << language->parseLock(); } writeLock.lock(); globalItemRepositoryRegistry().lockForWriting(); qCDebug(LANGUAGE) << "starting cleanup"; } QTime startTime = QTime::currentTime(); PersistentSymbolTable::self().clearCache(); storeAllInformation(!retries, writeLock); //Puts environment-information into a repository //We don't need to increase the reference-count, since the cleanup-mutex is locked QSet workOnContexts; { QMutexLocker l(&m_chainsMutex); workOnContexts.reserve(m_chainsByUrl.size()); for (TopDUContext* top : qAsConst(m_chainsByUrl)) { workOnContexts << top; Q_ASSERT(hasChainForIndex(top->ownIndex())); } } for (TopDUContext* context : qAsConst(workOnContexts)) { context->m_dynamicData->store(); if (retries) { //Eventually give other threads a chance to access the duchain writeLock.unlock(); //Sleep to give the other threads a realistic chance to get a read-lock in between QThread::usleep(500); writeLock.lock(); } } //Unload all top-contexts that don't have a reference-count and that are not imported by a referenced one QSet unloadedNames; bool unloadedOne = true; bool unloadAllUnreferenced = !retries; //Now unload contexts, but only ones that are not imported by any other currently loaded context //The complication: Since during the lock-break new references may be added, we must never keep //the du-chain in an invalid state. Thus we can only unload contexts that are not imported by any //currently loaded contexts. In case of loops, we have to unload everything at once. while (unloadedOne) { unloadedOne = false; int hadUnloadable = 0; unloadContexts: const auto currentWorkOnContexts = workOnContexts; for (TopDUContext * unload : currentWorkOnContexts) { bool hasReference = false; { QMutexLocker l(&m_referenceCountsMutex); //Test if the context is imported by a referenced one for (auto it = m_referenceCounts.constBegin(), end = m_referenceCounts.constEnd(); it != end; ++it) { auto* context = it.key(); if (context == unload || context->imports(unload, CursorInRevision())) { workOnContexts.remove(unload); hasReference = true; } } } if (!hasReference) ++hadUnloadable; //We have found a context that is not referenced else continue; //This context is referenced bool isImportedByLoaded = !unload->loadedImporters().isEmpty(); //If we unload a context that is imported by other contexts, we create a bad loaded state if (isImportedByLoaded && !unloadAllUnreferenced) continue; unloadedNames.insert(unload->url()); //Since we've released the write-lock in between, we've got to call store() again to be sure that none of the data is dynamic //If nothing has changed, it is only a low-cost call. unload->m_dynamicData->store(); Q_ASSERT(!unload->d_func()->m_dynamic); removeDocumentChainFromMemory(unload); workOnContexts.remove(unload); unloadedOne = true; if (!unloadAllUnreferenced) { //Eventually give other threads a chance to access the duchain writeLock.unlock(); //Sleep to give the other threads a realistic chance to get a read-lock in between QThread::usleep(500); writeLock.lock(); } } if (hadUnloadable && !unloadedOne) { Q_ASSERT(!unloadAllUnreferenced); //This can happen in case of loops. We have o unload everything at one time. qCDebug(LANGUAGE) << "found" << hadUnloadable << "unloadable contexts, but could not unload separately. Unloading atomically."; unloadAllUnreferenced = true; hadUnloadable = 0; //Reset to 0, so we cannot loop forever goto unloadContexts; } } if (retries == 0) { QMutexLocker lock(&m_chainsMutex); //Do this atomically, since we must be sure that _everything_ is already saved for (QMultiMap::iterator it = m_fileEnvironmentInformations.begin(); it != m_fileEnvironmentInformations.end();) { ParsingEnvironmentFile* f = it->data(); Q_ASSERT(f->d_func()->classId); if (f->ref.load() == 1) { Q_ASSERT(!f->d_func()->isDynamic()); //It cannot be dynamic, since we have stored before //The ParsingEnvironmentFilePointer is only referenced once. This means that it does not belong to any //loaded top-context, so just remove it to save some memory and processing time. ///@todo use some kind of timeout before removing it = m_fileEnvironmentInformations.erase(it); } else { ++it; } } } if (retries) writeLock.unlock(); //This must be the last step, due to the on-disk reference counting globalItemRepositoryRegistry().store(); //Stores all repositories { //Store the static parsing-environment file data ///@todo Solve this more elegantly, using a general mechanism to store static duchain-like data Q_ASSERT(ParsingEnvironmentFile::m_staticData); QFile f(globalItemRepositoryRegistry().path() + QLatin1String("/parsing_environment_data")); bool opened = f.open(QIODevice::WriteOnly); Q_ASSERT(opened); Q_UNUSED(opened); f.write(( char* )ParsingEnvironmentFile::m_staticData, sizeof(StaticParsingEnvironmentData)); } ///Write out the list of available top-context indices { QMutexLocker lock(&m_chainsMutex); QFile f(globalItemRepositoryRegistry().path() + QLatin1String("/available_top_context_indices")); bool opened = f.open(QIODevice::WriteOnly); Q_ASSERT(opened); Q_UNUSED(opened); f.write(( char* )m_availableTopContextIndices.data(), m_availableTopContextIndices.size() * sizeof(uint)); } if (retries) { doMoreCleanup(retries - 1, NoLock); writeLock.lock(); } if (lockFlag != NoLock) { globalItemRepositoryRegistry().unlockForWriting(); const auto elapsedMS = startTime.msecsTo(QTime::currentTime()); qCDebug(LANGUAGE) << "time spent doing cleanup:" << elapsedMS << "ms - top-contexts still open:" << m_chainsByUrl.size() << "- retries" << retries; } for (QReadWriteLock* lock : qAsConst(locked)) { lock->unlock(); } #if HAVE_MALLOC_TRIM // trim unused memory but keep a pad buffer of about 50 MB // this can greatly decrease the perceived memory consumption of kdevelop // see: https://sourceware.org/bugzilla/show_bug.cgi?id=14827 malloc_trim(50 * 1024 * 1024); #endif } ///Checks whether the information is already loaded. ParsingEnvironmentFile* findInformation(uint topContextIndex) { QMutexLocker lock(&m_chainsMutex); QHash::iterator it = m_indexEnvironmentInformations.find(topContextIndex); if (it != m_indexEnvironmentInformations.end()) return (*it).data(); return nullptr; } ///Loads/gets the environment-information for the given top-context index, or returns zero if none exists ///@warning m_chainsMutex should NOT be locked when this is called, because it triggers I/O ///@warning no other mutexes should be locked, as that may lead to a dedalock ParsingEnvironmentFile* loadInformation(uint topContextIndex) { ParsingEnvironmentFile* alreadyLoaded = findInformation(topContextIndex); if (alreadyLoaded) return alreadyLoaded; //Step two: Check if it is on disk, and if is, load it uint dataIndex = m_environmentInfo.findIndex(EnvironmentInformationRequest(topContextIndex)); if (!dataIndex) { //No environment-information stored for this top-context return nullptr; } const EnvironmentInformationItem& item(*m_environmentInfo.itemFromIndex(dataIndex)); QMutexLocker lock(&m_chainsMutex); //Due to multi-threading, we must do this check after locking the mutex, so we can be sure we don't create the same item twice at the same time alreadyLoaded = findInformation(topContextIndex); if (alreadyLoaded) return alreadyLoaded; ///FIXME: ugly, and remove const_cast ParsingEnvironmentFile* ret = dynamic_cast(DUChainItemSystem::self().create( const_cast( reinterpret_cast( reinterpret_cast(& item) + sizeof( EnvironmentInformationItem))) )); if (ret) { Q_ASSERT(ret->d_func()->classId); Q_ASSERT(ret->indexedTopContext().index() == topContextIndex); ParsingEnvironmentFilePointer retPtr(ret); m_fileEnvironmentInformations.insert(ret->url(), retPtr); Q_ASSERT(!m_indexEnvironmentInformations.contains(ret->indexedTopContext().index())); m_indexEnvironmentInformations.insert(ret->indexedTopContext().index(), retPtr); } return ret; } struct CleanupListVisitor { QList checkContexts; bool operator()(const EnvironmentInformationItem* item) { checkContexts << item->m_topContext; return true; } }; ///Will check a selection of all top-contexts for up-to-date ness, and remove them if out of date void cleanupTopContexts() { DUChainWriteLocker lock(DUChain::lock()); qCDebug(LANGUAGE) << "cleaning top-contexts"; CleanupListVisitor visitor; uint startPos = 0; m_environmentInfo.visitAllItems(visitor); int checkContextsCount = maxFinalCleanupCheckContexts; int percentageOfContexts = (visitor.checkContexts.size() * 100) / minimumFinalCleanupCheckContextsPercentage; if (checkContextsCount < percentageOfContexts) checkContextsCount = percentageOfContexts; if (visitor.checkContexts.size() > ( int )checkContextsCount) startPos = qrand() % (visitor.checkContexts.size() - checkContextsCount); int endPos = startPos + maxFinalCleanupCheckContexts; if (endPos > visitor.checkContexts.size()) endPos = visitor.checkContexts.size(); QSet check; for (int a = startPos; a < endPos && check.size() < checkContextsCount; ++a) if (check.size() < checkContextsCount) addContextsForRemoval(check, IndexedTopDUContext(visitor.checkContexts[a])); for (uint topIndex : qAsConst(check)) { IndexedTopDUContext top(topIndex); if (top.data()) { qCDebug(LANGUAGE) << "removing top-context for" << top.data()->url().str() << "because it is out of date"; instance->removeDocumentChain(top.data()); } } qCDebug(LANGUAGE) << "check ready"; } private: void addContextsForRemoval(QSet& topContexts, IndexedTopDUContext top) { if (topContexts.contains(top.index())) return; QExplicitlySharedDataPointer info(instance->environmentFileForDocument(top)); ///@todo Also check if the context is "useful"(Not a duplicate context, imported by a useful one, ...) if (info && info->needsUpdate()) { //This context will be removed } else { return; } topContexts.insert(top.index()); if (info) { //Check whether importers need to be removed as well QList> importers = info->importers(); QSet> checkNext; //Do breadth first search, so less imports/importers have to be loaded, and a lower depth is reached for (QList>::iterator it = importers.begin(); it != importers.end(); ++it) { IndexedTopDUContext c = (*it)->indexedTopContext(); if (!topContexts.contains(c.index())) { topContexts.insert(c.index()); //Prevent useless recursion checkNext.insert(*it); } } for (auto& parsingEnvFile : qAsConst(checkNext)) { topContexts.remove(parsingEnvFile->indexedTopContext().index()); // Enable full check again addContextsForRemoval(topContexts, parsingEnvFile->indexedTopContext()); } } } ///Stores the environment-information for the given url void storeInformationList(const IndexedString& url) { QMutexLocker lock(m_environmentListInfo.mutex()); EnvironmentInformationListItem newItem; newItem.m_file = url; QSet newItems; { QMutexLocker lock(&m_chainsMutex); QMultiMap::iterator start = m_fileEnvironmentInformations.lowerBound(url); QMultiMap::iterator end = m_fileEnvironmentInformations.upperBound(url); for (QMultiMap::iterator it = start; it != end; ++it) { uint topContextIndex = (*it)->indexedTopContext().index(); newItems.insert(topContextIndex); newItem.itemsList().append(topContextIndex); } } uint index = m_environmentListInfo.findIndex(url); if (index) { //We only handle adding items here, since we can never be sure whether everything is loaded //Removal is handled directly in removeEnvironmentInformation const EnvironmentInformationListItem* item = m_environmentListInfo.itemFromIndex(index); QSet oldItems; FOREACH_FUNCTION(uint topContextIndex, item->items) { oldItems.insert(topContextIndex); if (!newItems.contains(topContextIndex)) { newItems.insert(topContextIndex); newItem.itemsList().append(topContextIndex); } } if (oldItems == newItems) return; ///Update/insert a new list m_environmentListInfo.deleteItem(index); //Remove the previous item } Q_ASSERT(m_environmentListInfo.findIndex(EnvironmentInformationListRequest(url)) == 0); //Insert the new item m_environmentListInfo.index(EnvironmentInformationListRequest(url, newItem)); Q_ASSERT(m_environmentListInfo.findIndex(EnvironmentInformationListRequest(url))); } //Loaded environment information. Protected by m_chainsMutex QMultiMap m_fileEnvironmentInformations; QHash m_indexEnvironmentInformations; ///The following repositories are thread-safe, and m_chainsMutex should not be locked when using them, because ///they may trigger I/O. Still it may be required to lock their local mutexes. ///Maps filenames to a list of top-contexts/environment-information. ItemRepository m_environmentListInfo; ///Maps top-context-indices to environment-information item. ItemRepository m_environmentInfo; }; Q_GLOBAL_STATIC(DUChainPrivate, sdDUChainPrivate) DUChain::DUChain() { Q_ASSERT(ICore::self()); connect( ICore::self()->documentController(), &IDocumentController::documentLoadedPrepare, this, &DUChain::documentLoadedPrepare); connect( ICore::self()->documentController(), &IDocumentController::documentUrlChanged, this, &DUChain::documentRenamed); connect( ICore::self()->documentController(), &IDocumentController::documentActivated, this, &DUChain::documentActivated); connect(ICore::self()->documentController(), &IDocumentController::documentClosed, this, &DUChain::documentClosed); } DUChain::~DUChain() { DUChain::m_deleted = true; } DUChain* DUChain::self() { return sdDUChainPrivate->instance; } extern void initModificationRevisionSetRepository(); extern void initDeclarationRepositories(); extern void initIdentifierRepository(); extern void initTypeRepository(); extern void initInstantiationInformationRepository(); QString DUChain::repositoryPathForSession(const KDevelop::ISessionLock::Ptr& session) { QString cacheDir = QStandardPaths::writableLocation(QStandardPaths::GenericCacheLocation); cacheDir += QStringLiteral("/kdevduchain"); QString baseDir = QProcessEnvironment::systemEnvironment().value(QStringLiteral("KDEV_DUCHAIN_DIR"), cacheDir); baseDir += QStringLiteral("/%1-%2").arg(qApp->applicationName(), session->id()); return baseDir; } void DUChain::initialize() { // Initialize the global item repository as first thing after loading the session Q_ASSERT(ICore::self()); Q_ASSERT(ICore::self()->activeSession()); ItemRepositoryRegistry::initialize(repositoryPathForSession(ICore::self()->activeSessionLock())); initReferenceCounting(); // This needs to be initialized here too as the function is not threadsafe, but can // sometimes be called from different threads. This results in the underlying QFile // being 0 and hence crashes at some point later when accessing the contents via // read. See https://bugs.kde.org/show_bug.cgi?id=250779 RecursiveImportRepository::repository(); RecursiveImportCacheRepository::repository(); // similar to above, see https://bugs.kde.org/show_bug.cgi?id=255323 initDeclarationRepositories(); initModificationRevisionSetRepository(); initIdentifierRepository(); initTypeRepository(); initInstantiationInformationRepository(); Importers::self(); globalImportIdentifier(); globalIndexedImportIdentifier(); globalAliasIdentifier(); globalIndexedAliasIdentifier(); } DUChainLock* DUChain::lock() { return &sdDUChainPrivate->lock; } QList DUChain::allChains() const { QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); return sdDUChainPrivate->m_chainsByUrl.values(); } void DUChain::updateContextEnvironment(TopDUContext* context, ParsingEnvironmentFile* file) { QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); removeFromEnvironmentManager(context); context->setParsingEnvironmentFile(file); addToEnvironmentManager(context); } void DUChain::removeDocumentChain(TopDUContext* context) { ENSURE_CHAIN_WRITE_LOCKED; IndexedTopDUContext indexed(context->indexed()); Q_ASSERT(indexed.data() == context); ///This assertion fails if you call removeDocumentChain(..) on a document that has not been added to the du-chain context->m_dynamicData->deleteOnDisk(); Q_ASSERT(indexed.data() == context); sdDUChainPrivate->removeDocumentChainFromMemory(context); Q_ASSERT(!indexed.data()); Q_ASSERT(!environmentFileForDocument(indexed)); QMutexLocker lock(&sdDUChainPrivate->m_chainsMutex); sdDUChainPrivate->m_availableTopContextIndices.push_back(indexed.index()); } void DUChain::addDocumentChain(TopDUContext* chain) { QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); // qCDebug(LANGUAGE) << "duchain: adding document" << chain->url().str() << " " << chain; Q_ASSERT(chain); Q_ASSERT(!sdDUChainPrivate->hasChainForIndex(chain->ownIndex())); { QMutexLocker lock(&DUChain::chainsByIndexLock); if (DUChain::chainsByIndex.size() <= chain->ownIndex()) DUChain::chainsByIndex.resize(chain->ownIndex() + 100, nullptr); DUChain::chainsByIndex[chain->ownIndex()] = chain; } { Q_ASSERT(DUChain::chainsByIndex[chain->ownIndex()]); } Q_ASSERT(sdDUChainPrivate->hasChainForIndex(chain->ownIndex())); sdDUChainPrivate->m_chainsByUrl.insert(chain->url(), chain); Q_ASSERT(sdDUChainPrivate->hasChainForIndex(chain->ownIndex())); chain->setInDuChain(true); l.unlock(); addToEnvironmentManager(chain); // This function might be called during shutdown by stale parse jobs // Make sure we don't access null-pointers here if (ICore::self() && ICore::self()->languageController() && ICore::self()->languageController()->backgroundParser()->trackerForUrl(chain->url())) { //Make sure the context stays alive at least as long as the context is open ReferencedTopDUContext ctx(chain); sdDUChainPrivate->m_openDocumentContexts.insert(ctx); } } void DUChain::addToEnvironmentManager(TopDUContext* chain) { ParsingEnvironmentFilePointer file = chain->parsingEnvironmentFile(); if (!file) return; //We don't need to manage Q_ASSERT(file->indexedTopContext().index() == chain->ownIndex()); if (ParsingEnvironmentFile* alreadyHave = sdDUChainPrivate->findInformation(file->indexedTopContext().index())) { ///If this triggers, there has already been another environment-information registered for this top-context. ///removeFromEnvironmentManager should have been called before to remove the old environment-information. Q_ASSERT(alreadyHave == file.data()); Q_UNUSED(alreadyHave); return; } sdDUChainPrivate->addEnvironmentInformation(file); } void DUChain::removeFromEnvironmentManager(TopDUContext* chain) { ParsingEnvironmentFilePointer file = chain->parsingEnvironmentFile(); if (!file) return; //We don't need to manage sdDUChainPrivate->removeEnvironmentInformation(file); } TopDUContext* DUChain::chainForDocument(const QUrl& document, bool proxyContext) const { return chainForDocument(IndexedString(document), proxyContext); } bool DUChain::isInMemory(uint topContextIndex) const { return DUChainPrivate::hasChainForIndex(topContextIndex); } IndexedString DUChain::urlForIndex(uint index) const { { TopDUContext* chain = DUChainPrivate::readChainForIndex(index); if (chain) return chain->url(); } return TopDUContextDynamicData::loadUrl(index); } TopDUContext* DUChain::loadChain(uint index) { QSet loaded; sdDUChainPrivate->loadChain(index, loaded); { QMutexLocker lock(&chainsByIndexLock); if (chainsByIndex.size() > index) { TopDUContext* top = chainsByIndex[index]; if (top) return top; } } return nullptr; } TopDUContext* DUChain::chainForDocument(const KDevelop::IndexedString& document, bool proxyContext) const { ENSURE_CHAIN_READ_LOCKED; if (sdDUChainPrivate->m_destroyed) return nullptr; const QList list = sdDUChainPrivate->getEnvironmentInformation(document); for (const ParsingEnvironmentFilePointer& file : list) { if (isInMemory(file->indexedTopContext().index()) && file->isProxyContext() == proxyContext) { return file->topContext(); } } for (const ParsingEnvironmentFilePointer& file : list) { if (proxyContext == file->isProxyContext()) { return file->topContext(); } } //Allow selecting a top-context even if there is no ParsingEnvironmentFile const QList ret = chainsForDocument(document); for (TopDUContext* ctx : ret) { if (!ctx->parsingEnvironmentFile() || (ctx->parsingEnvironmentFile()->isProxyContext() == proxyContext)) return ctx; } return nullptr; } QList DUChain::chainsForDocument(const QUrl& document) const { return chainsForDocument(IndexedString(document)); } QList DUChain::chainsForDocument(const IndexedString& document) const { QList chains; if (sdDUChainPrivate->m_destroyed) return chains; QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); // Match all parsed versions of this document for (auto it = sdDUChainPrivate->m_chainsByUrl.lowerBound(document); it != sdDUChainPrivate->m_chainsByUrl.end(); ++it) { if (it.key() == document) chains << it.value(); else break; } return chains; } TopDUContext* DUChain::chainForDocument(const QUrl& document, const KDevelop::ParsingEnvironment* environment, bool proxyContext) const { return chainForDocument(IndexedString(document), environment, proxyContext); } ParsingEnvironmentFilePointer DUChain::environmentFileForDocument(const IndexedString& document, const ParsingEnvironment* environment, bool proxyContext) const { ENSURE_CHAIN_READ_LOCKED; if (sdDUChainPrivate->m_destroyed) return ParsingEnvironmentFilePointer(); QList list = sdDUChainPrivate->getEnvironmentInformation(document); // qCDebug(LANGUAGE) << document.str() << ": matching" << list.size() << (onlyProxyContexts ? "proxy-contexts" : (noProxyContexts ? "content-contexts" : "contexts")); auto it = list.constBegin(); while (it != list.constEnd()) { if (*it && ((*it)->isProxyContext() == proxyContext) && (*it)->matchEnvironment(environment) && // Verify that the environment-file and its top-context are "good": The top-context must exist, // and there must be a content-context associated to the proxy-context. (*it)->topContext() && (!proxyContext || DUChainUtils::contentContextFromProxyContext((*it)->topContext()))) { return *it; } ++it; } return ParsingEnvironmentFilePointer(); } QList DUChain::allEnvironmentFiles(const IndexedString& document) { return sdDUChainPrivate->getEnvironmentInformation(document); } ParsingEnvironmentFilePointer DUChain::environmentFileForDocument(IndexedTopDUContext topContext) const { if (topContext.index() == 0) return ParsingEnvironmentFilePointer(); return ParsingEnvironmentFilePointer(sdDUChainPrivate->loadInformation(topContext.index())); } TopDUContext* DUChain::chainForDocument(const IndexedString& document, const ParsingEnvironment* environment, bool proxyContext) const { if (sdDUChainPrivate->m_destroyed) return nullptr; ParsingEnvironmentFilePointer envFile = environmentFileForDocument(document, environment, proxyContext); if (envFile) { return envFile->topContext(); } else { return nullptr; } } QList DUChain::documents() const { QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); QList ret; ret.reserve(sdDUChainPrivate->m_chainsByUrl.count()); for (TopDUContext* top : qAsConst(sdDUChainPrivate->m_chainsByUrl)) { ret << top->url().toUrl(); } return ret; } QList DUChain::indexedDocuments() const { QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); QList ret; ret.reserve(sdDUChainPrivate->m_chainsByUrl.count()); for (TopDUContext* top : qAsConst(sdDUChainPrivate->m_chainsByUrl)) { ret << top->url(); } return ret; } void DUChain::documentActivated(KDevelop::IDocument* doc) { if (sdDUChainPrivate->m_destroyed) return; DUChainReadLocker lock(DUChain::lock()); QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); auto backgroundParser = ICore::self()->languageController()->backgroundParser(); auto addWithHighPriority = [backgroundParser, doc]() { backgroundParser->addDocument(IndexedString(doc->url()), TopDUContext::VisibleDeclarationsAndContexts, BackgroundParser::BestPriority); }; TopDUContext* ctx = DUChainUtils::standardContextForUrl(doc->url(), true); //Check whether the document has an attached environment-manager, and whether that one thinks the document needs to be updated. //If yes, update it. if (ctx && ctx->parsingEnvironmentFile() && ctx->parsingEnvironmentFile()->needsUpdate()) { qCDebug(LANGUAGE) << "Document needs update, using best priority since it just got activated:" << doc->url(); addWithHighPriority(); } else if (backgroundParser->managedDocuments().contains(IndexedString(doc->url()))) { // increase priority if there's already parse job of this document in the queue qCDebug(LANGUAGE) << "Prioritizing activated document:" << doc->url(); addWithHighPriority(); } } void DUChain::documentClosed(IDocument* document) { if (sdDUChainPrivate->m_destroyed) return; IndexedString url(document->url()); const auto currentDocumentContexts = sdDUChainPrivate->m_openDocumentContexts; for (const ReferencedTopDUContext& top : currentDocumentContexts) { if (top->url() == url) sdDUChainPrivate->m_openDocumentContexts.remove(top); } } void DUChain::documentLoadedPrepare(KDevelop::IDocument* doc) { if (sdDUChainPrivate->m_destroyed) return; const IndexedString url(doc->url()); DUChainWriteLocker lock(DUChain::lock()); QMutexLocker l(&sdDUChainPrivate->m_chainsMutex); TopDUContext* standardContext = DUChainUtils::standardContextForUrl(doc->url()); QList chains = chainsForDocument(url); const auto languages = ICore::self()->languageController()->languagesForUrl(doc->url()); if (standardContext) { Q_ASSERT(chains.contains(standardContext)); //We have just loaded it Q_ASSERT((standardContext->url() == url)); sdDUChainPrivate->m_openDocumentContexts.insert(standardContext); bool needsUpdate = standardContext->parsingEnvironmentFile() && standardContext->parsingEnvironmentFile()->needsUpdate(); if (!needsUpdate) { //Only apply the highlighting if we don't need to update, else we might highlight total crap //Do instant highlighting only if all imports are loaded, to make sure that we don't block the user-interface too long //Else the highlighting will be done in the background-thread //This is not exactly right, as the direct imports don't necessarily equal the real imports used by uses //but it approximates the correct behavior. bool allImportsLoaded = true; const auto importedParentContexts = standardContext->importedParentContexts(); for (const DUContext::Import& import : importedParentContexts) { if (!import.indexedContext().indexedTopContext().isLoaded()) allImportsLoaded = false; } if (allImportsLoaded) { l.unlock(); lock.unlock(); for (const auto language : languages) { if (language->codeHighlighting()) { language->codeHighlighting()->highlightDUChain(standardContext); } } qCDebug(LANGUAGE) << "highlighted" << doc->url() << "in foreground"; return; } } else { qCDebug(LANGUAGE) << "not highlighting the duchain because the documents needs an update"; } if (needsUpdate || !(standardContext->features() & TopDUContext::AllDeclarationsContextsAndUses)) { ICore::self()->languageController()->backgroundParser()->addDocument(IndexedString(doc->url()), ( TopDUContext::Features )(TopDUContext :: AllDeclarationsContextsAndUses | TopDUContext :: ForceUpdate)); return; } } //Add for highlighting etc. ICore::self()->languageController()->backgroundParser()->addDocument(IndexedString( doc->url()), TopDUContext::AllDeclarationsContextsAndUses); } void DUChain::documentRenamed(KDevelop::IDocument* doc) { if (sdDUChainPrivate->m_destroyed) return; if (!doc->url().isValid()) { ///Maybe this happens when a file was deleted? qCWarning(LANGUAGE) << "Strange, url of renamed document is invalid!"; } else { ICore::self()->languageController()->backgroundParser()->addDocument(IndexedString(doc->url()), ( TopDUContext::Features )(TopDUContext:: AllDeclarationsContextsAndUses | TopDUContext:: ForceUpdate)); } } Uses* DUChain::uses() { return &sdDUChainPrivate->m_uses; } Definitions* DUChain::definitions() { return &sdDUChainPrivate->m_definitions; } static void finalCleanup() { DUChainWriteLocker writeLock(DUChain::lock()); qCDebug(LANGUAGE) << "doing final cleanup"; int cleaned = 0; while ((cleaned = globalItemRepositoryRegistry().finalCleanup())) { qCDebug(LANGUAGE) << "cleaned" << cleaned << "B"; if (cleaned < 1000) { qCDebug(LANGUAGE) << "cleaned enough"; break; } } qCDebug(LANGUAGE) << "final cleanup ready"; } void DUChain::shutdown() { // if core is not shutting down, we can end up in deadlocks or crashes // since language plugins might still try to access static duchain stuff Q_ASSERT(!ICore::self() || ICore::self()->shuttingDown()); qCDebug(LANGUAGE) << "Cleaning up and shutting down DUChain"; QMutexLocker lock(&sdDUChainPrivate->cleanupMutex()); { //Acquire write-lock of the repository, so when kdevelop crashes in that process, the repository is discarded //Crashes here may happen in an inconsistent state, thus this makes sense, to protect the user from more crashes globalItemRepositoryRegistry().lockForWriting(); sdDUChainPrivate->cleanupTopContexts(); globalItemRepositoryRegistry().unlockForWriting(); } sdDUChainPrivate->doMoreCleanup(); //Must be done _before_ finalCleanup, else we may be deleting yet needed data sdDUChainPrivate->m_openDocumentContexts.clear(); sdDUChainPrivate->m_destroyed = true; sdDUChainPrivate->clear(); { //Acquire write-lock of the repository, so when kdevelop crashes in that process, the repository is discarded //Crashes here may happen in an inconsistent state, thus this makes sense, to protect the user from more crashes globalItemRepositoryRegistry().lockForWriting(); finalCleanup(); globalItemRepositoryRegistry().unlockForWriting(); } globalItemRepositoryRegistry().shutdown(); } uint DUChain::newTopContextIndex() { { QMutexLocker lock(&sdDUChainPrivate->m_chainsMutex); if (!sdDUChainPrivate->m_availableTopContextIndices.isEmpty()) { uint ret = sdDUChainPrivate->m_availableTopContextIndices.back(); sdDUChainPrivate->m_availableTopContextIndices.pop_back(); if (TopDUContextDynamicData::fileExists(ret)) { qCWarning(LANGUAGE) << "Problem in the management of available top-context indices"; return newTopContextIndex(); } return ret; } } static QAtomicInt& currentId(globalItemRepositoryRegistry().customCounter(QStringLiteral("Top-Context Counter"), 1)); return currentId.fetchAndAddRelaxed(1); } void DUChain::refCountUp(TopDUContext* top) { QMutexLocker l(&sdDUChainPrivate->m_referenceCountsMutex); // note: value is default-constructed to zero if it does not exist ++sdDUChainPrivate->m_referenceCounts[top]; } bool DUChain::deleted() { return m_deleted; } void DUChain::refCountDown(TopDUContext* top) { QMutexLocker l(&sdDUChainPrivate->m_referenceCountsMutex); auto it = sdDUChainPrivate->m_referenceCounts.find(top); if (it == sdDUChainPrivate->m_referenceCounts.end()) { //qCWarning(LANGUAGE) << "tried to decrease reference-count for" << top->url().str() << "but this top-context is not referenced"; return; } auto& refCount = *it; --refCount; if (!refCount) { sdDUChainPrivate->m_referenceCounts.erase(it); } } void DUChain::emitDeclarationSelected(const DeclarationPointer& decl) { if (sdDUChainPrivate->m_destroyed) return; emit declarationSelected(decl); } void DUChain::emitUpdateReady(const IndexedString& url, const ReferencedTopDUContext& topContext) { if (sdDUChainPrivate->m_destroyed) return; emit updateReady(url, topContext); } KDevelop::ReferencedTopDUContext DUChain::waitForUpdate(const KDevelop::IndexedString& document, KDevelop::TopDUContext::Features minFeatures, bool proxyContext) { Q_ASSERT(!lock()->currentThreadHasReadLock() && !lock()->currentThreadHasWriteLock()); WaitForUpdate waiter; updateContextForUrl(document, minFeatures, &waiter); while (!waiter.m_ready) { // we might have been shut down in the meanwhile if (!ICore::self()) { return nullptr; } QMetaObject::invokeMethod(ICore::self()->languageController()->backgroundParser(), "parseDocuments"); QApplication::processEvents(); QThread::usleep(1000); } if (!proxyContext) { DUChainReadLocker readLock(DUChain::lock()); return DUChainUtils::contentContextFromProxyContext(waiter.m_topContext); } return waiter.m_topContext; } void DUChain::updateContextForUrl(const IndexedString& document, TopDUContext::Features minFeatures, QObject* notifyReady, int priority) const { DUChainReadLocker lock(DUChain::lock()); TopDUContext* standardContext = DUChainUtils::standardContextForUrl(document.toUrl()); if (standardContext && standardContext->parsingEnvironmentFile() && !standardContext->parsingEnvironmentFile()->needsUpdate() && standardContext->parsingEnvironmentFile()->featuresSatisfied(minFeatures)) { lock.unlock(); if (notifyReady) QMetaObject::invokeMethod(notifyReady, "updateReady", Qt::DirectConnection, Q_ARG(KDevelop::IndexedString, document), Q_ARG(KDevelop::ReferencedTopDUContext, ReferencedTopDUContext(standardContext))); } else { ///Start a parse-job for the given document ICore::self()->languageController()->backgroundParser()->addDocument(document, minFeatures, priority, notifyReady); } } void DUChain::disablePersistentStorage(bool disable) { sdDUChainPrivate->m_cleanupDisabled = disable; } void DUChain::storeToDisk() { bool wasDisabled = sdDUChainPrivate->m_cleanupDisabled; sdDUChainPrivate->m_cleanupDisabled = false; sdDUChainPrivate->doMoreCleanup(); sdDUChainPrivate->m_cleanupDisabled = wasDisabled; } bool DUChain::compareToDisk() { DUChainWriteLocker writeLock(DUChain::lock()); ///Step 1: Compare the repositories return true; } } diff --git a/kdevplatform/language/duchain/identifier.cpp b/kdevplatform/language/duchain/identifier.cpp index ecd60a227a..ec02df557b 100644 --- a/kdevplatform/language/duchain/identifier.cpp +++ b/kdevplatform/language/duchain/identifier.cpp @@ -1,1593 +1,1597 @@ /* This file is part of KDevelop Copyright 2006 Hamish Rodda Copyright 2007-2008 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 "identifier.h" #include #include "stringhelpers.h" #include "appendedlist_static.h" #include "serialization/itemrepository.h" #include "util/kdevhash.h" #include #include #include #define ifDebug(x) namespace KDevelop { template class IdentifierPrivate { public: IdentifierPrivate() { } template explicit IdentifierPrivate(const IdentifierPrivate& rhs) : m_unique(rhs.m_unique) , m_identifier(rhs.m_identifier) , m_refCount(0) , m_hash(rhs.m_hash) { copyListsFrom(rhs); } ~IdentifierPrivate() { templateIdentifiersList.free(const_cast(templateIdentifiers())); } + IdentifierPrivate& operator=(const IdentifierPrivate& rhs) = delete; + //Flags the stored hash-value invalid void clearHash() { //This is always called on an object private to an Identifier, so there is no threading-problem. Q_ASSERT(dynamic); m_hash = 0; } uint hash() const { // Since this only needs reading and the data needs not to be private, this may be called by // multiple threads simultaneously, so computeHash() must be thread-safe. if (!m_hash && dynamic) computeHash(); return m_hash; } int m_unique = 0; IndexedString m_identifier; uint m_refCount = 0; START_APPENDED_LISTS_STATIC(IdentifierPrivate) APPENDED_LIST_FIRST_STATIC(IndexedTypeIdentifier, templateIdentifiers) END_APPENDED_LISTS_STATIC(templateIdentifiers) uint itemSize() const { return sizeof(IdentifierPrivate ) + lastOffsetBehind(); } void computeHash() const { Q_ASSERT(dynamic); //this must stay thread-safe(may be called by multiple threads at a time) //The thread-safety is given because all threads will have the same result, and it will only be written once at the end. KDevHash kdevhash; kdevhash << m_identifier.hash() << m_unique; FOREACH_FUNCTION_STATIC(const IndexedTypeIdentifier &templateIdentifier, templateIdentifiers) kdevhash << templateIdentifier.hash(); m_hash = kdevhash; } mutable uint m_hash = 0; }; using DynamicIdentifierPrivate = IdentifierPrivate; using ConstantIdentifierPrivate = IdentifierPrivate; struct IdentifierItemRequest { IdentifierItemRequest(const DynamicIdentifierPrivate& identifier) : m_identifier(identifier) { identifier.hash(); //Make sure the hash is valid by calling this } enum { AverageSize = sizeof(IdentifierPrivate ) + 4 }; //Should return the hash-value associated with this request(For example the hash of a string) uint hash() const { return m_identifier.hash(); } //Should return the size of an item created with createItem uint itemSize() const { return m_identifier.itemSize(); } //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 createItem(ConstantIdentifierPrivate* item) const { new (item) ConstantIdentifierPrivate(m_identifier); } static bool persistent(const ConstantIdentifierPrivate* item) { return ( bool )item->m_refCount; } static void destroy(ConstantIdentifierPrivate* item, AbstractItemRepository&) { item->~ConstantIdentifierPrivate(); } //Should return whether the here requested item equals the given item bool equals(const ConstantIdentifierPrivate* item) const { return item->m_hash == m_identifier.m_hash && item->m_unique == m_identifier.m_unique && item->m_identifier == m_identifier.m_identifier && m_identifier.listsEqual(*item); } const DynamicIdentifierPrivate& m_identifier; }; using IdentifierRepository = RepositoryManager, false>; static IdentifierRepository& identifierRepository() { static IdentifierRepository identifierRepositoryObject(QStringLiteral("Identifier Repository")); return identifierRepositoryObject; } static uint emptyConstantIdentifierPrivateIndex() { static const uint index = identifierRepository()->index(DynamicIdentifierPrivate()); return index; } static const ConstantIdentifierPrivate* emptyConstantIdentifierPrivate() { static const ConstantIdentifierPrivate item; return &item; } bool IndexedIdentifier::isEmpty() const { return m_index == emptyConstantIdentifierPrivateIndex(); } /** * Before something is modified in QualifiedIdentifierPrivate, it must be made sure that * it is private to the QualifiedIdentifier it is used in(@see QualifiedIdentifier::prepareWrite) */ template class QualifiedIdentifierPrivate { public: QualifiedIdentifierPrivate() : m_explicitlyGlobal(false) , m_isExpression(false) { } template explicit QualifiedIdentifierPrivate(const QualifiedIdentifierPrivate& rhs) : m_explicitlyGlobal(rhs.m_explicitlyGlobal) , m_isExpression(rhs.m_isExpression) , m_hash(rhs.m_hash) , m_refCount(0) { copyListsFrom(rhs); } ~QualifiedIdentifierPrivate() { identifiersList.free(const_cast(identifiers())); } + QualifiedIdentifierPrivate& operator=(const QualifiedIdentifierPrivate& rhs) = delete; + bool m_explicitlyGlobal : 1; bool m_isExpression : 1; mutable uint m_hash = 0; uint m_refCount = 0; START_APPENDED_LISTS_STATIC(QualifiedIdentifierPrivate) APPENDED_LIST_FIRST_STATIC(IndexedIdentifier, identifiers) END_APPENDED_LISTS_STATIC(identifiers) uint itemSize() const { return sizeof(QualifiedIdentifierPrivate ) + lastOffsetBehind(); } //Constructs m_identifiers void splitIdentifiers(const QString& str, int start) { Q_ASSERT(dynamic); uint currentStart = start; while (currentStart < ( uint )str.length()) { identifiersList.append(IndexedIdentifier(Identifier(str, currentStart, ¤tStart))); while (currentStart < ( uint )str.length() && (str[currentStart] == QLatin1Char(' '))) ++currentStart; currentStart += 2; //Skip "::" } } inline void clearHash() const { m_hash = 0; } uint hash() const { if (m_hash == 0) { KDevHash hash; quint32 bitfields = static_cast(m_explicitlyGlobal) | (m_isExpression << 1); hash << bitfields << identifiersSize(); FOREACH_FUNCTION_STATIC(const IndexedIdentifier &identifier, identifiers) { hash << identifier.index(); } m_hash = hash; } return m_hash; } }; using DynamicQualifiedIdentifierPrivate = QualifiedIdentifierPrivate; using ConstantQualifiedIdentifierPrivate = QualifiedIdentifierPrivate; struct QualifiedIdentifierItemRequest { QualifiedIdentifierItemRequest(const DynamicQualifiedIdentifierPrivate& identifier) : m_identifier(identifier) { identifier.hash(); //Make sure the hash is valid by calling this } enum { AverageSize = sizeof(QualifiedIdentifierPrivate ) + 8 }; //Should return the hash-value associated with this request(For example the hash of a string) uint hash() const { return m_identifier.hash(); } //Should return the size of an item created with createItem uint itemSize() const { return m_identifier.itemSize(); } /** * 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 createItem(ConstantQualifiedIdentifierPrivate* item) const { Q_ASSERT(shouldDoDUChainReferenceCounting(item)); Q_ASSERT(shouldDoDUChainReferenceCounting((( char* )item) + (itemSize() - 1))); new (item) ConstantQualifiedIdentifierPrivate(m_identifier); } static bool persistent(const ConstantQualifiedIdentifierPrivate* item) { return ( bool )item->m_refCount; } static void destroy(ConstantQualifiedIdentifierPrivate* item, AbstractItemRepository&) { Q_ASSERT(shouldDoDUChainReferenceCounting(item)); item->~ConstantQualifiedIdentifierPrivate(); } //Should return whether the here requested item equals the given item bool equals(const ConstantQualifiedIdentifierPrivate* item) const { return item->m_explicitlyGlobal == m_identifier.m_explicitlyGlobal && item->m_isExpression == m_identifier.m_isExpression && item->m_hash == m_identifier.m_hash && m_identifier.listsEqual(*item); } const DynamicQualifiedIdentifierPrivate& m_identifier; }; using QualifiedIdentifierRepository = RepositoryManager, false>; static QualifiedIdentifierRepository& qualifiedidentifierRepository() { static QualifiedIdentifierRepository repo(QStringLiteral("Qualified Identifier Repository"), 1, []() -> AbstractRepositoryManager* { return &identifierRepository(); }); return repo; } static uint emptyConstantQualifiedIdentifierPrivateIndex() { static const uint index = qualifiedidentifierRepository()->index(DynamicQualifiedIdentifierPrivate()); return index; } static const ConstantQualifiedIdentifierPrivate* emptyConstantQualifiedIdentifierPrivate() { static const ConstantQualifiedIdentifierPrivate item; return &item; } Identifier::Identifier(const Identifier& rhs) { rhs.makeConstant(); cd = rhs.cd; m_index = rhs.m_index; } Identifier::Identifier(uint index) : m_index(index) { Q_ASSERT(m_index); cd = identifierRepository()->itemFromIndex(index); } Identifier::Identifier(const IndexedString& str) { if (str.isEmpty()) { m_index = emptyConstantIdentifierPrivateIndex(); cd = emptyConstantIdentifierPrivate(); } else { m_index = 0; dd = new IdentifierPrivate; dd->m_identifier = str; } } Identifier::Identifier(const QString& id, uint start, uint* takenRange) { if (id.isEmpty()) { m_index = emptyConstantIdentifierPrivateIndex(); cd = emptyConstantIdentifierPrivate(); return; } m_index = 0; dd = new IdentifierPrivate; ///Extract template-parameters ParamIterator paramIt(QStringLiteral("<>:"), id, start); dd->m_identifier = IndexedString(paramIt.prefix().trimmed()); while (paramIt) { appendTemplateIdentifier(IndexedTypeIdentifier(IndexedQualifiedIdentifier(QualifiedIdentifier(*paramIt)))); ++paramIt; } if (takenRange) *takenRange = paramIt.position(); } Identifier::Identifier() : m_index(emptyConstantIdentifierPrivateIndex()) , cd(emptyConstantIdentifierPrivate()) { } Identifier& Identifier::operator=(const Identifier& rhs) { if (dd == rhs.dd && cd == rhs.cd) return *this; if (!m_index) delete dd; dd = nullptr; rhs.makeConstant(); cd = rhs.cd; m_index = rhs.m_index; Q_ASSERT(cd); return *this; } Identifier::Identifier(Identifier&& rhs) Q_DECL_NOEXCEPT : m_index(rhs.m_index) { if (m_index) { cd = rhs.cd; } else { dd = rhs.dd; } rhs.cd = emptyConstantIdentifierPrivate(); rhs.m_index = emptyConstantIdentifierPrivateIndex(); } Identifier& Identifier::operator=(Identifier&& rhs) Q_DECL_NOEXCEPT { if (dd == rhs.dd && cd == rhs.cd) return *this; if (!m_index) { delete dd; dd = nullptr; } m_index = rhs.m_index; if (m_index) { cd = rhs.cd; } else { dd = rhs.dd; } rhs.cd = emptyConstantIdentifierPrivate(); rhs.m_index = emptyConstantIdentifierPrivateIndex(); return *this; } Identifier::~Identifier() { if (!m_index) delete dd; } bool Identifier::nameEquals(const Identifier& rhs) const { return identifier() == rhs.identifier(); } uint Identifier::hash() const { if (!m_index) return dd->hash(); else return cd->hash(); } bool Identifier::isEmpty() const { if (!m_index) return dd->m_identifier.isEmpty() && dd->m_unique == 0 && dd->templateIdentifiersSize() == 0; else return cd->m_identifier.isEmpty() && cd->m_unique == 0 && cd->templateIdentifiersSize() == 0; } Identifier Identifier::unique(int token) { Identifier ret; ret.setUnique(token); return ret; } bool Identifier::isUnique() const { if (!m_index) return dd->m_unique; else return cd->m_unique; } int Identifier::uniqueToken() const { if (!m_index) return dd->m_unique; else return cd->m_unique; } void Identifier::setUnique(int token) { if (token != uniqueToken()) { prepareWrite(); dd->m_unique = token; } } const IndexedString Identifier::identifier() const { if (!m_index) return dd->m_identifier; else return cd->m_identifier; } void Identifier::setIdentifier(const QString& identifier) { IndexedString id(identifier); if (id != this->identifier()) { prepareWrite(); dd->m_identifier = std::move(id); } } void Identifier::setIdentifier(const IndexedString& identifier) { if (identifier != this->identifier()) { prepareWrite(); dd->m_identifier = identifier; } } IndexedTypeIdentifier Identifier::templateIdentifier(int num) const { if (!m_index) return dd->templateIdentifiers()[num]; else return cd->templateIdentifiers()[num]; } uint Identifier::templateIdentifiersCount() const { if (!m_index) return dd->templateIdentifiersSize(); else return cd->templateIdentifiersSize(); } void Identifier::appendTemplateIdentifier(const IndexedTypeIdentifier& identifier) { prepareWrite(); dd->templateIdentifiersList.append(identifier); } void Identifier::clearTemplateIdentifiers() { prepareWrite(); dd->templateIdentifiersList.clear(); } uint Identifier::index() const { makeConstant(); Q_ASSERT(m_index); return m_index; } bool Identifier::inRepository() const { return m_index; } void Identifier::setTemplateIdentifiers(const QList& templateIdentifiers) { prepareWrite(); dd->templateIdentifiersList.clear(); for (const IndexedTypeIdentifier& id : templateIdentifiers) { dd->templateIdentifiersList.append(id); } } QString Identifier::toString(IdentifierStringFormattingOptions options) const { QString ret = identifier().str(); if (!options.testFlag(RemoveTemplateInformation) && templateIdentifiersCount()) { QStringList templateIds; templateIds.reserve(templateIdentifiersCount()); for (uint i = 0; i < templateIdentifiersCount(); ++i) { templateIds.append(templateIdentifier(i).toString(options)); } ret += QStringLiteral("< ") + templateIds.join(QStringLiteral(", ")) + QStringLiteral(" >"); } return ret; } bool Identifier::operator==(const Identifier& rhs) const { return index() == rhs.index(); } bool Identifier::operator!=(const Identifier& rhs) const { return !operator==(rhs); } uint QualifiedIdentifier::index() const { makeConstant(); Q_ASSERT(m_index); return m_index; } void Identifier::makeConstant() const { if (m_index) return; m_index = identifierRepository()->index(IdentifierItemRequest(*dd)); delete dd; cd = identifierRepository()->itemFromIndex(m_index); } void Identifier::prepareWrite() { if (m_index) { const IdentifierPrivate* oldCc = cd; dd = new IdentifierPrivate; dd->m_hash = oldCc->m_hash; dd->m_unique = oldCc->m_unique; dd->m_identifier = oldCc->m_identifier; dd->copyListsFrom(*oldCc); m_index = 0; } dd->clearHash(); } bool QualifiedIdentifier::inRepository() const { if (m_index) return true; else return ( bool )qualifiedidentifierRepository()->findIndex(QualifiedIdentifierItemRequest(*dd)); } QualifiedIdentifier::QualifiedIdentifier(uint index) : m_index(index) , cd(qualifiedidentifierRepository()->itemFromIndex(index)) { } QualifiedIdentifier::QualifiedIdentifier(const QString& id, bool isExpression) { if (id.isEmpty()) { m_index = emptyConstantQualifiedIdentifierPrivateIndex(); cd = emptyConstantQualifiedIdentifierPrivate(); return; } m_index = 0; dd = new DynamicQualifiedIdentifierPrivate; if (isExpression) { setIsExpression(true); if (!id.isEmpty()) { //Prevent tokenization, since we may lose information there Identifier finishedId; finishedId.setIdentifier(id); push(finishedId); } } else { if (id.startsWith(QStringLiteral("::"))) { dd->m_explicitlyGlobal = true; dd->splitIdentifiers(id, 2); } else { dd->m_explicitlyGlobal = false; dd->splitIdentifiers(id, 0); } } } QualifiedIdentifier::QualifiedIdentifier(const Identifier& id) { if (id.isEmpty()) { m_index = emptyConstantQualifiedIdentifierPrivateIndex(); cd = emptyConstantQualifiedIdentifierPrivate(); return; } m_index = 0; dd = new DynamicQualifiedIdentifierPrivate; if (id.dd->m_identifier.str().isEmpty()) { dd->m_explicitlyGlobal = true; } else { dd->m_explicitlyGlobal = false; dd->identifiersList.append(IndexedIdentifier(id)); } } QualifiedIdentifier::QualifiedIdentifier() : m_index(emptyConstantQualifiedIdentifierPrivateIndex()) , cd(emptyConstantQualifiedIdentifierPrivate()) { } QualifiedIdentifier::QualifiedIdentifier(const QualifiedIdentifier& id) { if (id.m_index) { m_index = id.m_index; cd = id.cd; } else { m_index = 0; dd = new QualifiedIdentifierPrivate(*id.dd); } } QualifiedIdentifier::QualifiedIdentifier(QualifiedIdentifier&& rhs) Q_DECL_NOEXCEPT : m_index(rhs.m_index) { if (m_index) { cd = rhs.cd; } else { dd = rhs.dd; } rhs.m_index = emptyConstantQualifiedIdentifierPrivateIndex(); rhs.cd = emptyConstantQualifiedIdentifierPrivate(); } QualifiedIdentifier& QualifiedIdentifier::operator=(const QualifiedIdentifier& rhs) { if (dd == rhs.dd && cd == rhs.cd) return *this; if (!m_index) delete dd; rhs.makeConstant(); cd = rhs.cd; m_index = rhs.m_index; return *this; } QualifiedIdentifier& QualifiedIdentifier::operator=(QualifiedIdentifier&& rhs) Q_DECL_NOEXCEPT { if (!m_index) delete dd; m_index = rhs.m_index; if (m_index) { cd = rhs.cd; } else { dd = rhs.dd; } rhs.cd = emptyConstantQualifiedIdentifierPrivate(); rhs.m_index = emptyConstantQualifiedIdentifierPrivateIndex(); return *this; } QualifiedIdentifier::~QualifiedIdentifier() { if (!m_index) delete dd; } QStringList QualifiedIdentifier::toStringList(IdentifierStringFormattingOptions options) const { QStringList ret; ret.reserve(explicitlyGlobal() + count()); if (explicitlyGlobal()) ret.append(QString()); if (m_index) { ret.reserve(ret.size() + cd->identifiersSize()); FOREACH_FUNCTION_STATIC(const IndexedIdentifier &index, cd->identifiers) ret << index.identifier().toString(options); } else { ret.reserve(ret.size() + dd->identifiersSize()); FOREACH_FUNCTION_STATIC(const IndexedIdentifier &index, dd->identifiers) ret << index.identifier().toString(options); } return ret; } QString QualifiedIdentifier::toString(IdentifierStringFormattingOptions options) const { const QString doubleColon = QStringLiteral("::"); QString ret; if (!options.testFlag(RemoveExplicitlyGlobalPrefix) && explicitlyGlobal()) ret = doubleColon; QStringList identifiers; if (m_index) { identifiers.reserve(cd->identifiersSize()); FOREACH_FUNCTION_STATIC(const IndexedIdentifier &index, cd->identifiers) { identifiers += index.identifier().toString(options); } } else { identifiers.reserve(dd->identifiersSize()); FOREACH_FUNCTION_STATIC(const IndexedIdentifier &index, dd->identifiers) { identifiers += index.identifier().toString(options); } } return ret + identifiers.join(doubleColon); } QualifiedIdentifier QualifiedIdentifier::merge(const QualifiedIdentifier& base) const { QualifiedIdentifier ret(base); ret.push(*this); return ret; } QualifiedIdentifier QualifiedIdentifier::operator+(const QualifiedIdentifier& rhs) const { return rhs.merge(*this); } QualifiedIdentifier& QualifiedIdentifier::operator+=(const QualifiedIdentifier& rhs) { push(rhs); return *this; } QualifiedIdentifier QualifiedIdentifier::operator+(const Identifier& rhs) const { QualifiedIdentifier ret(*this); ret.push(rhs); return ret; } QualifiedIdentifier& QualifiedIdentifier::operator+=(const Identifier& rhs) { push(rhs); return *this; } QualifiedIdentifier QualifiedIdentifier::operator+(const IndexedIdentifier& rhs) const { QualifiedIdentifier ret(*this); ret.push(rhs); return ret; } QualifiedIdentifier& QualifiedIdentifier::operator+=(const IndexedIdentifier& rhs) { push(rhs); return *this; } bool QualifiedIdentifier::isExpression() const { if (m_index) return cd->m_isExpression; else return dd->m_isExpression; } void QualifiedIdentifier::setIsExpression(bool is) { if (is != isExpression()) { prepareWrite(); dd->m_isExpression = is; } } bool QualifiedIdentifier::explicitlyGlobal() const { // True if started with "::" if (m_index) return cd->m_explicitlyGlobal; else return dd->m_explicitlyGlobal; } void QualifiedIdentifier::setExplicitlyGlobal(bool eg) { if (eg != explicitlyGlobal()) { prepareWrite(); dd->m_explicitlyGlobal = eg; } } bool QualifiedIdentifier::sameIdentifiers(const QualifiedIdentifier& rhs) const { if (m_index && rhs.m_index) return cd->listsEqual(*rhs.cd); else if (m_index && !rhs.m_index) return cd->listsEqual(*rhs.dd); else if (!m_index && !rhs.m_index) return dd->listsEqual(*rhs.dd); else return dd->listsEqual(*rhs.cd); } bool QualifiedIdentifier::operator==(const QualifiedIdentifier& rhs) const { if (cd == rhs.cd) return true; return hash() == rhs.hash() && sameIdentifiers(rhs); } bool QualifiedIdentifier::operator!=(const QualifiedIdentifier& rhs) const { return !operator==(rhs); } bool QualifiedIdentifier::beginsWith(const QualifiedIdentifier& other) const { uint c = count(); uint oc = other.count(); for (uint i = 0; i < c && i < oc; ++i) if (at(i) == other.at(i)) { continue; } else { return false; } return true; } struct Visitor { Visitor(KDevVarLengthArray& target, uint hash) : target(target) , hash(hash) { } bool operator()(const ConstantQualifiedIdentifierPrivate* item, uint index) const { if (item->m_hash == hash) target.append(QualifiedIdentifier(index)); return true; } KDevVarLengthArray& target; const uint hash; }; uint QualifiedIdentifier::hash() const { if (m_index) return cd->hash(); else return dd->hash(); } uint qHash(const IndexedTypeIdentifier& id) { return id.hash(); } uint qHash(const QualifiedIdentifier& id) { return id.hash(); } uint qHash(const Identifier& id) { return id.hash(); } bool QualifiedIdentifier::isQualified() const { return count() > 1 || explicitlyGlobal(); } void QualifiedIdentifier::push(const Identifier& id) { if (id.isEmpty()) return; push(IndexedIdentifier(id)); } void QualifiedIdentifier::push(const IndexedIdentifier& id) { if (id.isEmpty()) { return; } prepareWrite(); dd->identifiersList.append(id); } void QualifiedIdentifier::push(const QualifiedIdentifier& id) { if (id.isEmpty()) { return; } prepareWrite(); if (id.m_index) { dd->identifiersList.append(id.cd->identifiers(), id.cd->identifiersSize()); } else { dd->identifiersList.append(id.dd->identifiers(), id.dd->identifiersSize()); } if (id.explicitlyGlobal()) { setExplicitlyGlobal(true); } } void QualifiedIdentifier::pop() { prepareWrite(); if (!dd->identifiersSize()) return; dd->identifiersList.resize(dd->identifiersList.size() - 1); } void QualifiedIdentifier::clear() { prepareWrite(); dd->identifiersList.clear(); dd->m_explicitlyGlobal = false; dd->m_isExpression = false; } bool QualifiedIdentifier::isEmpty() const { if (m_index) return cd->identifiersSize() == 0; else return dd->identifiersSize() == 0; } int QualifiedIdentifier::count() const { if (m_index) return cd->identifiersSize(); else return dd->identifiersSize(); } Identifier QualifiedIdentifier::first() const { return indexedFirst().identifier(); } IndexedIdentifier QualifiedIdentifier::indexedFirst() const { if ((m_index && cd->identifiersSize() == 0) || (!m_index && dd->identifiersSize() == 0)) return IndexedIdentifier(); else return indexedAt(0); } Identifier QualifiedIdentifier::last() const { return indexedLast().identifier(); } IndexedIdentifier QualifiedIdentifier::indexedLast() const { uint c = count(); if (c) return indexedAt(c - 1); else return IndexedIdentifier(); } Identifier QualifiedIdentifier::top() const { return last(); } QualifiedIdentifier QualifiedIdentifier::mid(int pos, int len) const { QualifiedIdentifier ret; if (pos == 0) ret.setExplicitlyGlobal(explicitlyGlobal()); int cnt = ( int )count(); if (len == -1) len = cnt - pos; if (pos + len > cnt) len -= cnt - (pos + len); for (int a = pos; a < pos + len; a++) ret.push(at(a)); return ret; } Identifier QualifiedIdentifier::at(int i) const { return indexedAt(i).identifier(); } IndexedIdentifier QualifiedIdentifier::indexedAt(int i) const { if (m_index) { Q_ASSERT(i >= 0 && i < ( int )cd->identifiersSize()); return cd->identifiers()[i]; } else { Q_ASSERT(i >= 0 && i < ( int )dd->identifiersSize()); return dd->identifiers()[i]; } } void QualifiedIdentifier::makeConstant() const { if (m_index) return; m_index = qualifiedidentifierRepository()->index(QualifiedIdentifierItemRequest(*dd)); delete dd; cd = qualifiedidentifierRepository()->itemFromIndex(m_index); } void QualifiedIdentifier::prepareWrite() { if (m_index) { const QualifiedIdentifierPrivate* oldCc = cd; dd = new QualifiedIdentifierPrivate; dd->m_explicitlyGlobal = oldCc->m_explicitlyGlobal; dd->m_isExpression = oldCc->m_isExpression; dd->m_hash = oldCc->m_hash; dd->copyListsFrom(*oldCc); m_index = 0; } dd->clearHash(); } uint IndexedTypeIdentifier::hash() const { quint32 bitfields = static_cast(m_isConstant) | (m_isReference << 1) | (m_isRValue << 2) | (m_isVolatile << 3) | (m_pointerDepth << 4) | (m_pointerConstMask << 9); return KDevHash() << m_identifier.index() << bitfields; } bool IndexedTypeIdentifier::operator==(const IndexedTypeIdentifier& rhs) const { return m_identifier == rhs.m_identifier && m_isConstant == rhs.m_isConstant && m_isReference == rhs.m_isReference && m_isRValue == rhs.m_isRValue && m_isVolatile == rhs.m_isVolatile && m_pointerConstMask == rhs.m_pointerConstMask && m_pointerDepth == rhs.m_pointerDepth; } bool IndexedTypeIdentifier::operator!=(const IndexedTypeIdentifier& rhs) const { return !operator==(rhs); } bool IndexedTypeIdentifier::isReference() const { return m_isReference; } void IndexedTypeIdentifier::setIsReference(bool isRef) { m_isReference = isRef; } bool IndexedTypeIdentifier::isRValue() const { return m_isRValue; } void IndexedTypeIdentifier::setIsRValue(bool isRVal) { m_isRValue = isRVal; } bool IndexedTypeIdentifier::isConstant() const { return m_isConstant; } void IndexedTypeIdentifier::setIsConstant(bool isConst) { m_isConstant = isConst; } bool IndexedTypeIdentifier::isVolatile() const { return m_isVolatile; } void IndexedTypeIdentifier::setIsVolatile(bool isVolatile) { m_isVolatile = isVolatile; } int IndexedTypeIdentifier::pointerDepth() const { return m_pointerDepth; } void IndexedTypeIdentifier::setPointerDepth(int depth) { Q_ASSERT(depth <= 23 && depth >= 0); ///Clear the mask in removed fields for (int s = depth; s < ( int )m_pointerDepth; ++s) setIsConstPointer(s, false); m_pointerDepth = depth; } bool IndexedTypeIdentifier::isConstPointer(int depthNumber) const { return m_pointerConstMask & (1 << depthNumber); } void IndexedTypeIdentifier::setIsConstPointer(int depthNumber, bool constant) { if (constant) m_pointerConstMask |= (1 << depthNumber); else m_pointerConstMask &= (~(1 << depthNumber)); } QString IndexedTypeIdentifier::toString(IdentifierStringFormattingOptions options) const { QString ret; if (isConstant()) ret += QLatin1String("const "); if (isVolatile()) ret += QLatin1String("volatile "); ret += m_identifier.identifier().toString(options); for (int a = 0; a < pointerDepth(); ++a) { ret += QLatin1Char('*'); if (isConstPointer(a)) ret += QLatin1String("const"); } if (isRValue()) ret += QLatin1String("&&"); else if (isReference()) ret += QLatin1Char('&'); return ret; } IndexedTypeIdentifier::IndexedTypeIdentifier(const IndexedQualifiedIdentifier& identifier) : m_identifier(identifier) , m_isConstant(false) , m_isReference(false) , m_isRValue(false) , m_isVolatile(false) , m_pointerDepth(0) , m_pointerConstMask(0) { } IndexedTypeIdentifier::IndexedTypeIdentifier(const QString& identifier, bool isExpression) : m_identifier(QualifiedIdentifier(identifier, isExpression)) , m_isConstant(false) , m_isReference(false) , m_isRValue(false) , m_isVolatile(false) , m_pointerDepth(0) , m_pointerConstMask(0) { } IndexedIdentifier::IndexedIdentifier() : m_index(emptyConstantIdentifierPrivateIndex()) { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedIdentifier::IndexedIdentifier(const Identifier& id) : m_index(id.index()) { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedIdentifier::IndexedIdentifier(const IndexedIdentifier& rhs) : m_index(rhs.m_index) { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedIdentifier::IndexedIdentifier(IndexedIdentifier&& rhs) Q_DECL_NOEXCEPT : m_index(rhs.m_index) { rhs.m_index = emptyConstantIdentifierPrivateIndex(); } IndexedIdentifier::~IndexedIdentifier() { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); decrease(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedIdentifier& IndexedIdentifier::operator=(const Identifier& id) { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); decrease(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } m_index = id.index(); if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } return *this; } IndexedIdentifier& IndexedIdentifier::operator=(IndexedIdentifier&& rhs) Q_DECL_NOEXCEPT { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } else if (shouldDoDUChainReferenceCounting(&rhs)) { QMutexLocker lock(identifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(identifierRepository()->dynamicItemFromIndexSimple(rhs.m_index)->m_refCount, rhs.m_index); } m_index = rhs.m_index; rhs.m_index = emptyConstantIdentifierPrivateIndex(); if (shouldDoDUChainReferenceCounting(this) && !(shouldDoDUChainReferenceCounting(&rhs))) { QMutexLocker lock(identifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "increasing"; ) increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } return *this; } IndexedIdentifier& IndexedIdentifier::operator=(const IndexedIdentifier& id) { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); decrease(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } m_index = id.m_index; if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(identifierRepository()->mutex()); increase(identifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } return *this; } bool IndexedIdentifier::operator==(const IndexedIdentifier& rhs) const { return m_index == rhs.m_index; } bool IndexedIdentifier::operator!=(const IndexedIdentifier& rhs) const { return m_index != rhs.m_index; } bool IndexedIdentifier::operator==(const Identifier& id) const { return m_index == id.index(); } Identifier IndexedIdentifier::identifier() const { return Identifier(m_index); } IndexedIdentifier::operator Identifier() const { return Identifier(m_index); } bool IndexedQualifiedIdentifier::isValid() const { return m_index != emptyConstantQualifiedIdentifierPrivateIndex(); } bool IndexedQualifiedIdentifier::isEmpty() const { return m_index == emptyConstantQualifiedIdentifierPrivateIndex(); } int cnt = 0; IndexedQualifiedIdentifier IndexedTypeIdentifier::identifier() const { return m_identifier; } void IndexedTypeIdentifier::setIdentifier(const IndexedQualifiedIdentifier& id) { m_identifier = id; } IndexedQualifiedIdentifier::IndexedQualifiedIdentifier() : m_index(emptyConstantQualifiedIdentifierPrivateIndex()) { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << m_index; ) if (shouldDoDUChainReferenceCounting(this)) { ifDebug(qCDebug(LANGUAGE) << "increasing"; ) //qCDebug(LANGUAGE) << "(" << ++cnt << ")" << this << identifier().toString() << "inc" << index; QMutexLocker lock(qualifiedidentifierRepository()->mutex()); increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedQualifiedIdentifier::IndexedQualifiedIdentifier(const QualifiedIdentifier& id) : m_index(id.index()) { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << m_index; ) if (shouldDoDUChainReferenceCounting(this)) { ifDebug(qCDebug(LANGUAGE) << "increasing"; ) QMutexLocker lock(qualifiedidentifierRepository()->mutex()); increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedQualifiedIdentifier::IndexedQualifiedIdentifier(const IndexedQualifiedIdentifier& id) : m_index(id.m_index) { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << m_index; ) if (shouldDoDUChainReferenceCounting(this)) { ifDebug(qCDebug(LANGUAGE) << "increasing"; ) QMutexLocker lock(qualifiedidentifierRepository()->mutex()); increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } IndexedQualifiedIdentifier::IndexedQualifiedIdentifier(IndexedQualifiedIdentifier&& rhs) Q_DECL_NOEXCEPT : m_index(rhs.m_index) { rhs.m_index = emptyConstantQualifiedIdentifierPrivateIndex(); } IndexedQualifiedIdentifier& IndexedQualifiedIdentifier::operator=(const QualifiedIdentifier& id) { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << m_index; ) if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(qualifiedidentifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); m_index = id.index(); ifDebug(qCDebug(LANGUAGE) << m_index << "increasing"; ) increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } else { m_index = id.index(); } return *this; } IndexedQualifiedIdentifier& IndexedQualifiedIdentifier::operator=(const IndexedQualifiedIdentifier& rhs) { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << m_index; ) if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(qualifiedidentifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); m_index = rhs.m_index; ifDebug(qCDebug(LANGUAGE) << m_index << "increasing"; ) increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } else { m_index = rhs.m_index; } return *this; } IndexedQualifiedIdentifier& IndexedQualifiedIdentifier::operator=(IndexedQualifiedIdentifier&& rhs) Q_DECL_NOEXCEPT { if (shouldDoDUChainReferenceCounting(this)) { QMutexLocker lock(qualifiedidentifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } else if (shouldDoDUChainReferenceCounting(&rhs)) { QMutexLocker lock(qualifiedidentifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "decreasing"; ) decrease(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(rhs.m_index)->m_refCount, rhs.m_index); } m_index = rhs.m_index; rhs.m_index = emptyConstantQualifiedIdentifierPrivateIndex(); if (shouldDoDUChainReferenceCounting(this) && !(shouldDoDUChainReferenceCounting(&rhs))) { QMutexLocker lock(qualifiedidentifierRepository()->mutex()); ifDebug(qCDebug(LANGUAGE) << "increasing"; ) increase(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } return *this; } IndexedQualifiedIdentifier::~IndexedQualifiedIdentifier() { ifDebug(qCDebug(LANGUAGE) << "(" << ++cnt << ")" << identifier().toString() << index; ) if (shouldDoDUChainReferenceCounting(this)) { ifDebug(qCDebug(LANGUAGE) << index << "decreasing"; ) QMutexLocker lock(qualifiedidentifierRepository()->mutex()); decrease(qualifiedidentifierRepository()->dynamicItemFromIndexSimple(m_index)->m_refCount, m_index); } } bool IndexedQualifiedIdentifier::operator==(const IndexedQualifiedIdentifier& rhs) const { return m_index == rhs.m_index; } bool IndexedQualifiedIdentifier::operator==(const QualifiedIdentifier& id) const { return m_index == id.index(); } QualifiedIdentifier IndexedQualifiedIdentifier::identifier() const { return QualifiedIdentifier(m_index); } IndexedQualifiedIdentifier::operator QualifiedIdentifier() const { return QualifiedIdentifier(m_index); } void initIdentifierRepository() { emptyConstantIdentifierPrivateIndex(); emptyConstantIdentifierPrivate(); emptyConstantQualifiedIdentifierPrivateIndex(); emptyConstantQualifiedIdentifierPrivate(); } } QDebug operator<<(QDebug s, const KDevelop::Identifier& identifier) { s.nospace() << identifier.toString(); return s.space(); } QDebug operator<<(QDebug s, const KDevelop::QualifiedIdentifier& identifier) { s.nospace() << identifier.toString(); return s.space(); } diff --git a/kdevplatform/language/duchain/importers.cpp b/kdevplatform/language/duchain/importers.cpp index 1515c7645e..b18e9a6aa1 100644 --- a/kdevplatform/language/duchain/importers.cpp +++ b/kdevplatform/language/duchain/importers.cpp @@ -1,213 +1,215 @@ /* This file is part of KDevelop Copyright 2008 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 "importers.h" #include "declarationid.h" #include "duchainpointer.h" #include "serialization/itemrepository.h" #include "topducontext.h" namespace KDevelop { DEFINE_LIST_MEMBER_HASH(ImportersItem, importers, IndexedDUContext) class ImportersItem { public: ImportersItem() { initializeAppendedLists(); } ImportersItem(const ImportersItem& rhs, bool dynamic = true) : declaration(rhs.declaration) { initializeAppendedLists(dynamic); copyListsFrom(rhs); } ~ImportersItem() { freeAppendedLists(); } + ImportersItem& operator=(const ImportersItem& rhs) = delete; + unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return declaration.hash(); } unsigned int itemSize() const { return dynamicSize(); } uint classSize() const { return sizeof(ImportersItem); } DeclarationId declaration; START_APPENDED_LISTS(ImportersItem); APPENDED_LIST_FIRST(ImportersItem, IndexedDUContext, importers); END_APPENDED_LISTS(ImportersItem, importers); }; class ImportersRequestItem { public: ImportersRequestItem(const ImportersItem& item) : m_item(item) { } enum { AverageSize = 30 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_item.hash(); } uint itemSize() const { return m_item.itemSize(); } void createItem(ImportersItem* item) const { new (item) ImportersItem(m_item, false); } static void destroy(ImportersItem* item, KDevelop::AbstractItemRepository&) { item->~ImportersItem(); } static bool persistent(const ImportersItem* /*item*/) { return true; } bool equals(const ImportersItem* item) const { return m_item.declaration == item->declaration; } const ImportersItem& m_item; }; class ImportersPrivate { public: ImportersPrivate() : m_importers(QStringLiteral("Importer Map")) { } //Maps declaration-ids to Importers // mutable as things like findIndex are not const mutable ItemRepository m_importers; }; Importers::Importers() : d_ptr(new ImportersPrivate()) { } Importers::~Importers() = default; void Importers::addImporter(const DeclarationId& id, const IndexedDUContext& use) { Q_D(Importers); ImportersItem item; item.declaration = id; item.importersList().append(use); ImportersRequestItem request(item); uint index = d->m_importers.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const ImportersItem* oldItem = d->m_importers.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->importersSize(); ++a) { if (oldItem->importers()[a] == use) return; //Already there item.importersList().append(oldItem->importers()[a]); } d->m_importers.deleteItem(index); } //This inserts the changed item d->m_importers.index(request); } void Importers::removeImporter(const DeclarationId& id, const IndexedDUContext& use) { Q_D(Importers); ImportersItem item; item.declaration = id; ImportersRequestItem request(item); uint index = d->m_importers.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const ImportersItem* oldItem = d->m_importers.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->importersSize(); ++a) if (!(oldItem->importers()[a] == use)) item.importersList().append(oldItem->importers()[a]); d->m_importers.deleteItem(index); Q_ASSERT(d->m_importers.findIndex(item) == 0); //This inserts the changed item if (item.importersSize() != 0) d->m_importers.index(request); } } KDevVarLengthArray Importers::importers(const DeclarationId& id) const { Q_D(const Importers); KDevVarLengthArray ret; ImportersItem item; item.declaration = id; ImportersRequestItem request(item); uint index = d->m_importers.findIndex(item); if (index) { const ImportersItem* repositoryItem = d->m_importers.itemFromIndex(index); FOREACH_FUNCTION(const IndexedDUContext &decl, repositoryItem->importers) ret.append(decl); } return ret; } Importers& Importers::self() { static Importers globalImporters; return globalImporters; } } diff --git a/kdevplatform/language/duchain/persistentsymboltable.cpp b/kdevplatform/language/duchain/persistentsymboltable.cpp index 99ffc48073..0c5c012a9b 100644 --- a/kdevplatform/language/duchain/persistentsymboltable.cpp +++ b/kdevplatform/language/duchain/persistentsymboltable.cpp @@ -1,489 +1,491 @@ /* This file is part of KDevelop Copyright 2008 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 "persistentsymboltable.h" #include #include "declaration.h" #include "declarationid.h" #include "appendedlist.h" #include "serialization/itemrepository.h" #include "identifier.h" #include "ducontext.h" #include "topducontext.h" #include "duchain.h" #include "duchainlock.h" #include //For now, just _always_ use the cache const uint MinimumCountForCache = 1; namespace { QDebug fromTextStream(const QTextStream& out) { if (out.device()) return { out.device() }; return { out.string() }; } } namespace KDevelop { Utils::BasicSetRepository* RecursiveImportCacheRepository::repository() { static Utils::BasicSetRepository recursiveImportCacheRepositoryObject(QStringLiteral( "Recursive Imports Cache"), nullptr, false); return &recursiveImportCacheRepositoryObject; } DEFINE_LIST_MEMBER_HASH(PersistentSymbolTableItem, declarations, IndexedDeclaration) class PersistentSymbolTableItem { public: PersistentSymbolTableItem() : centralFreeItem(-1) { initializeAppendedLists(); } PersistentSymbolTableItem(const PersistentSymbolTableItem& rhs, bool dynamic = true) : id(rhs.id) , centralFreeItem(rhs.centralFreeItem) { initializeAppendedLists(dynamic); copyListsFrom(rhs); } ~PersistentSymbolTableItem() { freeAppendedLists(); } + PersistentSymbolTableItem& operator=(const PersistentSymbolTableItem& rhs) = delete; + inline unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return id.index(); } unsigned int itemSize() const { return dynamicSize(); } uint classSize() const { return sizeof(PersistentSymbolTableItem); } IndexedQualifiedIdentifier id; int centralFreeItem; START_APPENDED_LISTS(PersistentSymbolTableItem); APPENDED_LIST_FIRST(PersistentSymbolTableItem, IndexedDeclaration, declarations); END_APPENDED_LISTS(PersistentSymbolTableItem, declarations); }; class PersistentSymbolTableRequestItem { public: PersistentSymbolTableRequestItem(const PersistentSymbolTableItem& item) : m_item(item) { } enum { AverageSize = 30 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_item.hash(); } uint itemSize() const { return m_item.itemSize(); } void createItem(PersistentSymbolTableItem* item) const { new (item) PersistentSymbolTableItem(m_item, false); } static void destroy(PersistentSymbolTableItem* item, KDevelop::AbstractItemRepository&) { item->~PersistentSymbolTableItem(); } static bool persistent(const PersistentSymbolTableItem*) { return true; //Nothing to do } bool equals(const PersistentSymbolTableItem* item) const { return m_item.id == item->id; } const PersistentSymbolTableItem& m_item; }; template struct CacheEntry { using Data = KDevVarLengthArray; using DataHash = QHash; DataHash m_hash; }; class PersistentSymbolTablePrivate { public: PersistentSymbolTablePrivate() : m_declarations(QStringLiteral("Persistent Declaration Table")) { } //Maps declaration-ids to declarations // mutable as things like findIndex are not const mutable ItemRepository m_declarations; mutable QHash> m_declarationsCache; //We cache the imports so the currently used nodes are very close in memory, which leads to much better CPU cache utilization mutable QHash m_importsCache; }; void PersistentSymbolTable::clearCache() { Q_D(PersistentSymbolTable); ENSURE_CHAIN_WRITE_LOCKED { QMutexLocker lock(d->m_declarations.mutex()); d->m_importsCache.clear(); d->m_declarationsCache.clear(); } } PersistentSymbolTable::PersistentSymbolTable() : d_ptr(new PersistentSymbolTablePrivate()) { } PersistentSymbolTable::~PersistentSymbolTable() { //Workaround for a strange destruction-order related crash duing shutdown //We just let the data leak. This doesn't hurt, as there is no meaningful destructors. // TODO: analyze and fix it // delete d; } void PersistentSymbolTable::addDeclaration(const IndexedQualifiedIdentifier& id, const IndexedDeclaration& declaration) { Q_D(PersistentSymbolTable); QMutexLocker lock(d->m_declarations.mutex()); ENSURE_CHAIN_WRITE_LOCKED d->m_declarationsCache.remove(id); PersistentSymbolTableItem item; item.id = id; PersistentSymbolTableRequestItem request(item); uint index = d->m_declarations.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const PersistentSymbolTableItem* oldItem = d->m_declarations.itemFromIndex(index); EmbeddedTreeAlgorithms alg( oldItem->declarations(), oldItem->declarationsSize(), oldItem->centralFreeItem); if (alg.indexOf(declaration) != -1) return; DynamicItem editableItem = d->m_declarations.dynamicItemFromIndex(index); EmbeddedTreeAddItem add( const_cast(editableItem->declarations()), editableItem->declarationsSize(), editableItem->centralFreeItem, declaration); uint newSize = add.newItemCount(); if (newSize != editableItem->declarationsSize()) { //We need to resize. Update and fill the new item, and delete the old item. item.declarationsList().resize(newSize); add.transferData(item.declarationsList().data(), newSize, &item.centralFreeItem); d->m_declarations.deleteItem(index); Q_ASSERT(!d->m_declarations.findIndex(request)); } else { //We're fine, the item could be added to the existing list return; } } else { item.declarationsList().append(declaration); } //This inserts the changed item d->m_declarations.index(request); } void PersistentSymbolTable::removeDeclaration(const IndexedQualifiedIdentifier& id, const IndexedDeclaration& declaration) { Q_D(PersistentSymbolTable); QMutexLocker lock(d->m_declarations.mutex()); ENSURE_CHAIN_WRITE_LOCKED d->m_declarationsCache.remove(id); Q_ASSERT(!d->m_declarationsCache.contains(id)); PersistentSymbolTableItem item; item.id = id; PersistentSymbolTableRequestItem request(item); uint index = d->m_declarations.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const PersistentSymbolTableItem* oldItem = d->m_declarations.itemFromIndex(index); EmbeddedTreeAlgorithms alg( oldItem->declarations(), oldItem->declarationsSize(), oldItem->centralFreeItem); if (alg.indexOf(declaration) == -1) return; DynamicItem editableItem = d->m_declarations.dynamicItemFromIndex(index); EmbeddedTreeRemoveItem remove( const_cast(editableItem->declarations()), editableItem->declarationsSize(), editableItem->centralFreeItem, declaration); uint newSize = remove.newItemCount(); if (newSize != editableItem->declarationsSize()) { //We need to resize. Update and fill the new item, and delete the old item. item.declarationsList().resize(newSize); remove.transferData(item.declarationsList().data(), newSize, &item.centralFreeItem); d->m_declarations.deleteItem(index); Q_ASSERT(!d->m_declarations.findIndex(request)); } else { //We're fine, the item could be added to the existing list return; } } //This inserts the changed item if (item.declarationsSize()) d->m_declarations.index(request); } struct DeclarationCacheVisitor { explicit DeclarationCacheVisitor(KDevVarLengthArray& _cache) : cache(_cache) { } bool operator()(const IndexedDeclaration& decl) const { cache.append(decl); return true; } KDevVarLengthArray& cache; }; PersistentSymbolTable::FilteredDeclarationIterator PersistentSymbolTable::filteredDeclarations( const IndexedQualifiedIdentifier& id, const TopDUContext::IndexedRecursiveImports& visibility) const { Q_D(const PersistentSymbolTable); QMutexLocker lock(d->m_declarations.mutex()); ENSURE_CHAIN_READ_LOCKED Declarations decls = declarations(id).iterator(); CachedIndexedRecursiveImports cachedImports; QHash::const_iterator it = d->m_importsCache.constFind(visibility); if (it != d->m_importsCache.constEnd()) { cachedImports = *it; } else { cachedImports = CachedIndexedRecursiveImports(visibility.set().stdSet()); d->m_importsCache.insert(visibility, cachedImports); } if (decls.dataSize() > MinimumCountForCache) { //Do visibility caching CacheEntry& cached(d->m_declarationsCache[id]); CacheEntry::DataHash::const_iterator cacheIt = cached.m_hash.constFind(visibility); if (cacheIt != cached.m_hash.constEnd()) return FilteredDeclarationIterator(Declarations::Iterator(cacheIt->constData(), cacheIt->size(), -1), cachedImports); CacheEntry::DataHash::iterator insertIt = cached.m_hash.insert(visibility, KDevVarLengthArray()); KDevVarLengthArray& cache(*insertIt); { using FilteredDeclarationCacheVisitor = ConvenientEmbeddedSetTreeFilterVisitor; //The visitor visits all the declarations from within its constructor DeclarationCacheVisitor v(cache); FilteredDeclarationCacheVisitor visitor(v, decls.iterator(), cachedImports); } return FilteredDeclarationIterator(Declarations::Iterator(cache.constData(), cache.size(), -1), cachedImports, true); } else { return FilteredDeclarationIterator(decls.iterator(), cachedImports); } } PersistentSymbolTable::Declarations PersistentSymbolTable::declarations(const IndexedQualifiedIdentifier& id) const { Q_D(const PersistentSymbolTable); QMutexLocker lock(d->m_declarations.mutex()); ENSURE_CHAIN_READ_LOCKED PersistentSymbolTableItem item; item.id = id; uint index = d->m_declarations.findIndex(item); if (index) { const PersistentSymbolTableItem* repositoryItem = d->m_declarations.itemFromIndex(index); return PersistentSymbolTable::Declarations(repositoryItem->declarations(), repositoryItem->declarationsSize(), repositoryItem->centralFreeItem); } else { return PersistentSymbolTable::Declarations(); } } void PersistentSymbolTable::declarations(const IndexedQualifiedIdentifier& id, uint& countTarget, const IndexedDeclaration*& declarationsTarget) const { Q_D(const PersistentSymbolTable); QMutexLocker lock(d->m_declarations.mutex()); ENSURE_CHAIN_READ_LOCKED PersistentSymbolTableItem item; item.id = id; uint index = d->m_declarations.findIndex(item); if (index) { const PersistentSymbolTableItem* repositoryItem = d->m_declarations.itemFromIndex(index); countTarget = repositoryItem->declarationsSize(); declarationsTarget = repositoryItem->declarations(); } else { countTarget = 0; declarationsTarget = nullptr; } } struct DebugVisitor { explicit DebugVisitor(const QTextStream& _out) : out(_out) { } bool operator()(const PersistentSymbolTableItem* item) { QDebug qout = fromTextStream(out); QualifiedIdentifier id(item->id.identifier()); if (identifiers.contains(id)) { qout << "identifier" << id.toString() << "appears for" << identifiers[id] << "th time"; } ++identifiers[id]; for (uint a = 0; a < item->declarationsSize(); ++a) { IndexedDeclaration decl(item->declarations()[a]); if (!decl.isDummy()) { if (declarations.contains(decl)) { qout << "declaration found for multiple identifiers. Previous identifier:" << declarations[decl].toString() << "current identifier:" << id.toString() << endl; } else { declarations.insert(decl, id); } } if (decl.data() && decl.data()->qualifiedIdentifier() != item->id.identifier()) { qout << decl.data()->url().str() << "declaration" << decl.data()->qualifiedIdentifier() << "is registered as" << item->id.identifier() << endl; } const QString url = IndexedTopDUContext(decl.topContextIndex()).url().str(); if (!decl.data() && !decl.isDummy()) { qout << "Item in symbol-table is invalid:" << id.toString() << "- localIndex:" << decl.localIndex() << "- url:" << url << endl; } else { qout << "Item in symbol-table:" << id.toString() << "- localIndex:" << decl.localIndex() << "- url:" << url; if (auto d = decl.data()) { qout << "- range:" << d->range(); } else { qout << "- null declaration"; } qout << endl; } } return true; } const QTextStream& out; QHash identifiers; QHash declarations; }; void PersistentSymbolTable::dump(const QTextStream& out) { Q_D(PersistentSymbolTable); { QMutexLocker lock(d->m_declarations.mutex()); QDebug qout = fromTextStream(out); DebugVisitor v(out); d->m_declarations.visitAllItems(v); qout << "Statistics:" << endl; qout << d->m_declarations.statistics() << endl; } } PersistentSymbolTable& PersistentSymbolTable::self() { static PersistentSymbolTable ret; return ret; } } diff --git a/kdevplatform/language/duchain/uses.cpp b/kdevplatform/language/duchain/uses.cpp index 3d05c2ba0b..a175e68204 100644 --- a/kdevplatform/language/duchain/uses.cpp +++ b/kdevplatform/language/duchain/uses.cpp @@ -1,216 +1,218 @@ /* This file is part of KDevelop Copyright 2008 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 "uses.h" #include "declarationid.h" #include "duchainpointer.h" #include "serialization/itemrepository.h" #include "topducontext.h" namespace KDevelop { DEFINE_LIST_MEMBER_HASH(UsesItem, uses, IndexedTopDUContext) class UsesItem { public: UsesItem() { initializeAppendedLists(); } UsesItem(const UsesItem& rhs, bool dynamic = true) : declaration(rhs.declaration) { initializeAppendedLists(dynamic); copyListsFrom(rhs); } ~UsesItem() { freeAppendedLists(); } + UsesItem& operator=(const UsesItem& rhs) = delete; + unsigned int hash() const { //We only compare the declaration. This allows us implementing a map, although the item-repository //originally represents a set. return declaration.hash(); } unsigned int itemSize() const { return dynamicSize(); } uint classSize() const { return sizeof(UsesItem); } DeclarationId declaration; START_APPENDED_LISTS(UsesItem); APPENDED_LIST_FIRST(UsesItem, IndexedTopDUContext, uses); END_APPENDED_LISTS(UsesItem, uses); }; class UsesRequestItem { public: UsesRequestItem(const UsesItem& item) : m_item(item) { } enum { AverageSize = 30 //This should be the approximate average size of an Item }; unsigned int hash() const { return m_item.hash(); } uint itemSize() const { return m_item.itemSize(); } void createItem(UsesItem* item) const { new (item) UsesItem(m_item, false); } static void destroy(UsesItem* item, KDevelop::AbstractItemRepository&) { item->~UsesItem(); } static bool persistent(const UsesItem* /*item*/) { return true; } bool equals(const UsesItem* item) const { return m_item.declaration == item->declaration; } const UsesItem& m_item; }; class UsesPrivate { public: UsesPrivate() : m_uses(QStringLiteral("Use Map")) { } //Maps declaration-ids to Uses // mutable as things like findIndex are not const mutable ItemRepository m_uses; }; Uses::Uses() : d_ptr(new UsesPrivate()) { } Uses::~Uses() = default; void Uses::addUse(const DeclarationId& id, const IndexedTopDUContext& use) { Q_D(Uses); UsesItem item; item.declaration = id; item.usesList().append(use); UsesRequestItem request(item); uint index = d->m_uses.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const UsesItem* oldItem = d->m_uses.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->usesSize(); ++a) { if (oldItem->uses()[a] == use) return; //Already there item.usesList().append(oldItem->uses()[a]); } d->m_uses.deleteItem(index); } //This inserts the changed item d->m_uses.index(request); } void Uses::removeUse(const DeclarationId& id, const IndexedTopDUContext& use) { Q_D(Uses); UsesItem item; item.declaration = id; UsesRequestItem request(item); uint index = d->m_uses.findIndex(item); if (index) { //Check whether the item is already in the mapped list, else copy the list into the new created item const UsesItem* oldItem = d->m_uses.itemFromIndex(index); for (unsigned int a = 0; a < oldItem->usesSize(); ++a) if (!(oldItem->uses()[a] == use)) item.usesList().append(oldItem->uses()[a]); d->m_uses.deleteItem(index); Q_ASSERT(d->m_uses.findIndex(item) == 0); //This inserts the changed item if (item.usesSize() != 0) d->m_uses.index(request); } } bool Uses::hasUses(const DeclarationId& id) const { Q_D(const Uses); UsesItem item; item.declaration = id; return ( bool ) d->m_uses.findIndex(item); } KDevVarLengthArray Uses::uses(const DeclarationId& id) const { Q_D(const Uses); KDevVarLengthArray ret; UsesItem item; item.declaration = id; UsesRequestItem request(item); uint index = d->m_uses.findIndex(item); if (index) { const UsesItem* repositoryItem = d->m_uses.itemFromIndex(index); FOREACH_FUNCTION(const IndexedTopDUContext &decl, repositoryItem->uses) ret.append(decl); } return ret; } } diff --git a/kdevplatform/language/editor/modificationrevisionset.cpp b/kdevplatform/language/editor/modificationrevisionset.cpp index 347f1eaf93..339f830fa8 100644 --- a/kdevplatform/language/editor/modificationrevisionset.cpp +++ b/kdevplatform/language/editor/modificationrevisionset.cpp @@ -1,361 +1,363 @@ /* Copyright 2008 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 "modificationrevisionset.h" #include #include #include #include //When uncommented, the reason for needed updates is printed // #define DEBUG_NEEDSUPDATE namespace KDevelop { QMutex modificationRevisionSetMutex(QMutex::Recursive); struct FileModificationPair { KDevelop::IndexedString file; KDevelop::ModificationRevision revision; FileModificationPair() { } FileModificationPair(const KDevelop::IndexedString& _file, KDevelop::ModificationRevision _revision) : file(_file) , revision(_revision) { } + FileModificationPair& operator=(const FileModificationPair& rhs) = delete; + unsigned int hash() const { return ((file.hash() + revision.modificationTime) * 17 + revision.revision) * 73; } unsigned short int itemSize() const { return sizeof(FileModificationPair); } bool operator==(const FileModificationPair& rhs) const { return file == rhs.file && revision == rhs.revision; } }; struct FileModificationPairRequest { FileModificationPairRequest(const FileModificationPair& data) : m_data(data) { } const FileModificationPair& m_data; enum { AverageSize = sizeof(FileModificationPair) }; unsigned int hash() const { return m_data.hash(); } uint itemSize() const { return m_data.itemSize(); } void createItem(FileModificationPair* item) const { new (item) FileModificationPair(m_data); } bool equals(const FileModificationPair* item) const { return *item == m_data; } static void destroy(FileModificationPair* item, KDevelop::AbstractItemRepository&) { item->~FileModificationPair(); } static bool persistent(const FileModificationPair* /*item*/) { return true; //Reference-counting is done implicitly using the set-repository } }; using FileModificationPairRepository = KDevelop::ItemRepository; static FileModificationPairRepository& fileModificationPairRepository() { static FileModificationPairRepository rep(QStringLiteral("file modification repository")); rep.setMutex(&modificationRevisionSetMutex); return rep; } void initModificationRevisionSetRepository() { fileModificationPairRepository(); } QHash> needsUpdateCache; void ModificationRevisionSet::clearCache() { QMutexLocker lock(&modificationRevisionSetMutex); ///@todo More intelligent clearing. We actually need to watch the directory for changes, and if there are changes, clear the cache. needsUpdateCache.clear(); } struct FileModificationSetRepository : public Utils::BasicSetRepository { FileModificationSetRepository() : Utils::BasicSetRepository(QStringLiteral( "file modification sets"), &globalItemRepositoryRegistry(), true) { } void itemRemovedFromSets(uint index) override; }; //FileModificationSetRepository fileModificationSetRepository; struct FileModificationSetRepositoryRepresenter { static FileModificationSetRepository& repository() { static FileModificationSetRepository fileModificationSetRepository; return fileModificationSetRepository; } }; ModificationRevisionSet::ModificationRevisionSet(unsigned int index) : m_index(index) { } uint ModificationRevisionSet::size() const { Utils::Set set = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); return set.count(); } void ModificationRevisionSet::clear() { QMutexLocker lock(&modificationRevisionSetMutex); if (m_index) { Utils::Set oldModificationTimes = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); oldModificationTimes.staticUnref(); m_index = 0; } } void ModificationRevisionSet::addModificationRevision(const IndexedString& url, const KDevelop::ModificationRevision& revision) { QMutexLocker lock(&modificationRevisionSetMutex); if (m_index == 0) { Utils::Set set = FileModificationSetRepositoryRepresenter::repository().createSet( fileModificationPairRepository().index(FileModificationPair(url, revision))); set.staticRef(); m_index = set.setIndex(); } else { Utils::Set oldModificationTimes = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set newModificationTimes = oldModificationTimes; Utils::Set tempSet = FileModificationSetRepositoryRepresenter::repository().createSet( fileModificationPairRepository().index(FileModificationPair(url, revision))); tempSet.staticRef(); newModificationTimes += tempSet; newModificationTimes.staticRef(); oldModificationTimes.staticUnref(); tempSet.staticUnref(); m_index = newModificationTimes.setIndex(); } } bool ModificationRevisionSet::removeModificationRevision(const IndexedString& url, const KDevelop::ModificationRevision& revision) { QMutexLocker lock(&modificationRevisionSetMutex); if (!m_index) return false; Utils::Set oldModificationTimes = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set newModificationTimes = oldModificationTimes; Utils::Set tempSet = FileModificationSetRepositoryRepresenter::repository().createSet( fileModificationPairRepository().index(FileModificationPair(url, revision))); tempSet.staticRef(); newModificationTimes -= tempSet; newModificationTimes.staticRef(); oldModificationTimes.staticUnref(); tempSet.staticUnref(); m_index = newModificationTimes.setIndex(); return m_index != oldModificationTimes.setIndex(); } // const QMap ModificationRevisionSet::allModificationTimes() const { // QMap ret; // Utils::Set::Iterator it = m_allModificationTimes.iterator(); // while(it) { // const FileModificationPair* data = fileModificationPairRepository().itemFromIndex(*it); // ret[data->file] = data->revision; // ++it; // } // return ret; // } using ModificationRevisionSetNode = Utils::VirtualSetNode, FileModificationSetRepositoryRepresenter>; // static bool (const Utils::SetNodeData* node) { // ModificationRevisionSetNode // if(!node) // return false; // } static bool nodeNeedsUpdate(uint index) { QMutexLocker lock(&modificationRevisionSetMutex); if (!index) return false; const auto currentTime = QDateTime::currentDateTime(); auto cached = needsUpdateCache.constFind(index); if (cached != needsUpdateCache.constEnd()) { if ((*cached).first.secsTo(currentTime) < cacheModificationTimesForSeconds) { return cached->second; } } bool result = false; const Utils::SetNodeData* nodeData = FileModificationSetRepositoryRepresenter::repository().nodeFromIndex(index); if (nodeData->contiguous()) { //Do the actual checking for (unsigned int a = nodeData->start(); a < nodeData->end(); ++a) { const FileModificationPair* data = fileModificationPairRepository().itemFromIndex(a); ModificationRevision revision = KDevelop::ModificationRevision::revisionForFile(data->file); if (revision != data->revision) { result = true; break; } } } else { result = nodeNeedsUpdate(nodeData->leftNode()) || nodeNeedsUpdate(nodeData->rightNode()); } needsUpdateCache.insert(index, std::make_pair(currentTime, result)); return result; } QString ModificationRevisionSet::toString() const { QMutexLocker lock(&modificationRevisionSetMutex); Utils::Set set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set::Iterator it = set.iterator(); QStringList revisions; while (it) { const FileModificationPair* data = fileModificationPairRepository().itemFromIndex(*it); revisions.append(data->file.str() + QLatin1Char(':') + data->revision.toString()); ++it; } QString ret = QLatin1Char('[') + revisions.join(QLatin1String(", ")) + QLatin1Char(']'); return ret; } bool ModificationRevisionSet::needsUpdate() const { QMutexLocker lock(&modificationRevisionSetMutex); #ifdef DEBUG_NEEDSUPDATE Utils::Set set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set::Iterator it = set.iterator(); while (it) { const FileModificationPair* data = fileModificationPairRepository().itemFromIndex(*it); ModificationRevision revision = KDevelop::ModificationRevision::revisionForFile(data->file); if (revision != data->revision) { qCDebug(LANGUAGE) << "dependency" << data->file.str() << "has changed, stored stamp:" << data->revision << "new time:" << revision; return true; } ++it; } return false; #else return nodeNeedsUpdate(m_index); #endif } ModificationRevisionSet& ModificationRevisionSet::operator+=(const ModificationRevisionSet& rhs) { QMutexLocker lock(&modificationRevisionSetMutex); Utils::Set oldModificationTimes = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set otherModificationTimes = Utils::Set(rhs.m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set newModificationTimes = oldModificationTimes; newModificationTimes += otherModificationTimes; newModificationTimes.staticRef(); oldModificationTimes.staticUnref(); m_index = newModificationTimes.setIndex(); return *this; } ModificationRevisionSet& ModificationRevisionSet::operator-=(const ModificationRevisionSet& rhs) { QMutexLocker lock(&modificationRevisionSetMutex); Utils::Set oldModificationTimes = Utils::Set(m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set otherModificationTimes = Utils::Set(rhs.m_index, &FileModificationSetRepositoryRepresenter::repository()); Utils::Set newModificationTimes = oldModificationTimes; newModificationTimes -= otherModificationTimes; newModificationTimes.staticRef(); oldModificationTimes.staticUnref(); m_index = newModificationTimes.setIndex(); return *this; } void FileModificationSetRepository::itemRemovedFromSets(uint index) { fileModificationPairRepository().deleteItem(index); needsUpdateCache.remove(index); } } diff --git a/kdevplatform/serialization/indexedstring.cpp b/kdevplatform/serialization/indexedstring.cpp index 8bb025163b..73228e2ae3 100644 --- a/kdevplatform/serialization/indexedstring.cpp +++ b/kdevplatform/serialization/indexedstring.cpp @@ -1,406 +1,408 @@ /* This file is part of KDevelop Copyright 2008 David Nolden Copyright 2016 Milian Wolff 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. 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, see . */ #include "indexedstring.h" #include "serialization/stringrepository.h" #include "referencecounting.h" using namespace KDevelop; namespace { struct IndexedStringData { unsigned short length; uint refCount; + IndexedStringData& operator=(const IndexedStringData& rhs) = delete; + uint itemSize() const { return sizeof(IndexedStringData) + length; } uint hash() const { IndexedString::RunningHash running; const char* str = (( const char* )this) + sizeof(IndexedStringData); for (int a = length - 1; a >= 0; --a) { running.append(*str); ++str; } return running.hash; } }; inline void increase(uint& val) { ++val; } inline void decrease(uint& val) { --val; } struct IndexedStringRepositoryItemRequest { //The text is supposed to be utf8 encoded IndexedStringRepositoryItemRequest(const char* text, uint hash, unsigned short length) : m_hash(hash) , m_length(length) , m_text(text) { } enum { AverageSize = 10 //This should be the approximate average size of an Item }; using HashType = uint; //Should return the hash-value associated with this request(For example the hash of a string) HashType hash() const { return m_hash; } //Should return the size of an item created with createItem uint itemSize() const { return sizeof(IndexedStringData) + m_length; } //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 createItem(IndexedStringData* item) const { item->length = m_length; item->refCount = 0; ++item; memcpy(item, m_text, m_length); } static void destroy(IndexedStringData* item, AbstractItemRepository&) { Q_UNUSED(item); //Nothing to do here (The object is not intelligent) } static bool persistent(const IndexedStringData* item) { return ( bool )item->refCount; } //Should return whether the here requested item equals the given item bool equals(const IndexedStringData* item) const { return item->length == m_length && (memcmp(++item, m_text, m_length) == 0); } uint m_hash; unsigned short m_length; const char* m_text; }; inline const char* c_strFromItem(const IndexedStringData* item) { return reinterpret_cast(item + 1); } ///@param item must be valid(nonzero) inline QString stringFromItem(const IndexedStringData* item) { return QString::fromUtf8(c_strFromItem(item), item->length); } inline QByteArray arrayFromItem(const IndexedStringData* item) { return QByteArray(c_strFromItem(item), item->length); } inline bool isSingleCharIndex(uint index) { return (index & 0xffff0000) == 0xffff0000; } inline uint charToIndex(char c) { return 0xffff0000 | c; } inline char indexToChar(uint index) { Q_ASSERT(isSingleCharIndex(index)); return static_cast(index & 0xff); } using IndexedStringRepository = ItemRepository; using IndexedStringRepositoryManagerBase = RepositoryManager; class IndexedStringRepositoryManager : public IndexedStringRepositoryManagerBase { public: IndexedStringRepositoryManager() : IndexedStringRepositoryManagerBase(QStringLiteral("String Index")) { repository()->setMutex(&m_mutex); } private: // non-recursive mutex to increase speed QMutex m_mutex; }; IndexedStringRepository* globalIndexedStringRepository() { static IndexedStringRepositoryManager manager; return manager.repository(); } template auto readRepo(ReadAction action)->decltype(action(globalIndexedStringRepository())) { const auto* repo = globalIndexedStringRepository(); QMutexLocker lock(repo->mutex()); return action(repo); } template auto editRepo(EditAction action)->decltype(action(globalIndexedStringRepository())) { auto* repo = globalIndexedStringRepository(); QMutexLocker lock(repo->mutex()); return action(repo); } inline void ref(IndexedString* string) { const uint index = string->index(); if (index && !isSingleCharIndex(index)) { if (shouldDoDUChainReferenceCounting(string)) { editRepo([index](IndexedStringRepository* repo) { increase(repo->dynamicItemFromIndexSimple(index)->refCount); }); } } } inline void deref(IndexedString* string) { const uint index = string->index(); if (index && !isSingleCharIndex(index)) { if (shouldDoDUChainReferenceCounting(string)) { editRepo([index](IndexedStringRepository* repo) { decrease(repo->dynamicItemFromIndexSimple(index)->refCount); }); } } } } IndexedString::IndexedString() { } ///@param str must be a utf8 encoded string, does not need to be 0-terminated. ///@param length must be its length in bytes. IndexedString::IndexedString(const char* str, unsigned short length, uint hash) { if (!length) { m_index = 0; } else if (length == 1) { m_index = charToIndex(str[0]); } else { const auto request = IndexedStringRepositoryItemRequest(str, hash ? hash : hashString(str, length), length); bool refcount = shouldDoDUChainReferenceCounting(this); m_index = editRepo([request, refcount](IndexedStringRepository* repo) { auto index = repo->index(request); if (refcount) { increase(repo->dynamicItemFromIndexSimple(index)->refCount); } return index; }); } } IndexedString::IndexedString(char c) : m_index(charToIndex(c)) {} IndexedString::IndexedString(const QUrl& url) : IndexedString(url.isLocalFile() ? url.toLocalFile() : url.toString()) { Q_ASSERT(url.isEmpty() || !url.isRelative()); #if !defined(QT_NO_DEBUG) if (url != url.adjusted(QUrl::NormalizePathSegments)) { qWarning() << "wrong url" << url << url.adjusted(QUrl::NormalizePathSegments); } #endif Q_ASSERT(url == url.adjusted(QUrl::NormalizePathSegments)); } IndexedString::IndexedString(const QString& string) : IndexedString(string.toUtf8()) {} IndexedString::IndexedString(const char* str) : IndexedString(str, str ? qstrlen(str) : 0) {} IndexedString::IndexedString(const QByteArray& str) : IndexedString(str.constData(), str.length()) {} IndexedString::~IndexedString() { deref(this); } IndexedString::IndexedString(const IndexedString& rhs) : m_index(rhs.m_index) { ref(this); } IndexedString& IndexedString::operator=(const IndexedString& rhs) { if (m_index == rhs.m_index) { return *this; } deref(this); m_index = rhs.m_index; ref(this); return *this; } QUrl IndexedString::toUrl() const { if (isEmpty()) { return {}; } QUrl ret = QUrl::fromUserInput(str()); Q_ASSERT(!ret.isRelative()); return ret; } QString IndexedString::str() const { if (!m_index) { return QString(); } else if (isSingleCharIndex(m_index)) { return QString(QLatin1Char(indexToChar(m_index))); } else { const uint index = m_index; return readRepo([index](const IndexedStringRepository* repo) { return stringFromItem(repo->itemFromIndex(index)); }); } } int IndexedString::length() const { return lengthFromIndex(m_index); } int IndexedString::lengthFromIndex(uint index) { if (!index) { return 0; } else if (isSingleCharIndex(index)) { return 1; } else { return readRepo([index](const IndexedStringRepository* repo) { return repo->itemFromIndex(index)->length; }); } } const char* IndexedString::c_str() const { if (!m_index) { return nullptr; } else if (isSingleCharIndex(m_index)) { #if Q_BYTE_ORDER == Q_LITTLE_ENDIAN const uint offset = 0; #else const uint offset = 3; #endif return reinterpret_cast(&m_index) + offset; } else { const uint index = m_index; return readRepo([index](const IndexedStringRepository* repo) { return c_strFromItem(repo->itemFromIndex(index)); }); } } QByteArray IndexedString::byteArray() const { if (!m_index) { return QByteArray(); } else if (isSingleCharIndex(m_index)) { return QByteArray(1, indexToChar(m_index)); } else { const uint index = m_index; return readRepo([index](const IndexedStringRepository* repo) { return arrayFromItem(repo->itemFromIndex(index)); }); } } uint IndexedString::hashString(const char* str, unsigned short length) { RunningHash running; for (int a = length - 1; a >= 0; --a) { running.append(*str); ++str; } return running.hash; } uint IndexedString::indexForString(const char* str, short unsigned length, uint hash) { if (!length) { return 0; } else if (length == 1) { return charToIndex(str[0]); } else { const auto request = IndexedStringRepositoryItemRequest(str, hash ? hash : hashString(str, length), length); return editRepo([request](IndexedStringRepository* repo) { return repo->index(request); }); } } uint IndexedString::indexForString(const QString& str, uint hash) { const QByteArray array(str.toUtf8()); return indexForString(array.constBegin(), array.size(), hash); } QDebug operator<<(QDebug s, const IndexedString& string) { s.nospace() << string.str(); return s.space(); } diff --git a/kdevplatform/serialization/referencecounting.cpp b/kdevplatform/serialization/referencecounting.cpp index 067b73e776..b5e9ea49d1 100644 --- a/kdevplatform/serialization/referencecounting.cpp +++ b/kdevplatform/serialization/referencecounting.cpp @@ -1,275 +1,277 @@ /* * This file is part of KDevelop * * Copyright 2009 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 "referencecounting.h" #include #include #include #include "serialization/itemrepository.h" namespace KDevelop { bool doReferenceCounting = false; //Protects the reference-counting data through a spin-lock QMutex refCountingLock; QMap>* refCountingRanges = new QMap>(); //ptr, , leaked intentionally! bool refCountingHasAdditionalRanges = false; //Whether 'refCountingRanges' is non-empty //Speedup: In most cases there is only exactly one reference-counted range active, //so the first reference-counting range can be marked here. void* refCountingFirstRangeStart = nullptr; QPair refCountingFirstRangeExtent = qMakePair(0u, 0u); } void KDevelop::disableDUChainReferenceCounting(void* start) { QMutexLocker lock(&refCountingLock); if (refCountingFirstRangeStart && (( char* )refCountingFirstRangeStart) <= ( char* )start && ( char* )start < (( char* )refCountingFirstRangeStart) + refCountingFirstRangeExtent.first) { Q_ASSERT(refCountingFirstRangeExtent.second > 0); --refCountingFirstRangeExtent.second; if (refCountingFirstRangeExtent.second == 0) { refCountingFirstRangeExtent = qMakePair(0, 0); refCountingFirstRangeStart = nullptr; } } else if (refCountingHasAdditionalRanges) { QMap>::iterator it = refCountingRanges->upperBound(start); if (it != refCountingRanges->begin()) { --it; if ((( char* )it.key()) <= ( char* )start && ( char* )start < (( char* )it.key()) + it.value().first) { //Contained } else { Q_ASSERT(0); } } Q_ASSERT(it.value().second > 0); --it.value().second; if (it.value().second == 0) refCountingRanges->erase(it); refCountingHasAdditionalRanges = !refCountingRanges->isEmpty(); } else { Q_ASSERT(0); } if (!refCountingFirstRangeStart && !refCountingHasAdditionalRanges) doReferenceCounting = false; } void KDevelop::enableDUChainReferenceCounting(void* start, unsigned int size) { QMutexLocker lock(&refCountingLock); doReferenceCounting = true; if (refCountingFirstRangeStart && (( char* )refCountingFirstRangeStart) <= ( char* )start && ( char* )start < (( char* )refCountingFirstRangeStart) + refCountingFirstRangeExtent.first) { //Increase the count for the first range ++refCountingFirstRangeExtent.second; } else if (refCountingHasAdditionalRanges || refCountingFirstRangeStart) { //There is additional ranges in the ranges-structure. Add any new ranges there as well. QMap>::iterator it = refCountingRanges->upperBound(start); if (it != refCountingRanges->begin()) { --it; if ((( char* )it.key()) <= ( char* )start && ( char* )start < (( char* )it.key()) + it.value().first) { //Contained, count up } else { it = refCountingRanges->end(); //Insert own item } } else if (it != refCountingRanges->end() && it.key() > start) { //The item is behind it = refCountingRanges->end(); } if (it == refCountingRanges->end()) { QMap>::iterator inserted = refCountingRanges->insert(start, qMakePair(size, 1u)); //Merge following ranges QMap>::iterator it = inserted; ++it; while (it != refCountingRanges->end() && it.key() < (( char* )start) + size) { inserted.value().second += it.value().second; //Accumulate count if ((( char* )start) + size < (( char* )inserted.key()) + it.value().first) { //Update end position inserted.value().first = ((( char* )inserted.key()) + it.value().first) - (( char* )start); } it = refCountingRanges->erase(it); } } else { ++it.value().second; if (it.value().first < size) it.value().first = size; } refCountingHasAdditionalRanges = true; } else { refCountingFirstRangeStart = start; refCountingFirstRangeExtent.first = size; refCountingFirstRangeExtent.second = 1; } Q_ASSERT(refCountingHasAdditionalRanges == (refCountingRanges && !refCountingRanges->isEmpty())); #ifdef TEST_REFERENCE_COUNTING Q_ASSERT(shouldDoDUChainReferenceCounting(start)); Q_ASSERT(shouldDoDUChainReferenceCounting((( char* )start + (size - 1)))); #endif } #ifdef TEST_REFERENCE_COUNTING QAtomicInt& id() { static QAtomicInt& ret(KDevelop::globalItemRepositoryRegistry().getCustomCounter("referencer ids", 1)); return ret; } namespace KDevelop { ReferenceCountManager::ReferenceCountManager() : m_id(id().fetchAndAddRelaxed(1)) { } struct ReferenceCountItem { ///Item entries: ReferenceCountItem(uint id, uint target) : m_id(id) , m_targetId(target) { } + ReferenceCountItem& operator=(const ReferenceCountItem& rhs) = delete; + //Every item has to implement this function, and return a valid hash. //Must be exactly the same hash value as ReferenceCountItemRequest::hash() has returned while creating the item. unsigned int hash() const { return KDevHash() << m_id << m_targetId; } //Every item has to implement this function, and return the complete size this item takes in memory. //Must be exactly the same value as ReferenceCountItemRequest::itemSize() has returned while creating the item. unsigned short int itemSize() const { return sizeof(ReferenceCountItem); } uint m_id; uint m_targetId; ///Request entries: enum { AverageSize = 8 }; void createItem(ReferenceCountItem* item) const { * item = *this; } static void destroy(ReferenceCountItem* /*item*/, AbstractItemRepository&) { } static bool persistent(const ReferenceCountItem*) { return true; } bool equals(const ReferenceCountItem* item) const { return m_id == item->m_id && m_targetId == item->m_targetId; } }; static RepositoryManager, false>& references() { static RepositoryManager, false> referencesObject("Reference Count Debugging"); return referencesObject; } static RepositoryManager, false>& oldReferences() { static RepositoryManager, false> oldReferencesObject("Old Reference Count Debugging"); return oldReferencesObject; } void KDevelop::initReferenceCounting() { references(); oldReferences(); } ReferenceCountManager::~ReferenceCountManager() { //Make sure everything is cleaned up when the object is destroyed // Q_ASSERT(!references().contains(m_id)); } ReferenceCountManager::ReferenceCountManager(const ReferenceCountManager& rhs) : m_id(id().fetchAndAddRelaxed(1)) { //New id } ReferenceCountManager& ReferenceCountManager::ReferenceCountManager::operator=(const ReferenceCountManager& rhs) { //Keep id return *this; } // bool ReferenceCountManager::hasReferenceCount() const { // return references->findIndex(ReferenceCountItem); // } void ReferenceCountManager::increase(uint& ref, uint targetId) { Q_ASSERT(shouldDoDUChainReferenceCounting(this)); Q_ASSERT(!references->findIndex(ReferenceCountItem(m_id, targetId))); ++ref; { int oldIndex = oldReferences->findIndex(ReferenceCountItem(m_id, targetId)); if (oldIndex) oldReferences->deleteItem(oldIndex); } Q_ASSERT(references->index(ReferenceCountItem(m_id, targetId))); } void ReferenceCountManager::decrease(uint& ref, uint targetId) { Q_ASSERT(ref > 0); Q_ASSERT(shouldDoDUChainReferenceCounting(this)); Q_ASSERT(!oldReferences->findIndex(ReferenceCountItem(m_id, targetId))); uint refIndex = references->findIndex(ReferenceCountItem(m_id, targetId)); Q_ASSERT(refIndex); --ref; references->deleteItem(refIndex); oldReferences->index(ReferenceCountItem(m_id, targetId)); } } #else namespace KDevelop { void initReferenceCounting() { } } #endif diff --git a/kdevplatform/serialization/stringrepository.h b/kdevplatform/serialization/stringrepository.h index 4863784e8e..817fa2cbea 100644 --- a/kdevplatform/serialization/stringrepository.h +++ b/kdevplatform/serialization/stringrepository.h @@ -1,120 +1,123 @@ /* Copyright 2008 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. */ #ifndef KDEVPLATFORM_STRINGREPOSITORY_H #define KDEVPLATFORM_STRINGREPOSITORY_H #include #include "itemrepository.h" #include "indexedstring.h" namespace Repositories { using namespace KDevelop; struct StringData { unsigned short length; + + StringData& operator=(const StringData& rhs) = delete; + unsigned int itemSize() const { return sizeof(StringData) + length; } unsigned int hash() const { IndexedString::RunningHash running; const char* str = (( const char* )this) + sizeof(StringData); for (int a = length - 1; a >= 0; --a) { running.append(*str); ++str; } return running.hash; } }; struct StringRepositoryItemRequest { //The text is supposed to be utf8 encoded StringRepositoryItemRequest(const char* text, unsigned int hash, unsigned short length) : m_hash(hash) , m_length(length) , m_text(text) { } enum { AverageSize = 10 //This should be the approximate average size of an Item }; using HashType = unsigned int; //Should return the hash-value associated with this request(For example the hash of a string) HashType hash() const { return m_hash; } //Should return the size of an item created with createItem uint itemSize() const { return sizeof(StringData) + m_length; } //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 createItem(StringData* item) const { item->length = m_length; ++item; memcpy(item, m_text, m_length); } static void destroy(StringData*, KDevelop::AbstractItemRepository&) { } static bool persistent(const StringData*) { //Reference-counting not supported in the normal string repository return true; } //Should return whether the here requested item equals the given item bool equals(const StringData* item) const { return item->length == m_length && (memcmp(++item, m_text, m_length) == 0); } unsigned int m_hash; unsigned short m_length; const char* m_text; }; using StringRepository = ItemRepository; ///@param item must be valid(nonzero) inline QString stringFromItem(const StringData* item) { const unsigned short* textPos = ( unsigned short* )(item + 1); return QString::fromUtf8(( char* )textPos, item->length); } inline QByteArray arrayFromItem(const StringData* item) { const unsigned short* textPos = ( unsigned short* )(item + 1); return QByteArray(( char* )textPos, item->length); } } #endif diff --git a/kdevplatform/serialization/tests/bench_itemrepository.cpp b/kdevplatform/serialization/tests/bench_itemrepository.cpp index d5f1a90058..b4a7285c1c 100644 --- a/kdevplatform/serialization/tests/bench_itemrepository.cpp +++ b/kdevplatform/serialization/tests/bench_itemrepository.cpp @@ -1,221 +1,224 @@ /* * This file is part of KDevelop * Copyright 2012-2013 Milian Wolff * * 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) version 3 or any later version * accepted by the membership of KDE e.V. (or its successor approved * by the membership of KDE e.V.), which shall act as a proxy * defined in Section 14 of version 3 of the license. * * 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, see . */ #include "bench_itemrepository.h" #include #include #include #include QTEST_GUILESS_MAIN(BenchItemRepository) using namespace KDevelop; struct TestData { uint length; + + TestData& operator=(const TestData& rhs) = delete; + uint itemSize() const { return sizeof(TestData) + length; } uint hash() const { const char* str = (( const char* )this) + sizeof(TestData); return IndexedString::hashString(str, length); } }; struct TestDataRepositoryItemRequest { //The text is supposed to be utf8 encoded TestDataRepositoryItemRequest(const char* text, uint length) : m_length(length) , m_text(text) , m_hash(IndexedString::hashString(text, length)) { } enum { AverageSize = 10 //This should be the approximate average size of an Item }; using HashType = uint; //Should return the hash-value associated with this request(For example the hash of a string) HashType hash() const { return m_hash; } //Should return the size of an item created with createItem uint itemSize() const { return sizeof(TestData) + m_length; } //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 createItem(TestData* item) const { item->length = m_length; ++item; memcpy(item, m_text, m_length); } static void destroy(TestData* item, AbstractItemRepository&) { Q_UNUSED(item); //Nothing to do here (The object is not intelligent) } static bool persistent(const TestData* item) { Q_UNUSED(item); return true; } //Should return whether the here requested item equals the given item bool equals(const TestData* item) const { return item->length == m_length && (memcmp(++item, m_text, m_length) == 0); } unsigned short m_length; const char* m_text; unsigned int m_hash; }; using TestDataRepository = ItemRepository; void BenchItemRepository::initTestCase() { ItemRepositoryRegistry::initialize(m_repositoryPath); } void BenchItemRepository::cleanupTestCase() { ItemRepositoryRegistry::deleteRepositoryFromDisk(m_repositoryPath); } static QVector generateData() { QVector data; static const int NUM_ITEMS = 100000; data.resize(NUM_ITEMS); for (int i = 0; i < NUM_ITEMS; ++i) { data[i] = QStringLiteral("/foo/%1").arg(i); } return data; } static QVector insertData(const QVector& data, TestDataRepository& repo) { QVector indices; indices.reserve(data.size()); for (const QString& item : data) { const QByteArray byteArray = item.toUtf8(); indices << repo.index(TestDataRepositoryItemRequest(byteArray.constData(), byteArray.length())); } return indices; } void BenchItemRepository::insert() { TestDataRepository repo("TestDataRepositoryInsert"); const QVector data = generateData(); QVector indices; QBENCHMARK_ONCE { indices = insertData(data, repo); repo.store(); } Q_ASSERT(indices.size() == data.size()); QCOMPARE(repo.statistics().totalItems, uint(data.size())); } void BenchItemRepository::remove() { TestDataRepository repo("TestDataRepositoryRemove"); const QVector data = generateData(); const QVector indices = insertData(data, repo); repo.store(); QVERIFY(indices.size() == indices.toList().toSet().size()); QVERIFY(indices.size() == data.size()); QBENCHMARK_ONCE { for (uint index : indices) { repo.deleteItem(index); } repo.store(); } QCOMPARE(repo.statistics().totalItems, 0u); } void BenchItemRepository::removeDisk() { const QVector data = generateData(); QVector indices; { TestDataRepository repo("TestDataRepositoryRemoveDisk"); indices = insertData(data, repo); repo.store(); } TestDataRepository repo("TestDataRepositoryRemoveDisk"); QVERIFY(repo.statistics().totalItems == static_cast(data.size())); QBENCHMARK_ONCE { for (uint index : qAsConst(indices)) { repo.deleteItem(index); } repo.store(); } QCOMPARE(repo.statistics().totalItems, 0u); } void BenchItemRepository::lookupKey() { TestDataRepository repo("TestDataRepositoryLookupKey"); const QVector data = generateData(); QVector indices = insertData(data, repo); srand(0); std::random_shuffle(indices.begin(), indices.end()); QBENCHMARK { for (uint index : qAsConst(indices)) { repo.itemFromIndex(index); } } } void BenchItemRepository::lookupValue() { TestDataRepository repo("TestDataRepositoryLookupValue"); const QVector data = generateData(); QVector indices = insertData(data, repo); srand(0); std::random_shuffle(indices.begin(), indices.end()); QBENCHMARK { for (const QString& item : data) { const QByteArray byteArray = item.toUtf8(); repo.findIndex(TestDataRepositoryItemRequest(byteArray.constData(), byteArray.length())); } } } diff --git a/kdevplatform/serialization/tests/test_itemrepository.cpp b/kdevplatform/serialization/tests/test_itemrepository.cpp index 05e4e7973c..e5f6ec17ef 100644 --- a/kdevplatform/serialization/tests/test_itemrepository.cpp +++ b/kdevplatform/serialization/tests/test_itemrepository.cpp @@ -1,391 +1,394 @@ #include #include #include #include #include #include using namespace KDevelop; struct TestItem { TestItem(uint hash, uint dataSize) : m_hash(hash) , m_dataSize(dataSize) { } + + TestItem& operator=(const TestItem& rhs) = delete; + //Every item has to implement this function, and return a valid hash. //Must be exactly the same hash value as ExampleItemRequest::hash() has returned while creating the item. unsigned int hash() const { return m_hash; } //Every item has to implement this function, and return the complete size this item takes in memory. //Must be exactly the same value as ExampleItemRequest::itemSize() has returned while creating the item. unsigned int itemSize() const { return sizeof(TestItem) + m_dataSize; } bool equals(const TestItem* rhs) const { return rhs->m_hash == m_hash && itemSize() == rhs->itemSize() && memcmp(( char* )this, rhs, itemSize()) == 0; } uint m_hash; uint m_dataSize; }; struct TestItemRequest { TestItem& m_item; bool m_compareData; TestItemRequest(TestItem& item, bool compareData = false) : m_item(item) , m_compareData(compareData) { } enum { AverageSize = 700 //This should be the approximate average size of an Item }; uint hash() const { return m_item.hash(); } //Should return the size of an item created with createItem size_t itemSize() const { return m_item.itemSize(); } void createItem(TestItem* item) const { memcpy(item, &m_item, m_item.itemSize()); } static void destroy(TestItem* /*item*/, AbstractItemRepository&) { //Nothing to do } static bool persistent(const TestItem* /*item*/) { return true; } //Should return whether the here requested item equals the given item bool equals(const TestItem* item) const { return hash() == item->hash() && (!m_compareData || m_item.equals(item)); } }; uint smallItemsFraction = 20; //Fraction of items betwen 0 and 1 kb uint largeItemsFraction = 1; //Fraction of items between 0 and 200 kb uint cycles = 10000; uint deletionProbability = 1; //Percentual probability that a checked item is deleted. Per-cycle probability must be multiplied with checksPerCycle. uint checksPerCycle = 10; TestItem* createItem(uint id, uint size) { TestItem* ret; char* data = new char[size]; uint dataSize = size - sizeof(TestItem); ret = new (data) TestItem(id, dataSize); //Fill in same random pattern for (uint a = 0; a < dataSize; ++a) data[sizeof(TestItem) + a] = ( char )(a + id); return ret; } ///@todo Add a test where the complete content is deleted again, and make sure the result has a nice structure ///@todo More consistency and lost-space tests, especially about monster-buckets. Make sure their space is re-claimed class TestItemRepository : public QObject { Q_OBJECT private Q_SLOTS: void initTestCase() { ItemRepositoryRegistry::initialize(m_repositoryPath); } void cleanupTestCase() { ItemRepositoryRegistry::deleteRepositoryFromDisk(m_repositoryPath); } void testItemRepository() { ItemRepository repository(QStringLiteral("TestItemRepository")); uint itemId = 0; QHash realItemsByIndex; QHash realItemsById; uint totalInsertions = 0, totalDeletions = 0; uint maxSize = 0; uint totalSize = 0; srand(time(nullptr)); uint highestSeenIndex = 0; for (uint a = 0; a < cycles; ++a) { { //Insert an item uint itemDecision = rand() % (smallItemsFraction + largeItemsFraction); uint itemSize; if (itemDecision < largeItemsFraction) { //Create a large item: Up to 200kb itemSize = (rand() % 200000) + sizeof(TestItem); } else itemSize = (rand() % 1000) + sizeof(TestItem); TestItem* item = createItem(++itemId, itemSize); Q_ASSERT(item->hash() == itemId); QVERIFY(item->equals(item)); uint index = repository.index(TestItemRequest(*item)); if (index > highestSeenIndex) highestSeenIndex = index; Q_ASSERT(index); realItemsByIndex.insert(index, item); realItemsById.insert(itemId, item); ++totalInsertions; totalSize += itemSize; if (itemSize > maxSize) maxSize = itemSize; } for (uint a = 0; a < checksPerCycle; ++a) { //Check an item uint pick = rand() % itemId; if (realItemsById.contains(pick)) { uint index = repository.findIndex(*realItemsById[pick]); QVERIFY(index); QVERIFY(realItemsByIndex.contains(index)); QVERIFY(realItemsByIndex[index]->equals(repository.itemFromIndex(index))); if (( uint ) (rand() % 100) < deletionProbability) { ++totalDeletions; //Delete the item repository.deleteItem(index); QVERIFY(!repository.findIndex(*realItemsById[pick])); uint newIndex = repository.index(*realItemsById[pick]); QVERIFY(newIndex); QVERIFY(realItemsByIndex[index]->equals(repository.itemFromIndex(newIndex))); #ifdef POSITION_TEST //Since we have previously deleted the item, there must be enough space if (!((newIndex >> 16) <= (highestSeenIndex >> 16))) { qDebug() << "size:" << realItemsById[pick]->itemSize(); qDebug() << "previous highest seen bucket:" << (highestSeenIndex >> 16); qDebug() << "new bucket:" << (newIndex >> 16); } QVERIFY((newIndex >> 16) <= (highestSeenIndex >> 16)); #endif repository.deleteItem(newIndex); QVERIFY(!repository.findIndex(*realItemsById[pick])); delete[] realItemsById[pick]; realItemsById.remove(pick); realItemsByIndex.remove(index); } } } } // cleanup { for (auto it = realItemsByIndex.constBegin(); it != realItemsByIndex.constEnd(); ++it) { repository.deleteItem(it.key()); delete[] it.value(); } realItemsById.clear(); realItemsByIndex.clear(); } qDebug() << "total insertions:" << totalInsertions << "total deletions:" << totalDeletions << "average item size:" << (totalSize / totalInsertions) << "biggest item size:" << maxSize; ItemRepository::Statistics stats = repository.statistics(); qDebug() << stats; QVERIFY(stats.freeUnreachableSpace < stats.freeSpaceInBuckets / 100); // < 1% of the free space is unreachable QVERIFY(stats.freeSpaceInBuckets < stats.usedSpaceForBuckets); // < 20% free space } void testLeaks() { ItemRepository repository(QStringLiteral("TestItemRepository")); QList items; for (int i = 0; i < 10000; ++i) { TestItem* item = createItem(i, (rand() % 1000) + sizeof(TestItem)); items << item; repository.index(TestItemRequest(*item)); } for (auto item : qAsConst(items)) { delete[] item; } } void testStringSharing() { QString qString; qString.fill('.', 1000); IndexedString indexedString(qString); const int repeat = 10000; QVector strings; strings.resize(repeat); for (int i = 0; i < repeat; ++i) { strings[i] = indexedString.str(); QCOMPARE(qString, strings[i]); } } void deleteClashingMonsterBucket() { ItemRepository repository(QStringLiteral("TestItemRepository")); const uint hash = 1235; QScopedArrayPointer monsterItem(createItem(hash, ItemRepositoryBucketSize + 10)); QScopedArrayPointer smallItem(createItem(hash, 20)); QVERIFY(!monsterItem->equals(smallItem.data())); uint smallIndex = repository.index(TestItemRequest(*smallItem, true)); uint monsterIndex = repository.index(TestItemRequest(*monsterItem, true)); QVERIFY(monsterIndex != smallIndex); repository.deleteItem(smallIndex); QVERIFY(!repository.findIndex(TestItemRequest(*smallItem, true))); QCOMPARE(monsterIndex, repository.findIndex(TestItemRequest(*monsterItem, true))); repository.deleteItem(monsterIndex); // now in reverse order, with different data see: https://bugs.kde.org/show_bug.cgi?id=272408 monsterItem.reset(createItem(hash + 1, ItemRepositoryBucketSize + 10)); smallItem.reset(createItem(hash + 1, 20)); QVERIFY(!monsterItem->equals(smallItem.data())); monsterIndex = repository.index(TestItemRequest(*monsterItem, true)); smallIndex = repository.index(TestItemRequest(*smallItem, true)); repository.deleteItem(monsterIndex); QCOMPARE(smallIndex, repository.findIndex(TestItemRequest(*smallItem, true))); QVERIFY(!repository.findIndex(TestItemRequest(*monsterItem, true))); repository.deleteItem(smallIndex); } void usePermissiveModuloWhenRemovingClashLinks() { ItemRepository repository(QStringLiteral("PermissiveModulo")); const uint bucketHashSize = decltype(repository)::bucketHashSize; const uint nextBucketHashSize = decltype(repository)::MyBucket::NextBucketHashSize; auto bucketNumberForIndex = [](const uint index) { return index >> 16; }; const uint clashValue = 2; // Choose sizes that ensure that the items fit in the desired buckets const uint bigItemSize = ItemRepositoryBucketSize * 0.55 - 1; const uint smallItemSize = ItemRepositoryBucketSize * 0.25 - 1; // Will get placed in bucket 1 (bucket zero is invalid), so the root bucket table at position 'clashValue' will be '1' const QScopedArrayPointer firstChainFirstLink(createItem(clashValue, bigItemSize)); const uint firstChainFirstLinkIndex = repository.index(*firstChainFirstLink); QCOMPARE(bucketNumberForIndex(firstChainFirstLinkIndex), 1u); // Will also get placed in bucket 1, so root bucket table at position 'nextBucketHashSize + clashValue' will be '1' const QScopedArrayPointer secondChainFirstLink(createItem(nextBucketHashSize + clashValue, smallItemSize)); const uint secondChainFirstLinkIndex = repository.index(*secondChainFirstLink); QCOMPARE(bucketNumberForIndex(secondChainFirstLinkIndex), 1u); // Will get placed in bucket 2, so bucket 1's next hash table at position 'clashValue' will be '2' const QScopedArrayPointer firstChainSecondLink(createItem(bucketHashSize + clashValue, bigItemSize)); const uint firstChainSecondLinkIndex = repository.index(*firstChainSecondLink); QCOMPARE(bucketNumberForIndex(firstChainSecondLinkIndex), 2u); // Will also get placed in bucket 2, reachable since bucket 1's next hash table at position 'clashValue' is '2' const QScopedArrayPointer secondChainSecondLink(createItem( bucketHashSize + nextBucketHashSize + clashValue, smallItemSize)); const uint secondChainSecondLinkIndex = repository.index(*secondChainSecondLink); QCOMPARE(bucketNumberForIndex(secondChainSecondLinkIndex), 2u); /* * At this point we have two chains in the repository, rooted at 'clashValue' and 'nextBucketHashSize + clashValue' * Both of the chains start in bucket 1 and end in bucket 2, but both chains share the same link to bucket 2 * This is because two of the hashes clash the other two when % bucketHashSize, but all of them clash % nextBucketHashSize */ repository.deleteItem(firstChainSecondLinkIndex); /* * Now we've deleted the second item in the first chain, this means the first chain no longer requires a link to the * second bucket where that item was... but the link must remain, since it's shared (clashed) by the second chain. * * When cutting a link out of the middle of the chain, we need to check if its items clash using the "permissive" * modulus (the size of the /next/ buckets map), which is always a factor of the "stricter" modulus (the size of the * /root/ buckets map). * * This behavior implies that there will sometimes be useless buckets in the bucket chain for a given hash, so when * cutting out the root link, it's safe to skip over them to the first clash with the 'stricter' modulus. */ // The second item of the second chain must still be reachable QCOMPARE(repository.findIndex(*secondChainSecondLink), secondChainSecondLinkIndex); /* * As a memo to anyone who's still reading this, this also means the following situation can exist: * * bucketHashSize == 8 * nextBucketHashSize == 4 * U is a link table * B is a bucket * [...] are the hashes of the contained items * * U * U * U -> B1 * U * U * U * U -> B2 * U * * B0 (Invalid) * B1 -> [2, 6] * U * U * U -> B3 * U * B2 -> [14] * U * U * U -> B1 * U * B3 -> [10] * U * U * U * U * * The chain for hash 6 is: * Root[6] -> B2[2] -> B1[2] -> B3 * * If you remove the item with hash 6, 6 and 2 will clash with mod 4 (permissive) * * So the useless link `B2[2] -> B1` will be preserved, even though its useless * as the item with hash 2 is reachable directly from the root. * * So TODO: Don't preserve links to items accessible from root buckets. This cannot * be done correctly using only Bucket::hasClashingItem as of now. */ } private: QString m_repositoryPath = QDir::tempPath() + QStringLiteral("/test_itemrepository"); }; #include "test_itemrepository.moc" QTEST_MAIN(TestItemRepository)