299 lines
7.7 KiB
Dart
299 lines
7.7 KiB
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});
|
|
}
|