t/t4100/t-apply-7.patch

   1 diff a/Documentation/git-ls-tree.txt b/Documentation/git-ls-tree.txt
   2 --- a/Documentation/git-ls-tree.txt
   3 +++ b/Documentation/git-ls-tree.txt
   4 @@ -4,23 +4,26 @@ v0.1, May 2005
   5
   6  NAME
   7  ----
   8 -git-ls-tree - Displays a tree object in human readable form
   9 +git-ls-tree - Lists the contents of a tree object.
  10
  11
  12  SYNOPSIS
  13  --------
  14 -'git-ls-tree' [-r] [-z] <tree-ish> [paths...]
  15 +'git-ls-tree' [-d] [-r] [-z] <tree-ish> [paths...]
  16
  17  DESCRIPTION
  18  -----------
  19 -Converts the tree object to a human readable (and script processable)
  20 -form.
  21 +Lists the contents of a tree object, like what "/bin/ls -a" does
  22 +in the current working directory.
  23
  24  OPTIONS
  25  -------
  26  <tree-ish>::
  27         Id of a tree.
  28
  29 +-d::
  30 +       show only the named tree entry itself, not its children
  31 +
  32  -r::
  33         recurse into sub-trees
  34
  35 @@ -28,18 +31,19 @@ OPTIONS
  36         \0 line termination on output
  37
  38  paths::
  39 -       Optionally, restrict the output of git-ls-tree to specific
  40 -       paths. Directories will only list their tree blob ids.
  41 -       Implies -r.
  42 +       When paths are given, shows them.  Otherwise implicitly
  43 +       uses the root level of the tree as the sole path argument.
  44 +
  45
  46  Output Format
  47  -------------
  48 -        <mode>\t       <type>\t        <object>\t      <file>
  49 +        <mode> SP <type> SP <object> TAB <file>
  50
  51
  52  Author
  53  ------
  54  Written by Linus Torvalds <torvalds@osdl.org>
  55 +Completely rewritten from scratch by Junio C Hamano <junkio@cox.net>
  56
  57  Documentation
  58  --------------
  59 diff a/ls-tree.c b/ls-tree.c
  60 --- a/ls-tree.c
  61 +++ b/ls-tree.c
  62 @@ -4,188 +4,217 @@
  63   * Copyright (C) Linus Torvalds, 2005
  64   */
  65  #include "cache.h"
  66 +#include "blob.h"
  67 +#include "tree.h"
  68
  69  static int line_termination = '\n';
  70 -static int recursive = 0;
  71 +#define LS_RECURSIVE 1
  72 +#define LS_TREE_ONLY 2
  73 +static int ls_options = 0;
  74
  75 -struct path_prefix {
  76 -       struct path_prefix *prev;
  77 -       const char *name;
  78 -};
  79 -
  80 -#define DEBUG(fmt, ...)
  81 -
  82 -static int string_path_prefix(char *buff, size_t blen, struct path_prefix *prefix)
  83 -{
  84 -       int len = 0;
  85 -       if (prefix) {
  86 -               if (prefix->prev) {
  87 -                       len = string_path_prefix(buff,blen,prefix->prev);
  88 -                       buff += len;
  89 -                       blen -= len;
  90 -                       if (blen > 0) {
  91 -                               *buff = '/';
  92 -                               len++;
  93 -                               buff++;
  94 -                               blen--;
  95 -                       }
  96 -               }
  97 -               strncpy(buff,prefix->name,blen);
  98 -               return len + strlen(prefix->name);
  99 -       }
 100 +static struct tree_entry_list root_entry;
 101
 102 -       return 0;
 103 +static void prepare_root(unsigned char *sha1)
 104 +{
 105 +       unsigned char rsha[20];
 106 +       unsigned long size;
 107 +       void *buf;
 108 +       struct tree *root_tree;
 109 +
 110 +       buf = read_object_with_reference(sha1, "tree", &size, rsha);
 111 +       free(buf);
 112 +       if (!buf)
 113 +               die("Could not read %s", sha1_to_hex(sha1));
 114 +
 115 +       root_tree = lookup_tree(rsha);
 116 +       if (!root_tree)
 117 +               die("Could not read %s", sha1_to_hex(sha1));
 118 +
 119 +       /* Prepare a fake entry */
 120 +       root_entry.directory = 1;
 121 +       root_entry.executable = root_entry.symlink = 0;
 122 +       root_entry.mode = S_IFDIR;
 123 +       root_entry.name = "";
 124 +       root_entry.item.tree = root_tree;
 125 +       root_entry.parent = NULL;
 126  }
 127
 128 -static void print_path_prefix(struct path_prefix *prefix)
 129 +static int prepare_children(struct tree_entry_list *elem)
 130  {
 131 -       if (prefix) {
 132 -               if (prefix->prev) {
 133 -                       print_path_prefix(prefix->prev);
 134 -                       putchar('/');
 135 -               }
 136 -               fputs(prefix->name, stdout);
 137 +       if (!elem->directory)
 138 +               return -1;
 139 +       if (!elem->item.tree->object.parsed) {
 140 +               struct tree_entry_list *e;
 141 +               if (parse_tree(elem->item.tree))
 142 +                       return -1;
 143 +               /* Set up the parent link */
 144 +               for (e = elem->item.tree->entries; e; e = e->next)
 145 +                       e->parent = elem;
 146         }
 147 +       return 0;
 148  }
 149
 150 -/*
 151 - * return:
 152 - *     -1 if prefix is *not* a subset of path
 153 - *      0 if prefix == path
 154 - *      1 if prefix is a subset of path
 155 - */
 156 -static int pathcmp(const char *path, struct path_prefix *prefix)
 157 -{
 158 -       char buff[PATH_MAX];
 159 -       int len,slen;
 160 +static struct tree_entry_list *find_entry_0(struct tree_entry_list *elem,
 161 +                                           const char *path,
 162 +                                           const char *path_end)
 163 +{
 164 +       const char *ep;
 165 +       int len;
 166 +
 167 +       while (path < path_end) {
 168 +               if (prepare_children(elem))
 169 +                       return NULL;
 170
 171 -       if (prefix == NULL)
 172 -               return 1;
 173 +               /* In elem->tree->entries, find the one that has name
 174 +                * that matches what is between path and ep.
 175 +                */
 176 +               elem = elem->item.tree->entries;
 177
 178 -       len = string_path_prefix(buff, sizeof buff, prefix);
 179 -       slen = strlen(path);
 180 +               ep = strchr(path, '/');
 181 +               if (!ep || path_end <= ep)
 182 +                       ep = path_end;
 183 +               len = ep - path;
 184 +
 185 +               while (elem) {
 186 +                       if ((strlen(elem->name) == len) &&
 187 +                           !strncmp(elem->name, path, len))
 188 +                               break;
 189 +                       elem = elem->next;
 190 +               }
 191 +               if (path_end <= ep || !elem)
 192 +                       return elem;
 193 +               while (*ep == '/' && ep < path_end)
 194 +                       ep++;
 195 +               path = ep;
 196 +       }
 197 +       return NULL;
 198 +}
 199
 200 -       if (slen < len)
 201 -               return -1;
 202 +static struct tree_entry_list *find_entry(const char *path,
 203 +                                         const char *path_end)
 204 +{
 205 +       /* Find tree element, descending from root, that
 206 +        * corresponds to the named path, lazily expanding
 207 +        * the tree if possible.
 208 +        */
 209 +       if (path == path_end) {
 210 +               /* Special.  This is the root level */
 211 +               return &root_entry;
 212 +       }
 213 +       return find_entry_0(&root_entry, path, path_end);
 214 +}
 215
 216 -       if (strncmp(path,buff,len) == 0) {
 217 -               if (slen == len)
 218 -                       return 0;
 219 -               else
 220 -                       return 1;
 221 +static void show_entry_name(struct tree_entry_list *e)
 222 +{
 223 +       /* This is yucky.  The root level is there for
 224 +        * our convenience but we really want to do a
 225 +        * forest.
 226 +        */
 227 +       if (e->parent && e->parent != &root_entry) {
 228 +               show_entry_name(e->parent);
 229 +               putchar('/');
 230         }
 231 +       printf("%s", e->name);
 232 +}
 233
 234 -       return -1;
 235 -}
 236 +static const char *entry_type(struct tree_entry_list *e)
 237 +{
 238 +       return (e->directory ? "tree" : "blob");
 239 +}
 240
 241 -/*
 242 - * match may be NULL, or a *sorted* list of paths
 243 - */
 244 -static void list_recursive(void *buffer,
 245 -                          const char *type,
 246 -                          unsigned long size,
 247 -                          struct path_prefix *prefix,
 248 -                          char **match, int matches)
 249 -{
 250 -       struct path_prefix this_prefix;
 251 -       this_prefix.prev = prefix;
 252 -
 253 -       if (strcmp(type, "tree"))
 254 -               die("expected a 'tree' node");
 255 -
 256 -       if (matches)
 257 -               recursive = 1;
 258 -
 259 -       while (size) {
 260 -               int namelen = strlen(buffer)+1;
 261 -               void *eltbuf = NULL;
 262 -               char elttype[20];
 263 -               unsigned long eltsize;
 264 -               unsigned char *sha1 = buffer + namelen;
 265 -               char *path = strchr(buffer, ' ') + 1;
 266 -               unsigned int mode;
 267 -               const char *matched = NULL;
 268 -               int mtype = -1;
 269 -               int mindex;
 270 -
 271 -               if (size < namelen + 20 || sscanf(buffer, "%o", &mode) != 1)
 272 -                       die("corrupt 'tree' file");
 273 -               buffer = sha1 + 20;
 274 -               size -= namelen + 20;
 275 -
 276 -               this_prefix.name = path;
 277 -               for ( mindex = 0; mindex < matches; mindex++) {
 278 -                       mtype = pathcmp(match[mindex],&this_prefix);
 279 -                       if (mtype >= 0) {
 280 -                               matched = match[mindex];
 281 -                               break;
 282 -                       }
 283 -               }
 284 +static const char *entry_hex(struct tree_entry_list *e)
 285 +{
 286 +       return sha1_to_hex(e->directory
 287 +                          ? e->item.tree->object.sha1
 288 +                          : e->item.blob->object.sha1);
 289 +}
 290
 291 -               /*
 292 -                * If we're not matching, or if this is an exact match,
 293 -                * print out the info
 294 -                */
 295 -               if (!matches || (matched != NULL && mtype == 0)) {
 296 -                       printf("%06o %s %s\t", mode,
 297 -                              S_ISDIR(mode) ? "tree" : "blob",
 298 -                              sha1_to_hex(sha1));
 299 -                       print_path_prefix(&this_prefix);
 300 -                       putchar(line_termination);
 301 -               }
 302 +/* forward declaration for mutually recursive routines */
 303 +static int show_entry(struct tree_entry_list *, int);
 304
 305 -               if (! recursive || ! S_ISDIR(mode))
 306 -                       continue;
 307 +static int show_children(struct tree_entry_list *e, int level)
 308 +{
 309 +       if (prepare_children(e))
 310 +               die("internal error: ls-tree show_children called with non tree");
 311 +       e = e->item.tree->entries;
 312 +       while (e) {
 313 +               show_entry(e, level);
 314 +               e = e->next;
 315 +       }
 316 +       return 0;
 317 +}
 318
 319 -               if (matches && ! matched)
 320 -                       continue;
 321 +static int show_entry(struct tree_entry_list *e, int level)
 322 +{
 323 +       int err = 0;
 324
 325 -               if (! (eltbuf = read_sha1_file(sha1, elttype, &eltsize)) ) {
 326 -                       error("cannot read %s", sha1_to_hex(sha1));
 327 -                       continue;
 328 -               }
 329 +       if (e != &root_entry) {
 330 +               printf("%06o %s %s      ", e->mode, entry_type(e),
 331 +                      entry_hex(e));
 332 +               show_entry_name(e);
 333 +               putchar(line_termination);
 334 +       }
 335
 336 -               /* If this is an exact directory match, we may have
 337 -                * directory files following this path. Match on them.
 338 -                * Otherwise, we're at a pach subcomponent, and we need
 339 -                * to try to match again.
 340 +       if (e->directory) {
 341 +               /* If this is a directory, we have the following cases:
 342 +                * (1) This is the top-level request (explicit path from the
 343 +                *     command line, or "root" if there is no command line).
 344 +                *  a. Without any flag.  We show direct children.  We do not
 345 +                *     recurse into them.
 346 +                *  b. With -r.  We do recurse into children.
 347 +                *  c. With -d.  We do not recurse into children.
 348 +                * (2) We came here because our caller is either (1-a) or
 349 +                *     (1-b).
 350 +                *  a. Without any flag.  We do not show our children (which
 351 +                *     are grandchildren for the original request).
 352 +                *  b. With -r.  We continue to recurse into our children.
 353 +                *  c. With -d.  We should not have come here to begin with.
 354                  */
 355 -               if (mtype == 0)
 356 -                       mindex++;
 357 -
 358 -               list_recursive(eltbuf, elttype, eltsize, &this_prefix, &match[mindex], matches-mindex);
 359 -               free(eltbuf);
 360 +               if (level == 0 && !(ls_options & LS_TREE_ONLY))
 361 +                       /* case (1)-a and (1)-b */
 362 +                       err = err | show_children(e, level+1);
 363 +               else if (level && ls_options & LS_RECURSIVE)
 364 +                       /* case (2)-b */
 365 +                       err = err | show_children(e, level+1);
 366         }
 367 +       return err;
 368  }
 369
 370 -static int qcmp(const void *a, const void *b)
 371 +static int list_one(const char *path, const char *path_end)
 372  {
 373 -       return strcmp(*(char **)a, *(char **)b);
 374 +       int err = 0;
 375 +       struct tree_entry_list *e = find_entry(path, path_end);
 376 +       if (!e) {
 377 +               /* traditionally ls-tree does not complain about
 378 +                * missing path.  We may change this later to match
 379 +                * what "/bin/ls -a" does, which is to complain.
 380 +                */
 381 +               return err;
 382 +       }
 383 +       err = err | show_entry(e, 0);
 384 +       return err;
 385  }
 386
 387 -static int list(unsigned char *sha1,char **path)
 388 +static int list(char **path)
 389  {
 390 -       void *buffer;
 391 -       unsigned long size;
 392 -       int npaths;
 393 -
 394 -       for (npaths = 0; path[npaths] != NULL; npaths++)
 395 -               ;
 396 -
 397 -       qsort(path,npaths,sizeof(char *),qcmp);
 398 -
 399 -       buffer = read_object_with_reference(sha1, "tree", &size, NULL);
 400 -       if (!buffer)
 401 -               die("unable to read sha1 file");
 402 -       list_recursive(buffer, "tree", size, NULL, path, npaths);
 403 -       free(buffer);
 404 -       return 0;
 405 +       int i;
 406 +       int err = 0;
 407 +       for (i = 0; path[i]; i++) {
 408 +               int len = strlen(path[i]);
 409 +               while (0 <= len && path[i][len] == '/')
 410 +                       len--;
 411 +               err = err | list_one(path[i], path[i] + len);
 412 +       }
 413 +       return err;
 414  }
 415
 416 -static const char *ls_tree_usage = "git-ls-tree [-r] [-z] <key> [paths...]";
 417 +static const char *ls_tree_usage =
 418 +       "git-ls-tree [-d] [-r] [-z] <tree-ish> [path...]";
 419
 420  int main(int argc, char **argv)
 421  {
 422 +       static char *path0[] = { "", NULL };
 423 +       char **path;
 424         unsigned char sha1[20];
 425
 426         while (1 < argc && argv[1][0] == '-') {
 427 @@ -194,7 +223,10 @@ int main(int argc, char **argv)
 428                         line_termination = 0;
 429                         break;
 430                 case 'r':
 431 -                       recursive = 1;
 432 +                       ls_options |= LS_RECURSIVE;
 433 +                       break;
 434 +               case 'd':
 435 +                       ls_options |= LS_TREE_ONLY;
 436                         break;
 437                 default:
 438                         usage(ls_tree_usage);
 439 @@ -206,7 +238,10 @@ int main(int argc, char **argv)
 440                 usage(ls_tree_usage);
 441         if (get_sha1(argv[1], sha1) < 0)
 442                 usage(ls_tree_usage);
 443 -       if (list(sha1, &argv[2]) < 0)
 444 +
 445 +       path = (argc == 2) ? path0 : (argv + 2);
 446 +       prepare_root(sha1);
 447 +       if (list(path) < 0)
 448                 die("list failed");
 449         return 0;
 450  }
 451 diff a/t/t3100-ls-tree-restrict.sh b/t/t3100-ls-tree-restrict.sh
 452 --- a/t/t3100-ls-tree-restrict.sh
 453 +++ b/t/t3100-ls-tree-restrict.sh
 454 @@ -74,8 +74,8 @@ test_expect_success \
 455      'ls-tree filtered' \
 456      'git-ls-tree $tree path1 path0 >current &&
 457       cat >expected <<\EOF &&
 458 -100644 blob X  path0
 459  120000 blob X  path1
 460 +100644 blob X  path0
 461  EOF
 462       test_output'
 463
 464 @@ -85,7 +85,6 @@ test_expect_success \
 465       cat >expected <<\EOF &&
 466  040000 tree X  path2
 467  040000 tree X  path2/baz
 468 -100644 blob X  path2/baz/b
 469  120000 blob X  path2/bazbo
 470  100644 blob X  path2/foo
 471  EOF
 472 diff a/tree.c b/tree.c
 473 --- a/tree.c
 474 +++ b/tree.c
 475 @@ -133,7 +133,7 @@ int parse_tree_buffer(struct tree *item,
 476                 }
 477                 if (obj)
 478                         add_ref(&item->object, obj);
 479 -
 480 +               entry->parent = NULL; /* needs to be filled by the user */
 481                 *list_p = entry;
 482                 list_p = &entry->next;
 483         }
 484 diff a/tree.h b/tree.h
 485 --- a/tree.h
 486 +++ b/tree.h
 487 @@ -16,6 +16,7 @@ struct tree_entry_list {
 488                 struct tree *tree;
 489                 struct blob *blob;
 490         } item;
 491 +       struct tree_entry_list *parent;
 492  };
 493
 494  struct tree {