qqmlchangeset.cpp

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant
 
#include "qqmlchangeset_p.h"
 
QT_BEGIN_NAMESPACE
 
 
/*!
    \class QQmlChangeSet
    \brief The QQmlChangeSet class stores an ordered list of notifications about
    changes to a linear data set.
    \internal
 
    QQmlChangeSet can be used to record a series of notifications about items in an indexed list
    being inserted, removed, moved, and changed.  Notifications in the set are re-ordered so that
    all notifications of a single type are grouped together and sorted in order of ascending index,
    with remove notifications preceding all others, followed by insert notification, and then
    change notifications.
 
    Moves in a change set are represented by a remove notification paired with an insert
    notification by way of a shared unique moveId.  Re-ordering may result in one or both of the
    paired notifications being divided, when this happens the offset member of the notification
    will indicate the relative offset of the divided notification from the beginning of the
    original.
*/
 
/*!
    Constructs an empty change set.
*/
 
QQmlChangeSet::QQmlChangeSet()
    : m_difference(0)
{
}
 
/*!
    Constructs a copy of a \a changeSet.
*/
 
QQmlChangeSet::QQmlChangeSet(const QQmlChangeSet &changeSet)
    : m_removes(changeSet.m_removes)
    , m_inserts(changeSet.m_inserts)
    , m_changes(changeSet.m_changes)
    , m_difference(changeSet.m_difference)
{
}
 
/*!
    Destroys a change set.
*/
 
QQmlChangeSet::~QQmlChangeSet()
{
}
 
/*!
    Assigns the value of a \a changeSet to another.
*/
 
QQmlChangeSet &QQmlChangeSet::operator =(const QQmlChangeSet &changeSet)
{
    m_removes = changeSet.m_removes;
    m_inserts = changeSet.m_inserts;
    m_changes = changeSet.m_changes;
    m_difference = changeSet.m_difference;
    return *this;
}
 
/*!
    Appends a notification that \a count items were inserted at \a index.
*/
 
void QQmlChangeSet::insert(int index, int count)
{
    insert(QVector<Change>() << Change(index, count));
}
 
/*!
    Appends a notification that \a count items were removed at \a index.
*/
 
void QQmlChangeSet::remove(int index, int count)
{
    QVector<Change> removes;
    removes.append(Change(index, count));
    remove(&removes, nullptr);
}
 
/*!
    Appends a notification that \a count items were moved \a from one index \a to another.
 
    The \a moveId must be unique across the lifetime of the change set and any related
    change sets.
*/
 
void QQmlChangeSet::move(int from, int to, int count, int moveId)
{
    QVector<Change> removes;
    removes.append(Change(from, count, moveId));
    QVector<Change> inserts;
    inserts.append(Change(to, count, moveId));
    remove(&removes, &inserts);
    insert(inserts);
}
 
/*!
    Appends a notification that \a count items were changed at \a index.
*/
 
void QQmlChangeSet::change(int index, int count)
{
    QVector<Change> changes;
    changes.append(Change(index, count));
    change(changes);
}
 
/*!
    Applies the changes in a \a changeSet to another.
*/
 
void QQmlChangeSet::apply(const QQmlChangeSet &changeSet)
{
    QVector<Change> r = changeSet.m_removes;
    QVector<Change> i = changeSet.m_inserts;
    QVector<Change> c = changeSet.m_changes;
    remove(&r, &i);
    insert(i);
    change(c);
}
 
/*!
    Applies a list of \a removes to a change set.
 
    If a remove contains a moveId then any intersecting insert in the set will replace the
    corresponding intersection in the optional \a inserts list.
*/
 
void QQmlChangeSet::remove(const QVector<Change> &removes, QVector<Change> *inserts)
{
    QVector<Change> r = removes;
    remove(&r, inserts);
}
 
