OutlineViewDiffableDataSource.swift

//
//  OutlineViewDiffableDataSource.swift
//  OutlineDiffer
//
//  Created by Steve Sparks on 2/7/20.
//

import Cocoa

class OutlineViewDiffableDataSource: NSObject {
    private let dataSource: NSOutlineViewDataSource!
    private let outlineView: NSOutlineView!

    init(baseDataSource: NSOutlineViewDataSource, targetView: NSOutlineView) {
        self.dataSource = baseDataSource
        self.outlineView = targetView
        super.init()
        snapshot = Snapshot(from: dataSource, for: outlineView)
        targetView.dataSource = self
    }

    private var snapshot = Snapshot.empty {
        didSet {

        }
    }

    // Use when the model has changed and you want animation
    func applySnapshot() {
        guard Thread.current == Thread.main else {
            DispatchQueue.main.async { self.applySnapshot() }
            return
        }

        guard !isEmpty else {
            refreshSnapshot()
            outlineView.reloadData()
            return
        }

        let oldSnapshot = snapshot
        let newSnapshot = refreshSnapshot()
        outlineView.apply(oldSnapshot.instructions(forMorphingInto: newSnapshot))
    }

    @discardableResult
    func refreshSnapshot() -> Snapshot {
        snapshot = Snapshot(from: dataSource, for: outlineView)
        return snapshot
    }

    var isEmpty: Bool {
        return snapshot.isEmpty
    }
}


extension NSObject {
    func report(_ message: String = "", _ preamble: String = "", function: String = #function) {
        let fn = String(describing: type(of: self))
        print("--> \(preamble)\(fn) \(function) \(message) ")
    }
}
// Everything passes through.
extension OutlineViewDiffableDataSource: NSOutlineViewDataSource {

    func outlineView(_ outlineView: NSOutlineView, numberOfChildrenOfItem item: Any?) -> Int {
        guard let item = item as? AnyHashable? else {
            return 0
        }
        let ret = snapshot.numberOfChildren(ofItem: item)
        report(" item \(String(describing: item)) -> \(ret)")
        return ret
    }

    func outlineView(_ outlineView: NSOutlineView, child index: Int, ofItem item: Any?) -> Any {
        if item == nil { return snapshot.child(index, ofItem: nil) ?? "" }

        guard let item = item as? OutlineMemberItem? else {
            return ""
        }
        let ret = snapshot.child(index, ofItem: item)
        //        report(" child \(index) item \(String(describing: item)) -> \(String(describing: ret))")
        return ret ?? ""
    }

    func outlineView(_ outlineView: NSOutlineView, isItemExpandable item: Any) -> Bool {
        guard let item = item as? AnyHashable else {
            return false
        }
        let ret = snapshot.isItemExpandable(item)
        //        report(" item \(String(describing: item)) -> \(ret)")
        return ret
    }

    func outlineView(_ outlineView: NSOutlineView, persistentObjectForItem item: Any?) -> Any? {
        report()
        return dataSource.outlineView?(outlineView, persistentObjectForItem: item)
    }

    func outlineView(_ outlineView: NSOutlineView, itemForPersistentObject object: Any) -> Any? {
        report()
        return dataSource.outlineView?(outlineView, itemForPersistentObject: object)
    }

    func outlineView(_ outlineView: NSOutlineView, updateDraggingItemsForDrag draggingInfo: NSDraggingInfo) {
        report()
        dataSource.outlineView?(outlineView, updateDraggingItemsForDrag: draggingInfo)
    }

    func outlineView(_ outlineView: NSOutlineView, pasteboardWriterForItem item: Any) -> NSPasteboardWriting? {
        report()
        return dataSource.outlineView?(outlineView, pasteboardWriterForItem: item)
    }

    func outlineView(_ outlineView: NSOutlineView, sortDescriptorsDidChange oldDescriptors: [NSSortDescriptor]) {
        report()
        dataSource.outlineView?(outlineView, sortDescriptorsDidChange: oldDescriptors)
    }

    func outlineView(_ outlineView: NSOutlineView, writeItems items: [Any], to pasteboard: NSPasteboard) -> Bool {
        report()
        return dataSource.outlineView?(outlineView, writeItems: items, to: pasteboard) ?? false
    }

    func outlineView(_ outlineView: NSOutlineView, objectValueFor tableColumn: NSTableColumn?, byItem item: Any?) -> Any? {
        //        report()
        return dataSource.outlineView?(outlineView, objectValueFor: tableColumn, byItem: item)
    }

    func outlineView(_ outlineView: NSOutlineView, acceptDrop info: NSDraggingInfo, item: Any?, childIndex index: Int) -> Bool {
        report()
        return dataSource.outlineView?(outlineView, acceptDrop: info, item: item, childIndex: index) ?? false
    }

