From d91ce887c936affbbf24ab2461d924ad1c6eefc7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:09 +0100 Subject: t6120-describe: correct test repo history graph in comment MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit At the top of 't6120-describe.sh' an ASCII graph illustrates the repository's history used in this test script. This graph is a bit misleading, because it swapped the second merge commit's first and second parents. When describing/naming a commit it does make a difference which parent is the first and which is the second/Nth, so update this graph to accurately represent that second merge. While at it, move this history graph from the 'test_description' variable to a regular comment. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh index 45047d0..9b18417 100755 --- a/t/t6120-describe.sh +++ b/t/t6120-describe.sh @@ -1,15 +1,16 @@ #!/bin/sh -test_description='test describe +test_description='test describe' + +# o---o-----o----o----o-------o----x +# \ D,R e / +# \---o-------------o-' +# \ B / +# `-o----o----o-' +# A c +# +# First parent of a merge commit is on the same line, second parent below. - B - .--------------o----o----o----x - / / / - o----o----o----o----o----. / - \ A c / - .------------o---o---o - D,R e -' . ./test-lib.sh check_describe () { -- cgit v0.10.2-6-g49f6 From c593a2634837234c91afc875cb569a53fbaadbfb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:10 +0100 Subject: t6120-describe: modernize the 'check_describe' helper MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The 'check_describe' helper function runs 'git describe' outside of 'test_expect_success' blocks, with extra hand-rolled code to record and examine its exit code. Update this helper and move the 'git describe' invocation inside the 'test_expect_success' block. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh index 9b18417..a2988fa 100755 --- a/t/t6120-describe.sh +++ b/t/t6120-describe.sh @@ -16,14 +16,12 @@ test_description='test describe' check_describe () { expect="$1" shift - R=$(git describe "$@" 2>err.actual) - S=$? - cat err.actual >&3 - test_expect_success "describe $*" ' - test $S = 0 && + describe_opts="$@" + test_expect_success "describe $describe_opts" ' + R=$(git describe $describe_opts 2>err.actual) && case "$R" in $expect) echo happy ;; - *) echo "Oops - $R is not $expect"; + *) echo "Oops - $R is not $expect" && false ;; esac ' -- cgit v0.10.2-6-g49f6 From c3794d4ccb70c6b36be3fd4981682f422b04de05 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Tue, 12 Nov 2019 11:38:11 +0100 Subject: name-rev: use strbuf_strip_suffix() in get_rev_name() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit get_name_rev() basically open-codes strip_suffix() before adding a string to a strbuf. Let's use the strbuf right from the beginning, i.e. add the whole string to the strbuf and then use strbuf_strip_suffix(), making the code more idiomatic. Signed-off-by: René Scharfe Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index b0f0776..15919ad 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -321,11 +321,10 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf) if (!n->generation) return n->tip_name; else { - int len = strlen(n->tip_name); - if (len > 2 && !strcmp(n->tip_name + len - 2, "^0")) - len -= 2; strbuf_reset(buf); - strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation); + strbuf_addstr(buf, n->tip_name); + strbuf_strip_suffix(buf, "^0"); + strbuf_addf(buf, "~%d", n->generation); return buf->buf; } } -- cgit v0.10.2-6-g49f6 From e0c4da6f2adcede27fb097337c71f7b377a074a1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:12 +0100 Subject: name-rev: avoid unnecessary cast in name_ref() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Casting a 'struct object' to 'struct commit' is unnecessary there, because it's already available in the local 'commit' variable. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 15919ad..e40f51c 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -272,7 +272,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo int from_tag = starts_with(path, "refs/tags/"); if (taggerdate == TIME_MAX) - taggerdate = ((struct commit *)o)->date; + taggerdate = commit->date; path = name_ref_abbrev(path, can_abbreviate_output); name_rev(commit, xstrdup(path), taggerdate, 0, 0, from_tag, deref); -- cgit v0.10.2-6-g49f6 From bf43abc6e60fc9732a287f529a6cedcbdfe2a74c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:13 +0100 Subject: name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index e40f51c..7e003c2 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -102,7 +102,7 @@ static void name_rev(struct commit *commit, } if (name == NULL) { - name = xmalloc(sizeof(rev_name)); + name = xmalloc(sizeof(*name)); set_commit_rev_name(commit, name); goto copy_data; } else if (is_better_name(name, taggerdate, distance, from_tag)) { -- cgit v0.10.2-6-g49f6 From d59fc8369703eda30e02943d0e4884df90061af8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:14 +0100 Subject: t6120: add a test to cover inner conditions in 'git name-rev's name_rev() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit In 'builtin/name-rev.c' in the name_rev() function there is a loop iterating over all parents of the given commit, and the loop body looks like this: if (parent_number > 1) { if (generation > 0) // branch #1 new_name = ... else // branch #2 new_name = ... name_rev(parent, new_name, ...); } else { // branch #3 name_rev(...); } These conditions are not covered properly in the test suite. As far as purely test coverage goes, they are all executed several times over in 't6120-describe.sh'. However, they don't directly influence the command's output, because the repository used in that test script contains several branches and tags pointing somewhere into the middle of the commit DAG, and thus result in a better name for the to-be-named commit. This can hide bugs: e.g. by replacing the 'new_name' parameter of the first recursive name_rev() call with 'tip_name' (effectively making both branch #1 and #2 a noop) 'git name-rev --all' shows thousands of bogus names in the Git repository, but the whole test suite still passes successfully. In an early version of a later patch in this series I managed to mess up all three branches (at once!), but the test suite still passed. So add a new test case that operates on the following history: A--------------master \ / \----------M2 \ / \---M1-C \ / B and names the commit 'B' to make sure that all three branches are crucial to determine 'B's name: - There is only a single ref, so all names are based on 'master', without any undesired interference from other refs. - Each time name_rev() follows the second parent of a merge commit, it appends "^2" to the name. Following 'master's second parent right at the start ensures that all commits on the ancestry path from 'master' to 'B' have a different base name from the original 'tip_name' of the very first name_rev() invocation. Currently, while name_rev() is recursive, it doesn't matter, but it will be necessary to properly cover all three branches after the recursion is eliminated later in this series. - Following 'M2's second parent makes sure that branch #2 (i.e. when 'generation = 0') affects 'B's name. - Following the only parent of the non-merge commit 'C' ensures that branch #3 affects 'B's name, and that it increments 'generation'. - Coming from 'C' 'generation' is 1, thus following 'M1's second parent makes sure that branch #1 affects 'B's name. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh index a2988fa..0d119e9 100755 --- a/t/t6120-describe.sh +++ b/t/t6120-describe.sh @@ -438,4 +438,45 @@ test_expect_success 'name-rev a rev shortly after epoch' ' test_cmp expect actual ' +# A--------------master +# \ / +# \----------M2 +# \ / +# \---M1-C +# \ / +# B +test_expect_success 'name-rev covers all conditions while looking at parents' ' + git init repo && + ( + cd repo && + + echo A >file && + git add file && + git commit -m A && + A=$(git rev-parse HEAD) && + + git checkout --detach && + echo B >file && + git commit -m B file && + B=$(git rev-parse HEAD) && + + git checkout $A && + git merge --no-ff $B && # M1 + + echo C >file && + git commit -m C file && + + git checkout $A && + git merge --no-ff HEAD@{1} && # M2 + + git checkout master && + git merge --no-ff HEAD@{1} && + + echo "$B master^2^2~1^2" >expect && + git name-rev $B >actual && + + test_cmp expect actual + ) +' + test_done -- cgit v0.10.2-6-g49f6 From 766f9e39c007f527c5ab63d65a0d8ff9d36e2a2e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:15 +0100 Subject: name-rev: extract creating/updating a 'struct name_rev' into a helper MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit In a later patch in this series we'll want to do this in two places. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 7e003c2..e43df19 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -79,12 +79,36 @@ static int is_better_name(struct rev_name *name, return 0; } +static struct rev_name *create_or_update_name(struct commit *commit, + const char *tip_name, + timestamp_t taggerdate, + int generation, int distance, + int from_tag) +{ + struct rev_name *name = get_commit_rev_name(commit); + + if (name == NULL) { + name = xmalloc(sizeof(*name)); + set_commit_rev_name(commit, name); + goto copy_data; + } else if (is_better_name(name, taggerdate, distance, from_tag)) { +copy_data: + name->tip_name = tip_name; + name->taggerdate = taggerdate; + name->generation = generation; + name->distance = distance; + name->from_tag = from_tag; + + return name; + } else + return NULL; +} + static void name_rev(struct commit *commit, const char *tip_name, timestamp_t taggerdate, int generation, int distance, int from_tag, int deref) { - struct rev_name *name = get_commit_rev_name(commit); struct commit_list *parents; int parent_number = 1; char *to_free = NULL; @@ -101,18 +125,8 @@ static void name_rev(struct commit *commit, die("generation: %d, but deref?", generation); } - if (name == NULL) { - name = xmalloc(sizeof(*name)); - set_commit_rev_name(commit, name); - goto copy_data; - } else if (is_better_name(name, taggerdate, distance, from_tag)) { -copy_data: - name->tip_name = tip_name; - name->taggerdate = taggerdate; - name->generation = generation; - name->distance = distance; - name->from_tag = from_tag; - } else { + if (!create_or_update_name(commit, tip_name, taggerdate, generation, + distance, from_tag)) { free(to_free); return; } -- cgit v0.10.2-6-g49f6 From dd090a8a37b4507bf6c79ad93ec076673fa6313c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:16 +0100 Subject: name-rev: pull out deref handling from the recursion MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The 'if (deref) { ... }' condition near the beginning of the recursive name_rev() function can only ever be true in the first invocation, because the 'deref' parameter is always 0 in the subsequent recursive invocations. Extract this condition from the recursion into name_rev()'s caller and drop the function's 'deref' parameter. This makes eliminating the recursion a bit easier to follow, and it will be moved back into name_rev() after the recursion is eliminated. Furthermore, drop the condition that die()s when both 'deref' and 'generation' are non-null (which should have been a BUG() to begin with). Note that this change reintroduces the memory leak that was plugged in in commit 5308224633 (name-rev: avoid leaking memory in the `deref` case, 2017-05-04), but a later patch (name-rev: restructure creating/updating 'struct rev_name' instances) in this series will plug it in again. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index e43df19..e112a92 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -106,30 +106,19 @@ copy_data: static void name_rev(struct commit *commit, const char *tip_name, timestamp_t taggerdate, - int generation, int distance, int from_tag, - int deref) + int generation, int distance, int from_tag) { struct commit_list *parents; int parent_number = 1; - char *to_free = NULL; parse_commit(commit); if (commit->date < cutoff) return; - if (deref) { - tip_name = to_free = xstrfmt("%s^0", tip_name); - - if (generation) - die("generation: %d, but deref?", generation); - } - if (!create_or_update_name(commit, tip_name, taggerdate, generation, - distance, from_tag)) { - free(to_free); + distance, from_tag)) return; - } for (parents = commit->parents; parents; @@ -148,11 +137,11 @@ static void name_rev(struct commit *commit, name_rev(parents->item, new_name, taggerdate, 0, distance + MERGE_TRAVERSAL_WEIGHT, - from_tag, 0); + from_tag); } else { name_rev(parents->item, tip_name, taggerdate, generation + 1, distance + 1, - from_tag, 0); + from_tag); } } } @@ -284,12 +273,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo if (o && o->type == OBJ_COMMIT) { struct commit *commit = (struct commit *)o; int from_tag = starts_with(path, "refs/tags/"); + const char *tip_name; if (taggerdate == TIME_MAX) taggerdate = commit->date; path = name_ref_abbrev(path, can_abbreviate_output); - name_rev(commit, xstrdup(path), taggerdate, 0, 0, - from_tag, deref); + if (deref) + tip_name = xstrfmt("%s^0", path); + else + tip_name = xstrdup(path); + name_rev(commit, tip_name, taggerdate, 0, 0, from_tag); } return 0; } -- cgit v0.10.2-6-g49f6 From dd432a6ecf022b40760dd04fe4e94fdfcb1b270d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:17 +0100 Subject: name-rev: restructure parsing commits and applying date cutoff MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit At the beginning of the recursive name_rev() function it parses the commit it got as parameter, and returns early if the commit is older than a cutoff limit. Restructure this so the caller parses the commit and checks its date, and doesn't invoke name_rev() if the commit to be passed as parameter is older than the cutoff, i.e. both name_ref() before calling name_rev() and name_rev() itself as it iterates over the parent commits. This makes eliminating the recursion a bit easier to follow, and the condition moved to name_ref() will be moved back to name_rev() after the recursion is eliminated. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index e112a92..5041227 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -111,11 +111,6 @@ static void name_rev(struct commit *commit, struct commit_list *parents; int parent_number = 1; - parse_commit(commit); - - if (commit->date < cutoff) - return; - if (!create_or_update_name(commit, tip_name, taggerdate, generation, distance, from_tag)) return; @@ -123,6 +118,12 @@ static void name_rev(struct commit *commit, for (parents = commit->parents; parents; parents = parents->next, parent_number++) { + struct commit *parent = parents->item; + + parse_commit(parent); + if (parent->date < cutoff) + continue; + if (parent_number > 1) { size_t len; char *new_name; @@ -135,11 +136,11 @@ static void name_rev(struct commit *commit, new_name = xstrfmt("%.*s^%d", (int)len, tip_name, parent_number); - name_rev(parents->item, new_name, taggerdate, 0, + name_rev(parent, new_name, taggerdate, 0, distance + MERGE_TRAVERSAL_WEIGHT, from_tag); } else { - name_rev(parents->item, tip_name, taggerdate, + name_rev(parent, tip_name, taggerdate, generation + 1, distance + 1, from_tag); } @@ -273,16 +274,18 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo if (o && o->type == OBJ_COMMIT) { struct commit *commit = (struct commit *)o; int from_tag = starts_with(path, "refs/tags/"); - const char *tip_name; if (taggerdate == TIME_MAX) taggerdate = commit->date; path = name_ref_abbrev(path, can_abbreviate_output); - if (deref) - tip_name = xstrfmt("%s^0", path); - else - tip_name = xstrdup(path); - name_rev(commit, tip_name, taggerdate, 0, 0, from_tag); + if (commit->date >= cutoff) { + const char *tip_name; + if (deref) + tip_name = xstrfmt("%s^0", path); + else + tip_name = xstrdup(path); + name_rev(commit, tip_name, taggerdate, 0, 0, from_tag); + } } return 0; } -- cgit v0.10.2-6-g49f6 From 3a521503019de7ca0c550c3861619bb8881c388c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:18 +0100 Subject: name-rev: restructure creating/updating 'struct rev_name' instances MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit At the beginning of the recursive name_rev() function it creates a new 'struct rev_name' instance for each previously unvisited commit or, if this visit results in better name for an already visited commit, then updates the 'struct rev_name' instance attached to the commit, or returns early. Restructure this so it's caller creates or updates the 'struct rev_name' instance associated with the commit to be passed as parameter, i.e. both name_ref() before calling name_rev() and name_rev() itself as it iterates over the parent commits. This makes eliminating the recursion a bit easier to follow, and the condition moved to name_ref() will be moved back to name_rev() after the recursion is eliminated. This change also plugs the memory leak that was temporarily unplugged in the earlier "name-rev: pull out deref handling from the recursion" patch in this series. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 5041227..6416c49 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -111,14 +111,12 @@ static void name_rev(struct commit *commit, struct commit_list *parents; int parent_number = 1; - if (!create_or_update_name(commit, tip_name, taggerdate, generation, - distance, from_tag)) - return; - for (parents = commit->parents; parents; parents = parents->next, parent_number++) { struct commit *parent = parents->item; + const char *new_name; + int new_generation, new_distance; parse_commit(parent); if (parent->date < cutoff) @@ -126,7 +124,6 @@ static void name_rev(struct commit *commit, if (parent_number > 1) { size_t len; - char *new_name; strip_suffix(tip_name, "^0", &len); if (generation > 0) @@ -135,15 +132,19 @@ static void name_rev(struct commit *commit, else new_name = xstrfmt("%.*s^%d", (int)len, tip_name, parent_number); - - name_rev(parent, new_name, taggerdate, 0, - distance + MERGE_TRAVERSAL_WEIGHT, - from_tag); + new_generation = 0; + new_distance = distance + MERGE_TRAVERSAL_WEIGHT; } else { - name_rev(parent, tip_name, taggerdate, - generation + 1, distance + 1, - from_tag); + new_name = tip_name; + new_generation = generation + 1; + new_distance = distance + 1; } + + if (create_or_update_name(parent, new_name, taggerdate, + new_generation, new_distance, + from_tag)) + name_rev(parent, new_name, taggerdate, + new_generation, new_distance, from_tag); } } @@ -280,11 +281,17 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo path = name_ref_abbrev(path, can_abbreviate_output); if (commit->date >= cutoff) { const char *tip_name; + char *to_free = NULL; if (deref) - tip_name = xstrfmt("%s^0", path); + tip_name = to_free = xstrfmt("%s^0", path); else tip_name = xstrdup(path); - name_rev(commit, tip_name, taggerdate, 0, 0, from_tag); + if (create_or_update_name(commit, tip_name, taggerdate, + 0, 0, from_tag)) + name_rev(commit, tip_name, taggerdate, 0, 0, + from_tag); + else + free(to_free); } } return 0; -- cgit v0.10.2-6-g49f6 From 8c5724c585791662ec5701719e8665a2db5517fd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Tue, 12 Nov 2019 11:38:19 +0100 Subject: name-rev: drop name_rev()'s 'generation' and 'distance' parameters MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Following the previous patches in this series we can get the values of name_rev()'s 'generation' and 'distance' parameters from the 'stuct rev_name' associated with the commit as well. Let's simplify the function's signature and remove these two unnecessary parameters. Note that at this point we could do the same with the 'tip_name', 'taggerdate' and 'from_tag' parameters as well, but those parameters will be necessary later, after the recursion is eliminated. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 6416c49..fc61d6f 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -106,8 +106,9 @@ copy_data: static void name_rev(struct commit *commit, const char *tip_name, timestamp_t taggerdate, - int generation, int distance, int from_tag) + int from_tag) { + struct rev_name *name = get_commit_rev_name(commit); struct commit_list *parents; int parent_number = 1; @@ -116,7 +117,7 @@ static void name_rev(struct commit *commit, parents = parents->next, parent_number++) { struct commit *parent = parents->item; const char *new_name; - int new_generation, new_distance; + int generation, distance; parse_commit(parent); if (parent->date < cutoff) @@ -126,25 +127,25 @@ static void name_rev(struct commit *commit, size_t len; strip_suffix(tip_name, "^0", &len); - if (generation > 0) + if (name->generation > 0) new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name, - generation, parent_number); + name->generation, + parent_number); else new_name = xstrfmt("%.*s^%d", (int)len, tip_name, parent_number); - new_generation = 0; - new_distance = distance + MERGE_TRAVERSAL_WEIGHT; + generation = 0; + distance = name->distance + MERGE_TRAVERSAL_WEIGHT; } else { new_name = tip_name; - new_generation = generation + 1; - new_distance = distance + 1; + generation = name->generation + 1; + distance = name->distance + 1; } if (create_or_update_name(parent, new_name, taggerdate, - new_generation, new_distance, + generation, distance, from_tag)) - name_rev(parent, new_name, taggerdate, - new_generation, new_distance, from_tag); + name_rev(parent, new_name, taggerdate, from_tag); } } @@ -288,7 +289,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo tip_name = xstrdup(path); if (create_or_update_name(commit, tip_name, taggerdate, 0, 0, from_tag)) - name_rev(commit, tip_name, taggerdate, 0, 0, + name_rev(commit, tip_name, taggerdate, from_tag); else free(to_free); -- cgit v0.10.2-6-g49f6 From fee984bcab9f7331b319aa5a48824593e854b784 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Mon, 9 Dec 2019 12:52:56 +0100 Subject: name-rev: use 'name->tip_name' instead of 'tip_name' MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Following the previous patches in this series we can get the value of 'name_rev()'s 'tip_name' parameter from the 'struct rev_name' associated with the commit as well. So let's use 'name->tip_name' instead, which makes the patch eliminating the recursion of name_rev() a bit easier to follow. Note that at this point we could drop the 'tip_name' parameter as well, but that parameter will be necessary later, after the recursion is eliminated. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index fc61d6f..6c1e6e9 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -126,18 +126,21 @@ static void name_rev(struct commit *commit, if (parent_number > 1) { size_t len; - strip_suffix(tip_name, "^0", &len); + strip_suffix(name->tip_name, "^0", &len); if (name->generation > 0) - new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name, + new_name = xstrfmt("%.*s~%d^%d", + (int)len, + name->tip_name, name->generation, parent_number); else - new_name = xstrfmt("%.*s^%d", (int)len, tip_name, + new_name = xstrfmt("%.*s^%d", (int)len, + name->tip_name, parent_number); generation = 0; distance = name->distance + MERGE_TRAVERSAL_WEIGHT; } else { - new_name = tip_name; + new_name = name->tip_name; generation = name->generation + 1; distance = name->distance + 1; } -- cgit v0.10.2-6-g49f6 From 49f7a2fde98e375562c2f8f2e3e3effba70d0402 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Mon, 9 Dec 2019 12:52:57 +0100 Subject: name-rev: eliminate recursion in name_rev() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The name_rev() function calls itself recursively for each interesting parent of the commit it got as parameter, and, consequently, it can segfault when processing a deep history if it exhausts the available stack space. E.g. running 'git name-rev --all' and 'git name-rev HEAD~100000' in the gcc, gecko-dev, llvm, and WebKit repositories results in segfaults on my machine ('ulimit -s' reports 8192kB of stack size limit), and nowadays the former segfaults in the Linux repo as well (it reached the necessasry depth sometime between v5.3-rc4 and -rc5). Eliminate the recursion by inserting the interesting parents into a LIFO 'prio_queue' [1] and iterating until the queue becomes empty. Note that the parent commits must be added in reverse order to the LIFO 'prio_queue', so their relative order is preserved during processing, i.e. the first parent should come out first from the queue, because otherwise performance greatly suffers on mergy histories [2]. The stacksize-limited test 'name-rev works in a deep repo' in 't6120-describe.sh' demonstrated this issue and expected failure. Now the recursion is gone, so flip it to expect success. Also gone are the dmesg entries logging the segfault of that segfaulting 'git name-rev' process on every execution of the test suite. Note that this slightly changes the order of lines in the output of 'git name-rev --all', usually swapping two lines every 35 lines in git.git or every 150 lines in linux.git. This shouldn't matter in practice, because the output has always been unordered anyway. This patch is best viewed with '--ignore-all-space'. [1] Early versions of this patch used a 'commit_list', resulting in ~15% performance penalty for 'git name-rev --all' in 'linux.git', presumably because of the memory allocation and release for each insertion and removal. Using a LIFO 'prio_queue' has basically no effect on performance. [2] We prefer shorter names, i.e. 'v0.1~234' is preferred over 'v0.1^2~5', meaning that usually following the first parent of a merge results in the best name for its ancestors. So when later we follow the remaining parent(s) of a merge, and reach an already named commit, then we usually find that we can't give that commit a better name, and thus we don't have to visit any of its ancestors again. OTOH, if we were to follow the Nth parent of the merge first, then the name of all its ancestors would include a corresponding '^N'. Those are not the best names for those commits, so when later we reach an already named commit following the first parent of that merge, then we would have to update the name of that commit and the names of all of its ancestors as well. Consequently, we would have to visit many commits several times, resulting in a significant slowdown. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 6c1e6e9..a3b796e 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -6,6 +6,7 @@ #include "tag.h" #include "refs.h" #include "parse-options.h" +#include "prio-queue.h" #include "sha1-lookup.h" #include "commit-slab.h" @@ -104,52 +105,77 @@ copy_data: return NULL; } -static void name_rev(struct commit *commit, +static void name_rev(struct commit *start_commit, const char *tip_name, timestamp_t taggerdate, int from_tag) { - struct rev_name *name = get_commit_rev_name(commit); - struct commit_list *parents; - int parent_number = 1; - - for (parents = commit->parents; - parents; - parents = parents->next, parent_number++) { - struct commit *parent = parents->item; - const char *new_name; - int generation, distance; - - parse_commit(parent); - if (parent->date < cutoff) - continue; + struct prio_queue queue; + struct commit *commit; + struct commit **parents_to_queue = NULL; + size_t parents_to_queue_nr, parents_to_queue_alloc = 0; + + memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */ + prio_queue_put(&queue, start_commit); + + while ((commit = prio_queue_get(&queue))) { + struct rev_name *name = get_commit_rev_name(commit); + struct commit_list *parents; + int parent_number = 1; + + parents_to_queue_nr = 0; + + for (parents = commit->parents; + parents; + parents = parents->next, parent_number++) { + struct commit *parent = parents->item; + const char *new_name; + int generation, distance; + + parse_commit(parent); + if (parent->date < cutoff) + continue; - if (parent_number > 1) { - size_t len; + if (parent_number > 1) { + size_t len; + + strip_suffix(name->tip_name, "^0", &len); + if (name->generation > 0) + new_name = xstrfmt("%.*s~%d^%d", + (int)len, + name->tip_name, + name->generation, + parent_number); + else + new_name = xstrfmt("%.*s^%d", (int)len, + name->tip_name, + parent_number); + generation = 0; + distance = name->distance + MERGE_TRAVERSAL_WEIGHT; + } else { + new_name = name->tip_name; + generation = name->generation + 1; + distance = name->distance + 1; + } - strip_suffix(name->tip_name, "^0", &len); - if (name->generation > 0) - new_name = xstrfmt("%.*s~%d^%d", - (int)len, - name->tip_name, - name->generation, - parent_number); - else - new_name = xstrfmt("%.*s^%d", (int)len, - name->tip_name, - parent_number); - generation = 0; - distance = name->distance + MERGE_TRAVERSAL_WEIGHT; - } else { - new_name = name->tip_name; - generation = name->generation + 1; - distance = name->distance + 1; + if (create_or_update_name(parent, new_name, taggerdate, + generation, distance, + from_tag)) { + ALLOC_GROW(parents_to_queue, + parents_to_queue_nr + 1, + parents_to_queue_alloc); + parents_to_queue[parents_to_queue_nr] = parent; + parents_to_queue_nr++; + } } - if (create_or_update_name(parent, new_name, taggerdate, - generation, distance, - from_tag)) - name_rev(parent, new_name, taggerdate, from_tag); + /* The first parent must come out first from the prio_queue */ + while (parents_to_queue_nr) + prio_queue_put(&queue, + parents_to_queue[--parents_to_queue_nr]); } + + clear_prio_queue(&queue); + free(parents_to_queue); } static int subpath_matches(const char *path, const char *filter) diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh index 0d119e9..09c50f3 100755 --- a/t/t6120-describe.sh +++ b/t/t6120-describe.sh @@ -381,7 +381,7 @@ test_expect_success 'describe tag object' ' test_i18ngrep "fatal: test-blob-1 is neither a commit nor blob" actual ' -test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' ' +test_expect_success ULIMIT_STACK_SIZE 'name-rev works in a deep repo' ' i=1 && while test $i -lt 8000 do -- cgit v0.10.2-6-g49f6 From 2866fd284c57d729d486ed93a7fc118f78e765cb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= Date: Mon, 9 Dec 2019 12:52:58 +0100 Subject: name-rev: cleanup name_ref() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Earlier patches in this series moved a couple of conditions from the recursive name_rev() function into its caller name_ref(), for no other reason than to make eliminating the recursion a bit easier to follow. Since the previous patch name_rev() is not recursive anymore, so let's move all those conditions back into name_rev(). Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano diff --git a/builtin/name-rev.c b/builtin/name-rev.c index a3b796e..cc488ee 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -107,12 +107,26 @@ copy_data: static void name_rev(struct commit *start_commit, const char *tip_name, timestamp_t taggerdate, - int from_tag) + int from_tag, int deref) { struct prio_queue queue; struct commit *commit; struct commit **parents_to_queue = NULL; size_t parents_to_queue_nr, parents_to_queue_alloc = 0; + char *to_free = NULL; + + parse_commit(start_commit); + if (start_commit->date < cutoff) + return; + + if (deref) + tip_name = to_free = xstrfmt("%s^0", tip_name); + + if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0, + from_tag)) { + free(to_free); + return; + } memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */ prio_queue_put(&queue, start_commit); @@ -309,20 +323,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo if (taggerdate == TIME_MAX) taggerdate = commit->date; path = name_ref_abbrev(path, can_abbreviate_output); - if (commit->date >= cutoff) { - const char *tip_name; - char *to_free = NULL; - if (deref) - tip_name = to_free = xstrfmt("%s^0", path); - else - tip_name = xstrdup(path); - if (create_or_update_name(commit, tip_name, taggerdate, - 0, 0, from_tag)) - name_rev(commit, tip_name, taggerdate, - from_tag); - else - free(to_free); - } + name_rev(commit, xstrdup(path), taggerdate, from_tag, deref); } return 0; } -- cgit v0.10.2-6-g49f6