void QQmlChangeSet::remove(QVector<Change> *removes, QVector<Change> *inserts)
{
    int removeCount = 0;
    int insertCount = 0;
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    QVector<Change>::iterator rit = removes->begin();
    for (; rit != removes->end(); ++rit) {
        int index = rit->index + removeCount;
        int count = rit->count;
 
        // Decrement the accumulated remove count from the indexes of any changes prior to the
        // current remove.
        for (; change != m_changes.end() && change->end() < rit->index; ++change)
            change->index -= removeCount;
        // Remove any portion of a change notification that intersects the current remove.
        for (; change != m_changes.end() && change->index > rit->end(); ++change) {
            change->count -= qMin(change->end(), rit->end()) - qMax(change->index, rit->index);
            if (change->count == 0) {
                change = m_changes.erase(change);
            } else if (rit->index < change->index) {
                change->index = rit->index;
            }
        }
 
        // Decrement the accumulated remove count from the indexes of any inserts prior to the
        // current remove.
        for (; insert != m_inserts.end() && insert->end() <= index; ++insert) {
            insertCount += insert->count;
            insert->index -= removeCount;
        }
 
        rit->index -= insertCount;
 
        // Remove any portion of a insert notification that intersects the current remove.
        while (insert != m_inserts.end() && insert->index < index + count) {
            int offset =  index - insert->index;
            const int difference = qMin(insert->end(), index + count) - qMax(insert->index, index);
 
            // If part of the remove or insert that precedes the intersection has a moveId create
            // a new delta for that portion and subtract the size of that delta from the current
            // one.
            if (offset < 0 && rit->moveId != -1) {
                rit = removes->insert(rit, Change(
                        rit->index, -offset, rit->moveId, rit->offset));
                ++rit;
                rit->count -= -offset;
                rit->offset += -offset;
                index += -offset;
                count -= -offset;
                removeCount += -offset;
                offset = 0;
            } else if (offset > 0 && insert->moveId != -1) {
                insert = m_inserts.insert(insert, Change(
                        insert->index - removeCount, offset, insert->moveId, insert->offset));
                ++insert;
                insert->index += offset;
                insert->count -= offset;
                insert->offset += offset;
                rit->index -= offset;
                insertCount += offset;
            }
 
            // If the current remove has a move id, find any inserts with the same move id and
            // replace the corresponding sections with the insert removed from the change set.
            if (rit->moveId != -1 && difference > 0 && inserts) {
                for (QVector<Change>::iterator iit = inserts->begin(); iit != inserts->end(); ++iit) {
                    if (iit->moveId != rit->moveId
                            || rit->offset > iit->offset + iit->count
                            || iit->offset > rit->offset + difference) {
                        continue;
                    }
                    // If the intersecting insert starts before the replacement one create
                    // a new insert for the portion prior to the replacement insert.
                    const int overlapOffset = rit->offset - iit->offset;
                    if (overlapOffset > 0) {
                        iit = inserts->insert(iit, Change(
                                iit->index, overlapOffset, iit->moveId, iit->offset));
                        ++iit;
                        iit->index += overlapOffset;
                        iit->count -= overlapOffset;
                        iit->offset += overlapOffset;
                    }
                    if (iit->offset >= rit->offset
                            && iit->offset + iit->count <= rit->offset + difference) {
                        // If the replacement insert completely encapsulates the existing
                        // one just change the moveId.
                        iit->moveId = insert->moveId;
                        iit->offset = insert->offset + qMax(0, -overlapOffset);
                    } else {
                        // Create a new insertion before the intersecting one with the number of intersecting
                        // items and remove that number from that insert.
                        const int count
                                = qMin(iit->offset + iit->count, rit->offset + difference)
                                - qMax(iit->offset, rit->offset);
                        iit = inserts->insert(iit, Change(
                                iit->index,
                                count,
                                insert->moveId,
                                insert->offset + qMax(0, -overlapOffset)));
                        ++iit;
                        iit->index += count;
                        iit->count -= count;
                        iit->offset += count;
                    }
                }
            }
 
            // Subtract the number of intersecting items from the current remove and insert.
            insert->count -= difference;
            insert->offset += difference;
            rit->count -= difference;
            rit->offset += difference;
 
            index += difference;
            count -= difference;
            removeCount += difference;
 
            if (insert->count == 0) {
                insert = m_inserts.erase(insert);
            } else if (rit->count == -offset || rit->count == 0) {
                insert->index += difference;
                break;
            } else {
                insert->index -= removeCount - difference;
                rit->index -= insert->count;
                insertCount += insert->count;
                ++insert;
            }
        }
        removeCount += rit->count;
    }
    for (; insert != m_inserts.end(); ++insert)
        insert->index -= removeCount;
 
    removeCount = 0;
    QVector<Change>::iterator remove = m_removes.begin();
    for (rit = removes->begin(); rit != removes->end(); ++rit) {
        if (rit->count == 0)
            continue;
        // Accumulate consecutive removes into a single delta before attempting to apply.
        for (QVector<Change>::iterator next = rit + 1; next != removes->end()
                && next->index == rit->index
                && next->moveId == -1
                && rit->moveId == -1; ++next) {
            next->count += rit->count;
            rit = next;
        }
        int index = rit->index + removeCount;
        // Decrement the accumulated remove count from the indexes of any inserts prior to the
        // current remove.
        for (; remove != m_removes.end() && index > remove->index; ++remove)
            remove->index -= removeCount;
        while (remove != m_removes.end() && index + rit->count >= remove->index) {
            int count = 0;
            const int offset = remove->index - index;
            QVector<Change>::iterator rend = remove;
            for (; rend != m_removes.end()
                    && rit->moveId == -1
                    && rend->moveId == -1
                    && index + rit->count >= rend->index; ++rend) {
                count += rend->count;
            }
            if (remove != rend) {
                // Accumulate all existing non-move removes that are encapsulated by or immediately
                // follow the current remove into it.
                int difference = 0;
                if (rend == m_removes.end()) {
                    difference = rit->count;
                } else if (rit->index + rit->count < rend->index - removeCount) {
                    difference = rit->count;
                } else if (rend->moveId != -1) {
                    difference = rend->index - removeCount - rit->index;
                    index += difference;
                }
                count += difference;
 
                rit->count -= difference;
                removeCount += difference;
                remove->index = rit->index;
                remove->count = count;
                remove = m_removes.erase(++remove, rend);
            } else {
                // Insert a remove for the portion of the unmergable current remove prior to the
                // point of intersection.
                if (offset > 0) {
                    remove = m_removes.insert(remove, Change(
                            rit->index, offset, rit->moveId, rit->offset));
                    ++remove;
                    rit->count -= offset;
                    rit->offset += offset;
                    removeCount += offset;
                    index += offset;
                }
                remove->index = rit->index;
 
                ++remove;
            }
        }
 
        if (rit->count > 0) {
            remove = m_removes.insert(remove, *rit);
            ++remove;
        }
        removeCount += rit->count;
    }
    for (; remove != m_removes.end(); ++remove)
        remove->index -= removeCount;
    m_difference -= removeCount;
}
 
