Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Johannes Schindelin]

Hi Junio,

On Tue, 23 Jan 2018, Junio C Hamano wrote:

> Johannes Schindelin  writes:
> 
> > structure (similar in spirit to --preserve-merges, but with a
> > substantially less-broken design).
> > ...
> > @@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
> > ignore_footer, unsigned flag)
> > strbuf_release();
> >  }
> >  
> > +struct labels_entry {
> > +   struct hashmap_entry entry;
> > +   char label[FLEX_ARRAY];
> > +};
> > +
> > +static int labels_cmp(const void *fndata, const struct labels_entry *a,
> > + const struct labels_entry *b, const void *key)
> > +{
> > +   return key ? strcmp(a->label, key) : strcmp(a->label, b->label);
> > +}
> 
> label_oid() accesses state->labels hash using strihash() as the hash
> function, but the final comparison between the entries in the same
> hash buckets are done with case sensitivity.  It is unclear to me if
> that is what was intended, and why.

Heh... you were almost there with your analysis. strihash() is needed for
case-insensitive comparisons, and labels are... ref names.

So the idea (which I implemented only partially) was to make the labels
case-insensitive based on `ignore_case`.

I think the best way forward will be to copy
merge-recursive.c:path_hash().

> > +struct string_entry {
> > +   struct oidmap_entry entry;
> > +   char string[FLEX_ARRAY];
> > +};
> > +
> > +struct label_state {
> > +   struct oidmap commit2label;
> > +   struct hashmap labels;
> > +   struct strbuf buf;
> > +};
> > +
> > +static const char *label_oid(struct object_id *oid, const char *label,
> > +struct label_state *state)
> > +{
> > +   struct labels_entry *labels_entry;
> > +   struct string_entry *string_entry;
> > +   struct object_id dummy;
> > +   size_t len;
> > +   int i;
> > +
> > +   string_entry = oidmap_get(>commit2label, oid);
> > +   if (string_entry)
> > +   return string_entry->string;
> > +
> > +   /*
> > +* For "uninteresting" commits, i.e. commits that are not to be
> > +* rebased, and which can therefore not be labeled, we use a unique
> > +* abbreviation of the commit name. This is slightly more complicated
> > +* than calling find_unique_abbrev() because we also need to make
> > +* sure that the abbreviation does not conflict with any other
> > +* label.
> > +*
> > +* We disallow "interesting" commits to be labeled by a string that
> > +* is a valid full-length hash, to ensure that we always can find an
> > +* abbreviation for any uninteresting commit's names that does not
> > +* clash with any other label.
> > +*/
> > +   if (!label) {
> > +   char *p;
> > +
> > +   strbuf_reset(>buf);
> > +   strbuf_grow(>buf, GIT_SHA1_HEXSZ);
> > +   label = p = state->buf.buf;
> > +
> > +   find_unique_abbrev_r(p, oid->hash, default_abbrev);
> > +
> > +   /*
> > +* We may need to extend the abbreviated hash so that there is
> > +* no conflicting label.
> > +*/
> > +   if (hashmap_get_from_hash(>labels, strihash(p), p)) {
> > +   size_t i = strlen(p) + 1;
> > +
> > +   oid_to_hex_r(p, oid);
> > +   for (; i < GIT_SHA1_HEXSZ; i++) {
> > +   char save = p[i];
> > +   p[i] = '\0';
> > +   if (!hashmap_get_from_hash(>labels,
> > +  strihash(p), p))
> > +   break;
> > +   p[i] = save;
> > +   }
> > +   }
> 
> If oid->hash required full 40-hex to disambiguate, then
> find-unique-abbrev would give 40-hex and we'd want the same "-"
> suffix technique employed below to make it consistently unique.  I
> wonder if organizing the function this way ...
> 
>   if (!label)
>   label = oid-to-hex(oid);
> 
>   if (label already exists or full oid) {
>   make it unambiguous;
>   }

It was hard to miss, I agree. The first arm of the if() is not trying to
make a label unambiguous by adding `-`, but by extending the
abbreviated 40-hex until it is unique. (And we guarantee that there is a
solution, as we do not allow valid 40-hex strings to be used as label.)

The reason: if no `label` is provided, we want a valid raw (possibly
abbreviated) commit name. If `label` is provided, we want a valid ref name
(possibly made unique by appending `-`).

Different beasts. Cannot be put into the same if() arm.

> A related tangent.  Does an auto-label given to "uninteresting"
> commit need to be visible to end users?

Yes. The reason for this is the `merge`/`reset` commands when *not*
rebasing cousins. Because in that case, we have to refer to commits that
we could not possibly have `label`ed, because they were never the current
revision. Therefore we cannot assign - labels, but 

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Johannes Schindelin]

Hi Junio,

On Tue, 23 Jan 2018, Junio C Hamano wrote:

> Eric Sunshine  writes:
> 
> >> +   is_octopus = to_merge && to_merge->next;
> >> +
> >> +   if (is_octopus)
> >> +   BUG("Octopus merges not yet supported");
> >
> > Is this a situation which the end-user can trigger by specifying a
> > merge with more than two parents? If so, shouldn't this be just a
> > normal error message rather than a (developer) bug message? Or, am I
> > misunderstanding?
> 
> BUG() is "we wrote code carefully so that this should not trigger;
> we do not _expect_ the code to reach here".  This one is expected to
> trigger, and I agree with you that it should be die(), if the series
> is meant to be released to the general public in the current form
> (i.e. until the limitation is lifted so that it can handle an
> octopus).
> 
> If the callers are made more careful to check if there is an octopus
> involved and reject the request early, then seeing an octopus in
> this location in a loop will become a BUG().

This has occupied both of you for way too long.

It is *not interesting*. What *is* interesting is for example the
discussion about the "cousin commits". And maybe both of you gentle
persons can spend your brain cycles splendidly by trying to come up with a
better term. Or by trying to beat out obvious or not-so-obvious bugs in
the code.

Seriously, I am not interested in a discussion about BUG() vs die() as
long as there may be real bugs hiding.

Ciao,
Dscho

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Johannes Schindelin]

