Re: [PATCH v2] name-rev: prefer shorter names over following merges

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi Elijah,

On Sat, 4 Dec 2021, Elijah Newren via GitGitGadget wrote:

> Range-diff vs v1:
>
>  1:  50812ed6fdf ! 1:  5d068486f9f name-rev: prefer shorter names over following merges
>      @@ Commit message
>           the printed name over fewer total parent traversals performed to get the
>           answer.
>
>      +    == Side-note on tie-breakers ==
>      +
>      +    When there are the same number of segments for two different names, we
>      +    actually use the name of an ancestor commit as a tie-breaker as well.
>      +    For example, for the commit cbdca289fb in the git.git repository, we
>      +    prefer the name v2.33.0-rc0~112^2~1 over v2.33.0-rc0~57^2~5.  This is
>      +    because:
>      +
>      +      * cbdca289fb is the parent of 25e65b6dd5, which implies the name for
>      +        cbdca289fb should be the first parent of the preferred name for
>      +        25e65b6dd5
>      +      * 25e65b6dd5 could be named either v2.33.0-rc0~112^2 or
>      +        v2.33.0-rc0~57^2~4, but the former is preferred over the latter due
>      +        to fewer segments
>      +      * combine the two previous facts, and the name we get for cbdca289fb
>      +        is "v2.33.0-rc0~112^2~1" rather than "v2.33.0-rc0~57^2~5".
>      +
>      +    Technically, we get this for free out of the implementation since we
>      +    only keep track of one name for each commit as we walk history (and
>      +    re-add parents to the queue if we find a better name for those parents),
>      +    but the first bullet point above ensures users get results that feel
>      +    more consistent.
>      +
>      +    == Alternative Ideas and Meanings Discussed ==
>      +
>      +    One suggestion that came up during review was that shortest
>      +    string-length might be easiest for users to consume.  However, such a
>      +    scheme would be rather computationally expensive (we'd have to track all
>      +    names for each commit as we traversed the graph) and would additionally
>      +    come with the possibly perplexing result that on a linear segment of
>      +    history we could rapidly swap back and forth on names:
>      +       MYTAG~3^2     would     be preferred over   MYTAG~9998
>      +       MYTAG~3^2~1   would NOT be preferred over   MYTAG~9999
>      +       MYTAG~3^2~2   might     be preferred over   MYTAG~10000
>      +
>      +    Another item that came up was possible auxiliary semantic meanings for
>      +    name-rev results either before or after this patch.  The basic answer
>      +    was that the previous implementation had no known useful auxiliary
>      +    semantics, but that for many repositories (most in my experience), the
>      +    new scheme does.  In particular, the new name-rev output can often be
>      +    used to answer the question, "How or when did this commit get merged?"
>      +    Since that usefulness depends on how merges happen within the repository
>      +    and thus isn't universally applicable, details are omitted here but you
>      +    can see them at [1].
>      +
>      +    [1] https://lore.kernel.org/git/CABPp-BEeUM+3NLKDVdak90_UUeNghYCx=Dgir6=8ixvYmvyq3Q@mail.gmail.com/
>      +
>      +    Finally, it was noted that the algorithm could be improved by just
>      +    explicitly tracking the number of segments and using both it and
>      +    distance in the comparison, instead of giving a magic number that tries
>      +    to blend the two (and which therefore might give suboptimal results in
>      +    repositories with really huge numbers of commits that periodically merge
>      +    older code).  However, "[this patch] seems to give us a much better
>      +    results than the current code, so let's take it and leave further
>      +    futzing outside the scope."
>      +
>           Signed-off-by: Elijah Newren <newren@gmail.com>

Very nice addition!

And obviously, I am still in favor of moving this patch along in the
direction of `main`.

Thank you,
Dscho