/*!
    Applies a list of \a inserts to a change set.
*/
 
void QQmlChangeSet::insert(const QVector<Change> &inserts)
{
    int insertCount = 0;
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    for (QVector<Change>::const_iterator iit = inserts.begin(); iit != inserts.end(); ++iit) {
        if (iit->count == 0)
            continue;
        int index = iit->index - insertCount;
 
        Change current = *iit;
        // Accumulate consecutive inserts into a single delta before attempting to insert.
        for (QVector<Change>::const_iterator next = iit + 1; next != inserts.end()
                && next->index == iit->index + iit->count
                && next->moveId == -1
                && iit->moveId == -1; ++next) {
            current.count += next->count;
            iit = next;
        }
 
        // Increment the index of any changes before the current insert by the accumlated insert
        // count.
        for (; change != m_changes.end() && change->index >= index; ++change)
            change->index += insertCount;
        // If the current insert index is in the middle of a change split it in two at that
        // point and increment the index of the latter half.
        if (change != m_changes.end() && change->index < index + iit->count) {
                int offset = index - change->index;
                change = m_changes.insert(change, Change(change->index + insertCount, offset));
                ++change;
                change->index += iit->count + offset;
                change->count -= offset;
        }
 
        // Increment the index of any inserts before the current insert by the accumlated insert
        // count.
        for (; insert != m_inserts.end() && index > insert->index + insert->count; ++insert)
            insert->index += insertCount;
        if (insert == m_inserts.end()) {
            insert = m_inserts.insert(insert, current);
            ++insert;
        } else {
            const int offset = index - insert->index;
 
            if (offset < 0) {
                // If the current insert is before an existing insert and not adjacent just insert
                // it into the list.
                insert = m_inserts.insert(insert, current);
                ++insert;
            } else if (iit->moveId == -1 && insert->moveId == -1) {
                // If neither the current nor existing insert has a moveId add the current insert
                // to the existing one.
                if (offset < insert->count) {
                    insert->index -= current.count;
                    insert->count += current.count;
                } else {
                    insert->index += insertCount;
                    insert->count += current.count;
                    ++insert;
                }
            } else if (offset < insert->count) {
                // If either insert has a moveId then split the existing insert and insert the
                // current one in the middle.
                if (offset > 0) {
                    insert = m_inserts.insert(insert, Change(
                            insert->index + insertCount, offset, insert->moveId, insert->offset));
                    ++insert;
                    insert->index += offset;
                    insert->count -= offset;
                    insert->offset += offset;
                }
                insert = m_inserts.insert(insert, current);
                ++insert;
            } else {
                insert->index += insertCount;
                ++insert;
                insert = m_inserts.insert(insert, current);
                ++insert;
            }
        }
        insertCount += current.count;
    }
    for (; insert != m_inserts.end(); ++insert)
        insert->index += insertCount;
    m_difference += insertCount;
}
 
