[PATCH] Rewrite ls-tree to behave more like "/bin/ls -a"
[git] / ls-tree.c
1 /*
2  * GIT - The information manager from hell
3  *
4  * Copyright (C) Linus Torvalds, 2005
5  */
6 #include "cache.h"
7 #include "blob.h"
8 #include "tree.h"
9
10 static int line_termination = '\n';
11 #define LS_RECURSIVE 1
12 #define LS_TREE_ONLY 2
13 static int ls_options = 0;
14
15 static struct tree_entry_list root_entry;
16
17 static void prepare_root(unsigned char *sha1)
18 {
19         unsigned char rsha[20];
20         unsigned long size;
21         void *buf;
22         struct tree *root_tree;
23
24         buf = read_object_with_reference(sha1, "tree", &size, rsha);
25         free(buf);
26         if (!buf)
27                 die("Could not read %s", sha1_to_hex(sha1));
28
29         root_tree = lookup_tree(rsha);
30         if (!root_tree)
31                 die("Could not read %s", sha1_to_hex(sha1));
32
33         /* Prepare a fake entry */
34         root_entry.directory = 1;
35         root_entry.executable = root_entry.symlink = 0;
36         root_entry.mode = S_IFDIR;
37         root_entry.name = "";
38         root_entry.item.tree = root_tree;
39         root_entry.parent = NULL;
40 }
41
42 static int prepare_children(struct tree_entry_list *elem)
43 {
44         if (!elem->directory)
45                 return -1;
46         if (!elem->item.tree->object.parsed) {
47                 struct tree_entry_list *e;
48                 if (parse_tree(elem->item.tree))
49                         return -1;
50                 /* Set up the parent link */
51                 for (e = elem->item.tree->entries; e; e = e->next)
52                         e->parent = elem;
53         }
54         return 0;
55 }
56
57 static struct tree_entry_list *find_entry_0(struct tree_entry_list *elem,
58                                             const char *path,
59                                             const char *path_end)
60 {
61         const char *ep;
62         int len;
63
64         while (path < path_end) {
65                 if (prepare_children(elem))
66                         return NULL;
67
68                 /* In elem->tree->entries, find the one that has name
69                  * that matches what is between path and ep.
70                  */
71                 elem = elem->item.tree->entries;
72
73                 ep = strchr(path, '/');
74                 if (!ep || path_end <= ep)
75                         ep = path_end;
76                 len = ep - path;
77
78                 while (elem) {
79                         if ((strlen(elem->name) == len) &&
80                             !strncmp(elem->name, path, len))
81                                 break;
82                         elem = elem->next;
83                 }
84                 if (path_end <= ep || !elem)
85                         return elem;
86                 while (*ep == '/' && ep < path_end)
87                         ep++;
88                 path = ep;
89         }
90         return NULL;
91 }
92
93 static struct tree_entry_list *find_entry(const char *path,
94                                           const char *path_end)
95 {
96         /* Find tree element, descending from root, that
97          * corresponds to the named path, lazily expanding
98          * the tree if possible.
99          */
100         if (path == path_end) {
101                 /* Special.  This is the root level */
102                 return &root_entry;
103         }
104         return find_entry_0(&root_entry, path, path_end);
105 }
106
107 static void show_entry_name(struct tree_entry_list *e)
108 {
109         /* This is yucky.  The root level is there for
110          * our convenience but we really want to do a
111          * forest.
112          */
113         if (e->parent && e->parent != &root_entry) {
114                 show_entry_name(e->parent);
115                 putchar('/');
116         }
117         printf("%s", e->name);
118 }
119
120 static const char *entry_type(struct tree_entry_list *e)
121 {
122         return (e->directory ? "tree" : "blob");
123 }
124
125 static const char *entry_hex(struct tree_entry_list *e)
126 {
127         return sha1_to_hex(e->directory
128                            ? e->item.tree->object.sha1
129                            : e->item.blob->object.sha1);
130 }
131
132 /* forward declaration for mutually recursive routines */
133 static int show_entry(struct tree_entry_list *, int);
134
135 static int show_children(struct tree_entry_list *e, int level)
136 {
137         if (prepare_children(e))
138                 die("internal error: ls-tree show_children called with non tree");
139         e = e->item.tree->entries;
140         while (e) {
141                 show_entry(e, level);
142                 e = e->next;
143         }
144         return 0;
145 }
146
147 static int show_entry(struct tree_entry_list *e, int level)
148 {
149         int err = 0; 
150
151         if (e != &root_entry) {
152                 printf("%06o %s %s      ", e->mode, entry_type(e),
153                        entry_hex(e));
154                 show_entry_name(e);
155                 putchar(line_termination);
156         }
157
158         if (e->directory) {
159                 /* If this is a directory, we have the following cases:
160                  * (1) This is the top-level request (explicit path from the
161                  *     command line, or "root" if there is no command line).
162                  *  a. Without any flag.  We show direct children.  We do not 
163                  *     recurse into them.
164                  *  b. With -r.  We do recurse into children.
165                  *  c. With -d.  We do not recurse into children.
166                  * (2) We came here because our caller is either (1-a) or
167                  *     (1-b).
168                  *  a. Without any flag.  We do not show our children (which
169                  *     are grandchildren for the original request).
170                  *  b. With -r.  We continue to recurse into our children.
171                  *  c. With -d.  We should not have come here to begin with.
172                  */
173                 if (level == 0 && !(ls_options & LS_TREE_ONLY))
174                         /* case (1)-a and (1)-b */
175                         err = err | show_children(e, level+1);
176                 else if (level && ls_options & LS_RECURSIVE)
177                         /* case (2)-b */
178                         err = err | show_children(e, level+1);
179         }
180         return err;
181 }
182
183 static int list_one(const char *path, const char *path_end)
184 {
185         int err = 0;
186         struct tree_entry_list *e = find_entry(path, path_end);
187         if (!e) {
188                 /* traditionally ls-tree does not complain about
189                  * missing path.  We may change this later to match
190                  * what "/bin/ls -a" does, which is to complain.
191                  */
192                 return err;
193         }
194         err = err | show_entry(e, 0);
195         return err;
196 }
197
198 static int list(char **path)
199 {
200         int i;
201         int err = 0;
202         for (i = 0; path[i]; i++) {
203                 int len = strlen(path[i]);
204                 while (0 <= len && path[i][len] == '/')
205                         len--;
206                 err = err | list_one(path[i], path[i] + len);
207         }
208         return err;
209 }
210
211 static const char *ls_tree_usage =
212         "git-ls-tree [-d] [-r] [-z] <tree-ish> [path...]";
213
214 int main(int argc, char **argv)
215 {
216         static char *path0[] = { "", NULL };
217         char **path;
218         unsigned char sha1[20];
219
220         while (1 < argc && argv[1][0] == '-') {
221                 switch (argv[1][1]) {
222                 case 'z':
223                         line_termination = 0;
224                         break;
225                 case 'r':
226                         ls_options |= LS_RECURSIVE;
227                         break;
228                 case 'd':
229                         ls_options |= LS_TREE_ONLY;
230                         break;
231                 default:
232                         usage(ls_tree_usage);
233                 }
234                 argc--; argv++;
235         }
236
237         if (argc < 2)
238                 usage(ls_tree_usage);
239         if (get_sha1(argv[1], sha1) < 0)
240                 usage(ls_tree_usage);
241
242         path = (argc == 2) ? path0 : (argv + 2);
243         prepare_root(sha1);
244         if (list(path) < 0)
245                 die("list failed");
246         return 0;
247 }