Comparar arquivos e identificar diferencas e uma operacao fundamental no desenvolvimento de software. O comando diff do Unix e a base de sistemas de controle de versao como Git, code review e ferramentas de merge. Neste projeto, vamos construir uma ferramenta de diff completa em Rust, implementando o algoritmo de Myers — o mesmo algoritmo usado pelo git diff — que encontra a menor sequencia de edicoes para transformar um arquivo em outro.
Ao construir esta ferramenta, voce aprendera sobre algoritmos de programacao dinamica, manipulacao avancada de strings e slices, e formatacao de saida para o terminal. O resultado e uma ferramenta que pode usar no dia a dia para comparar arquivos diretamente do terminal.
O Que Vamos Construir
Nossa ferramenta rdiff tera os seguintes recursos:
- Algoritmo de Myers para calculo do diff minimo
- Saida colorida com linhas adicionadas (verde) e removidas (vermelho)
- Formato unified diff compativel com
patch - Numeracao de linhas para ambos os arquivos
- Modo side-by-side (lado a lado)
- Estatisticas de alteracoes (linhas adicionadas, removidas, inalteradas)
- Suporte a comparacao de stdin com arquivo
Estrutura do Projeto
rdiff/
├── Cargo.toml
└── src/
├── main.rs
├── myers.rs
├── formatador.rs
└── cli.rs
Configurando o Projeto
cargo new rdiff
cd rdiff
Configure o Cargo.toml:
[package]
name = "rdiff"
version = "0.1.0"
edition = "2021"
[dependencies]
clap = { version = "4", features = ["derive"] }
colored = "2"
Usamos apenas clap para a interface de linha de comando e colored para a saida colorida. O algoritmo de diff e implementado do zero, sem dependencias externas.
Passo 1: Implementando o Algoritmo de Myers
O algoritmo de Myers e a base da nossa ferramenta. Ele encontra a menor sequencia de edicoes (Shortest Edit Script — SES) para transformar uma sequencia em outra. O algoritmo trabalha com um grafo de edicoes e busca em largura por diagonais, resultando em complexidade O((N+M)D) onde D e o numero de diferencas.
Crie o arquivo src/myers.rs:
// src/myers.rs
/// Tipo de operacao no diff
#[derive(Debug, Clone, PartialEq)]
pub enum Operacao {
/// Linha igual nos dois arquivos
Igual(String),
/// Linha adicionada (presente apenas no novo)
Adicionar(String),
/// Linha removida (presente apenas no original)
Remover(String),
}
/// Resultado do diff com estatisticas
pub struct ResultadoDiff {
pub operacoes: Vec<Operacao>,
pub linhas_adicionadas: usize,
pub linhas_removidas: usize,
pub linhas_iguais: usize,
}
/// Calcula o diff entre duas sequencias de linhas usando o algoritmo de Myers.
///
/// O algoritmo busca o caminho mais curto em um grafo de edicoes,
/// onde mover na horizontal significa remover e na vertical significa adicionar.
/// Movimentos diagonais representam linhas iguais e sao "gratis".
pub fn calcular_diff(original: &[&str], modificado: &[&str]) -> ResultadoDiff {
let n = original.len();
let m = modificado.len();
// Caso especial: um dos arquivos esta vazio
if n == 0 && m == 0 {
return ResultadoDiff {
operacoes: Vec::new(),
linhas_adicionadas: 0,
linhas_removidas: 0,
linhas_iguais: 0,
};
}
if n == 0 {
let ops: Vec<Operacao> = modificado
.iter()
.map(|l| Operacao::Adicionar(l.to_string()))
.collect();
return ResultadoDiff {
linhas_adicionadas: m,
linhas_removidas: 0,
linhas_iguais: 0,
operacoes: ops,
};
}
if m == 0 {
let ops: Vec<Operacao> = original
.iter()
.map(|l| Operacao::Remover(l.to_string()))
.collect();
return ResultadoDiff {
linhas_adicionadas: 0,
linhas_removidas: n,
linhas_iguais: 0,
operacoes: ops,
};
}
// Fase 1: Encontrar o caminho mais curto (algoritmo de Myers)
let max_d = n + m;
let tamanho = 2 * max_d + 1;
// v[k] armazena o x mais avancado para a diagonal k
// Usamos offset para indexar diagonais negativas
let offset = max_d as isize;
// Historico de estados v para cada passo d
let mut historico: Vec<Vec<isize>> = Vec::new();
let mut v: Vec<isize> = vec![0; tamanho];
// Buscar o menor d que alcanca (n, m)
let mut d_final = 0;
'outer: for d in 0..=(max_d as isize) {
let v_anterior = v.clone();
historico.push(v_anterior);
let mut k = -d;
while k <= d {
let idx_k = (k + offset) as usize;
// Decidir se vamos para baixo (adicionar) ou direita (remover)
let x: isize = if k == -d
|| (k != d && v[(k - 1 + offset) as usize] < v[(k + 1 + offset) as usize])
{
// Mover para baixo: usar x da diagonal k+1
v[(k + 1 + offset) as usize]
} else {
// Mover para a direita: usar x da diagonal k-1, incrementando
v[(k - 1 + offset) as usize] + 1
};
let mut x = x;
let mut y = x - k;
// Seguir diagonais (linhas iguais) o maximo possivel
while (x as usize) < n
&& (y as usize) < m
&& original[x as usize] == modificado[y as usize]
{
x += 1;
y += 1;
}
v[idx_k] = x;
// Verificar se alcancamos o final
if x as usize == n && y as usize == m {
d_final = d;
historico.push(v.clone());
break 'outer;
}
k += 2;
}
}
// Fase 2: Reconstruir o caminho a partir do historico
let operacoes = reconstruir_caminho(
&historico,
d_final,
offset,
original,
modificado,
);
// Calcular estatisticas
let mut adicionadas = 0;
let mut removidas = 0;
let mut iguais = 0;
for op in &operacoes {
match op {
Operacao::Adicionar(_) => adicionadas += 1,
Operacao::Remover(_) => removidas += 1,
Operacao::Igual(_) => iguais += 1,
}
}
ResultadoDiff {
operacoes,
linhas_adicionadas: adicionadas,
linhas_removidas: removidas,
linhas_iguais: iguais,
}
}
/// Reconstroi a sequencia de operacoes a partir do historico do algoritmo
fn reconstruir_caminho(
historico: &[Vec<isize>],
d_final: isize,
offset: isize,
original: &[&str],
modificado: &[&str],
) -> Vec<Operacao> {
let mut operacoes: Vec<Operacao> = Vec::new();
let mut x = original.len() as isize;
let mut y = modificado.len() as isize;
// Percorrer o historico de tras para frente
let mut d = d_final;
while d > 0 {
let v = &historico[d as usize];
let v_ant = &historico[(d - 1) as usize];
let k = x - y;
// Determinar de qual diagonal viemos
let k_anterior = if k == -d
|| (k != d && v_ant[(k - 1 + offset) as usize] < v_ant[(k + 1 + offset) as usize])
{
k + 1 // Veio de cima (adicao)
} else {
k - 1 // Veio da esquerda (remocao)
};
let x_anterior = v_ant[(k_anterior + offset) as usize];
let y_anterior = x_anterior - k_anterior;
// Adicionar diagonais (linhas iguais) — percorremos de tras para frente
while x > x_anterior && y > y_anterior {
x -= 1;
y -= 1;
operacoes.push(Operacao::Igual(original[x as usize].to_string()));
}
// Adicionar a operacao de edicao
if k_anterior == k + 1 {
// Veio de cima: linha foi adicionada
y -= 1;
operacoes.push(Operacao::Adicionar(modificado[y as usize].to_string()));
} else {
// Veio da esquerda: linha foi removida
x -= 1;
operacoes.push(Operacao::Remover(original[x as usize].to_string()));
}
d -= 1;
}
// Adicionar diagonais restantes do inicio
while x > 0 && y > 0 {
x -= 1;
y -= 1;
operacoes.push(Operacao::Igual(original[x as usize].to_string()));
}
// Inverter pois construimos de tras para frente
operacoes.reverse();
operacoes
}
#[cfg(test)]
mod testes {
use super::*;
#[test]
fn testar_arquivos_iguais() {
let original = vec!["linha 1", "linha 2", "linha 3"];
let modificado = vec!["linha 1", "linha 2", "linha 3"];
let resultado = calcular_diff(&original, &modificado);
assert_eq!(resultado.linhas_iguais, 3);
assert_eq!(resultado.linhas_adicionadas, 0);
assert_eq!(resultado.linhas_removidas, 0);
}
#[test]
fn testar_adicao() {
let original = vec!["a", "b"];
let modificado = vec!["a", "c", "b"];
let resultado = calcular_diff(&original, &modificado);
assert_eq!(resultado.linhas_adicionadas, 1);
assert_eq!(resultado.linhas_iguais, 2);
}
#[test]
fn testar_remocao() {
let original = vec!["a", "b", "c"];
let modificado = vec!["a", "c"];
let resultado = calcular_diff(&original, &modificado);
assert_eq!(resultado.linhas_removidas, 1);
assert_eq!(resultado.linhas_iguais, 2);
}
#[test]
fn testar_arquivos_vazios() {
let original: Vec<&str> = vec![];
let modificado: Vec<&str> = vec![];
let resultado = calcular_diff(&original, &modificado);
assert_eq!(resultado.operacoes.len(), 0);
}
#[test]
fn testar_original_vazio() {
let original: Vec<&str> = vec![];
let modificado = vec!["a", "b"];
let resultado = calcular_diff(&original, &modificado);
assert_eq!(resultado.linhas_adicionadas, 2);
}
}
O algoritmo funciona em duas fases: primeiro encontra o caminho mais curto no grafo de edicoes (fase de busca), depois reconstroi a sequencia de operacoes a partir do historico (fase de backtracking). A complexidade e proporcional ao numero de diferencas, nao ao tamanho dos arquivos — por isso e eficiente para arquivos similares.
Passo 2: Formatacao da Saida
O modulo formatador.rs transforma o resultado do diff em diferentes formatos visuais.
// src/formatador.rs
use crate::myers::{Operacao, ResultadoDiff};
use colored::*;
/// Exibe o diff com cores no terminal (formato inline)
pub fn exibir_colorido(resultado: &ResultadoDiff) {
let mut num_original: usize = 0;
let mut num_modificado: usize = 0;
for op in &resultado.operacoes {
match op {
Operacao::Igual(linha) => {
num_original += 1;
num_modificado += 1;
println!(
" {:>4} {:>4} {}",
num_original.to_string().dimmed(),
num_modificado.to_string().dimmed(),
linha
);
}
Operacao::Remover(linha) => {
num_original += 1;
println!(
" {:>4} {:>4} {} {}",
num_original.to_string().red(),
" ",
"-".red().bold(),
linha.red()
);
}
Operacao::Adicionar(linha) => {
num_modificado += 1;
println!(
" {:>4} {:>4} {} {}",
" ",
num_modificado.to_string().green(),
"+".green().bold(),
linha.green()
);
}
}
}
}
/// Exibe o diff no formato unified (compativel com patch)
pub fn exibir_unified(
resultado: &ResultadoDiff,
nome_original: &str,
nome_modificado: &str,
contexto: usize,
) {
// Cabecalho do unified diff
println!("{}", format!("--- {}", nome_original).red());
println!("{}", format!("+++ {}", nome_modificado).green());
// Agrupar operacoes em hunks com linhas de contexto
let hunks = gerar_hunks(&resultado.operacoes, contexto);
for hunk in &hunks {
// Cabecalho do hunk: @@ -inicio,tamanho +inicio,tamanho @@
println!(
"{}",
format!(
"@@ -{},{} +{},{} @@",
hunk.inicio_original,
hunk.tamanho_original,
hunk.inicio_modificado,
hunk.tamanho_modificado,
)
.cyan()
);
for op in &hunk.operacoes {
match op {
Operacao::Igual(linha) => println!(" {}", linha),
Operacao::Remover(linha) => {
println!("{}", format!("-{}", linha).red());
}
Operacao::Adicionar(linha) => {
println!("{}", format!("+{}", linha).green());
}
}
}
}
}
/// Representa um bloco de alteracoes com contexto
struct Hunk {
inicio_original: usize,
tamanho_original: usize,
inicio_modificado: usize,
tamanho_modificado: usize,
operacoes: Vec<Operacao>,
}
/// Agrupa operacoes em hunks com linhas de contexto ao redor das mudancas
fn gerar_hunks(operacoes: &[Operacao], contexto: usize) -> Vec<Hunk> {
if operacoes.is_empty() {
return Vec::new();
}
// Encontrar indices das linhas com alteracoes
let mut indices_mudanca: Vec<usize> = Vec::new();
for (i, op) in operacoes.iter().enumerate() {
if !matches!(op, Operacao::Igual(_)) {
indices_mudanca.push(i);
}
}
if indices_mudanca.is_empty() {
return Vec::new();
}
// Agrupar mudancas proximas no mesmo hunk
let mut grupos: Vec<(usize, usize)> = Vec::new();
let mut inicio = indices_mudanca[0];
let mut fim = indices_mudanca[0];
for &idx in &indices_mudanca[1..] {
if idx <= fim + 2 * contexto + 1 {
fim = idx;
} else {
grupos.push((inicio, fim));
inicio = idx;
fim = idx;
}
}
grupos.push((inicio, fim));
// Converter grupos em hunks
let mut hunks = Vec::new();
for (inicio_grupo, fim_grupo) in grupos {
let inicio_hunk = inicio_grupo.saturating_sub(contexto);
let fim_hunk = (fim_grupo + contexto + 1).min(operacoes.len());
let ops: Vec<Operacao> = operacoes[inicio_hunk..fim_hunk].to_vec();
// Calcular posicoes nos arquivos original e modificado
let mut pos_original: usize = 1;
let mut pos_modificado: usize = 1;
for op in &operacoes[..inicio_hunk] {
match op {
Operacao::Igual(_) => {
pos_original += 1;
pos_modificado += 1;
}
Operacao::Remover(_) => pos_original += 1,
Operacao::Adicionar(_) => pos_modificado += 1,
}
}
let mut tam_original = 0;
let mut tam_modificado = 0;
for op in &ops {
match op {
Operacao::Igual(_) => {
tam_original += 1;
tam_modificado += 1;
}
Operacao::Remover(_) => tam_original += 1,
Operacao::Adicionar(_) => tam_modificado += 1,
}
}
hunks.push(Hunk {
inicio_original: pos_original,
tamanho_original: tam_original,
inicio_modificado: pos_modificado,
tamanho_modificado: tam_modificado,
operacoes: ops,
});
}
hunks
}
/// Exibe estatisticas do diff
pub fn exibir_estatisticas(resultado: &ResultadoDiff) {
let total = resultado.linhas_adicionadas
+ resultado.linhas_removidas
+ resultado.linhas_iguais;
println!();
println!("{}", "--- Estatisticas ---".bold());
println!(
" Linhas iguais: {} ({:.1}%)",
resultado.linhas_iguais,
if total > 0 {
resultado.linhas_iguais as f64 / total as f64 * 100.0
} else {
100.0
}
);
println!(
" Linhas adicionadas: {} {}",
resultado.linhas_adicionadas,
format!("(+{})", resultado.linhas_adicionadas).green()
);
println!(
" Linhas removidas: {} {}",
resultado.linhas_removidas,
format!("(-{})", resultado.linhas_removidas).red()
);
println!(" Total de linhas: {}", total);
}
O formato unified diff e o padrao usado pelo git diff e pelo comando diff -u. Ele agrupa as alteracoes em “hunks” com linhas de contexto ao redor, facilitando a compreensao. Cada hunk tem um cabecalho @@ -inicio,tamanho +inicio,tamanho @@ que indica a posicao exata nos dois arquivos.
Passo 3: Interface de Linha de Comando
// src/cli.rs
use clap::Parser;
#[derive(Parser, Debug)]
#[command(name = "rdiff")]
#[command(about = "Ferramenta de diff para comparar arquivos")]
pub struct Argumentos {
/// Arquivo original
pub original: String,
/// Arquivo modificado
pub modificado: String,
/// Formato unified diff (similar ao git diff)
#[arg(short, long)]
pub unified: bool,
/// Numero de linhas de contexto no formato unified
#[arg(short, long, default_value_t = 3)]
pub contexto: usize,
/// Exibir estatisticas das alteracoes
#[arg(short = 'e', long)]
pub estatisticas: bool,
/// Saida sem cores (para redirecionar para arquivo)
#[arg(long)]
pub sem_cor: bool,
}
Passo 4: Juntando Tudo no main.rs
// src/main.rs
mod cli;
mod formatador;
mod myers;
use clap::Parser;
use colored::control;
use std::fs;
use std::process;
fn main() {
let args = cli::Argumentos::parse();
// Desabilitar cores se solicitado
if args.sem_cor {
control::set_override(false);
}
// Ler os arquivos
let conteudo_original = ler_arquivo(&args.original);
let conteudo_modificado = ler_arquivo(&args.modificado);
// Dividir em linhas
let linhas_original: Vec<&str> = conteudo_original.lines().collect();
let linhas_modificado: Vec<&str> = conteudo_modificado.lines().collect();
// Calcular o diff
let resultado = myers::calcular_diff(&linhas_original, &linhas_modificado);
// Verificar se ha diferencas
if resultado.linhas_adicionadas == 0 && resultado.linhas_removidas == 0 {
println!("Os arquivos sao identicos.");
return;
}
// Exibir o diff no formato escolhido
if args.unified {
formatador::exibir_unified(
&resultado,
&args.original,
&args.modificado,
args.contexto,
);
} else {
println!(
"Comparando '{}' com '{}':\n",
args.original, args.modificado
);
formatador::exibir_colorido(&resultado);
}
// Exibir estatisticas se solicitado
if args.estatisticas {
formatador::exibir_estatisticas(&resultado);
}
}
/// Le o conteudo de um arquivo ou exibe erro e encerra
fn ler_arquivo(caminho: &str) -> String {
match fs::read_to_string(caminho) {
Ok(conteudo) => conteudo,
Err(e) => {
eprintln!("Erro ao ler '{}': {}", caminho, e);
process::exit(1);
}
}
}
O main.rs segue o fluxo tipico de uma ferramenta CLI: parsear argumentos, ler entradas, processar e exibir resultados. A separacao entre o algoritmo (myers.rs), a formatacao (formatador.rs) e a interface (cli.rs) mantem o codigo organizado e testavel.
Como Executar
cargo build --release
Crie dois arquivos de exemplo para testar:
# Criar arquivo original
cat > original.txt << 'EOF'
fn main() {
let nome = "mundo";
println!("Ola, {}!", nome);
}
EOF
# Criar arquivo modificado
cat > modificado.txt << 'EOF'
fn main() {
let nome = "Rust";
let versao = "2026";
println!("Ola, {} {}!", nome, versao);
}
EOF
Exemplos de uso:
# Diff com saida colorida (padrao)
./target/release/rdiff original.txt modificado.txt
# Comparando 'original.txt' com 'modificado.txt':
#
# 1 1 fn main() {
# 2 - let nome = "mundo";
# 2 + let nome = "Rust";
# 3 + let versao = "2026";
# 3 - println!("Ola, {}!", nome);
# 4 + println!("Ola, {} {}!", nome, versao);
# 4 5 }
# Formato unified diff (como git diff)
./target/release/rdiff original.txt modificado.txt --unified
# --- original.txt
# +++ modificado.txt
# @@ -1,4 +1,5 @@
# fn main() {
# - let nome = "mundo";
# - println!("Ola, {}!", nome);
# + let nome = "Rust";
# + let versao = "2026";
# + println!("Ola, {} {}!", nome, versao);
# }
# Com estatisticas
./target/release/rdiff original.txt modificado.txt --estatisticas
# --- Estatisticas ---
# Linhas iguais: 2 (28.6%)
# Linhas adicionadas: 3 (+3)
# Linhas removidas: 2 (-2)
# Total de linhas: 7
# Redirecionar para arquivo (sem cores ANSI)
./target/release/rdiff original.txt modificado.txt --unified --sem-cor > diff.patch
# Executar os testes unitarios
cargo test
Desafios para Expandir
Diff de diretorios: Implemente comparacao recursiva de diretorios, listando arquivos adicionados, removidos e modificados, com a opcao de exibir o diff de cada arquivo alterado.
Diff semantico por palavras: Em vez de comparar linhas inteiras, implemente diff por palavras dentro de cada linha alterada, destacando exatamente quais palavras mudaram — como o
git diff --word-diff.Modo interativo com merge: Adicione um modo interativo que permita ao usuario escolher, para cada hunk, se aceita a versao original, a modificada ou ambas — implementando um merge manual basico.
Suporte a arquivos binarios: Detecte arquivos binarios e exiba apenas a informacao de que eles diferem, com hash e tamanho, em vez de tentar comparar o conteudo como texto.
Saida em HTML: Gere um arquivo HTML com o diff formatado visualmente, com cores e destaque, ideal para code review ou documentacao — similar ao que ferramentas como GitHub exibem.
Veja Tambem
- Manipulacao de Strings — operacoes com texto linha a linha
- Trabalhando com Vec — vetores e algoritmos sobre colecoes
- Modulo fs — leitura de arquivos para comparacao
- Trabalhando com Slices — fatias e operacoes em subsequencias
- Lendo Arquivos — padroes de leitura de arquivos em Rust