Changeless<LowestFee> prunes away changeless solutions that max_weight forces

[evanlinjin]

What Changeless is meant to do

Changeless<M> finds the best selection that has no change output. It asks the inner metric (usually LowestFee) whether a selection would have change; if it would, that selection doesn't count.

To avoid searching pointlessly it has a shortcut, change_unavoidable: if every selection reachable from here would have change, skip this whole branch. It decides that by building the reachable selection with the smallest excess — add every remaining coin with negative effective value, since those shrink the excess. If even that one still has change, prune.

The bug

There is a second route to being changeless that the shortcut does not know about.

LowestFee refuses to add change when the change output would push the transaction over Target::max_weight. So a selection can be changeless purely because change would not fit. The shortcut only reasons about excess, so it prunes branches containing exactly those solutions.

Net effect: BnB reports no solution while a perfectly good changeless solution exists.

Verified reproduction (master, abfb0ed)

Three candidates, max_weight = 710, 1 sat/vb, target value 10 000, DrainWeights::TR_KEYSPEND:

let candidates = vec![
    Candidate { value: 121_861, weight: 200, input_count: 1, is_segwit: true },
    Candidate { value:   1_000, weight: 500, input_count: 1, is_segwit: true },
    Candidate { value: 193_757, weight: 368, input_count: 1, is_segwit: true },
];
let target = Target {
    fee: TargetFee { rate: FeeRate::from_sat_per_vb(1.0), absolute: 0, replace: None },
    outputs: TargetOutputs { value_sum: 10_000, weight_sum: 100, n_outputs: 1 },
    max_weight: Some(710),
};
let metric = || Changeless(LowestFee {
    long_term_feerate: FeeRate::from_sat_per_vb(1.0),
    dust_relay_feerate: FeeRate::from_sat_per_vb(1.0),
    drain_weights: DrainWeights::TR_KEYSPEND,
});

let mut a = CoinSelector::new(&candidates);
let expected = common::exhaustive_search(&mut a, target, &mut metric());

let mut b = CoinSelector::new(&candidates);
let found = common::bnb_search(&mut b, target, metric(), usize::MAX);

assert_eq!(expected.map(|(s, _)| s), found.ok().map(|(s, _)| s));

solution=[0✔, 2✔, 1☐], score=305618          <- brute force
exhaustive = Some(Ordf32(305618.0))
bnb        = Err(RoundLimit { max_rounds: 18446744073709551615, rounds: 2 })

rounds: 2 matters: the queue emptied, so this is a prune, not a round limit. Unlimited-rounds BnB should be an exact detector here.

Mechanism

selection	weight, no change	weight, with change	change?	Changeless score
{0}	342	514 (fits)	yes, 111 732	rejected — has change
{0,2}	710 (exactly the cap)	882 (over cap)	no	305 618

At node {0}, LowestFee wants change, so change_unavoidable looks for a reachable selection with less excess. The only remaining coin (candidate 1) has positive effective value (+875), so nothing is added; the "least excess" selection is {0} itself, which still has change → prune. But {0,2} sits under {0}, and it is changeless because its change would weigh 882 > 710.

Fix options — input wanted

1. Make the shortcut cap-aware. Don't prune when a reachable selection could exceed the cap with change weights. Cheap conservative test: if selecting everything still fits under cap-with-change, prune as today; otherwise don't. Keeps the prune wherever it is valid.
2. Drop the shortcut whenever target.max_weight.is_some(). Simplest and correct; loses pruning on every capped problem.
3. Have the inner metric say why it refused change (not worthwhile / dust / too heavy) so the wrapper can reason instead of guessing. More invasive, but removes the guesswork for good — and any future reason for refusing change won't silently reintroduce this.

My read: (1) is the best cost/benefit, (3) is the honest fix. Which do you prefer?

Notes

• Unrelated to unconfirmed ancestors — reproduces on plain master, and predates feat!: ancestor-aware coin selection (CPFP bump via SelectionProblem) #64.
• Distinct from Make Changeless metric more useful when combined. #17 (Changeless usefulness when combined), though both are about this wrapper.
• In feat!: ancestor-aware coin selection (CPFP bump via SelectionProblem) #64 the new Changeless proptest forces max_weight: None with a comment pointing here, so this stays visible rather than hidden.