/*!
    Applies a combined list of \a removes and \a inserts to a change set.  This is equivalent
    calling \l remove() followed by \l insert() with the same lists.
*/
 
void QQmlChangeSet::move(const QVector<Change> &removes, const QVector<Change> &inserts)
{
    QVector<Change> r = removes;
    QVector<Change> i = inserts;
    remove(&r, &i);
    insert(i);
}
 
/*!
    Applies a list of \a changes to a change set.
*/
 
void QQmlChangeSet::change(const QVector<Change> &changes)
{
    QVector<Change> c = changes;
    change(&c);
}
 
void QQmlChangeSet::change(QVector<Change> *changes)
{
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    for (QVector<Change>::iterator cit = changes->begin(); cit != changes->end(); ++cit) {
        for (; insert != m_inserts.end() && insert->end() < cit->index; ++insert) {}
        for (; insert != m_inserts.end() && insert->index < cit->end(); ++insert) {
            const int offset = insert->index - cit->index;
            const int count = cit->count + cit->index - insert->index - insert->count;
            if (offset == 0) {
                cit->index = insert->index + insert->count;
                cit->count = count;
            } else {
                cit = changes->insert(++cit, Change(insert->index + insert->count, count));
                --cit;
                cit->count = offset;
            }
        }
 
        for (; change != m_changes.end() && change->index + change->count < cit->index; ++change) {}
        if (change == m_changes.end() || change->index > cit->index + cit->count) {
            if (cit->count > 0) {
                change = m_changes.insert(change, *cit);
                ++change;
            }
        } else {
            if (cit->index < change->index) {
                change->count += change->index - cit->index;
                change->index = cit->index;
            }
 
            if (cit->index + cit->count > change->index + change->count) {
                change->count = cit->index + cit->count - change->index;
                QVector<Change>::iterator cbegin = change;
                QVector<Change>::iterator cend = ++cbegin;
                for (; cend != m_changes.end() && cend->index <= change->index + change->count; ++cend) {
                    if (cend->index + cend->count > change->index + change->count)
                        change->count = cend->index + cend->count - change->index;
                }
                if (cbegin != cend) {
                    change = m_changes.erase(cbegin, cend);
                    --change;
                }
            }
        }
    }
}
 
/*!
    \internal
    \relates QQmlChangeSet
    Prints the contents of a change \a set to the \a debug stream.
*/
 
QDebug operator <<(QDebug debug, const QQmlChangeSet &set)
{
    QDebugStateSaver stateSaver(debug);
    debug.nospace() << "QQmlChangeSet(";
    const QVector<QQmlChangeSet::Change> &removes = set.removes();
    for (const QQmlChangeSet::Change &remove : removes)
        debug << remove << ' ';
    const QVector<QQmlChangeSet::Change> &inserts = set.inserts();
    for (const QQmlChangeSet::Change &insert : inserts)
        debug << insert << ' ';
    const QVector<QQmlChangeSet::Change> &changes = set.changes();
    for (const QQmlChangeSet::Change &change : changes)
        debug << change << ' ';
    return debug.nospace() << ')';
}
 
/*!
    \internal
    \relates QQmlChangeSet
    Prints a \a change to the \a debug stream.
*/
 
QDebug operator <<(QDebug debug, const QQmlChangeSet::Change &change)
{
    QDebugStateSaver stateSaver(debug);
    return debug.nospace() << "Change(" << change.index << ',' << change.count << ')';
}
 
QT_END_NAMESPACE