Skip to content

findMergeBase uses naive LCA algorithm designed for Trees, not DAGs #2109

@wavim

Description

@wavim

Consider the following commit graph

HEAD | \ A F B | C | D | | / E 

For the merge base of HEAD and C, the naive algorithm used by isomorphic-git
will return E as the merge base, as the walkers reach E first.

But the best merge base would be C itself, being an ancestor of HEAD already,
with total distance of 3 as opposed to 4 for E.

Without retrieving or computing generation numbers this will never get quite right.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions