{"thread":{"id":"734","subject":"[PATCH] ls-tree path restriction semantics fixes","startedAt":"2005-05-27T12:08:51Z","lastAt":"2005-05-29T18:44:22Z","messageCount":7,"participants":["Jason McMullan","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4044","messageId":"20050527120851.GA11823@port.evillabs.net","threadId":"734","inReplyTo":null,"subject":"[PATCH] ls-tree path restriction semantics fixes","fromName":"Jason McMullan","fromEmail":"jason.mcmullan@timesys.com","sentAt":"2005-05-27T12:08:51Z","receivedAt":"2005-05-27T12:08:51Z","isPatch":true,"sender":{"key":"jason.mcmullan@timesys.com","avatar":null},"body":"This patch fixes the git-ls-tree semantics to be less stupid, namely:\n\t\n\t* ls of a 'tree' path should just return the SHA1 of the tree\n\t* ls of a 'tree' path with a trailing '/' should work properly\n\t* ls of two identical paths should have the same output as ls of\n\t  a single path. (I consider ls-tree's output to be a hash dictionary)\n\nAlso, I added test cases to verify that these issues are fixed.\n\nOld Results:\n\n\t$ git-ls-tree t\n\t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\t100644 blob 6882e23be568ccf14f3adb0c766139086f2ee952    t/Makefile\n\t100644 blob 2a94fdb0b83ab5fcbf1a2c6edaf36c2dbe765ec6    t/README\n\t100644 blob d920c6b3a3bfbb5994244a78d1ad99ce02748122    t/lib-read-tree-m-3way.sh\n\t...\n\n\t$ git-ls-tree t/\n\t(no output)\n\n\t$ git-ls-tree t t\n\t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\nNew Results:\n\n\t$ git-ls-tree f\n\t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\n\t$ git-ls-tree t/\n\t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\n\t$ git-ls-tree t t\n\t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\nSigned-Off-By: Jason McMullan <jason.mcmullan@timesys.com>\n\ndiff --git a/ls-tree.c b/ls-tree.c\n--- a/ls-tree.c\n+++ b/ls-tree.c\n@@ -13,8 +13,6 @@ struct path_prefix {\n \tconst char *name;\n };\n \n-#define DEBUG(fmt, ...)\t\n-\n static int string_path_prefix(char *buff, size_t blen, struct path_prefix *prefix)\n {\n \tint len = 0;\n@@ -118,6 +116,8 @@ static void list_recursive(void *buffer,\n \t\t\tmtype = pathcmp(match[mindex],&this_prefix);\n \t\t\tif (mtype >= 0) {\n \t\t\t\tmatched = match[mindex];\n+\t\t\t\t/* Skip over any duplicates */\n+\t\t\t\tfor (; mindex+1 < matches && strcmp(match[mindex+1],matched)==0; mindex++);\n \t\t\t\tbreak;\n \t\t\t}\n \t\t}\n@@ -140,19 +140,22 @@ static void list_recursive(void *buffer,\n \t\tif (matches && ! matched)\n \t\t\tcontinue;\n \n-\t\tif (! (eltbuf = read_sha1_file(sha1, elttype, &eltsize)) ) {\n-\t\t\terror(\"cannot read %s\", sha1_to_hex(sha1));\n-\t\t\tcontinue;\n-\t\t}\n-\n \t\t/* If this is an exact directory match, we may have\n \t\t * directory files following this path. Match on them.\n-\t\t * Otherwise, we're at a pach subcomponent, and we need\n+\t\t * Otherwise, we're at a path subcomponent, and we need\n \t\t * to try to match again.\n \t\t */\n \t\tif (mtype == 0)\n \t\t\tmindex++;\n \n+\t\tif (matched && matches-mindex==0)\n+\t\t\tcontinue;\n+\n+\t\tif (! (eltbuf = read_sha1_file(sha1, elttype, &eltsize)) ) {\n+\t\t\terror(\"cannot read %s\", sha1_to_hex(sha1));\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tlist_recursive(eltbuf, elttype, eltsize, &this_prefix, &match[mindex], matches-mindex);\n \t\tfree(eltbuf);\n \t}\n@@ -169,9 +172,14 @@ static int list(unsigned char *sha1,char\n \tunsigned long size;\n \tint npaths;\n \n-\tfor (npaths = 0; path[npaths] != NULL; npaths++)\n-\t\t;\n+\t/* Count the paths, and any trailling '/' */\n+\tfor (npaths = 0; path[npaths] != NULL; npaths++) {\n+\t\tchar *cp = strrchr(path[npaths],'/');\n+\t\tif (cp != NULL && *(cp+1) == 0)\n+\t\t\t*cp=0;\n+\t}\t\n \n+\t/* Sort the paths */\n \tqsort(path,npaths,sizeof(char *),qcmp);\n \n \tbuffer = read_object_with_reference(sha1, \"tree\", &size, NULL);\ndiff --git a/t/t3100-ls-tree-restrict.sh b/t/t3100-ls-tree-restrict.sh\n--- a/t/t3100-ls-tree-restrict.sh\n+++ b/t/t3100-ls-tree-restrict.sh\n@@ -84,10 +84,22 @@ test_expect_success \\\n     'git-ls-tree $tree path2 >current &&\n      cat >expected <<\\EOF &&\n 040000 tree X\tpath2\n-040000 tree X\tpath2/baz\n-100644 blob X\tpath2/baz/b\n-120000 blob X\tpath2/bazbo\n-100644 blob X\tpath2/foo\n+EOF\n+     test_output'\n+\n+test_expect_success \\\n+    'ls-tree filtered' \\\n+    'git-ls-tree $tree path2/ >current &&\n+     cat >expected <<\\EOF &&\n+040000 tree X\tpath2\n+EOF\n+     test_output'\n+\n+test_expect_success \\\n+    'ls-tree filtered' \\\n+    'git-ls-tree $tree path2 path2 >current &&\n+     cat >expected <<\\EOF &&\n+040000 tree X\tpath2\n EOF\n      test_output'\n \n@@ -96,7 +108,16 @@ test_expect_success \\\n     'git-ls-tree $tree path2/baz >current &&\n      cat >expected <<\\EOF &&\n 040000 tree X\tpath2/baz\n-100644 blob X\tpath2/baz/b\n+EOF\n+     test_output'\n+\n+test_expect_success \\\n+    'ls-tree filtered' \\\n+    'git-ls-tree $tree path2 path2/bazbo path2/baz >current &&\n+     cat >expected <<\\EOF &&\n+040000 tree X\tpath2\n+040000 tree X\tpath2/baz\n+120000 blob X\tpath2/bazbo\n EOF\n      test_output'\n \n"},{"id":"4065","messageId":"7vmzqgzg8a.fsf@assigned-by-dhcp.cox.net","threadId":"734","inReplyTo":"20050527120851.GA11823@port.evillabs.net","subject":"Re: [PATCH] ls-tree path restriction semantics fixes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-27T18:16:53Z","receivedAt":"2005-05-27T18:16:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JM\" == Jason McMullan <jason.mcmullan@timesys.com> writes:\n\nJM> This patch fixes the git-ls-tree semantics to be less stupid, namely:\nJM> \t* ls of a 'tree' path should just return the SHA1 of the tree\nJM> \t* ls of a 'tree' path with a trailing '/' should work properly\nJM> \t* ls of two identical paths should have the same output as ls of\nJM> \t  a single path. (I consider ls-tree's output to be a hash dictionary)\n\nI haven't read your code yet, but...\n\nJM> Old Results:\n\nJM> \t$ git-ls-tree t\nJM> \t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\nJM> \t100644 blob 6882e23be568ccf14f3adb0c766139086f2ee952    t/Makefile\nJM> \t100644 blob 2a94fdb0b83ab5fcbf1a2c6edaf36c2dbe765ec6    t/README\nJM> \t100644 blob d920c6b3a3bfbb5994244a78d1ad99ce02748122    t/lib-read-tree-m-3way.sh\nJM> \t...\n\nI presume the counterpart to this one in your \"New Results\"\nexample, which is spelled \"git-ls-tree f\" is a typo of\n\"git-ls-tree t\", but if that is the case I strongly disagree.\n\nWhat you really want is something similar to '-d' flag to\n/bin/ls.  You are interested in the directory itself not its\ncontents and I think your gripe is that giving a path that\nmatches a tree always descends into it (i.e. there is no way to\ndo the equivalent of \"/bin/ls -d t\").  I agree that it is a\nproblem, but changing \"/bin/ls t\" not to show the directory\ncontents of \"t\" is not a solution.\n\nJM> \t$ git-ls-tree t/\nJM> \t(no output)\n\nI agree with you that this is not what we want and we should\nbehave the same way as \"git-ls-tree t\" would in this case.\n\nJM> \t$ git-ls-tree t t\nJM> \t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n\nI do not know what you wanted to say in this example.  Your\n\"Old\" and \"New\" look the same to me.\n\n\n\n\n\n"},{"id":"4070","messageId":"1117221986.11542.29.camel@jmcmullan.timesys","threadId":"734","inReplyTo":"7vmzqgzg8a.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] ls-tree path restriction semantics fixes","fromName":"Jason McMullan","fromEmail":"jason.mcmullan@timesys.com","sentAt":"2005-05-27T19:26:25Z","receivedAt":"2005-05-27T19:26:25Z","isPatch":true,"sender":{"key":"jason.mcmullan@timesys.com","avatar":null},"body":"On Fri, 2005-05-27 at 11:16 -0700, Junio C Hamano wrote:\n> What you really want is something similar to '-d' flag to\n> /bin/ls.  You are interested in the directory itself not its\n> contents and I think your gripe is that giving a path that\n> matches a tree always descends into it (i.e. there is no way to\n> do the equivalent of \"/bin/ls -d t\").  I agree that it is a\n> problem, but changing \"/bin/ls t\" not to show the directory\n> contents of \"t\" is not a solution.\n\n  git-ls-tree reporting just the tree's hash is valid, because if\nyou want everything in that tree, you can just do:\n\ngit-ls-tree `git-ls-tree HEAD path/dir | (read m t h n; echo $h)`\n\n  I don't see the problem there.\n\n\n> JM> \t$ git-ls-tree t t\n> JM> \t040000 tree 4eeb3990955b8badc4c14712b89d8cd9fff02f15    t\n> \n> I do not know what you wanted to say in this example.  Your\n> \"Old\" and \"New\" look the same to me.\n\nThe problem was that 't' and 't t' produced *vastly* different output\nin the old code. 't' would emit everything in the tree, and 't t' would\nonly emit t's hash.\n\n-- \nJason McMullan <jason.mcmullan@timesys.com>\nTimeSys Corporation\n\n"},{"id":"4121","messageId":"7v1x7syqkm.fsf@assigned-by-dhcp.cox.net","threadId":"734","inReplyTo":"1117221986.11542.29.camel@jmcmullan.timesys","subject":"Re: [PATCH] ls-tree path restriction semantics fixes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-28T03:31:05Z","receivedAt":"2005-05-28T03:31:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JM\" == Jason McMullan <jason.mcmullan@timesys.com> writes:\n\nJM>   git-ls-tree reporting just the tree's hash is valid, because if\nJM> you want everything in that tree, you can just do:\n\nJM> git-ls-tree `git-ls-tree HEAD path/dir | (read m t h n; echo $h)`\n\nJM>   I don't see the problem there.\n\nI do not see the problem either in Turing sense, but that is\nlike saying you could code anything given an assembler.  There\nis a difference between being possible and being practical.\n\nI do think the current behaviour is broken, so I think we are in\nhalf agreement.  What I think is the cleanest would be to make\n\"git-ls-tree $tree\" behave similarly to what \"/bin/ls -a\" does.\nThen we have various combination of options, and also path\narguments, to think about.  How about doing something like this?\n\n - Running without any paths.\n\n   \"git-ls-tree $tree\" shows everything first level, just like\n   \"/bin/ls -a\" shows everything in cwd.  There is nothing to\n   fix here.\n\n - Running with paths.\n\n   \"git-ls-tree $tree path1 path2...\" should show path$n if\n   path$n is not a tree and everything under path$n including\n   path$n itself if path$n is a tree, just like the way \"/bin/ls\n   -a path1 path2...\" works.  There is major breakage here as\n   you pointed out with your \"git-ls-tree $tree t\" vs\n   \"git-ls-tree $tree t t\" example.\n\n - Recursive behaviour without paths.\n\n   \"git-ls-tree -r $tree\" should show everything recursively,\n   just like what \"/bin/ls -a -R\" does.  There is nothing to\n   fix.\n\n - Recursive behaviour with paths.\n\n   \"git-ls-tree -r $tree path1 path2...\" should show everything\n   recursively under path$n, just like what \"/bin/ls -a -R path1\n   path2...\" does.  Again this is not how it currently works as\n   you pointed out.\n\n - With paths but not descending into them.\n\n   \"git-ls-tree -d $tree path1 path2...\" should show only the\n   named path$n even when path$n is a tree, just like what\n   \"/bin/ls -a -R -d path1 path2...\" does.  This is what is\n   missing from today's git-ls-tree.\n\n"},{"id":"4124","messageId":"7vll5zygn1.fsf_-_@assigned-by-dhcp.cox.net","threadId":"734","inReplyTo":"7v1x7syqkm.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH-RFC] Rewrite ls-tree to behave more like \"/bin/ls -a\"","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-28T07:05:38Z","receivedAt":"2005-05-28T07:05:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is a complete rewrite of ls-tree to make it behave more\nlike what \"/bin/ls -a\" does in the current working directory.\n\nNamely, the changes are:\n\n - Unlike the old ls-tree behaviour that used paths arguments to\n   restrict output (not that it worked as intended---as pointed\n   out in the mailing list discussion, it was quite incoherent),\n   this rewrite uses paths arguments to specify what to show.\n\n - Without arguments, it implicitly uses the root level as its\n   sole argument (\"/bin/ls -a\" behaves as if \".\" is given\n   without argument).\n\n - Without -r (recursive) flag, it shows the named blob (either\n   file or symlink), or the named tree and its immediate\n   children.\n\n - With -r flag, it shows the named path, and recursively\n   descends into it if it is a tree.\n\n - With -d flag, it shows the named path and does not show its\n   children even if the path is a tree, nor descends into it\n   recursively.\n\nThis is still request-for-comments patch.  There is no mailing\nlist consensus that this proposed new behaviour is a good one.\n\nThe patch to t/t3100-ls-tree-restrict.sh illustrates\nuser-visible behaviour changes.  Namely:\n\n * \"git-ls-tree $tree path1 path0\" lists path1 first and then\n   path0.  It used to use paths as an output restrictor and\n   showed output in cache entry order (i.e. path0 first and then\n   path1) regardless of the order of paths arguments.\n\n * \"git-ls-tree $tree path2\" lists path2 and its immediate\n   children but having explicit paths argument does not imply\n   recursive behaviour anymore, hence paths/baz is shown but not\n   paths/baz/b.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\nDocumentation/git-ls-tree.txt |   20 +-\nls-tree.c                     |  333 +++++++++++++++++++++++-------------------\nt/t3100-ls-tree-restrict.sh   |    3 \ntree.c                        |    2 \ntree.h                        |    1 \n5 files changed, 199 insertions(+), 160 deletions(-)\n\ndiff --git a/Documentation/git-ls-tree.txt b/Documentation/git-ls-tree.txt\n--- a/Documentation/git-ls-tree.txt\n+++ b/Documentation/git-ls-tree.txt\n@@ -4,23 +4,26 @@ v0.1, May 2005\n \n NAME\n ----\n-git-ls-tree - Displays a tree object in human readable form\n+git-ls-tree - Lists the contents of a tree object.\n \n \n SYNOPSIS\n --------\n-'git-ls-tree' [-r] [-z] <tree-ish> [paths...]\n+'git-ls-tree' [-d] [-r] [-z] <tree-ish> [paths...]\n \n DESCRIPTION\n -----------\n-Converts the tree object to a human readable (and script processable)\n-form.\n+Lists the contents of a tree object, like what \"/bin/ls -a\" does\n+in the current working directory.\n \n OPTIONS\n -------\n <tree-ish>::\n \tId of a tree.\n \n+-d::\n+\tshow only the named tree entry itself, not its children\n+\n -r::\n \trecurse into sub-trees\n \n@@ -28,18 +31,19 @@ OPTIONS\n \t\\0 line termination on output\n \n paths::\n-\tOptionally, restrict the output of git-ls-tree to specific\n-\tpaths. Directories will only list their tree blob ids.\n-\tImplies -r.\n+\tWhen paths are given, shows them.  Otherwise implicitly\n+\tuses the root level of the tree as the sole path argument.\n+\n \n Output Format\n -------------\n-        <mode>\\t\t<type>\\t\t<object>\\t\t<file>\n+        <mode> SP <type> SP <object> TAB <file>\n \n \n Author\n ------\n Written by Linus Torvalds <torvalds@osdl.org>\n+Completely rewritten from scratch by Junio C Hamano <junkio@cox.net>\n \n Documentation\n --------------\ndiff --git a/ls-tree.c b/ls-tree.c\n--- a/ls-tree.c\n+++ b/ls-tree.c\n@@ -4,188 +4,217 @@\n  * Copyright (C) Linus Torvalds, 2005\n  */\n #include \"cache.h\"\n+#include \"blob.h\"\n+#include \"tree.h\"\n \n static int line_termination = '\\n';\n-static int recursive = 0;\n+#define LS_RECURSIVE 1\n+#define LS_TREE_ONLY 2\n+static int ls_options = 0;\n \n-struct path_prefix {\n-\tstruct path_prefix *prev;\n-\tconst char *name;\n-};\n-\n-#define DEBUG(fmt, ...)\t\n-\n-static int string_path_prefix(char *buff, size_t blen, struct path_prefix *prefix)\n-{\n-\tint len = 0;\n-\tif (prefix) {\n-\t\tif (prefix->prev) {\n-\t\t\tlen = string_path_prefix(buff,blen,prefix->prev);\n-\t\t\tbuff += len;\n-\t\t\tblen -= len;\n-\t\t\tif (blen > 0) {\n-\t\t\t\t*buff = '/';\n-\t\t\t\tlen++;\n-\t\t\t\tbuff++;\n-\t\t\t\tblen--;\n-\t\t\t}\n-\t\t}\n-\t\tstrncpy(buff,prefix->name,blen);\n-\t\treturn len + strlen(prefix->name);\n-\t}\n+static struct tree_entry_list root_entry;\n \n-\treturn 0;\n+static void prepare_root(unsigned char *sha1)\n+{\n+\tunsigned char rsha[20];\n+\tunsigned long size;\n+\tvoid *buf;\n+\tstruct tree *root_tree;\n+\n+\tbuf = read_object_with_reference(sha1, \"tree\", &size, rsha);\n+\tfree(buf);\n+\tif (!buf)\n+\t\tdie(\"Could not read %s\", sha1_to_hex(sha1));\n+\n+\troot_tree = lookup_tree(rsha);\n+\tif (!root_tree)\n+\t\tdie(\"Could not read %s\", sha1_to_hex(sha1));\n+\n+\t/* Prepare a fake entry */\n+\troot_entry.directory = 1;\n+\troot_entry.executable = root_entry.symlink = 0;\n+\troot_entry.mode = S_IFDIR;\n+\troot_entry.name = \"\";\n+\troot_entry.item.tree = root_tree;\n+\troot_entry.parent = NULL;\n }\n \n-static void print_path_prefix(struct path_prefix *prefix)\n+static int prepare_children(struct tree_entry_list *elem)\n {\n-\tif (prefix) {\n-\t\tif (prefix->prev) {\n-\t\t\tprint_path_prefix(prefix->prev);\n-\t\t\tputchar('/');\n-\t\t}\n-\t\tfputs(prefix->name, stdout);\n+\tif (!elem->directory)\n+\t\treturn -1;\n+\tif (!elem->item.tree->object.parsed) {\n+\t\tstruct tree_entry_list *e;\n+\t\tif (parse_tree(elem->item.tree))\n+\t\t\treturn -1;\n+\t\t/* Set up the parent link */\n+\t\tfor (e = elem->item.tree->entries; e; e = e->next)\n+\t\t\te->parent = elem;\n \t}\n+\treturn 0;\n }\n \n-/*\n- * return:\n- * \t-1 if prefix is *not* a subset of path\n- * \t 0 if prefix == path\n- * \t 1 if prefix is a subset of path\n- */\n-static int pathcmp(const char *path, struct path_prefix *prefix)\n-{\n-\tchar buff[PATH_MAX];\n-\tint len,slen;\n+static struct tree_entry_list *find_entry_0(struct tree_entry_list *elem,\n+\t\t\t\t\t    const char *path,\n+\t\t\t\t\t    const char *path_end)\n+{\n+\tconst char *ep;\n+\tint len;\n+\n+\twhile (path < path_end) {\n+\t\tif (prepare_children(elem))\n+\t\t\treturn NULL;\n \n-\tif (prefix == NULL)\n-\t\treturn 1;\n+\t\t/* In elem->tree->entries, find the one that has name\n+\t\t * that matches what is between path and ep.\n+\t\t */\n+\t\telem = elem->item.tree->entries;\n \n-\tlen = string_path_prefix(buff, sizeof buff, prefix);\n-\tslen = strlen(path);\n+\t\tep = strchr(path, '/');\n+\t\tif (!ep || path_end <= ep)\n+\t\t\tep = path_end;\n+\t\tlen = ep - path;\n+\n+\t\twhile (elem) {\n+\t\t\tif ((strlen(elem->name) == len) &&\n+\t\t\t    !strncmp(elem->name, path, len))\n+\t\t\t\tbreak;\n+\t\t\telem = elem->next;\n+\t\t}\n+\t\tif (path_end <= ep || !elem)\n+\t\t\treturn elem;\n+\t\twhile (*ep == '/' && ep < path_end)\n+\t\t\tep++;\n+\t\tpath = ep;\n+\t}\n+\treturn NULL;\n+}\n \n-\tif (slen < len)\n-\t\treturn -1;\n+static struct tree_entry_list *find_entry(const char *path,\n+\t\t\t\t\t  const char *path_end)\n+{\n+\t/* Find tree element, descending from root, that\n+\t * corresponds to the named path, lazily expanding\n+\t * the tree if possible.\n+\t */\n+\tif (path == path_end) {\n+\t\t/* Special.  This is the root level */\n+\t\treturn &root_entry;\n+\t}\n+\treturn find_entry_0(&root_entry, path, path_end);\n+}\n \n-\tif (strncmp(path,buff,len) == 0) {\n-\t\tif (slen == len)\n-\t\t\treturn 0;\n-\t\telse\n-\t\t\treturn 1;\n+static void show_entry_name(struct tree_entry_list *e)\n+{\n+\t/* This is yucky.  The root level is there for\n+\t * our convenience but we really want to do a\n+\t * forest.\n+\t */\n+\tif (e->parent && e->parent != &root_entry) {\n+\t\tshow_entry_name(e->parent);\n+\t\tputchar('/');\n \t}\n+\tprintf(\"%s\", e->name);\n+}\n \n-\treturn -1;\n-}\t\n+static const char *entry_type(struct tree_entry_list *e)\n+{\n+\treturn (e->directory ? \"tree\" : \"blob\");\n+}\n \n-/*\n- * match may be NULL, or a *sorted* list of paths\n- */\n-static void list_recursive(void *buffer,\n-\t\t\t   const char *type,\n-\t\t\t   unsigned long size,\n-\t\t\t   struct path_prefix *prefix,\n-\t\t\t   char **match, int matches)\n-{\n-\tstruct path_prefix this_prefix;\n-\tthis_prefix.prev = prefix;\n-\n-\tif (strcmp(type, \"tree\"))\n-\t\tdie(\"expected a 'tree' node\");\n-\n-\tif (matches)\n-\t\trecursive = 1;\n-\n-\twhile (size) {\n-\t\tint namelen = strlen(buffer)+1;\n-\t\tvoid *eltbuf = NULL;\n-\t\tchar elttype[20];\n-\t\tunsigned long eltsize;\n-\t\tunsigned char *sha1 = buffer + namelen;\n-\t\tchar *path = strchr(buffer, ' ') + 1;\n-\t\tunsigned int mode;\n-\t\tconst char *matched = NULL;\n-\t\tint mtype = -1;\n-\t\tint mindex;\n-\n-\t\tif (size < namelen + 20 || sscanf(buffer, \"%o\", &mode) != 1)\n-\t\t\tdie(\"corrupt 'tree' file\");\n-\t\tbuffer = sha1 + 20;\n-\t\tsize -= namelen + 20;\n-\n-\t\tthis_prefix.name = path;\n-\t\tfor ( mindex = 0; mindex < matches; mindex++) {\n-\t\t\tmtype = pathcmp(match[mindex],&this_prefix);\n-\t\t\tif (mtype >= 0) {\n-\t\t\t\tmatched = match[mindex];\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n+static const char *entry_hex(struct tree_entry_list *e)\n+{\n+\treturn sha1_to_hex(e->directory\n+\t\t\t   ? e->item.tree->object.sha1\n+\t\t\t   : e->item.blob->object.sha1);\n+}\n \n-\t\t/*\n-\t\t * If we're not matching, or if this is an exact match,\n-\t\t * print out the info\n-\t\t */\n-\t\tif (!matches || (matched != NULL && mtype == 0)) {\n-\t\t\tprintf(\"%06o %s %s\\t\", mode,\n-\t\t\t       S_ISDIR(mode) ? \"tree\" : \"blob\",\n-\t\t\t       sha1_to_hex(sha1));\n-\t\t\tprint_path_prefix(&this_prefix);\n-\t\t\tputchar(line_termination);\n-\t\t}\n+/* forward declaration for mutually recursive routines */\n+static int show_entry(struct tree_entry_list *, int);\n \n-\t\tif (! recursive || ! S_ISDIR(mode))\n-\t\t\tcontinue;\n+static int show_children(struct tree_entry_list *e, int level)\n+{\n+\tif (prepare_children(e))\n+\t\tdie(\"internal error: ls-tree show_children called with non tree\");\n+\te = e->item.tree->entries;\n+\twhile (e) {\n+\t\tshow_entry(e, level);\n+\t\te = e->next;\n+\t}\n+\treturn 0;\n+}\n \n-\t\tif (matches && ! matched)\n-\t\t\tcontinue;\n+static int show_entry(struct tree_entry_list *e, int level)\n+{\n+\tint err = 0; \n \n-\t\tif (! (eltbuf = read_sha1_file(sha1, elttype, &eltsize)) ) {\n-\t\t\terror(\"cannot read %s\", sha1_to_hex(sha1));\n-\t\t\tcontinue;\n-\t\t}\n+\tif (e != &root_entry) {\n+\t\tprintf(\"%06o %s %s\t\", e->mode, entry_type(e),\n+\t\t       entry_hex(e));\n+\t\tshow_entry_name(e);\n+\t\tputchar(line_termination);\n+\t}\n \n-\t\t/* If this is an exact directory match, we may have\n-\t\t * directory files following this path. Match on them.\n-\t\t * Otherwise, we're at a pach subcomponent, and we need\n-\t\t * to try to match again.\n+\tif (e->directory) {\n+\t\t/* If this is a directory, we have the following cases:\n+\t\t * (1) This is the top-level request (explicit path from the\n+\t\t *     command line, or \"root\" if there is no command line).\n+\t\t *  a. Without any flag.  We show direct children.  We do not \n+\t\t *     recurse into them.\n+\t\t *  b. With -r.  We do recurse into children.\n+\t\t *  c. With -d.  We do not recurse into children.\n+\t\t * (2) We came here because our caller is either (1-a) or\n+\t\t *     (1-b).\n+\t\t *  a. Without any flag.  We do not show our children (which\n+\t\t *     are grandchildren for the original request).\n+\t\t *  b. With -r.  We continue to recurse into our children.\n+\t\t *  c. With -d.  We should not have come here to begin with.\n \t\t */\n-\t\tif (mtype == 0)\n-\t\t\tmindex++;\n-\n-\t\tlist_recursive(eltbuf, elttype, eltsize, &this_prefix, &match[mindex], matches-mindex);\n-\t\tfree(eltbuf);\n+\t\tif (level == 0 && !(ls_options & LS_TREE_ONLY))\n+\t\t\t/* case (1)-a and (1)-b */\n+\t\t\terr = err | show_children(e, level+1);\n+\t\telse if (level && ls_options & LS_RECURSIVE)\n+\t\t\t/* case (2)-b */\n+\t\t\terr = err | show_children(e, level+1);\n \t}\n+\treturn err;\n }\n \n-static int qcmp(const void *a, const void *b)\n+static int list_one(const char *path, const char *path_end)\n {\n-\treturn strcmp(*(char **)a, *(char **)b);\n+\tint err = 0;\n+\tstruct tree_entry_list *e = find_entry(path, path_end);\n+\tif (!e) {\n+\t\t/* traditionally ls-tree does not complain about\n+\t\t * missing path.  We may change this later to match\n+\t\t * what \"/bin/ls -a\" does, which is to complain.\n+\t\t */\n+\t\treturn err;\n+\t}\n+\terr = err | show_entry(e, 0);\n+\treturn err;\n }\n \n-static int list(unsigned char *sha1,char **path)\n+static int list(char **path)\n {\n-\tvoid *buffer;\n-\tunsigned long size;\n-\tint npaths;\n-\n-\tfor (npaths = 0; path[npaths] != NULL; npaths++)\n-\t\t;\n-\n-\tqsort(path,npaths,sizeof(char *),qcmp);\n-\n-\tbuffer = read_object_with_reference(sha1, \"tree\", &size, NULL);\n-\tif (!buffer)\n-\t\tdie(\"unable to read sha1 file\");\n-\tlist_recursive(buffer, \"tree\", size, NULL, path, npaths);\n-\tfree(buffer);\n-\treturn 0;\n+\tint i;\n+\tint err = 0;\n+\tfor (i = 0; path[i]; i++) {\n+\t\tint len = strlen(path[i]);\n+\t\twhile (0 <= len && path[i][len] == '/')\n+\t\t\tlen--;\n+\t\terr = err | list_one(path[i], path[i] + len);\n+\t}\n+\treturn err;\n }\n \n-static const char *ls_tree_usage = \"git-ls-tree [-r] [-z] <key> [paths...]\";\n+static const char *ls_tree_usage =\n+\t\"git-ls-tree [-d] [-r] [-z] <tree-ish> [path...]\";\n \n int main(int argc, char **argv)\n {\n+\tstatic char *path0[] = { \"\", NULL };\n+\tchar **path;\n \tunsigned char sha1[20];\n \n \twhile (1 < argc && argv[1][0] == '-') {\n@@ -194,7 +223,10 @@ int main(int argc, char **argv)\n \t\t\tline_termination = 0;\n \t\t\tbreak;\n \t\tcase 'r':\n-\t\t\trecursive = 1;\n+\t\t\tls_options |= LS_RECURSIVE;\n+\t\t\tbreak;\n+\t\tcase 'd':\n+\t\t\tls_options |= LS_TREE_ONLY;\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tusage(ls_tree_usage);\n@@ -206,7 +238,10 @@ int main(int argc, char **argv)\n \t\tusage(ls_tree_usage);\n \tif (get_sha1(argv[1], sha1) < 0)\n \t\tusage(ls_tree_usage);\n-\tif (list(sha1, &argv[2]) < 0)\n+\n+\tpath = (argc == 2) ? path0 : (argv + 2);\n+\tprepare_root(sha1);\n+\tif (list(path) < 0)\n \t\tdie(\"list failed\");\n \treturn 0;\n }\ndiff --git a/t/t3100-ls-tree-restrict.sh b/t/t3100-ls-tree-restrict.sh\n--- a/t/t3100-ls-tree-restrict.sh\n+++ b/t/t3100-ls-tree-restrict.sh\n@@ -74,8 +74,8 @@ test_expect_success \\\n     'ls-tree filtered' \\\n     'git-ls-tree $tree path1 path0 >current &&\n      cat >expected <<\\EOF &&\n-100644 blob X\tpath0\n 120000 blob X\tpath1\n+100644 blob X\tpath0\n EOF\n      test_output'\n \n@@ -85,7 +85,6 @@ test_expect_success \\\n      cat >expected <<\\EOF &&\n 040000 tree X\tpath2\n 040000 tree X\tpath2/baz\n-100644 blob X\tpath2/baz/b\n 120000 blob X\tpath2/bazbo\n 100644 blob X\tpath2/foo\n EOF\ndiff --git a/tree.c b/tree.c\n--- a/tree.c\n+++ b/tree.c\n@@ -133,7 +133,7 @@ int parse_tree_buffer(struct tree *item,\n \t\t}\n \t\tif (obj)\n \t\t\tadd_ref(&item->object, obj);\n-\n+\t\tentry->parent = NULL; /* needs to be filled by the user */\n \t\t*list_p = entry;\n \t\tlist_p = &entry->next;\n \t}\ndiff --git a/tree.h b/tree.h\n--- a/tree.h\n+++ b/tree.h\n@@ -16,6 +16,7 @@ struct tree_entry_list {\n \t\tstruct tree *tree;\n \t\tstruct blob *blob;\n \t} item;\n+\tstruct tree_entry_list *parent;\n };\n \n struct tree {\n------------------------------------------------\n\n"},{"id":"4147","messageId":"1117317729.11542.32.camel@jmcmullan.timesys","threadId":"734","inReplyTo":"7vll5zygn1.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH-RFC] Rewrite ls-tree to behave more like \"/bin/ls -a\"","fromName":"Jason McMullan","fromEmail":"jason.mcmullan@timesys.com","sentAt":"2005-05-28T22:02:08Z","receivedAt":"2005-05-28T22:02:08Z","isPatch":true,"sender":{"key":"jason.mcmullan@timesys.com","avatar":null},"body":"On Sat, 2005-05-28 at 00:05 -0700, Junio C Hamano wrote:\n>  - Unlike the old ls-tree behaviour that used paths arguments to\n>    restrict output (not that it worked as intended---as pointed\n>    out in the mailing list discussion, it was quite incoherent),\n>    this rewrite uses paths arguments to specify what to show.\n> \n>  - Without arguments, it implicitly uses the root level as its\n>    sole argument (\"/bin/ls -a\" behaves as if \".\" is given\n>    without argument).\n> \n>  - Without -r (recursive) flag, it shows the named blob (either\n>    file or symlink), or the named tree and its immediate\n>    children.\n> \n>  - With -r flag, it shows the named path, and recursively\n>    descends into it if it is a tree.\n> \n>  - With -d flag, it shows the named path and does not show its\n>    children even if the path is a tree, nor descends into it\n>    recursively.\n\nThis behavior pattern is very agreeable. I'll take it!\n\nConsider your patch:\n\nSigned-Off-By: Jason McMullan <jason.mcmullan@timesys.com>\n\n-- \nJason McMullan <jason.mcmullan@timesys.com>\nTimeSys Corporation\n\n"},{"id":"4182","messageId":"7vhdgloos9.fsf@assigned-by-dhcp.cox.net","threadId":"734","inReplyTo":"1117317729.11542.32.camel@jmcmullan.timesys","subject":"Re: [PATCH-RFC] Rewrite ls-tree to behave more like \"/bin/ls -a\"","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-29T18:44:22Z","receivedAt":"2005-05-29T18:44:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JM\" == Jason McMullan <jason.mcmullan@timesys.com> writes:\n\nJM> On Sat, 2005-05-28 at 00:05 -0700, Junio C Hamano wrote:\n\n>> - Unlike the old ls-tree behaviour that used paths arguments to\n>> restrict output (not that it worked as intended---as pointed\n>> out in the mailing list discussion, it was quite incoherent),\n>> this rewrite uses paths arguments to specify what to show.\n>> ...\n\nJM> This behavior pattern is very agreeable. I'll take it!\n\nGlad to know we are in agreement.\n\nBTW, long after finishing the rewrite, I realized that all of\nthe problems you raised did not exist in the very original\nversion of ls-tree, but were bugs in _your_ patch that added the\npaths restriction.  I was merely cleaning up your mess for you\nwithout knowing what I was doing. ;-) Not that I do not like\nwhat the resulting code does, though.\n\nI am not going to re-submit this to Linus right now, since he\nseems to be quiet here and spending more time and attention to\nthe kernel, which is what I want to see.  When Linus starts\npulling in update for GIT, and if you see this one not applied\nto his tree, please remind him.\n\n"}]}