File indexing completed on 2024-07-21 06:38:23

0001 /*
0002     SPDX-FileCopyrightText: 2009 Stephen Kelly <steveire@gmail.com>
0003     SPDX-FileCopyrightText: 2016 Ableton AG <info@ableton.com>
0004     SPDX-FileContributor: Stephen Kelly <stephen.kelly@ableton.com>
0005 
0006     SPDX-License-Identifier: LGPL-2.0-or-later
0007 */
0008 
0009 #include "kselectionproxymodel.h"
0010 
0011 #include <QItemSelectionRange>
0012 #include <QPointer>
0013 #include <QStringList>
0014 
0015 #include "kbihash_p.h"
0016 #include "kmodelindexproxymapper.h"
0017 #include "kvoidpointerfactory_p.h"
0018 
0019 typedef KBiHash<QPersistentModelIndex, QModelIndex> SourceProxyIndexMapping;
0020 typedef KBiHash<void *, QModelIndex> ParentMapping;
0021 typedef KHash2Map<QPersistentModelIndex, int> SourceIndexProxyRowMapping;
0022 
0023 /**
0024   Return true if @p idx is a descendant of one of the indexes in @p list.
0025   Note that this returns false if @p list contains @p idx.
0026 */
0027 template<typename ModelIndex>
0028 bool isDescendantOf(const QList<ModelIndex> &list, const QModelIndex &idx)
0029 {
0030     if (!idx.isValid()) {
0031         return false;
0032     }
0033 
0034     if (list.contains(idx)) {
0035         return false;
0036     }
0037 
0038     QModelIndex parent = idx.parent();
0039     while (parent.isValid()) {
0040         if (list.contains(parent)) {
0041             return true;
0042         }
0043         parent = parent.parent();
0044     }
0045     return false;
0046 }
0047 
0048 static bool isDescendantOf(const QItemSelection &selection, const QModelIndex &descendant)
0049 {
0050     if (!descendant.isValid()) {
0051         return false;
0052     }
0053 
0054     if (selection.contains(descendant)) {
0055         return false;
0056     }
0057 
0058     QModelIndex parent = descendant.parent();
0059     while (parent.isValid()) {
0060         if (selection.contains(parent)) {
0061             return true;
0062         }
0063 
0064         parent = parent.parent();
0065     }
0066     return false;
0067 }
0068 
0069 static bool isDescendantOf(const QItemSelectionRange &range, const QModelIndex &descendant)
0070 {
0071     if (!descendant.isValid()) {
0072         return false;
0073     }
0074 
0075     if (range.contains(descendant)) {
0076         return false;
0077     }
0078 
0079     QModelIndex parent = descendant.parent();
0080     while (parent.isValid()) {
0081         if (range.contains(parent)) {
0082             return true;
0083         }
0084 
0085         parent = parent.parent();
0086     }
0087     return false;
0088 }
0089 
0090 static int _getRootListRow(const QList<QModelIndexList> &rootAncestors, const QModelIndex &index)
0091 {
0092     QModelIndex commonParent = index;
0093     QModelIndex youngestAncestor;
0094 
0095     int firstCommonParent = -1;
0096     int bestParentRow = -1;
0097     while (commonParent.isValid()) {
0098         youngestAncestor = commonParent;
0099         commonParent = commonParent.parent();
0100 
0101         for (int i = 0; i < rootAncestors.size(); ++i) {
0102             const QModelIndexList ancestorList = rootAncestors.at(i);
0103 
0104             const int parentRow = ancestorList.indexOf(commonParent);
0105 
0106             if (parentRow < 0) {
0107                 continue;
0108             }
0109 
0110             if (parentRow > bestParentRow) {
0111                 firstCommonParent = i;
0112                 bestParentRow = parentRow;
0113             }
0114         }
0115 
0116         if (firstCommonParent >= 0) {
0117             break;
0118         }
0119     }
0120 
0121     // If @p list is non-empty, the invalid QModelIndex() will at least be found in ancestorList.
0122     Q_ASSERT(firstCommonParent >= 0);
0123 
0124     const QModelIndexList firstAnsList = rootAncestors.at(firstCommonParent);
0125 
0126     const QModelIndex eldestSibling = firstAnsList.value(bestParentRow + 1);
0127 
0128     if (eldestSibling.isValid()) {
0129         // firstCommonParent is a sibling of one of the ancestors of @p index.
0130         // It is the first index to share a common parent with one of the ancestors of @p index.
0131         if (eldestSibling.row() >= youngestAncestor.row()) {
0132             return firstCommonParent;
0133         }
0134     }
0135 
0136     int siblingOffset = 1;
0137 
0138     // The same commonParent might be common to several root indexes.
0139     // If this is the last in the list, it's the only match. We instruct the model
0140     // to insert the new index after it ( + siblingOffset).
0141     if (rootAncestors.size() <= firstCommonParent + siblingOffset) {
0142         return firstCommonParent + siblingOffset;
0143     }
0144 
0145     // A
0146     // - B
0147     //   - C
0148     //   - D
0149     //   - E
0150     // F
0151     //
0152     // F is selected, then C then D. When inserting D into the model, the commonParent is B (the parent of C).
0153     // The next existing sibling of B is F (in the proxy model). bestParentRow will then refer to an index on
0154     // the level of a child of F (which doesn't exist - Boom!). If it doesn't exist, then we've already found
0155     // the place to insert D
0156     QModelIndexList ansList = rootAncestors.at(firstCommonParent + siblingOffset);
0157     if (ansList.size() <= bestParentRow) {
0158         return firstCommonParent + siblingOffset;
0159     }
0160 
0161     QModelIndex nextParent = ansList.at(bestParentRow);
0162     while (nextParent == commonParent) {
0163         if (ansList.size() < bestParentRow + 1)
0164         // If the list is longer, it means that at the end of it is a descendant of the new index.
0165         // We insert the ancestors items first in that case.
0166         {
0167             break;
0168         }
0169 
0170         const QModelIndex nextSibling = ansList.value(bestParentRow + 1);
0171 
0172         if (!nextSibling.isValid()) {
0173             continue;
0174         }
0175 
0176         if (youngestAncestor.row() <= nextSibling.row()) {
0177             break;
0178         }
0179 
0180         siblingOffset++;
0181 
0182         if (rootAncestors.size() <= firstCommonParent + siblingOffset) {
0183             break;
0184         }
0185 
0186         ansList = rootAncestors.at(firstCommonParent + siblingOffset);
0187 
0188         // In the scenario above, E is selected after D, causing this loop to be entered,
0189         // and requiring a similar result if the next sibling in the proxy model does not have children.
0190         if (ansList.size() <= bestParentRow) {
0191             break;
0192         }
0193 
0194         nextParent = ansList.at(bestParentRow);
0195     }
0196 
0197     return firstCommonParent + siblingOffset;
0198 }
0199 
0200 /**
0201   Determines the correct location to insert @p index into @p list.
0202 */
0203 static int getRootListRow(const QList<QPersistentModelIndex> &list, const QModelIndex &index)
0204 {
0205     if (!index.isValid()) {
0206         return -1;
0207     }
0208 
0209     if (list.isEmpty()) {
0210         return 0;
0211     }
0212 
0213     // What's going on?
0214     // Consider a tree like
0215     //
0216     // A
0217     // - B
0218     // - - C
0219     // - - - D
0220     // - E
0221     // - F
0222     // - - G
0223     // - - - H
0224     // - I
0225     // - - J
0226     // - K
0227     //
0228     // If D, E and J are already selected, and H is newly selected, we need to put H between E and J in the proxy model.
0229     // To figure that out, we create a list for each already selected index of its ancestors. Then,
0230     // we climb the ancestors of H until we reach an index with siblings which have a descendant
0231     // selected (F above has siblings B, E and I which have descendants which are already selected).
0232     // Those child indexes are traversed to find the right sibling to put F beside.
0233     //
0234     // i.e., new items are inserted in the expected location.
0235 
0236     QList<QModelIndexList> rootAncestors;
0237     for (const auto &root : list) {
0238         QModelIndexList ancestors;
0239         ancestors.append(root);
0240         QModelIndex parent = root.parent();
0241         while (parent.isValid()) {
0242             ancestors.prepend(parent);
0243             parent = parent.parent();
0244         }
0245         ancestors.prepend(QModelIndex());
0246         rootAncestors.append(ancestors);
0247     }
0248     return _getRootListRow(rootAncestors, index);
0249 }
0250 
0251 /**
0252   Returns a selection in which no descendants of selected indexes are also themselves selected.
0253   For example,
0254   @code
0255     A
0256     - B
0257     C
0258     D
0259   @endcode
0260   If A, B and D are selected in @p selection, the returned selection contains only A and D.
0261 */
0262 static QItemSelection getRootRanges(const QItemSelection &_selection)
0263 {
0264     QItemSelection rootSelection;
0265     QItemSelection selection = _selection;
0266     QList<QItemSelectionRange>::iterator it = selection.begin();
0267     while (it != selection.end()) {
0268         if (!it->topLeft().parent().isValid()) {
0269             rootSelection.append(*it);
0270             it = selection.erase(it);
0271         } else {
0272             ++it;
0273         }
0274     }
0275 
0276     it = selection.begin();
0277     while (it != selection.end()) {
0278         const QItemSelectionRange range = *it;
0279         it = selection.erase(it);
0280 
0281         if (isDescendantOf(rootSelection, range.topLeft()) || isDescendantOf(selection, range.topLeft())) {
0282             continue;
0283         }
0284 
0285         rootSelection << range;
0286     }
0287     return rootSelection;
0288 }
0289 
0290 /**
0291  */
0292 struct RangeLessThan {
0293     bool operator()(const QItemSelectionRange &left, const QItemSelectionRange &right) const
0294     {
0295         if (right.model() == left.model()) {
0296             // parent has to be calculated, so we only do so once.
0297             const QModelIndex topLeftParent = left.parent();
0298             const QModelIndex otherTopLeftParent = right.parent();
0299             if (topLeftParent == otherTopLeftParent) {
0300                 if (right.top() == left.top()) {
0301                     if (right.left() == left.left()) {
0302                         if (right.bottom() == left.bottom()) {
0303                             return left.right() < right.right();
0304                         }
0305                         return left.bottom() < right.bottom();
0306                     }
0307                     return left.left() < right.left();
0308                 }
0309                 return left.top() < right.top();
0310             }
0311             return topLeftParent < otherTopLeftParent;
0312         }
0313         return left.model() < right.model();
0314     }
0315 };
0316 
0317 static QItemSelection stableNormalizeSelection(const QItemSelection &selection)
0318 {
0319     if (selection.size() <= 1) {
0320         return selection;
0321     }
0322 
0323     QItemSelection::const_iterator it = selection.begin();
0324     const QItemSelection::const_iterator end = selection.end();
0325 
0326     Q_ASSERT(it != end);
0327     QItemSelection::const_iterator scout = it + 1;
0328 
0329     QItemSelection result;
0330     while (scout != end) {
0331         Q_ASSERT(it != end);
0332         int bottom = it->bottom();
0333         while (scout != end && it->parent() == scout->parent() && bottom + 1 == scout->top()) {
0334             bottom = scout->bottom();
0335             ++scout;
0336         }
0337         if (bottom != it->bottom()) {
0338             const QModelIndex topLeft = it->topLeft();
0339             result << QItemSelectionRange(topLeft, topLeft.sibling(bottom, it->right()));
0340         }
0341         Q_ASSERT(it != scout);
0342         if (scout == end) {
0343             break;
0344         }
0345         if (it + 1 == scout) {
0346             result << *it;
0347         }
0348         it = scout;
0349         ++scout;
0350         if (scout == end) {
0351             result << *it;
0352         }
0353     }
0354     return result;
0355 }
0356 
0357 static QItemSelection kNormalizeSelection(QItemSelection selection)
0358 {
0359     if (selection.size() <= 1) {
0360         return selection;
0361     }
0362 
0363     // KSelectionProxyModel has a strong assumption that
0364     // the views always select rows, so usually the
0365     // @p selection here contains ranges that span all
0366     // columns. However, if a QSortFilterProxyModel
0367     // is used too, it splits up the complete ranges into
0368     // one index per range. That confuses the data structures
0369     // held by this proxy (which keeps track of indexes in the
0370     // first column). As this proxy already assumes that if the
0371     // zeroth column is selected, then its entire row is selected,
0372     // we can safely remove the ranges which do not include
0373     // column 0 without a loss of functionality.
0374     QItemSelection::iterator i = selection.begin();
0375     while (i != selection.end()) {
0376         if (i->left() > 0) {
0377             i = selection.erase(i);
0378         } else {
0379             ++i;
0380         }
0381     }
0382 
0383     RangeLessThan lt;
0384     std::sort(selection.begin(), selection.end(), lt);
0385     return stableNormalizeSelection(selection);
0386 }
0387 
0388 class KSelectionProxyModelPrivate
0389 {
0390 public:
0391     KSelectionProxyModelPrivate(KSelectionProxyModel *model)
0392         : q_ptr(model)
0393         , m_indexMapper(nullptr)
0394         , m_startWithChildTrees(false)
0395         , m_omitChildren(false)
0396         , m_omitDescendants(false)
0397         , m_includeAllSelected(false)
0398         , m_rowsInserted(false)
0399         , m_rowsRemoved(false)
0400         , m_recreateFirstChildMappingOnRemoval(false)
0401         , m_rowsMoved(false)
0402         , m_resetting(false)
0403         , m_sourceModelResetting(false)
0404         , m_doubleResetting(false)
0405         , m_layoutChanging(false)
0406         , m_ignoreNextLayoutAboutToBeChanged(false)
0407         , m_ignoreNextLayoutChanged(false)
0408         , m_selectionModel(nullptr)
0409         , m_filterBehavior(KSelectionProxyModel::InvalidBehavior)
0410     {
0411     }
0412 
0413     Q_DECLARE_PUBLIC(KSelectionProxyModel)
0414     KSelectionProxyModel *const q_ptr;
0415 
0416     // A unique id is generated for each parent. It is used for the internalPointer of its children in the proxy
0417     // This is used to store a unique id for QModelIndexes in the proxy which have children.
0418     // If an index newly gets children it is added to this hash. If its last child is removed it is removed from this map.
0419     // If this map contains an index, that index hasChildren(). This hash is populated when new rows are inserted in the
0420     // source model, or a new selection is made.
0421     mutable ParentMapping m_parentIds;
0422     // This mapping maps indexes with children in the source to indexes with children in the proxy.
0423     // The order of indexes in this list is not relevant.
0424     mutable SourceProxyIndexMapping m_mappedParents;
0425 
0426     KVoidPointerFactory<> m_voidPointerFactory;
0427 
0428     /**
0429       Keeping Persistent indexes from this model in this model breaks in certain situations
0430       such as after source insert, but before calling endInsertRows in this model. In such a state,
0431       the persistent indexes are not updated, but the methods assume they are already up-to-date.
0432 
0433       Instead of using persistentindexes for proxy indexes in m_mappedParents, we maintain them ourselves with this method.
0434 
0435       m_mappedParents and m_parentIds are affected.
0436 
0437       @p parent and @p start refer to the proxy model. Any rows >= @p start will be updated.
0438       @p offset is the amount that affected indexes will be changed.
0439     */
0440     void updateInternalIndexes(const QModelIndex &parent, int start, int offset);
0441 
0442     /**
0443      * Updates stored indexes in the proxy. Any proxy row >= @p start is changed by @p offset.
0444      *
0445      * This is only called to update indexes in the top level of the proxy. Most commonly that is
0446      *
0447      * m_mappedParents, m_parentIds and m_mappedFirstChildren are affected.
0448      */
0449     void updateInternalTopIndexes(int start, int offset);
0450 
0451     void updateFirstChildMapping(const QModelIndex &parent, int offset);
0452 
0453     bool isFlat() const
0454     {
0455         return m_omitChildren || (m_omitDescendants && m_startWithChildTrees);
0456     }
0457 
0458     /**
0459      * Tries to ensure that @p parent is a mapped parent in the proxy.
0460      * Returns true if parent is mappable in the model, and false otherwise.
0461      */
0462     bool ensureMappable(const QModelIndex &parent) const;
0463     bool parentIsMappable(const QModelIndex &parent) const
0464     {
0465         return parentAlreadyMapped(parent) || m_rootIndexList.contains(parent);
0466     }
0467 
0468     /**
0469      * Maps @p parent to source if it is already mapped, and otherwise returns an invalid QModelIndex.
0470      */
0471     QModelIndex mapFromSource(const QModelIndex &parent) const;
0472 
0473     /**
0474       Creates mappings in m_parentIds and m_mappedParents between the source and the proxy.
0475 
0476       This is not recursive
0477     */
0478     void createParentMappings(const QModelIndex &parent, int start, int end) const;
0479     void createFirstChildMapping(const QModelIndex &parent, int proxyRow) const;
0480     bool firstChildAlreadyMapped(const QModelIndex &firstChild) const;
0481     bool parentAlreadyMapped(const QModelIndex &parent) const;
0482     void removeFirstChildMappings(int start, int end);
0483     void removeParentMappings(const QModelIndex &parent, int start, int end);
0484 
0485     /**
0486       Given a QModelIndex in the proxy, return the corresponding QModelIndex in the source.
0487 
0488       This method works only if the index has children in the proxy model which already has a mapping from the source.
0489 
0490       This means that if the proxy is a flat list, this method will always return QModelIndex(). Additionally, it means that m_mappedParents is not populated
0491       automatically and must be populated manually.
0492 
0493       No new mapping is created by this method.
0494     */
0495     QModelIndex mapParentToSource(const QModelIndex &proxyParent) const;
0496 
0497     /**
0498       Given a QModelIndex in the source model, return the corresponding QModelIndex in the proxy.
0499 
0500       This method works only if the index has children in the proxy model which already has a mapping from the source.
0501 
0502       No new mapping is created by this method.
0503     */
0504     QModelIndex mapParentFromSource(const QModelIndex &sourceParent) const;
0505 
0506     QModelIndex mapTopLevelToSource(int row, int column) const;
0507     QModelIndex mapTopLevelFromSource(const QModelIndex &sourceIndex) const;
0508     QModelIndex createTopLevelIndex(int row, int column) const;
0509     int topLevelRowCount() const;
0510 
0511     void *parentId(const QModelIndex &proxyParent) const
0512     {
0513         return m_parentIds.rightToLeft(proxyParent);
0514     }
0515     QModelIndex parentForId(void *id) const
0516     {
0517         return m_parentIds.leftToRight(id);
0518     }
0519 
0520     // Only populated if m_startWithChildTrees.
0521 
0522     mutable SourceIndexProxyRowMapping m_mappedFirstChildren;
0523 
0524     // Source list is the selection in the source model.
0525     QList<QPersistentModelIndex> m_rootIndexList;
0526 
0527     KModelIndexProxyMapper *m_indexMapper;
0528 
0529     QPair<int, int> beginRemoveRows(const QModelIndex &parent, int start, int end) const;
0530     QPair<int, int> beginInsertRows(const QModelIndex &parent, int start, int end) const;
0531     void endRemoveRows(const QModelIndex &sourceParent, int proxyStart, int proxyEnd);
0532     void endInsertRows(const QModelIndex &parent, int start, int end);
0533 
0534     void sourceRowsAboutToBeInserted(const QModelIndex &parent, int start, int end);
0535     void sourceRowsInserted(const QModelIndex &parent, int start, int end);
0536     void sourceRowsAboutToBeRemoved(const QModelIndex &parent, int start, int end);
0537     void sourceRowsRemoved(const QModelIndex &parent, int start, int end);
0538     void sourceRowsAboutToBeMoved(const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow);
0539     void sourceRowsMoved(const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow);
0540     void sourceModelAboutToBeReset();
0541     void sourceModelReset();
0542     void sourceLayoutAboutToBeChanged();
0543     void sourceLayoutChanged();
0544     void emitContinuousRanges(const QModelIndex &sourceFirst, const QModelIndex &sourceLast, const QModelIndex &proxyFirst, const QModelIndex &proxyLast);
0545     void sourceDataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight);
0546 
0547     void removeSelectionFromProxy(const QItemSelection &selection);
0548 
0549     void selectionChanged(const QItemSelection &selected, const QItemSelection &deselected);
0550     void sourceModelDestroyed();
0551 
0552     void resetInternalData();
0553 
0554     bool rootWillBeRemoved(const QItemSelection &selection, const QModelIndex &root);
0555 
0556     /**
0557       When items are inserted or removed in the m_startWithChildTrees configuration,
0558       this method helps find the startRow for use emitting the signals from the proxy.
0559     */
0560     int getProxyInitialRow(const QModelIndex &parent) const;
0561 
0562     /**
0563       If m_startWithChildTrees is true, this method returns the row in the proxy model to insert newIndex
0564       items.
0565 
0566       This is a special case because the items above rootListRow in the list are not in the model, but
0567       their children are. Those children must be counted.
0568 
0569       If m_startWithChildTrees is false, this method returns @p rootListRow.
0570     */
0571     int getTargetRow(int rootListRow);
0572 
0573     /**
0574       Inserts the indexes in @p list into the proxy model.
0575     */
0576     void insertSelectionIntoProxy(const QItemSelection &selection);
0577 
0578     bool m_startWithChildTrees;
0579     bool m_omitChildren;
0580     bool m_omitDescendants;
0581     bool m_includeAllSelected;
0582     bool m_rowsInserted;
0583     bool m_rowsRemoved;
0584     bool m_recreateFirstChildMappingOnRemoval;
0585     QPair<int, int> m_proxyRemoveRows;
0586     bool m_rowsMoved;
0587     bool m_resetting;
0588     bool m_sourceModelResetting;
0589     bool m_doubleResetting;
0590     bool m_layoutChanging;
0591     bool m_ignoreNextLayoutAboutToBeChanged;
0592     bool m_ignoreNextLayoutChanged;
0593     QPointer<QItemSelectionModel> m_selectionModel;
0594 
0595     KSelectionProxyModel::FilterBehavior m_filterBehavior;
0596 
0597     QList<QPersistentModelIndex> m_layoutChangePersistentIndexes;
0598     QModelIndexList m_proxyIndexes;
0599 
0600     struct PendingSelectionChange {
0601         PendingSelectionChange()
0602         {
0603         }
0604         PendingSelectionChange(const QItemSelection &selected_, const QItemSelection &deselected_)
0605             : selected(selected_)
0606             , deselected(deselected_)
0607         {
0608         }
0609         QItemSelection selected;
0610         QItemSelection deselected;
0611     };
0612     QList<PendingSelectionChange> m_pendingSelectionChanges;
0613     QMetaObject::Connection selectionModelModelAboutToBeResetConnection;
0614     QMetaObject::Connection selectionModelModelResetConnection;
0615 };
0616 
0617 void KSelectionProxyModelPrivate::emitContinuousRanges(const QModelIndex &sourceFirst,
0618                                                        const QModelIndex &sourceLast,
0619                                                        const QModelIndex &proxyFirst,
0620                                                        const QModelIndex &proxyLast)
0621 {
0622     Q_Q(KSelectionProxyModel);
0623 
0624     Q_ASSERT(sourceFirst.model() == q->sourceModel());
0625     Q_ASSERT(sourceLast.model() == q->sourceModel());
0626     Q_ASSERT(proxyFirst.model() == q);
0627     Q_ASSERT(proxyLast.model() == q);
0628 
0629     const int proxyRangeSize = proxyLast.row() - proxyFirst.row();
0630     const int sourceRangeSize = sourceLast.row() - sourceFirst.row();
0631 
0632     if (proxyRangeSize == sourceRangeSize) {
0633         Q_EMIT q->dataChanged(proxyFirst, proxyLast);
0634         return;
0635     }
0636 
0637     // TODO: Loop to skip descendant ranges.
0638     //     int lastRow;
0639     //
0640     //     const QModelIndex sourceHalfWay = sourceFirst.sibling(sourceFirst.row() + (sourceRangeSize / 2));
0641     //     const QModelIndex proxyHalfWay = proxyFirst.sibling(proxyFirst.row() + (proxyRangeSize / 2));
0642     //     const QModelIndex mappedSourceHalfway = q->mapToSource(proxyHalfWay);
0643     //
0644     //     const int halfProxyRange = mappedSourceHalfway.row() - proxyFirst.row();
0645     //     const int halfSourceRange = sourceHalfWay.row() - sourceFirst.row();
0646     //
0647     //     if (proxyRangeSize == sourceRangeSize)
0648     //     {
0649     //         Q_EMIT q->dataChanged(proxyFirst, proxyLast.sibling(proxyFirst.row() + proxyRangeSize, proxyLast.column()));
0650     //         return;
0651     //     }
0652 
0653     Q_EMIT q->dataChanged(proxyFirst, proxyLast);
0654 }
0655 
0656 void KSelectionProxyModelPrivate::sourceDataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight)
0657 {
0658     Q_Q(KSelectionProxyModel);
0659 
0660     Q_ASSERT(topLeft.model() == q->sourceModel());
0661     Q_ASSERT(bottomRight.model() == q->sourceModel());
0662 
0663     const QModelIndex sourceRangeParent = topLeft.parent();
0664     if (!sourceRangeParent.isValid() && m_startWithChildTrees && !m_rootIndexList.contains(sourceRangeParent)) {
0665         return;
0666     }
0667 
0668     const QModelIndex proxyTopLeft = q->mapFromSource(topLeft);
0669     const QModelIndex proxyBottomRight = q->mapFromSource(bottomRight);
0670 
0671     const QModelIndex proxyRangeParent = proxyTopLeft.parent();
0672 
0673     if (!m_omitChildren && m_omitDescendants && m_startWithChildTrees && m_includeAllSelected) {
0674         // ChildrenOfExactSelection
0675         if (proxyTopLeft.isValid()) {
0676             emitContinuousRanges(topLeft, bottomRight, proxyTopLeft, proxyBottomRight);
0677         }
0678         return;
0679     }
0680 
0681     if ((m_omitChildren && !m_startWithChildTrees && m_includeAllSelected) || (!proxyRangeParent.isValid() && !m_startWithChildTrees)) {
0682         // Exact selection and SubTreeRoots and SubTrees in top level
0683         // Emit continuous ranges.
0684         QList<int> changedRows;
0685         for (int row = topLeft.row(); row <= bottomRight.row(); ++row) {
0686             const QModelIndex index = q->sourceModel()->index(row, topLeft.column(), topLeft.parent());
0687             const int idx = m_rootIndexList.indexOf(index);
0688             if (idx != -1) {
0689                 changedRows.append(idx);
0690             }
0691         }
0692         if (changedRows.isEmpty()) {
0693             return;
0694         }
0695         int first = changedRows.first();
0696         int previous = first;
0697         QList<int>::const_iterator it = changedRows.constBegin();
0698         const QList<int>::const_iterator end = changedRows.constEnd();
0699         for (; it != end; ++it) {
0700             if (*it == previous + 1) {
0701                 ++previous;
0702             } else {
0703                 const QModelIndex _top = q->index(first, topLeft.column());
0704                 const QModelIndex _bottom = q->index(previous, bottomRight.column());
0705                 Q_EMIT q->dataChanged(_top, _bottom);
0706                 previous = first = *it;
0707             }
0708         }
0709         if (first != previous) {
0710             const QModelIndex _top = q->index(first, topLeft.column());
0711             const QModelIndex _bottom = q->index(previous, bottomRight.column());
0712             Q_EMIT q->dataChanged(_top, _bottom);
0713         }
0714         return;
0715     }
0716     if (proxyRangeParent.isValid()) {
0717         if (m_omitChildren && !m_startWithChildTrees && !m_includeAllSelected)
0718         // SubTreeRoots
0719         {
0720             return;
0721         }
0722         if (!proxyTopLeft.isValid()) {
0723             return;
0724         }
0725         // SubTrees and SubTreesWithoutRoots
0726         Q_EMIT q->dataChanged(proxyTopLeft, proxyBottomRight);
0727         return;
0728     }
0729 
0730     if (m_startWithChildTrees && !m_omitChildren && !m_includeAllSelected && !m_omitDescendants) {
0731         // SubTreesWithoutRoots
0732         if (proxyTopLeft.isValid()) {
0733             Q_EMIT q->dataChanged(proxyTopLeft, proxyBottomRight);
0734         }
0735         return;
0736     }
0737 }
0738 
0739 void KSelectionProxyModelPrivate::sourceLayoutAboutToBeChanged()
0740 {
0741     Q_Q(KSelectionProxyModel);
0742 
0743     if (m_ignoreNextLayoutAboutToBeChanged) {
0744         m_ignoreNextLayoutAboutToBeChanged = false;
0745         return;
0746     }
0747 
0748     if (m_rootIndexList.isEmpty()) {
0749         return;
0750     }
0751 
0752     Q_EMIT q->layoutAboutToBeChanged();
0753 
0754     QItemSelection selection;
0755     for (const auto &rootIndex : std::as_const(m_rootIndexList)) {
0756         // This will be optimized later.
0757         Q_EMIT q->rootIndexAboutToBeRemoved(rootIndex, KSelectionProxyModel::QPrivateSignal());
0758         selection.append(QItemSelectionRange(rootIndex, rootIndex));
0759     }
0760 
0761     selection = kNormalizeSelection(selection);
0762     Q_EMIT q->rootSelectionAboutToBeRemoved(selection, KSelectionProxyModel::QPrivateSignal());
0763 
0764     QPersistentModelIndex srcPersistentIndex;
0765     const auto lst = q->persistentIndexList();
0766     for (const QModelIndex &proxyPersistentIndex : lst) {
0767         m_proxyIndexes << proxyPersistentIndex;
0768         Q_ASSERT(proxyPersistentIndex.isValid());
0769         srcPersistentIndex = q->mapToSource(proxyPersistentIndex);
0770         Q_ASSERT(srcPersistentIndex.isValid());
0771         m_layoutChangePersistentIndexes << srcPersistentIndex;
0772     }
0773 
0774     m_rootIndexList.clear();
0775 }
0776 
0777 void KSelectionProxyModelPrivate::sourceLayoutChanged()
0778 {
0779     Q_Q(KSelectionProxyModel);
0780 
0781     if (m_ignoreNextLayoutChanged) {
0782         m_ignoreNextLayoutChanged = false;
0783         return;
0784     }
0785 
0786     if (!m_selectionModel || !m_selectionModel->hasSelection()) {
0787         return;
0788     }
0789 
0790     // Handling this signal is slow.
0791     // The problem is that anything can happen between emissions of layoutAboutToBeChanged and layoutChanged.
0792     // We can't assume anything is the same about the structure anymore. items have been sorted, items which
0793     // were parents before are now not, items which were not parents before now are, items which used to be the
0794     // first child are now the Nth child and items which used to be the Nth child are now the first child.
0795     // We effectively can't update our mapping because we don't have enough information to update everything.
0796     // The only way we would have is if we take a persistent index of the entire source model
0797     // on sourceLayoutAboutToBeChanged and then examine it here. That would be far too expensive.
0798     // Instead we just have to clear the entire mapping and recreate it.
0799 
0800     m_rootIndexList.clear();
0801     m_mappedFirstChildren.clear();
0802     m_mappedParents.clear();
0803     m_parentIds.clear();
0804 
0805     m_resetting = true;
0806     m_layoutChanging = true;
0807     selectionChanged(m_selectionModel->selection(), QItemSelection());
0808     m_resetting = false;
0809     m_layoutChanging = false;
0810 
0811     for (int i = 0; i < m_proxyIndexes.size(); ++i) {
0812         q->changePersistentIndex(m_proxyIndexes.at(i), q->mapFromSource(m_layoutChangePersistentIndexes.at(i)));
0813     }
0814 
0815     m_layoutChangePersistentIndexes.clear();
0816     m_proxyIndexes.clear();
0817 
0818     Q_EMIT q->layoutChanged();
0819 }
0820 
0821 void KSelectionProxyModelPrivate::resetInternalData()
0822 {
0823     m_rootIndexList.clear();
0824     m_layoutChangePersistentIndexes.clear();
0825     m_proxyIndexes.clear();
0826     m_mappedParents.clear();
0827     m_parentIds.clear();
0828     m_mappedFirstChildren.clear();
0829     m_voidPointerFactory.clear();
0830 }
0831 
0832 void KSelectionProxyModelPrivate::sourceModelDestroyed()
0833 {
0834     // There is very little we can do here.
0835     resetInternalData();
0836     m_resetting = false;
0837     m_sourceModelResetting = false;
0838 }
0839 
0840 void KSelectionProxyModelPrivate::sourceModelAboutToBeReset()
0841 {
0842     Q_Q(KSelectionProxyModel);
0843 
0844     // We might be resetting as a result of the selection source model resetting.
0845     // If so we don't want to emit
0846     // sourceModelAboutToBeReset
0847     // sourceModelAboutToBeReset
0848     // sourceModelReset
0849     // sourceModelReset
0850     // So we ensure that we just emit one.
0851     if (m_resetting) {
0852         // If both the source model and the selection source model are reset,
0853         // We want to begin our reset before the first one is reset and end
0854         // it after the second one is reset.
0855         m_doubleResetting = true;
0856         return;
0857     }
0858 
0859     q->beginResetModel();
0860     m_resetting = true;
0861     m_sourceModelResetting = true;
0862 }
0863 
0864 void KSelectionProxyModelPrivate::sourceModelReset()
0865 {
0866     Q_Q(KSelectionProxyModel);
0867 
0868     if (m_doubleResetting) {
0869         m_doubleResetting = false;
0870         return;
0871     }
0872 
0873     resetInternalData();
0874     m_sourceModelResetting = false;
0875     m_resetting = false;
0876     selectionChanged(m_selectionModel->selection(), QItemSelection());
0877     q->endResetModel();
0878 }
0879 
0880 int KSelectionProxyModelPrivate::getProxyInitialRow(const QModelIndex &parent) const
0881 {
0882     Q_ASSERT(m_rootIndexList.contains(parent));
0883 
0884     // The difficulty here is that parent and parent.parent() might both be in the m_rootIndexList.
0885 
0886     // - A
0887     // - B
0888     // - - C
0889     // - - D
0890     // - - - E
0891 
0892     // Consider that B and D are selected. The proxy model is:
0893 
0894     // - C
0895     // - D
0896     // - E
0897 
0898     // Then D gets a new child at 0. In that case we require adding F between D and E.
0899 
0900     // Consider instead that D gets removed. Then @p parent will be B.
0901 
0902     Q_Q(const KSelectionProxyModel);
0903 
0904     Q_ASSERT(parent.model() == q->sourceModel());
0905 
0906     int parentPosition = m_rootIndexList.indexOf(parent);
0907 
0908     QModelIndex parentAbove;
0909 
0910     // If parentPosition == 0, then parent.parent() is not also in the model. (ordering is preserved)
0911     while (parentPosition > 0) {
0912         parentPosition--;
0913 
0914         parentAbove = m_rootIndexList.at(parentPosition);
0915         Q_ASSERT(parentAbove.isValid());
0916 
0917         int rows = q->sourceModel()->rowCount(parentAbove);
0918         if (rows > 0) {
0919             QModelIndex sourceIndexAbove = q->sourceModel()->index(rows - 1, 0, parentAbove);
0920             Q_ASSERT(sourceIndexAbove.isValid());
0921             QModelIndex proxyChildAbove = mapFromSource(sourceIndexAbove);
0922             Q_ASSERT(proxyChildAbove.isValid());
0923             return proxyChildAbove.row() + 1;
0924         }
0925     }
0926     return 0;
0927 }
0928 
0929 void KSelectionProxyModelPrivate::updateFirstChildMapping(const QModelIndex &parent, int offset)
0930 {
0931     Q_Q(KSelectionProxyModel);
0932 
0933     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
0934 
0935     static const int column = 0;
0936     static const int row = 0;
0937 
0938     const QPersistentModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
0939 
0940     const QPersistentModelIndex previousFirstChild = q->sourceModel()->index(offset, column, parent);
0941 
0942     SourceIndexProxyRowMapping::left_iterator it = m_mappedFirstChildren.findLeft(previousFirstChild);
0943     if (it == m_mappedFirstChildren.leftEnd()) {
0944         return;
0945     }
0946 
0947     Q_ASSERT(srcIndex.isValid());
0948     const int proxyRow = it.value();
0949     Q_ASSERT(proxyRow >= 0);
0950 
0951     m_mappedFirstChildren.eraseLeft(it);
0952 
0953     // The proxy row in the mapping has already been updated by the offset in updateInternalTopIndexes
0954     // so we restore it by applying the reverse.
0955     m_mappedFirstChildren.insert(srcIndex, proxyRow - offset);
0956 }
0957 
0958 QPair<int, int> KSelectionProxyModelPrivate::beginInsertRows(const QModelIndex &parent, int start, int end) const
0959 {
0960     const QModelIndex proxyParent = mapFromSource(parent);
0961 
0962     if (!proxyParent.isValid()) {
0963         if (!m_startWithChildTrees) {
0964             return qMakePair(-1, -1);
0965         }
0966 
0967         if (!m_rootIndexList.contains(parent)) {
0968             return qMakePair(-1, -1);
0969         }
0970     }
0971 
0972     if (!m_startWithChildTrees) {
0973         // SubTrees
0974         if (proxyParent.isValid()) {
0975             return qMakePair(start, end);
0976         }
0977         return qMakePair(-1, -1);
0978     }
0979 
0980     if (!m_includeAllSelected && proxyParent.isValid()) {
0981         // SubTreesWithoutRoots deeper than topLevel
0982         return qMakePair(start, end);
0983     }
0984 
0985     if (!m_rootIndexList.contains(parent)) {
0986         return qMakePair(-1, -1);
0987     }
0988 
0989     const int proxyStartRow = getProxyInitialRow(parent) + start;
0990     return qMakePair(proxyStartRow, proxyStartRow + (end - start));
0991 }
0992 
0993 void KSelectionProxyModelPrivate::sourceRowsAboutToBeInserted(const QModelIndex &parent, int start, int end)
0994 {
0995     Q_Q(KSelectionProxyModel);
0996 
0997     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
0998 
0999     if (!m_selectionModel || !m_selectionModel->hasSelection()) {
1000         return;
1001     }
1002 
1003     if (m_omitChildren)
1004     // ExactSelection and SubTreeRoots
1005     {
1006         return;
1007     }
1008 
1009     // topLevel insertions can be ignored because topLevel items would need to be selected to affect the proxy.
1010     if (!parent.isValid()) {
1011         return;
1012     }
1013 
1014     QPair<int, int> pair = beginInsertRows(parent, start, end);
1015     if (pair.first == -1) {
1016         return;
1017     }
1018 
1019     const QModelIndex proxyParent = m_startWithChildTrees ? QModelIndex() : mapFromSource(parent);
1020 
1021     m_rowsInserted = true;
1022     q->beginInsertRows(proxyParent, pair.first, pair.second);
1023 }
1024 
1025 void KSelectionProxyModelPrivate::endInsertRows(const QModelIndex &parent, int start, int end)
1026 {
1027     Q_Q(const KSelectionProxyModel);
1028     const QModelIndex proxyParent = mapFromSource(parent);
1029     const int offset = end - start + 1;
1030 
1031     const bool isNewParent = (q->sourceModel()->rowCount(parent) == offset);
1032 
1033     if (m_startWithChildTrees && m_rootIndexList.contains(parent)) {
1034         const int proxyInitialRow = getProxyInitialRow(parent);
1035         Q_ASSERT(proxyInitialRow >= 0);
1036         const int proxyStartRow = proxyInitialRow + start;
1037 
1038         updateInternalTopIndexes(proxyStartRow, offset);
1039         if (isNewParent) {
1040             createFirstChildMapping(parent, proxyStartRow);
1041         } else if (start == 0)
1042         // We already have a first child mapping, but what we have mapped is not the first child anymore
1043         // so we need to update it.
1044         {
1045             updateFirstChildMapping(parent, end + 1);
1046         }
1047     } else {
1048         Q_ASSERT(proxyParent.isValid());
1049         if (!isNewParent) {
1050             updateInternalIndexes(proxyParent, start, offset);
1051         } else {
1052             createParentMappings(parent.parent(), parent.row(), parent.row());
1053         }
1054     }
1055     createParentMappings(parent, start, end);
1056 }
1057 
1058 void KSelectionProxyModelPrivate::sourceRowsInserted(const QModelIndex &parent, int start, int end)
1059 {
1060     Q_Q(KSelectionProxyModel);
1061 
1062     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1063 
1064     if (!m_rowsInserted) {
1065         return;
1066     }
1067     m_rowsInserted = false;
1068     endInsertRows(parent, start, end);
1069     q->endInsertRows();
1070     for (const PendingSelectionChange &pendingChange : std::as_const(m_pendingSelectionChanges)) {
1071         selectionChanged(pendingChange.selected, pendingChange.deselected);
1072     }
1073     m_pendingSelectionChanges.clear();
1074 }
1075 
1076 static bool rootWillBeRemovedFrom(const QModelIndex &ancestor, int start, int end, const QModelIndex &root)
1077 {
1078     Q_ASSERT(root.isValid());
1079 
1080     auto parent = root;
1081     while (parent.isValid()) {
1082         auto prev = parent;
1083         parent = parent.parent();
1084         if (parent == ancestor) {
1085             return (prev.row() <= end && prev.row() >= start);
1086         }
1087     }
1088     return false;
1089 }
1090 
1091 bool KSelectionProxyModelPrivate::rootWillBeRemoved(const QItemSelection &selection, const QModelIndex &root)
1092 {
1093     Q_ASSERT(root.isValid());
1094 
1095     for (auto &r : selection) {
1096         if (m_includeAllSelected) {
1097             if (r.parent() == root.parent() && root.row() <= r.bottom() && root.row() >= r.top()) {
1098                 return true;
1099             }
1100         } else {
1101             if (rootWillBeRemovedFrom(r.parent(), r.top(), r.bottom(), root)) {
1102                 return true;
1103             }
1104         }
1105     }
1106     return false;
1107 }
1108 
1109 QPair<int, int> KSelectionProxyModelPrivate::beginRemoveRows(const QModelIndex &parent, int start, int end) const
1110 {
1111     Q_Q(const KSelectionProxyModel);
1112 
1113     if (!m_includeAllSelected && !m_omitChildren) {
1114         // SubTrees and SubTreesWithoutRoots
1115         const QModelIndex proxyParent = mapParentFromSource(parent);
1116         if (proxyParent.isValid()) {
1117             return qMakePair(start, end);
1118         }
1119     }
1120 
1121     if (m_startWithChildTrees && m_rootIndexList.contains(parent)) {
1122         const int proxyStartRow = getProxyInitialRow(parent) + start;
1123         const int proxyEndRow = proxyStartRow + (end - start);
1124         return qMakePair(proxyStartRow, proxyEndRow);
1125     }
1126 
1127     QList<QPersistentModelIndex>::const_iterator rootIt = m_rootIndexList.constBegin();
1128     const QList<QPersistentModelIndex>::const_iterator rootEnd = m_rootIndexList.constEnd();
1129     int proxyStartRemove = 0;
1130 
1131     for (; rootIt != rootEnd; ++rootIt) {
1132         if (rootWillBeRemovedFrom(parent, start, end, *rootIt)) {
1133             break;
1134         } else {
1135             if (m_startWithChildTrees) {
1136                 proxyStartRemove += q->sourceModel()->rowCount(*rootIt);
1137             } else {
1138                 ++proxyStartRemove;
1139             }
1140         }
1141     }
1142 
1143     if (rootIt == rootEnd) {
1144         return qMakePair(-1, -1);
1145     }
1146 
1147     int proxyEndRemove = proxyStartRemove;
1148 
1149     for (; rootIt != rootEnd; ++rootIt) {
1150         if (!rootWillBeRemovedFrom(parent, start, end, *rootIt)) {
1151             break;
1152         }
1153         if (m_startWithChildTrees) {
1154             proxyEndRemove += q->sourceModel()->rowCount(*rootIt);
1155         } else {
1156             ++proxyEndRemove;
1157         }
1158     }
1159 
1160     --proxyEndRemove;
1161     if (proxyEndRemove >= proxyStartRemove) {
1162         return qMakePair(proxyStartRemove, proxyEndRemove);
1163     }
1164     return qMakePair(-1, -1);
1165 }
1166 
1167 void KSelectionProxyModelPrivate::sourceRowsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
1168 {
1169     Q_Q(KSelectionProxyModel);
1170 
1171     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1172 
1173     if (!m_selectionModel || !m_selectionModel->hasSelection()) {
1174         return;
1175     }
1176 
1177     QPair<int, int> pair = beginRemoveRows(parent, start, end);
1178     if (pair.first == -1) {
1179         return;
1180     }
1181 
1182     const QModelIndex proxyParent = mapParentFromSource(parent);
1183 
1184     m_rowsRemoved = true;
1185     m_proxyRemoveRows = pair;
1186     m_recreateFirstChildMappingOnRemoval = m_mappedFirstChildren.leftContains(q->sourceModel()->index(start, 0, parent));
1187     q->beginRemoveRows(proxyParent, pair.first, pair.second);
1188 }
1189 
1190 void KSelectionProxyModelPrivate::endRemoveRows(const QModelIndex &sourceParent, int proxyStart, int proxyEnd)
1191 {
1192     const QModelIndex proxyParent = mapParentFromSource(sourceParent);
1193 
1194     // We need to make sure to remove entries from the mappings before updating internal indexes.
1195 
1196     // - A
1197     // - - B
1198     // - C
1199     // - - D
1200 
1201     // If A and C are selected, B and D are in the proxy. B maps to row 0 and D maps to row 1.
1202     // If B is then deleted leaving only D in the proxy, D needs to be updated to be a mapping
1203     // to row 0 instead of row 1. If that is done before removing the mapping for B, then the mapping
1204     // for D would overwrite the mapping for B and then the code for removing mappings would incorrectly
1205     // remove D.
1206     // So we first remove B and then update D.
1207 
1208     {
1209         SourceProxyIndexMapping::right_iterator it = m_mappedParents.rightBegin();
1210 
1211         while (it != m_mappedParents.rightEnd()) {
1212             if (!it.value().isValid()) {
1213                 m_parentIds.removeRight(it.key());
1214                 it = m_mappedParents.eraseRight(it);
1215             } else {
1216                 ++it;
1217             }
1218         }
1219     }
1220 
1221     {
1222         // Depending on what is selected at the time, a single removal in the source could invalidate
1223         // many mapped first child items at once.
1224 
1225         // - A
1226         // - B
1227         // - - C
1228         // - - D
1229         // - - - E
1230         // - - - F
1231         // - - - - G
1232         // - - - - H
1233 
1234         // If D and F are selected, the proxy contains E, F, G, H. If B is then deleted E to H will
1235         // be removed, including both first child mappings at E and G.
1236 
1237         if (!proxyParent.isValid()) {
1238             removeFirstChildMappings(proxyStart, proxyEnd);
1239         }
1240     }
1241 
1242     if (proxyParent.isValid()) {
1243         updateInternalIndexes(proxyParent, proxyEnd + 1, -1 * (proxyEnd - proxyStart + 1));
1244     } else {
1245         updateInternalTopIndexes(proxyEnd + 1, -1 * (proxyEnd - proxyStart + 1));
1246     }
1247 
1248     QList<QPersistentModelIndex>::iterator rootIt = m_rootIndexList.begin();
1249     while (rootIt != m_rootIndexList.end()) {
1250         if (!rootIt->isValid()) {
1251             rootIt = m_rootIndexList.erase(rootIt);
1252         } else {
1253             ++rootIt;
1254         }
1255     }
1256 }
1257 
1258 void KSelectionProxyModelPrivate::sourceRowsRemoved(const QModelIndex &parent, int start, int end)
1259 {
1260     Q_Q(KSelectionProxyModel);
1261     Q_UNUSED(end)
1262     Q_UNUSED(start)
1263 
1264     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1265 
1266     if (!m_selectionModel) {
1267         return;
1268     }
1269 
1270     if (!m_rowsRemoved) {
1271         return;
1272     }
1273     m_rowsRemoved = false;
1274 
1275     Q_ASSERT(m_proxyRemoveRows.first >= 0);
1276     Q_ASSERT(m_proxyRemoveRows.second >= 0);
1277     endRemoveRows(parent, m_proxyRemoveRows.first, m_proxyRemoveRows.second);
1278     if (m_recreateFirstChildMappingOnRemoval && q->sourceModel()->hasChildren(parent))
1279     // The private endRemoveRows call might remove the first child mapping for parent, so
1280     // we create it again in that case.
1281     {
1282         createFirstChildMapping(parent, m_proxyRemoveRows.first);
1283     }
1284     m_recreateFirstChildMappingOnRemoval = false;
1285 
1286     m_proxyRemoveRows = qMakePair(-1, -1);
1287     q->endRemoveRows();
1288 }
1289 
1290 void KSelectionProxyModelPrivate::sourceRowsAboutToBeMoved(const QModelIndex &srcParent, int srcStart, int srcEnd, const QModelIndex &destParent, int destRow)
1291 {
1292     Q_UNUSED(srcParent)
1293     Q_UNUSED(srcStart)
1294     Q_UNUSED(srcEnd)
1295     Q_UNUSED(destParent)
1296     Q_UNUSED(destRow)
1297     // we cheat and just act like the layout changed; this might benefit from some
1298     // optimization
1299     sourceLayoutAboutToBeChanged();
1300 }
1301 
1302 void KSelectionProxyModelPrivate::sourceRowsMoved(const QModelIndex &srcParent, int srcStart, int srcEnd, const QModelIndex &destParent, int destRow)
1303 {
1304     Q_UNUSED(srcParent)
1305     Q_UNUSED(srcStart)
1306     Q_UNUSED(srcEnd)
1307     Q_UNUSED(destParent)
1308     Q_UNUSED(destRow)
1309     // we cheat and just act like the layout changed; this might benefit from some
1310     // optimization
1311     sourceLayoutChanged();
1312 }
1313 
1314 QModelIndex KSelectionProxyModelPrivate::mapParentToSource(const QModelIndex &proxyParent) const
1315 {
1316     return m_mappedParents.rightToLeft(proxyParent);
1317 }
1318 
1319 QModelIndex KSelectionProxyModelPrivate::mapParentFromSource(const QModelIndex &sourceParent) const
1320 {
1321     return m_mappedParents.leftToRight(sourceParent);
1322 }
1323 
1324 static bool
1325 indexIsValid(bool startWithChildTrees, int row, const QList<QPersistentModelIndex> &rootIndexList, const SourceIndexProxyRowMapping &mappedFirstChildren)
1326 {
1327     if (!startWithChildTrees) {
1328         Q_ASSERT(rootIndexList.size() > row);
1329     } else {
1330         Q_ASSERT(!mappedFirstChildren.isEmpty());
1331 
1332         SourceIndexProxyRowMapping::right_const_iterator result = std::prev(mappedFirstChildren.rightUpperBound(row));
1333 
1334         Q_ASSERT(result != mappedFirstChildren.rightEnd());
1335         const int proxyFirstRow = result.key();
1336         const QModelIndex sourceFirstChild = result.value();
1337         Q_ASSERT(proxyFirstRow >= 0);
1338         Q_ASSERT(sourceFirstChild.isValid());
1339         Q_ASSERT(sourceFirstChild.parent().isValid());
1340         Q_ASSERT(row <= proxyFirstRow + sourceFirstChild.model()->rowCount(sourceFirstChild.parent()));
1341     }
1342     return true;
1343 }
1344 
1345 QModelIndex KSelectionProxyModelPrivate::createTopLevelIndex(int row, int column) const
1346 {
1347     Q_Q(const KSelectionProxyModel);
1348 
1349     Q_ASSERT(indexIsValid(m_startWithChildTrees, row, m_rootIndexList, m_mappedFirstChildren));
1350     return q->createIndex(row, column);
1351 }
1352 
1353 QModelIndex KSelectionProxyModelPrivate::mapTopLevelFromSource(const QModelIndex &sourceIndex) const
1354 {
1355     Q_Q(const KSelectionProxyModel);
1356 
1357     const QModelIndex sourceParent = sourceIndex.parent();
1358     const int row = m_rootIndexList.indexOf(sourceIndex);
1359     if (row == -1) {
1360         return QModelIndex();
1361     }
1362 
1363     if (!m_startWithChildTrees) {
1364         Q_ASSERT(m_rootIndexList.size() > row);
1365         return q->createIndex(row, sourceIndex.column());
1366     }
1367     if (!m_rootIndexList.contains(sourceParent)) {
1368         return QModelIndex();
1369     }
1370 
1371     const QModelIndex firstChild = q->sourceModel()->index(0, 0, sourceParent);
1372     const int firstProxyRow = m_mappedFirstChildren.leftToRight(firstChild);
1373 
1374     return q->createIndex(firstProxyRow + sourceIndex.row(), sourceIndex.column());
1375 }
1376 
1377 QModelIndex KSelectionProxyModelPrivate::mapFromSource(const QModelIndex &sourceIndex) const
1378 {
1379     Q_Q(const KSelectionProxyModel);
1380 
1381     const QModelIndex maybeMapped = mapParentFromSource(sourceIndex);
1382     if (maybeMapped.isValid()) {
1383         //     Q_ASSERT((!d->m_startWithChildTrees && d->m_rootIndexList.contains(maybeMapped)) ? maybeMapped.row() < 0 : true );
1384         return maybeMapped;
1385     }
1386     const QModelIndex sourceParent = sourceIndex.parent();
1387 
1388     const QModelIndex proxyParent = mapParentFromSource(sourceParent);
1389     if (proxyParent.isValid()) {
1390         void *const parentId = m_parentIds.rightToLeft(proxyParent);
1391         static const int column = 0;
1392         return q->createIndex(sourceIndex.row(), column, parentId);
1393     }
1394 
1395     const QModelIndex firstChild = q->sourceModel()->index(0, 0, sourceParent);
1396 
1397     if (m_mappedFirstChildren.leftContains(firstChild)) {
1398         const int firstProxyRow = m_mappedFirstChildren.leftToRight(firstChild);
1399         return q->createIndex(firstProxyRow + sourceIndex.row(), sourceIndex.column());
1400     }
1401     return mapTopLevelFromSource(sourceIndex);
1402 }
1403 
1404 int KSelectionProxyModelPrivate::topLevelRowCount() const
1405 {
1406     Q_Q(const KSelectionProxyModel);
1407 
1408     if (!m_startWithChildTrees) {
1409         return m_rootIndexList.size();
1410     }
1411 
1412     if (m_mappedFirstChildren.isEmpty()) {
1413         return 0;
1414     }
1415 
1416     const SourceIndexProxyRowMapping::right_const_iterator result = std::prev(m_mappedFirstChildren.rightConstEnd());
1417 
1418     const int proxyFirstRow = result.key();
1419     const QModelIndex sourceFirstChild = result.value();
1420     Q_ASSERT(sourceFirstChild.isValid());
1421     const QModelIndex sourceParent = sourceFirstChild.parent();
1422     Q_ASSERT(sourceParent.isValid());
1423     return q->sourceModel()->rowCount(sourceParent) + proxyFirstRow;
1424 }
1425 
1426 bool KSelectionProxyModelPrivate::ensureMappable(const QModelIndex &parent) const
1427 {
1428     Q_Q(const KSelectionProxyModel);
1429 
1430     if (isFlat()) {
1431         return true;
1432     }
1433 
1434     if (parentIsMappable(parent)) {
1435         return true;
1436     }
1437 
1438     QModelIndex ancestor = parent.parent();
1439     QModelIndexList ancestorList;
1440     while (ancestor.isValid()) {
1441         if (parentIsMappable(ancestor)) {
1442             break;
1443         } else {
1444             ancestorList.prepend(ancestor);
1445         }
1446 
1447         ancestor = ancestor.parent();
1448     }
1449 
1450     if (!ancestor.isValid())
1451     // @p parent is not a descendant of m_rootIndexList.
1452     {
1453         return false;
1454     }
1455 
1456     // sourceIndex can be mapped to the proxy. We just need to create mappings for its ancestors first.
1457     for (int i = 0; i < ancestorList.size(); ++i) {
1458         const QModelIndex existingAncestor = mapParentFromSource(ancestor);
1459         Q_ASSERT(existingAncestor.isValid());
1460 
1461         void *const ansId = m_parentIds.rightToLeft(existingAncestor);
1462         const QModelIndex newSourceParent = ancestorList.at(i);
1463         const QModelIndex newProxyParent = q->createIndex(newSourceParent.row(), newSourceParent.column(), ansId);
1464 
1465         void *const newId = m_voidPointerFactory.createPointer();
1466         m_parentIds.insert(newId, newProxyParent);
1467         m_mappedParents.insert(QPersistentModelIndex(newSourceParent), newProxyParent);
1468         ancestor = newSourceParent;
1469     }
1470     return true;
1471 }
1472 
1473 void KSelectionProxyModelPrivate::updateInternalTopIndexes(int start, int offset)
1474 {
1475     updateInternalIndexes(QModelIndex(), start, offset);
1476 
1477     QHash<QPersistentModelIndex, int> updates;
1478     {
1479         SourceIndexProxyRowMapping::right_iterator it = m_mappedFirstChildren.rightLowerBound(start);
1480         const SourceIndexProxyRowMapping::right_iterator end = m_mappedFirstChildren.rightEnd();
1481 
1482         for (; it != end; ++it) {
1483             updates.insert(*it, it.key() + offset);
1484         }
1485     }
1486     {
1487         QHash<QPersistentModelIndex, int>::const_iterator it = updates.constBegin();
1488         const QHash<QPersistentModelIndex, int>::const_iterator end = updates.constEnd();
1489 
1490         for (; it != end; ++it) {
1491             m_mappedFirstChildren.insert(it.key(), it.value());
1492         }
1493     }
1494 }
1495 
1496 void KSelectionProxyModelPrivate::updateInternalIndexes(const QModelIndex &parent, int start, int offset)
1497 {
1498     Q_Q(KSelectionProxyModel);
1499 
1500     Q_ASSERT(start + offset >= 0);
1501     Q_ASSERT(parent.isValid() ? parent.model() == q : true);
1502 
1503     if (isFlat()) {
1504         return;
1505     }
1506 
1507     SourceProxyIndexMapping::left_iterator mappedParentIt = m_mappedParents.leftBegin();
1508 
1509     QHash<void *, QModelIndex> updatedParentIds;
1510     QHash<QPersistentModelIndex, QModelIndex> updatedParents;
1511 
1512     for (; mappedParentIt != m_mappedParents.leftEnd(); ++mappedParentIt) {
1513         const QModelIndex proxyIndex = mappedParentIt.value();
1514         Q_ASSERT(proxyIndex.isValid());
1515 
1516         if (proxyIndex.row() < start) {
1517             continue;
1518         }
1519 
1520         const QModelIndex proxyParent = proxyIndex.parent();
1521 
1522         if (parent.isValid()) {
1523             if (proxyParent != parent) {
1524                 continue;
1525             }
1526         } else {
1527             if (proxyParent.isValid()) {
1528                 continue;
1529             }
1530         }
1531         Q_ASSERT(m_parentIds.rightContains(proxyIndex));
1532         void *const key = m_parentIds.rightToLeft(proxyIndex);
1533 
1534         const QModelIndex newIndex = q->createIndex(proxyIndex.row() + offset, proxyIndex.column(), proxyIndex.internalPointer());
1535 
1536         Q_ASSERT(newIndex.isValid());
1537 
1538         updatedParentIds.insert(key, newIndex);
1539         updatedParents.insert(mappedParentIt.key(), newIndex);
1540     }
1541 
1542     {
1543         QHash<QPersistentModelIndex, QModelIndex>::const_iterator it = updatedParents.constBegin();
1544         const QHash<QPersistentModelIndex, QModelIndex>::const_iterator end = updatedParents.constEnd();
1545         for (; it != end; ++it) {
1546             m_mappedParents.insert(it.key(), it.value());
1547         }
1548     }
1549 
1550     {
1551         QHash<void *, QModelIndex>::const_iterator it = updatedParentIds.constBegin();
1552         const QHash<void *, QModelIndex>::const_iterator end = updatedParentIds.constEnd();
1553         for (; it != end; ++it) {
1554             m_parentIds.insert(it.key(), it.value());
1555         }
1556     }
1557 }
1558 
1559 bool KSelectionProxyModelPrivate::parentAlreadyMapped(const QModelIndex &parent) const
1560 {
1561     Q_Q(const KSelectionProxyModel);
1562     Q_UNUSED(q) // except in Q_ASSERT
1563     Q_ASSERT(parent.model() == q->sourceModel());
1564     return m_mappedParents.leftContains(parent);
1565 }
1566 
1567 bool KSelectionProxyModelPrivate::firstChildAlreadyMapped(const QModelIndex &firstChild) const
1568 {
1569     Q_Q(const KSelectionProxyModel);
1570     Q_UNUSED(q) // except in Q_ASSERT
1571     Q_ASSERT(firstChild.model() == q->sourceModel());
1572     return m_mappedFirstChildren.leftContains(firstChild);
1573 }
1574 
1575 void KSelectionProxyModelPrivate::createFirstChildMapping(const QModelIndex &parent, int proxyRow) const
1576 {
1577     Q_Q(const KSelectionProxyModel);
1578 
1579     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1580 
1581     static const int column = 0;
1582     static const int row = 0;
1583 
1584     const QPersistentModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
1585 
1586     if (firstChildAlreadyMapped(srcIndex)) {
1587         return;
1588     }
1589 
1590     Q_ASSERT(srcIndex.isValid());
1591     m_mappedFirstChildren.insert(srcIndex, proxyRow);
1592 }
1593 
1594 void KSelectionProxyModelPrivate::createParentMappings(const QModelIndex &parent, int start, int end) const
1595 {
1596     if (isFlat()) {
1597         return;
1598     }
1599 
1600     Q_Q(const KSelectionProxyModel);
1601 
1602     Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1603 
1604     static const int column = 0;
1605 
1606     for (int row = start; row <= end; ++row) {
1607         const QModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
1608         Q_ASSERT(srcIndex.isValid());
1609         if (!q->sourceModel()->hasChildren(srcIndex) || parentAlreadyMapped(srcIndex)) {
1610             continue;
1611         }
1612 
1613         const QModelIndex proxyIndex = mapFromSource(srcIndex);
1614         if (!proxyIndex.isValid()) {
1615             return; // If one of them is not mapped, its siblings won't be either
1616         }
1617 
1618         void *const newId = m_voidPointerFactory.createPointer();
1619         m_parentIds.insert(newId, proxyIndex);
1620         Q_ASSERT(srcIndex.isValid());
1621         m_mappedParents.insert(QPersistentModelIndex(srcIndex), proxyIndex);
1622     }
1623 }
1624 
1625 void KSelectionProxyModelPrivate::removeFirstChildMappings(int start, int end)
1626 {
1627     SourceIndexProxyRowMapping::right_iterator it = m_mappedFirstChildren.rightLowerBound(start);
1628     const SourceIndexProxyRowMapping::right_iterator endIt = m_mappedFirstChildren.rightUpperBound(end);
1629     while (it != endIt) {
1630         it = m_mappedFirstChildren.eraseRight(it);
1631     }
1632 }
1633 
1634 void KSelectionProxyModelPrivate::removeParentMappings(const QModelIndex &parent, int start, int end)
1635 {
1636     Q_Q(KSelectionProxyModel);
1637 
1638     Q_ASSERT(parent.isValid() ? parent.model() == q : true);
1639 
1640     // collect all removals first, as executing them recursively will invalidate our iterators
1641     struct RemovalInfo {
1642         QPersistentModelIndex idx;
1643         QModelIndex sourceIdx;
1644     };
1645     std::vector<RemovalInfo> removals;
1646     removals.reserve(end - start + 1);
1647     for (auto it = m_mappedParents.rightBegin(); it != m_mappedParents.rightEnd(); ++it) {
1648         if (it.key().row() >= start && it.key().row() <= end) {
1649             const QModelIndex sourceParent = it.value();
1650             const QModelIndex proxyGrandParent = mapParentFromSource(sourceParent.parent());
1651             if (proxyGrandParent == parent) {
1652                 removals.push_back({it.key(), it.value()});
1653             }
1654         }
1655     }
1656 
1657     // execute the removals
1658     const bool flatList = isFlat();
1659     for (const auto &r : removals) {
1660         if (!flatList) {
1661             removeParentMappings(r.idx, 0, q->sourceModel()->rowCount(r.sourceIdx) - 1);
1662         }
1663         m_parentIds.removeRight(r.idx);
1664         m_mappedParents.removeRight(r.idx);
1665     }
1666 }
1667 
1668 QModelIndex KSelectionProxyModelPrivate::mapTopLevelToSource(int row, int column) const
1669 {
1670     if (!m_startWithChildTrees) {
1671         const QModelIndex idx = m_rootIndexList.at(row);
1672         return idx.sibling(idx.row(), column);
1673     }
1674 
1675     if (m_mappedFirstChildren.isEmpty()) {
1676         return QModelIndex();
1677     }
1678 
1679     SourceIndexProxyRowMapping::right_iterator result = std::prev(m_mappedFirstChildren.rightUpperBound(row));
1680 
1681     Q_ASSERT(result != m_mappedFirstChildren.rightEnd());
1682 
1683     const int proxyFirstRow = result.key();
1684     const QModelIndex sourceFirstChild = result.value();
1685     Q_ASSERT(sourceFirstChild.isValid());
1686     return sourceFirstChild.sibling(row - proxyFirstRow, column);
1687 }
1688 
1689 void KSelectionProxyModelPrivate::removeSelectionFromProxy(const QItemSelection &selection)
1690 {
1691     Q_Q(KSelectionProxyModel);
1692     if (selection.isEmpty()) {
1693         return;
1694     }
1695 
1696     QList<QPersistentModelIndex>::iterator rootIt = m_rootIndexList.begin();
1697     const QList<QPersistentModelIndex>::iterator rootEnd = m_rootIndexList.end();
1698     int proxyStartRemove = 0;
1699 
1700     for (; rootIt != rootEnd; ++rootIt) {
1701         if (rootWillBeRemoved(selection, *rootIt)) {
1702             break;
1703         } else {
1704             if (m_startWithChildTrees) {
1705                 auto rc = q->sourceModel()->rowCount(*rootIt);
1706                 proxyStartRemove += rc;
1707             } else {
1708                 ++proxyStartRemove;
1709             }
1710         }
1711     }
1712 
1713     if (rootIt == rootEnd) {
1714         return;
1715     }
1716 
1717     int proxyEndRemove = proxyStartRemove;
1718 
1719     QList<QPersistentModelIndex>::iterator rootRemoveStart = rootIt;
1720 
1721     for (; rootIt != rootEnd; ++rootIt) {
1722         if (!rootWillBeRemoved(selection, *rootIt)) {
1723             break;
1724         }
1725         q->rootIndexAboutToBeRemoved(*rootIt, KSelectionProxyModel::QPrivateSignal());
1726         if (m_startWithChildTrees) {
1727             auto rc = q->sourceModel()->rowCount(*rootIt);
1728             proxyEndRemove += rc;
1729         } else {
1730             ++proxyEndRemove;
1731         }
1732     }
1733 
1734     --proxyEndRemove;
1735     if (proxyEndRemove >= proxyStartRemove) {
1736         q->beginRemoveRows(QModelIndex(), proxyStartRemove, proxyEndRemove);
1737 
1738         rootIt = m_rootIndexList.erase(rootRemoveStart, rootIt);
1739 
1740         removeParentMappings(QModelIndex(), proxyStartRemove, proxyEndRemove);
1741         if (m_startWithChildTrees) {
1742             removeFirstChildMappings(proxyStartRemove, proxyEndRemove);
1743         }
1744         updateInternalTopIndexes(proxyEndRemove + 1, -1 * (proxyEndRemove - proxyStartRemove + 1));
1745 
1746         q->endRemoveRows();
1747     } else {
1748         rootIt = m_rootIndexList.erase(rootRemoveStart, rootIt);
1749     }
1750     if (rootIt != rootEnd) {
1751         removeSelectionFromProxy(selection);
1752     }
1753 }
1754 
1755 void KSelectionProxyModelPrivate::selectionChanged(const QItemSelection &_selected, const QItemSelection &_deselected)
1756 {
1757     Q_Q(KSelectionProxyModel);
1758 
1759     if (!q->sourceModel() || (_selected.isEmpty() && _deselected.isEmpty())) {
1760         return;
1761     }
1762 
1763     if (m_sourceModelResetting) {
1764         return;
1765     }
1766 
1767     if (m_rowsInserted || m_rowsRemoved) {
1768         m_pendingSelectionChanges.append(PendingSelectionChange(_selected, _deselected));
1769         return;
1770     }
1771 
1772     // Any deselected indexes in the m_rootIndexList are removed. Then, any
1773     // indexes in the selected range which are not a descendant of one of the already selected indexes
1774     // are inserted into the model.
1775     //
1776     // All ranges from the selection model need to be split into individual rows. Ranges which are contiguous in
1777     // the selection model may not be contiguous in the source model if there's a sort filter proxy model in the chain.
1778     //
1779     // Some descendants of deselected indexes may still be selected. The ranges in m_selectionModel->selection()
1780     // are examined. If any of the ranges are descendants of one of the
1781     // indexes in deselected, they are added to the ranges to be inserted into the model.
1782     //
1783     // The new indexes are inserted in sorted order.
1784 
1785     const QItemSelection selected = kNormalizeSelection(m_indexMapper->mapSelectionRightToLeft(_selected));
1786     const QItemSelection deselected = kNormalizeSelection(m_indexMapper->mapSelectionRightToLeft(_deselected));
1787 
1788 #if QT_VERSION < 0x040800
1789     // The QItemSelectionModel sometimes doesn't remove deselected items from its selection
1790     // Fixed in Qt 4.8 : http://qt.gitorious.org/qt/qt/merge_requests/2403
1791     QItemSelection reportedSelection = m_selectionModel->selection();
1792     reportedSelection.merge(deselected, QItemSelectionModel::Deselect);
1793     QItemSelection fullSelection = m_indexMapper->mapSelectionRightToLeft(reportedSelection);
1794 #else
1795     QItemSelection fullSelection = m_indexMapper->mapSelectionRightToLeft(m_selectionModel->selection());
1796 #endif
1797 
1798     fullSelection = kNormalizeSelection(fullSelection);
1799 
1800     QItemSelection newRootRanges;
1801     QItemSelection removedRootRanges;
1802     if (!m_includeAllSelected) {
1803         newRootRanges = getRootRanges(selected);
1804 
1805         QItemSelection existingSelection = fullSelection;
1806         // What was selected before the selection was made.
1807         existingSelection.merge(selected, QItemSelectionModel::Deselect);
1808 
1809         // This is similar to m_rootRanges, but that m_rootRanges at this point still contains the roots
1810         // of deselected and existingRootRanges does not.
1811 
1812         const QItemSelection existingRootRanges = getRootRanges(existingSelection);
1813         {
1814             QMutableListIterator<QItemSelectionRange> i(newRootRanges);
1815             while (i.hasNext()) {
1816                 const QItemSelectionRange range = i.next();
1817                 const QModelIndex topLeft = range.topLeft();
1818                 if (isDescendantOf(existingRootRanges, topLeft)) {
1819                     i.remove();
1820                 }
1821             }
1822         }
1823 
1824         QItemSelection exposedSelection;
1825         {
1826             QItemSelection deselectedRootRanges = getRootRanges(deselected);
1827             QListIterator<QItemSelectionRange> i(deselectedRootRanges);
1828             while (i.hasNext()) {
1829                 const QItemSelectionRange range = i.next();
1830                 const QModelIndex topLeft = range.topLeft();
1831                 // Consider this:
1832                 //
1833                 // - A
1834                 // - - B
1835                 // - - - C
1836                 // - - - - D
1837                 //
1838                 // B and D were selected, then B was deselected and C was selected in one go.
1839                 if (!isDescendantOf(existingRootRanges, topLeft)) {
1840                     // B is topLeft and fullSelection contains D.
1841                     // B is not a descendant of D.
1842 
1843                     // range is not a descendant of the selection, but maybe the selection is a descendant of range.
1844                     // no need to check selected here. That's already in newRootRanges.
1845                     // existingRootRanges and newRootRanges do not overlap.
1846                     for (const QItemSelectionRange &selectedRange : existingRootRanges) {
1847                         const QModelIndex selectedRangeTopLeft = selectedRange.topLeft();
1848                         // existingSelection (and selectedRangeTopLeft) is D.
1849                         // D is a descendant of B, so when B was removed, D might have been exposed as a root.
1850                         if (isDescendantOf(range, selectedRangeTopLeft)
1851                             // But D is also a descendant of part of the new selection C, which is already set to be a new root
1852                             // so D would not be added to exposedSelection because C is in newRootRanges.
1853                             && !isDescendantOf(newRootRanges, selectedRangeTopLeft)) {
1854                             exposedSelection.append(selectedRange);
1855                         }
1856                     }
1857                     removedRootRanges << range;
1858                 }
1859             }
1860         }
1861 
1862         QItemSelection obscuredRanges;
1863         {
1864             QListIterator<QItemSelectionRange> i(existingRootRanges);
1865             while (i.hasNext()) {
1866                 const QItemSelectionRange range = i.next();
1867                 if (isDescendantOf(newRootRanges, range.topLeft())) {
1868                     obscuredRanges << range;
1869                 }
1870             }
1871         }
1872         removedRootRanges << getRootRanges(obscuredRanges);
1873         newRootRanges << getRootRanges(exposedSelection);
1874 
1875         removedRootRanges = kNormalizeSelection(removedRootRanges);
1876         newRootRanges = kNormalizeSelection(newRootRanges);
1877     } else {
1878         removedRootRanges = deselected;
1879         newRootRanges = selected;
1880     }
1881 
1882     removeSelectionFromProxy(removedRootRanges);
1883 
1884     if (!m_selectionModel->hasSelection()) {
1885         Q_ASSERT(m_rootIndexList.isEmpty());
1886         Q_ASSERT(m_mappedFirstChildren.isEmpty());
1887         Q_ASSERT(m_mappedParents.isEmpty());
1888         Q_ASSERT(m_parentIds.isEmpty());
1889     }
1890 
1891     insertSelectionIntoProxy(newRootRanges);
1892 }
1893 
1894 int KSelectionProxyModelPrivate::getTargetRow(int rootListRow)
1895 {
1896     Q_Q(KSelectionProxyModel);
1897     if (!m_startWithChildTrees) {
1898         return rootListRow;
1899     }
1900 
1901     --rootListRow;
1902     while (rootListRow >= 0) {
1903         const QModelIndex idx = m_rootIndexList.at(rootListRow);
1904         Q_ASSERT(idx.isValid());
1905         const int rowCount = q->sourceModel()->rowCount(idx);
1906         if (rowCount > 0) {
1907             static const int column = 0;
1908             const QModelIndex srcIdx = q->sourceModel()->index(rowCount - 1, column, idx);
1909             const QModelIndex proxyLastChild = mapFromSource(srcIdx);
1910             return proxyLastChild.row() + 1;
1911         }
1912         --rootListRow;
1913     }
1914     return 0;
1915 }
1916 
1917 void KSelectionProxyModelPrivate::insertSelectionIntoProxy(const QItemSelection &selection)
1918 {
1919     Q_Q(KSelectionProxyModel);
1920 
1921     if (selection.isEmpty()) {
1922         return;
1923     }
1924 
1925     const auto lst = selection.indexes();
1926     for (const QModelIndex &newIndex : lst) {
1927         Q_ASSERT(newIndex.model() == q->sourceModel());
1928         if (newIndex.column() > 0) {
1929             continue;
1930         }
1931         if (m_startWithChildTrees) {
1932             const int rootListRow = getRootListRow(m_rootIndexList, newIndex);
1933             Q_ASSERT(q->sourceModel() == newIndex.model());
1934             const int rowCount = q->sourceModel()->rowCount(newIndex);
1935             const int startRow = getTargetRow(rootListRow);
1936 
1937             if (rowCount == 0) {
1938                 // Even if the newindex doesn't have any children to put into the model yet,
1939                 // We still need to make sure its future children are inserted into the model.
1940                 m_rootIndexList.insert(rootListRow, newIndex);
1941                 if (!m_resetting || m_layoutChanging) {
1942                     Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1943                 }
1944                 continue;
1945             }
1946             if (!m_resetting) {
1947                 q->beginInsertRows(QModelIndex(), startRow, startRow + rowCount - 1);
1948             }
1949             Q_ASSERT(newIndex.isValid());
1950             m_rootIndexList.insert(rootListRow, newIndex);
1951             if (!m_resetting || m_layoutChanging) {
1952                 Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1953             }
1954 
1955             int _start = 0;
1956             for (int i = 0; i < rootListRow; ++i) {
1957                 _start += q->sourceModel()->rowCount(m_rootIndexList.at(i));
1958             }
1959 
1960             updateInternalTopIndexes(_start, rowCount);
1961             createFirstChildMapping(newIndex, _start);
1962             createParentMappings(newIndex, 0, rowCount - 1);
1963 
1964             if (!m_resetting) {
1965                 q->endInsertRows();
1966             }
1967 
1968         } else {
1969             const int row = getRootListRow(m_rootIndexList, newIndex);
1970             if (!m_resetting) {
1971                 q->beginInsertRows(QModelIndex(), row, row);
1972             }
1973 
1974             Q_ASSERT(newIndex.isValid());
1975             m_rootIndexList.insert(row, newIndex);
1976 
1977             if (!m_resetting || m_layoutChanging) {
1978                 Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1979             }
1980             Q_ASSERT(m_rootIndexList.size() > row);
1981             updateInternalIndexes(QModelIndex(), row, 1);
1982             createParentMappings(newIndex.parent(), newIndex.row(), newIndex.row());
1983 
1984             if (!m_resetting) {
1985                 q->endInsertRows();
1986             }
1987         }
1988     }
1989     Q_EMIT q->rootSelectionAdded(selection, KSelectionProxyModel::QPrivateSignal());
1990 }
1991 
1992 KSelectionProxyModel::KSelectionProxyModel(QItemSelectionModel *selectionModel, QObject *parent)
1993     : QAbstractProxyModel(parent)
1994     , d_ptr(new KSelectionProxyModelPrivate(this))
1995 {
1996     setSelectionModel(selectionModel);
1997 }
1998 
1999 KSelectionProxyModel::KSelectionProxyModel()
2000     : QAbstractProxyModel(nullptr)
2001     , d_ptr(new KSelectionProxyModelPrivate(this))
2002 {
2003 }
2004 
2005 KSelectionProxyModel::~KSelectionProxyModel() = default;
2006 
2007 void KSelectionProxyModel::setFilterBehavior(FilterBehavior behavior)
2008 {
2009     Q_D(KSelectionProxyModel);
2010 
2011     Q_ASSERT(behavior != InvalidBehavior);
2012     if (behavior == InvalidBehavior) {
2013         return;
2014     }
2015     if (d->m_filterBehavior != behavior) {
2016         beginResetModel();
2017 
2018         d->m_filterBehavior = behavior;
2019 
2020         switch (behavior) {
2021         case InvalidBehavior: {
2022             Q_ASSERT(!"InvalidBehavior can't be used here");
2023             return;
2024         }
2025         case SubTrees: {
2026             d->m_omitChildren = false;
2027             d->m_omitDescendants = false;
2028             d->m_startWithChildTrees = false;
2029             d->m_includeAllSelected = false;
2030             break;
2031         }
2032         case SubTreeRoots: {
2033             d->m_omitChildren = true;
2034             d->m_startWithChildTrees = false;
2035             d->m_includeAllSelected = false;
2036             break;
2037         }
2038         case SubTreesWithoutRoots: {
2039             d->m_omitChildren = false;
2040             d->m_omitDescendants = false;
2041             d->m_startWithChildTrees = true;
2042             d->m_includeAllSelected = false;
2043             break;
2044         }
2045         case ExactSelection: {
2046             d->m_omitChildren = true;
2047             d->m_startWithChildTrees = false;
2048             d->m_includeAllSelected = true;
2049             break;
2050         }
2051         case ChildrenOfExactSelection: {
2052             d->m_omitChildren = false;
2053             d->m_omitDescendants = true;
2054             d->m_startWithChildTrees = true;
2055             d->m_includeAllSelected = true;
2056             break;
2057         }
2058         }
2059         Q_EMIT filterBehaviorChanged(QPrivateSignal());
2060         d->resetInternalData();
2061         if (d->m_selectionModel) {
2062             d->selectionChanged(d->m_selectionModel->selection(), QItemSelection());
2063         }
2064 
2065         endResetModel();
2066     }
2067 }
2068 
2069 KSelectionProxyModel::FilterBehavior KSelectionProxyModel::filterBehavior() const
2070 {
2071     Q_D(const KSelectionProxyModel);
2072     return d->m_filterBehavior;
2073 }
2074 
2075 void KSelectionProxyModel::setSourceModel(QAbstractItemModel *_sourceModel)
2076 {
2077     Q_D(KSelectionProxyModel);
2078 
2079     Q_ASSERT(_sourceModel != this);
2080 
2081     if (_sourceModel == sourceModel()) {
2082         return;
2083     }
2084 
2085     beginResetModel();
2086     d->m_resetting = true;
2087 
2088     if (auto *oldSourceModel = sourceModel()) {
2089         disconnect(oldSourceModel, nullptr, this, nullptr);
2090     }
2091 
2092     // Must be called before QAbstractProxyModel::setSourceModel because it emit some signals.
2093     d->resetInternalData();
2094     QAbstractProxyModel::setSourceModel(_sourceModel);
2095     if (_sourceModel) {
2096         if (d->m_selectionModel) {
2097             delete d->m_indexMapper;
2098             d->m_indexMapper = new KModelIndexProxyMapper(_sourceModel, d->m_selectionModel->model(), this);
2099             if (d->m_selectionModel->hasSelection()) {
2100                 d->selectionChanged(d->m_selectionModel->selection(), QItemSelection());
2101             }
2102         }
2103 
2104         connect(_sourceModel, &QAbstractItemModel::rowsAboutToBeInserted, this, [d](const QModelIndex &parent, int start, int end) {
2105             d->sourceRowsAboutToBeInserted(parent, start, end);
2106         });
2107 
2108         connect(_sourceModel, &QAbstractItemModel::rowsInserted, this, [d](const QModelIndex &parent, int start, int end) {
2109             d->sourceRowsInserted(parent, start, end);
2110         });
2111 
2112         connect(_sourceModel, &QAbstractItemModel::rowsAboutToBeRemoved, this, [d](const QModelIndex &parent, int start, int end) {
2113             d->sourceRowsAboutToBeRemoved(parent, start, end);
2114         });
2115 
2116         connect(_sourceModel, &QAbstractItemModel::rowsRemoved, this, [d](const QModelIndex &parent, int start, int end) {
2117             d->sourceRowsRemoved(parent, start, end);
2118         });
2119 
2120         connect(_sourceModel,
2121                 &QAbstractItemModel::rowsAboutToBeMoved,
2122                 this,
2123                 [d](const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow) {
2124                     d->sourceRowsAboutToBeMoved(parent, start, end, destParent, destRow);
2125                 });
2126 
2127         connect(_sourceModel,
2128                 &QAbstractItemModel::rowsMoved,
2129                 this,
2130                 [d](const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow) {
2131                     d->sourceRowsMoved(parent, start, end, destParent, destRow);
2132                 });
2133 
2134         connect(_sourceModel, &QAbstractItemModel::modelAboutToBeReset, this, [d]() {
2135             d->sourceModelAboutToBeReset();
2136         });
2137 
2138         connect(_sourceModel, &QAbstractItemModel::modelReset, this, [d]() {
2139             d->sourceModelReset();
2140         });
2141 
2142         connect(_sourceModel, &QAbstractItemModel::dataChanged, this, [d](const QModelIndex &topLeft, const QModelIndex &bottomRight) {
2143             d->sourceDataChanged(topLeft, bottomRight);
2144         });
2145 
2146         connect(_sourceModel, &QAbstractItemModel::layoutAboutToBeChanged, this, [d]() {
2147             d->sourceLayoutAboutToBeChanged();
2148         });
2149 
2150         connect(_sourceModel, &QAbstractItemModel::layoutChanged, this, [d]() {
2151             d->sourceLayoutChanged();
2152         });
2153 
2154         connect(_sourceModel, &QObject::destroyed, this, [d]() {
2155             d->sourceModelDestroyed();
2156         });
2157     }
2158 
2159     d->m_resetting = false;
2160     endResetModel();
2161 }
2162 
2163 QModelIndex KSelectionProxyModel::mapToSource(const QModelIndex &proxyIndex) const
2164 {
2165     Q_D(const KSelectionProxyModel);
2166 
2167     if (!proxyIndex.isValid() || !sourceModel() || d->m_rootIndexList.isEmpty()) {
2168         return QModelIndex();
2169     }
2170 
2171     Q_ASSERT(proxyIndex.model() == this);
2172 
2173     if (proxyIndex.internalPointer() == nullptr) {
2174         return d->mapTopLevelToSource(proxyIndex.row(), proxyIndex.column());
2175     }
2176 
2177     const QModelIndex proxyParent = d->parentForId(proxyIndex.internalPointer());
2178     Q_ASSERT(proxyParent.isValid());
2179     const QModelIndex sourceParent = d->mapParentToSource(proxyParent);
2180     Q_ASSERT(sourceParent.isValid());
2181     return sourceModel()->index(proxyIndex.row(), proxyIndex.column(), sourceParent);
2182 }
2183 
2184 QModelIndex KSelectionProxyModel::mapFromSource(const QModelIndex &sourceIndex) const
2185 {
2186     Q_D(const KSelectionProxyModel);
2187 
2188     if (!sourceModel() || !sourceIndex.isValid() || d->m_rootIndexList.isEmpty()) {
2189         return QModelIndex();
2190     }
2191 
2192     Q_ASSERT(sourceIndex.model() == sourceModel());
2193 
2194     if (!sourceIndex.isValid()) {
2195         return QModelIndex();
2196     }
2197 
2198     if (!d->ensureMappable(sourceIndex)) {
2199         return QModelIndex();
2200     }
2201 
2202     return d->mapFromSource(sourceIndex);
2203 }
2204 
2205 int KSelectionProxyModel::rowCount(const QModelIndex &index) const
2206 {
2207     Q_D(const KSelectionProxyModel);
2208 
2209     if (!sourceModel() || index.column() > 0 || d->m_rootIndexList.isEmpty()) {
2210         return 0;
2211     }
2212 
2213     Q_ASSERT(index.isValid() ? index.model() == this : true);
2214     if (!index.isValid()) {
2215         return d->topLevelRowCount();
2216     }
2217 
2218     // index is valid
2219     if (d->isFlat()) {
2220         return 0;
2221     }
2222 
2223     QModelIndex sourceParent = d->mapParentToSource(index);
2224 
2225     if (!sourceParent.isValid() && sourceModel()->hasChildren(sourceParent)) {
2226         sourceParent = mapToSource(index.parent());
2227         d->createParentMappings(sourceParent, 0, sourceModel()->rowCount(sourceParent) - 1);
2228         sourceParent = d->mapParentToSource(index);
2229     }
2230 
2231     if (!sourceParent.isValid()) {
2232         return 0;
2233     }
2234 
2235     return sourceModel()->rowCount(sourceParent);
2236 }
2237 
2238 QModelIndex KSelectionProxyModel::index(int row, int column, const QModelIndex &parent) const
2239 {
2240     Q_D(const KSelectionProxyModel);
2241 
2242     if (!sourceModel() || d->m_rootIndexList.isEmpty() || !hasIndex(row, column, parent)) {
2243         return QModelIndex();
2244     }
2245 
2246     Q_ASSERT(parent.isValid() ? parent.model() == this : true);
2247 
2248     if (!parent.isValid()) {
2249         return d->createTopLevelIndex(row, column);
2250     }
2251 
2252     void *const parentId = d->parentId(parent);
2253     Q_ASSERT(parentId);
2254     return createIndex(row, column, parentId);
2255 }
2256 
2257 QModelIndex KSelectionProxyModel::parent(const QModelIndex &index) const
2258 {
2259     Q_D(const KSelectionProxyModel);
2260 
2261     if (!sourceModel() || !index.isValid() || d->m_rootIndexList.isEmpty()) {
2262         return QModelIndex();
2263     }
2264 
2265     Q_ASSERT(index.model() == this);
2266 
2267     return d->parentForId(index.internalPointer());
2268 }
2269 
2270 Qt::ItemFlags KSelectionProxyModel::flags(const QModelIndex &index) const
2271 {
2272     if (!index.isValid() || !sourceModel()) {
2273         return QAbstractProxyModel::flags(index);
2274     }
2275 
2276     Q_ASSERT(index.model() == this);
2277 
2278     const QModelIndex srcIndex = mapToSource(index);
2279     Q_ASSERT(srcIndex.isValid());
2280     return sourceModel()->flags(srcIndex);
2281 }
2282 
2283 QVariant KSelectionProxyModel::data(const QModelIndex &index, int role) const
2284 {
2285     if (!sourceModel()) {
2286         return QVariant();
2287     }
2288 
2289     if (index.isValid()) {
2290         Q_ASSERT(index.model() == this);
2291         const QModelIndex idx = mapToSource(index);
2292         return idx.data(role);
2293     }
2294     return sourceModel()->data(index, role);
2295 }
2296 
2297 QVariant KSelectionProxyModel::headerData(int section, Qt::Orientation orientation, int role) const
2298 {
2299     if (!sourceModel()) {
2300         return QVariant();
2301     }
2302     return sourceModel()->headerData(section, orientation, role);
2303 }
2304 
2305 QMimeData *KSelectionProxyModel::mimeData(const QModelIndexList &indexes) const
2306 {
2307     if (!sourceModel()) {
2308         return QAbstractProxyModel::mimeData(indexes);
2309     }
2310     QModelIndexList sourceIndexes;
2311     for (const QModelIndex &index : indexes) {
2312         sourceIndexes << mapToSource(index);
2313     }
2314     return sourceModel()->mimeData(sourceIndexes);
2315 }
2316 
2317 QStringList KSelectionProxyModel::mimeTypes() const
2318 {
2319     if (!sourceModel()) {
2320         return QAbstractProxyModel::mimeTypes();
2321     }
2322     return sourceModel()->mimeTypes();
2323 }
2324 
2325 Qt::DropActions KSelectionProxyModel::supportedDropActions() const
2326 {
2327     if (!sourceModel()) {
2328         return QAbstractProxyModel::supportedDropActions();
2329     }
2330     return sourceModel()->supportedDropActions();
2331 }
2332 
2333 bool KSelectionProxyModel::hasChildren(const QModelIndex &parent) const
2334 {
2335     Q_D(const KSelectionProxyModel);
2336 
2337     if (d->m_rootIndexList.isEmpty() || !sourceModel()) {
2338         return false;
2339     }
2340 
2341     if (parent.isValid()) {
2342         Q_ASSERT(parent.model() == this);
2343         if (d->isFlat()) {
2344             return false;
2345         }
2346         return sourceModel()->hasChildren(mapToSource(parent));
2347     }
2348 
2349     if (!d->m_startWithChildTrees) {
2350         return true;
2351     }
2352 
2353     return !d->m_mappedFirstChildren.isEmpty();
2354 }
2355 
2356 int KSelectionProxyModel::columnCount(const QModelIndex &index) const
2357 {
2358     if (!sourceModel() || index.column() > 0) {
2359         return 0;
2360     }
2361 
2362     return sourceModel()->columnCount(mapToSource(index));
2363 }
2364 
2365 QItemSelectionModel *KSelectionProxyModel::selectionModel() const
2366 {
2367     Q_D(const KSelectionProxyModel);
2368     return d->m_selectionModel;
2369 }
2370 
2371 void KSelectionProxyModel::setSelectionModel(QItemSelectionModel *itemSelectionModel)
2372 {
2373     Q_D(KSelectionProxyModel);
2374     if (d->m_selectionModel != itemSelectionModel) {
2375         if (d->m_selectionModel) {
2376             disconnect(d->m_selectionModel,
2377                        SIGNAL(selectionChanged(QItemSelection, QItemSelection)),
2378                        this,
2379                        SLOT(selectionChanged(QItemSelection, QItemSelection)));
2380         }
2381 
2382         d->m_selectionModel = itemSelectionModel;
2383         Q_EMIT selectionModelChanged(QPrivateSignal());
2384 
2385         if (d->m_selectionModel) {
2386             connect(d->m_selectionModel, SIGNAL(selectionChanged(QItemSelection, QItemSelection)), SLOT(selectionChanged(QItemSelection, QItemSelection)));
2387 
2388             auto handleSelectionModelModel = [&, d] {
2389                 beginResetModel();
2390                 if (d->selectionModelModelAboutToBeResetConnection) {
2391                     disconnect(d->selectionModelModelAboutToBeResetConnection);
2392                 }
2393                 if (d->selectionModelModelResetConnection) {
2394                     disconnect(d->selectionModelModelResetConnection);
2395                 }
2396                 if (d->m_selectionModel->model()) {
2397                     d->selectionModelModelAboutToBeResetConnection =
2398                         connect(d->m_selectionModel->model(), SIGNAL(modelAboutToBeReset()), this, SLOT(sourceModelAboutToBeReset()));
2399                     d->selectionModelModelResetConnection = connect(d->m_selectionModel->model(), SIGNAL(modelReset()), this, SLOT(sourceModelReset()));
2400                     d->m_rootIndexList.clear();
2401                     delete d->m_indexMapper;
2402                     d->m_indexMapper = new KModelIndexProxyMapper(sourceModel(), d->m_selectionModel->model(), this);
2403                 }
2404                 endResetModel();
2405             };
2406             connect(d->m_selectionModel.data(), &QItemSelectionModel::modelChanged, this, handleSelectionModelModel);
2407             handleSelectionModelModel();
2408         }
2409 
2410         if (sourceModel()) {
2411             delete d->m_indexMapper;
2412             d->m_indexMapper = new KModelIndexProxyMapper(sourceModel(), d->m_selectionModel->model(), this);
2413             if (d->m_selectionModel->hasSelection()) {
2414                 d->selectionChanged(d->m_selectionModel->selection(), QItemSelection());
2415             }
2416         }
2417     }
2418 }
2419 
2420 bool KSelectionProxyModel::dropMimeData(const QMimeData *data, Qt::DropAction action, int row, int column, const QModelIndex &parent)
2421 {
2422     Q_D(const KSelectionProxyModel);
2423     if (!sourceModel() || d->m_rootIndexList.isEmpty()) {
2424         return false;
2425     }
2426 
2427     if ((row == -1) && (column == -1)) {
2428         return sourceModel()->dropMimeData(data, action, -1, -1, mapToSource(parent));
2429     }
2430 
2431     int source_destination_row = -1;
2432     int source_destination_column = -1;
2433     QModelIndex source_parent;
2434 
2435     if (row == rowCount(parent)) {
2436         source_parent = mapToSource(parent);
2437         source_destination_row = sourceModel()->rowCount(source_parent);
2438     } else {
2439         const QModelIndex proxy_index = index(row, column, parent);
2440         const QModelIndex source_index = mapToSource(proxy_index);
2441         source_destination_row = source_index.row();
2442         source_destination_column = source_index.column();
2443         source_parent = source_index.parent();
2444     }
2445     return sourceModel()->dropMimeData(data, action, source_destination_row, source_destination_column, source_parent);
2446 }
2447 
2448 QList<QPersistentModelIndex> KSelectionProxyModel::sourceRootIndexes() const
2449 {
2450     Q_D(const KSelectionProxyModel);
2451     return d->m_rootIndexList;
2452 }
2453 
2454 QModelIndexList KSelectionProxyModel::match(const QModelIndex &start, int role, const QVariant &value, int hits, Qt::MatchFlags flags) const
2455 {
2456     if (role < Qt::UserRole) {
2457         return QAbstractProxyModel::match(start, role, value, hits, flags);
2458     }
2459 
2460     QModelIndexList list;
2461     QModelIndex proxyIndex;
2462     const auto lst = sourceModel()->match(mapToSource(start), role, value, hits, flags);
2463     for (const QModelIndex &idx : lst) {
2464         proxyIndex = mapFromSource(idx);
2465         if (proxyIndex.isValid()) {
2466             list << proxyIndex;
2467         }
2468     }
2469     return list;
2470 }
2471 
2472 QItemSelection KSelectionProxyModel::mapSelectionFromSource(const QItemSelection &selection) const
2473 {
2474     Q_D(const KSelectionProxyModel);
2475     if (!d->m_startWithChildTrees && d->m_includeAllSelected) {
2476         // QAbstractProxyModel::mapSelectionFromSource puts invalid ranges in the result
2477         // without checking. We can't have that.
2478         QItemSelection proxySelection;
2479         for (const QItemSelectionRange &range : selection) {
2480             QModelIndex proxyTopLeft = mapFromSource(range.topLeft());
2481             if (!proxyTopLeft.isValid()) {
2482                 continue;
2483             }
2484             QModelIndex proxyBottomRight = mapFromSource(range.bottomRight());
2485             Q_ASSERT(proxyBottomRight.isValid());
2486             proxySelection.append(QItemSelectionRange(proxyTopLeft, proxyBottomRight));
2487         }
2488         return proxySelection;
2489     }
2490 
2491     QItemSelection proxySelection;
2492     QItemSelection::const_iterator it = selection.constBegin();
2493     const QItemSelection::const_iterator end = selection.constEnd();
2494     for (; it != end; ++it) {
2495         const QModelIndex proxyTopLeft = mapFromSource(it->topLeft());
2496         if (!proxyTopLeft.isValid()) {
2497             continue;
2498         }
2499 
2500         if (it->height() == 1 && it->width() == 1) {
2501             proxySelection.append(QItemSelectionRange(proxyTopLeft, proxyTopLeft));
2502         } else {
2503             proxySelection.append(QItemSelectionRange(proxyTopLeft, d->mapFromSource(it->bottomRight())));
2504         }
2505     }
2506     return proxySelection;
2507 }
2508 
2509 QItemSelection KSelectionProxyModel::mapSelectionToSource(const QItemSelection &selection) const
2510 {
2511     Q_D(const KSelectionProxyModel);
2512 
2513     if (selection.isEmpty()) {
2514         return selection;
2515     }
2516 
2517     if (!d->m_startWithChildTrees && d->m_includeAllSelected) {
2518         // QAbstractProxyModel::mapSelectionFromSource puts invalid ranges in the result
2519         // without checking. We can't have that.
2520         QItemSelection sourceSelection;
2521         for (const QItemSelectionRange &range : selection) {
2522             QModelIndex sourceTopLeft = mapToSource(range.topLeft());
2523             Q_ASSERT(sourceTopLeft.isValid());
2524 
2525             QModelIndex sourceBottomRight = mapToSource(range.bottomRight());
2526             Q_ASSERT(sourceBottomRight.isValid());
2527             sourceSelection.append(QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2528         }
2529         return sourceSelection;
2530     }
2531 
2532     QItemSelection sourceSelection;
2533     QItemSelection extraSelection;
2534     QItemSelection::const_iterator it = selection.constBegin();
2535     const QItemSelection::const_iterator end = selection.constEnd();
2536     for (; it != end; ++it) {
2537         const QModelIndex sourceTopLeft = mapToSource(it->topLeft());
2538         if (it->height() == 1 && it->width() == 1) {
2539             sourceSelection.append(QItemSelectionRange(sourceTopLeft, sourceTopLeft));
2540         } else if (it->parent().isValid()) {
2541             sourceSelection.append(QItemSelectionRange(sourceTopLeft, mapToSource(it->bottomRight())));
2542         } else {
2543             // A contiguous selection in the proxy might not be contiguous in the source if it
2544             // is at the top level of the proxy.
2545             if (d->m_startWithChildTrees) {
2546                 const QModelIndex sourceParent = mapFromSource(sourceTopLeft);
2547                 Q_ASSERT(sourceParent.isValid());
2548                 const int rowCount = sourceModel()->rowCount(sourceParent);
2549                 if (rowCount < it->bottom()) {
2550                     Q_ASSERT(sourceTopLeft.isValid());
2551                     Q_ASSERT(it->bottomRight().isValid());
2552                     const QModelIndex sourceBottomRight = mapToSource(it->bottomRight());
2553                     Q_ASSERT(sourceBottomRight.isValid());
2554                     sourceSelection.append(QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2555                     continue;
2556                 }
2557                 // Store the contiguous part...
2558                 const QModelIndex sourceBottomRight = sourceModel()->index(rowCount - 1, it->right(), sourceParent);
2559                 Q_ASSERT(sourceTopLeft.isValid());
2560                 Q_ASSERT(sourceBottomRight.isValid());
2561                 sourceSelection.append(QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2562                 // ... and the rest will be processed later.
2563                 extraSelection.append(QItemSelectionRange(createIndex(it->top() - rowCount, it->right()), it->bottomRight()));
2564             } else {
2565                 QItemSelection topSelection;
2566                 const QModelIndex idx = createIndex(it->top(), it->right());
2567                 const QModelIndex sourceIdx = mapToSource(idx);
2568                 Q_ASSERT(sourceIdx.isValid());
2569                 topSelection.append(QItemSelectionRange(sourceTopLeft, sourceIdx));
2570                 for (int i = it->top() + 1; i <= it->bottom(); ++i) {
2571                     const QModelIndex left = mapToSource(createIndex(i, 0));
2572                     const QModelIndex right = mapToSource(createIndex(i, it->right()));
2573                     Q_ASSERT(left.isValid());
2574                     Q_ASSERT(right.isValid());
2575                     topSelection.append(QItemSelectionRange(left, right));
2576                 }
2577                 sourceSelection += kNormalizeSelection(topSelection);
2578             }
2579         }
2580     }
2581     sourceSelection << mapSelectionToSource(extraSelection);
2582     return sourceSelection;
2583 }
2584 
2585 #include "moc_kselectionproxymodel.cpp"