Skip to content

name-rev: eliminate recursion

SZEDER Gábor git 3 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest14 patches 2 repliesIn review
  2. v213 patches 9 repliesSuperseded
  3. v115 patches 38 repliesSuperseded

Changes in v3 from the cover letter

- Add the new patch 12 to use 'name->tip_name' instead of 'tip_name', to make the patch eliminating the recursion a bit even easier to follow (only with '--ignore-all-space', though, without that option that patch's diff is still mostly gibberish). The end result is the still same, see the empty interdiff.

- Minor commit message updates (a typofix and René's signoff).

Patches in v3 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/14t6120-describe: correct test repo history graph in commentt/t6120-describe.sh+10 -90 replies
2/14t6120-describe: modernize the 'check_describe' helpert/t6120-describe.sh+4 -60 replies
3/14name-rev: use strbuf_strip_suffix() in get_rev_name()builtin/name-rev.c+3 -40 replies
4/14name-rev: avoid unnecessary cast in name_ref()builtin/name-rev.c+1 -10 replies
5/14name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationbuiltin/name-rev.c+1 -10 replies
6/14t6120: add a test to cover inner conditions in 'git name-rev's name_rev()t/t6120-describe.sh+41 -00 replies
7/14name-rev: extract creating/updating a 'struct name_rev' into a helperbuiltin/name-rev.c+27 -130 replies
8/14name-rev: pull out deref handling from the recursionbuiltin/name-rev.c+10 -170 replies
9/14name-rev: restructure parsing commits and applying date cutoffbuiltin/name-rev.c+16 -130 replies
10/14name-rev: restructure creating/updating 'struct rev_name' instancesbuiltin/name-rev.c+21 -140 replies
11/14name-rev: drop name_rev()'s 'generation' and 'distance' parametersbuiltin/name-rev.c+13 -120 replies
12/14name-rev: use 'name->tip_name' instead of 'tip_name'builtin/name-rev.c+7 -40 replies
13/14name-rev: eliminate recursion in name_rev()builtin/name-rev.c t/t6120-describe.sh+65 -390 replies
14/14name-rev: cleanup name_ref()builtin/name-rev.c+16 -150 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.

Read the v3 thread

Cover letter [PATCH v3 00/14] name-rev: eliminate recursion

'git name-rev' is implemented using a recursive algorithm, and, consequently, it can segfault in deep histories (e.g. WebKit), and thanks to a test case demonstrating this limitation every test run results in a dmesg entry logging the segfaulting git process.

This patch series eliminates the recursion.

Changes since v2:

- Add the new patch 12 to use 'name->tip_name' instead of 'tip_name', to make the patch eliminating the recursion a bit even easier to follow (only with '--ignore-all-space', though, without that option that patch's diff is still mostly gibberish). The end result is the still same, see the empty interdiff.

- Minor commit message updates (a typofix and René's signoff).

v2: https://public-inbox.org/git/[email protected]/
v1: https://public-inbox.org/git/[email protected]/T/#u

René Scharfe (1):
name-rev: use strbuf_strip_suffix() in get_rev_name()

SZEDER Gábor (13):
t6120-describe: correct test repo history graph in comment
t6120-describe: modernize the 'check_describe' helper
name-rev: avoid unnecessary cast in name_ref()
name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
t6120: add a test to cover inner conditions in 'git name-rev's

    name_rev()

name-rev: extract creating/updating a 'struct name_rev' into a helper
name-rev: pull out deref handling from the recursion
name-rev: restructure parsing commits and applying date cutoff
name-rev: restructure creating/updating 'struct rev_name' instances
name-rev: drop name_rev()'s 'generation' and 'distance' parameters
name-rev: use 'name->tip_name' instead of 'tip_name'
name-rev: eliminate recursion in name_rev()
name-rev: cleanup name_ref()

 builtin/name-rev.c  | 147 +++++++++++++++++++++++++++++---------------
 t/t6120-describe.sh |  72 +++++++++++++++++-----
 2 files changed, 153 insertions(+), 66 deletions(-)

Interdiff against v2:
Range-diff against v2:

 1:  8d70ed050d =  1:  8d70ed050d t6120-describe: correct test repo history graph in comment
 2:  3720b6859d !  2:  d2091869c8 t6120-describe: modernize the 'check_describe' helper

@@ Commit message
'test_expect_success' blocks, with extra hand-rolled code to record and examine its exit code.

- Update this helper and move the 'git decribe' invocation inside the
+ Update this helper and move the 'git describe' invocation inside the
'test_expect_success' block.

3: ad2f2eee68 ! 3: 9d13032871 name-rev: use strbuf_strip_suffix() in get_rev_name()
@@ Commit message
string to the strbuf and then use strbuf_strip_suffix(), making the code more idiomatic.

- [TODO: René's signoff!]
+ Signed-off-by: René Scharfe <[email protected]>

## builtin/name-rev.c ##

 4:  c86a2ae2d0 =  4:  b1a8d7ce03 name-rev: avoid unnecessary cast in name_ref()
 5:  4fc960cc05 =  5:  3497d0bc42 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
 6:  1493cb4484 =  6:  43cba1a369 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()
 7:  fc842e578b =  7:  7053fc707c name-rev: extract creating/updating a 'struct name_rev' into a helper
 8:  7f182503e2 =  8:  28d957df88 name-rev: pull out deref handling from the recursion
 9:  0cdd40b75b =  9:  5bd4dede3d name-rev: restructure parsing commits and applying date cutoff
10:  e1733e3c56 = 10:  92f3897ff3 name-rev: restructure creating/updating 'struct rev_name' instances
11:  bd6e2e6d87 = 11:  cd24270f23 name-rev: drop name_rev()'s 'generation' and 'distance' parameters
 -:  ---------- > 12:  f33c0bbfd0 name-rev: use 'name->tip_name' instead of 'tip_name'
12:  0cf63c6d64 ! 13:  e5d7d291bd name-rev: eliminate recursion in name_rev()
    @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
     +				distance = name->distance + 1;
     +			}
      
    --			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;
     +			if (create_or_update_name(parent, new_name, taggerdate,

13: 316f7af43c = 14: 0b556389a3 name-rev: cleanup name_ref()

Signature · 1 line
2.24.0.801.g241c134b8d