Remove ordered list assumptions in PathView

When flicking fast or jumping around on paths with some items not seen,
the current algorithm makes assumptions about list ordering which are
hard to maintain. Specifically that it has the index of the first item
in the list cached and that all changed will be to either prepend or
append an item to the current ordered set.

This patch removes that assumption, leading to a little more work each
time to identify where new elements will go. There is still a slightly
faster path for the common case of adding elements to the beginning or
end of the path.

Task-number: QTBUG-42716
Change-Id: Ief76c93967d254d405e6656ef27d06b4ecc470c8
Reviewed-by: Jørgen Lind <jorgen.lind@theqtcompany.com>
Reviewed-by: Shawn Rutledge <shawn.rutledge@digia.com>

4 files changed, 272 insertions, 48 deletions

diff --git a/src/quick/items/qquickpathview.cpp b/src/quick/items/qquickpathview.cpp
index 58605f79dd..302532c3d1 100644
--- a/src/quick/items/qquickpathview.cpp
+++ b/src/quick/items/qquickpathview.cpp
@@ -98,7 +98,7 @@ QQuickPathViewPrivate::QQuickPathViewPrivate()
     , inRefill(false)
     , dragMargin(0), deceleration(100), maximumFlickVelocity(QML_FLICK_DEFAULTMAXVELOCITY)
     , moveOffset(this, &QQuickPathViewPrivate::setAdjustedOffset), flickDuration(0)
-    , firstIndex(-1), pathItems(-1), requestedIndex(-1), cacheSize(0), requestedZ(0)
+    , pathItems(-1), requestedIndex(-1), cacheSize(0), requestedZ(0)
     , moveReason(Other), moveDirection(Shortest), attType(0), highlightComponent(0), highlightItem(0)
     , moveHighlight(this, &QQuickPathViewPrivate::setHighlightPosition)
     , highlightPosition(0)
@@ -447,7 +447,6 @@ void QQuickPathViewPrivate::regenerate()
     if (!isValid())
         return;
 
-    firstIndex = -1;
     updateMappedRange();
     q->refill();
 }
@@ -1473,7 +1472,7 @@ int QQuickPathView::indexAt(qreal x, qreal y) const
         QQuickItem *item = d->items.at(idx);
         QPointF p = item->mapFromItem(this, QPointF(x, y));
         if (item->contains(p))
-            return (d->firstIndex + idx) % d->modelCount;
+            return d->model->indexOf(item, 0);
     }
 
     return -1;
@@ -1896,12 +1895,12 @@ void QQuickPathView::refill()
     int count = d->pathItems == -1 ? d->modelCount : qMin(d->pathItems, d->modelCount);
 
     // first move existing items and remove items off path
-    int idx = d->firstIndex;
-    qCDebug(lcItemViewDelegateLifecycle) << "firstIndex" << idx << "currentIndex" << d->currentIndex << "offset" << d->offset;
+    qCDebug(lcItemViewDelegateLifecycle) << "currentIndex" << d->currentIndex << "offset" << d->offset;
     QList<QQuickItem*>::iterator it = d->items.begin();
     while (it != d->items.end()) {
-        qreal pos = d->positionOfIndex(idx);
         QQuickItem *item = *it;
+        int idx = d->model->indexOf(item, 0);
+        qreal pos = d->positionOfIndex(idx);
         if (lcItemViewDelegateLifecycle().isDebugEnabled()) {
             QQuickText *text = qmlobject_cast<QQuickText*>(item);
             if (text)
@@ -1923,81 +1922,140 @@ void QQuickPathView::refill()
             if (!d->isInBound(pos, d->mappedRange - d->mappedCache, 1.0 + d->mappedCache)) {
                 qCDebug(lcItemViewDelegateLifecycle) << "release" << idx << "@" << pos << ", !isInBound: lower" << (d->mappedRange - d->mappedCache) << "upper" << (1.0 + d->mappedCache);
                 d->releaseItem(item);
-                if (it == d->items.begin()) {
-                    if (++d->firstIndex >= d->modelCount) {
-                        d->firstIndex = 0;
-                    }
-                }
                 it = d->items.erase(it);
             } else {
                 ++it;
             }
         }
-        ++idx;
-        if (idx >= d->modelCount)
-            idx = 0;
     }
 
