`repair` can reorder or omit records and hide fatal BAM failures

[SuhasSrinivasan]

repair can reorder or omit records and hide fatal BAM failures

Summary

modkit repair writes multi-worker results in completion order while retaining the acceptor's query-name-sorted header. Its equality-only donor/acceptor merge can also stop after an unmatched acceptor and omit later repairable records.

Fatal BAM decode, worker, write, and finalization failures are not handled as one joined command lifecycle. Depending on the failure, modkit 0.6.4 can loop indefinitely, report success with incomplete output, or destroy an existing destination before the failure is known.

Severity

Severity: High — scientific output integrity and reliability

Rationale: Reordering occurs on ordinary valid multi-threaded input and makes the output disagree with its SO:queryname header. A missing donor can silently remove later valid records, while fatal I/O paths can report success or leave an incomplete BAM. These outcomes change record membership or make downstream query-name grouping unreliable without a definitive failure result.

User and scientific impact

• Affected result or workflow: repaired BAM record membership, QNAME adjacency, MM/ML tags retained downstream, and replacement of an existing repair output.
• Direction of error: thread-dependent permutation, split equal-QNAME groups, omission after a donor gap, nontermination, partial output, false success, or destructive truncation.
• Likely exposure: ordering can change on ordinary valid inputs when multiple repair workers finish out of order; donor gaps are data-dependent; decoder and storage failures are uncommon but materially destructive.
• Detectability or workaround: --threads 1 reduces completion-order exposure but does not fix merge or failure handling. Users can compare the output QNAME vector with the acceptor and validate BAM EOF/readability/cardinality before replacing a prior result.

Affected versions and environment

• Released version: modkit 0.6.4.
• Development revision: 5cecc3fb3a9336068d9e3c68d5c08d678153dd2c.
• Operating system and architecture used for verification: macOS on Apple Silicon.
• Input format: query-name-sorted donor and acceptor BAM.
• Related tool used to inspect and generate compact fixtures: samtools 1.23.1.
• Public donor fixture: tests/resources/donor_read_sort.bam, 5,566 bytes, SHA-256 56b61038afceba5e206572e8b8c21766a87208fc766166ae4276306183f39d7f.
• Public acceptor fixture: tests/resources/trimmed_read_sort.mapped.bam, 2,707 bytes, SHA-256 fc7a77d6b506e57a0111e399c96786fa0df15913303653fa2973022c582b1a38.

Steps to reproduce

Multi-worker ordering

From the modkit repository, retain the acceptor QNAME vector and run the released binary repeatedly:

samtools view tests/resources/trimmed_read_sort.mapped.bam \
  | cut -f1 > acceptor.qnames

for run in 1 2 3; do
  modkit repair \
    --donor tests/resources/donor_read_sort.bam \
    --acceptor tests/resources/trimmed_read_sort.mapped.bam \
    --output "repaired-${run}.bam" \
    --threads 8
  samtools view "repaired-${run}.bam" | cut -f1 > "repaired-${run}.qnames"
  cmp -s acceptor.qnames "repaired-${run}.qnames" \
    || echo "run ${run}: QNAME order changed"
done

Missing-donor gap

Create lexicographically query-name-sorted donor records read1 and read3, with an unmatched read2 between them in the acceptor:

cat > gap-donor.sam <<'EOF'
@HD	VN:1.6	SO:queryname	SS:queryname:lexicographical
read1	4	*	0	0	*	*	0	0	TACGT	IIIII	MM:Z:A+a.,0;	ML:B:C,11
read3	4	*	0	0	*	*	0	0	TACGT	IIIII	MM:Z:A+a.,0;	ML:B:C,33
EOF

cat > gap-acceptor.sam <<'EOF'
@HD	VN:1.6	SO:queryname	SS:queryname:lexicographical
read1	4	*	0	0	*	*	0	0	ACG	III
read2	4	*	0	0	*	*	0	0	ACG	III
read3	4	*	0	0	*	*	0	0	ACG	III
EOF

samtools view -b -o gap-donor.bam gap-donor.sam
samtools view -b -o gap-acceptor.bam gap-acceptor.sam

modkit repair \
  --donor gap-donor.bam \
  --acceptor gap-acceptor.bam \
  --output gap-repaired.bam \
  --threads 4

samtools view gap-repaired.bam

Truncated-input lifecycle

