uutils / uutils/coreutils

tr: a large `[c*n]` repeat count is materialized unbounded — `capacity overflow` panic / allocation abort (exit 134)

Open
#14,420 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

U - tr
Dominant language
Rust
Stars
24.1k
Forks
2k
Avg merge
1d 5h
Merged PRs (30d)
365

Description

tr accepts any repeat count in the [c*n] construct up to u64::MAX, then eagerly materializes the repeat into a Vec<u8> — one byte per repetition. A count in the 10^14 range aborts the process with an allocation failure; a count at or above 2^63 aborts with a capacity overflow panic.

Steps to reproduce

$ tr '[a*9223372036854775808]' b </dev/null
thread 'main' panicked at library/alloc/src/raw_vec/mod.rs:28:5:
capacity overflow
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Aborted (core dumped)
$ echo $?
134
$ tr '[a*99999999999999]' b </dev/null
memory allocation of 99999999999999 bytes failed
Aborted (core dumped)
$ echo $?
134

Root cause

Sequence::flatten expands a repeat into an iterator of n bytes:

// src/uu/tr/src/operation.rs:210, 215 
pub fn flatten(&self) -> Box<dyn Iterator<Item = u8>> {
    match self {
        // ...
        Self::CharRepeat(c, n) => Box::new(std::iter::repeat_n(*c, *n)),

The two consumers of that iterator fail in two different ways:

// src/uu/tr/src/operation.rs:295  -- SET1: allocates n bytes up front
let mut set1_solved: Vec<u8> = set1.iter().flat_map(Self::flatten).collect();

// src/uu/tr/src/operation.rs:301-308 -- SET2: iterates n times
let set2_len = set2
            .iter()
            .filter_map(|s| match s {
                Self::CharStar(_) => None,
                r => Some(r),
            })
            .flat_map(Self::flatten)
            .count();
  • collect() (SET1)Box<dyn Iterator> forwards size_hint, and repeat_n reports it exactly, so Vec's SpecFromIterNested reserves all n bytes in one request. That is the abort.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in src/uu/tr/src/operation.rs at Sequence::flatten and the SET1 and SET2 consumers around the cited lines. Run the two reproduction commands to observe the allocation failure and capacity-overflow panic; done means large repeat counts no longer abort the tr process, while the existing repeat behavior remains correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
cli
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.