diff --git a/CMakeLists.txt b/CMakeLists.txt index b05df09..af2f7a1 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -1,174 +1,175 @@ CMAKE_MINIMUM_REQUIRED(VERSION 3.0) PROJECT(kquickview) IF(POLICY CMP0063) CMAKE_POLICY(SET CMP0063 NEW) ENDIF(POLICY CMP0063) FIND_PACKAGE(ECM 1.1.0 REQUIRED NO_MODULE) LIST(APPEND CMAKE_MODULE_PATH "${ECM_MODULE_PATH}") OPTION(BUILD_SHARED_LIBS "" OFF ) INCLUDE(ECMInstallIcons) INCLUDE(ECMOptionalAddSubdirectory) INCLUDE(KDEInstallDirs) INCLUDE(KDECMakeSettings) INCLUDE(KDECompilerSettings) if(NOT BUILD_SHARED_LIBS) set(STATIC_LIBRARY 1) else() set(STATIC_LIBRARY 0) endif() SET(CMAKE_AUTOMOC ON) SET(CMAKE_AUTORCC ON) SET(CMAKE_CXX_STANDARD 14) # if(STATIC_LIBRARY) add_definitions(-DQT_PLUGIN) add_definitions(-DQT_STATICPLUGIN=1) # else(STATIC_LIBRARY) # if (BUILD_TESTING) # add_subdirectory(autotests) # endif() # endif(STATIC_LIBRARY) FIND_PACKAGE(Qt5 CONFIG REQUIRED Core Gui Quick QuickControls2 ) add_definitions(-isystem ${Qt5Core_PRIVATE_INCLUDE_DIRS}) if("${CMAKE_BUILD_TYPE}" MATCHES "DEBUG") add_definitions(-DENABLE_EXTRA_VALIDATION=1) endif() SET(GENERIC_LIB_VERSION "1.0.0") #File to compile SET( kquickview_LIB_SRCS # Adapters src/adapters/abstractitemadapter.cpp src/adapters/decorationadapter.cpp src/adapters/modeladapter.cpp src/adapters/scrollbaradapter.cpp src/adapters/selectionadapter.cpp src/adapters/geometryadapter.cpp # Building blocks src/flickablescrollbar.cpp src/plugin.cpp src/proxies/sizehintproxymodel.cpp src/singlemodelviewbase.cpp src/viewbase.cpp src/viewport.cpp src/contextadapterfactory.cpp src/qmodelindexwatcher.cpp src/qmodelindexbinder.cpp # Views src/views/comboboxview.cpp src/views/flickable.cpp src/views/hierarchyview.cpp src/views/listview.cpp src/views/treeview.cpp src/views/indexview.cpp # State trackers src/private/statetracker/index_p.cpp src/private/statetracker/geometry_p.cpp src/private/statetracker/proximity_p.cpp src/private/statetracker/model_p.cpp src/private/statetracker/modelitem_p.cpp src/private/statetracker/selection_p.cpp src/private/statetracker/content_p.cpp + src/private/statetracker/continuity_p.cpp src/private/runtimetests_p.cpp src/private/indexmetadata_p.cpp src/private/geostrategyselector_p.cpp # Geometry strategies src/strategies/justintime.cpp src/strategies/proxy.cpp src/strategies/role.cpp src/strategies/delegate.cpp src/strategies/uniform.cpp src/strategies/aheadoftime.cpp ) set(AUTOMOC_MOC_OPTIONS -Muri=org.kde.playground.kquickview) add_library(kquickview STATIC ${kquickview_LIB_SRCS} ) target_link_libraries( kquickview Qt5::Core Qt5::Gui Qt5::Quick Qt5::QuickControls2 ) SET( kquickview_LIB_HDRS adapters/abstractitemadapter.h adapters/contextadapter.h adapters/decorationadapter.h adapters/modeladapter.h adapters/scrollbaradapter.h adapters/selectionadapter.h adapters/geometryadapter.h extensions/contextextension.h flickablescrollbar.h plugin.h proxies/sizehintproxymodel.h singlemodelviewbase.h contextadapterfactory.h qmodelindexwatcher.h qmodelindexbinder.h viewbase.h views/comboboxview.h views/flickable.h views/indexview.h views/hierarchyview.h views/listview.h views/treeview.h viewport.h # Geometry strategies strategies/justintime.h strategies/proxy.h strategies/role.h strategies/delegate.h strategies/aheadoftime.h strategies/uniform.h ) # Create include file aliases foreach(header ${kquickview_LIB_HDRS}) file(COPY ${CMAKE_CURRENT_SOURCE_DIR}/src/${header} DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/api/KQuickView/ ) endforeach() target_include_directories(kquickview PUBLIC "${CMAKE_CURRENT_SOURCE_DIR}/src;${CMAKE_CURRENT_BINARY_DIR}/api" ) set_target_properties(kquickview PROPERTIES INCLUDE_DIRECTORIES "${CMAKE_CURRENT_BINARY_DIR}/api;${CMAKE_CURRENT_SOURCE_DIR}/src" ) set_target_properties(kquickview PROPERTIES PUBLIC_HEADER "${CMAKE_CURRENT_BINARY_DIR}/api;${CMAKE_CURRENT_SOURCE_DIR}/src" ) add_subdirectory(tests) include_directories(${CMAKE_CURRENT_BINARY_DIR}/api/) diff --git a/src/private/statetracker/content_p.cpp b/src/private/statetracker/content_p.cpp index 37543cd..eb12f82 100644 --- a/src/private/statetracker/content_p.cpp +++ b/src/private/statetracker/content_p.cpp @@ -1,1009 +1,1041 @@ /*************************************************************************** * Copyright (C) 2017-2018 by Emmanuel Lepage Vallee * * Author : Emmanuel Lepage Vallee * * * * 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 3 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 "content_p.h" // KQuickItemViews #include "viewitem_p.h" #include "proximity_p.h" #include "model_p.h" #include "modelitem_p.h" #include #include #include +#include #include // Qt #include using EdgeType = IndexMetadata::EdgeType; namespace StateTracker { class Index; class Model; class Content; } class AbstractItemAdapter; class ModelRect; #include #include class ContentPrivate : public QObject { Q_OBJECT public: explicit ContentPrivate(); // Helpers StateTracker::ModelItem* addChildren(const QModelIndex& index); StateTracker::ModelItem* ttiForIndex(const QModelIndex& idx) const; bool isInsertActive(const QModelIndex& p, int first, int last) const; QList setTemporaryIndices(const QModelIndex &parent, int start, int end, const QModelIndex &destination, int row); void resetTemporaryIndices(const QList&); void reloadEdges(); StateTracker::ModelItem *m_pRoot {nullptr}; //TODO add a circular buffer to GC the items // * relative index: when to trigger GC // * absolute array index: kept in the StateTracker::ModelItem so it can // remove itself /// All elements with loaded children QHash m_hMapper; QModelIndex getNextIndex(const QModelIndex& idx) const; ModelRect m_lRects[3]; StateTracker::Model *m_pModelTracker; Viewport *m_pViewport; StateTracker::Content* q_ptr; // Update the ModelRect void insertEdge(IndexMetadata *, StateTracker::ModelItem::State); void removeEdge(IndexMetadata *, StateTracker::ModelItem::State); void enterState(IndexMetadata *, StateTracker::ModelItem::State); void leaveState(IndexMetadata *, StateTracker::ModelItem::State); void error (IndexMetadata *, StateTracker::ModelItem::State); void resetState(IndexMetadata *, StateTracker::ModelItem::State); typedef void(ContentPrivate::*StateFS)(IndexMetadata*, StateTracker::ModelItem::State); static const StateFS m_fStateLogging[8][2]; public Q_SLOTS: void slotCleanup(); void slotRowsInserted (const QModelIndex& parent, int first, int last); void slotRowsRemoved (const QModelIndex& parent, int first, int last); void slotLayoutChanged ( ); void slotDataChanged (const QModelIndex& tl, const QModelIndex& br, const QVector &roles ); void slotRowsMoved (const QModelIndex &p, int start, int end, const QModelIndex &dest, int row); }; #define A &ContentPrivate:: // Keep track of the number of instances per state const ContentPrivate::StateFS ContentPrivate::m_fStateLogging[8][2] = { /* ENTER LEAVE */ /*NEW */ { A error , A leaveState }, /*BUFFER */ { A enterState, A leaveState }, /*REMOVED */ { A enterState, A leaveState }, /*REACHABLE*/ { A enterState, A leaveState }, /*VISIBLE */ { A insertEdge, A removeEdge }, /*ERROR */ { A enterState, A leaveState }, /*DANGLING */ { A enterState, A error }, /*MOVING */ { A enterState, A resetState }, }; #undef A void ContentPrivate::insertEdge(IndexMetadata *md, StateTracker::ModelItem::State s) { auto tti = md->modelTracker(); Q_UNUSED(s) const auto first = q_ptr->edges(EdgeType::VISIBLE)->getEdge( Qt::TopEdge ); const auto last = q_ptr->edges(EdgeType::VISIBLE)->getEdge( Qt::BottomEdge ); const auto prev = tti->up(); const auto next = tti->down(); if (first == next) q_ptr->setEdge(EdgeType::VISIBLE, tti, Qt::TopEdge); if (last == prev) q_ptr->setEdge(EdgeType::VISIBLE, tti, Qt::BottomEdge); _DO_TEST(_test_validate_edges_simple, q_ptr) } void ContentPrivate::removeEdge(IndexMetadata *md, StateTracker::ModelItem::State s) { Q_UNUSED(s) auto tti = md->modelTracker(); const auto first = q_ptr->edges(EdgeType::VISIBLE)->getEdge(Qt::TopEdge); const auto last = q_ptr->edges(EdgeType::VISIBLE)->getEdge(Qt::BottomEdge); // The item was somewhere in between, not an edge case if ((tti != first) && (tti != last)) return; auto prev = tti->up(); auto next = tti->down(); if (tti == first) q_ptr->setEdge(EdgeType::VISIBLE, (next && next->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::VISIBLE) ? next : nullptr, Qt::TopEdge ); if (tti == last) q_ptr->setEdge(EdgeType::VISIBLE, (prev && prev->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::VISIBLE) ? prev : nullptr, Qt::BottomEdge ); _DO_TEST(_test_validate_edges_simple, q_ptr) } /** * This method is called when an item moves into a new area and the "real" * new state needs to be determined. */ void ContentPrivate::resetState(IndexMetadata *i, StateTracker::ModelItem::State) { i->modelTracker()->rebuildState(); } ContentPrivate::ContentPrivate() {} StateTracker::Content::Content(Viewport* parent) : QObject(parent), d_ptr(new ContentPrivate()) { d_ptr->m_pViewport = parent; d_ptr->m_pRoot = new StateTracker::ModelItem(parent); d_ptr->m_pModelTracker = new StateTracker::Model(this); d_ptr->q_ptr = this; } StateTracker::Content::~Content() { delete d_ptr->m_pModelTracker; d_ptr->m_pModelTracker = nullptr; delete d_ptr->m_pRoot; } void ContentPrivate::slotRowsInserted(const QModelIndex& parent, int first, int last) { // This method uses modelCandidate() because it needs to be called during // initilization (thus not always directly by QAbstractItemModel::rowsInserted Q_ASSERT(((!parent.isValid()) || parent.model() == m_pModelTracker->modelCandidate()) && first <= last); // It is the job of isInsertActive to decide what's correct if (!isInsertActive(parent, first, last)) { _DO_TEST(_test_validateLinkedList, q_ptr) return; } const auto pitem = parent.isValid() ? m_hMapper.value(parent) : m_pRoot; //FIXME it is possible if the anchor is at the bottom that the parent // needs to be loaded. But this is currently too not supported. if (!pitem) { _DO_TEST(_test_validateLinkedList, q_ptr) return; } StateTracker::Index *prev = nullptr; //FIXME use up() if (first && pitem) prev = pitem->childrenLookup(m_pModelTracker->modelCandidate()->index(first-1, 0, parent)); // There is no choice here but to load a larger subset to avoid holes, in // theory, edges(EdgeType::FREE)->m_Edges will prevent runaway loading if (pitem->firstChild()) last = std::max(last, pitem->firstChild()->effectiveRow() - 1); if (prev && prev->down()) { m_pViewport->s_ptr->notifyInsert(prev->down()->metadata()); //Q_ASSERT(!TTI(prev->down())->metadata()->isValid()); } else if ((!prev) && (!pitem) && m_pRoot->firstChild()) { Q_ASSERT((!first) && !parent.isValid()); m_pViewport->s_ptr->notifyInsert(m_pRoot->firstChild()->metadata()); //Q_ASSERT(!TTI(m_pRoot->firstChild())->metadata()->isValid()); } else if (pitem && pitem != m_pRoot && pitem->down()) { //Q_ASSERT(!first); m_pViewport->s_ptr->notifyInsert(pitem->down()->metadata()); //TODO check if this one is still correct, right now notifyInsert update the geo //Q_ASSERT(!TTI(pitem->down())->metadata()->isValid()); } //FIXME support smaller ranges for (int i = first; i <= last; i++) { auto idx = m_pModelTracker->modelCandidate()->index(i, 0, parent); Q_ASSERT(idx.isValid() && idx.parent() != idx && idx.model() == m_pModelTracker->modelCandidate()); // If the insertion is sandwiched between loaded items, not doing it // will corrupt the view, but if it's a "tail" insertion, then they // can be discarded. if (!(q_ptr->edges(EdgeType::FREE)->m_Edges & (Qt::BottomEdge | Qt::TopEdge))) { const auto nextIdx = getNextIndex(idx); const auto nextTTI = nextIdx.isValid() ? ttiForIndex(nextIdx) : nullptr; if (!nextTTI) { m_pViewport->s_ptr->refreshVisible(); _DO_TEST(_test_validateLinkedList, q_ptr) return; //FIXME break } } auto e = addChildren(idx); if (pitem->firstChild() && pitem->firstChild()->effectiveRow() == idx.row()+1) { Q_ASSERT(idx.parent() == pitem->firstChild()->effectiveParentIndex()); // m_pViewport->s_ptr->notifyInsert(&TTI(pitem->firstChild())->m_Geometry); StateTracker::Index::insertChildBefore(e, pitem->firstChild(), pitem); } else { StateTracker::Index::insertChildAfter(e, prev, pitem); //FIXME incorrect // m_pViewport->s_ptr->notifyInsert(&TTI(prev)->m_Geometry); } //FIXME It can happen if the previous is out of the visible range Q_ASSERT( e->previousSibling() || e->nextSibling() || e->effectiveRow() == 0); //TODO merge with bridgeGap if (prev) { StateTracker::Index::bridgeGap(prev, e); _DO_TEST_IDX(_test_validate_chain, prev->parent()) } // This is required before ::ATTACH because otherwise ::down() wont work Q_ASSERT((!pitem->firstChild()) || !pitem->firstChild()->hasTemporaryIndex()); //TODO const bool needDownMove = (!pitem->lastChild()) || e->effectiveRow() > pitem->lastChild()->effectiveRow(); const bool needUpMove = (!pitem->firstChild()) || e->effectiveRow() < pitem->firstChild()->effectiveRow(); _DO_TEST_IDX(_test_validate_chain, e->parent()) // The item is about the current parent first item if (needUpMove) { // Q_ASSERT(false); //TODO merge with the other bridgeGap above m_pViewport->s_ptr->notifyInsert(m_pRoot->firstChild()->metadata()); Q_ASSERT((!m_pRoot->firstChild()) || !m_pRoot->firstChild()->metadata()->isValid()); StateTracker::Index::insertChildBefore(e, nullptr, pitem); } _DO_TEST_IDX(_test_validate_chain, e->parent()) Q_ASSERT(e->metadata()->geometryTracker()->state() == StateTracker::Geometry::State::INIT); Q_ASSERT(e->state() != StateTracker::ModelItem::State::VISIBLE); // NEW -> REACHABLE, this should never fail if (!e->metadata()->performAction(IndexMetadata::LoadAction::ATTACH)) { qDebug() << "\n\nATTACH FAILED"; _DO_TEST(_test_validateLinkedList, q_ptr) break; } if (needUpMove) { Q_ASSERT(pitem != e); if (auto pe = e->up()) pe->metadata() << IndexMetadata::LoadAction::MOVE; } Q_ASSERT((!pitem->lastChild()) || !pitem->lastChild()->hasTemporaryIndex()); //TODO if (needDownMove) { if (auto ne = e->down()) { Q_ASSERT(!ne->metadata()->isValid()); ne->metadata() << IndexMetadata::LoadAction::MOVE; Q_ASSERT(!ne->metadata()->isValid()); } } int rc = m_pModelTracker->modelCandidate()->rowCount(idx); if (rc && q_ptr->edges(EdgeType::FREE)->m_Edges & Qt::BottomEdge) { slotRowsInserted(idx, 0, rc-1); } // Validate early to prevent propagating garbage that's nearly impossible // to debug. if (pitem && pitem != m_pRoot && !i) { Q_ASSERT(e->up() == pitem); Q_ASSERT(e == pitem->down()); } prev = e; } m_pViewport->s_ptr->refreshVisible(); _DO_TEST(_test_validateLinkedList, q_ptr) _DO_TEST_IDX(_test_validate_chain, pitem) Q_EMIT q_ptr->contentChanged(); } void ContentPrivate::slotRowsRemoved(const QModelIndex& parent, int first, int last) { Q_ASSERT((!parent.isValid()) || parent.model() == m_pModelTracker->modelCandidate()); if (!q_ptr->isActive(parent, first, last)) { _DO_TEST(_test_validateLinkedList, q_ptr) _DO_TEST(_test_validateUnloaded, q_ptr, parent, first, last) return; } auto pitem = parent.isValid() ? m_hMapper.value(parent) : m_pRoot; if (!pitem) return; //TODO make sure the state machine support them //StateTracker::ModelItem *prev(nullptr), *next(nullptr); //FIXME use up() //if (first && pitem) // prev = pitem->m_hLookup.value(model()->index(first-1, 0, parent)); //next = pitem->m_hLookup.value(model()->index(last+1, 0, parent)); //FIXME support smaller ranges for (int i = first; i <= last; i++) { auto idx = m_pModelTracker->modelCandidate()->index(i, 0, parent); if (auto elem = pitem->childrenLookup(idx)) { elem->metadata() << IndexMetadata::LoadAction::HIDE << IndexMetadata::LoadAction::DETACH; } } Q_EMIT q_ptr->contentChanged(); } //TODO optimize this void ContentPrivate::slotDataChanged(const QModelIndex& tl, const QModelIndex& br, const QVector &roles) { Q_UNUSED(roles) if (!q_ptr->isActive(tl.parent(), tl.row(), br.row())) return; for (int i = tl.row(); i <= br.row(); i++) { const auto idx = m_pModelTracker->modelCandidate()->index(i, tl.column(), tl.parent()); if (auto tti = ttiForIndex(idx)) { if (tti->metadata()->viewTracker()) { tti->metadata()->contextAdapter()->updateRoles(roles); tti->metadata() << IndexMetadata::ViewAction::UPDATE; } } } } void ContentPrivate::slotLayoutChanged() { if (auto rc = m_pModelTracker->modelCandidate()->rowCount()) slotRowsInserted({}, 0, rc - 1); Q_EMIT q_ptr->contentChanged(); } void ContentPrivate::slotRowsMoved(const QModelIndex &parent, int start, int end, const QModelIndex &destination, int row) { Q_ASSERT((!parent.isValid()) || parent.model() == m_pModelTracker->modelCandidate()); Q_ASSERT((!destination.isValid()) || destination.model() == m_pModelTracker->modelCandidate()); // There is literally nothing to do if (parent == destination && start == row) return; // Whatever has to be done only affect a part that's not currently tracked. if (!q_ptr->isActive(destination, row, row)) { //Q_ASSERT(false); //TODO so I don't forget return; } auto tmp = setTemporaryIndices(parent, start, end, destination, row); // As the actual view is implemented as a daisy chained list, only moving // the edges is necessary for the StateTracker::ModelItem. Each StateTracker::ViewItem // need to be moved. const auto idxStart = m_pModelTracker->modelCandidate()->index(start, 0, parent); const auto idxEnd = m_pModelTracker->modelCandidate()->index(end , 0, parent); Q_ASSERT(idxStart.isValid() && idxEnd.isValid()); //FIXME once partial ranges are supported, this is no longer always valid auto startTTI = ttiForIndex(idxStart); auto endTTI = ttiForIndex(idxEnd); if (end - start == 1) Q_ASSERT(startTTI->nextSibling() == endTTI); //FIXME so I don't forget, it will mess things up if silently ignored Q_ASSERT(startTTI->parent() == endTTI->parent()); //TODO not implemented Q_ASSERT(startTTI && endTTI); //TODO partially loaded move are not implemented auto oldPreviousTTI = startTTI->up(); auto oldNextTTI = endTTI->down(); Q_ASSERT((!oldPreviousTTI) || oldPreviousTTI->down() == startTTI); Q_ASSERT((!oldNextTTI) || oldNextTTI->up() == endTTI); auto newNextIdx = m_pModelTracker->modelCandidate()->index(row, 0, destination); // You cannot move things into an empty model Q_ASSERT((!row) || newNextIdx.isValid()); StateTracker::Index *newNextTTI(nullptr), *newPrevTTI(nullptr); // Rewind until a next element is found, this happens when destination is empty if (!newNextIdx.isValid() && destination.parent().isValid()) { Q_ASSERT(m_pModelTracker->modelCandidate()->rowCount(destination) == row); auto par = destination.parent(); do { if (m_pModelTracker->modelCandidate()->rowCount(par.parent()) > par.row()) { newNextIdx = m_pModelTracker->modelCandidate()->index(par.row(), 0, par.parent()); break; } par = par.parent(); } while (par.isValid()); newNextTTI = ttiForIndex(newNextIdx); } else { newNextTTI = ttiForIndex(newNextIdx); newPrevTTI = newNextTTI ? newNextTTI->up() : nullptr; } if (!row) { auto otherI = ttiForIndex(destination); Q_ASSERT((!newPrevTTI) || otherI == newPrevTTI); } // When there is no next element, then the parent has to be extracted manually if (!(newNextTTI || newPrevTTI)) { if (!row) newPrevTTI = ttiForIndex(destination); else { newPrevTTI = ttiForIndex( destination.model()->index(row-1, 0, destination) ); } } StateTracker::ModelItem* newParentTTI = ttiForIndex(destination); Q_ASSERT(newParentTTI || !destination.isValid()); //TODO not coded yet newParentTTI = newParentTTI ? newParentTTI : m_pRoot; // Remove everything //TODO add batching again StateTracker::Index* tti = endTTI; StateTracker::Index* dest = newNextTTI && newNextTTI->parent() == newParentTTI ? newNextTTI : nullptr; QList tmp2; do { tmp2 << tti; } while(endTTI != startTTI && (tti = tti->previousSibling()) != startTTI); if (endTTI != startTTI) //FIXME use a better condition tmp2 << startTTI; Q_ASSERT( (end - start) == tmp2.size() - 1); // Check if the point where //TODO this isn't good enough bool isRangeVisible = (newPrevTTI && newPrevTTI->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::VISIBLE) || (newNextTTI && newNextTTI->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::VISIBLE); const auto topEdge = q_ptr->edges(EdgeType::VISIBLE)->getEdge(Qt::TopEdge); const auto bottomEdge = q_ptr->edges(EdgeType::VISIBLE)->getEdge(Qt::TopEdge); bool needRefreshVisibleTop = false; bool needRefreshVisibleBottom = false; /*bool needRefreshBufferTop = false; //TODO lateral move is not implemented bool needRefreshBufferBottom = false;*/ for (auto item : qAsConst(tmp2)) { needRefreshVisibleTop |= item != topEdge; needRefreshVisibleBottom |= item != bottomEdge; item->metadata() << IndexMetadata::GeometryAction::MOVE; item->remove(); StateTracker::Index::insertChildBefore(item, dest, newParentTTI); Q_ASSERT((!dest) || item->down() == dest); if (dest) dest->metadata() << IndexMetadata::GeometryAction::MOVE; _DO_TEST(_test_validate_edges_simple, q_ptr) m_pViewport->s_ptr->notifyInsert(item->metadata()); dest = item; if (isRangeVisible) { if (item->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::BUFFER) item->metadata() << IndexMetadata::LoadAction::ATTACH; item->metadata() << IndexMetadata::LoadAction::SHOW; } } _DO_TEST(_test_validate_move, q_ptr, newParentTTI, startTTI, endTTI, newPrevTTI, newNextTTI, row) resetTemporaryIndices(tmp); // The visible edges are now probably incorectly placed, reload them if (needRefreshVisibleTop || needRefreshVisibleBottom) { reloadEdges(); m_pViewport->s_ptr->refreshVisible(); } //WARNING The indices still are in transition mode, do not use their value } QList ContentPrivate::setTemporaryIndices(const QModelIndex &parent, int start, int end, const QModelIndex &destination, int row) { //FIXME This exists but for now ignoring it hasn't caused too many problems if (parent != destination) { qWarning() << "setTemporaryIndices called with corrupted arguments"; return {}; } QList ret; // Before moving them, set a temporary now/col value because it wont be set // on the index until before endMoveRows is called (but after this // method returns). const auto pitem = parent.isValid() ? m_hMapper.value(parent) : m_pRoot; for (int i = start; i <= end; i++) { auto idx = m_pModelTracker->modelCandidate()->index(i, 0, parent); //TODO do not use the hashmap, it is already known auto elem = pitem->childrenLookup(idx); Q_ASSERT(elem); elem->setTemporaryIndex( destination, row + (i - start), idx.column() ); ret << elem; } for (int i = row; i <= row + (end - start); i++) { auto idx = m_pModelTracker->modelCandidate()->index(i, 0, parent); //TODO do not use the hashmap, it is already known auto elem = pitem->childrenLookup(idx); Q_ASSERT(elem); elem->setTemporaryIndex( destination, row + (end - start) + 1, idx.column() ); ret << elem; } return ret; } void ContentPrivate::resetTemporaryIndices(const QList& indices) { for (auto i : qAsConst(indices)) i->resetTemporaryIndex(); } void StateTracker::Content::resetEdges() { for (int i = 0; i < (int) EdgeType::NONE; i++) for (const auto e : {Qt::BottomEdge, Qt::TopEdge, Qt::LeftEdge, Qt::RightEdge}) setEdge((EdgeType)i, nullptr, e); } // Go O(N) for now. Optimize when it becomes a problem (read: soon) void ContentPrivate::reloadEdges() { //FIXME optimize this enum Range : uint16_t { TOP = 0x0 << 0, BUFFER_TOP = 0x1 << 0, VISIBLE = 0x1 << 1, BUFFER_BOTTOM = 0x1 << 2, BOTTOM = 0x1 << 3, IS_VISIBLE = 0x1 << 4, IS_NOT_VISIBLE = 0x1 << 5, IS_BUFFER = 0x1 << 6, IS_NOT_BUFFER = 0x1 << 7, }; Range pos = Range::TOP; for (auto item = m_pRoot->firstChild(); item; item = item->down()) { const uint16_t isVisible = item->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::VISIBLE ? IS_VISIBLE : IS_NOT_VISIBLE; const uint16_t isBuffer = item->metadata()->modelTracker()->state() == StateTracker::ModelItem::State::BUFFER ? IS_BUFFER : IS_NOT_BUFFER; switch(pos | isVisible | isBuffer) { case Range::TOP | Range::IS_BUFFER: pos = Range::BUFFER_TOP; q_ptr->setEdge(EdgeType::BUFFERED, item, Qt::TopEdge); break; case Range::TOP | Range::IS_VISIBLE: case Range::BUFFER_TOP | Range::IS_VISIBLE: pos = Range::VISIBLE; q_ptr->setEdge(EdgeType::VISIBLE, item, Qt::TopEdge); break; case Range::VISIBLE | Range::IS_NOT_VISIBLE: case Range::VISIBLE | Range::IS_NOT_BUFFER: q_ptr->setEdge(EdgeType::VISIBLE, item->up(), Qt::BottomEdge); pos = Range::BOTTOM; break; case Range::VISIBLE | Range::IS_NOT_VISIBLE | Range::IS_BUFFER: pos = Range::BUFFER_BOTTOM; break; case Range::VISIBLE | Range::IS_NOT_BUFFER | Range::IS_NOT_VISIBLE: q_ptr->setEdge(EdgeType::BUFFERED, item->up(), Qt::BottomEdge); pos = Range::BOTTOM; break; } } } void ContentPrivate::enterState(IndexMetadata *tti, StateTracker::ModelItem::State s) { Q_UNUSED(tti); Q_UNUSED(s); //TODO count the number of active objects in each states for the "frame" load balancing } void ContentPrivate::leaveState(IndexMetadata *tti, StateTracker::ModelItem::State s) { Q_UNUSED(tti); Q_UNUSED(s); //TODO count the number of active objects in each states for the "frame" load balancing } void ContentPrivate::error(IndexMetadata *, StateTracker::ModelItem::State) { Q_ASSERT(false); } StateTracker::Index *StateTracker::Content::firstItem() const { return root()->firstChild(); } StateTracker::Index *StateTracker::Content::lastItem() const { auto candidate = d_ptr->m_pRoot->lastChild(); while (candidate && candidate->lastChild()) candidate = candidate->lastChild(); return candidate; } bool ContentPrivate::isInsertActive(const QModelIndex& p, int first, int last) const { Q_UNUSED(last) //TODO auto pitem = p.isValid() ? m_hMapper.value(p) : m_pRoot; StateTracker::Index *prev(nullptr); //FIXME use up() if (first && pitem) - prev = pitem->childrenLookup(m_pModelTracker->trackedModel()->index(first-1, 0, p)); + prev = pitem->childrenLookup(m_pModelTracker->modelCandidate()->index(first-1, 0, p)); if (first && !prev) return false; if (q_ptr->edges(EdgeType::FREE)->m_Edges & (Qt::TopEdge|Qt::BottomEdge)) return true; const auto parent = p.isValid() ? ttiForIndex(p) : m_pRoot; // It's controversial as it means if the items would otherwise be // visible because their parent "virtual" position + insertion height // could happen to be in the view but in this case the scrollbar would // move. Mobile views tend to not shuffle the current content around so // from that point of view it is correct, but if the item is in the // buffer, then it will move so doing this is a bit buggy. return parent != nullptr; } /// Return true if the indices affect the current view bool StateTracker::Content::isActive(const QModelIndex& parent, int first, int last) { if (!parent.isValid()) { // There is nothing loaded, so everything is active (so far) if (!d_ptr->m_pRoot->firstChild()) return true; // There is room for more. Assuming the code that makes sure all items // that can be loaded are, then it only happens when there is room for // more. if (edges(EdgeType::FREE)->m_Edges & (Qt::BottomEdge | Qt::TopEdge)) return true; const QRect loadedRect( d_ptr->m_pRoot->firstChild()->index().column(), d_ptr->m_pRoot->firstChild()->index().row(), d_ptr->m_pRoot->lastChild ()->index().column() + 1, d_ptr->m_pRoot->lastChild ()->index().row() + 1 ); const QRect changedRect( 0, first, 1, //FIXME use columnCount+!? last ); return loadedRect.intersects(changedRect); } //FIXME This method is incomplete // Q_ASSERT(false); //TODO THIS_COMMIT return true; } /// Add new entries to the mapping StateTracker::ModelItem* ContentPrivate::addChildren(const QModelIndex& index) { Q_ASSERT(index.isValid() && !m_hMapper.contains(index)); auto e = new StateTracker::ModelItem(m_pViewport); e->setModelIndex(index); m_hMapper[index] = e; return e; } void ContentPrivate::slotCleanup() { // The whole slotCleanup cycle isn't necessary, it wont find anything. if (!m_pRoot->firstChild()) return; m_pModelTracker << StateTracker::Model::Action::RESET; m_pRoot->metadata() << IndexMetadata::LoadAction::HIDE << IndexMetadata::LoadAction::DETACH; m_hMapper.clear(); m_pRoot = new StateTracker::ModelItem(m_pViewport); } StateTracker::ModelItem* ContentPrivate::ttiForIndex(const QModelIndex& idx) const { if (!idx.isValid()) return nullptr; const auto parent = (!idx.parent().isValid()) ? m_pRoot : m_hMapper.value(idx.parent()); return parent ? static_cast(parent->childrenLookup(idx)) : nullptr; } IndexMetadata *StateTracker::Content::metadataForIndex(const QModelIndex& idx) const { const auto tti = d_ptr->ttiForIndex(idx); return tti ? tti->metadata() : nullptr; } void StateTracker::Content::setAvailableEdges(Qt::Edges es, EdgeType t) { edges(t)->m_Edges = es; } Qt::Edges StateTracker::Content::availableEdges(EdgeType t) const { return edges(t)->m_Edges; } IndexMetadata *StateTracker::Content::getEdge(EdgeType t, Qt::Edge e) const { const auto ret = edges(t)->getEdge(e); return ret ? ret->metadata() : nullptr; } ModelRect* StateTracker::Content::edges(EdgeType e) const { Q_ASSERT((int) e >= 0 && (int)e <= 2); return (ModelRect*) &d_ptr->m_lRects[(int)e]; } // Add more validation to detect possible invalid edges being set void StateTracker::Content:: setEdge(EdgeType et, StateTracker::Index* tti, Qt::Edge e) { //DEBUG this only works with proxy models, not JIT/AOT strategies // if (tti && et == EdgeType::VISIBLE) // Q_ASSERT(TTI(tti)->metadata()->isValid()); edges(et)->setEdge(tti, e); _DO_TEST(_test_validate_edges_simple, this) } StateTracker::Index *StateTracker::Content:: find(StateTracker::Index *from, Qt::Edge direction, std::function cond) const { auto f = from; while(f && cond(f) && f->next(direction) && (f = f->next(direction))); return f; } StateTracker::Model *StateTracker::Content::modelTracker() const { return d_ptr->m_pModelTracker; } //DEPRECATED use StateTracker::Proximity QModelIndex ContentPrivate::getNextIndex(const QModelIndex& idx) const { // There is 2 possibilities, a sibling or a [[great]grand]uncle if (m_pModelTracker->modelCandidate()->rowCount(idx)) return m_pModelTracker->modelCandidate()->index(0,0, idx); auto sib = idx.siblingAtRow(idx.row()+1); if (sib.isValid()) return sib; if (!idx.parent().isValid()) return {}; auto p = idx.parent(); while (p.isValid()) { sib = p.siblingAtRow(p.row()+1); if (sib.isValid()) return sib; p = p.parent(); } return {}; } void StateTracker::Content::connectModel(QAbstractItemModel *m) { QObject::connect(m, &QAbstractItemModel::rowsInserted, d_ptr, &ContentPrivate::slotRowsInserted ); QObject::connect(m, &QAbstractItemModel::rowsAboutToBeRemoved, d_ptr, &ContentPrivate::slotRowsRemoved ); QObject::connect(m, &QAbstractItemModel::layoutAboutToBeChanged, d_ptr, &ContentPrivate::slotCleanup); QObject::connect(m, &QAbstractItemModel::layoutChanged, d_ptr, &ContentPrivate::slotLayoutChanged); QObject::connect(m, &QAbstractItemModel::modelAboutToBeReset, d_ptr, &ContentPrivate::slotCleanup); QObject::connect(m, &QAbstractItemModel::modelReset, d_ptr, &ContentPrivate::slotLayoutChanged); QObject::connect(m, &QAbstractItemModel::rowsAboutToBeMoved, d_ptr, &ContentPrivate::slotRowsMoved); QObject::connect(m, &QAbstractItemModel::dataChanged, d_ptr, &ContentPrivate::slotDataChanged); #ifdef ENABLE_EXTRA_VALIDATION QObject::connect(m, &QAbstractItemModel::rowsMoved, d_ptr, [this](){_DO_TEST(_test_validateLinkedList, this);}); QObject::connect(m, &QAbstractItemModel::rowsRemoved, d_ptr, [this](){_DO_TEST(_test_validateLinkedList, this);}); #endif } void StateTracker::Content::disconnectModel(QAbstractItemModel *m) { QObject::disconnect(m, &QAbstractItemModel::rowsInserted, d_ptr, &ContentPrivate::slotRowsInserted); QObject::disconnect(m, &QAbstractItemModel::rowsAboutToBeRemoved, d_ptr, &ContentPrivate::slotRowsRemoved); QObject::disconnect(m, &QAbstractItemModel::layoutAboutToBeChanged, d_ptr, &ContentPrivate::slotCleanup); QObject::disconnect(m, &QAbstractItemModel::layoutChanged, d_ptr, &ContentPrivate::slotLayoutChanged); QObject::disconnect(m, &QAbstractItemModel::modelAboutToBeReset, d_ptr, &ContentPrivate::slotCleanup); QObject::disconnect(m, &QAbstractItemModel::modelReset, d_ptr, &ContentPrivate::slotLayoutChanged); QObject::disconnect(m, &QAbstractItemModel::rowsAboutToBeMoved, d_ptr, &ContentPrivate::slotRowsMoved); QObject::disconnect(m, &QAbstractItemModel::dataChanged, d_ptr, &ContentPrivate::slotDataChanged); #ifdef ENABLE_EXTRA_VALIDATION // QObject::disconnect(m, &QAbstractItemModel::rowsMoved, d_ptr, // [this](){d_ptr->_test_validateLinkedList();}); // QObject::disconnect(m, &QAbstractItemModel::rowsRemoved, d_ptr, // [this](){d_ptr->_test_validateLinkedList();}); #endif } StateTracker::Index *StateTracker::Content::root() const { return d_ptr->m_pRoot; } void StateTracker::Content::resetRoot() { root()->metadata() << IndexMetadata::LoadAction::RESET; for (int i = 0; i < 3; i++) d_ptr->m_lRects[i] = {}; d_ptr->m_hMapper.clear(); delete d_ptr->m_pRoot; d_ptr->m_pRoot = new StateTracker::ModelItem(d_ptr->m_pViewport); } void StateTracker::Content::perfromStateChange(Event e, IndexMetadata *md, StateTracker::ModelItem::State s) { const auto ms = e == Event::LEAVE_STATE ? s : md->modelTracker()->state(); (d_ptr->*ContentPrivate::m_fStateLogging[(int)ms][(int)e])(md, s); } void StateTracker::Content::forceInsert(const QModelIndex& idx) { //TODO add some safety check or find a way to get rid of this hack d_ptr->slotRowsInserted(idx.parent(), idx.row(), idx.row()); } +// Also make sure not to load the same element twice void StateTracker::Content::forceInsert(const QModelIndex& parent, int first, int last) { + auto parNode = parent.isValid() ? d_ptr->m_hMapper[parent] : d_ptr->m_pRoot; + + // If the parent isn't loaded, there is no risk of collision + if (!parNode) { + //TODO loading the parent chain of `parent` is needed + d_ptr->slotRowsInserted(parent, first, last); + return; + } + + // If the parent has no children elements, then there is no collisions + if (!parNode->firstChild()) { + d_ptr->slotRowsInserted(parent, first, last); + return; + } + + // If the range isn't overlapping, there is no collisions + if (parNode->lastChild()->effectiveRow() < first || parNode->firstChild()->effectiveRow() > last) { + d_ptr->slotRowsInserted(parent, first, last); + return; + } + + // If there is a continuity encompassing `first` and `last` then there + // is nothing to do. + if (parNode->firstChild()->continuityTracker()->size() >= last) { + return; + } + + //TODO the case above only works if firstChild()->row() == 0. If another + // case is hit, then it will assert in slotRowsInserted + d_ptr->slotRowsInserted(parent, first, last); } #include diff --git a/src/private/statetracker/continuity_p.cpp b/src/private/statetracker/continuity_p.cpp new file mode 100644 index 0000000..bcaed69 --- /dev/null +++ b/src/private/statetracker/continuity_p.cpp @@ -0,0 +1,117 @@ +/*************************************************************************** + * Copyright (C) 2018 by Emmanuel Lepage Vallee * + * Author : Emmanuel Lepage Vallee * + * * + * 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 3 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 "continuity_p.h" + +#include "index_p.h" + +void StateTracker::Continuity::remove(StateTracker::Index *i) +{ + if (!i->m_pContinuity) + return; + + // Free the existing StateTracker::Continuity + if (i->m_pContinuity->size() == 1) { + delete i->m_pContinuity; + i->m_pContinuity = nullptr; + return; + } + + // Make sure first()/last() are not outdated + if (i->m_pContinuity->m_pFirst == i) + i->m_pContinuity->m_pFirst = i->nextSibling(); + + if (i->m_pContinuity->m_pLast == i) + i->m_pContinuity->m_pLast = i->previousSibling(); + + i->m_pContinuity = nullptr; +} + +void StateTracker::Continuity::setContinuity(StateTracker::Index *i, StateTracker::Continuity *c) +{ + if (i->m_pContinuity == c) + return; + + remove(i); + + i->m_pContinuity = c; +} + +StateTracker::Continuity::Continuity(Index *first) : + m_pFirst(first), m_pLast(first) +{} + +int StateTracker::Continuity::size() const +{ + if (!first()) + return 0; + + // +1 it starts at zero + return (last()->effectiveRow() - first()->effectiveRow()) + 1; +} + +StateTracker::Index *StateTracker::Continuity::first() const +{ + return m_pFirst; +} + +StateTracker::Index *StateTracker::Continuity::last() const +{ + return m_pLast; +} + +StateTracker::Continuity *StateTracker::Continuity::select(StateTracker::Index *i) +{ + auto prev = i->previousSibling(); + auto next = i->nextSibling(); + auto old = i->m_pContinuity; + + if (prev && i->isNeighbor(prev)) { + if (prev->continuityTracker()->last() == prev) + prev->continuityTracker()->m_pLast = i; + i->m_pContinuity = prev->continuityTracker(); + } + else if (next && i->isNeighbor(next)) { + if (next->continuityTracker()->first() == next) + next->continuityTracker()->m_pFirst = i; + i->m_pContinuity = next->continuityTracker(); + } + else if (!old) + i->m_pContinuity = new Continuity(i); + + Q_ASSERT(i->m_pContinuity); + + return i->m_pContinuity; +} + +void StateTracker::Continuity::split(StateTracker::Index *at) +{ + Q_ASSERT(false); //TODO + auto old = at->m_pContinuity; + auto n = new Continuity(at); + + do { + at->m_pContinuity = n; + } while((at = at->nextSibling()) && at->m_pContinuity == old); +} + +void StateTracker::Continuity::merge(StateTracker::Index *one, StateTracker::Index *two) +{ + Q_UNUSED(one) + Q_UNUSED(two) + Q_ASSERT(false); //TODO +} diff --git a/src/private/statetracker/continuity_p.h b/src/private/statetracker/continuity_p.h new file mode 100644 index 0000000..c513f22 --- /dev/null +++ b/src/private/statetracker/continuity_p.h @@ -0,0 +1,76 @@ +/*************************************************************************** + * Copyright (C) 2018 by Emmanuel Lepage Vallee * + * Author : Emmanuel Lepage Vallee * + * * + * 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 3 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 . * + **************************************************************************/ +#pragma once + +namespace StateTracker { + +class Index; + +/** + * This bare-bone state tracker helps to track the continuity between the + * ELEMENTS WITH THE SAME PARENT. + * + * The use case for this is to prevent the O(N) operation of the list of + * elements to check if there is missing holes in them. This could be done with + * simple artmetic on the row of the last child, first child and the number of + * children, but this would not handle the corner cases where there multiple + * "holes". It would also not allow to know where the hole(s) are without + * looping. + * + * This may seem overkill to waste memory tracking this, but there is 2 reasons + * why it isn't such a bad idea: + * + * * Some ViewportStategies need to know this in every frame (fps) of a scroll + * operation with tight frame duration deadlines. + * * If the viewport loads a full list model, the "N" of "O(N)" can be very + * large. + * + * @todo This should, once fully implemented, go hand in hand with + * StateTracker::Proximity to avoid useless rowCount other overhead in + * StateTracker::Content and make methods such as `isActive` reliable. + * + * @todo Slicing a StateTracker::Continuity is currently rather expensive. This + * can be brought down to "O(N*log(N))" by using double pointers to create + * "pages" of a size representative of the total number of elements. However + * this will take more memory and has an overhead in itself. It wont be done + * unless it is proven to be significantly faster for real-world models. + */ +class Continuity final +{ + friend class Index; // Factory, call private API + +public: + Index *first() const; + Index *last () const; + + int size() const; + +private: + explicit Continuity(Index *first); + + StateTracker::Index *m_pFirst {nullptr}; + StateTracker::Index *m_pLast {nullptr}; + + static void split(StateTracker::Index *at); + static void merge(StateTracker::Index *one, StateTracker::Index *two); + static void remove(Index *i); + static void setContinuity(Index *i, Continuity *c); + static Continuity *select(StateTracker::Index *i); +}; + +} diff --git a/src/private/statetracker/index_p.cpp b/src/private/statetracker/index_p.cpp index e19254f..1e065f0 100644 --- a/src/private/statetracker/index_p.cpp +++ b/src/private/statetracker/index_p.cpp @@ -1,515 +1,552 @@ /*************************************************************************** * Copyright (C) 2017-2018 by Emmanuel Lepage Vallee * * Author : Emmanuel Lepage Vallee * * * * 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 3 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 "index_p.h" +#include "continuity_p.h" // Use some constant for readability #define PREVIOUS 0 #define NEXT 1 #define FIRST 0 #define LAST 1 StateTracker::Index::~Index() { remove(); } StateTracker::Index* StateTracker::Index::firstChild() const { return m_tChildren[FIRST]; } StateTracker::Index* StateTracker::Index::lastChild() const { return m_tChildren[LAST]; } StateTracker::Index* StateTracker::Index::nextSibling() const { return m_tSiblings[NEXT]; } StateTracker::Index* StateTracker::Index::previousSibling() const { return m_tSiblings[PREVIOUS]; } StateTracker::Index *StateTracker::Index::parent() const { return m_pParent; } void StateTracker::Index::insertChildAfter(StateTracker::Index* self, StateTracker::Index* other, StateTracker::Index* parent) { Q_ASSERT(!self->m_pParent); Q_ASSERT(parent); Q_ASSERT(self->m_LifeCycleState == LifeCycleState::NEW); Q_ASSERT(parent->firstChild() || !other); //Always detach first Q_ASSERT(!self->m_tSiblings[PREVIOUS]); Q_ASSERT(!self->m_tSiblings[NEXT]); if (!parent->m_tChildren[FIRST]) { Q_ASSERT(!parent->m_tChildren[LAST]); Q_ASSERT(!parent->loadedChildrenCount()); parent->m_hLookup[self->m_Index] = self; parent->m_tChildren[FIRST] = parent->m_tChildren[LAST] = self; self->m_pParent = parent; self->m_LifeCycleState = self->m_MoveToRow != -1 ? LifeCycleState::TRANSITION : LifeCycleState::NORMAL; + StateTracker::Continuity::select(self); + _DO_TEST_IDX(_test_validate_chain, parent) return; } Q_ASSERT(other); Q_ASSERT(other->m_pParent == parent); Q_ASSERT(!parent->m_hLookup.contains(self->m_Index)); Q_ASSERT(!parent->m_hLookup.values().contains(self)); parent->m_hLookup[self->m_Index] = self; self->m_pParent = parent; self->m_LifeCycleState = self->m_MoveToRow != -1 ? LifeCycleState::TRANSITION : LifeCycleState::NORMAL; self->m_tSiblings[NEXT] = other->m_tSiblings[NEXT]; if (other->m_tSiblings[NEXT]) { Q_ASSERT(other->m_tSiblings[NEXT]->m_tSiblings[PREVIOUS] == other); other->m_tSiblings[NEXT]->m_tSiblings[PREVIOUS] = self; } other->m_tSiblings[NEXT] = self; self->m_tSiblings[PREVIOUS] = other; if (parent->m_tChildren[LAST] == other) parent->m_tChildren[LAST] = self; + StateTracker::Continuity::select(self); + _DO_TEST_IDX(_test_validate_chain, parent) } void StateTracker::Index::insertChildBefore(StateTracker::Index* self, StateTracker::Index* other, StateTracker::Index* parent) { Q_ASSERT(!self->m_pParent); Q_ASSERT(parent); Q_ASSERT(self->m_LifeCycleState == LifeCycleState::NEW); Q_ASSERT(!parent->m_hLookup.contains(self->m_Index)); _DO_TEST_IDX(_test_validate_chain, parent) Q_ASSERT(!parent->m_hLookup.values().contains(self)); parent->m_hLookup[self->m_Index] = self; self->m_pParent = parent; self->m_LifeCycleState = self->m_MoveToRow != -1 ? LifeCycleState::TRANSITION : LifeCycleState::NORMAL; if (!parent->firstChild()) { Q_ASSERT(!parent->lastChild()); parent->m_tChildren[FIRST] = parent->m_tChildren[LAST] = self; self->m_tSiblings[PREVIOUS] = self->m_tSiblings[NEXT] = nullptr; Q_ASSERT(!self->nextSibling()); Q_ASSERT(!self->previousSibling()); + + StateTracker::Continuity::select(self); + _DO_TEST_IDX(_test_validate_chain, parent) return; } // Q_ASSERT(!self->nextSibling()); Q_ASSERT(parent == self->m_pParent); if (!other) { if (auto f = parent->firstChild()) f->m_tSiblings[PREVIOUS] = self; self->m_tSiblings[NEXT] = parent->firstChild(); parent->m_tChildren[FIRST] = self; Q_ASSERT(!self->previousSibling()); Q_ASSERT(parent->lastChild()); + StateTracker::Continuity::select(self); + _DO_TEST_IDX(_test_validate_chain, parent) return; } Q_ASSERT(other); Q_ASSERT(other->m_pParent == parent); Q_ASSERT(other->m_pParent == parent); if (other == parent->firstChild()) { Q_ASSERT(!other->previousSibling()); Q_ASSERT(other->nextSibling() || other == parent->lastChild()); parent->m_tChildren[FIRST] = self; self->m_tSiblings[NEXT] = other; self->m_tSiblings[PREVIOUS] = nullptr; other->m_tSiblings[PREVIOUS] = self; Q_ASSERT(!self->previousSibling()); Q_ASSERT(parent->lastChild()); Q_ASSERT(parent->firstChild()); } else { Q_ASSERT(other->previousSibling()); other->previousSibling()->m_tSiblings[NEXT] = self; self->m_tSiblings[PREVIOUS] = other->previousSibling(); self->m_tSiblings[NEXT] = other; other->m_tSiblings[PREVIOUS] = self; } + StateTracker::Continuity::select(self); + _DO_TEST_IDX(_test_validate_chain, parent) } /// Fix the issues introduced by createGap (does not update m_pParent and m_hLookup) void StateTracker::Index::bridgeGap(StateTracker::Index* first, StateTracker::Index* second) { // 3 possible case: siblings, first child or last child if (first && second && first->m_pParent == second->m_pParent) { // first and second are siblings if (first == first->m_pParent->lastChild()) Q_ASSERT(false);//TODO if (first->m_pParent->lastChild() == first) { Q_ASSERT(!second->nextSibling()); first->m_pParent->m_tChildren[LAST] = second; } first->m_tSiblings [ NEXT ] = second; second->m_tSiblings[PREVIOUS] = first; // Q_ASSERT(!second->m_pParent->lastChild() ==second); } else if (second && ((!first) || first == second->m_pParent)) { auto par = second->m_pParent; second->remove(true); Q_ASSERT(second->m_LifeCycleState == LifeCycleState::NEW); insertChildBefore(second, nullptr, par); } else if (first && second && first->m_pParent->lastChild() == first) { // There is nothing to do Q_ASSERT(second->parent() == first->parent()->parent()); Q_ASSERT(second->previousSibling() == first->parent()); } else if (first) { // `first` may be the last child of a last child (of a...) Q_ASSERT((!second) || second->parent()->lastChild() == second); // It's the last element or the second is a last leaf and first is unrelated first->m_tSiblings[NEXT] = nullptr; if (!first->m_pParent->firstChild()) first->m_pParent->m_tChildren[FIRST] = first; if (first->m_pParent->lastChild() && first->m_pParent->lastChild() != first) { first->m_pParent->lastChild()->m_tSiblings[NEXT] = first; first->m_tSiblings[PREVIOUS] = first->m_pParent->lastChild(); } first->m_pParent->m_tChildren[LAST] = first; Q_ASSERT((!first) || first->m_pParent->lastChild()); // // //BEGIN test // int count =0; // for (auto c = first->m_pParent->lastChild(); c; c = c->previousSibling()) // count++; // // Q_ASSERT(first->m_pParent->firstChild()); // // Q_ASSERT(count == first->m_pParent->m_hLookup.size()); // //END test } else { Q_ASSERT(false); //Something went really wrong elsewhere } _DO_TEST_IDX_STATIC(_test_bridgeGap, first, second) } void StateTracker::Index::remove(bool reparent) { if (m_LifeCycleState == LifeCycleState::NEW) return; + // Make sure the StateTracker::Continuity doesn't lose its state too early + // and end up in a crash or memory corruption + StateTracker::Continuity::remove(this); + // You can't remove ROOT, so this should always be true Q_ASSERT(m_pParent); Q_ASSERT(m_pParent->m_hLookup.values().contains(this)); const int size = m_pParent->m_hLookup.size(); m_pParent->m_hLookup.remove(m_Index); Q_ASSERT(size == m_pParent->m_hLookup.size()+1); Q_ASSERT(!m_pParent->m_hLookup.values().contains(this)); if (!reparent) { Q_ASSERT(!firstChild()); Q_ASSERT(m_hLookup.isEmpty()); } const auto oldNext(nextSibling()), oldPrev(previousSibling()); // Do not use bridgeGap to prevent rist of recursion on invalid trees if (oldPrev && oldNext) { Q_ASSERT(oldPrev != oldNext); oldPrev->m_tSiblings[NEXT] = oldNext; oldNext->m_tSiblings[PREVIOUS] = oldPrev; } Q_ASSERT((!oldPrev) || oldPrev->previousSibling() != oldPrev); Q_ASSERT((!oldNext) || oldNext->nextSibling() != oldNext); if (m_pParent->firstChild() == this) { Q_ASSERT(!oldPrev); Q_ASSERT((!oldNext) || oldNext->previousSibling() == this); if (auto next = oldNext) next->m_tSiblings[PREVIOUS] = nullptr; m_pParent->m_tChildren[FIRST] = oldNext; Q_ASSERT((!oldNext) || !oldNext->previousSibling()); if (m_pParent->firstChild()) m_pParent->firstChild()->m_tSiblings[PREVIOUS] = nullptr; } if (m_pParent->lastChild() == this) { Q_ASSERT((!oldNext)); Q_ASSERT((!oldPrev) || oldPrev->nextSibling() ==this); m_pParent->m_tChildren[LAST] = oldPrev; if (m_pParent->lastChild()) m_pParent->lastChild()->m_tSiblings[NEXT] = nullptr; } Q_ASSERT((!m_pParent->firstChild()) || m_pParent->lastChild()); // else if (previousSibling()) { // Q_ASSERT(false); //TODO // } // else if (oldNext) { // Q_ASSERT(false); //TODO // } // else { //FIXME very wrong // Q_ASSERT(m_pParent->m_hLookup.isEmpty()); // m_pParent->m_tChildren[FIRST] = nullptr; // m_pParent->m_tChildren[LAST] = nullptr; // } m_LifeCycleState = LifeCycleState::NEW; m_pParent = nullptr; } StateTracker::Index* StateTracker::Index::up() const { StateTracker::Index* ret = nullptr; // Another simple case, there is no parent if (!m_pParent) { Q_ASSERT(!m_Index.parent().isValid()); //TODO remove, no longer true when partial loading is implemented return nullptr; } // Keep in mind that the "root" means no parent if (m_pParent && m_pParent->m_pParent && !previousSibling()) return m_pParent; ret = previousSibling(); while (ret && ret->lastChild()) ret = ret->lastChild(); return ret; } StateTracker::Index* StateTracker::Index::next(Qt::Edge e) const { switch (e) { case Qt::TopEdge: return up(); case Qt::BottomEdge: return down(); case Qt::LeftEdge: return left(); case Qt::RightEdge: return right(); } Q_ASSERT(false); return nullptr; } StateTracker::Index* StateTracker::Index::down() const { StateTracker::Index* ret = nullptr; auto i = this; if (firstChild()) { //Q_ASSERT(m_pParent->firstChild()->m_Index.row() == 0); //racy ret = firstChild(); return ret; } // Recursively unwrap the tree until an element is found while(i) { if (i->nextSibling() && (ret = i->nextSibling())) return ret; i = i->parent(); } // Can't happen, exists to detect corrupted code if (m_Index.parent().isValid()) { Q_ASSERT(m_pParent); // Q_ASSERT(m_pParent->parent()->parent()->m_hLookup.size() // == m_pParent->m_Index.parent().row()+1); } return ret; } StateTracker::Index* StateTracker::Index::left() const { return nullptr; //TODO } StateTracker::Index* StateTracker::Index::right() const { return nullptr; //TODO } void ModelRect::setEdge(StateTracker::Index* tti, Qt::Edge e) { m_lpEdges.set(tti, e); } StateTracker::Index* ModelRect::getEdge(Qt::Edge e) const { return m_lpEdges.get(e); } StateTracker::Index *StateTracker::Index::childrenLookup(const QPersistentModelIndex &index) const { return m_hLookup.value(index); } bool StateTracker::Index::hasChildren(StateTracker::Index *child) const { return !m_hLookup.keys(child).isEmpty(); } int StateTracker::Index::loadedChildrenCount() const { return m_hLookup.size(); } QList StateTracker::Index::allLoadedChildren() const { return m_hLookup.values(); } bool StateTracker::Index::withinRange(QAbstractItemModel* m, int last, int first) const { // Return true if the previous element or next element are loaded const QModelIndex prev = first ? m->index(first - 1, 0, m_Index) : QModelIndex(); const QModelIndex next = first ? m->index(last + 1, 0, m_Index) : QModelIndex(); return (prev.isValid() && m_hLookup.contains(prev)) || (next.isValid() && m_hLookup.contains(next)); } int StateTracker::Index::effectiveRow() const { return m_MoveToRow == -1 ? m_Index.row() : m_MoveToRow; } int StateTracker::Index::effectiveColumn() const { return m_MoveToColumn == -1 ? m_Index.column() : m_MoveToColumn; } QPersistentModelIndex StateTracker::Index::effectiveParentIndex() const { return m_LifeCycleState == LifeCycleState::TRANSITION ? m_MoveToParent : m_pParent->index(); } void StateTracker::Index::resetTemporaryIndex() { Q_ASSERT(m_pParent); Q_ASSERT(m_LifeCycleState == LifeCycleState::TRANSITION); m_LifeCycleState = LifeCycleState::NORMAL; m_MoveToRow = -1; m_MoveToColumn = -1; m_MoveToParent = QModelIndex(); } bool StateTracker::Index::hasTemporaryIndex() { return m_MoveToRow != -1 || m_MoveToColumn != -1; } void StateTracker::Index::setTemporaryIndex(const QModelIndex& newParent, int row, int column) { //TODO handle parent Q_ASSERT(m_LifeCycleState == LifeCycleState::NORMAL); - m_MoveToParent = newParent; - m_MoveToRow = row; - m_MoveToColumn = column; + m_MoveToParent = newParent; + m_MoveToRow = row; + m_MoveToColumn = column; m_LifeCycleState = LifeCycleState::TRANSITION; } QPersistentModelIndex StateTracker::Index::index() const { return m_Index; } void StateTracker::Index::setModelIndex(const QPersistentModelIndex& idx) { Q_ASSERT(m_LifeCycleState == LifeCycleState::NEW); m_Index = idx; } int StateTracker::Index::depth() const { int d = 0; auto s = this; while((s = s->parent()) && ++d); return d;//FIXME m_pTTI->m_Depth; } +bool StateTracker::Index::isNeighbor(Index *other) const +{ + if (!other) + return parent()->lastChild() == this || parent()->firstChild() == this; + + return previousSibling() == other || nextSibling() == other; +} + IndexMetadata *StateTracker::Index::metadata() const { return &m_Geometry; } +StateTracker::Continuity *StateTracker::Index::continuityTracker() const +{ + Q_ASSERT(m_pContinuity); + + // This should not happen and means the StateTracker::Continuity::size() + // is currently returning the wrong value, but it can be recovered from and + // is not worth crashing over this in release mode. + if (!m_pContinuity) + StateTracker::Continuity::select(const_cast(this)); + + return m_pContinuity; +} + #undef PREVIOUS #undef NEXT #undef FIRST #undef LAST #undef TTI diff --git a/src/private/statetracker/index_p.h b/src/private/statetracker/index_p.h index f93399d..974547d 100644 --- a/src/private/statetracker/index_p.h +++ b/src/private/statetracker/index_p.h @@ -1,159 +1,170 @@ /*************************************************************************** * Copyright (C) 2017-2018 by Emmanuel Lepage Vallee * * Author : Emmanuel Lepage Vallee * * * * 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 3 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 . * **************************************************************************/ #pragma once #include #include #include #include class Viewport; namespace StateTracker { +class Continuity; + /** * Internal navigation structure designed to support partial tree loading. * * This isn't intended to be used directly. It exists as its own class because * previous iterations were embedded within the model event slots and it made * it generally unmaintainable. The idea is to provide atomic and batch * operations that can be unit tested individually (eventually). * * * Support continuous but incomplete sets of indices * * Support indices currently being moved or removed * * Support moving and reparenting * * Provide both a geometric/cartesian and tree navigation API. */ class Index { + friend class Continuity; //Manage the m_pContinuity public: enum class LifeCycleState { NEW , /*!< Not part of a tree yet */ NORMAL , /*!< There is a valid index and a parent node */ TRANSITION , /*!< Between rowsAbouttoMove and rowsMoved (and removed) */ ROOT , /*!< This is the root element */ }; explicit Index(Viewport *p) : m_Geometry(this, p) {} virtual ~Index(); static void insertChildBefore(Index* self, StateTracker::Index* other, StateTracker::Index* parent); static void insertChildAfter(Index* self, StateTracker::Index* other, StateTracker::Index* parent); Index *firstChild() const; Index *lastChild () const; Index *nextSibling () const; Index *previousSibling() const; Index *parent() const; // Geometric navigation Index* up () const; //TODO remove Index* down () const; //TODO remove Index* left () const; //TODO remove Index* right() const; //TODO remove Index* next(Qt::Edge e) const; int depth() const; int effectiveRow() const; int effectiveColumn() const; QPersistentModelIndex effectiveParentIndex() const; virtual void remove(bool reparent = false); static void bridgeGap(Index* first, StateTracker::Index* second); Index *childrenLookup(const QPersistentModelIndex &index) const; bool hasChildren(Index *child) const; int loadedChildrenCount() const; QList allLoadedChildren() const; bool withinRange(QAbstractItemModel* m, int last, int first) const; void resetTemporaryIndex(); bool hasTemporaryIndex(); void setTemporaryIndex(const QModelIndex& newParent, int row, int column); + /** Return true when both elements have the same parent and are continuous. + * If other is `nullptr` and `i` is first (or last), then that's also true + */ + bool isNeighbor(Index *other) const; QPersistentModelIndex index() const; void setModelIndex(const QPersistentModelIndex& idx); LifeCycleState lifeCycleState() const {return m_LifeCycleState;} IndexMetadata *metadata() const; + //TODO have one for vertical and horizontal axis + Continuity *continuityTracker() const; + // Runtime tests #ifdef ENABLE_EXTRA_VALIDATION void _test_validate_chain() const; static void _test_bridgeGap(Index *first, Index *second); #endif private: // Because slotRowsMoved is called before the change take effect, cache // the "new real row and column" since the current index()->row() is now // garbage. int m_MoveToRow {-1}; int m_MoveToColumn {-1}; QPersistentModelIndex m_MoveToParent; uint m_Depth {0}; LifeCycleState m_LifeCycleState {LifeCycleState::NEW}; Index* m_tSiblings[2] = {nullptr, nullptr}; Index* m_tChildren[2] = {nullptr, nullptr}; // Keep the parent to be able to get back to the root Index* m_pParent {nullptr}; QPersistentModelIndex m_Index; //TODO use a btree, not an hash QHash m_hLookup; mutable IndexMetadata m_Geometry; + Continuity *m_pContinuity {nullptr}; }; } /** * TODO get rid of this and implement paging * * Keep track of state "edges". * * This allows to manipulate rectangles of QModelIndex similar to QtCore * dataChanged and other signals. */ class ModelRect final { public: StateTracker::Index* getEdge(Qt::Edge e) const; void setEdge(StateTracker::Index* tti, Qt::Edge e); Qt::Edges m_Edges {Qt::TopEdge|Qt::LeftEdge|Qt::RightEdge|Qt::BottomEdge}; private: GeoRect m_lpEdges; //TODO port to ModelRect }; // Inject some extra validation when executed in debug mode. #ifdef ENABLE_EXTRA_VALIDATION #define _DO_TEST_IDX(f, self, ...) self->f(__VA_ARGS__); #define _DO_TEST_IDX_STATIC(f, ...) f(__VA_ARGS__); #else #define _DO_TEST_IDX(f, self, ...) /*NOP*/; #define _DO_TEST_IDX_STATIC(f, ...) /*NOP*/; #endif