glossary: expand and clarify some definitions, prune cross-references
[git] / dir.c
1 /*
2  * This handles recursive filename detection with exclude
3  * files, index knowledge etc..
4  *
5  * Copyright (C) Linus Torvalds, 2005-2006
6  *               Junio Hamano, 2005-2006
7  */
8 #include "cache.h"
9 #include "dir.h"
10
11 int common_prefix(const char **pathspec)
12 {
13         const char *path, *slash, *next;
14         int prefix;
15
16         if (!pathspec)
17                 return 0;
18
19         path = *pathspec;
20         slash = strrchr(path, '/');
21         if (!slash)
22                 return 0;
23
24         prefix = slash - path + 1;
25         while ((next = *++pathspec) != NULL) {
26                 int len = strlen(next);
27                 if (len >= prefix && !memcmp(path, next, prefix))
28                         continue;
29                 len = prefix - 1;
30                 for (;;) {
31                         if (!len)
32                                 return 0;
33                         if (next[--len] != '/')
34                                 continue;
35                         if (memcmp(path, next, len+1))
36                                 continue;
37                         prefix = len + 1;
38                         break;
39                 }
40         }
41         return prefix;
42 }
43
44 /*
45  * Does 'match' matches the given name?
46  * A match is found if
47  *
48  * (1) the 'match' string is leading directory of 'name', or
49  * (2) the 'match' string is a wildcard and matches 'name', or
50  * (3) the 'match' string is exactly the same as 'name'.
51  *
52  * and the return value tells which case it was.
53  *
54  * It returns 0 when there is no match.
55  */
56 static int match_one(const char *match, const char *name, int namelen)
57 {
58         int matchlen;
59
60         /* If the match was just the prefix, we matched */
61         matchlen = strlen(match);
62         if (!matchlen)
63                 return MATCHED_RECURSIVELY;
64
65         /*
66          * If we don't match the matchstring exactly,
67          * we need to match by fnmatch
68          */
69         if (strncmp(match, name, matchlen))
70                 return !fnmatch(match, name, 0) ? MATCHED_FNMATCH : 0;
71
72         if (!name[matchlen])
73                 return MATCHED_EXACTLY;
74         if (match[matchlen-1] == '/' || name[matchlen] == '/')
75                 return MATCHED_RECURSIVELY;
76         return 0;
77 }
78
79 /*
80  * Given a name and a list of pathspecs, see if the name matches
81  * any of the pathspecs.  The caller is also interested in seeing
82  * all pathspec matches some names it calls this function with
83  * (otherwise the user could have mistyped the unmatched pathspec),
84  * and a mark is left in seen[] array for pathspec element that
85  * actually matched anything.
86  */
87 int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen)
88 {
89         int retval;
90         const char *match;
91
92         name += prefix;
93         namelen -= prefix;
94
95         for (retval = 0; (match = *pathspec++) != NULL; seen++) {
96                 int how;
97                 if (retval && *seen == MATCHED_EXACTLY)
98                         continue;
99                 match += prefix;
100                 how = match_one(match, name, namelen);
101                 if (how) {
102                         if (retval < how)
103                                 retval = how;
104                         if (*seen < how)
105                                 *seen = how;
106                 }
107         }
108         return retval;
109 }
110
111 void add_exclude(const char *string, const char *base,
112                  int baselen, struct exclude_list *which)
113 {
114         struct exclude *x = xmalloc(sizeof (*x));
115
116         x->pattern = string;
117         x->base = base;
118         x->baselen = baselen;
119         if (which->nr == which->alloc) {
120                 which->alloc = alloc_nr(which->alloc);
121                 which->excludes = xrealloc(which->excludes,
122                                            which->alloc * sizeof(x));
123         }
124         which->excludes[which->nr++] = x;
125 }
126
127 static int add_excludes_from_file_1(const char *fname,
128                                     const char *base,
129                                     int baselen,
130                                     struct exclude_list *which)
131 {
132         struct stat st;
133         int fd, i;
134         size_t size;
135         char *buf, *entry;
136
137         fd = open(fname, O_RDONLY);
138         if (fd < 0 || fstat(fd, &st) < 0)
139                 goto err;
140         size = xsize_t(st.st_size);
141         if (size == 0) {
142                 close(fd);
143                 return 0;
144         }
145         buf = xmalloc(size+1);
146         if (read_in_full(fd, buf, size) != size)
147                 goto err;
148         close(fd);
149
150         buf[size++] = '\n';
151         entry = buf;
152         for (i = 0; i < size; i++) {
153                 if (buf[i] == '\n') {
154                         if (entry != buf + i && entry[0] != '#') {
155                                 buf[i - (i && buf[i-1] == '\r')] = 0;
156                                 add_exclude(entry, base, baselen, which);
157                         }
158                         entry = buf + i + 1;
159                 }
160         }
161         return 0;
162
163  err:
164         if (0 <= fd)
165                 close(fd);
166         return -1;
167 }
168
169 void add_excludes_from_file(struct dir_struct *dir, const char *fname)
170 {
171         if (add_excludes_from_file_1(fname, "", 0,
172                                      &dir->exclude_list[EXC_FILE]) < 0)
173                 die("cannot use %s as an exclude file", fname);
174 }
175
176 int push_exclude_per_directory(struct dir_struct *dir, const char *base, int baselen)
177 {
178         char exclude_file[PATH_MAX];
179         struct exclude_list *el = &dir->exclude_list[EXC_DIRS];
180         int current_nr = el->nr;
181
182         if (dir->exclude_per_dir) {
183                 memcpy(exclude_file, base, baselen);
184                 strcpy(exclude_file + baselen, dir->exclude_per_dir);
185                 add_excludes_from_file_1(exclude_file, base, baselen, el);
186         }
187         return current_nr;
188 }
189
190 void pop_exclude_per_directory(struct dir_struct *dir, int stk)
191 {
192         struct exclude_list *el = &dir->exclude_list[EXC_DIRS];
193
194         while (stk < el->nr)
195                 free(el->excludes[--el->nr]);
196 }
197
198 /* Scan the list and let the last match determines the fate.
199  * Return 1 for exclude, 0 for include and -1 for undecided.
200  */
201 static int excluded_1(const char *pathname,
202                       int pathlen,
203                       struct exclude_list *el)
204 {
205         int i;
206
207         if (el->nr) {
208                 for (i = el->nr - 1; 0 <= i; i--) {
209                         struct exclude *x = el->excludes[i];
210                         const char *exclude = x->pattern;
211                         int to_exclude = 1;
212
213                         if (*exclude == '!') {
214                                 to_exclude = 0;
215                                 exclude++;
216                         }
217
218                         if (!strchr(exclude, '/')) {
219                                 /* match basename */
220                                 const char *basename = strrchr(pathname, '/');
221                                 basename = (basename) ? basename+1 : pathname;
222                                 if (fnmatch(exclude, basename, 0) == 0)
223                                         return to_exclude;
224                         }
225                         else {
226                                 /* match with FNM_PATHNAME:
227                                  * exclude has base (baselen long) implicitly
228                                  * in front of it.
229                                  */
230                                 int baselen = x->baselen;
231                                 if (*exclude == '/')
232                                         exclude++;
233
234                                 if (pathlen < baselen ||
235                                     (baselen && pathname[baselen-1] != '/') ||
236                                     strncmp(pathname, x->base, baselen))
237                                     continue;
238
239                                 if (fnmatch(exclude, pathname+baselen,
240                                             FNM_PATHNAME) == 0)
241                                         return to_exclude;
242                         }
243                 }
244         }
245         return -1; /* undecided */
246 }
247
248 int excluded(struct dir_struct *dir, const char *pathname)
249 {
250         int pathlen = strlen(pathname);
251         int st;
252
253         for (st = EXC_CMDL; st <= EXC_FILE; st++) {
254                 switch (excluded_1(pathname, pathlen, &dir->exclude_list[st])) {
255                 case 0:
256                         return 0;
257                 case 1:
258                         return 1;
259                 }
260         }
261         return 0;
262 }
263
264 struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
265 {
266         struct dir_entry *ent;
267
268         if (cache_name_pos(pathname, len) >= 0)
269                 return NULL;
270
271         if (dir->nr == dir->alloc) {
272                 int alloc = alloc_nr(dir->alloc);
273                 dir->alloc = alloc;
274                 dir->entries = xrealloc(dir->entries, alloc*sizeof(ent));
275         }
276         ent = xmalloc(sizeof(*ent) + len + 1);
277         ent->ignored = ent->ignored_dir = 0;
278         ent->len = len;
279         memcpy(ent->name, pathname, len);
280         ent->name[len] = 0;
281         dir->entries[dir->nr++] = ent;
282         return ent;
283 }
284
285 static int dir_exists(const char *dirname, int len)
286 {
287         int pos = cache_name_pos(dirname, len);
288         if (pos >= 0)
289                 return 1;
290         pos = -pos-1;
291         if (pos >= active_nr) /* can't */
292                 return 0;
293         return !strncmp(active_cache[pos]->name, dirname, len);
294 }
295
296 /*
297  * Read a directory tree. We currently ignore anything but
298  * directories, regular files and symlinks. That's because git
299  * doesn't handle them at all yet. Maybe that will change some
300  * day.
301  *
302  * Also, we ignore the name ".git" (even if it is not a directory).
303  * That likely will not change.
304  */
305 static int read_directory_recursive(struct dir_struct *dir, const char *path, const char *base, int baselen, int check_only)
306 {
307         DIR *fdir = opendir(path);
308         int contents = 0;
309
310         if (fdir) {
311                 int exclude_stk;
312                 struct dirent *de;
313                 char fullname[PATH_MAX + 1];
314                 memcpy(fullname, base, baselen);
315
316                 exclude_stk = push_exclude_per_directory(dir, base, baselen);
317
318                 while ((de = readdir(fdir)) != NULL) {
319                         int len;
320
321                         if ((de->d_name[0] == '.') &&
322                             (de->d_name[1] == 0 ||
323                              !strcmp(de->d_name + 1, ".") ||
324                              !strcmp(de->d_name + 1, "git")))
325                                 continue;
326                         len = strlen(de->d_name);
327                         memcpy(fullname + baselen, de->d_name, len+1);
328                         if (excluded(dir, fullname) != dir->show_ignored) {
329                                 if (!dir->show_ignored || DTYPE(de) != DT_DIR) {
330                                         continue;
331                                 }
332                         }
333
334                         switch (DTYPE(de)) {
335                         struct stat st;
336                         default:
337                                 continue;
338                         case DT_UNKNOWN:
339                                 if (lstat(fullname, &st))
340                                         continue;
341                                 if (S_ISREG(st.st_mode) || S_ISLNK(st.st_mode))
342                                         break;
343                                 if (!S_ISDIR(st.st_mode))
344                                         continue;
345                                 /* fallthrough */
346                         case DT_DIR:
347                                 memcpy(fullname + baselen + len, "/", 2);
348                                 len++;
349                                 if (dir->show_other_directories &&
350                                     !dir_exists(fullname, baselen + len)) {
351                                         if (dir->hide_empty_directories &&
352                                             !read_directory_recursive(dir,
353                                                     fullname, fullname,
354                                                     baselen + len, 1))
355                                                 continue;
356                                         break;
357                                 }
358
359                                 contents += read_directory_recursive(dir,
360                                         fullname, fullname, baselen + len, 0);
361                                 continue;
362                         case DT_REG:
363                         case DT_LNK:
364                                 break;
365                         }
366                         contents++;
367                         if (check_only)
368                                 goto exit_early;
369                         else
370                                 dir_add_name(dir, fullname, baselen + len);
371                 }
372 exit_early:
373                 closedir(fdir);
374
375                 pop_exclude_per_directory(dir, exclude_stk);
376         }
377
378         return contents;
379 }
380
381 static int cmp_name(const void *p1, const void *p2)
382 {
383         const struct dir_entry *e1 = *(const struct dir_entry **)p1;
384         const struct dir_entry *e2 = *(const struct dir_entry **)p2;
385
386         return cache_name_compare(e1->name, e1->len,
387                                   e2->name, e2->len);
388 }
389
390 int read_directory(struct dir_struct *dir, const char *path, const char *base, int baselen)
391 {
392         /*
393          * Make sure to do the per-directory exclude for all the
394          * directories leading up to our base.
395          */
396         if (baselen) {
397                 if (dir->exclude_per_dir) {
398                         char *p, *pp = xmalloc(baselen+1);
399                         memcpy(pp, base, baselen+1);
400                         p = pp;
401                         while (1) {
402                                 char save = *p;
403                                 *p = 0;
404                                 push_exclude_per_directory(dir, pp, p-pp);
405                                 *p++ = save;
406                                 if (!save)
407                                         break;
408                                 p = strchr(p, '/');
409                                 if (p)
410                                         p++;
411                                 else
412                                         p = pp + baselen;
413                         }
414                         free(pp);
415                 }
416         }
417
418         read_directory_recursive(dir, path, base, baselen, 0);
419         qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
420         return dir->nr;
421 }
422
423 int
424 file_exists(const char *f)
425 {
426   struct stat sb;
427   return stat(f, &sb) == 0;
428 }