    func outlineView(_ outlineView: NSOutlineView, setObjectValue object: Any?, for tableColumn: NSTableColumn?, byItem item: Any?) {
        report()
        dataSource.outlineView?(outlineView, setObjectValue: object, for: tableColumn, byItem: item)
    }

    func outlineView(_ outlineView: NSOutlineView, draggingSession session: NSDraggingSession, endedAt screenPoint: NSPoint, operation: NSDragOperation) {
        report()
        dataSource.outlineView?(outlineView, draggingSession: session, endedAt: screenPoint, operation: operation)
    }

    func outlineView(_ outlineView: NSOutlineView, draggingSession session: NSDraggingSession, willBeginAt screenPoint: NSPoint, forItems draggedItems: [Any]) {
        report()
        dataSource.outlineView?(outlineView, draggingSession: session, willBeginAt: screenPoint, forItems: draggedItems)
    }

    func outlineView(_ outlineView: NSOutlineView, validateDrop info: NSDraggingInfo, proposedItem item: Any?, proposedChildIndex index: Int) -> NSDragOperation {
        report()
        return dataSource.outlineView?(outlineView, validateDrop: info, proposedItem: item, proposedChildIndex: index) ?? NSDragOperation.generic
    }
}

typealias OutlineMemberItem = AnyHashable
extension OutlineViewDiffableDataSource {
    struct SnapshotMember {
        var item: OutlineMemberItem?
        var children: [SnapshotMember] = []
        var isExpandable = false

        func indexPath(of member: SnapshotMember) -> IndexPath? {
            for (idx, child) in children.enumerated() {
                if child == member {
                    return IndexPath(indexes: [idx])
                } else if let childIP = child.indexPath(of: member) {
                    return IndexPath(indexes: [idx]).appending(childIP)
                }
            }
            return nil
        }

        func parent(of member: SnapshotMember) -> SnapshotMember? {
            for child in children {
                if child == member { return self }
                if let p = child.parent(of: member) { return p }
            }
            return nil
        }

        func search(for item: OutlineMemberItem) -> SnapshotMember? {
            if item == self.item { return self }
            for child in children {
                if let hit = child.search(for: item) {
                    return hit
                }
            }
            return nil
        }
    }

    class Snapshot: NSObject {
        private var root: SnapshotMember

        init(from ds: NSOutlineViewDataSource, for view: NSOutlineView) {
            root = Snapshot.member(using: ds, in: view)
            super.init()
        }

        override init() {
            root = SnapshotMember()
            super.init()
        }

        var isEmpty: Bool { return root.children.isEmpty }

        private static func member(for item: OutlineMemberItem? = nil, using ds: NSOutlineViewDataSource, in view: NSOutlineView, recursive: Bool = true) -> SnapshotMember {
            let itemCount = ds.outlineView?(view, numberOfChildrenOfItem: item) ?? 0
            var children = [SnapshotMember]()
            if recursive && itemCount > 0 {
                (0..<itemCount).forEach { counter in
                    if let child = ds.outlineView?(view, child: counter, ofItem: item) as? AnyHashable {
                        children.append(member(for: child, using: ds, in: view, recursive: recursive))
                    }
                }
            }

            let exp: Bool = {
                if let item = item {
                    return ds.outlineView?(view, isItemExpandable: item) ?? false
                } else {
                    return false
                }
            }()

            return SnapshotMember(item: item, children: children, isExpandable: exp)
        }

        static let empty = Snapshot()

        func parent(of member: SnapshotMember) -> SnapshotMember? {
            return root.parent(of: member)
        }

        func instructions(forMorphingInto destination: Snapshot) -> OutlineViewSnapshotDiff {
            return root.rectify(against: destination.root, from: IndexPath())
        }

        func numberOfChildren(ofItem item: AnyHashable?) -> Int {
            if let item = item {
                if let member = root.search(for: item) {
                    return member.children.count
                }
            } else {
                return root.children.count
            }
            return 0
        }

        func child(_ index: Int, ofItem item: OutlineMemberItem?) -> OutlineMemberItem? {
            if let item = item {
                if let member = root.search(for: item) {
                    return member.children[index].item
                }
            } else {
                return root.children[index].item
            }
            return nil
        }

        func isItemExpandable(_ item: OutlineMemberItem) -> Bool {
            if let member = root.search(for: item) {
                return member.isExpandable
            }
            return false
        }
    }
}

extension OutlineViewDiffableDataSource {
    enum ChangeInstruction: CustomStringConvertible {
        case remove(IndexPath)
        case insert(AnyHashable, IndexPath)
        case move(IndexPath, IndexPath)

        var description: String {
            switch self {
            case .remove(let idx): return "Removing @ \(idx)"
            case .insert(let item, let idx): return "Inserting @ \(idx): \(item)"
            case .move(let from, let to): return "Move from \(from) to \(to)"
            }
        }
    }
}

