Files
2026-09-18 18:16:21 +08:00

524 lines
15 KiB
Dart
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
import 'dart:convert';
import 'dart:math' as math;
import 'package:flutter/foundation.dart';
/// 差异行类型
enum DiffLineType {
/// 未更改
unchanged,
/// 新增
added,
/// 删除
deleted,
/// 空占位行 (在双屏对齐模式下用于填充高度保持两侧对齐)
empty,
}
/// 单侧差异行模型
class DiffLine {
final DiffLineType type;
final String text;
final int? lineNumber;
const DiffLine({
required this.type,
required this.text,
this.lineNumber,
});
bool get isEmptyPlaceholder => type == DiffLineType.empty;
}
/// 单屏内联差异行模型
class UnifiedDiffLine {
final DiffLineType type;
final String text;
final int? oldLineNumber;
final int? newLineNumber;
const UnifiedDiffLine({
required this.type,
required this.text,
this.oldLineNumber,
this.newLineNumber,
});
}
/// 双屏差异对比计算结果
class SplitDiffResult {
final List<DiffLine> leftLines;
final List<DiffLine> rightLines;
final List<int> changeRowIndices;
final int additionsCount;
final int deletionsCount;
const SplitDiffResult({
required this.leftLines,
required this.rightLines,
required this.changeRowIndices,
required this.additionsCount,
required this.deletionsCount,
});
}
/// 编辑区行号栏 Git 差异提示类型(对标 VS Code)
enum GitGutterDiffType {
/// 修改行(黄色/Amber)
modified,
/// 新增行(绿色/Green)
added,
/// 删除标记(红色/Red)
deleted,
}
/// Git Diff 算法与行对齐计算工具类
class GitDiffHelper {
/// 计算编辑区每一行的 Git 差异标记映射(0-based 行号 -> 差异类型)
static Map<int, GitGutterDiffType> computeLineDiff(
String baseContent,
String currentContent,
) {
if (baseContent == currentContent) return const {};
final originalLines = splitLines(baseContent);
final currentLines = splitLines(currentContent);
if (originalLines.isEmpty && currentLines.isEmpty) return const {};
if (originalLines.isEmpty) {
final map = <int, GitGutterDiffType>{};
for (int i = 0; i < currentLines.length; i++) {
map[i] = GitGutterDiffType.added;
}
return map;
}
if (currentLines.isEmpty) {
return {0: GitGutterDiffType.deleted};
}
// 1. 公共前后缀双向 O(1) 快速收缩剪枝 (与 Myers Diff 对齐,规避大文件整屏计算与误判)
int prefixCount = 0;
while (prefixCount < originalLines.length &&
prefixCount < currentLines.length &&
originalLines[prefixCount] == currentLines[prefixCount]) {
prefixCount++;
}
int suffixCount = 0;
while (suffixCount < (originalLines.length - prefixCount) &&
suffixCount < (currentLines.length - prefixCount) &&
originalLines[originalLines.length - 1 - suffixCount] ==
currentLines[currentLines.length - 1 - suffixCount]) {
suffixCount++;
}
// 若前后缀完全覆盖,内容完全一致
if (prefixCount == originalLines.length && prefixCount == currentLines.length) {
return const {};
}
final middleOrig = originalLines.sublist(
prefixCount,
originalLines.length - suffixCount,
);
final middleCurr = currentLines.sublist(
prefixCount,
currentLines.length - suffixCount,
);
final diffOps = _computeDiffOperations(middleOrig, middleCurr);
final markers = <int, GitGutterDiffType>{};
int currentLineIndex = prefixCount;
int opIndex = 0;
while (opIndex < diffOps.length) {
final op = diffOps[opIndex];
if (op.type == _DiffOpType.equal) {
currentLineIndex++;
opIndex++;
} else {
int deleteCount = 0;
int insertCount = 0;
while (opIndex < diffOps.length && diffOps[opIndex].type != _DiffOpType.equal) {
if (diffOps[opIndex].type == _DiffOpType.delete) {
deleteCount++;
} else if (diffOps[opIndex].type == _DiffOpType.insert) {
insertCount++;
}
opIndex++;
}
if (deleteCount > 0 && insertCount > 0) {
final modifiedLinesCount = math.min(deleteCount, insertCount);
for (int i = 0; i < modifiedLinesCount; i++) {
markers[currentLineIndex + i] = GitGutterDiffType.modified;
}
for (int i = modifiedLinesCount; i < insertCount; i++) {
markers[currentLineIndex + i] = GitGutterDiffType.added;
}
currentLineIndex += insertCount;
} else if (insertCount > 0) {
for (int i = 0; i < insertCount; i++) {
markers[currentLineIndex + i] = GitGutterDiffType.added;
}
currentLineIndex += insertCount;
} else if (deleteCount > 0) {
final targetLine = currentLineIndex < currentLines.length
? currentLineIndex
: math.max(0, currentLines.length - 1);
markers.putIfAbsent(targetLine, () => GitGutterDiffType.deleted);
}
}
}
return markers;
}
/// 异步计算编辑区 Git 差异(在大文件或复杂改动时将计算丢入后台 Isolate,保障主线程 60fps)
static Future<Map<int, GitGutterDiffType>> computeLineDiffAsync(
String baseContent,
String currentContent,
) async {
if (baseContent == currentContent) return const {};
if (baseContent.length < 32768 && currentContent.length < 32768) {
return computeLineDiff(baseContent, currentContent);
}
return compute<_DiffInputPayload, Map<int, GitGutterDiffType>>(
_computeLineDiffEntry,
_DiffInputPayload(baseContent, currentContent),
);
}
/// 公开的按行分割函数
static List<String> splitLines(String text) => _splitLines(text);
/// 计算双屏并排对齐结果
static SplitDiffResult computeSplitDiff(String originalText, String modifiedText) {
final originalLines = _splitLines(originalText);
final modifiedLines = _splitLines(modifiedText);
// 1. 公共前后缀快速收缩剪枝 (大幅提升常见文件差异计算性能)
int prefixCount = 0;
while (prefixCount < originalLines.length &&
prefixCount < modifiedLines.length &&
originalLines[prefixCount] == modifiedLines[prefixCount]) {
prefixCount++;
}
int suffixCount = 0;
while (suffixCount < (originalLines.length - prefixCount) &&
suffixCount < (modifiedLines.length - prefixCount) &&
originalLines[originalLines.length - 1 - suffixCount] ==
modifiedLines[modifiedLines.length - 1 - suffixCount]) {
suffixCount++;
}
final leftResult = <DiffLine>[];
final rightResult = <DiffLine>[];
final changeRowIndices = <int>[];
int additions = 0;
int deletions = 0;
// 前缀相同部分
for (int i = 0; i < prefixCount; i++) {
final line = originalLines[i];
leftResult.add(DiffLine(
type: DiffLineType.unchanged,
text: line,
lineNumber: i + 1,
));
rightResult.add(DiffLine(
type: DiffLineType.unchanged,
text: line,
lineNumber: i + 1,
));
}
// 中间变化部分
final middleOrig = originalLines.sublist(
prefixCount,
originalLines.length - suffixCount,
);
final middleMod = modifiedLines.sublist(
prefixCount,
modifiedLines.length - suffixCount,
);
int origLineNo = prefixCount + 1;
int modLineNo = prefixCount + 1;
final diffOps = _computeDiffOperations(middleOrig, middleMod);
// 将 diff 操作块分组合并以构建双屏对齐
int opIndex = 0;
while (opIndex < diffOps.length) {
final op = diffOps[opIndex];
if (op.type == _DiffOpType.equal) {
leftResult.add(DiffLine(
type: DiffLineType.unchanged,
text: op.text,
lineNumber: origLineNo++,
));
rightResult.add(DiffLine(
type: DiffLineType.unchanged,
text: op.text,
lineNumber: modLineNo++,
));
opIndex++;
} else {
// 遇到变更块 (连续的 delete 与 insert)
final delBlock = <String>[];
final addBlock = <String>[];
while (opIndex < diffOps.length && diffOps[opIndex].type != _DiffOpType.equal) {
if (diffOps[opIndex].type == _DiffOpType.delete) {
delBlock.add(diffOps[opIndex].text);
deletions++;
} else if (diffOps[opIndex].type == _DiffOpType.insert) {
addBlock.add(diffOps[opIndex].text);
additions++;
}
opIndex++;
}
// 记录差异起点行索引
changeRowIndices.add(leftResult.length);
final maxLen = math.max(delBlock.length, addBlock.length);
for (int i = 0; i < maxLen; i++) {
if (i < delBlock.length) {
leftResult.add(DiffLine(
type: DiffLineType.deleted,
text: delBlock[i],
lineNumber: origLineNo++,
));
} else {
leftResult.add(const DiffLine(
type: DiffLineType.empty,
text: '',
lineNumber: null,
));
}
if (i < addBlock.length) {
rightResult.add(DiffLine(
type: DiffLineType.added,
text: addBlock[i],
lineNumber: modLineNo++,
));
} else {
rightResult.add(const DiffLine(
type: DiffLineType.empty,
text: '',
lineNumber: null,
));
}
}
}
}
// 后缀相同部分
final origSuffixStart = originalLines.length - suffixCount;
final modSuffixStart = modifiedLines.length - suffixCount;
for (int i = 0; i < suffixCount; i++) {
final line = originalLines[origSuffixStart + i];
leftResult.add(DiffLine(
type: DiffLineType.unchanged,
text: line,
lineNumber: origSuffixStart + i + 1,
));
rightResult.add(DiffLine(
type: DiffLineType.unchanged,
text: line,
lineNumber: modSuffixStart + i + 1,
));
}
return SplitDiffResult(
leftLines: leftResult,
rightLines: rightResult,
changeRowIndices: changeRowIndices,
additionsCount: additions,
deletionsCount: deletions,
);
}
/// 将双屏结果或文本转换为单屏内联 (Unified) 差异行列表
static List<UnifiedDiffLine> toUnifiedDiff(String originalText, String modifiedText) {
final originalLines = _splitLines(originalText);
final modifiedLines = _splitLines(modifiedText);
// 公共前缀快速收缩剪枝
int prefixCount = 0;
while (prefixCount < originalLines.length &&
prefixCount < modifiedLines.length &&
originalLines[prefixCount] == modifiedLines[prefixCount]) {
prefixCount++;
}
// 公共后缀快速收缩剪枝
int suffixCount = 0;
while (suffixCount < (originalLines.length - prefixCount) &&
suffixCount < (modifiedLines.length - prefixCount) &&
originalLines[originalLines.length - 1 - suffixCount] ==
modifiedLines[modifiedLines.length - 1 - suffixCount]) {
suffixCount++;
}
final result = <UnifiedDiffLine>[];
int origLineNo = 1;
int modLineNo = 1;
// 1. 前缀相同部分
for (int i = 0; i < prefixCount; i++) {
result.add(UnifiedDiffLine(
type: DiffLineType.unchanged,
text: originalLines[i],
oldLineNumber: origLineNo++,
newLineNumber: modLineNo++,
));
}
// 2. 中间差异部分
final middleOrig = originalLines.sublist(
prefixCount,
originalLines.length - suffixCount,
);
final middleMod = modifiedLines.sublist(
prefixCount,
modifiedLines.length - suffixCount,
);
final diffOps = _computeDiffOperations(middleOrig, middleMod);
for (final op in diffOps) {
switch (op.type) {
case _DiffOpType.equal:
result.add(UnifiedDiffLine(
type: DiffLineType.unchanged,
text: op.text,
oldLineNumber: origLineNo++,
newLineNumber: modLineNo++,
));
break;
case _DiffOpType.delete:
result.add(UnifiedDiffLine(
type: DiffLineType.deleted,
text: op.text,
oldLineNumber: origLineNo++,
newLineNumber: null,
));
break;
case _DiffOpType.insert:
result.add(UnifiedDiffLine(
type: DiffLineType.added,
text: op.text,
oldLineNumber: null,
newLineNumber: modLineNo++,
));
break;
}
}
// 3. 后缀相同部分
final origSuffixStart = originalLines.length - suffixCount;
for (int i = 0; i < suffixCount; i++) {
result.add(UnifiedDiffLine(
type: DiffLineType.unchanged,
text: originalLines[origSuffixStart + i],
oldLineNumber: origLineNo++,
newLineNumber: modLineNo++,
));
}
return result;
}
static List<String> _splitLines(String text) {
if (text.isEmpty) return [];
return const LineSplitter().convert(text);
}
/// 计算差异编辑脚本 (基于标准动态规划 LCS 矩阵,针对超长文本具备平滑防御)
static List<_DiffOp> _computeDiffOperations(List<String> a, List<String> b) {
final n = a.length;
final m = b.length;
if (n == 0) {
return b.map((text) => _DiffOp(_DiffOpType.insert, text)).toList();
}
if (m == 0) {
return a.map((text) => _DiffOp(_DiffOpType.delete, text)).toList();
}
// 防御过大矩阵导致的 OOM (单次差异超过 200,000 元素积时快速回退)
if (n * m > 250000) {
return [
...a.map((text) => _DiffOp(_DiffOpType.delete, text)),
...b.map((text) => _DiffOp(_DiffOpType.insert, text)),
];
}
// LCS 动态规划
final dp = List.generate(n + 1, (_) => List<int>.filled(m + 1, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i] == b[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
// 回溯生成操作队列
final ops = <_DiffOp>[];
int i = n;
int j = m;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && a[i - 1] == b[j - 1]) {
ops.add(_DiffOp(_DiffOpType.equal, a[i - 1]));
i--;
j--;
} else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
ops.add(_DiffOp(_DiffOpType.insert, b[j - 1]));
j--;
} else if (i > 0 && (j == 0 || dp[i][j - 1] < dp[i - 1][j])) {
ops.add(_DiffOp(_DiffOpType.delete, a[i - 1]));
i--;
}
}
return ops.reversed.toList();
}
}
enum _DiffOpType { equal, delete, insert }
class _DiffOp {
final _DiffOpType type;
final String text;
_DiffOp(this.type, this.text);
}
class _DiffInputPayload {
final String baseContent;
final String currentContent;
const _DiffInputPayload(this.baseContent, this.currentContent);
}
Map<int, GitGutterDiffType> _computeLineDiffEntry(_DiffInputPayload payload) {
return GitDiffHelper.computeLineDiff(payload.baseContent, payload.currentContent);
}