//
// Copyright 2021 Signal Messenger, LLC
// SPDX-License-Identifier: AGPL-3.0-only
//
import SignalServiceKit
public protocol BatchUpdateValue: Equatable {
var batchUpdateId: String { get }
}
// MARK: -
public enum BatchUpdateType: Equatable {
case delete(oldIndex: Int)
case insert(newIndex: Int)
case move(oldIndex: Int, newIndex: Int)
case update(oldIndex: Int, newIndex: Int)
}
// MARK: -
extension BatchUpdateType {
var isDelete: Bool {
guard case .delete = self else {
return false
}
return true
}
var isInsert: Bool {
guard case .insert = self else {
return false
}
return true
}
var isMove: Bool {
guard case .move = self else {
return false
}
return true
}
var isUpdate: Bool {
guard case .update = self else {
return false
}
return true
}
fileprivate var oldRemovedIndex: Int? {
switch self {
case .delete(let oldIndex):
return oldIndex
case .insert:
return nil
case .move(let oldIndex, _):
return oldIndex
case .update:
return nil
}
}
fileprivate var newAddedIndex: Int? {
switch self {
case .delete:
return nil
case .insert(let newIndex):
return newIndex
case .move(_, let newIndex):
return newIndex
case .update:
return nil
}
}
}
// MARK: -
public class BatchUpdate<T: BatchUpdateValue> {
@available(*, unavailable, message: "Do not instantiate this class.")
private init() {}
public struct Item: Equatable {
public let value: T
public let updateType: BatchUpdateType
}
fileprivate typealias ValueId = String
public enum ViewType {
case uiCollectionView
case uiTableView
var doMovesUpdateCells: Bool {
switch self {
case .uiCollectionView:
return false
case .uiTableView:
return true
}
}
}
// Given the list of "old values", "new values" and "changed values",
// generate a series of "batch update items" that _safely_
// transforms the "old value list" into the "new value list"
// for UITableView or UICollectionView.
//
// Notes
//
// * We use "value" to refer to the Model/ViewModel for the content.
// In practice this is a CVRenderItem in conversation view and a
// threadUniqueId box in chat list.
// * We use "value id" to refer to a unique identifier for the model.
// In practice this is a model uniqueId.
// * We use "cell" to refer to the view item that renders the content.
// * We use "item" to refer to the batch update item, e.g. a .insert.
// * We use the terms .delete, .insert, .move and .update with a
// leading period to refer to an item type (e.g. BatchUpdateType).
// Some cells/values are .deleted but not removed from the view,
// etc. See below.
//
// Requirements
//
// * Ensure all cells whose content has changed are updated.
// * Handle differences between UITableView or UICollectionView.
// * Avoid crashes. UICollectionView is particularly prone to
// throwing exceptions (see below).
// * Detect mistakes and throw here, before the "batch updates
// items" are applied to the view, risking a crash.
// Callers will catch throw exceptions and reload entire view
// contents. This will be expensive and not have the correct
// animations, but it will be safe and the view state will end
// up in the correct state.
// * Avoid throwing/reloading (nice to have) for perf &
// animation reasons.
// * Enable logging (here and later when catching view
// exceptions) that will allow us to fix any issues and/or
// update the unit tests.
//
// Pitfalls:
//
// * Views will crash if items have invalid indices.
// * Views will crash if more than one item affects the same
// cell (e.g. .update a cell after .moving it, or insert
// two values at the same index, etc.).
// * Some item indices (like deletes) use "old indices",
// some item indices (like inserts) use "new indices",
// .move use an "old index" for the "from location" and a
// "new" index for the "to location".
// NOTE: .update items use old indices.
// * In UITableView, .moved cells are updated.
// In UICollectionView, .moved cells are not updated.
// Therefore if a value moves and changes in a
// UICollectionView, we need to "implement" move
// using two separate items, a .delete and an .insert.
// This ensures that content has the right ordering and
// views are updated as needed, but we lose the .move
// animation.
//
// Ordering of items matters conceptually but the views
// don't actually care about the order in which items are
// performed.
//
// See:
//
// * This WWDC is very useful:
// https://developer.apple.com/videos/play/wwdc2018/225/?time=2016
public static func build(
viewType: ViewType,
oldValues: [T],
newValues: [T],
changedValues: [T],
) throws -> [Item] {
func buildValueMap(values: [T]) throws -> [ValueId: T] {
var valueMap = [ValueId: T]()
for value in values {
let valueId = value.batchUpdateId
guard valueMap[valueId] == nil else {
throw OWSAssertionError("Could not build value map.")
}
valueMap[valueId] = value
}
return valueMap
}
let oldValueMap = try buildValueMap(values: oldValues)
let newValueMap = try buildValueMap(values: newValues)
guard
oldValueMap.count == oldValues.count,
newValueMap.count == newValues.count
else {
throw OWSAssertionError("Duplicate values.")
}
let oldValueIdList: [ValueId] = oldValues.map { $0.batchUpdateId }
let newValueIdList: [ValueId] = newValues.map { $0.batchUpdateId }
let oldValueIdSet = Set(oldValueIdList)
let newValueIdSet = Set(newValueIdList)
let changedValueIdSet = Set(changedValues.map { $0.batchUpdateId })
// The set of values in both "old" and "new" states.
let holdoverValueIdSet = oldValueIdSet.intersection(newValueIdSet)
// The output from this method is a list of items.
var batchUpdateItems = [Item]()
// We can simulate the outcome of the update for logging and to check correctness.
// We update the list of "value ids" by performing the items as UITableView and
// UICollectionView would. This simulation deals only in values ids, not values.
func simulateUpdate(items: [Item]) throws -> [ValueId] {
var updatedValueIdList = oldValueIdList
// UITableView and UICollection view don't care about the order
// in which the items are performed in a given performBatchUpdates()
// block, but they are applied to the view state in a very specific
// order to avoid index conflicts. Therefore to simulate UITableView
// and UICollection behavior we sort before performing.
//
// For the purposes of simulation, we treat .move as a separate .delete and
// .insert and ignore .update altogether.
// Perform all removing actions (.delete, .move).
var oldRemovedIndices = items.compactMap { item in
item.updateType.oldRemovedIndex
}
oldRemovedIndices.sort()
// Perform in descending order so that each remove doesn't
// affect indices of subsequent items.
for index in oldRemovedIndices.reversed() {
guard index >= 0, index < updatedValueIdList.count else {
throw OWSAssertionError("Invalid index: \(index)")
}
updatedValueIdList.remove(at: index)
}
// Perform all adding actions (.insert, .move).
var addItems = items.compactMap { item -> MockAddItem? in
guard let newIndex = item.updateType.newAddedIndex else {
return nil
}
return MockAddItem(newIndex: newIndex, valueId: item.value.batchUpdateId)
}
addItems.sort { left, right in
left.newIndex < right.newIndex
}
// Perform in ascending order so that each add doesn't
// affect indices of subsequent items.
for addItem in addItems {
guard addItem.newIndex >= 0, addItem.newIndex <= updatedValueIdList.count else {
throw OWSAssertionError("Invalid index: \(addItem.newIndex)")
}
updatedValueIdList.insert(addItem.valueId, at: addItem.newIndex)
}
return updatedValueIdList
}
// Identify values that we need to move. This is non-trival.
// See comment on findValueIdsToMove().
let valueIdsToMoveAll = try findValueIdsToMove(
oldValueIds: oldValueIdList,
newValueIds: newValueIdList,
holdoverValueIdSet: holdoverValueIdSet,
)
// In addition to deletions, insertions and updates, we need to
// support moves. Moves can be implemented as .delete + .insert
// items. We sometimes implement them that way (rather than as a
// single .move item) because in UICollectionView a .move _does
// not_ update the cell and the cell may have changed.
let valueIdsToMoveWithMove: Set<ValueId>
switch viewType {
case .uiCollectionView:
// UICollectionView .moves _do not_ update the cell.
//
// Therefore, if a UICollectionView value moves, we need to
// implement its move using an .insert/.delete pair. The animation
// isn't as attractive, but it properly updates the cell.
if Self.canUseMoveInCollectionView {
// Alternately, we could use .moves only for moves of unchanged items.
// But CVC moves should be incredibly rare, and always using .delete/.insert
// is safer.
valueIdsToMoveWithMove = valueIdsToMoveAll.subtracting(changedValueIdSet)
} else {
valueIdsToMoveWithMove = []
}
case .uiTableView:
// UITableView moves _do_ update the cell.
//
// Therefore, if a UICollectionView value moves, we can move it
// using a .move item.
valueIdsToMoveWithMove = valueIdsToMoveAll
}
let valueIdsToMoveWithDeleteInsert = valueIdsToMoveAll.subtracting(valueIdsToMoveWithMove)
// 1. Deletes
//
// We need to .delete any values from the old value ids that are not in
// the new value ids.
//
// We also need to .delete any values which are a move implemented with
// .delete/.insert.
var valueIdsToDelete = Set(oldValueIdList).subtracting(newValueIdSet)
valueIdsToDelete.formUnion(valueIdsToMoveWithDeleteInsert)
for valueId in valueIdsToDelete {
guard
oldValueIdSet.contains(valueId),
!newValueIdSet.contains(valueId) || valueIdsToMoveWithDeleteInsert.contains(valueId)
else {
throw OWSAssertionError("Invalid delete.")
}
// .delete items use the old index.
guard let oldIndex = oldValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
guard let value = oldValueMap[valueId] else {
throw OWSAssertionError("Can't find value.")
}
let item = Item(value: value, updateType: .delete(oldIndex: oldIndex))
batchUpdateItems.append(item)
}
// 2. Inserts
//
// We need to .insert any values from the new value ids that are not in
// the old value ids.
//
// We also need to .insert any values which are a "move" implemented with
// .delete/.insert.
let valueIdsAfterDeletes = oldValueIdSet.subtracting(valueIdsToDelete)
let valueIdsToInsert = Set(newValueIdSet).subtracting(valueIdsAfterDeletes)
for valueId in valueIdsToInsert {
guard
!oldValueIdSet.contains(valueId) || valueIdsToMoveWithDeleteInsert.contains(valueId),
newValueIdSet.contains(valueId)
else {
throw OWSAssertionError("Invalid insert.")
}
// .insert items use the new index.
guard let newIndex = newValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
guard let value = newValueMap[valueId] else {
throw OWSAssertionError("Can't find value.")
}
let item = Item(value: value, updateType: .insert(newIndex: newIndex))
batchUpdateItems.append(item)
}
// By now, the "transformed" list (which is the old list, updated with just
// the .delete and .insert items) and the new list should have the same content,
// but might not yet have the same ordering.
let valueIdValueAfterDeletesAndInserts = try simulateUpdate(items: batchUpdateItems)
guard Set(newValueIdList) == Set(valueIdValueAfterDeletesAndInserts) else {
throw OWSAssertionError("New and updated unordered contents don't match.")
}
// 3. Moves
//
// We need to .move all values which haven't already been moved with
// a .delete/.insert pair.
let valueIdsToMove = newValueIdList.filter { valueIdsToMoveWithMove.contains($0) }
guard
valueIdsToMove.count == valueIdsToMoveWithMove.count,
Set(valueIdsToMove) == valueIdsToMoveWithMove
else {
throw OWSAssertionError("Couldn't build list of value ids to move.")
}
for valueId in valueIdsToMove {
guard oldValueIdSet.contains(valueId), newValueIdSet.contains(valueId) else {
throw OWSAssertionError("Invalid move.")
}
// .move "from" indices use "old indices."
guard let oldIndex = oldValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
// .move "to" indices use "new indices."
guard let newIndex = newValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
// Take care to capture the new value.
guard let newValue = newValueMap[valueId] else {
throw OWSAssertionError("Can't find value.")
}
let item = Item(value: newValue, updateType: .move(oldIndex: oldIndex, newIndex: newIndex))
batchUpdateItems.append(item)
}
// By now, the "transformed" list (which is the old list, updated with just the
// .delete, .insert and .move items) and the new list should have the same content,
// in the same order.
let valueIdValueAfterDeletesInsertsAndMoves = try simulateUpdate(items: batchUpdateItems)
guard newValueIdList == valueIdValueAfterDeletesInsertsAndMoves else {
throw OWSAssertionError("New and updated ordered contents don't match.")
}
// 4. Updates
//
// We need to .update all values which changed and haven't already been updated
// by other items, e.g. a .move item or a .delete/.insert pair.
var valueIdsAlreadyUpdated = valueIdsToDelete.union(valueIdsToInsert)
switch viewType {
case .uiCollectionView:
// UICollectionView moves _do not_ update the cell.
break
case .uiTableView:
// UITableView moves _do_ update the cell.
valueIdsAlreadyUpdated.formUnion(valueIdsToMoveWithMove)
}
// We need to .update any "holdovers" that changed and have not already been updated.
let valueIdsToUpdate = holdoverValueIdSet.intersection(changedValueIdSet).subtracting(valueIdsAlreadyUpdated)
for valueId in valueIdsToUpdate {
// Take care to capture the new value.
guard let newValue = newValueMap[valueId] else {
throw OWSAssertionError("Can't find value.")
}
guard let oldIndex = oldValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
guard let newIndex = newValueIdList.firstIndex(of: valueId) else {
throw OWSAssertionError("Can't find index of value.")
}
let item = Item(value: newValue, updateType: .update(oldIndex: oldIndex, newIndex: newIndex))
batchUpdateItems.append(item)
}
let valueIdValueAfterAllItems = try simulateUpdate(items: batchUpdateItems)
guard newValueIdList == valueIdValueAfterAllItems else {
throw OWSAssertionError("New and updated ordered contents don't match.")
}
return batchUpdateItems
}
private struct MockAddItem {
let newIndex: Int
let valueId: ValueId
}
// It's important (and non-trivial) that we update the ordering
// of the values using the minimum number of moves possible.
//
// Consider the case of chat list displaying threads ABCDEF.
// Thread D receives a new message and moves to the top of
// chat list: D ABC EF. This can be accomplished many ways.
// We can .move D up or we can .move ABC down.
//
// In the case of more complex re-orderings, the number of
// possible solutions explodes.
//
// The solution that uses the minimum number of moves is most
// efficient, looks best, and is most likely to correspond to
// the "change" that re-ordered the values.
//
// In chat list and conversation view, most values ("the herd")
// don't move in a given set of batch updates. A few ("the
// wanderers") do.
//
// The algorithm for finding the most efficient set of moves
// is:
//
// * Identify "biggest wanderers" by recursing.
// * At each step, find the value ("the wanderer") that moved
// most between the old state and the new state.
// * Remove the value ("the wanderer") from the old and new
// state, and note that it moved.
// * Continue until old and new states have identical ordering.
// * Return the set of values that need to move ("the wanderers").
private static func findValueIdsToMove(
oldValueIds: [ValueId],
newValueIds: [ValueId],
holdoverValueIdSet: Set<String>,
) throws -> Set<ValueId> {
let oldHoldoverIds = oldValueIds.filter { holdoverValueIdSet.contains($0) }
let newHoldoverIds = newValueIds.filter { holdoverValueIdSet.contains($0) }
return try findValueIdsToMoveStep(
currentValueIds: oldHoldoverIds,
finalValueIds: newHoldoverIds,
)
}
private struct ValueDistance {
let valueId: ValueId
let distance: Int
}
private static func findValueIdsToMoveStep(
currentValueIds: [ValueId],
finalValueIds: [ValueId],
) throws -> Set<ValueId> {
guard currentValueIds != finalValueIds else {
// Values already have the correct order, stop recursing.
return Set()
}
var greatestValueDistance: ValueDistance?
for valueId in currentValueIds {
guard
let currentIndex = currentValueIds.firstIndex(of: valueId),
let finalIndex = finalValueIds.firstIndex(of: valueId)
else {
throw OWSAssertionError("Could not find value indices.")
}
let newDistance = ValueDistance(
valueId: valueId,
distance: abs(currentIndex - finalIndex),
)
if let otherDistance = greatestValueDistance {
if otherDistance.distance < newDistance.distance {
greatestValueDistance = newDistance
}
} else {
greatestValueDistance = newDistance
}
}
guard let valueDistance = greatestValueDistance else {
throw OWSAssertionError("Could not find value with greatest distance.")
}
var valueIdsToMove = Set([valueDistance.valueId])
let newCurrentValueIds = currentValueIds.filter { $0 != valueDistance.valueId }
let newFinalValueIds = finalValueIds.filter { $0 != valueDistance.valueId }
// It's important that we ensure that the "current" and "final" value id
// lists decrease in size with each pass or we may never converge and
// risk recursing forever.
guard
newCurrentValueIds.count < currentValueIds.count,
newFinalValueIds.count < finalValueIds.count,
Set(newCurrentValueIds) == Set(newFinalValueIds)
else {
throw OWSAssertionError("Could not remove value with greatest distance.")
}
valueIdsToMove.formUnion(try findValueIdsToMoveStep(
currentValueIds: newCurrentValueIds,
finalValueIds: newFinalValueIds,
))
return valueIdsToMove
}
public static var canUseMoveInCollectionView: Bool { false }
}