Create a public truncated donor and preserve a valid existing destination as a sentinel:

cp tests/resources/donor_read_sort.bam truncated-donor.bam
python3 - <<'PY'
from pathlib import Path

path = Path("truncated-donor.bam")
path.write_bytes(path.read_bytes()[:-40])
PY

cp tests/resources/donor_read_sort.bam existing-output.bam

python3 - <<'PY'
import os
import subprocess

command = [
    "modkit", "repair",
    "--donor", "truncated-donor.bam",
    "--acceptor", "tests/resources/trimmed_read_sort.mapped.bam",
    "--output", "existing-output.bam",
    "--threads", "4",
]
try:
    subprocess.run(
        command,
        stdout=subprocess.DEVNULL,
        stderr=subprocess.DEVNULL,
        timeout=5,
        check=False,
    )
    print("completed")
except subprocess.TimeoutExpired:
    print("timed out after 5 seconds")

print("destination bytes:", os.path.getsize("existing-output.bam"))
PY

The truncated donor is 5,526 bytes with SHA-256 a508f1bf6c31d08b22017b3f756789231a5899a61b1a1dc7bb7f95e63aa58f39.

Observed behavior

• The released binary retains SO:queryname but emits thread-dependent QNAME permutations. In one four-thread run the first two records were swapped; three eight-thread runs produced three different orders.
• The corresponding BAM SHA-256 values differed: 933a4bff8d52dccff9f1d4ee9523fcdbd5adec6b552acf6387e0dc165cf7c790 at four threads, then 80e2c710d0ac46ffd89824185ba0aa3cb7109a35b34fcf3f35fdeb78fe6767ce, dcf286d50c34d33b9a627f415cb905b02b8b993fffc1f16f0555077bc9caf7b2, and a4d2a0d1e8cb0388035fd3faae3c3871ccb516e5335bdcc7f41cae1fd064aff4 in three eight-thread runs.
• The missing-donor fixture exits 0, reports one repaired record and zero failed, emits read1, and silently omits the later repairable read3.
• The truncated-donor command repeatedly logs the same decoder error, exceeds the five-second watchdog, and truncates existing-output.bam from 5,566 bytes to zero bytes. A truncated acceptor produces the same behavior.
• Deterministic fault-injection tests also reproduce discarded writer errors and detached worker failure paths.

Control or independent oracle

The output is a subset of the acceptor, so every successfully repaired record must retain acceptor order and equal QNAMEs must remain adjacent. A missing donor is one per-record rejection; it must not consume later donors or terminate the merge.

A corrected implementation produced one byte-identical 3,142-byte BAM at threads 1, 2, 3, 4, and 8, SHA-256 52b8a3a227b08d0cd98d79c826421199971f5c2e2feead0e3d5c6441e25dc813. That file is also byte-identical to released 0.6.4 at threads 1 and 2, where the released runs happened to preserve order.

For the truncated donor and acceptor, the corrected implementation exits 1 immediately with the failing input and record number, leaves the existing 5,566-byte sentinel byte-identical, and removes its staging directory.

Expected behavior

• Validate compatible declared query-name ordering and reject an observed input-order inversion.
• Preserve acceptor-relative order and exact successful-record cardinality at every worker count, including duplicate QNAME groups.
• Represent an unmatched acceptor as one ordered, nonfatal record rejection and continue with later records.
• Treat decoder, feeder, scheduler worker/panic, output-write, and final-output validation failures as fatal command errors.
• After a fatal error, cancel pending work, join every started thread, discard the staged BAM, and return the first fatal error observed by the coordinator.
• Replace the destination only after the complete staged BAM has a canonical BGZF EOF block, decodes fully, contains the expected record count, and has been synchronized.
• Preserve ordinary successful output bytes and existing regular-file permissions.

Root-cause evidence

• repair_tags.rs:91-131 detaches the source and Rayon work, then sends par_bridge results in completion order without an ordinal drain.
• repair_tags.rs:133-154 logs record-write failures and still returns Ok(()); writer close status is not available through the pinned rust-htslib API.
• repair_tags.rs:191-215 retries BAM decode errors indefinitely.
• repair_tags.rs:243-296 advances only the donor on every QNAME mismatch and stops when donors run out, which loses later valid matches after a donor gap.
• The existing regression collected records into a QNAME-keyed map, erasing order, duplicate names, and exact cardinality from its oracle.

