In e721a41:

Lol, we take a Txid, convert it to a sha256d::Hash and then convert it to a TxMerkleNode. The intermediate step really isn't needed at all, and kinda obfuscates what's happening (which is that in the single-transaction case we "cast" a txid directly into a Merkle root....this looks suspicious because it is suspicious! But that's Bitcoin for you.)

This is a simple enough change and a fairly small PR so I'd like you to make this change before I ack.

To be clear: the change I'm requesting is to compress the 2 conversion lines into one.

Oh, yes, good find! I agree it'd be better to do it in this PR. But maybe make this change in a separate preparatory commit with explanation since it was weird to begin with.

Nice, quick touch up on my merkle root calculation knowledge and added a patch upfront that is 4 lines of red one line of green - WIN.

Oh, yes, IIRC the function has a length check upfront, so this has no perf impact and is semantically more sensible.

BTW, I've noticed a lot of projects require non-empty slice/vec/hashmap/hashset/... in the APIs. I'm becoming more and more annoyed that there's no good NonEmpty* type (crate) and I'm seriously thinking of writing one. @apoelstra how do you feel about having such thing in, possibly public, dependency of bitcoin? I obviously intend to make it stable, maybe even very soon. (I don't think there will be too much design space.)

I'd like to see it. I'm skeptical. I think that Rust's type system is too weak to do such a thing ergonomically.

Are you imagining having functions take e.g. a NonEmpty<HashSet<T>> and then users need to fallibly convert their normal HashSet<T>s into this and then deal with the error case even if they know it won't ever happen? That's too much ergonomic cost.

The ergonomic cost has to show up somewhere anyway - by having expect like in this case, by surprise runtime panic, or even undefined behavior... As someone said "complexity cannot be destroyed, it can only be moved to a more appropriate place".

There are various cases where it's possible to return NonEmpty<Whatever> knowing that it's definitely correct which may actually make the API more ergonomic.

One example is where you have a single item (as the initial value, before adding more or simply you only happen to need one - like here). You can have pub fn with_first(item: T) -> Self. It's also possible to implement conversions on arrays - either by simply choosing a reasonable range (up to 64 elements or whatever) or by implementing it for all arrays but post-mono compile erroring. And by accepting Into<NonEmpty<T>> and such you can allow arrays being passed in directly with no runtime checks (explicit or implicit). On the other side, you can have first, split_first, last, split_last... methods return non-Option which then simplifies the internal code.

Also while iterators are not compatible, you can still have .map() method that's equivalent to .into_iter().map().collect(). You can also have push and even pop (that simply refuses to pop the single element). And if you let the types bubble up you often find the end at deserialization - where it reminds you of handling it properly. (TBF I have some crazy code that has to deal with ~4 errors during deserialization of several different objects and "empty" is one of them but I can't just ignore it - I need to reject it upfront.)

It might not be appropriate in non-security-critical applications but bitcoin is quite security-critical. And for some odd reason I'm drawn into writing security-critical stuff.

Also the latest issue with invalid expect has shown me that we've become complacent. We no longer question code that panics because we write it so much it's getting normal to see it. I want to do something about it. Part of it is "does every panicking thing have a test?" but part of it is removing panics at type level.

This comment says it's just a refactor, although a surface level inspection indicates this can now panic whereas before I don't see that as true.

@yancyribbens the called function only returns None if the input is empty and it's not.

Fair point. Could have just said that in the expect message :P

Oh, but your question demonstrates a new point - is what I said above actually correct? The only way to know for sure is to read the code of compute_merkle_tree. If there is another reason to return None that expect would become invalid. And the function could accidentally do so. By moving the requirement into arguments and not returning Option we move this into very clear NonEmpty::ftry_from (or, in this case, no fallibility anywhere since you can just pass an array).

Without getting too into the weeds of what the compiler might be able to do so that a useless expect() isn't needed, it would be nice maybe for readability to agree on something like expect() but with a message for the developer why this should never be needed. Expect messages I guess are more for bubbling message when the code is run then it is for the person reading the code. Of course there's always the risk that code refactor makes the expect actually panic someday.

The expect message is better than nothing but even if you put the literal Coq proof there, there's no mechanism to enforce it's not out-of-sync. Imagine this code:

// Computes the arithmetic average if the numbers, returns `None` if empty.
fn compute_average(items: &[usize]) -> Option<usize> {
    items.iter().copied().sum::<usize>().checked_div(items.len())
}

The someone somewhere calls it like this:

compute_average(&[a, b, c, d]).expect("the function returns None if the input is empty and the input is certainly not empty - as you can see we're passing in an array of four items")

Looks great, doesn't it?

Except one day someone realizes: "oh, the sum could overflow, we need checked sum" and rewrites compute_average to also return None in that case. And now the consumer code has a DoS vector because while the function call will not panic because of empty input it will panic if the sum is too large.

One very annoying way to address that is to return Result where the error is an enum and is either exhaustive - in which case the caller has to match all variants (could be just one variant) and the callee will have to break the API alerting the caller of the problem or the enum is non-exhaustive in which case the caller will theoretically know that calling expect on it is wrong. (Well, I think a clippy lint warning against this would be nice.)

The expect message is better than nothing but even if you put the literal Coq proof there

Hah. I remember studying formal language verification a bit at the university, although I never did study Coq specifically. It's a very interesting area of research though. I think one of the things that stuck with me is Tony Hoare's billion dollar mistake with the invention of the null pointer which increased my interest in Rust, not C.

Except one day someone realizes: "oh, the sum could overflow, we need checked sum" and rewrites compute_average to also return None in that case..

I agree. I had also mentioned above that the use of expect() here is fine now but not robust against refactors. I think it would have been nice to just write in the commit message though why expect is safe but just nit picking.

write in the commit message

It's better in code I think but we really want better tools to handle this.

This comment looks like another refactor commit. Would be helpful to call it out as such.

Comment?

doh. commit.