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

["SZEDER Gábor" <szeder.dev@gmail.com>]

'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/20191112103821.30265-1-szeder.dev@gmail.com/
v1: https://public-inbox.org/git/20190919214712.7348-1-szeder.dev@gmail.com/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.
     
         Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
 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 <l.s.r@web.de>
         Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
     
      ## 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()
-- 
2.24.0.801.g241c134b8d