std/src/text/diff.nv - main - nv-lang/nova

std/src/text/diff.nv
90 строк2 KB
Evgeniy Golovin
merge: comment-hygiene-2 — чистка комментариев std (batch 1-20) + линт-свип 330→13
01 авг 2026, 18:13
01 авг 2026, 18:13bb8b33d
// stdlib/diff.nv — Myers diff algorithm для двух массивов строк.
// http://www.xmailserver.org/diff2.pdf
//
// API:
//   Diff.compute(a []str, b []str) -> []DiffOp
//   DiffOp = Equal(str) | Insert(str) | Delete(str)

module text.diff

/// Diff operation on one element: Equal (same), Insert (only in b), Delete (only in a).
#stable(since = "0.1")
export type DiffOp enum
    | Equal(str)
    | Insert(str)
    | Delete(str)

/// Compute LCS-based diff between two `[]str`. O(NM) memory + time.
///
/// Used for CI snapshot tests (rejected, accepted, etc.).
///
/// # Examples
/// ```nova
/// let ops = Diff.compute(["a", "c"], ["a", "b", "c"])
/// // ops contains Insert("b") in the middle
/// ```
#stable(since = "0.1")
export fn Diff.compute(a []str, b []str) -> []DiffOp {
    // Вычисляем LCS таблицу
    ro n = a.len()
    ro m = b.len()
    mut lcs [][]int = []
    for i in 0..=n {
        mut row []int = []
        for j in 0..=m { row.push(0) }
        lcs.push(row)
    }

    // Заполняем DP-таблицу
    for ii in 1..=n {
        for jj in 1..=m {
            if a[ii - 1] == b[jj - 1] {
                lcs[ii][jj] = lcs[ii - 1][jj - 1] + 1
            } else {
                ro up = lcs[ii - 1][jj]
                ro left = lcs[ii][jj - 1]
                lcs[ii][jj] = up.max(left)
            }
        }
    }

    // Backtrack
    mut ops_rev []DiffOp = []
    mut x = n
    mut y = m
    while x > 0 || y > 0 {
        if x > 0 && y > 0 && a[x - 1] == b[y - 1] {
            ops_rev.push(Equal(a[x - 1]))
            x -= 1
            y -= 1
        } else if y > 0 && (x == 0 || lcs[x][y - 1] >= lcs[x - 1][y]) {
            ops_rev.push(Insert(b[y - 1]))
            y -= 1
        } else {
            ops_rev.push(Delete(a[x - 1]))
            x -= 1
        }
    }

    // Reverse in place (не поэлементная копия).
    ops_rev.reverse()
    ops_rev
}

/// Pretty-print: `+` for Insert, `-` for Delete, ` ` for Equal. Newline-separated.
#stable(since = "0.1")
export fn Diff.format(ops []DiffOp) -> str {
    consume buf = StringBuilder.new()
    for op in ops {
        match op {
            Equal(s) => { buf.append(' '); buf.append(s) }
            Insert(s) => { buf.append('+'); buf.append(s) }
            Delete(s) => { buf.append('-'); buf.append(s) }
        }
        buf.append('\n')
    }
    ro result = buf.into_str()
    result
}

// Тесты — см. peer-файл diff_test.nv (module text.diff_test).