hybrid_diff.dart

import 'dart:math';
import 'dart:typed_data';

enum ChangeOp { insert, delete, modify, equal }

class DiffNode {
  final ChangeOp op;
  final String key;
  final Object? oldValue;
  final Object? newValue;
  final List<DiffNode>? children;
  final TextSplice? splice;

  DiffNode.insert(this.key, this.newValue)
    : op = ChangeOp.insert,
      oldValue = null,
      children = null,
      splice = null;

  DiffNode.delete(this.key, this.oldValue)
    : op = ChangeOp.delete,
      newValue = null,
      children = null,
      splice = null;

  DiffNode.equal(this.key, this.newValue)
    : op = ChangeOp.equal,
      oldValue = newValue,
      children = null,
      splice = null;

  DiffNode.modify(
    this.key,
    this.oldValue,
    this.newValue, {
    this.children,
    this.splice,
  }) : op = ChangeOp.modify;

  @override
  String toString() => '$op: $key';
}

class TextSplice {
  final int index;
  final int deleteCount;
  final String insertText;

  TextSplice(this.index, this.deleteCount, this.insertText);

  Map<String, dynamic> toJson() => {
    'i': index,
    'd': deleteCount,
    't': insertText,
  };
}

class HybridDiffer {
  static List<DiffNode> diff(
    List<Map<String, Object?>> oldList,
    List<Map<String, Object?>> newList, {
    required String idField,
  }) {
    final oldIds = oldList.map((e) => e[idField]).toList();
    final newIds = newList.map((e) => e[idField]).toList();

    final structuralOps = _myersDiff(oldIds, newIds);
    final results = <DiffNode>[];

    for (final op in structuralOps) {
      if (op.type == _MyersOpType.delete) {
        final item = oldList[op.oldIndex!];
        results.add(DiffNode.delete(item[idField].toString(), item));
      } else if (op.type == _MyersOpType.insert) {
        final item = newList[op.newIndex!];
        results.add(DiffNode.insert(item[idField].toString(), item));
      } else {
        // Equal ID: Check Content
        final oldItem = oldList[op.oldIndex!];
        final newItem = newList[op.newIndex!];
        final key = newItem[idField].toString();

        if (_areDeepEqual(oldItem, newItem)) {
          results.add(DiffNode.equal(key, newItem));
        } else {
          final fieldChanges = _generateObjectDiff(oldItem, newItem);
          results.add(
            DiffNode.modify(key, oldItem, newItem, children: fieldChanges),
          );
        }
      }
    }
    return results;
  }

  static List<DiffNode> _generateObjectDiff(
    Map<String, Object?> oldObj,
    Map<String, Object?> newObj,
  ) {
    final diffs = <DiffNode>[];
    final allKeys = {...oldObj.keys, ...newObj.keys}.toList()..sort();

    for (final key in allKeys) {
      final oldVal = oldObj[key];
      final newVal = newObj[key];

      if (!oldObj.containsKey(key)) {
        diffs.add(DiffNode.insert(key, newVal));
      } else if (!newObj.containsKey(key)) {
        diffs.add(DiffNode.delete(key, oldVal));
      } else if (oldVal is Map<String, Object?> &&
          newVal is Map<String, Object?>) {
        final nested = _generateObjectDiff(oldVal, newVal);
        if (nested.isNotEmpty) {
          diffs.add(DiffNode.modify(key, oldVal, newVal, children: nested));
        }
      } else if (oldVal is String && newVal is String) {
        if (oldVal != newVal) {
          final splice = _calculateStringSplice(oldVal, newVal);
          diffs.add(DiffNode.modify(key, oldVal, newVal, splice: splice));
        }
      } else {
        if (!_areDeepEqual(oldVal, newVal)) {
          diffs.add(DiffNode.modify(key, oldVal, newVal));
        }
      }
    }
    return diffs;
  }

