Hacktoberfest 2026 : les issues que les mainteneurs ont marquées pour octobre, ouvertes et accessibles aux débutants. Parcourir les issues Hacktoberfest

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

Ouverte
#287 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
45/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
Active
Stack technique
rust
Domaine
cli

Piste de recherche

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.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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.

Langage dominant
Rust
Étoiles
276
Forks
39
Merge moyen
4 j 12 h
PR mergées (30 j)
3

Guide de contribution

Ouvrir le guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de uutils/diffutils

Toutes les issues de uutils/diffutils

Issues similaires

Plus d'issues Rust

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.