)]}'
{
  "commit": "49f7a2fde98e375562c2f8f2e3e3effba70d0402",
  "tree": "231bec7df797870efd57d7458961c75b1c29f7f9",
  "parents": [
    "fee984bcab9f7331b319aa5a48824593e854b784"
  ],
  "author": {
    "name": "SZEDER Gábor",
    "email": "szeder.dev@gmail.com",
    "time": "Mon Dec 09 12:52:57 2019 +0100"
  },
  "committer": {
    "name": "Junio C Hamano",
    "email": "gitster@pobox.com",
    "time": "Mon Dec 09 13:33:01 2019 -0800"
  },
  "message": "name-rev: eliminate recursion in name_rev()\n\nThe name_rev() function calls itself recursively for each interesting\nparent of the commit it got as parameter, and, consequently, it can\nsegfault when processing a deep history if it exhausts the available\nstack space.  E.g. running \u0027git name-rev --all\u0027 and \u0027git name-rev\nHEAD~100000\u0027 in the gcc, gecko-dev, llvm, and WebKit repositories\nresults in segfaults on my machine (\u0027ulimit -s\u0027 reports 8192kB of\nstack size limit), and nowadays the former segfaults in the Linux repo\nas well (it reached the necessasry depth sometime between v5.3-rc4 and\n-rc5).\n\nEliminate the recursion by inserting the interesting parents into a\nLIFO \u0027prio_queue\u0027 [1] and iterating until the queue becomes empty.\n\nNote that the parent commits must be added in reverse order to the\nLIFO \u0027prio_queue\u0027, so their relative order is preserved during\nprocessing, i.e. the first parent should come out first from the\nqueue, because otherwise performance greatly suffers on mergy\nhistories [2].\n\nThe stacksize-limited test \u0027name-rev works in a deep repo\u0027 in\n\u0027t6120-describe.sh\u0027 demonstrated this issue and expected failure.  Now\nthe recursion is gone, so flip it to expect success.  Also gone are\nthe dmesg entries logging the segfault of that segfaulting \u0027git\nname-rev\u0027 process on every execution of the test suite.\n\nNote that this slightly changes the order of lines in the output of\n\u0027git name-rev --all\u0027, usually swapping two lines every 35 lines in\ngit.git or every 150 lines in linux.git.  This shouldn\u0027t matter in\npractice, because the output has always been unordered anyway.\n\nThis patch is best viewed with \u0027--ignore-all-space\u0027.\n\n[1] Early versions of this patch used a \u0027commit_list\u0027, resulting in\n    ~15% performance penalty for \u0027git name-rev --all\u0027 in \u0027linux.git\u0027,\n    presumably because of the memory allocation and release for each\n    insertion and removal. Using a LIFO \u0027prio_queue\u0027 has basically no\n    effect on performance.\n\n[2] We prefer shorter names, i.e. \u0027v0.1~234\u0027 is preferred over\n    \u0027v0.1^2~5\u0027, meaning that usually following the first parent of a\n    merge results in the best name for its ancestors.  So when later\n    we follow the remaining parent(s) of a merge, and reach an already\n    named commit, then we usually find that we can\u0027t give that commit\n    a better name, and thus we don\u0027t have to visit any of its\n    ancestors again.\n\n    OTOH, if we were to follow the Nth parent of the merge first, then\n    the name of all its ancestors would include a corresponding \u0027^N\u0027.\n    Those are not the best names for those commits, so when later we\n    reach an already named commit following the first parent of that\n    merge, then we would have to update the name of that commit and\n    the names of all of its ancestors as well.  Consequently, we would\n    have to visit many commits several times, resulting in a\n    significant slowdown.\n\nSigned-off-by: SZEDER Gábor \u003cszeder.dev@gmail.com\u003e\nSigned-off-by: Junio C Hamano \u003cgitster@pobox.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "6c1e6e98681b9c5b5e56c400497d6b877325d45c",
      "old_mode": 33188,
      "old_path": "builtin/name-rev.c",
      "new_id": "a3b796eac45244df80bf9759caab7066ade44ff7",
      "new_mode": 33188,
      "new_path": "builtin/name-rev.c"
    },
    {
      "type": "modify",
      "old_id": "0d119e96520577d70062a19a17d916aa43acb2d8",
      "old_mode": 33261,
      "old_path": "t/t6120-describe.sh",
      "new_id": "09c50f3f0492acd4a44dcee8a67d4b3ee67fe581",
      "new_mode": 33261,
      "new_path": "t/t6120-describe.sh"
    }
  ]
}