-    if (!d->items.count())
-        d->firstIndex = -1;
-
     bool waiting = false;
     if (d->modelCount) {
-        // add items to beginning and end
+        // add items as needed
         if (d->items.count() < count+d->cacheSize) {
-            int idx = qRound(d->modelCount - d->offset) % d->modelCount;
+            int endIdx = 0;
+            qreal endPos;
+            int startIdx = 0;
             qreal startPos = 0.0;
-            if (d->haveHighlightRange && (d->highlightRangeMode != QQuickPathView::NoHighlightRange
-                                          || d->snapMode != QQuickPathView::NoSnap))
-                startPos = d->highlightRangeStart;
-            if (d->firstIndex >= 0) {
-                startPos = d->positionOfIndex(d->firstIndex);
-                idx = (d->firstIndex + d->items.count()) % d->modelCount;
+            if (d->items.count()) {
+                //Find the beginning and end, items may not be in sorted order
+                endPos = -1.0;
+                startPos = 2.0;
+
+                for (int i = 0; i < d->items.count(); i++) {
+                    int idx = d->model->indexOf(d->items[i], 0);
+                    qreal curPos = d->positionOfIndex(idx);
+                    if (curPos > endPos) {
+                        endPos = curPos;
+                        endIdx = idx;
+                    }
+
+                    if (curPos < startPos) {
+                        startPos = curPos;
+                        startIdx = idx;
+                    }
+                }
+            } else {
+                if (d->haveHighlightRange
+                            && (d->highlightRangeMode != QQuickPathView::NoHighlightRange
+                                    || d->snapMode != QQuickPathView::NoSnap))
+                    startPos = d->highlightRangeStart;
+                // With no items, then "end" is just off the top so we populate via append
+                endIdx = (qRound(d->modelCount - d->offset) - 1) % d->modelCount;
+                endPos = d->positionOfIndex(endIdx);
             }
-            qreal pos = d->positionOfIndex(idx);
-            while ((d->isInBound(pos, startPos, 1.0 + d->mappedCache) || !d->items.count()) && d->items.count() < count+d->cacheSize) {
-                qCDebug(lcItemViewDelegateLifecycle)  << "append" << idx << "@" << pos << (d->currentIndex == idx ? "current" : "") << "items count was" << d->items.count();
-                QQuickItem *item = d->getItem(idx, idx+1, pos >= 1.0);
+            //Append
+            int idx = endIdx + 1;
+            if (idx >= d->modelCount)
+                idx = 0;
+            qreal nextPos = d->positionOfIndex(idx);
+            while ((d->isInBound(nextPos, endPos, 1.0 + d->mappedCache) || !d->items.count())
+                    && d->items.count() < count+d->cacheSize) {
+                qCDebug(lcItemViewDelegateLifecycle) << "append" << idx << "@" << nextPos << (d->currentIndex == idx ? "current" : "") << "items count was" << d->items.count();
+                QQuickItem *item = d->getItem(idx, idx+1, nextPos >= 1.0);
                 if (!item) {
                     waiting = true;
                     break;
                 }
+                if (d->items.contains(item)) {
+                    break; //Otherwise we'd "re-add" it, and get confused
+                }
                 if (d->currentIndex == idx) {
                     currentVisible = true;
-                    d->currentItemOffset = pos;
+                    d->currentItemOffset = nextPos;
                 }
-                if (d->items.count() == 0)
-                    d->firstIndex = idx;
                 d->items.append(item);
-                d->updateItem(item, pos);
+                d->updateItem(item, nextPos);
+                endIdx = idx;
+                endPos = nextPos;
                 ++idx;
                 if (idx >= d->modelCount)
                     idx = 0;
-                pos = d->positionOfIndex(idx);
+                nextPos = d->positionOfIndex(idx);
             }
 
-            idx = d->firstIndex - 1;
+            //Prepend
+            idx = startIdx - 1;
             if (idx < 0)
                 idx = d->modelCount - 1;
-            pos = d->positionOfIndex(idx);
-            while (!waiting && d->isInBound(pos, d->mappedRange - d->mappedCache, startPos) && d->items.count() < count+d->cacheSize) {
-                qCDebug(lcItemViewDelegateLifecycle)  << "prepend" << idx << "@" << pos << (d->currentIndex == idx ? "current" : "") << "items count was" << d->items.count();
-                QQuickItem *item = d->getItem(idx, idx+1, pos >= 1.0);
+            nextPos = d->positionOfIndex(idx);
+            while (!waiting && d->isInBound(nextPos, d->mappedRange - d->mappedCache, startPos)
+                    && d->items.count() < count+d->cacheSize) {
+                qCDebug(lcItemViewDelegateLifecycle) << "prepend" << idx << "@" << nextPos << (d->currentIndex == idx ? "current" : "") << "items count was" << d->items.count();
+                QQuickItem *item = d->getItem(idx, idx+1, nextPos >= 1.0);
                 if (!item) {
                     waiting = true;
                     break;
                 }
+                if (d->items.contains(item)) {
+                    break; //Otherwise we'd "re-add" it, and get confused
+                }
                 if (d->currentIndex == idx) {
                     currentVisible = true;
-                    d->currentItemOffset = pos;
+                    d->currentItemOffset = nextPos;
                 }
                 d->items.prepend(item);
-                d->updateItem(item, pos);
-                d->firstIndex = idx;
-                idx = d->firstIndex - 1;
+                d->updateItem(item, nextPos);
+                startIdx = idx;
+                startPos = nextPos;
+                --idx;
                 if (idx < 0)
                     idx = d->modelCount - 1;
-                pos = d->positionOfIndex(idx);
+                nextPos = d->positionOfIndex(idx);
+            }
+
+            // In rare cases, when jumping around with pathCount close to modelCount,
+            // new items appear in the middle. This more generic addition iteration handles this
+            // Since this is the rare case, we try append/prepend first and only do this if
+            // there are gaps still left to fill.
+            if (!waiting && d->items.count() < count+d->cacheSize) {
+                qCDebug(lcItemViewDelegateLifecycle) << "Checking for pathview middle inserts, items count was" << d->items.count();
+                idx = startIdx;
+                QQuickItem *lastItem = d->items[0];
+                while (idx != endIdx) {
+                    //This gets the reference from the delegate model, and will not re-create
+                    QQuickItem *item = d->getItem(idx, idx+1, nextPos >= 1.0);
+                    if (!item) {
+                        waiting = true;
+                        break;
+                    }
+                    if (!d->items.contains(item)) { //We found a hole
+                        nextPos = d->positionOfIndex(idx);
+                        qCDebug(lcItemViewDelegateLifecycle) << "middle insert" << idx << "@" << nextPos << (d->currentIndex == idx ? "current" : "") << "items count was" << d->items.count();
+                        if (d->currentIndex == idx) {
+                            currentVisible = true;
+                            d->currentItemOffset = nextPos;
+                        }
+                        int lastListIdx = d->items.indexOf(lastItem);
+                        d->items.insert(lastListIdx + 1, item);
+                        d->updateItem(item, nextPos);
+                    }
+
+                    lastItem = item;
+                    ++idx;
+                    if (idx >= d->modelCount)
+                        idx = 0;
+                }
             }
         }
     }
@@ -2128,7 +2186,6 @@ void QQuickPathView::modelUpdated(const QQmlChangeSet &changeSet, bool reset)
             d->offset = qmlMod(d->modelCount - d->currentIndex, d->modelCount);
             changedOffset = true;
         }
-        d->firstIndex = -1;
         d->updateMappedRange();
         d->scheduleLayout();
     }
@@ -2185,8 +2242,16 @@ void QQuickPathViewPrivate::createCurrentItem()
 {
     if (requestedIndex != -1)
         return;
-    int itemIndex = (currentIndex - firstIndex + modelCount) % modelCount;
-    if (itemIndex < items.count()) {
+
+    bool inItems = false;
+    for (int i = 0; i < items.count(); i++) {
+        if (model->indexOf(items[i], 0) == currentIndex) {
+            inItems = true;
+            break;
+        }
+    }
+
+    if (inItems) {
         if ((currentItem = getItem(currentIndex, currentIndex))) {
             currentItem->setFocus(true);
             if (QQuickPathViewAttached *att = attached(currentItem))
diff --git a/src/quick/items/qquickpathview_p_p.h b/src/quick/items/qquickpathview_p_p.h
index 35ea8616a5..2a497881d4 100644
--- a/src/quick/items/qquickpathview_p_p.h
+++ b/src/quick/items/qquickpathview_p_p.h
@@ -155,7 +155,6 @@ public:
     QQuickTimeLine tl;
     QQuickTimeLineValueProxy<QQuickPathViewPrivate> moveOffset;
     int flickDuration;
-    int firstIndex;
     int pathItems;
     int requestedIndex;
     int cacheSize;
diff --git a/tests/auto/quick/qquickpathview/data/qtbug42716.qml b/tests/auto/quick/qquickpathview/data/qtbug42716.qml
new file mode 100644
index 0000000000..81d52d5ea3
--- /dev/null
+++ b/tests/auto/quick/qquickpathview/data/qtbug42716.qml
@@ -0,0 +1,111 @@
+import QtQuick 2.0
+
+Rectangle {
+    //Note that this file was originally the manual reproduction, MouseAreas were left in.
+    id: qmlBrowser
+
+    width: 500
+    height: 350
+
+    ListModel {
+        id: myModel
+        ListElement {
+            name: "Bill Jones 0"
+        }
+        ListElement {
+            name: "Jane Doe 1"
+        }
+        ListElement {
+            name: "John Smith 2"
+        }
+        ListElement {
+            name: "Bill Jones 3"
+        }
+        ListElement {
+            name: "Jane Doe 4"
+        }
+        ListElement {
+            name: "John Smith 5"
+        }
+        ListElement {
+            name: "John Smith 6"
+        }
+        ListElement {
+            name: "John Smith 7"
+        }
+    }
+
+    Component {
+        id: delegate
+
+        Text {
+            id: nameText
+            height: 33
+            width: parent.width
+            objectName: "delegate"+index
+
+            text: "index: " + index + "   text: " + name
+            font.pointSize: 16
+            color: PathView.isCurrentItem ? "red" : "black"
+        }
+    }
+
+    PathView {
+        id: contentList
+        objectName: "pathView"
+        anchors.fill: parent
+
+        property int maxPathItemCount: 7
+        property real itemHeight: 34
+
+        delegate: delegate
+        model: myModel
+        currentIndex: 5
+        pathItemCount: maxPathItemCount
+        highlightMoveDuration: 0
+
+        path: Path {
+            startX: 30 + contentList.width / 2
+            startY: 30
+            PathLine {
+                relativeX: 0
+                relativeY: contentList.itemHeight * contentList.maxPathItemCount
+            }
+        }
+
+        focus: true
+        Keys.onLeftPressed: decrementCurrentIndex()
+        Keys.onRightPressed: incrementCurrentIndex()
+    }
+
+    Column {
+        anchors.right: parent.right
+        Text {
+            text: "Go 1"
+            font.weight: Font.Bold
+            font.pixelSize: 24
+            MouseArea {
+                anchors.fill: parent
+                onClicked:  contentList.offset = 2.55882
+            }
+        }
+        Text {
+            text: "Go 2"
+            font.weight: Font.Bold
+            font.pixelSize: 24
+            MouseArea {
+                anchors.fill: parent
+                onClicked:  contentList.offset = 0.0882353
+            }
+        }
+        Text {
+            text: "Go 3"
+            font.weight: Font.Bold
+            font.pixelSize: 24
+            MouseArea {
+                anchors.fill: parent
+                onClicked:  contentList.offset = 0.99987
+            }
+        }
+    }
+}
diff --git a/tests/auto/quick/qquickpathview/tst_qquickpathview.cpp b/tests/auto/quick/qquickpathview/tst_qquickpathview.cpp
index 7db15522b5..0910f6cb2e 100644
--- a/tests/auto/quick/qquickpathview/tst_qquickpathview.cpp
+++ b/tests/auto/quick/qquickpathview/tst_qquickpathview.cpp
@@ -140,6 +140,7 @@ private slots:
     void nestedinFlickable();
     void flickableDelegate();
     void jsArrayChange();
+    void qtbug42716();
 };
 
 class TestObject : public QObject
@@ -2322,6 +2323,54 @@ void tst_QQuickPathView::jsArrayChange()
     QCOMPARE(spy.count(), 1);
 }
 
+/* This bug was one where if you jump the list such that the sole missing item needed to be
+ * added in the middle of the list, it would instead move an item somewhere else in the list
+ * to the middle (messing it up very badly).
+ *
+ * The test checks correct visual order both before and after the jump.
+ */
+void tst_QQuickPathView::qtbug42716()
+{
+    QScopedPointer<QQuickView> window(createView());
+
+    window->setSource(testFileUrl("qtbug42716.qml"));
+    window->show();
+    QVERIFY(QTest::qWaitForWindowActive(window.data()));
+    QCOMPARE(window.data(), qGuiApp->focusWindow());
+
+    QQuickPathView *pathView = findItem<QQuickPathView>(window->rootObject(), "pathView");
+    QVERIFY(pathView != 0);
+
+    int order1[] = {5,6,7,0,1,2,3};
+    int missing1 = 4;
+    int order2[] = {0,1,2,3,4,5,6};
+    int missing2 = 7;
+
+    qreal lastY = 0.0;
+    for (int i = 0; i<7; i++) {
+        QQuickItem *item = findItem<QQuickItem>(pathView, QString("delegate%1").arg(order1[i]));
+        QVERIFY(item);
+        QVERIFY(item->y() > lastY);
+        lastY = item->y();
+    }
+    QQuickItem *itemMiss = findItem<QQuickItem>(pathView, QString("delegate%1").arg(missing1));
+    QVERIFY(!itemMiss);
+
+    pathView->setOffset(0.0882353);
+    //Note refill is delayed, needs time to take effect
+    QTest::qWait(100);
+
+    lastY = 0.0;
+    for (int i = 0; i<7; i++) {
+        QQuickItem *item = findItem<QQuickItem>(pathView, QString("delegate%1").arg(order2[i]));
+        QVERIFY(item);
+        QVERIFY(item->y() > lastY);
+        lastY = item->y();
+    }
+    itemMiss = findItem<QQuickItem>(pathView, QString("delegate%1").arg(missing2));
+    QVERIFY(!itemMiss);
+}
+
 QTEST_MAIN(tst_QQuickPathView)
 
 #include "tst_qquickpathview.moc"