Hacktoberfest 2026: as issues que os mantenedores marcaram para outubro, abertas e boas para iniciantes. Ver issues do Hacktoberfest

diff: two large files abort with a ~100 TB allocation

Aberta
#287 0 comentários 0 reações 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
45/100
Tipo de issue
Bug
Clareza
Claramente especificada
Status de atividade
Ativa
Stack de tecnologia
rust
Domínio
cli

Direção de pesquisa

The issue is in src/ed_diff.rs and related files (unified_diff.rs, normal_diff.rs, context_diff.rs, side_diff.rs) where diff::slice is called. First, understand the diff crate's algorithm and its O(n*m) allocation. Look for existing linear-space Myers implementations in Rust or consider patching the diff crate dependency. The goal is to replace the current call with an algorithm that handles large files without excessive memory, and ensure proper error handling instead of aborting. Test with the provided large file example to verify the fix.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

diff builds its line-level LCS with diff::slice() from the diff crate, which allocates an O(n·m) table over the two line vectors. For two
multi-million-line files that table is hundreds of terabytes, the allocation fails, and the process aborts with no diff:-prefixed diagnostic. GNU diff uses a linear-space Myers algorithm and handles the same files in the normal way.

$ python3 -c "open('a','w').write('\n'*5000000)"       # 5 MB, 5M empty lines
$ python3 -c "open('b','w').write('z\n'*5000000)"      # 10 MB, 5M 'z' lines
$ diff a b > /dev/null
memory allocation of 100000040000004 bytes failed
Aborted (core dumped)
$ echo $?
134

Every output mode fails the same way — the allocation happens before any
formatting:

$ for m in "" -u -c -e -y; do diff $m a b >/dev/null; echo "$m -> $?"; done
 -> 134
-u -> 134
-c -> 134
-e -> 134
-y -> 134

Root cause

Each output mode drives the same routine:

// src/ed_diff.rs:74   (identically: unified_diff.rs:68, normal_diff.rs:57,
//                      context_diff.rs:80, side_diff.rs:351)
for result in diff::slice(&expected_lines, &actual_lines) {

diff::slice is the diff crate's LCS over two slices; its dynamic-programming table is proportional to expected_lines.len() * actual_lines.len(). With 5M lines on each side that is ~2.5·10¹³ cells — the observed request is 100,000,040,000,004 bytes (~100 TB). Nothing bounds the input size before the call, and the allocation failure is an abort rather than an error the caller can report.

Linguagem predominante
Rust
Estrelas
276
Forks
39
Merge médio
4d 12h
PRs com merge (30d)
3

Guia de contribuição

Abrir o guia de contribuição

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de uutils/diffutils

Todas as issues de uutils/diffutils

Issues semelhantes

Mais issues de Rust

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.