A lib diff — Algoritmo LCS, Distância de Edição, Unified Diff e Patches

21.1. Por que existe a lib diff? (O problema real e a filosofia Ridgun)

«Por que preciso de uma lib diff escrita de raiz em Ridgun puro em vez de ligar uma biblioteca C tradicional?»

Essa é a primeira pergunta que qualquer engenheiro de sistemas faz ao chegar à diff. E a resposta resume toda a filosofia do ridgun-libs:

Sejamos sinceros: quando um teste falha ou um ficheiro de configuração muda, um seco "expected A, got B" de 200 linhas obriga-o a queimar as pestanas à procura da linha exata que mudou.

A lib diff calcula a Subsequência Comum Mais Longa (LCS) sobre Tensor[Int] 2D para produzir edições mínimas (DiffKeep, DiffAdd, DiffDel), distância de edição, estatísticas, formato Unified Diff (---/+++/@@) e reconstrução exata com diff apply.

Num ecossistema tradicional, resolver as tarefas do domínio DIFF implica arrastar dependências externas em C, lidar com ponteiros brutos, conversões opacas de tipos, exceções não verificadas ou pausas imprevisíveis do coletor de lixo. Em Ridgun, a lib diff (src/main/ridgun/lib/diff.rg) aborda o problema com quatro princípios inegociáveis:

1. Declare import diff (ou import diff as alias) no início do ficheiro: cada lib define o seu espaço de nomes module :: diff e em modo --strict as funções multi-palavra são sempre invocadas com espaços naturais.
2. Encadeie os seus pipelines da esquerda para a direita com ->: escreva entrada passo um -> passo dois -> resultado, use máscaras (+ _ _ +) para desestruturar sequências e omita _ = em instruções sequenciais (ou descarte com -> ()).
3. Recursão de cauda com TCO (Tail-Call Optimization): todas as travessias internas da diff são compiladas para ciclos nativos em espaço de pilha $O(1)$.
4. Memória determinística (RMM1 / RMM2): cada estrutura intermédia é libertada no instante exato em que termina a sua última leitura, sem Garbage Collector.

---

21.2. Artefactos nativos, importação e catálogo completo da API de diff

No ridgun-libs, diff é uma lib de primeira classe localizada em src/main/ridgun/lib/diff.rg (domínio DIFF). Ao compilar com stable bundle, é empacotada em três formatos nativos:

Artefacto	Caminho	Finalidade
Bundle Ridgun	target/bundles/diff.rglib	Distribuição e importação direta com import diff
Ficheiro compilado	target/diff.rgc	Artefacto intermédio verificado pelo ridgunc
Objeto partilhado ELF64	target/libdiff.so	Biblioteca dinâmica nativa sem dependências de C nem libc

Cada lib declara o seu próprio espaço de nomes com module :: diff: basta escrever import diff (ou import diff as alias) no topo e invocar as suas funções com espaços naturais (minha funcao x) e pipelines -> (x minha funcao -> resultado).

21.2.1. Resumo das famílias funcionais da diff

