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

[leeewee]

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.