Hi Eric,

On Fri, 19 Jan 2018, Eric Sunshine wrote:

> On Thu, Jan 18, 2018 at 10:35 AM, Johannes Schindelin
>  wrote:
> 
> > structure (similar in spirit to --preserve-merges, but with a
> > substantially less-broken design).
> > [...]
> > Signed-off-by: Johannes Schindelin 
> > ---
> > diff --git a/sequencer.c b/sequencer.c
> > @@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
> > ignore_footer, unsigned flag)
> > +static const char *label_oid(struct object_id *oid, const char *label,
> > +struct label_state *state)
> > +{
> > +   [...]
> > +   } else if (((len = strlen(label)) == GIT_SHA1_RAWSZ &&
> > +   !get_oid_hex(label, )) ||
> > +  hashmap_get_from_hash(>labels,
> > +strihash(label), label)) {
> > +   /*
> > +* If the label already exists, or if the label is a valid 
> > full
> > +* OID, we append a dash and a number to make it unique.
> > +*/
> > +   [...]
> > +   for (i = 2; ; i++) {
> 
> Why '2'? Is there some non-obvious significance to this value?

I personally found it irritating to have labels "sequencer",
"sequencer-1". It sounds *wrong* to have a "-1". Because it is the second
label referring to the term "sequencer". So if there are two labels that
both want to be named "sequencer", the first one wins, and the second one
will be called "sequencer-2".

Hence the 2.

> > +static int make_script_with_merges(struct pretty_print_context *pp,
> > +  struct rev_info *revs, FILE *out,
> > +  unsigned flags)
> > +{
> > +   [...]
> > +   is_octopus = to_merge && to_merge->next;
> > +
> > +   if (is_octopus)
> > +   BUG("Octopus merges not yet supported");
> 
> Is this a situation which the end-user can trigger by specifying a
> merge with more than two parents? If so, shouldn't this be just a
> normal error message rather than a (developer) bug message? Or, am I
> misunderstanding?

You are misunderstanding.

This is just a place-holder here. The patches to introduce support for
octopus merges are already written. They are lined up after this here
patch series, is all.

As such, please do not occupy your mind on the specifics or even the
upper-case of the "Octopus". This line is here only as a hint for the
reviewer that this is not yet implemented. And BUG(...) was chosen because
that way, we are not even tempted to waste the time of translators.

Speaking of wasting time... let's move on to further interesting code
reviews.

Ciao,
Dscho

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Junio C Hamano]

Eric Sunshine  writes:

>> +   is_octopus = to_merge && to_merge->next;
>> +
>> +   if (is_octopus)
>> +   BUG("Octopus merges not yet supported");
>
> Is this a situation which the end-user can trigger by specifying a
> merge with more than two parents? If so, shouldn't this be just a
> normal error message rather than a (developer) bug message? Or, am I
> misunderstanding?

BUG() is "we wrote code carefully so that this should not trigger;
we do not _expect_ the code to reach here".  This one is expected to
trigger, and I agree with you that it should be die(), if the series
is meant to be released to the general public in the current form
(i.e. until the limitation is lifted so that it can handle an
octopus).

If the callers are made more careful to check if there is an octopus
involved and reject the request early, then seeing an octopus in
this location in a loop will become a BUG().

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Junio C Hamano]

Johannes Schindelin  writes:

> The sequencer just learned a new commands intended to recreate branch

s/a //;

> structure (similar in spirit to --preserve-merges, but with a
> substantially less-broken design).
> ...
> @@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
> ignore_footer, unsigned flag)
>   strbuf_release();
>  }
>  
> +struct labels_entry {
> + struct hashmap_entry entry;
> + char label[FLEX_ARRAY];
> +};
> +
> +static int labels_cmp(const void *fndata, const struct labels_entry *a,
> +   const struct labels_entry *b, const void *key)
> +{
> + return key ? strcmp(a->label, key) : strcmp(a->label, b->label);
> +}