typealias OutlineViewSnapshotDiff = [OutlineViewDiffableDataSource.ChangeInstruction]

extension OutlineViewDiffableDataSource.SnapshotMember: CustomStringConvertible {
    var description: String {
        let thing: Any = item ?? "-nil-"
        return "<OutlineMember: \(String(describing: thing))>"
    }
}

extension OutlineViewDiffableDataSource.SnapshotMember: Equatable {
    static func ==(lhs: OutlineViewDiffableDataSource.SnapshotMember, rhs: OutlineViewDiffableDataSource.SnapshotMember) -> Bool {
        return lhs.item == rhs.item
    }
}

extension OutlineViewDiffableDataSource.SnapshotMember: Hashable {
    func hash(into hasher: inout Hasher) {
        item.hash(into: &hasher)
    }
}

// Here is where the old snapshot and new snapshot are rectified
extension OutlineViewDiffableDataSource.SnapshotMember {
    func rectify(against other: OutlineViewDiffableDataSource.SnapshotMember, from baseIndexPath: IndexPath) -> OutlineViewSnapshotDiff {
        let src = children
        let dst = other.children

        var result = OutlineViewSnapshotDiff()

        func log(_ str: String) {
            // Uncomment for logging info
            //            print(str)
        }

        var work = src
        if src != dst {

            log("\(baseIndexPath) BEGIN")
            log("\(src) -> \(dst)")
            log(" -> \(work)")

            func appendResult(_ inst: OutlineViewDiffableDataSource.ChangeInstruction) {
                result.append(inst)
                log("APPEND: \(inst)\n -> \(work)")
            }

            log("\(baseIndexPath) DELETE PHASE")
            // 1. Find things that don't belong and remove them.
            var deletables = [OutlineViewDiffableDataSource.SnapshotMember]()
            for item in work {
                if !dst.contains(item) {
                    deletables.append(item)
                }
            }
            for deletable in deletables {
                if let delIdx = work.firstIndex(of: deletable) {
                    work.remove(at: delIdx)
                    appendResult(.remove(baseIndexPath.appending(delIdx)))
                }
            }

            log("\(baseIndexPath) INSERT PHASE")
            // 2. Insert missing items.
            for (dstIdx, item) in dst.enumerated() {
                if work.firstIndex(of: item) == nil {
                    // insert
                    work.insert(item, at: dstIdx)
                    appendResult(.insert(item, baseIndexPath.appending(dstIdx)))
                }
            }

            // 3. Moves
            // At this point src and dst have the same contents
            // possibly in different order

            log("\(baseIndexPath) MOVE PHASE")
            for (dstIdx, item) in dst.enumerated() {
                if let workIdx = work.firstIndex(of: item) {
                    if workIdx != dstIdx {
                        work.remove(at: workIdx)
                        work.insert(item, at: dstIdx)
                        appendResult(.move(baseIndexPath.appending(workIdx), baseIndexPath.appending(dstIdx)))
                    }
                }
            }
        }

        log("\(baseIndexPath) RECURSION PHASE")

        // 4. Recurse
        // The hash value is based on the actual item, and not its children.
        // Ergo each item must generate its own instruction set.
        for (index, item) in dst.enumerated() {
            let indexPath = baseIndexPath.appending(index)
            if let workIdx = work.firstIndex(of: item) {
                let workItem = work[workIdx]
                result.append(contentsOf: workItem.rectify(against: item, from: indexPath))
            }
        }

        return result
    }
}

// Turn a diff into commands
extension NSOutlineView {
    func apply(_ snapshot: OutlineViewSnapshotDiff, with animation: NSTableView.AnimationOptions = [.effectFade]) {
        beginUpdates()
        snapshot.forEach { instr in
            switch instr {
            case .insert(_, let indexPath):
                let parent = lastParent(for: indexPath)
                if let childIndex = indexPath.last {
                    insertItems(at: [childIndex], inParent: parent, withAnimation: animation)
                }
            case .move(let src, let dst):
                let srcParent = lastParent(for: src)
                let dstParent = lastParent(for: dst)

                if let srcChild = src.last, let dstChild = dst.last {
                    moveItem(at: srcChild, inParent: srcParent, to: dstChild, inParent: dstParent)
                }
            case .remove(let indexPath):
                let parent = lastParent(for: indexPath)
                if let childIndex = indexPath.last {
                    removeItems(at: [childIndex], inParent: parent, withAnimation: animation)
                }
            }
        }
        endUpdates()
    }

    func lastParent(for indexPath: IndexPath) -> Any? {
        var parent: Any?

        var ip = indexPath
        ip.removeLast()

        for index in ip {
            if let g = child(index, ofItem: parent) {
                parent = g
            }
        }
        return parent
    }
}