Refactor bitcoin_merkle_root functions by tcharding · Pull Request #710 · rust-bitcoin/rust-bitcoin

tcharding · 2021-11-18T23:33:41Z

~~Do two minor refactorings to the `bitcoin_merkle_root[_inline] functions.~~

This PR has grown, is no longer a refactoring because the two functions have been changed to return an Option.

First patch is cleanup. Here is the commit message for the second patch

The merkle_root of an empty tree is undefined, this is the only error
case we have for the two `bitcoin_merkle_root*` functions. We can fully
describe this error case by returning an `Option` if args are found to
be empty.

While we are at it, refactor out a recursive helper function to make
reading the code between the two functions easier.

Kixunil

Very good!

ACK 150d9559f164164a5fb30897bec9336a54af0e05

dr-orlovsky

Yes, this makes code much more readable. However it seems like there is a way to get rid from unnecessary unwrap as well

src/util/hash.rs

tcharding · 2021-11-24T00:05:54Z

I've added two more patches that quite heavily refactor the two functions in question. Please re-review at your leisure, this work is really just for the pure fun of beautiful code.

(Includes fix to typo that I recently introduced 'merkel' -> 'merkle' :(

dr-orlovsky

I think that we should return a error and not panic if the tree is empty, since it may be quite a common situation

dr-orlovsky · 2021-11-24T08:40:36Z

src/util/hash.rs

This can be improved even more by

match data.len() { O => panic!(), 1 => data[1], 2 => merkle_root_r(data), }

I deleted my original thoughts because they turned out to be wrong and were really long. PR now includes this suggestion.

Kixunil · 2021-11-24T08:54:44Z

src/util/hash.rs

This same condition is in markle_root_r, so probably not needed here.

I added it there for two reasons:

It gives a line of code that can carry the code comment

In merkle_root_r this call is the recursion base case, here it is not, so slightly different

I was trying to separate the recursion from the two 'higher' functions.

Kixunil · 2021-11-24T08:58:07Z

src/util/hash.rs

Unrelated but I think ExactSIzeIterator is not actually required. Just allocate Vec based on size_hint and let the Vec resize itself if the hint is incorrect (that's actually what happens today - len is not strictly guaranteed to be correct).

But then we cannot call iter.len()?

I don't think we need to:

let first = iter.next()?; let second = match iter.next() { Some(second) => second, // A single hash is by definition the merkle root. None => return Some(first), }; let (min, max) = iter.size_hint(); let mut hashes = Vec::with_capacity(max.unwrap_or(min) / 2 + 1); let iter = [first, second].iter().chain(iter); // Continue using `hashes` and `iter` as before.

Note: s/hashes/alloc/g, s/iter/hashes per latest change.

let iter = [first, second].iter().chain(iter);

I couldn't get this line to build, I used instead:

let mut hashes = iter::once(first).chain(iter::once(second)).chain(hashes);

Kixunil · 2021-11-24T09:00:45Z

src/util/hash.rs

I think it'd be nice to highlight the word "hashes" here and above to make it more obvious it's not data.

Nice, more descriptive and further unifies the functions!

I believe you forgot about highlighting.

Kixunil

Looks good, had a few more ideas. I'm unsure if panic! is better than Option but I think Result would be overkill.

tcharding · 2021-11-24T22:04:55Z

I think that we should return a error and not panic if the tree is empty, since it may be quite a common situation

Thanks for the review @dr-orlovsky, I'm leaning towards @Kixunil suggestion of using an Option. I'll outline the reasoning here to make sure I'm not missing something in your suggestion of returning an error.

No panic because if we panic we are placing a burden on the caller to check their input
If the merkle root of an empty tree is undefined then its not really an error to try and calculate it it just does not exist, implies Option
There is only one error case with no additional information other than 'input was empty', Option fully describes this case

I'll push this change, please comment though if you'd like me to re-consider using an error.

dr-orlovsky · 2021-11-24T22:29:30Z

I think the Option is fine. I was not that much about error as much about not panicking

tcharding · 2021-11-24T22:33:39Z

I'm not sure what is the accepted protocol re force pushing in rust-bitcoin? I've tried to find a balance between keeping the PR consisting of sane, easily reviewed patches and making reviewers have to re-review everything again. If there are any strong opinions on force pushing, please let me know. Thanks again for all the reviews.

tcharding · 2021-11-24T22:34:51Z

I think the Option is fine. I was not that much about error as much about not panicking

Cool, thanks. Easy consensus :)

dr-orlovsky · 2021-11-25T08:56:04Z

@tcharding from my experience here it seems that force-pushes are more preferable than bloating commit log with fix commits. As for re-ACKs, the normal solution for that is using git diff (if no rebase happened), git range-diff master <old-commit> <new-commit> so this does not make a big problem

dr-orlovsky

utACK e0e708b1a4af00fa735c2fb16cb895499ebbef12

src/util/hash.rs

tcharding · 2021-12-02T04:35:49Z

This PR was getting out of control, I've squashed all the hash.rs changes into a single commit. Please re-review at your leisure :)

Kixunil

I believe at least undocumented panics should be resolved.

src/blockdata/block.rs

Kixunil · 2021-12-02T09:24:05Z

src/util/hash.rs

I believe you forgot about highlighting.

src/util/hash.rs

tcharding · 2021-12-03T02:54:29Z

I believe you forgot about highlighting.

I don't understand this comment @Kixunil, can you repeat please? (There is no response box under the original comment for some reason.)

Kixunil · 2021-12-03T07:54:48Z

I suggested adding asterisks around the word "hashes" in the docs, so it becomes hashes. This will make it clear it's not data. I guess you misunderstood what I meant by "highlighting".

Kixunil

ACK 086f4807bad8cb5d06f2b8bbc9d1c506d4822328

Nice improvement! I consider my comments to be optional.

Kixunil · 2021-12-03T07:57:50Z

src/blockdata/block.rs

Maybe this is nicer, I'm not sure, do as you wish.

self.merkle_root() .map(|merkle_root| self.header.merkle_root == merkle_root) .unwrap_or(false)

I played with the combinator here as suggested and also on the call to self.witness_root(). It wasn't clearly better either way to me so I ended going with the code as it is since seemed slightly easier to read.

tcharding · 2021-12-08T20:13:14Z

I suggested adding asterisks around the word "hashes" in the docs, so it becomes hashes. This will make it clear it's not data. I guess you misunderstood what I meant by "highlighting".

Ooooh, my bad, good idea. Will add.

Fix typo in test function name to use the correct spelling of 'merkle' (not 'merkel').

The merkle_root of an empty tree is undefined, this is the only error case we have for the two `bitcoin_merkle_root*` functions. We can fully describe this error case by returning an `Option` if args are found to be empty. We can do the same for the wrapper functions in `block` module. While we are at it, refactor out a recursive helper function to make reading the code between the two functions easier.

tcharding · 2021-12-10T00:33:27Z

Added italics to 'hashes' as suggested, rebased, force pushed.

Kixunil

ACK b454cf8

dr-orlovsky

Seems like we have a bug in the implementation - pls see my comment

src/util/hash.rs

dr-orlovsky

ACK b454cf8

tcharding · 2021-12-13T21:09:30Z

'one-ack' badge is stale :)

Thanks for all the reviews fellas.

Kixunil · 2021-12-13T21:12:20Z

Would merge it but I still didn't setup commit signing properly. My understanding is it's not nice to merge without it.

Kixunil added code quality Makes code easier to understand and less likely to lead to problems P-low Low priority labels Nov 19, 2021

Kixunil previously approved these changes Nov 19, 2021

View reviewed changes

dr-orlovsky suggested changes Nov 22, 2021

View reviewed changes

src/util/hash.rs Outdated Show resolved Hide resolved

tcharding dismissed Kixunil’s stale review via 31a469e November 22, 2021 22:47

Kixunil reviewed Nov 23, 2021

View reviewed changes

src/util/hash.rs Outdated Show resolved Hide resolved

tcharding force-pushed the merkel-root branch from 31a469e to 2196e57 Compare November 24, 2021 00:04

tcharding requested review from Kixunil and dr-orlovsky November 24, 2021 00:06

dr-orlovsky suggested changes Nov 24, 2021

View reviewed changes

Kixunil reviewed Nov 24, 2021

View reviewed changes

tcharding force-pushed the merkel-root branch from 2196e57 to e0e708b Compare November 24, 2021 22:31

dr-orlovsky previously approved these changes Nov 25, 2021

View reviewed changes

src/util/hash.rs Outdated Show resolved Hide resolved

tcharding dismissed dr-orlovsky’s stale review via 2a985ad December 2, 2021 04:24

tcharding force-pushed the merkel-root branch 2 times, most recently from 2a985ad to 3e59061 Compare December 2, 2021 04:34

tcharding requested review from Kixunil and dr-orlovsky December 2, 2021 04:35

tcharding force-pushed the merkel-root branch from 3e59061 to 342bf63 Compare December 2, 2021 04:38

Kixunil requested changes Dec 2, 2021

View reviewed changes

tcharding force-pushed the merkel-root branch from e2ce9f0 to 1eabb77 Compare December 3, 2021 02:58

tcharding requested a review from Kixunil December 3, 2021 02:58

tcharding force-pushed the merkel-root branch from 1eabb77 to 086f480 Compare December 3, 2021 03:09

Kixunil previously approved these changes Dec 3, 2021

View reviewed changes

Kixunil added the one ack PRs that have one ACK, so one more can progress them label Dec 3, 2021

tcharding added 2 commits December 10, 2021 11:18

Use correct spelling of merkle

7a8b017

Fix typo in test function name to use the correct spelling of 'merkle' (not 'merkel').

tcharding dismissed Kixunil’s stale review via b454cf8 December 10, 2021 00:33

tcharding force-pushed the merkel-root branch from 086f480 to b454cf8 Compare December 10, 2021 00:33

Kixunil approved these changes Dec 10, 2021

View reviewed changes

Kixunil added the API break This PR requires a version bump for the next release label Dec 10, 2021

dr-orlovsky suggested changes Dec 11, 2021

View reviewed changes

src/util/hash.rs Show resolved Hide resolved

dr-orlovsky approved these changes Dec 12, 2021

View reviewed changes

Kixunil removed the one ack PRs that have one ACK, so one more can progress them label Dec 13, 2021

RCasatta merged commit fe43e3c into rust-bitcoin:master Dec 16, 2021

dr-orlovsky mentioned this pull request Jan 15, 2022

Bump version to v0.28 #785

Closed

tcharding deleted the merkel-root branch August 17, 2023 02:49

Conversation

tcharding commented Nov 18, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Kixunil left a comment

Choose a reason for hiding this comment

Uh oh!

dr-orlovsky left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

tcharding commented Nov 24, 2021

Uh oh!

dr-orlovsky left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding Nov 24, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Kixunil Nov 30, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Kixunil left a comment

Choose a reason for hiding this comment

Uh oh!

tcharding commented Nov 24, 2021

Uh oh!

dr-orlovsky commented Nov 24, 2021

Uh oh!

tcharding commented Nov 24, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tcharding commented Nov 24, 2021

Uh oh!

dr-orlovsky commented Nov 25, 2021

Uh oh!

dr-orlovsky left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tcharding commented Dec 2, 2021

Uh oh!

Kixunil left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tcharding commented Dec 3, 2021

Uh oh!

Kixunil commented Dec 3, 2021

Uh oh!

Kixunil left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

tcharding commented Nov 18, 2021 •

edited

Loading

dr-orlovsky left a comment •

edited

Loading

tcharding Nov 24, 2021 •

edited

Loading

Kixunil Nov 30, 2021 •

edited

Loading

tcharding commented Nov 24, 2021 •

edited

Loading