label_oid() accesses state->labels hash using strihash() as the hash
function, but the final comparison between the entries in the same
hash buckets are done with case sensitivity.  It is unclear to me if
that is what was intended, and why.

> +struct string_entry {
> + struct oidmap_entry entry;
> + char string[FLEX_ARRAY];
> +};
> +
> +struct label_state {
> + struct oidmap commit2label;
> + struct hashmap labels;
> + struct strbuf buf;
> +};
> +
> +static const char *label_oid(struct object_id *oid, const char *label,
> +  struct label_state *state)
> +{
> + struct labels_entry *labels_entry;
> + struct string_entry *string_entry;
> + struct object_id dummy;
> + size_t len;
> + int i;
> +
> + string_entry = oidmap_get(>commit2label, oid);
> + if (string_entry)
> + return string_entry->string;
> +
> + /*
> +  * For "uninteresting" commits, i.e. commits that are not to be
> +  * rebased, and which can therefore not be labeled, we use a unique
> +  * abbreviation of the commit name. This is slightly more complicated
> +  * than calling find_unique_abbrev() because we also need to make
> +  * sure that the abbreviation does not conflict with any other
> +  * label.
> +  *
> +  * We disallow "interesting" commits to be labeled by a string that
> +  * is a valid full-length hash, to ensure that we always can find an
> +  * abbreviation for any uninteresting commit's names that does not
> +  * clash with any other label.
> +  */
> + if (!label) {
> + char *p;
> +
> + strbuf_reset(>buf);
> + strbuf_grow(>buf, GIT_SHA1_HEXSZ);
> + label = p = state->buf.buf;
> +
> + find_unique_abbrev_r(p, oid->hash, default_abbrev);
> +
> + /*
> +  * We may need to extend the abbreviated hash so that there is
> +  * no conflicting label.
> +  */
> + if (hashmap_get_from_hash(>labels, strihash(p), p)) {
> + size_t i = strlen(p) + 1;
> +
> + oid_to_hex_r(p, oid);
> + for (; i < GIT_SHA1_HEXSZ; i++) {
> + char save = p[i];
> + p[i] = '\0';
> + if (!hashmap_get_from_hash(>labels,
> +strihash(p), p))
> + break;
> + p[i] = save;
> + }
> + }

If oid->hash required full 40-hex to disambiguate, then
find-unique-abbrev would give 40-hex and we'd want the same "-"
suffix technique employed below to make it consistently unique.  I
wonder if organizing the function this way ...

if (!label)
label = oid-to-hex(oid);

if (label already exists or full oid) {
make it unambiguous;
}

... allows the resulting code easier to understand and manage.

A related tangent.  Does an auto-label given to "uninteresting"
commit need to be visible to end users?  I doubted it and that is
why I said oid-to-hex in the above, but if it is given to end users,
use of find-unique-abbrev-r is perfectly fine.

> +static int make_script_with_merges(struct pretty_print_context *pp,
> +struct rev_info *revs, FILE *out,
> +unsigned flags)
> +{
> + ...
> + int abbr = flags & TODO_LIST_ABBREVIATE_CMDS;
> + const char *p = abbr ? "p" : "pick", *l = abbr ? "l" : "label",
> +  *t = abbr ? "t" : "reset", *b = abbr ? "b" : "bud",
> +  *m = abbr ? "m" : "merge";

It would be easier to understand if these short named variables are
reserved only for temporary use, not as constants.  It is not too
much to spell 

fprintf(out, "%s onto\n", cmd_label);

than

fprintf(out, "%s onto\n", l);

and would save readers from head-scratching, wondering where the
last assignment to variable "l" is.

> +
> + oidmap_init(, 0);
> + oidmap_init(, 0);
> + hashmap_init(, (hashmap_cmp_fn) labels_cmp, NULL, 0);
> + strbuf_init(, 32);
> +
> + if (revs->cmdline.nr && 

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Eric Sunshine]

On Thu, Jan 18, 2018 at 10:35 AM, Johannes Schindelin
 wrote:
> The sequencer just learned a new commands intended to recreate branch

s/a //

> structure (similar in spirit to --preserve-merges, but with a
> substantially less-broken design).
> [...]
> Signed-off-by: Johannes Schindelin 
> ---
> diff --git a/sequencer.c b/sequencer.c
> @@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
> ignore_footer, unsigned flag)
> +static const char *label_oid(struct object_id *oid, const char *label,
> +struct label_state *state)
> +{
> +   [...]
> +   } else if (((len = strlen(label)) == GIT_SHA1_RAWSZ &&
> +   !get_oid_hex(label, )) ||
> +  hashmap_get_from_hash(>labels,
> +strihash(label), label)) {
> +   /*
> +* If the label already exists, or if the label is a valid 
> full
> +* OID, we append a dash and a number to make it unique.
> +*/
> +   [...]
> +   for (i = 2; ; i++) {

Why '2'? Is there some non-obvious significance to this value?

> +   strbuf_setlen(buf, len);
> +   strbuf_addf(buf, "-%d", i);
> +   if (!hashmap_get_from_hash(>labels,
> +  strihash(buf->buf),
> +  buf->buf))
> +   break;
> +   }
> +
> +static int make_script_with_merges(struct pretty_print_context *pp,
> +  struct rev_info *revs, FILE *out,
> +  unsigned flags)
> +{
> +   [...]
> +   is_octopus = to_merge && to_merge->next;
> +
> +   if (is_octopus)
> +   BUG("Octopus merges not yet supported");

Is this a situation which the end-user can trigger by specifying a
merge with more than two parents? If so, shouldn't this be just a
normal error message rather than a (developer) bug message? Or, am I
misunderstanding?

Re: [PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Philip Oakley]

From: "Johannes Schindelin" 

The sequencer just learned a new commands intended to recreate branch
structure (similar in spirit to --preserve-merges, but with a
substantially less-broken design).

Let's allow the rebase--helper to generate todo lists making use of
these commands, triggered by the new --recreate-merges option. For a
commit topology like this:

A - B - C
  \   /
D


Could the topology include the predecessor for context. Alo it is easy for 
readers to become confused between the arcs of the graphs and the nodes of 
the graphs, such that we confuse 'commits as patches' with 'commits as 
snapshots'. It might need an 'Aa' distinction between the two types, 
especially around merges and potential evilness.




the generated todo list would look like this:

# branch D
pick 0123 A
label branch-point
pick 1234 D
label D

reset branch-point
pick 2345 B
merge 3456 D C

To keep things simple, we first only implement support for merge commits
with exactly two parents, leaving support for octopus merges to a later
patch in this patch series.

Signed-off-by: Johannes Schindelin 
---
builtin/rebase--helper.c |   4 +-
sequencer.c  | 343 
++-

sequencer.h  |   1 +
3 files changed, 345 insertions(+), 3 deletions(-)

diff --git a/builtin/rebase--helper.c b/builtin/rebase--helper.c
index 7daee544b7b..a34ab5c0655 100644
--- a/builtin/rebase--helper.c
+++ b/builtin/rebase--helper.c
@@ -12,7 +12,7 @@ static const char * const builtin_rebase_helper_usage[] 
= {

int cmd_rebase__helper(int argc, const char **argv, const char *prefix)
{
 struct replay_opts opts = REPLAY_OPTS_INIT;
- unsigned flags = 0, keep_empty = 0;
+ unsigned flags = 0, keep_empty = 0, recreate_merges = 0;
 int abbreviate_commands = 0;
 enum {
 CONTINUE = 1, ABORT, MAKE_SCRIPT, SHORTEN_OIDS, EXPAND_OIDS,
@@ -22,6 +22,7 @@ int cmd_rebase__helper(int argc, const char **argv, 
const char *prefix)

 struct option options[] = {
 OPT_BOOL(0, "ff", _ff, N_("allow fast-forward")),
 OPT_BOOL(0, "keep-empty", _empty, N_("keep empty commits")),
+ OPT_BOOL(0, "recreate-merges", _merges, N_("recreate merge 
commits")),

 OPT_CMDMODE(0, "continue", , N_("continue rebase"),
 CONTINUE),
 OPT_CMDMODE(0, "abort", , N_("abort rebase"),
@@ -55,6 +56,7 @@ int cmd_rebase__helper(int argc, const char **argv, 
const char *prefix)


 flags |= keep_empty ? TODO_LIST_KEEP_EMPTY : 0;
 flags |= abbreviate_commands ? TODO_LIST_ABBREVIATE_CMDS : 0;
+ flags |= recreate_merges ? TODO_LIST_RECREATE_MERGES : 0;
 flags |= command == SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;

 if (command == CONTINUE && argc == 1)
diff --git a/sequencer.c b/sequencer.c
index a96255426e7..1bef16647b4 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -23,6 +23,8 @@
#include "hashmap.h"
#include "unpack-trees.h"
#include "worktree.h"
+#include "oidmap.h"
+#include "oidset.h"

#define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"

@@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
ignore_footer, unsigned flag)

 strbuf_release();
}

+struct labels_entry {
+ struct hashmap_entry entry;
+ char label[FLEX_ARRAY];
+};
+
+static int labels_cmp(const void *fndata, const struct labels_entry *a,
+   const struct labels_entry *b, const void *key)
+{
+ return key ? strcmp(a->label, key) : strcmp(a->label, b->label);
+}
+
+struct string_entry {
+ struct oidmap_entry entry;
+ char string[FLEX_ARRAY];
+};
+
+struct label_state {
+ struct oidmap commit2label;
+ struct hashmap labels;
+ struct strbuf buf;
+};
+
+static const char *label_oid(struct object_id *oid, const char *label,
+  struct label_state *state)
+{
+ struct labels_entry *labels_entry;
+ struct string_entry *string_entry;
+ struct object_id dummy;
+ size_t len;
+ int i;
+
+ string_entry = oidmap_get(>commit2label, oid);
+ if (string_entry)
+ return string_entry->string;
+
+ /*
+ * For "uninteresting" commits, i.e. commits that are not to be
+ * rebased, and which can therefore not be labeled, we use a unique
+ * abbreviation of the commit name. This is slightly more complicated
+ * than calling find_unique_abbrev() because we also need to make
+ * sure that the abbreviation does not conflict with any other
+ * label.
+ *
+ * We disallow "interesting" commits to be labeled by a string that
+ * is a valid full-length hash, to ensure that we always can find an
+ * abbreviation for any uninteresting commit's names that does not
+ * clash with any other label.
+ */
+ if (!label) {
+ char *p;
+
+ strbuf_reset(>buf);
+ strbuf_grow(>buf, GIT_SHA1_HEXSZ);
+ label = p = state->buf.buf;
+
+ find_unique_abbrev_r(p, oid->hash, default_abbrev);
+
+ /*
+ * We may need to extend the abbreviated hash so that there is
+ * no conflicting label.
+ */
+ if (hashmap_get_from_hash(>labels, strihash(p), p)) {
+ size_t i = strlen(p) + 1;
+
+ oid_to_hex_r(p, oid);
+ for (; i < GIT_SHA1_HEXSZ; i++) {
+ char save = p[i];
+ p[i] = '\0';

[PATCH 4/8] rebase-helper --make-script: introduce a flag to recreate merges

[Johannes Schindelin]

The sequencer just learned a new commands intended to recreate branch
structure (similar in spirit to --preserve-merges, but with a
substantially less-broken design).

Let's allow the rebase--helper to generate todo lists making use of
these commands, triggered by the new --recreate-merges option. For a
commit topology like this:

A - B - C
  \   /
D

the generated todo list would look like this:

# branch D
pick 0123 A
label branch-point
pick 1234 D
label D

reset branch-point
pick 2345 B
merge 3456 D C

To keep things simple, we first only implement support for merge commits
with exactly two parents, leaving support for octopus merges to a later
patch in this patch series.

Signed-off-by: Johannes Schindelin 
---
 builtin/rebase--helper.c |   4 +-
 sequencer.c  | 343 ++-
 sequencer.h  |   1 +
 3 files changed, 345 insertions(+), 3 deletions(-)

diff --git a/builtin/rebase--helper.c b/builtin/rebase--helper.c
index 7daee544b7b..a34ab5c0655 100644
--- a/builtin/rebase--helper.c
+++ b/builtin/rebase--helper.c
@@ -12,7 +12,7 @@ static const char * const builtin_rebase_helper_usage[] = {
 int cmd_rebase__helper(int argc, const char **argv, const char *prefix)
 {
struct replay_opts opts = REPLAY_OPTS_INIT;
-   unsigned flags = 0, keep_empty = 0;
+   unsigned flags = 0, keep_empty = 0, recreate_merges = 0;
int abbreviate_commands = 0;
enum {
CONTINUE = 1, ABORT, MAKE_SCRIPT, SHORTEN_OIDS, EXPAND_OIDS,
@@ -22,6 +22,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
char *prefix)
struct option options[] = {
OPT_BOOL(0, "ff", _ff, N_("allow fast-forward")),
OPT_BOOL(0, "keep-empty", _empty, N_("keep empty 
commits")),
+   OPT_BOOL(0, "recreate-merges", _merges, N_("recreate 
merge commits")),
OPT_CMDMODE(0, "continue", , N_("continue rebase"),
CONTINUE),
OPT_CMDMODE(0, "abort", , N_("abort rebase"),
@@ -55,6 +56,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
char *prefix)
 
flags |= keep_empty ? TODO_LIST_KEEP_EMPTY : 0;
flags |= abbreviate_commands ? TODO_LIST_ABBREVIATE_CMDS : 0;
+   flags |= recreate_merges ? TODO_LIST_RECREATE_MERGES : 0;
flags |= command == SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;
 
if (command == CONTINUE && argc == 1)
diff --git a/sequencer.c b/sequencer.c
index a96255426e7..1bef16647b4 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -23,6 +23,8 @@
 #include "hashmap.h"
 #include "unpack-trees.h"
 #include "worktree.h"
+#include "oidmap.h"
+#include "oidset.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -2785,6 +2787,335 @@ void append_signoff(struct strbuf *msgbuf, int 
ignore_footer, unsigned flag)
strbuf_release();
 }
 
+struct labels_entry {
+   struct hashmap_entry entry;
+   char label[FLEX_ARRAY];
+};
+
+static int labels_cmp(const void *fndata, const struct labels_entry *a,
+ const struct labels_entry *b, const void *key)
+{
+   return key ? strcmp(a->label, key) : strcmp(a->label, b->label);
+}
+
+struct string_entry {
+   struct oidmap_entry entry;
+   char string[FLEX_ARRAY];
+};
+
+struct label_state {
+   struct oidmap commit2label;
+   struct hashmap labels;
+   struct strbuf buf;
+};
+
+static const char *label_oid(struct object_id *oid, const char *label,
+struct label_state *state)
+{
+   struct labels_entry *labels_entry;
+   struct string_entry *string_entry;
+   struct object_id dummy;
+   size_t len;
+   int i;
+
+   string_entry = oidmap_get(>commit2label, oid);
+   if (string_entry)
+   return string_entry->string;
+
+   /*
+* For "uninteresting" commits, i.e. commits that are not to be
+* rebased, and which can therefore not be labeled, we use a unique
+* abbreviation of the commit name. This is slightly more complicated
+* than calling find_unique_abbrev() because we also need to make
+* sure that the abbreviation does not conflict with any other
+* label.
+*
+* We disallow "interesting" commits to be labeled by a string that
+* is a valid full-length hash, to ensure that we always can find an
+* abbreviation for any uninteresting commit's names that does not
+* clash with any other label.
+*/
+   if (!label) {
+   char *p;
+
+   strbuf_reset(>buf);
+   strbuf_grow(>buf, GIT_SHA1_HEXSZ);
+   label = p = state->buf.buf;
+
+   find_unique_abbrev_r(p, oid->hash, default_abbrev);
+
+   /*
+* We may need to extend the abbreviated hash so