  static bool _areDeepEqual(Object? a, Object? b) {
    if (a == b) return true;
    if (a is List && b is List) {
      if (a.length != b.length) return false;
      for (var i = 0; i < a.length; i++) {
        if (!_areDeepEqual(a[i], b[i])) return false;
      }
      return true;
    }
    if (a is Map && b is Map) {
      if (a.length != b.length) return false;
      for (final key in a.keys) {
        if (!b.containsKey(key) || !_areDeepEqual(a[key], b[key])) return false;
      }
      return true;
    }
    return false;
  }

  static TextSplice? _calculateStringSplice(String oldText, String newText) {
    if (oldText == newText) return null;
    int start = 0;
    final minLen = min(oldText.length, newText.length);
    while (start < minLen &&
        oldText.codeUnitAt(start) == newText.codeUnitAt(start)) {
      start++;
    }

    if (start > 0 &&
        start < oldText.length &&
        _isSurrogate(oldText.codeUnitAt(start - 1))) {
      start--;
    }

    int oldEnd = oldText.length;
    int newEnd = newText.length;
    while (oldEnd > start &&
        newEnd > start &&
        oldText.codeUnitAt(oldEnd - 1) == newText.codeUnitAt(newEnd - 1)) {
      oldEnd--;
      newEnd--;
    }

    return TextSplice(start, oldEnd - start, newText.substring(start, newEnd));
  }

  static bool _isSurrogate(int code) => (code >= 0xD800 && code <= 0xDFFF);

  // --- MYERS ALGORITHM ---

  static List<_MyersOp> _myersDiff(List oldIds, List newIds) {
    final n = oldIds.length;
    final m = newIds.length;
    final max = n + m;
    final v = Int32List(2 * max + 1)..fillRange(0, 2 * max + 1, -1);
    final trace = <Int32List>[];

    v[max] = 0;

    for (var d = 0; d <= max; d++) {
      trace.add(Int32List.fromList(v));
      for (var k = -d; k <= d; k += 2) {
        final indexK = max + k;
        int x;
        if (d == 0) {
          x = 0;
        } else if (k == -d || (k != d && v[indexK - 1] < v[indexK + 1])) {
          x = v[indexK + 1];
        } else {
          x = v[indexK - 1] + 1;
        }
        int y = x - k;
        while (x < n && y < m && oldIds[x] == newIds[y]) {
          x++;
          y++;
        }
        v[indexK] = x;
        if (x >= n && y >= m) {
          return _buildMyersScript(oldIds, newIds, trace, d, max);
        }
      }
    }
    return [];
  }

  static List<_MyersOp> _buildMyersScript(
    List oldIds,
    List newIds,
    List<Int32List> trace,
    int d,
    int maxOffset,
  ) {
    var script = <_MyersOp>[];
    var x = oldIds.length;
    var y = newIds.length;

    for (var i = d; i > 0; i--) {
      final k = x - y;
      final kIndex = maxOffset + k;
      final prevV = trace[i];
      final kMinus1 = kIndex - 1;
      final kPlus1 = kIndex - 1 + 2; // kIndex + 1

      int prevKIndex;
      final bool pickInsert;

      if (k == -i) {
        pickInsert = true;
      } else if (k == i) {
        pickInsert = false;
      } else if (prevV[kMinus1] == -1) {
        pickInsert = true;
      } else if (prevV[kPlus1] == -1) {
        pickInsert = false;
      } else {
        pickInsert = prevV[kMinus1] < prevV[kPlus1];
      }

      if (pickInsert) {
        prevKIndex = kPlus1;
      } else {
        prevKIndex = kMinus1;
      }

      final prevX = prevV[prevKIndex];
      final isInsert = prevKIndex == kPlus1;
      final startX = isInsert ? prevX : prevX + 1;

      while (x > startX) {
        // Snake loop logic
        script.add(
          _MyersOp(_MyersOpType.equal, oldIndex: x - 1, newIndex: y - 1),
        );
        x--;
        y--;
      }

      if (isInsert) {
        // Moved down (Insert)
        script.add(_MyersOp(_MyersOpType.insert, newIndex: y - 1));
        y--;
      } else {
        // Moved right (Delete)
        script.add(_MyersOp(_MyersOpType.delete, oldIndex: x - 1));
        x--;
      }
    }

    // Flush remaining snakes
    while (x > 0 && y > 0) {
      script.add(
        _MyersOp(_MyersOpType.equal, oldIndex: x - 1, newIndex: y - 1),
      );
      x--;
      y--;
    }
    return script.reversed.toList();
  }
}

