{"thread":{"id":"31385","subject":"[PATCH v2 0/6] describe --contains / name-rev --weight","startedAt":"2012-08-30T03:50:23Z","lastAt":"2012-09-04T22:29:39Z","messageCount":8,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":6},"messages":[{"id":"198071","messageId":"1346298629-13730-1-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":null,"subject":"[PATCH v2 0/6] describe --contains / name-rev --weight","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:23Z","receivedAt":"2012-08-30T03:50:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Greg KH noticed that the commit 0136db586c that was merged to the\nmainline back in v3.5-rc1 days was merged again as part of a\ndifferent branch to the mainline before v3.6-rc1.\n\n\"git describe --contains\" gives the commit a name based on the newer\nv3.6-rc1 tag, which was surprising.\n\nThis is because \"describe --contains\" calls \"name-rev\", which tries\nto use the tag that minimizes the steps between the tag and the\ncommit being named. The branch merged recently to the mainline did\nnot have as much work done on top of the commit as the old branch\nthat was merged earlier, and \"name-rev\" chose to use the newer tag\nto base the name on.\n\nThe new \"--weight\" option introduced by this series tells it to use\nthe oldest tag that contains the commit being named instead. This\nmatches what people expect from \"describe --contains\" better.\n\nJunio C Hamano (6):\n name-rev: lose unnecessary typedef\n name_rev: clarify the logic to assign a new tip-name to a commit\n name-rev: --weight option\n name-rev --weight: cache the computed weight in notes\n name-rev --weight: tests and documentation\n describe --contains: use \"name-rev --weight\"\n\n Documentation/git-name-rev.txt | 14 ++-\n builtin/describe.c | 3 +-\n builtin/name-rev.c | 195 ++++++++++++++++++++++++++++++++++++-----\n t/t6039-name-rev.sh | 62 +++++++++++++\n 4 files changed, 248 insertions(+), 26 deletions(-)\n create mode 100755 t/t6039-name-rev.sh\n\n-- \n1.7.12.286.g9df01f7\n"},{"id":"198072","messageId":"1346298629-13730-2-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":"1346298629-13730-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 1/6] name-rev: lose unnecessary typedef","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:24Z","receivedAt":"2012-08-30T03:50:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Just spell it \"struct rev_name\"; it makes it more clear what is\ngoing on.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/name-rev.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 1b37458..8af2cfa 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -7,11 +7,11 @@\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n-typedef struct rev_name {\n+struct rev_name {\n \tconst char *tip_name;\n \tint generation;\n \tint distance;\n-} rev_name;\n+};\n \n static long cutoff = LONG_MAX;\n \n@@ -43,7 +43,7 @@ static void name_rev(struct commit *commit,\n \t}\n \n \tif (name == NULL) {\n-\t\tname = xmalloc(sizeof(rev_name));\n+\t\tname = xmalloc(sizeof(struct rev_name));\n \t\tcommit->util = name;\n \t\tgoto copy_data;\n \t} else if (name->distance > distance) {\n-- \n1.7.12.286.g9df01f7\n"},{"id":"198078","messageId":"1346298629-13730-3-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":"1346298629-13730-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 2/6] name_rev: clarify the logic to assign a new tip-name to a commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:25Z","receivedAt":"2012-08-30T03:50:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In preparation for later changes, restructure the logic a little bit\nto separate how the code decides to use the new \"tip\" for naming a\nparticular commit, and what happens based on the decision.\n\nAlso re-indent and correct style of this function while we are at it.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/name-rev.c | 45 +++++++++++++++++++++++++--------------------\n 1 file changed, 25 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 8af2cfa..ebbf541 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -19,12 +19,13 @@ static long cutoff = LONG_MAX;\n #define MERGE_TRAVERSAL_WEIGHT 65535\n \n static void name_rev(struct commit *commit,\n-\t\tconst char *tip_name, int generation, int distance,\n-\t\tint deref)\n+\t\t const char *tip_name, int generation, int distance,\n+\t\t int deref)\n {\n \tstruct rev_name *name = (struct rev_name *)commit->util;\n \tstruct commit_list *parents;\n-\tint parent_number = 1;\n+\tint parent_number;\n+\tint use_this_tip = 0;\n \n \tif (!commit->object.parsed)\n \t\tparse_commit(commit);\n@@ -42,21 +43,26 @@ static void name_rev(struct commit *commit,\n \t\t\tdie(\"generation: %d, but deref?\", generation);\n \t}\n \n-\tif (name == NULL) {\n-\t\tname = xmalloc(sizeof(struct rev_name));\n+\tif (!name) {\n+\t\tname = xcalloc(1, sizeof(struct rev_name));\n \t\tcommit->util = name;\n-\t\tgoto copy_data;\n-\t} else if (name->distance > distance) {\n-copy_data:\n-\t\tname->tip_name = tip_name;\n-\t\tname->generation = generation;\n-\t\tname->distance = distance;\n-\t} else\n+\t\tuse_this_tip = 1;\n+\t}\n+\n+\tif (distance < name->distance)\n+\t\tuse_this_tip = 1;\n+\n+\tif (!use_this_tip)\n \t\treturn;\n \n-\tfor (parents = commit->parents;\n-\t\t\tparents;\n-\t\t\tparents = parents->next, parent_number++) {\n+\tname->tip_name = tip_name;\n+\tname->generation = generation;\n+\tname->distance = distance;\n+\n+\t/* Propagate our name to our parents */\n+\tfor (parents = commit->parents, parent_number = 1;\n+\t parents;\n+\t parents = parents->next, parent_number++) {\n \t\tif (parent_number > 1) {\n \t\t\tint len = strlen(tip_name);\n \t\t\tchar *new_name = xmalloc(len +\n@@ -68,16 +74,15 @@ copy_data:\n \t\t\t\tlen -= 2;\n \t\t\tif (generation > 0)\n \t\t\t\tsprintf(new_name, \"%.*s~%d^%d\", len, tip_name,\n-\t\t\t\t\t\tgeneration, parent_number);\n+\t\t\t\t\tgeneration, parent_number);\n \t\t\telse\n \t\t\t\tsprintf(new_name, \"%.*s^%d\", len, tip_name,\n-\t\t\t\t\t\tparent_number);\n-\n+\t\t\t\t\tparent_number);\n \t\t\tname_rev(parents->item, new_name, 0,\n-\t\t\t\tdistance + MERGE_TRAVERSAL_WEIGHT, 0);\n+\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT, 0);\n \t\t} else {\n \t\t\tname_rev(parents->item, tip_name, generation + 1,\n-\t\t\t\tdistance + 1, 0);\n+\t\t\t\t distance + 1, 0);\n \t\t}\n \t}\n }\n-- \n1.7.12.286.g9df01f7\n"},{"id":"198076","messageId":"1346298629-13730-4-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":"1346298629-13730-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 3/6] name-rev: --weight option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:26Z","receivedAt":"2012-08-30T03:50:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Instead of naming a rev after a tip that is topologically closest,\nuse the tip that is the oldest one among those which contain the\nrev.\n\nThe semantics \"name-rev --weight\" would give us is closer to what\npeople expect from \"describe --contains\".\n\nNote that this is fairly expensive to compute; a later change in the\nseries will cache the weight value using notes-cache.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/name-rev.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 102 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex ebbf541..7cdb758 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -4,6 +4,8 @@\n #include \"tag.h\"\n #include \"refs.h\"\n #include \"parse-options.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n@@ -11,8 +13,85 @@ struct rev_name {\n \tconst char *tip_name;\n \tint generation;\n \tint distance;\n+\tint weight;\n };\n \n+/*\n+ * Historically, \"name-rev\" named a rev based on the tip that is\n+ * topologically closest to it.\n+ *\n+ * It does not give a good answer to \"what is the earliest tag that\n+ * contains the commit?\", however, because you can build a new commit\n+ * on top of an ancient commit X, merge it to the tip and tag the\n+ * result, which would make X reachable from the new tag in two hops,\n+ * even though it appears in the part of the history that is contained\n+ * in other ancient tags.\n+ *\n+ * In order to answer that question, \"name-rev\" can be told to name a\n+ * rev based on the tip that has smallest number of commits behind it.\n+ */\n+static int use_weight;\n+\n+/*\n+ * NEEDSWORK: the result of this computation must be cached to\n+ * a dedicated notes tree, keyed by the commit object name.\n+ */\n+static int compute_ref_weight(struct commit *commit)\n+{\n+\tstruct rev_info revs;\n+\tint weight = 1; /* give root the weight of 1 */\n+\n+\treset_revision_walk();\n+\tinit_revisions(&revs, NULL);\n+\tadd_pending_object(&revs, (struct object *)commit, NULL);\n+\tprepare_revision_walk(&revs);\n+\twhile (get_revision(&revs))\n+\t\tweight++;\n+\treturn weight;\n+}\n+\n+static int ref_weight(const char *refname, size_t reflen)\n+{\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tunsigned char sha1[20];\n+\tstruct commit *commit;\n+\tstruct rev_name *name;\n+\n+\tstrbuf_add(&buf, refname, reflen);\n+\tif (get_sha1(buf.buf, sha1))\n+\t\tdie(\"Internal error: cannot parse tip '%s'\", buf.buf);\n+\tstrbuf_release(&buf);\n+\n+\tcommit = lookup_commit_reference_gently(sha1, 0);\n+\tif (!commit)\n+\t\tdie(\"Internal error: cannot look up commit '%s'\", buf.buf);\n+\tname = commit->util;\n+\tif (!name)\n+\t\tdie(\"Internal error: a tip without name '%s'\", buf.buf);\n+\tif (!name->weight)\n+\t\tname->weight = compute_ref_weight(commit);\n+\treturn name->weight;\n+}\n+\n+static int tip_weight_cmp(const char *a, const char *b)\n+{\n+\tsize_t reflen_a, reflen_b;\n+\tstatic const char traversal[] = \"^~\";\n+\n+\t/*\n+\t * A \"tip\" may look like followed by traversal\n+\t * instruction (e.g. ^2~74). We only are interested in\n+\t * the weight of the ref part.\n+\t */\n+\treflen_a = strcspn(a, traversal);\n+\treflen_b = strcspn(b, traversal);\n+\n+\tif (reflen_a == reflen_b && !memcmp(a, b, reflen_a))\n+\t\treturn 0;\n+\n+\treturn ref_weight(a, reflen_a) - ref_weight(b, reflen_b);\n+}\n+\n static long cutoff = LONG_MAX;\n \n /* How many generations are maximally preferred over _one_ merge traversal? */\n@@ -49,8 +128,27 @@ static void name_rev(struct commit *commit,\n \t\tuse_this_tip = 1;\n \t}\n \n-\tif (distance < name->distance)\n-\t\tuse_this_tip = 1;\n+\tif (!use_weight) {\n+\t\tif (distance < name->distance)\n+\t\t\tuse_this_tip = 1;\n+\t} else {\n+\t\tif (!name->tip_name)\n+\t\t\tuse_this_tip = 1;\n+\t\telse {\n+\t\t\t/*\n+\t\t\t * Pick a name based on the ref that is older,\n+\t\t\t * i.e. having smaller number of commits\n+\t\t\t * behind it. Break the tie by picking the\n+\t\t\t * path with smaller numer of steps to reach\n+\t\t\t * that ref from the commit.\n+\t\t\t */\n+\t\t\tint cmp = tip_weight_cmp(name->tip_name, tip_name);\n+\t\t\tif (0 < cmp)\n+\t\t\t\tuse_this_tip = 1;\n+\t\t\telse if (!cmp && distance < name->distance)\n+\t\t\t\tuse_this_tip = 1;\n+\t\t}\n+\t}\n \n \tif (!use_this_tip)\n \t\treturn;\n@@ -241,6 +339,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tOPT_BOOLEAN(0, \"undefined\", &allow_undefined, \"allow to print `undefined` names\"),\n \t\tOPT_BOOLEAN(0, \"always\", &always,\n \t\t\t \"show abbreviated commit object as fallback\"),\n+\t\tOPT_BOOLEAN(0, \"weight\", &use_weight,\n+\t\t\t \"name revs based on the oldest tip that contain them\"),\n \t\tOPT_END(),\n \t};\n \n-- \n1.7.12.286.g9df01f7\n"},{"id":"198077","messageId":"1346298629-13730-5-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":"1346298629-13730-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 4/6] name-rev --weight: cache the computed weight in notes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:27Z","receivedAt":"2012-08-30T03:50:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"With the \"weight\" assigned to tip of each ref, we can give more\nintuitive results from \"name-rev\" that is more suitable to answer\n\"what is the oldest tag that contains this commit?\" However, this\nnumber is very expensive to compute.\n\nUse the notes-cache mechanism to cache this value. The result\nbecomes usable again.\n\n (priming the cache from scratch)\n $ rm .git/refs/notes/name-rev-weight\n $ /usr/bin/time git name-rev --weight --tags 0136db586c\n 0136db586c tags/v3.5-rc1~83^2~81^2~76\n 6.06user 0.46system 0:06.54elapsed 99%CPU (0avgtext+0avgdata 1861456maxresident)k\n 8inputs+16outputs (0major+128576minor)pagefaults 0swaps\n\n (with cache already primed)\n $ /usr/bin/time git name-rev --weight --tags 0136db586c\n 0136db586c tags/v3.5-rc1~83^2~81^2~76\n 0.50user 0.22system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 244224maxresident)k\n 0inputs+0outputs (0major+16062minor)pagefaults 0swaps\n\n (the old \"shortest path\" version)\n $ /usr/bin/time git name-rev --tags 0136db586c\n 0136db586c tags/v3.6-rc1~59^2~56^2~76\n 0.31user 0.01system 0:00.32elapsed 100%CPU (0avgtext+0avgdata 243488maxresident)k\n 0inputs+0outputs (0major+16000minor)pagefaults 0swaps\n\nThis version does not invalidate the cache in the presense of\nmodified grafts and object replacement, but in a later version we\ncan compute a hash of the grafts and replacement data and pass it as\nthe validity token to automatically invalidate the cache when these\ndata that affects the perceived topology change.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/name-rev.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 51 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 7cdb758..d78eedd 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -6,6 +6,7 @@\n #include \"parse-options.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n+#include \"notes-cache.h\"\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n@@ -32,10 +33,6 @@ struct rev_name {\n */\n static int use_weight;\n \n-/*\n- * NEEDSWORK: the result of this computation must be cached to\n- * a dedicated notes tree, keyed by the commit object name.\n- */\n static int compute_ref_weight(struct commit *commit)\n {\n \tstruct rev_info revs;\n@@ -50,6 +47,32 @@ static int compute_ref_weight(struct commit *commit)\n \treturn weight;\n }\n \n+static struct notes_cache weight_cache;\n+static int weight_cache_updated;\n+\n+static int get_ref_weight(struct commit *commit)\n+{\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tsize_t sz;\n+\tint weight;\n+\tchar *note;\n+\n+\tnote = notes_cache_get(&weight_cache, commit->object.sha1, &sz);\n+\tif (note && !strtol_i(note, 10, &weight)) {\n+\t\tfree(note);\n+\t\treturn weight;\n+\t}\n+\tfree(note);\n+\n+\tweight = compute_ref_weight(commit);\n+\tstrbuf_addf(&buf, \"%d\", weight);\n+\tnotes_cache_put(&weight_cache, commit->object.sha1,\n+\t\t\tbuf.buf, buf.len);\n+\tstrbuf_release(&buf);\n+\tweight_cache_updated = 1;\n+\treturn weight;\n+}\n+\n static int ref_weight(const char *refname, size_t reflen)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -69,7 +92,7 @@ static int ref_weight(const char *refname, size_t reflen)\n \tif (!name)\n \t\tdie(\"Internal error: a tip without name '%s'\", buf.buf);\n \tif (!name->weight)\n-\t\tname->weight = compute_ref_weight(commit);\n+\t\tname->weight = get_ref_weight(commit);\n \treturn name->weight;\n }\n \n@@ -323,6 +346,22 @@ static void name_rev_line(char *p, struct name_ref_data *data)\n \t\tfwrite(p_start, p - p_start, 1, stdout);\n }\n \n+static const char *get_validity_token(void)\n+{\n+\t/*\n+\t * In future versions, we may want to automatically invalidate\n+\t * the cached weight data whenever grafts and replacement\n+\t * changes. We could do so by (1) reading the contents of the\n+\t * grafts file, (2) enumerating the replacement data (original\n+\t * object name and replacement object name) and sorting the\n+\t * result, and (3) concatenating (1) and (2) and hashing it,\n+\t * to come up with \"dynamic validity: [0-9a-f]{40}\" or something.\n+\t *\n+\t * In this verison, we simply do not bother ;-).\n+\t */\n+\treturn \"static validity token\";\n+}\n+\n int cmd_name_rev(int argc, const char **argv, const char *prefix)\n {\n \tstruct object_array revs = OBJECT_ARRAY_INIT;\n@@ -353,6 +392,10 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \tif (all || transform_stdin)\n \t\tcutoff = 0;\n \n+\tif (use_weight)\n+\t\tnotes_cache_init(&weight_cache, \"name-rev-weight\",\n+\t\t\t\t get_validity_token());\n+\n \tfor (; argc; argc--, argv++) {\n \t\tunsigned char sha1[20];\n \t\tstruct object *o;\n@@ -408,5 +451,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t\t\t always, allow_undefined, data.name_only);\n \t}\n \n+\tif (use_weight && weight_cache_updated)\n+\t\tnotes_cache_write(&weight_cache);\n+\n \treturn 0;\n }\n-- \n1.7.12.286.g9df01f7\n"},{"id":"198074","messageId":"1346298629-13730-6-git-send-email-gitster@pobox.com","threadId":"31385","inReplyTo":"1346298629-13730-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 5/6] name-rev --weight: tests and documentation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:50:28Z","receivedAt":"2012-08-30T03:50:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We are almost there...\n\nSigned-off-by: Junio C Hamano \n---\n Documentation/git-name-rev.txt | 14 ++++++++--\n t/t6039-name-rev.sh | 62 ++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 73 insertions(+), 3 deletions(-)\n create mode 100755 t/t6039-name-rev.sh\n\ndiff --git a/Documentation/git-name-rev.txt b/Documentation/git-name-rev.txt\nindex ad1d146..f40027a 100644\n--- a/Documentation/git-name-rev.txt\n+++ b/Documentation/git-name-rev.txt\n@@ -9,13 +9,13 @@ git-name-rev - Find symbolic names for given revs\n SYNOPSIS\n --------\n [verse]\n-'git name-rev' [--tags] [--refs=]\n+'git name-rev' [--tags] [--refs=] [--weight]\n \t ( --all | --stdin | ... )\n \n DESCRIPTION\n -----------\n-Finds symbolic names suitable for human digestion for revisions given in any\n-format parsable by 'git rev-parse'.\n+Finds symbolic names suitable for human digestion for revisions\n+given in any format parsable by 'git rev-parse'.\n \n \n OPTIONS\n@@ -47,6 +47,14 @@ OPTIONS\n --always::\n \tShow uniquely abbreviated commit object as fallback.\n \n+--weight::\n+\tName commits based on the oldest ref that contains it. This\n+\tis way more expensive than the default behaviour of the\n+\tcommand, in which commits are named based on the ref that\n+\tis topologically the closest, but gives more intuitive\n+\tanswer to the question: what is the oldest tag that contains\n+\tthis commit?\n+\n EXAMPLE\n -------\n \ndiff --git a/t/t6039-name-rev.sh b/t/t6039-name-rev.sh\nnew file mode 100755\nindex 0000000..315ce14\n--- /dev/null\n+++ b/t/t6039-name-rev.sh\n@@ -0,0 +1,62 @@\n+#!/bin/sh\n+\n+test_description='name-rev'\n+. ./test-lib.sh\n+\n+# Prepare a history with this shape\n+#\n+# ---0--1--2--3--4--Y--5---7---Z\n+# \\ / /\n+# \\ / /\n+# X---------------6\n+#\n+\n+test_expect_success setup '\n+\ttest_tick &&\n+\tgit commit --allow-empty -m 0 &&\n+\tgit branch side &&\n+\tgit commit --allow-empty -m 1 &&\n+\tgit checkout side &&\n+\tgit commit --allow-empty -m X &&\n+\tgit branch X &&\n+\tgit commit --allow-empty -m 6 &&\n+\tgit checkout master &&\n+\tgit merge -m 2 X &&\n+\tgit commit --allow-empty -m 3 &&\n+\tgit commit --allow-empty -m 4 &&\n+\tgit commit --allow-empty -m Y &&\n+\tgit tag Y &&\n+\tgit commit --allow-empty -m 5 &&\n+\tgit merge -m 7 side &&\n+\tgit commit --allow-empty -m Z &&\n+\tgit tag Z\n+'\n+\n+test_expect_success 'name-rev (plain)' '\n+\t# We expect \"X tags/Z~1^2~1\" but it could\n+\t# be written as \"X tags/Z^^2^\"; the only two\n+\t# important things that matter are that it\n+\t# is named after Z (not Y), and it correctly\n+\t# names X.\n+\tgit name-rev --tags X >actual &&\n+\tread X T actual &&\n+\tread X T \n---\n builtin/describe.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 9f63067..fbd5be5 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -436,11 +436,12 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\tdie(_(\"--long is incompatible with --abbrev=0\"));\n \n \tif (contains) {\n-\t\tconst char **args = xmalloc((7 + argc) * sizeof(char *));\n+\t\tconst char **args = xmalloc((8 + argc) * sizeof(char *));\n \t\tint i = 0;\n \t\targs[i++] = \"name-rev\";\n \t\targs[i++] = \"--name-only\";\n \t\targs[i++] = \"--no-undefined\";\n+\t\targs[i++] = \"--weight\";\n \t\tif (always)\n \t\t\targs[i++] = \"--always\";\n \t\tif (!all) {\n-- \n1.7.12.286.g9df01f7\n"},{"id":"198346","messageId":"7va9x58lrg.fsf_-_@alter.siamese.dyndns.org","threadId":"31385","inReplyTo":"1346298629-13730-4-git-send-email-gitster@pobox.com","subject":"[PATCH 3.5/6] name-rev --weight: trivial optimization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-04T22:29:39Z","receivedAt":"2012-09-04T22:29:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Instead of naming a rev after a tip that is topologically closest,\n> use the tip that is the oldest one among those which contain the\n> rev.\n>\n> The semantics \"name-rev --weight\" would give us is closer to what\n> people expect from \"describe --contains\".\n>\n> Note that this is fairly expensive to compute; a later change in the\n> series will cache the weight value using notes-cache.\n>\n> Signed-off-by: Junio C Hamano \n\nHere is a trivial optimization on top of the one from the other day.\n\n-- >8 --\nIt often happens that immediately after traversing from v1.2.3 to\nfind out its weight, we are asked to see if another commit v1.2.0\nis heavier than that.\n\nBecause the commits that are reachable from v1.2.3 are painted with\nthe SHOWN flag until the next \"rev-list\" traversal, we can notice\nthat the new commit v1.2.0 is reachable from v1.2.3 without doing\nany traversal. We cannot learn exactly how much it weighs, but we\ncan tell it must weigh less than v1.2.3, and that is all that the\ncaller wants to know.\n\nIn the kernel history, \"git name-rev --tags 0136db586c\" which\nstarted this topic needs 26k calls to tip_weight_cmp(). 13k of them\nare comparisons between tips based on the same ref and answered\nwithout computing any weight. Among the remaining 13k, 1.8k\ncomparisons are answered with this trivial \"fast-forward\"\noptimization.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/name-rev.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 7cdb758..809553b 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -32,6 +32,9 @@ struct rev_name {\n */\n static int use_weight;\n \n+/* To optimize revision traversal */\n+static struct commit *painted_commit;\n+\n /*\n * NEEDSWORK: the result of this computation must be cached to\n * a dedicated notes tree, keyed by the commit object name.\n@@ -47,15 +50,15 @@ static int compute_ref_weight(struct commit *commit)\n \tprepare_revision_walk(&revs);\n \twhile (get_revision(&revs))\n \t\tweight++;\n+\tpainted_commit = commit;\n \treturn weight;\n }\n \n-static int ref_weight(const char *refname, size_t reflen)\n+static struct commit *ref_commit(const char *refname, size_t reflen)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n \tunsigned char sha1[20];\n \tstruct commit *commit;\n-\tstruct rev_name *name;\n \n \tstrbuf_add(&buf, refname, reflen);\n \tif (get_sha1(buf.buf, sha1))\n@@ -65,9 +68,16 @@ static int ref_weight(const char *refname, size_t reflen)\n \tcommit = lookup_commit_reference_gently(sha1, 0);\n \tif (!commit)\n \t\tdie(\"Internal error: cannot look up commit '%s'\", buf.buf);\n+\treturn commit;\n+}\n+\n+static int ref_weight(struct commit *commit, const char *refname, size_t reflen)\n+{\n+\tstruct rev_name *name;\n+\n \tname = commit->util;\n \tif (!name)\n-\t\tdie(\"Internal error: a tip without name '%s'\", buf.buf);\n+\t\tdie(\"Internal error: a tip without name '%.*s'\", (int) reflen, refname);\n \tif (!name->weight)\n \t\tname->weight = compute_ref_weight(commit);\n \treturn name->weight;\n@@ -76,6 +86,7 @@ static int ref_weight(const char *refname, size_t reflen)\n static int tip_weight_cmp(const char *a, const char *b)\n {\n \tsize_t reflen_a, reflen_b;\n+\tstruct commit *commit_a, *commit_b;\n \tstatic const char traversal[] = \"^~\";\n \n \t/*\n@@ -89,7 +100,25 @@ static int tip_weight_cmp(const char *a, const char *b)\n \tif (reflen_a == reflen_b && !memcmp(a, b, reflen_a))\n \t\treturn 0;\n \n-\treturn ref_weight(a, reflen_a) - ref_weight(b, reflen_b);\n+\tcommit_a = ref_commit(a, reflen_a);\n+\tcommit_b = ref_commit(b, reflen_b);\n+\n+\t/* Have we painted either one of these recently? */\n+\tif (commit_a == painted_commit &&\n+\t (commit_b->object.flags & SHOWN)) {\n+\t\t/*\n+\t\t * We know b can be reached from a, so b must be older\n+\t\t * (lighter, as it has fewer commits behind it) than\n+\t\t * a.\n+\t\t */\n+\t\treturn 1;\n+\t} else if (commit_b == painted_commit &&\n+\t\t (commit_a->object.flags & SHOWN)) {\n+\t\t/* Likewise */\n+\t\treturn -1;\n+\t}\n+\n+\treturn ref_weight(commit_a, a, reflen_a) - ref_weight(commit_b, b, reflen_b);\n }\n \n static long cutoff = LONG_MAX;\n-- \n1.7.12.321.g60f00e5\n"}]}