Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

common ancestor should return the youngest ancestor instead of the oldest one #2056

Merged
merged 11 commits into from Mar 29, 2019
Merged

common ancestor should return the youngest ancestor instead of the oldest one #2056

merged 11 commits into from Mar 29, 2019

Conversation

ghost-not-in-the-shell
Copy link
Member

In this PR, I fixed a bug in Transition_frontier.get_path_diff. Namely when we try to find the ancestor for two blocks, we should always try to find the youngest ancestor.

@wu-s-john
Copy link
Contributor

I think it would be useful to have a unit test of this. Can you write one in test_transition_frontier.ml? Shouldn't be tricky. Just create a transition_frontier with a fork of unequal length. Get the breadcrumbs at both ends. Then apply the breadcrumbs to get_path_diff

emberian
emberian requested changes Mar 28, 2019
View reviewed changes
src/lib/transition_frontier/transition_frontier.ml Outdated
@@ -770,6 +770,13 @@ struct
let new_root_node = move_root t heir_node in
(* 4.V *)
let garbage = List.bind bad_hashes ~f:(successor_hashes_rec t) in
Logger.info t.logger ~module_:__MODULE__ ~location:__LOC__
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can you also change this to a Logger.trace?

wu-s-john
wu-s-john suggested changes Mar 28, 2019
View reviewed changes
src/lib/transition_frontier_controller_tests/test_transition_frontier.ml Outdated
Transition_frontier.add_breadcrumb_exn frontier ancestor )
in
let%bind branch1 =
create_breadcrumbs ~logger ~size:(max_length / 2) youngest_ancestor
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Small nit, can you randomly generate a size between 1 and max_legnth/2 for both branches? I want to show in the test that we can retrieve the breadcrumbs successfully even with two uneven branches.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sure, I would do that.

@enolan
Copy link
Contributor

enolan commented Mar 28, 2019

I don't understand what you're saying here. The oldest common ancestor of two breadcrumbs will always be the root of the transition frontier, which is definitely not what it used to return. What is the change? Given this diagram

           -->6-->7-->8
          /
         /
1-->2-->3
         \
          \-->4-->5

What did common_ancestor return when called on 8 and 5 before and what does it return now?

enolan
enolan previously requested changes Mar 28, 2019
View reviewed changes
Copy link
Contributor

@enolan enolan left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good work finding this bug!

src/lib/transition_frontier_controller_tests/test_transition_frontier.ml Outdated
in
let%bind branch1 =
create_breadcrumbs ~logger
~size:(1 + Random.int ((max_length / 2) - 1))
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Use QuickCheck to make this try a bunch of possibilities every time you run the test, rather than picking one each time. Also I think the probability of randomly getting two paths of the same length is very low, so add a test that explicitly checks that situation, since that's where the bug was.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's quite slow to generate breadcrumbs. As a result, we only generate one instance of it. I think it would be a good idea to have a test where the forks have even lengths and where the forks don't have even lengths.

@emberian
Copy link
Member

@enolan is right, the bug only happens on branches of the same length. So instead of chosing randomly, I would just make 2 ancestors and 1 child on each path.

@emberian emberian dismissed enolan’s stale review March 29, 2019 07:15

previously it returned the root if the branches were the same length, but you seem to have figured that out.

@emberian emberian added the ready-to-merge Adding this label will trigger mergify and trigger CI to run and merge the PR label Mar 29, 2019
@mergify mergify bot merged commit ed8e28c into master Mar 29, 2019
@mergify mergify bot deleted the fix/common-ancestor branch March 29, 2019 07:28
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@wu-s-john wu-s-john wu-s-john approved these changes

@emberian emberian emberian approved these changes

@enolan enolan enolan left review comments

Assignees
No one assigned
Labels
ready-to-merge Adding this label will trigger mergify and trigger CI to run and merge the PR
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@ghost-not-in-the-shell @wu-s-john @enolan @emberian