freefire
5270fee2b7
- 新增 smartDiff 差异计算与 EditHistoryModal 编辑历史弹窗，替换原 CommentEditHistoryModal - 新增 PostEditedMark 编辑标记展示 - 新增内容锁定机制（content_lock）防止并发编辑冲突 - 审核与通知服务适配
528 lines
17 KiB
TypeScript
528 lines
17 KiB
TypeScript
/**
|
||
* smartDiff —— 面向可读性的结构化行级 diff（自研，无第三方依赖）。
|
||
*
|
||
* 四层处理：
|
||
* 1. 预处理：CRLF/CR → LF（仅用于比较与展示），行尾空白在比较时忽略（展示保留原文）。
|
||
* 2. 算法选择：行级相似度（difflib ratio 思路：2M/(a+b)，M 为多重集交集）低于阈值时
|
||
* 判定「整段替换」，输出一个 block-replace，跳过逐行对齐——避免把毫无对应关系的
|
||
* 两段文本切成几十对 -/+ 碎片；否则用 Patience diff（锚定双方唯一行，LIS 选链），
|
||
* 无锚点/超大规模/超深递归的子区间回退为 LCS 或整块替换。
|
||
* 3. 后处理：相邻同向变更合并为一个块（del 在前 ins 在后），消除 LCS 的交叉配对；
|
||
* 上下文折叠（默认 3 行，头/尾块只保留单侧上下文）。
|
||
* 4. 行内细分：replace 块内按下标配对的行对，先分词（CJK 单字、西文单词、空白、符号），
|
||
* 词级 LCS 相似度 > 阈值时输出变更片段的字符偏移（segments），否则整行视为变更。
|
||
*
|
||
* 输出为结构化块数组，供 diff 视图组件渲染；segments 直接挂在对应行上
|
||
* （start/end 为该行文本的 UTF-16 偏移），UI 只高亮变更部分。
|
||
*/
|
||
|
||
export type LineOp = "equal" | "del" | "ins";
|
||
export type BlockType = "equal" | "insert" | "delete" | "replace" | "block-replace";
|
||
|
||
/** 行内变更片段：start/end 为行文本的 UTF-16 偏移，type 为该行视角下的变更方向 */
|
||
export interface InlineSegment {
|
||
start: number;
|
||
end: number;
|
||
type: "del" | "ins";
|
||
}
|
||
|
||
export interface DiffLine {
|
||
op: LineOp;
|
||
/** 原始行文本（保留行尾空白，供展示） */
|
||
text: string;
|
||
/** 仅 replace 块中被判定为「修改」的行对附带；缺省表示整行变更 */
|
||
segments?: InlineSegment[];
|
||
}
|
||
|
||
export interface DiffBlock {
|
||
type: BlockType;
|
||
lines: DiffLine[];
|
||
}
|
||
|
||
export interface DiffStats {
|
||
adds: number;
|
||
dels: number;
|
||
}
|
||
|
||
export interface DiffResult {
|
||
blocks: DiffBlock[];
|
||
stats: DiffStats;
|
||
}
|
||
|
||
export interface SmartDiffOptions {
|
||
/** 行级相似度低于该值判定整段替换（默认 0.2；仅任一侧 ≥2 行时生效） */
|
||
replaceThreshold?: number;
|
||
/** 行对词级相似度高于该值才做行内细分（默认 0.6） */
|
||
inlineThreshold?: number;
|
||
}
|
||
|
||
// 行级 LCS 回退的规模上限（超出则该区间整块替换，避免 O(n·m) 爆炸）
|
||
const MAX_REGION_CELLS = 400_000;
|
||
// 行内词级 LCS 的 token 数上限
|
||
const MAX_INLINE_CELLS = 20_000;
|
||
// 行对合计字符数超过则跳过行内细分
|
||
const MAX_INLINE_CHARS = 4_000;
|
||
// Patience 递归深度上限（超过直接整块替换，防御构造性深递归）
|
||
const MAX_PATIENCE_DEPTH = 32;
|
||
|
||
/* ---------------- 第一层：预处理 ---------------- */
|
||
|
||
interface SplitText {
|
||
raw: string[];
|
||
/** 归一化后的行（比较用）：行尾空白已去除 */
|
||
cmp: string[];
|
||
}
|
||
|
||
function splitLines(text: string): SplitText {
|
||
const norm = text.replace(/\r\n?/g, "\n");
|
||
const raw = norm === "" ? [] : norm.split("\n");
|
||
return { raw, cmp: raw.map((l) => l.replace(/\s+$/, "")) };
|
||
}
|
||
|
||
/* ---------------- 第二层：相似度与算法选择 ---------------- */
|
||
|
||
/** 行级相似度：difflib ratio 思路，2M/(a+b)，M 为行多重集交集大小 */
|
||
function lineSimilarity(a: string[], b: string[]): number {
|
||
if (a.length === 0 && b.length === 0) return 1;
|
||
const freq = new Map<string, number>();
|
||
for (const l of a) freq.set(l, (freq.get(l) ?? 0) + 1);
|
||
let m = 0;
|
||
for (const l of b) {
|
||
const c = freq.get(l) ?? 0;
|
||
if (c > 0) {
|
||
m += 1;
|
||
freq.set(l, c - 1);
|
||
}
|
||
}
|
||
return (2 * m) / (a.length + b.length);
|
||
}
|
||
|
||
type RawOp = { op: LineOp; ai: number; bi: number };
|
||
|
||
/**
|
||
* Patience diff：在区间内找到「双方都恰好出现一次」的公共行作锚点，
|
||
* 对锚点按 i 升序求 j 的最长递增子序列（patience sorting，O(k log k)）作骨架，
|
||
* 骨架之间的间隙递归；无锚点/超深的区间回退 fallbackRegion。
|
||
*/
|
||
function patienceDiff(
|
||
cmpA: string[],
|
||
cmpB: string[],
|
||
loA: number,
|
||
hiA: number,
|
||
loB: number,
|
||
hiB: number,
|
||
out: RawOp[],
|
||
depth: number
|
||
): void {
|
||
if (loA >= hiA && loB >= hiB) return;
|
||
|
||
const countA = new Map<string, number>();
|
||
for (let i = loA; i < hiA; i++) countA.set(cmpA[i], (countA.get(cmpA[i]) ?? 0) + 1);
|
||
const countB = new Map<string, number>();
|
||
for (let j = loB; j < hiB; j++) countB.set(cmpB[j], (countB.get(cmpB[j]) ?? 0) + 1);
|
||
|
||
const posA = new Map<string, number>();
|
||
for (let i = loA; i < hiA; i++) {
|
||
if (countA.get(cmpA[i]) === 1) posA.set(cmpA[i], i);
|
||
}
|
||
const anchors: Array<{ i: number; j: number }> = [];
|
||
for (let j = loB; j < hiB; j++) {
|
||
if (countB.get(cmpB[j]) === 1) {
|
||
const i = posA.get(cmpB[j]);
|
||
if (i !== undefined) anchors.push({ i, j });
|
||
}
|
||
}
|
||
if (anchors.length === 0 || depth >= MAX_PATIENCE_DEPTH) {
|
||
fallbackRegion(cmpA, cmpB, loA, hiA, loB, hiB, out);
|
||
return;
|
||
}
|
||
|
||
anchors.sort((x, y) => x.i - y.i);
|
||
const tails: number[] = [];
|
||
const prev = new Array<number>(anchors.length).fill(-1);
|
||
for (let k = 0; k < anchors.length; k++) {
|
||
const j = anchors[k].j;
|
||
let lo = 0;
|
||
let hi = tails.length;
|
||
while (lo < hi) {
|
||
const mid = (lo + hi) >> 1;
|
||
if (anchors[tails[mid]].j < j) lo = mid + 1;
|
||
else hi = mid;
|
||
}
|
||
if (lo > 0) prev[k] = tails[lo - 1];
|
||
if (lo === tails.length) tails.push(k);
|
||
else tails[lo] = k;
|
||
}
|
||
const chain: number[] = [];
|
||
for (let k = tails[tails.length - 1]; k !== -1; k = prev[k]) chain.push(k);
|
||
chain.reverse();
|
||
|
||
let ai = loA;
|
||
let bi = loB;
|
||
for (const k of chain) {
|
||
const { i, j } = anchors[k];
|
||
patienceDiff(cmpA, cmpB, ai, i, bi, j, out, depth + 1);
|
||
out.push({ op: "equal", ai: i, bi: j });
|
||
ai = i + 1;
|
||
bi = j + 1;
|
||
}
|
||
patienceDiff(cmpA, cmpB, ai, hiA, bi, hiB, out, depth + 1);
|
||
}
|
||
|
||
/** 无锚点区间：无公共行或规模超限时整块替换；否则 LCS 细对齐 */
|
||
function fallbackRegion(
|
||
cmpA: string[],
|
||
cmpB: string[],
|
||
loA: number,
|
||
hiA: number,
|
||
loB: number,
|
||
hiB: number,
|
||
out: RawOp[]
|
||
): void {
|
||
const n = hiA - loA;
|
||
const m = hiB - loB;
|
||
if (n === 0 && m === 0) return;
|
||
if (n === 0) {
|
||
for (let j = loB; j < hiB; j++) out.push({ op: "ins", ai: loA, bi: j });
|
||
return;
|
||
}
|
||
if (m === 0) {
|
||
for (let i = loA; i < hiA; i++) out.push({ op: "del", ai: i, bi: loB });
|
||
return;
|
||
}
|
||
if (n * m > MAX_REGION_CELLS || !hasCommonLine(cmpA, cmpB, loA, hiA, loB, hiB)) {
|
||
for (let i = loA; i < hiA; i++) out.push({ op: "del", ai: i, bi: loB });
|
||
for (let j = loB; j < hiB; j++) out.push({ op: "ins", ai: hiA, bi: j });
|
||
return;
|
||
}
|
||
lcsRegion(cmpA, cmpB, loA, hiA, loB, hiB, out);
|
||
}
|
||
|
||
function hasCommonLine(
|
||
cmpA: string[],
|
||
cmpB: string[],
|
||
loA: number,
|
||
hiA: number,
|
||
loB: number,
|
||
hiB: number
|
||
): boolean {
|
||
const set = new Set<string>();
|
||
for (let i = loA; i < hiA; i++) set.add(cmpA[i]);
|
||
for (let j = loB; j < hiB; j++) {
|
||
if (set.has(cmpB[j])) return true;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
/** 行级 LCS（规模已由调用方限制），供无锚点但有公共行的区间使用 */
|
||
function lcsRegion(
|
||
cmpA: string[],
|
||
cmpB: string[],
|
||
loA: number,
|
||
hiA: number,
|
||
loB: number,
|
||
hiB: number,
|
||
out: RawOp[]
|
||
): void {
|
||
const n = hiA - loA;
|
||
const m = hiB - loB;
|
||
const width = m + 1;
|
||
const dp = new Uint32Array((n + 1) * width);
|
||
for (let i = n - 1; i >= 0; i--) {
|
||
const aLine = cmpA[loA + i];
|
||
for (let j = m - 1; j >= 0; j--) {
|
||
dp[i * width + j] =
|
||
aLine === cmpB[loB + j]
|
||
? dp[(i + 1) * width + (j + 1)] + 1
|
||
: Math.max(dp[(i + 1) * width + j], dp[i * width + (j + 1)]);
|
||
}
|
||
}
|
||
let i = 0;
|
||
let j = 0;
|
||
while (i < n && j < m) {
|
||
if (cmpA[loA + i] === cmpB[loB + j]) {
|
||
out.push({ op: "equal", ai: loA + i, bi: loB + j });
|
||
i += 1;
|
||
j += 1;
|
||
} else if (dp[(i + 1) * width + j] >= dp[i * width + (j + 1)]) {
|
||
out.push({ op: "del", ai: loA + i, bi: loB + j });
|
||
i += 1;
|
||
} else {
|
||
out.push({ op: "ins", ai: loA + i, bi: loB + j });
|
||
j += 1;
|
||
}
|
||
}
|
||
while (i < n) {
|
||
out.push({ op: "del", ai: loA + i, bi: loB + j });
|
||
i += 1;
|
||
}
|
||
while (j < m) {
|
||
out.push({ op: "ins", ai: loA + i, bi: loB + j });
|
||
j += 1;
|
||
}
|
||
}
|
||
|
||
/* ---------------- 第三层：后处理（块构建 + 上下文折叠） ---------------- */
|
||
|
||
/**
|
||
* 把扁平 op 序列整理成块：
|
||
* - 连续 equal → equal 块（展示用旧文本原文）
|
||
* - 连续非 equal 合并为一个变更区域：del 按原顺序在前、ins 按新顺序在后，
|
||
* 两侧都有 → replace（后续做行内细分），单侧 → delete / insert。
|
||
* 这一步消除了 LCS 可能出现的 -/+ 交叉碎片（del,ins,del,ins → 一个 replace 块）。
|
||
*/
|
||
function buildBlocks(ops: RawOp[], rawA: string[], rawB: string[]): DiffBlock[] {
|
||
const blocks: DiffBlock[] = [];
|
||
let k = 0;
|
||
while (k < ops.length) {
|
||
if (ops[k].op === "equal") {
|
||
const lines: DiffLine[] = [];
|
||
while (k < ops.length && ops[k].op === "equal") {
|
||
lines.push({ op: "equal", text: rawA[ops[k].ai] });
|
||
k += 1;
|
||
}
|
||
blocks.push({ type: "equal", lines });
|
||
continue;
|
||
}
|
||
const dels: DiffLine[] = [];
|
||
const inss: DiffLine[] = [];
|
||
while (k < ops.length && ops[k].op !== "equal") {
|
||
const o = ops[k];
|
||
if (o.op === "del") dels.push({ op: "del", text: rawA[o.ai] });
|
||
else inss.push({ op: "ins", text: rawB[o.bi] });
|
||
k += 1;
|
||
}
|
||
const type: BlockType =
|
||
dels.length > 0 && inss.length > 0 ? "replace" : dels.length > 0 ? "delete" : "insert";
|
||
blocks.push({ type, lines: [...dels, ...inss] });
|
||
}
|
||
return blocks;
|
||
}
|
||
|
||
export type FoldedRow =
|
||
| { kind: "line"; op: LineOp; text: string; segments?: InlineSegment[] }
|
||
| { kind: "fold"; count: number };
|
||
|
||
/**
|
||
* 上下文折叠：超过 context*2+2 行的 equal 块只保留变更两侧各 context 行，
|
||
* 头/尾 equal 块只保留单侧；返回渲染用的行序列（fold 为折叠标记）。
|
||
*/
|
||
export function toFoldedRows(blocks: DiffBlock[], context = 3): FoldedRow[] {
|
||
const rows: FoldedRow[] = [];
|
||
const pushLine = (l: DiffLine) =>
|
||
rows.push({ kind: "line", op: l.op, text: l.text, segments: l.segments });
|
||
blocks.forEach((b, bi) => {
|
||
if (!(b.type === "equal" && b.lines.length > context * 2 + 2)) {
|
||
b.lines.forEach(pushLine);
|
||
return;
|
||
}
|
||
const isHead = bi === 0;
|
||
const isTail = bi === blocks.length - 1;
|
||
if (isHead && isTail) {
|
||
// 整个 diff 都是相同内容：不折叠
|
||
b.lines.forEach(pushLine);
|
||
return;
|
||
}
|
||
const head = isHead ? 0 : context;
|
||
const tail = isTail ? 0 : context;
|
||
for (let i = 0; i < head; i++) pushLine(b.lines[i]);
|
||
rows.push({ kind: "fold", count: b.lines.length - head - tail });
|
||
for (let i = b.lines.length - tail; i < b.lines.length; i++) pushLine(b.lines[i]);
|
||
});
|
||
return rows;
|
||
}
|
||
|
||
/* ---------------- 第四层：行内细分（词级 diff） ---------------- */
|
||
|
||
// CJK 逐字成 token（中文无词边界），西文按单词，空白连续，其余单字符
|
||
const TOKEN_RE = /[\p{Script=Han}\p{Script=Hiragana}\p{Script=Katakana}\p{Script=Hangul}]|[A-Za-z0-9_]+|\s+|[^\s]/gu;
|
||
|
||
interface Tokens {
|
||
tokens: string[];
|
||
starts: number[];
|
||
ends: number[];
|
||
}
|
||
|
||
function tokenize(line: string): Tokens {
|
||
const tokens: string[] = [];
|
||
const starts: number[] = [];
|
||
const ends: number[] = [];
|
||
for (const m of line.matchAll(TOKEN_RE)) {
|
||
const start = m.index;
|
||
if (start === undefined) continue;
|
||
tokens.push(m[0]);
|
||
starts.push(start);
|
||
ends.push(start + m[0].length);
|
||
}
|
||
return { tokens, starts, ends };
|
||
}
|
||
|
||
function lcsTokenLen(a: string[], b: string[]): number {
|
||
const n = a.length;
|
||
const m = b.length;
|
||
const width = m + 1;
|
||
const dp = new Uint32Array((n + 1) * width);
|
||
for (let i = n - 1; i >= 0; i--) {
|
||
for (let j = m - 1; j >= 0; j--) {
|
||
dp[i * width + j] =
|
||
a[i] === b[j]
|
||
? dp[(i + 1) * width + (j + 1)] + 1
|
||
: Math.max(dp[(i + 1) * width + j], dp[i * width + (j + 1)]);
|
||
}
|
||
}
|
||
return dp[0];
|
||
}
|
||
|
||
/** X 视角下的变更片段：词级 LCS 中未被匹配的连续 token 合并为一个字符区间 */
|
||
function changedSegments(
|
||
t: Tokens,
|
||
ops: Array<{ op: "equal" | "chg"; idx: number }>,
|
||
type: "del" | "ins"
|
||
): InlineSegment[] {
|
||
const segs: InlineSegment[] = [];
|
||
let cur: InlineSegment | null = null;
|
||
for (const o of ops) {
|
||
if (o.op === "equal") {
|
||
cur = null;
|
||
continue;
|
||
}
|
||
const start = t.starts[o.idx];
|
||
const end = t.ends[o.idx];
|
||
if (cur && cur.end === start) {
|
||
cur.end = end;
|
||
} else {
|
||
cur = { start, end, type };
|
||
segs.push(cur);
|
||
}
|
||
}
|
||
return segs;
|
||
}
|
||
|
||
/** 词级 LCS 回溯，产出 X/Y 各自的 equal/chg 序列（idx 为各自 token 下标） */
|
||
function tokenOps(x: Tokens, y: Tokens): {
|
||
xOps: Array<{ op: "equal" | "chg"; idx: number }>;
|
||
yOps: Array<{ op: "equal" | "chg"; idx: number }>;
|
||
} {
|
||
const n = x.tokens.length;
|
||
const m = y.tokens.length;
|
||
const width = m + 1;
|
||
const dp = new Uint32Array((n + 1) * width);
|
||
for (let i = n - 1; i >= 0; i--) {
|
||
for (let j = m - 1; j >= 0; j--) {
|
||
dp[i * width + j] =
|
||
x.tokens[i] === y.tokens[j]
|
||
? dp[(i + 1) * width + (j + 1)] + 1
|
||
: Math.max(dp[(i + 1) * width + j], dp[i * width + (j + 1)]);
|
||
}
|
||
}
|
||
const xOps: Array<{ op: "equal" | "chg"; idx: number }> = [];
|
||
const yOps: Array<{ op: "equal" | "chg"; idx: number }> = [];
|
||
let i = 0;
|
||
let j = 0;
|
||
while (i < n && j < m) {
|
||
if (x.tokens[i] === y.tokens[j]) {
|
||
xOps.push({ op: "equal", idx: i });
|
||
yOps.push({ op: "equal", idx: j });
|
||
i += 1;
|
||
j += 1;
|
||
} else if (dp[(i + 1) * width + j] >= dp[i * width + (j + 1)]) {
|
||
xOps.push({ op: "chg", idx: i });
|
||
i += 1;
|
||
} else {
|
||
yOps.push({ op: "chg", idx: j });
|
||
j += 1;
|
||
}
|
||
}
|
||
while (i < n) {
|
||
xOps.push({ op: "chg", idx: i });
|
||
i += 1;
|
||
}
|
||
while (j < m) {
|
||
yOps.push({ op: "chg", idx: j });
|
||
j += 1;
|
||
}
|
||
return { xOps, yOps };
|
||
}
|
||
|
||
/** 对 replace 块内按下标配对的行对做词级细分；相似度不足则整行变更、不产出 segments */
|
||
function annotateInline(blocks: DiffBlock[], inlineThreshold: number): void {
|
||
for (const b of blocks) {
|
||
if (b.type !== "replace") continue;
|
||
const dels = b.lines.filter((l) => l.op === "del");
|
||
const inss = b.lines.filter((l) => l.op === "ins");
|
||
const n = Math.min(dels.length, inss.length);
|
||
for (let i = 0; i < n; i++) {
|
||
const delLine = dels[i];
|
||
const insLine = inss[i];
|
||
if (delLine.text.length + insLine.text.length > MAX_INLINE_CHARS) continue;
|
||
const x = tokenize(delLine.text);
|
||
const y = tokenize(insLine.text);
|
||
if (x.tokens.length === 0 || y.tokens.length === 0) continue;
|
||
if (x.tokens.length * y.tokens.length > MAX_INLINE_CELLS) continue;
|
||
const ratio = (2 * lcsTokenLen(x.tokens, y.tokens)) / (x.tokens.length + y.tokens.length);
|
||
if (!(ratio > inlineThreshold)) continue;
|
||
const { xOps, yOps } = tokenOps(x, y);
|
||
const delSegs = changedSegments(x, xOps, "del");
|
||
const insSegs = changedSegments(y, yOps, "ins");
|
||
if (delSegs.length > 0) delLine.segments = delSegs;
|
||
if (insSegs.length > 0) insLine.segments = insSegs;
|
||
}
|
||
}
|
||
}
|
||
|
||
/* ---------------- 入口 ---------------- */
|
||
|
||
export function smartDiff(
|
||
oldText: string,
|
||
newText: string,
|
||
options: SmartDiffOptions = {}
|
||
): DiffResult {
|
||
const replaceThreshold = options.replaceThreshold ?? 0.2;
|
||
const inlineThreshold = options.inlineThreshold ?? 0.6;
|
||
const a = splitLines(oldText);
|
||
const b = splitLines(newText);
|
||
|
||
const ops: RawOp[] = [];
|
||
let wholeReplace = false;
|
||
if (a.cmp.length === 0 && b.cmp.length === 0) {
|
||
// 两侧皆空：无块
|
||
} else if (a.cmp.length === 0 || b.cmp.length === 0) {
|
||
// 单侧为空：整体删除/新增
|
||
if (a.cmp.length > 0) {
|
||
for (let i = 0; i < a.cmp.length; i++) ops.push({ op: "del", ai: i, bi: 0 });
|
||
} else {
|
||
for (let j = 0; j < b.cmp.length; j++) ops.push({ op: "ins", ai: 0, bi: j });
|
||
}
|
||
} else if (
|
||
a.cmp.length >= 2 &&
|
||
b.cmp.length >= 2 &&
|
||
lineSimilarity(a.cmp, b.cmp) < replaceThreshold
|
||
) {
|
||
// 整段替换：跳过逐行对齐，输出一个大删除块 + 一个大新增块
|
||
wholeReplace = true;
|
||
for (let i = 0; i < a.cmp.length; i++) ops.push({ op: "del", ai: i, bi: 0 });
|
||
for (let j = 0; j < b.cmp.length; j++) ops.push({ op: "ins", ai: 0, bi: j });
|
||
} else {
|
||
patienceDiff(a.cmp, b.cmp, 0, a.cmp.length, 0, b.cmp.length, ops, 0);
|
||
}
|
||
|
||
const blocks = buildBlocks(ops, a.raw, b.raw);
|
||
if (wholeReplace) {
|
||
// 相似度低于阈值判定为整段替换：唯一变更块标记为 block-replace，
|
||
// 不做行内细分（两侧内容无对应关系，细对齐只会产出噪音）
|
||
const blk = blocks.find((x) => x.type === "replace");
|
||
if (blk) blk.type = "block-replace";
|
||
}
|
||
annotateInline(blocks, inlineThreshold);
|
||
|
||
let dels = 0;
|
||
let adds = 0;
|
||
for (const blk of blocks) {
|
||
for (const l of blk.lines) {
|
||
if (l.op === "del") dels += 1;
|
||
else if (l.op === "ins") adds += 1;
|
||
}
|
||
}
|
||
return { blocks, stats: { adds, dels } };
|
||
}
|