{"thread":{"id":"34831","subject":"[PATCH] sha1-name: refactor get_sha1() parsing","startedAt":"2013-09-02T06:50:43Z","lastAt":"2013-09-02T06:50:43Z","messageCount":1,"participants":["Felipe Contreras"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"226517","messageId":"1378104643-3636-1-git-send-email-felipe.contreras@gmail.com","threadId":"34831","inReplyTo":null,"subject":"[PATCH] sha1-name: refactor get_sha1() parsing","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2013-09-02T06:50:43Z","receivedAt":"2013-09-02T06:50:43Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Instead of parsing left to right, do it right do left, this way it is\nmuch more natural and probably efficient too, as there's less\nrecursivity.\n\nIn theory there shouldn't be any functional changes, although there's at\nleast one error message that has changed.\n\nSigned-off-by: Felipe Contreras <felipe.contreras@gmail.com>\n---\n sha1_name.c                    | 319 ++++++++++++++++++++++++-----------------\n t/t1506-rev-parse-diagnosis.sh |   2 +-\n 2 files changed, 185 insertions(+), 136 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 65ad066..e66bda1 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -430,7 +430,6 @@ static inline int upstream_mark(const char *string, int len)\n \treturn 0;\n }\n \n-static int get_sha1_1(const char *name, int len, unsigned char *sha1, unsigned lookup_flags);\n static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf);\n \n static int get_sha1_basic(const char *str, int len, unsigned char *sha1)\n@@ -571,29 +570,24 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)\n \treturn 0;\n }\n \n-static int get_parent(const char *name, int len,\n-\t\t      unsigned char *result, int idx)\n+static int get_parent(unsigned char *sha1, int idx)\n {\n-\tunsigned char sha1[20];\n-\tint ret = get_sha1_1(name, len, sha1, GET_SHA1_COMMITTISH);\n \tstruct commit *commit;\n \tstruct commit_list *p;\n \n-\tif (ret)\n-\t\treturn ret;\n \tcommit = lookup_commit_reference(sha1);\n \tif (!commit)\n \t\treturn -1;\n \tif (parse_commit(commit))\n \t\treturn -1;\n \tif (!idx) {\n-\t\thashcpy(result, commit->object.sha1);\n+\t\thashcpy(sha1, commit->object.sha1);\n \t\treturn 0;\n \t}\n \tp = commit->parents;\n \twhile (p) {\n \t\tif (!--idx) {\n-\t\t\thashcpy(result, p->item->object.sha1);\n+\t\t\thashcpy(sha1, p->item->object.sha1);\n \t\t\treturn 0;\n \t\t}\n \t\tp = p->next;\n@@ -601,16 +595,10 @@ static int get_parent(const char *name, int len,\n \treturn -1;\n }\n \n-static int get_nth_ancestor(const char *name, int len,\n-\t\t\t    unsigned char *result, int generation)\n+static int get_nth_ancestor(unsigned char *sha1, int generation)\n {\n-\tunsigned char sha1[20];\n \tstruct commit *commit;\n-\tint ret;\n \n-\tret = get_sha1_1(name, len, sha1, GET_SHA1_COMMITTISH);\n-\tif (ret)\n-\t\treturn ret;\n \tcommit = lookup_commit_reference(sha1);\n \tif (!commit)\n \t\treturn -1;\n@@ -620,7 +608,7 @@ static int get_nth_ancestor(const char *name, int len,\n \t\t\treturn -1;\n \t\tcommit = commit->parents->item;\n \t}\n-\thashcpy(result, commit->object.sha1);\n+\thashcpy(sha1, commit->object.sha1);\n \treturn 0;\n }\n \n@@ -649,12 +637,10 @@ struct object *peel_to_type(const char *name, int namelen,\n \t}\n }\n \n-static int peel_onion(const char *name, int len, unsigned char *sha1)\n+static int peel_onion(const char *name, const char *str, int len, unsigned char *sha1)\n {\n-\tunsigned char outer[20];\n-\tconst char *sp;\n+\tconst char *sp, *end = NULL;\n \tunsigned int expected_type = 0;\n-\tunsigned lookup_flags = 0;\n \tstruct object *o;\n \n \t/*\n@@ -665,18 +651,24 @@ static int peel_onion(const char *name, int len, unsigned char *sha1)\n \t * \"ref^{commit}\".  \"commit^{tree}\" could be used to find the\n \t * top-level tree of the given commit.\n \t */\n-\tif (len < 4 || name[len-1] != '}')\n-\t\treturn -1;\n \n-\tfor (sp = name + len - 1; name <= sp; sp--) {\n-\t\tint ch = *sp;\n-\t\tif (ch == '{' && name < sp && sp[-1] == '^')\n+\tif (len < 3)\n+\t\treturn 0;\n+\n+\tsp = str;\n+\tif (sp[0] != '^' || sp[1] != '{')\n+\t\treturn 0;\n+\n+\tfor (end = sp; *end; end++)\n+\t\tif (*end == '}')\n \t\t\tbreak;\n-\t}\n-\tif (sp <= name)\n-\t\treturn -1;\n+\tif (!end)\n+\t\treturn 0;\n+\n+\tend++;\n+\tlen = end - str;\n \n-\tsp++; /* beginning of type name, or closing brace for empty */\n+\tsp += 2;\n \tif (!strncmp(commit_type, sp, 6) && sp[6] == '}')\n \t\texpected_type = OBJ_COMMIT;\n \telse if (!strncmp(tree_type, sp, 4) && sp[4] == '}')\n@@ -692,35 +684,28 @@ static int peel_onion(const char *name, int len, unsigned char *sha1)\n \telse\n \t\treturn -1;\n \n-\tif (expected_type == OBJ_COMMIT)\n-\t\tlookup_flags = GET_SHA1_COMMITTISH;\n-\telse if (expected_type == OBJ_TREE)\n-\t\tlookup_flags = GET_SHA1_TREEISH;\n-\n-\tif (get_sha1_1(name, sp - name - 2, outer, lookup_flags))\n-\t\treturn -1;\n-\n-\to = parse_object(outer);\n+\to = parse_object(sha1);\n \tif (!o)\n \t\treturn -1;\n \tif (!expected_type) {\n-\t\to = deref_tag(o, name, sp - name - 2);\n+\t\to = deref_tag(o, name, end - name);\n \t\tif (!o || (!o->parsed && !parse_object(o->sha1)))\n \t\t\treturn -1;\n \t\thashcpy(sha1, o->sha1);\n-\t\treturn 0;\n+\t\treturn len;\n \t}\n \n \t/*\n-\t * At this point, the syntax look correct, so\n+\t * At this point, the syntax looks correct, so\n \t * if we do not get the needed object, we should\n \t * barf.\n \t */\n-\to = peel_to_type(name, len, o, expected_type);\n+\to = peel_to_type(name, end - name, o, expected_type);\n \tif (!o)\n \t\treturn -1;\n \n \thashcpy(sha1, o->sha1);\n+\n \tif (sp[0] == '/') {\n \t\t/* \"$commit^{/foo}\" */\n \t\tchar *prefix;\n@@ -732,15 +717,16 @@ static int peel_onion(const char *name, int len, unsigned char *sha1)\n \t\t * We don't need regex anyway. '' pattern always matches.\n \t\t */\n \t\tif (sp[1] == '}')\n-\t\t\treturn 0;\n+\t\t\treturn len;\n \n-\t\tprefix = xstrndup(sp + 1, name + len - 1 - (sp + 1));\n+\t\tprefix = xstrndup(sp + 1, end - sp - 2);\n \t\tcommit_list_insert((struct commit *)o, &list);\n \t\tret = get_sha1_oneline(prefix, sha1, list);\n \t\tfree(prefix);\n-\t\treturn ret;\n+\t\tif (ret)\n+\t\t\treturn -1;\n \t}\n-\treturn 0;\n+\treturn len;\n }\n \n static int get_describe_name(const char *name, int len, unsigned char *sha1)\n@@ -764,54 +750,6 @@ static int get_describe_name(const char *name, int len, unsigned char *sha1)\n \treturn -1;\n }\n \n-static int get_sha1_1(const char *name, int len, unsigned char *sha1, unsigned lookup_flags)\n-{\n-\tint ret, has_suffix;\n-\tconst char *cp;\n-\n-\t/*\n-\t * \"name~3\" is \"name^^^\", \"name~\" is \"name~1\", and \"name^\" is \"name^1\".\n-\t */\n-\thas_suffix = 0;\n-\tfor (cp = name + len - 1; name <= cp; cp--) {\n-\t\tint ch = *cp;\n-\t\tif ('0' <= ch && ch <= '9')\n-\t\t\tcontinue;\n-\t\tif (ch == '~' || ch == '^')\n-\t\t\thas_suffix = ch;\n-\t\tbreak;\n-\t}\n-\n-\tif (has_suffix) {\n-\t\tint num = 0;\n-\t\tint len1 = cp - name;\n-\t\tcp++;\n-\t\twhile (cp < name + len)\n-\t\t\tnum = num * 10 + *cp++ - '0';\n-\t\tif (!num && len1 == len - 1)\n-\t\t\tnum = 1;\n-\t\tif (has_suffix == '^')\n-\t\t\treturn get_parent(name, len1, sha1, num);\n-\t\t/* else if (has_suffix == '~') -- goes without saying */\n-\t\treturn get_nth_ancestor(name, len1, sha1, num);\n-\t}\n-\n-\tret = peel_onion(name, len, sha1);\n-\tif (!ret)\n-\t\treturn 0;\n-\n-\tret = get_sha1_basic(name, len, sha1);\n-\tif (!ret)\n-\t\treturn 0;\n-\n-\t/* It could be describe output that is \"SOMETHING-gXXXX\" */\n-\tret = get_describe_name(name, len, sha1);\n-\tif (!ret)\n-\t\treturn 0;\n-\n-\treturn get_short_sha1(name, len, sha1, lookup_flags);\n-}\n-\n /*\n  * This interprets names like ':/Initial revision of \"git\"' by searching\n  * through history and returning the first commit whose message starts\n@@ -1288,22 +1226,168 @@ static char *resolve_relative_path(const char *rel)\n \t\t\t   rel);\n }\n \n+static int resolve_ancestry(const char *str, int len, unsigned char *sha1)\n+{\n+\tint has_suffix;\n+\tconst char *cp, *end;\n+\tint num = 0, ret;\n+\n+\t/*\n+\t * \"name~3\" is \"name^^^\", \"name~\" is \"name~1\", and \"name^\" is \"name^1\".\n+\t */\n+\thas_suffix = 0;\n+\tfor (cp = str; *cp; cp++) {\n+\t\tint ch = *cp;\n+\t\tif ('0' <= ch && ch <= '9')\n+\t\t\tcontinue;\n+\t\tif (ch == '~' || ch == '^') {\n+\t\t\tif (has_suffix)\n+\t\t\t\tbreak;\n+\t\t\thas_suffix = ch;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tbreak;\n+\t}\n+\n+\tif (!has_suffix)\n+\t\treturn 0;\n+\n+\tend = cp;\n+\tcp = str + 1;\n+\tif (cp == end)\n+\t\tnum = 1;\n+\telse\n+\t\twhile (cp < end)\n+\t\t\tnum = num * 10 + *cp++ - '0';\n+\tlen = end - str;\n+\tif (has_suffix == '^')\n+\t\tret = get_parent(sha1, num);\n+\telse\n+\t\tret = get_nth_ancestor(sha1, num);\n+\tif (ret)\n+\t\treturn ret;\n+\treturn len;\n+}\n+\n+static int resolve_tree(struct object_context *oc, const char *str, int len,\n+\t\tunsigned char *sha1, unsigned char *tree_sha1)\n+{\n+\tint ret;\n+\tconst char *filename = str + 1;\n+\tchar *new_filename = NULL;\n+\n+\tnew_filename = resolve_relative_path(filename);\n+\tif (new_filename)\n+\t\tfilename = new_filename;\n+\thashcpy(tree_sha1, sha1);\n+\tret = get_tree_entry(tree_sha1, filename, sha1, &oc->mode);\n+\thashcpy(oc->tree, tree_sha1);\n+\tstrncpy(oc->path, filename, sizeof(oc->path));\n+\toc->path[sizeof(oc->path) - 1] = '\\0';\n+\n+\tfree(new_filename);\n+\treturn ret;\n+}\n+\n+static int resolve(const char *name, int len, unsigned char *sha1,\n+\t\tstruct object_context *oc, const char *prefix, unsigned flags)\n+{\n+\tconst char *cp;\n+\tint ret;\n+\tint tmp_len;\n+\tint bracket_depth;\n+\tunsigned char tree_sha1[20];\n+\tunsigned lookup_flags = flags;\n+\n+\tfor (cp = name, bracket_depth = 0; *cp; cp++) {\n+\t\tif (*cp == '{')\n+\t\t\tbracket_depth++;\n+\t\telse if (bracket_depth && *cp == '}')\n+\t\t\tbracket_depth--;\n+\t\telse if (!bracket_depth) {\n+\t\t\tif (*cp == '^') {\n+\t\t\t\tif (cp[1] == '{') {\n+\t\t\t\t\tconst char *sp = cp + 2;\n+\t\t\t\t\tif (!strncmp(commit_type, sp, 6) && sp[6] == '}')\n+\t\t\t\t\t\tlookup_flags = GET_SHA1_COMMITTISH;\n+\t\t\t\t\telse if (!strncmp(tree_type, sp, 4) && sp[4] == '}')\n+\t\t\t\t\t\tlookup_flags = GET_SHA1_TREEISH;\n+\t\t\t\t\telse if (sp[0] == '/')\n+\t\t\t\t\t\tlookup_flags = GET_SHA1_COMMITTISH;\n+\t\t\t\t\telse\n+\t\t\t\t\t\tlookup_flags = 0;\n+\t\t\t\t} else {\n+\t\t\t\t\tlookup_flags = GET_SHA1_COMMITTISH;\n+\t\t\t\t}\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (*cp == '~') {\n+\t\t\t\tlookup_flags = GET_SHA1_COMMITTISH;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (*cp == ':') {\n+\t\t\t\tlookup_flags = GET_SHA1_TREEISH;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\ttmp_len = cp - name;\n+\tret = get_sha1_basic(name, tmp_len, sha1);\n+\tif (!ret)\n+\t\tgoto next;\n+\tret = get_short_sha1(name, tmp_len, sha1, lookup_flags);\n+\tif (!ret)\n+\t\tgoto next;\n+\tret = get_describe_name(name, tmp_len, sha1);\n+\tif (!ret)\n+\t\tgoto next;\n+\n+\treturn -1;\n+\n+next:\n+\tif (!*cp)\n+\t\treturn 0;\n+\twhile (*cp == '^' || *cp == '~') {\n+\t\tret = peel_onion(name, cp, len - (cp - name), sha1);\n+\t\tif (ret < 0)\n+\t\t\treturn ret;\n+\t\tcp += ret;\n+\t\tret = resolve_ancestry(cp, len - (cp - name), sha1);\n+\t\tif (ret < 0)\n+\t\t\treturn ret;\n+\t\tcp += ret;\n+\t}\n+\tif (!*cp)\n+\t\treturn 0;\n+\tif (*cp != ':')\n+\t\t/* malformed */\n+\t\treturn -1;\n+\tret = resolve_tree(oc, cp, len - (cp - name), sha1, tree_sha1);\n+\tif (ret < 0) {\n+\t\tif (flags & GET_SHA1_ONLY_TO_DIE) {\n+\t\t\tdiagnose_invalid_sha1_path(prefix, oc->path,\n+\t\t\t\t\t\t   tree_sha1,\n+\t\t\t\t\t\t   name, cp - name);\n+\t\t}\n+\t\treturn ret;\n+\t}\n+\treturn 0;\n+}\n+\n static int get_sha1_with_context_1(const char *name,\n \t\t\t\t   unsigned flags,\n \t\t\t\t   const char *prefix,\n \t\t\t\t   unsigned char *sha1,\n \t\t\t\t   struct object_context *oc)\n {\n-\tint ret, bracket_depth;\n \tint namelen = strlen(name);\n \tconst char *cp;\n \tint only_to_die = flags & GET_SHA1_ONLY_TO_DIE;\n \n \tmemset(oc, 0, sizeof(*oc));\n \toc->mode = S_IFINVALID;\n-\tret = get_sha1_1(name, namelen, sha1, flags);\n-\tif (!ret)\n-\t\treturn ret;\n+\n \t/*\n \t * sha1:path --> object name of path in ent sha1\n \t * :path -> object name of absolute path in index\n@@ -1364,43 +1448,8 @@ static int get_sha1_with_context_1(const char *name,\n \t\tfree(new_path);\n \t\treturn -1;\n \t}\n-\tfor (cp = name, bracket_depth = 0; *cp; cp++) {\n-\t\tif (*cp == '{')\n-\t\t\tbracket_depth++;\n-\t\telse if (bracket_depth && *cp == '}')\n-\t\t\tbracket_depth--;\n-\t\telse if (!bracket_depth && *cp == ':')\n-\t\t\tbreak;\n-\t}\n-\tif (*cp == ':') {\n-\t\tunsigned char tree_sha1[20];\n-\t\tint len = cp - name;\n-\t\tif (!get_sha1_1(name, len, tree_sha1, GET_SHA1_TREEISH)) {\n-\t\t\tconst char *filename = cp+1;\n-\t\t\tchar *new_filename = NULL;\n-\n-\t\t\tnew_filename = resolve_relative_path(filename);\n-\t\t\tif (new_filename)\n-\t\t\t\tfilename = new_filename;\n-\t\t\tret = get_tree_entry(tree_sha1, filename, sha1, &oc->mode);\n-\t\t\tif (ret && only_to_die) {\n-\t\t\t\tdiagnose_invalid_sha1_path(prefix, filename,\n-\t\t\t\t\t\t\t   tree_sha1,\n-\t\t\t\t\t\t\t   name, len);\n-\t\t\t}\n-\t\t\thashcpy(oc->tree, tree_sha1);\n-\t\t\tstrncpy(oc->path, filename,\n-\t\t\t\tsizeof(oc->path));\n-\t\t\toc->path[sizeof(oc->path)-1] = '\\0';\n \n-\t\t\tfree(new_filename);\n-\t\t\treturn ret;\n-\t\t} else {\n-\t\t\tif (only_to_die)\n-\t\t\t\tdie(\"Invalid object name '%.*s'.\", len, name);\n-\t\t}\n-\t}\n-\treturn ret;\n+\treturn resolve(name, namelen, sha1, oc, prefix, flags);\n }\n \n /*\ndiff --git a/t/t1506-rev-parse-diagnosis.sh b/t/t1506-rev-parse-diagnosis.sh\nindex f950c10..0f76d1f 100755\n--- a/t/t1506-rev-parse-diagnosis.sh\n+++ b/t/t1506-rev-parse-diagnosis.sh\n@@ -104,7 +104,7 @@ test_expect_success 'correct relative file objects (6)' '\n \n test_expect_success 'incorrect revision id' '\n \ttest_must_fail git rev-parse foobar:file.txt 2>error &&\n-\tgrep \"Invalid object name '\"'\"'foobar'\"'\"'.\" error &&\n+\tgrep \"unknown revision or path not in the working tree.\" error\n \ttest_must_fail git rev-parse foobar 2> error &&\n \tgrep \"unknown revision or path not in the working tree.\" error\n '\n-- \n1.8.4-338-gefd7fa6\n"}]}