Proposed fix scope

• Use one bounded ordinal scheduler whose source, workers, ordered drain, and output consumer share cancellation and joined failure propagation.
• Merge compatible natural, legacy-natural, or lexicographical query-name streams monotonically; group comparator-equivalent donor names while matching exact QNAME bytes.
• Advance every acceptor through an explicit repaired-or-rejected ordinal so expected biological failures cannot create an ordering gap.
• Stage output in an owner-only same-filesystem temporary directory, retain the original staged descriptor, validate identity/EOF/decode/cardinality, synchronize, and atomically replace the destination only on success.
• Reject symbolic-link and nonregular destinations, use ordinary creation permissions for new output, and preserve permissions when replacing an existing regular file.

Non-goals

• Ambiguous overlapping donor-to-acceptor sequence placement is a separate scientific correction.
• The policy for duplicate-flagged donor records is separate.
• Per-record biological repair failures remain nonfatal; this change distinguishes them from infrastructure and I/O failures.
• No validation of an unused donor tail after all acceptors are exhausted, no corrupt-input repair, and no new CRAM reference policy.
• No crash- or power-loss guarantee, parent-directory fsync, inode/hard-link identity preservation, owner/group/ACL/xattr preservation, or protection against every hostile non-sticky-parent race.
• No guarantee of interrupting an htslib operation already in progress.
• No successful-path performance claim. Full staged-output decoding and synchronization add deliberate I/O before publication.

Acceptance criteria

• Public and synthetic fixtures retain exact acceptor-relative QNAME order and cardinality at threads 1, 2, 3, and 8, including duplicate names and forced out-of-order completion.
• A success/rejection/success sequence drains both successful records in order and counts exactly one rejection.
• Natural, legacy-natural, and lexicographical inputs are handled according to compatible header metadata; mixed modes and actual inversions fail before publication.
• Truncated donor and acceptor input, feeder errors, worker errors/panics, Nth-write failure, and staged-output validation failure return promptly and nonzero under watchdogs.
• Every fatal case preserves an existing destination byte-for-byte, leaves an absent destination absent, joins all threads, and cleans staging artifacts.
• Successful new/existing output preserves the intended mode, while live/dangling symlinks and nonregular targets are rejected without mutation.
• Valid output remains byte-identical across supported worker counts and to the stated released-version control.
• Focused scheduler/repair tests and the full workspace suite pass.

Reproduction artifacts

Artifact	Size	SHA-256	Notes
tests/resources/donor_read_sort.bam	5,566 bytes	56b61038afceba5e206572e8b8c21766a87208fc766166ae4276306183f39d7f	Public donor and destination sentinel
tests/resources/trimmed_read_sort.mapped.bam	2,707 bytes	fc7a77d6b506e57a0111e399c96786fa0df15913303653fa2973022c582b1a38	Public acceptor/order oracle
gap-donor.bam	303 bytes	1ac2927c4a6cdff628ec8518f1f5c0e733476a8701ef67614f8636851112c36d	Inline missing-donor fixture generated with samtools 1.23.1
gap-acceptor.bam	288 bytes	1f46f7f9e1fd534a18bff84b3b38be55a2c6eb52e0a397b0b3d9b0759aa2ee7b	Inline missing-donor fixture generated with samtools 1.23.1
truncated-donor.bam	5,526 bytes	a508f1bf6c31d08b22017b3f756789231a5899a61b1a1dc7bb7f95e63aa58f39	Public donor with the final 40 bytes removed
Corrected valid output	3,142 bytes	52b8a3a227b08d0cd98d79c826421199971f5c2e2feead0e3d5c6441e25dc813	Identical at threads 1/2/3/4/8 and to released threads 1/2 controls

Related work

• The shared ordered scheduler originates in separately scoped pileup failure propagation and should land as a prerequisite rather than being hidden in this repair PR.
• Ambiguous overlapping sequence placement should remain a small standalone scientific PR.
• Duplicate-flagged donor eligibility remains a separate policy question.
• Proposed PR: recompose the scheduler extraction, ordered repair, and atomic lifecycle commits after their prerequisites, then rerun the exact focused and workspace gates before opening.

[SuhasSrinivasan]

The confirmed repair fix is now included in the consolidated, ready-for-review PR #711. Closing this standalone issue in line with the maintainer's request to keep the identified bug and its code change together in the PR.