name = "itertools"
description = """
ETNA workload for the Rust `itertools` crate. Each variant re-introduces one
historical bug-fix into a fresh patched branch and pairs it with a
framework-neutral property, four PBT adapters, and a deterministic witness
test.
"""
language = "rust"
strategies = ["proptest", "quickcheck", "crabcheck", "hegel"]
crate = "itertools"
base_commit = "af7184e4626891f897d212c1ca4f2e55d75bbc38"

[[tasks]]
mutations = ["merge_join_size_hint_overflow_9f41c18_1"]

[tasks.source]
repo = "https://github.com/rust-itertools/itertools"
commits = ["9f41c18435249691cb06c0e98ca5653a3d02ed57"]
commit_subjects = ["Fix potential overflow in MergeJoinBy::size_hint"]
summary = "`MergeJoinBy::size_hint` added the two upstream upper bounds as plain `usize + usize`, so when both bounds were near `usize::MAX` the addition panicked in debug and silently wrapped in release; the fix uses `checked_add` and reports `None` on overflow."

[tasks.injection]
kind = "patch"
files = ["src/merge_join.rs"]
locations = [{ file = "src/merge_join.rs" }]
patch = "patches/merge_join_size_hint_overflow_9f41c18_1.patch"

[tasks.bug]
short_name = "merge_join_size_hint_overflow"
invariant = """
`MergeJoinBy`'s `size_hint` upper bound must never wrap on arithmetic overflow. `Iterator::size_hint` returns `Option<usize>`, where `None` represents "cannot be determined" (including when the real bound exceeds `usize::MAX`). The merged length is at most `a.len() + b.len()`, so when both upper bounds are `usize`, the sum must use `checked_add` and return `None` on overflow.
"""
how_triggered = "Reverts the `size_hint` upper-bound computation from `x.checked_add(y)` to `Some(x + y)`. The property passes two upper bounds that sum to `> usize::MAX` via an `OpaqueIter` that reports a huge upper hint while yielding nothing. On the buggy variant, the `x + y` either panics (debug) or silently wraps (release); either outcome fails the property — only graceful `None` is accepted."

[[tasks.tasks]]
property = "MergeJoinSizeHintOverflow"
witnesses = [
  { test_fn = "witness_merge_join_size_hint_overflow_case_max_plus_max" },
]

[[tasks]]
mutations = ["combinations_zero_empty_13aa10e_1"]

[tasks.source]
repo = "https://github.com/rust-itertools/itertools"
commits = ["13aa10e27a6bb5b5dd70cb677924af5846862560"]
commit_subjects = ["Fix combinations(0) and combinations_with_replacement(0)"]
summary = "`combinations(0)` and `combinations_with_replacement(0)` short-circuited to an empty iterator, but mathematically they must yield exactly one empty combination (`vec![vec![]]`, matching `choose(n, 0) = 1`); the fix stops treating `k == 0` as \"done\"."

[tasks.injection]
kind = "patch"
files = ["src/combinations.rs", "src/combinations_with_replacement.rs"]
locations = [{ file = "src/combinations.rs" }]
patch = "patches/combinations_zero_empty_13aa10e_1.patch"

[tasks.bug]
short_name = "combinations_zero_empty"
invariant = "`(a..b).combinations(0)` and `(a..b).combinations_with_replacement(0)` must each yield exactly one empty combination, `vec![vec![]]`. The empty combination is always a valid 0-length combination, independent of pool size (mirrors `choose(n, 0) = 1`)."
how_triggered = "Short-circuits both iterators when `k == 0`: adds `self.k() == 0 ||` to the `done` check inside `CombinationsGeneric::init`, and flips the empty-indices guard in `CombinationsWithReplacementGeneric::next` so empty indices immediately return `None`. The property asserts the collected output equals `vec![Vec::new()]`; under the mutation it collects to an empty `Vec<Vec<u32>>` and reports `got [], expected [[]]`."

[[tasks.tasks]]
property = "CombinationsZero"
witnesses = [
  { test_fn = "witness_combinations_zero_case_small_pool" },
]

[[tasks]]
mutations = ["cwr_remaining_overflow_c13ee58_1"]

[tasks.source]
repo = "https://github.com/rust-itertools/itertools"
commits = ["c13ee581247fb009dbd12f7685b155e8c6bdcff5"]
commit_subjects = ["remaining_for: handle n + k - 1 overflowing"]
summary = "`remaining_for` in `combinations_with_replacement` computed `checked_binomial((n + k).saturating_sub(1), k)`, which evaluates `n + k` eagerly; when `n` is near `usize::MAX` this overflows (panic in debug, wrap in release) instead of returning `None` from the size hint."

[tasks.injection]
kind = "patch"
files = ["src/combinations_with_replacement.rs"]
locations = [{ file = "src/combinations_with_replacement.rs" }]
patch = "patches/cwr_remaining_overflow_c13ee58_1.patch"

[tasks.bug]
short_name = "cwr_remaining_overflow"
invariant = "`combinations_with_replacement(k)` exposes a `size_hint` that equals `binomial(n + k - 1, k)`. When `n + k - 1` would overflow `usize`, the upper bound must be `Option::None` — never a garbage wrapped value and never a panic."
how_triggered = "Reverts the `count` helper inside `remaining_for` from a two-branch form (`n == 0` ⇒ `k.saturating_sub(1)`, else `(n - 1).checked_add(k)?`) back to the one-liner `checked_binomial((n + k).saturating_sub(1), k)`. Feeding `n = usize::MAX` and `k >= 2` through this computes `n + k` which overflows — panicking in debug, wrapping in release. The property wraps the `size_hint()` call in `catch_unwind`: both a panic and a `Some(u)` result are failures, only a clean `None` passes."

[[tasks.tasks]]
property = "CwrSizeHintOverflow"
witnesses = [
  { test_fn = "witness_cwr_size_hint_overflow_case_huge_pool" },
]

[[tasks]]
mutations = ["kmerge_heapify_order_ca70258_1"]

[tasks.source]
repo = "https://github.com/rust-itertools/itertools"
commits = ["ca7025816a263ab7b57f439962341309a1073273"]
commit_subjects = ["Fix bug in kmerge (heapify)"]
summary = "`kmerge`'s `heapify` iterated internal node indices forward (`0..n/2`) instead of bottom-up (`(0..n/2).rev()`); the forward order produced an invalid min-heap and the iterator yielded elements out of sorted order."

[tasks.injection]
kind = "patch"
files = ["src/kmerge_impl.rs"]
locations = [{ file = "src/kmerge_impl.rs" }]
patch = "patches/kmerge_heapify_order_ca70258_1.patch"

[tasks.bug]
short_name = "kmerge_heapify_order"
invariant = "`Itertools::kmerge()` on sorted sub-iterators must produce a sorted merge equal to the sort of the concatenation. The standard min-heap construction via repeated `sift_down` requires iterating internal node indices **bottom-up** (`(0..n/2).rev()`); forward iteration produces an invalid heap."
how_triggered = "Flips the loop bound in `heapify` from `(0..data.len() / 2).rev()` to `0..data.len() / 2`. With four sorted inputs whose heads are `3, 2, 1, 0` (i.e. sub-iterators starting in descending order of their first element), the buggy forward iteration places `1` at the root instead of `0`, so `KMerge::next` yields `1` before `0`. The property compares the collected merge against the sorted concatenation and fails with a `got … expected …` diff."

[[tasks.tasks]]
property = "KmergeSorted"
witnesses = [
  { test_fn = "witness_kmerge_sorted_case_descending_starts" },
]