enum _MyersOpType { insert, delete, equal }

class _MyersOp {
  final _MyersOpType type;
  final int? oldIndex;
  final int? newIndex;
  _MyersOp(this.type, {this.oldIndex, this.newIndex});
}

hybrid_diff_test.dart

import 'package:test/test.dart';

import 'hybrid_diff.dart';

void main() {
  group('HybridDiffer Structural Tests (Myers)', () {
    test('Identical lists return no changes', () {
      final list = [
        {'id': 1, 'val': 'a'},
        {'id': 2, 'val': 'b'},
      ];
      final changes = HybridDiffer.diff(list, list, idField: 'id');

      // We expect equal nodes or no nodes depending on filtering.
      // The implementation returns Equal nodes for matches.
      expect(changes.every((c) => c.op == ChangeOp.equal), isTrue);
      expect(changes.length, equals(2));
    });

    test('Detects simple insertion', () {
      final oldList = [
        {'id': 1, 'val': 'a'},
      ];
      final newList = [
        {'id': 1, 'val': 'a'},
        {'id': 2, 'val': 'b'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');

      expect(changes.length, equals(2));
      expect(changes[0].op, equals(ChangeOp.equal));
      expect(changes[1].op, equals(ChangeOp.insert));
      expect(changes[1].key, equals('2'));
    });

    test('Detects simple deletion', () {
      final oldList = [
        {'id': 1, 'val': 'a'},
        {'id': 2, 'val': 'b'},
      ];
      final newList = [
        {'id': 1, 'val': 'a'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');

      expect(changes.length, equals(2));
      expect(changes[0].op, equals(ChangeOp.equal));
      expect(changes[1].op, equals(ChangeOp.delete));
      expect(changes[1].key, equals('2'));
    });

    test('Detects moves (Delete + Insert)', () {
      // Myers detects moves as a delete of the old position and insert at new
      final oldList = [
        {'id': 1},
        {'id': 2},
        {'id': 3},
      ];
      final newList = [
        {'id': 1},
        {'id': 3},
        {'id': 2},
      ]; // 2 moved to end

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');

      // Expected: Equal(1), Equal(3), Insert(2), Delete(2) OR Equal(1), Delete(2), Equal(3), Insert(2)
      // Myers usually prefers deletes first if weights are equal, but let's check operations.
      final ops = changes.map((c) => c.op).toList();

      expect(ops, contains(ChangeOp.insert));
      expect(ops, contains(ChangeOp.delete));

      final insertNode = changes.firstWhere((c) => c.op == ChangeOp.insert);
      final deleteNode = changes.firstWhere((c) => c.op == ChangeOp.delete);

      expect(insertNode.key, equals(deleteNode.key));
      expect(['2', '3'], contains(insertNode.key));
    });
  });

  group('HybridDiffer Content Tests (Deep Diff)', () {
    test('Detects modification in primitive fields', () {
      final oldList = [
        {'id': 1, 'name': 'Alice'},
      ];
      final newList = [
        {'id': 1, 'name': 'Bob'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');

      expect(changes.length, equals(1));
      final mod = changes.first;

      expect(mod.op, equals(ChangeOp.modify));
      expect(mod.children, isNotNull);
      expect(mod.children!.length, equals(1));

      final fieldChange = mod.children!.first;
      expect(fieldChange.key, equals('name'));
      expect(fieldChange.oldValue, equals('Alice'));
      expect(fieldChange.newValue, equals('Bob'));
    });

    test('Detects nested map changes recursively', () {
      final oldList = [
        {
          'id': 1,
          'meta': {'ver': 1, 'author': 'me'},
        },
      ];
      final newList = [
        {
          'id': 1,
          'meta': {'ver': 2, 'author': 'me'},
        },
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');
      final rootMod = changes.first;

      // Look inside the 'meta' field
      final metaMod = rootMod.children!.firstWhere((c) => c.key == 'meta');
      expect(metaMod.op, equals(ChangeOp.modify));

      // Look inside 'ver' field
      final verMod = metaMod.children!.firstWhere((c) => c.key == 'ver');
      expect(verMod.oldValue, equals(1));
      expect(verMod.newValue, equals(2));
    });

    test('Handles null values correctly', () {
      final oldList = [
        {'id': 1, 'val': null},
      ];
      final newList = [
        {'id': 1, 'val': 'not null'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');
      final fieldChange = changes.first.children!.first;

      expect(fieldChange.key, equals('val'));
      expect(fieldChange.oldValue, isNull);
      expect(fieldChange.newValue, equals('not null'));
    });
  });

  group('String Splice Optimization', () {
    test('Generates TextSplice for string changes', () {
      final oldList = [
        {'id': 1, 'text': 'Hello World'},
      ];
      final newList = [
        {'id': 1, 'text': 'Hello Flutter World'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');
      final fieldChange = changes.first.children!.first;

      expect(fieldChange.key, equals('text'));
      expect(fieldChange.splice, isNotNull);

      // "Hello " (len 6) match. Insert "Flutter ".
      expect(fieldChange.splice!.index, equals(6));
      expect(fieldChange.splice!.deleteCount, equals(0));
      expect(fieldChange.splice!.insertText, equals('Flutter '));
    });

    test('Handles Unicode Surrogate Pairs (Emoji Safety)', () {
      // 🤚 is \uD83E\uDD1A (2 code units)
      final oldList = [
        {'id': 1, 'text': 'Hi 🤚'},
      ];
      final newList = [
        {'id': 1, 'text': 'Hi 🤚 there'},
      ];

      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');
      final fieldChange = changes.first.children!.first;

      expect(fieldChange.splice, isNotNull);
      // Ensure we didn't split the emoji. The index should differ by proper length.
      // 'Hi ' is 3. Emoji is 2. Total 5.
      expect(fieldChange.splice!.index, greaterThanOrEqualTo(5));
      expect(fieldChange.splice!.insertText, contains('there'));
    });
  });

  group('Performance / Stress Test', () {
    test('Handles large lists efficiently', () {
      // Generate 5000 items
      final oldList = List<Map<String, dynamic>>.generate(
        5000,
        (i) => {'id': i, 'val': 'item $i'},
      );
      final newList = List<Map<String, dynamic>>.from(oldList);

      // Make 3 changes
      newList.removeAt(100); // Delete
      newList.insert(4000, {'id': 9999, 'val': 'new'}); // Insert
      // Index 2500 shifted to 2499
      newList[2499] = {'id': 2500, 'val': 'CHANGED'}; // Modify

      final stopwatch = Stopwatch()..start();
      final changes = HybridDiffer.diff(oldList, newList, idField: 'id');
      stopwatch.stop();

      print('Diff 5000 items took: ${stopwatch.elapsedMilliseconds}ms');

      final deletes = changes.where((c) => c.op == ChangeOp.delete);
      final inserts = changes.where((c) => c.op == ChangeOp.insert);
      final modifies = changes.where((c) => c.op == ChangeOp.modify);

      expect(deletes.length, equals(1));
      expect(inserts.length, equals(1));
      expect(modifies.length, equals(1));

      // Ensure it's reasonably fast (adjust threshold for your machine)
      expect(stopwatch.elapsedMilliseconds, lessThan(500));
    });
  });
}