Assinatura / Função / Tipo	O que faz e quando usar
type DiffOp	`DiffKeep String
diff lines / diff text	Calcula o script mínimo de edição LCS entre listas [String] ou textos multilinha
diff edit distance / diff stats	Distância mínima de inserção+remoção e contagem (kept, added, deleted)
diff format / diff unified	Formata linhas compactas + / - / ou Unified Diff padrão com cabeçalhos
diff apply / diff apply text	Reconstrói o documento de destino sem perdas a partir de um script de edição

21.2.2. Catálogo exaustivo de tipos e assinaturas em src/main/ridgun/lib/diff.rg

Abaixo encontra-se o inventário completo de tipos algébricos (type), operadores (op ::) e assinaturas de funções (fn ::) definidos em src/main/ridgun/lib/diff.rg (2 tipos, 0 operadores e 33 funções):

Tipos algébricos e registos (type) da diff:

type DiffEdit = diff_op: String, line_text: String, old_line_no: Int, new_line_no: Int
type DiffStats = equal_count: Int, insert_count: Int, delete_count: Int

#	Função / Assinatura (fn ::)	Tipo de Retorno
1	fn :: df max Int Int	Int
2	fn :: df int to str pos Int	String
3	fn :: df int to str Int	String
4	fn :: df rev [String] [String]	[String]
5	fn :: df rev ints [Int] [Int]	[Int]
6	fn :: df split lines loop String Int Int Int [String]	[String]
7	fn :: df split lines String	[String]
8	fn :: df zeros Int [Int]	[Int]
9	fn :: df nth int [Int] Int	Int
10	fn :: df head int [Int]	Int
11	fn :: df cell val String String Int Int Int	Int
12	fn :: df build row String [String] [Int] Int [Int]	[Int]
13	fn :: df build dp [String] [String] [[Int]]	[[Int]]
14	fn :: df tail rows [[Int]]	[[Int]]
15	fn :: df head row [[Int]]	[Int]
16	fn :: df rev edits [DiffEdit] [DiffEdit]	[DiffEdit]
17	fn :: df backtrack [String] [String] [[Int]] Int Int Int [DiffEdit]	[DiffEdit]
18	fn :: df backtrack step String [String] String [String] [[Int]] Int Int Int [DiffEdit]	[DiffEdit]
19	fn :: df backtrack branch String [String] String [String] [[Int]] [[Int]] Int Int Int Int Int [DiffEdit]	[DiffEdit]
20	fn :: df list length [String]	Int
21	fn :: diff lines [String] [String]	[DiffEdit]
22	fn :: diff text String String	[DiffEdit]
23	fn :: df stats loop [DiffEdit] Int Int Int	DiffStats
24	fn :: diff stats [DiffEdit]	DiffStats
25	fn :: diff edit distance String String	Int
26	fn :: diff has changes [DiffEdit]	Bool
27	fn :: df format unified lines [DiffEdit] String	String
28	fn :: df hunk start Int	Int
29	fn :: df unified header String String Int Int	String
30	fn :: diff unified String String String String	String
31	fn :: df apply collect [DiffEdit] [String]	[String]
32	fn :: df join lines [String]	String
33	fn :: diff apply [DiffEdit]	String

---

21.3. Explorando a diff a fundo: Exemplos passo a passo de cada funcionalidade

Não basta ver a tabela de assinaturas: vamos explorar cada uma das funcionalidades da lib diff através de exemplos progressivos e executáveis em Ridgun. Começaremos pelas duas receitas tabulares de uso diário e depois percorreremos em detalhe todos os cenários funcionais, transformações e casos de fronteira verificados em src/test/ridgun/test diff.rg.

21.3.1. Exemplo 1: Fluxo principal em estilo tabular com diff

Repare como em Ridgun os sinais = e os passos de transformação com diff ficam alinhados como uma tabela limpa, sem variáveis mutáveis desnecessárias nem efeitos colaterais ocultos:

import diff

fn :: auditar cambio String String => Int String
      auditar cambio antes despues =
        diff edit distance antes despues -> dist
        diff unified antes despues "config.old" "config.new" -> parche
        (dist, parche)

21.3.2. Exemplo 2: Composição segura e tratamento de casos de fronteira

Todas as funções da lib diff foram desenhadas para se comporem com guardas booleanas | e com as restantes 32 libs do ridgun-libs:

import diff

fn :: verificar parche String [DiffEdit] => String
      verificar parche orig ops =
        diff apply orig ops

21.3.3. Exemplo 3: Comparação de textos vazios e idênticos: distância de edição zero e verificação de invariantes

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff empty and identical => ()
      test diff empty and identical =
        nl = char from code 10
        e_empty = diff text "" ""
        assert int equals (count edits e_empty) 0 "AC1: empty diff edit count"
        assert false (diff has changes e_empty) "AC1: empty diff has no changes"
        assert int equals (diff edit distance "" "") 0 "AC1: empty edit distance"
        assert str eq (diff apply e_empty) "" "AC3: empty diff apply"
        same_doc = "alpha" + nl + "beta" + nl + "gamma"
        e_same = diff text same_doc same_doc
        assert int equals (count edits e_same) 3 "AC1: identical 3-line count"
        assert false (diff has changes e_same) "AC1: identical has no changes"
        st_same = diff stats e_same
        assert int equals (equal_count st_same) 3 "AC1: equal_count == 3"
        assert int equals (insert_count st_same) 0 "AC1: insert_count == 0"
        assert int equals (delete_count st_same) 0 "AC1: delete_count == 0"
        assert int equals (diff edit distance same_doc same_doc) 0 "AC1: identical edit distance == 0"
        assert str eq (diff apply e_same) same_doc "AC3: identical diff apply"
        ()

21.3.4. Exemplo 4: Inserções puras (DiffInsert), remoções puras (DiffDelete) e aplicação direta (diff patch)

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff pure insert and delete => ()
      test diff pure insert and delete =
        nl = char from code 10
        target = "line1" + nl + "line2" + nl + "line3"
        e_ins = diff text "" target
        assert true (diff has changes e_ins) "AC1: pure insert has changes"
        st_ins = diff stats e_ins
        assert int equals (equal_count st_ins) 0 "AC1: pure insert equal_count"
        assert int equals (insert_count st_ins) 3 "AC1: pure insert insert_count"
        assert int equals (delete_count st_ins) 0 "AC1: pure insert delete_count"
        assert int equals (diff edit distance "" target) 3 "AC1: pure insert edit distance"
        assert str eq (diff apply e_ins) target "AC3: pure insert apply"
        ins0 = nth edit e_ins 0
        ins2 = nth edit e_ins 2
        assert str eq (diff_op ins0) "insert" "AC1: ins0 op"
        assert int equals (old_line_no ins0) 0 "AC1: ins0 old_line_no"
        assert int equals (new_line_no ins0) 1 "AC1: ins0 new_line_no"
        assert int equals (new_line_no ins2) 3 "AC1: ins2 new_line_no"
        e_del = diff text target ""
        assert true (diff has changes e_del) "AC1: pure delete has changes"
        st_del = diff stats e_del
        assert int equals (equal_count st_del) 0 "AC1: pure delete equal_count"
        assert int equals (insert_count st_del) 0 "AC1: pure delete insert_count"
        assert int equals (delete_count st_del) 3 "AC1: pure delete delete_count"
        assert int equals (diff edit distance target "") 3 "AC1: pure delete edit distance"
        assert str eq (diff apply e_del) "" "AC3: pure delete apply"
        del0 = nth edit e_del 0
        del2 = nth edit e_del 2
        assert str eq (diff_op del0) "delete" "AC1: del0 op"
        assert int equals (old_line_no del0) 1 "AC1: del0 old_line_no"
        assert int equals (new_line_no del0) 0 "AC1: del0 new_line_no"
        assert int equals (old_line_no del2) 3 "AC1: del2 old_line_no"
        ()

21.3.5. Exemplo 5: O vetor clássico de Eugene Myers (ABCABBA $\rightarrow$ CBABAC): maior subsequência comum (LCS) e distância mínima

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff myers classic vector => ()
      test diff myers classic vector =
        nl = char from code 10
        old_lines = ["A", "B", "C", "A", "B", "B", "A"]
        new_lines = ["C", "B", "A", "B", "A", "C"]
        edits = diff lines old_lines new_lines
        st = diff stats edits
        assert int equals (equal_count st) 4 "AC1: Myers LCS length 4"
        assert int equals (delete_count st) 3 "AC1: Myers delete count 3"
        assert int equals (insert_count st) 2 "AC1: Myers insert count 2"
        old_s = "A" + nl + "B" + nl + "C" + nl + "A" + nl + "B" + nl + "B" + nl + "A"
        new_s = "C" + nl + "B" + nl + "A" + nl + "B" + nl + "A" + nl + "C"
        assert int equals (diff edit distance old_s new_s) 5 "AC1: Myers edit distance 5"
        assert str eq (diff apply edits) new_s "AC3: Myers apply reproduces CBABAC"
        ()

21.3.6. Exemplo 6: Inspeção de números de linha de origem e destino (diff old line, diff new line) e reconstrução exata com diff patch

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff code hunks and line numbers => ()
      test diff code hunks and line numbers =
        nl = char from code 10
        old_code = "fn :: add Int Int => Int" + nl + "      add a b = a + b" + nl + "" + nl + "fn :: sub Int Int => Int" + nl + "      sub a b = a - b"
        new_code = "fn :: add Int Int => Int" + nl + "      add x y = x + y" + nl + "" + nl + "fn :: mul Int Int => Int" + nl + "      mul a b = a * b" + nl + "" + nl + "fn :: sub Int Int => Int" + nl + "      sub a b = a - b"
        edits = diff text old_code new_code
        assert true (diff has changes edits) "AC1: code refactoring has changes"
        assert str eq (diff apply edits) new_code "AC3: code refactoring lossless apply"
        e0 = nth edit edits 0
        assert str eq (diff_op e0) "equal" "AC1: line 1 equal"
        assert int equals (old_line_no e0) 1 "AC1: line 1 old_line_no"
        assert int equals (new_line_no e0) 1 "AC1: line 1 new_line_no"
        e1 = nth edit edits 1
        assert str eq (diff_op e1) "delete" "AC1: line 2 deleted"
        assert str eq (line_text e1) "      add a b = a + b" "AC1: deleted line text"
        assert int equals (old_line_no e1) 2 "AC1: deleted old_line_no"
        assert int equals (new_line_no e1) 0 "AC1: deleted new_line_no"
        e2 = nth edit edits 2
        assert str eq (diff_op e2) "insert" "AC1: line 2 inserted"
        assert str eq (line_text e2) "      add x y = x + y" "AC1: inserted line text"
        assert int equals (old_line_no e2) 0 "AC1: inserted old_line_no"
        assert int equals (new_line_no e2) 2 "AC1: inserted new_line_no"
        ()

21.3.7. Exemplo 7: Geração de patches unificados estilo GNU (--- old, +++ new, -, +, ) com diff unified e estatísticas (kept, deleted, inserted)

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff unified formatting => ()
      test diff unified formatting =
        nl = char from code 10
        old_s = "one" + nl + "two" + nl + "three"
        new_s = "one" + nl + "TWO" + nl + "three" + nl + "four"
        uni = diff unified "a/sample.txt" "b/sample.txt" old_s new_s
        expected = "--- a/sample.txt" + nl + "+++ b/sample.txt" + nl + "@@ -1,3 +1,4 @@" + nl + " one" + nl + "-two" + nl + "+TWO" + nl + " three" + nl + "+four" + nl
        assert str eq uni expected "AC2: unified diff output matches standard header and hunk format"
        uni_empty = diff unified "a/empty" "b/empty" "" ""
        assert str eq uni_empty ("--- a/empty" + nl + "+++ b/empty" + nl + "@@ -0,0 +0,0 @@" + nl) "AC2: unified diff empty files"
        ()

21.3.8. Exemplo 8: Robustez perante ficheiros com linhas repetidas e blocos duplicados

Neste exemplo prático exploramos de forma exaustiva como a diff se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test diff repetitive lines => ()
      test diff repetitive lines =
        nl = char from code 10
        old_rep = "x" + nl + "x" + nl + "y" + nl + "x" + nl + "x"
        new_rep = "x" + nl + "y" + nl + "y" + nl + "x"
        edits = diff text old_rep new_rep
        st = diff stats edits
        assert int equals (equal_count st) 3 "AC1: repetitive LCS equal_count"
        assert int equals (delete_count st) 2 "AC1: repetitive LCS delete_count"
        assert int equals (insert_count st) 1 "AC1: repetitive LCS insert_count"
        assert str eq (diff apply edits) new_rep "AC3: repetitive lines apply"
        ()

---

21.4. Debaixo do capô: como a diff é construída em Ridgun puro (src/main/ridgun/lib/diff.rg)

Uma das maiores vantagens do ridgun-libs é que não existem caixas-pretas em C. Pode abrir src/main/ridgun/lib/diff.rg e ler exatamente como cada operação é implementada usando pattern matching, árvores de guardas | / |. e recursão de cauda (TCO). Vejamos as peças-chave da sua implementação real:

21.4.1. Implementação interna: Internal Helpers

Observe como diff.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

module :: diff

fn :: df max Int Int => Int
      df max a b =
        | a >= b = a
        | otherwise = b

fn :: df int to str pos Int => String
      df int to str pos n =
        | n == 0 = ""
        | otherwise = (df int to str pos (n / 10)) + (char from code ((n % 10) + 48))

fn :: df int to str Int => String
      df int to str n =
        | n == 0 = "0"
        | n < 0 = "-" + (df int to str pos (0 - n))
        | otherwise = df int to str pos n

fn :: df rev [String] [String] => [String]
      df rev [] acc = acc
      df rev (x:xs) acc = df rev xs ([x] :: acc)

fn :: df rev ints [Int] [Int] => [Int]
      df rev ints [] acc = acc
      df rev ints (x:xs) acc = df rev ints xs ([x] :: acc)

fn :: df split lines loop String Int Int Int [String] => [String]
      df split lines loop s idx n start acc =
        | idx >= n = df rev ([str slice s start n] :: acc) []
        | (str char at s idx) == 10 = df split lines loop s (idx + 1) n (idx + 1) ([str slice s start idx] :: acc)
        | otherwise = df split lines loop s (idx + 1) n start acc

fn :: df split lines String => [String]
      df split lines s =
        | (str len s) == 0 = []
        | otherwise = df split lines loop s 0 (str len s) 0 []

fn :: df zeros Int [Int] => [Int]
      df zeros n acc =
        | n <= 0 = acc
        | otherwise = df zeros (n - 1) ([0] :: acc)

fn :: df nth int [Int] Int => Int
      df nth int [] _ = 0
      df nth int (x:xs) idx =
        | idx <= 0 = x
        | otherwise = df nth int xs (idx - 1)

fn :: df head int [Int] => Int
      df head int [] = 0
      df head int (x:_) = x

fn :: df cell val String String Int Int Int => Int
      df cell val old_line b diag down right_val =
        | old_line == b = diag + 1
        | otherwise = df max down right_val

fn :: df build row String [String] [Int] Int [Int] => [Int]
      df build row _ [] _ _ acc = acc
      df build row old_line (b:bs) (diag:next_rest) right_val acc =
        cell = df cell val old_line b diag (df head int next_rest) right_val
        df build row old_line bs next_rest cell ([cell] :: acc)
      df build row _ (_:_) [] _ acc = acc

fn :: df build dp [String] [String] [[Int]] => [[Int]]
      df build dp [] _ rows = rows
      df build dp (a:as) rev_new (next_row:rest_rows) =
        next_rev = df rev ints next_row []
        curr_row = df build row a rev_new next_rev 0 [0]
        df build dp as rev_new ([curr_row, next_row] :: rest_rows)
      df build dp (_:_) _ [] = []

fn :: df tail rows [[Int]] => [[Int]]
      df tail rows [] = []
      df tail rows (_:rs) = rs

fn :: df head row [[Int]] => [Int]
      df head row [] = []
      df head row (r:_) = r

fn :: df rev edits [DiffEdit] [DiffEdit] => [DiffEdit]
      df rev edits [] acc = acc
      df rev edits (e:es) acc = df rev edits es ([e] :: acc)

fn :: df backtrack [String] [String] [[Int]] Int Int Int [DiffEdit] => [DiffEdit]
      df backtrack [] [] _ _ _ _ acc = df rev edits acc []
      df backtrack [] (b:bs) rows j old_no new_no acc =
        ed = DiffEdit "insert" b 0 new_no
        df backtrack [] bs rows (j + 1) old_no (new_no + 1) ([ed] :: acc)
      df backtrack (a:as) [] rows j old_no new_no acc =
        ed = DiffEdit "delete" a old_no 0
        df backtrack as [] (df tail rows rows) j (old_no + 1) new_no ([ed] :: acc)
      df backtrack (a:as) (b:bs) rows j old_no new_no acc =
        df backtrack step a as b bs rows j old_no new_no acc

fn :: df backtrack step String [String] String [String] [[Int]] Int Int Int [DiffEdit] => [DiffEdit]
      df backtrack step a as b bs rows j old_no new_no acc =
        | a == b =
          df backtrack as bs (df tail rows rows) (j + 1) (old_no + 1) (new_no + 1) ([DiffEdit "equal" a old_no new_no] :: acc)
        | otherwise =
          df backtrack branch a as b bs rows (df tail rows rows) j old_no new_no (df nth int (df head row (df tail rows rows)) j) (df nth int (df head row rows) (j + 1)) acc

fn :: df backtrack branch String [String] String [String] [[Int]] [[Int]] Int Int Int Int Int [DiffEdit] => [DiffEdit]
      df backtrack branch a as b bs rows next_rows j old_no new_no del_score ins_score acc =
        | del_score >= ins_score =
          df backtrack as ([b] :: bs) next_rows j (old_no + 1) new_no ([DiffEdit "delete" a old_no 0] :: acc)
        | otherwise =
          df backtrack ([a] :: as) bs rows (j + 1) old_no (new_no + 1) ([DiffEdit "insert" b 0 new_no] :: acc)

fn :: df list length [String] => Int
      df list length [] = 0
      df list length (_:xs) = 1 + (df list length xs)

21.4.2. Implementação interna: Public API

Observe como diff.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

fn :: diff lines [String] [String] => [DiffEdit]
      diff lines old_lines new_lines =
        old_lines df rev [] -> rev_old
        new_lines df rev [] -> rev_new
        df zeros ((df list length new_lines) + 1) [] -> zero_row
        df build dp rev_old rev_new [zero_row] -> dp_rows
        df backtrack old_lines new_lines dp_rows 0 1 1 []

fn :: diff text String String => [DiffEdit]
      diff text old_s new_s = diff lines (df split lines old_s) (df split lines new_s)

fn :: df stats loop [DiffEdit] Int Int Int => DiffStats
      df stats loop [] eq ins del = DiffStats eq ins del
      df stats loop (e:es) eq ins del =
        | (diff_op e) == "equal" = df stats loop es (eq + 1) ins del
        | (diff_op e) == "insert" = df stats loop es eq (ins + 1) del
        | otherwise = df stats loop es eq ins (del + 1)

fn :: diff stats [DiffEdit] => DiffStats
      diff stats edits = df stats loop edits 0 0 0

fn :: diff edit distance String String => Int
      diff edit distance old_s new_s =
        diff text old_s new_s -> diff stats -> st
        (insert_count st) + (delete_count st)

fn :: diff has changes [DiffEdit] => Bool
      diff has changes [] = False
      diff has changes (e:es) =
        | (diff_op e) == "equal" = diff has changes es
        | otherwise = True

fn :: df format unified lines [DiffEdit] String => String
      df format unified lines [] acc = acc
      df format unified lines (e:es) acc =
        | (diff_op e) == "equal" = df format unified lines es (acc + " " + (line_text e) + (char from code 10))
        | (diff_op e) == "delete" = df format unified lines es (acc + "-" + (line_text e) + (char from code 10))
        | otherwise = df format unified lines es (acc + "+" + (line_text e) + (char from code 10))

fn :: df hunk start Int => Int
      df hunk start cnt =
        | cnt == 0 = 0
        | otherwise = 1

fn :: df unified header String String Int Int => String
      df unified header old_label new_label old_cnt new_cnt =
        old_cnt df hunk start -> old_start
        new_cnt df hunk start -> new_start
        char from code 10 -> nl
        "--- " + old_label + nl + "+++ " + new_label + nl + "@@ -" + (df int to str old_start) + "," + (df int to str old_cnt) + " +" + (df int to str new_start) + "," + (df int to str new_cnt) + " @@" + nl

fn :: diff unified String String String String => String
      diff unified old_label new_label old_s new_s =
        diff text old_s new_s -> edits
        edits diff stats -> st
        (equal_count st) + (delete_count st) -> old_cnt
        (equal_count st) + (insert_count st) -> new_cnt
        df unified header old_label new_label old_cnt new_cnt -> hdr
        df format unified lines edits hdr

fn :: df apply collect [DiffEdit] [String] => [String]
      df apply collect [] acc = df rev acc []
      df apply collect (e:es) acc =
        | (diff_op e) == "delete" = df apply collect es acc
        | otherwise = df apply collect es ([line_text e] :: acc)

fn :: df join lines [String] => String
      df join lines [] = ""
      df join lines (x:[]) = x
      df join lines (x:xs) = x + (char from code 10) + (df join lines xs)

fn :: diff apply [DiffEdit] => String
      diff apply edits = df join lines (df apply collect edits [])

---

21.5. Garantias algorítmicas, memória RMM1/RMM2 e as 5 Regras de Ouro da diff

• Garantia algorítmica e de segurança: Identidade matemática garantida $diff_edit_distance(a, b) == |a| + |b| - 2 \cdot LCS(a, b)$ e reconstrução sem perdas diff apply (diff lines a b) == b.
• Complexidade de pilha $O(1)$ com TCO: Todos os ciclos recursivos em src/main/ridgun/lib/diff.rg estão em posição de cauda, pelo que o ridgunc os compila para saltos nativos sem crescimento de pilha.
• Memória determinística (RMM1/RMM2): Zero pausas de coletor de lixo; todas as estruturas intermédias são libertadas de forma determinística à saída do escopo.
• Verificação contínua: Testada exaustivamente com stable check e pela suite automatizada src/test/ridgun/test diff.rg.

As 5 Regras de Ouro ao programar com a diff

1. Declare import diff no início do ficheiro e aproveite a equivalência entre espaços e underscores para que o seu código se leia como prosa.
2. Alinhe os seus pipelines de dados com =: encadeie as chamadas à diff em passos nomeados e deixe o stable format alinhar as colunas.
3. Aproveite as funções totais da diff nas suas guardas |: verifique os valores de retorno ou desempacote os ADTs com pattern matching em vez de assumir que a entrada externa é sempre válida.
4. Evite copiar grandes estruturas se só precisa de consultar um campo: lembre-se de que no RMM2 os argumentos de entrada não incrementam nem decrementam contadores (+0 / -0).
5. Combine a diff com test (import test): escreva sempre asserções com assert equals ou assert true para fixar os invariantes do seu domínio.

---

No Capítulo 22 passaremos a explorar em profundidade a lib template (A lib template — Templates Mustache Seguros com Auto-Escape HTML e LaTeX).