path.c: don't call the match function without value in trie_find()
[thirdparty/git.git] / path.c
1 /*
2  * Utilities for paths and pathnames
3  */
4 #include "cache.h"
5 #include "repository.h"
6 #include "strbuf.h"
7 #include "string-list.h"
8 #include "dir.h"
9 #include "worktree.h"
10 #include "submodule-config.h"
11 #include "path.h"
12 #include "packfile.h"
13 #include "object-store.h"
14
15 static int get_st_mode_bits(const char *path, int *mode)
16 {
17         struct stat st;
18         if (lstat(path, &st) < 0)
19                 return -1;
20         *mode = st.st_mode;
21         return 0;
22 }
23
24 static char bad_path[] = "/bad-path/";
25
26 static struct strbuf *get_pathname(void)
27 {
28         static struct strbuf pathname_array[4] = {
29                 STRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT
30         };
31         static int index;
32         struct strbuf *sb = &pathname_array[index];
33         index = (index + 1) % ARRAY_SIZE(pathname_array);
34         strbuf_reset(sb);
35         return sb;
36 }
37
38 static const char *cleanup_path(const char *path)
39 {
40         /* Clean it up */
41         if (skip_prefix(path, "./", &path)) {
42                 while (*path == '/')
43                         path++;
44         }
45         return path;
46 }
47
48 static void strbuf_cleanup_path(struct strbuf *sb)
49 {
50         const char *path = cleanup_path(sb->buf);
51         if (path > sb->buf)
52                 strbuf_remove(sb, 0, path - sb->buf);
53 }
54
55 char *mksnpath(char *buf, size_t n, const char *fmt, ...)
56 {
57         va_list args;
58         unsigned len;
59
60         va_start(args, fmt);
61         len = vsnprintf(buf, n, fmt, args);
62         va_end(args);
63         if (len >= n) {
64                 strlcpy(buf, bad_path, n);
65                 return buf;
66         }
67         return (char *)cleanup_path(buf);
68 }
69
70 static int dir_prefix(const char *buf, const char *dir)
71 {
72         int len = strlen(dir);
73         return !strncmp(buf, dir, len) &&
74                 (is_dir_sep(buf[len]) || buf[len] == '\0');
75 }
76
77 /* $buf =~ m|$dir/+$file| but without regex */
78 static int is_dir_file(const char *buf, const char *dir, const char *file)
79 {
80         int len = strlen(dir);
81         if (strncmp(buf, dir, len) || !is_dir_sep(buf[len]))
82                 return 0;
83         while (is_dir_sep(buf[len]))
84                 len++;
85         return !strcmp(buf + len, file);
86 }
87
88 static void replace_dir(struct strbuf *buf, int len, const char *newdir)
89 {
90         int newlen = strlen(newdir);
91         int need_sep = (buf->buf[len] && !is_dir_sep(buf->buf[len])) &&
92                 !is_dir_sep(newdir[newlen - 1]);
93         if (need_sep)
94                 len--;   /* keep one char, to be replaced with '/'  */
95         strbuf_splice(buf, 0, len, newdir, newlen);
96         if (need_sep)
97                 buf->buf[newlen] = '/';
98 }
99
100 struct common_dir {
101         /* Not considered garbage for report_linked_checkout_garbage */
102         unsigned ignore_garbage:1;
103         unsigned is_dir:1;
104         /* Belongs to the common dir, though it may contain paths that don't */
105         unsigned is_common:1;
106         const char *path;
107 };
108
109 static struct common_dir common_list[] = {
110         { 0, 1, 1, "branches" },
111         { 0, 1, 1, "common" },
112         { 0, 1, 1, "hooks" },
113         { 0, 1, 1, "info" },
114         { 0, 0, 0, "info/sparse-checkout" },
115         { 1, 1, 1, "logs" },
116         { 1, 0, 0, "logs/HEAD" },
117         { 0, 1, 0, "logs/refs/bisect" },
118         { 0, 1, 0, "logs/refs/rewritten" },
119         { 0, 1, 0, "logs/refs/worktree" },
120         { 0, 1, 1, "lost-found" },
121         { 0, 1, 1, "objects" },
122         { 0, 1, 1, "refs" },
123         { 0, 1, 0, "refs/bisect" },
124         { 0, 1, 0, "refs/rewritten" },
125         { 0, 1, 0, "refs/worktree" },
126         { 0, 1, 1, "remotes" },
127         { 0, 1, 1, "worktrees" },
128         { 0, 1, 1, "rr-cache" },
129         { 0, 1, 1, "svn" },
130         { 0, 0, 1, "config" },
131         { 1, 0, 1, "gc.pid" },
132         { 0, 0, 1, "packed-refs" },
133         { 0, 0, 1, "shallow" },
134         { 0, 0, 0, NULL }
135 };
136
137 /*
138  * A compressed trie.  A trie node consists of zero or more characters that
139  * are common to all elements with this prefix, optionally followed by some
140  * children.  If value is not NULL, the trie node is a terminal node.
141  *
142  * For example, consider the following set of strings:
143  * abc
144  * def
145  * definite
146  * definition
147  *
148  * The trie would look like:
149  * root: len = 0, children a and d non-NULL, value = NULL.
150  *    a: len = 2, contents = bc, value = (data for "abc")
151  *    d: len = 2, contents = ef, children i non-NULL, value = (data for "def")
152  *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
153  *           e: len = 0, children all NULL, value = (data for "definite")
154  *           i: len = 2, contents = on, children all NULL,
155  *              value = (data for "definition")
156  */
157 struct trie {
158         struct trie *children[256];
159         int len;
160         char *contents;
161         void *value;
162 };
163
164 static struct trie *make_trie_node(const char *key, void *value)
165 {
166         struct trie *new_node = xcalloc(1, sizeof(*new_node));
167         new_node->len = strlen(key);
168         if (new_node->len) {
169                 new_node->contents = xmalloc(new_node->len);
170                 memcpy(new_node->contents, key, new_node->len);
171         }
172         new_node->value = value;
173         return new_node;
174 }
175
176 /*
177  * Add a key/value pair to a trie.  The key is assumed to be \0-terminated.
178  * If there was an existing value for this key, return it.
179  */
180 static void *add_to_trie(struct trie *root, const char *key, void *value)
181 {
182         struct trie *child;
183         void *old;
184         int i;
185
186         if (!*key) {
187                 /* we have reached the end of the key */
188                 old = root->value;
189                 root->value = value;
190                 return old;
191         }
192
193         for (i = 0; i < root->len; i++) {
194                 if (root->contents[i] == key[i])
195                         continue;
196
197                 /*
198                  * Split this node: child will contain this node's
199                  * existing children.
200                  */
201                 child = xmalloc(sizeof(*child));
202                 memcpy(child->children, root->children, sizeof(root->children));
203
204                 child->len = root->len - i - 1;
205                 if (child->len) {
206                         child->contents = xstrndup(root->contents + i + 1,
207                                                    child->len);
208                 }
209                 child->value = root->value;
210                 root->value = NULL;
211                 root->len = i;
212
213                 memset(root->children, 0, sizeof(root->children));
214                 root->children[(unsigned char)root->contents[i]] = child;
215
216                 /* This is the newly-added child. */
217                 root->children[(unsigned char)key[i]] =
218                         make_trie_node(key + i + 1, value);
219                 return NULL;
220         }
221
222         /* We have matched the entire compressed section */
223         if (key[i]) {
224                 child = root->children[(unsigned char)key[root->len]];
225                 if (child) {
226                         return add_to_trie(child, key + root->len + 1, value);
227                 } else {
228                         child = make_trie_node(key + root->len + 1, value);
229                         root->children[(unsigned char)key[root->len]] = child;
230                         return NULL;
231                 }
232         }
233
234         old = root->value;
235         root->value = value;
236         return old;
237 }
238
239 typedef int (*match_fn)(const char *unmatched, void *value, void *baton);
240
241 /*
242  * Search a trie for some key.  Find the longest /-or-\0-terminated
243  * prefix of the key for which the trie contains a value.  If there is
244  * no such prefix, return -1.  Otherwise call fn with the unmatched
245  * portion of the key and the found value.  If fn returns 0 or
246  * positive, then return its return value.  If fn returns negative,
247  * then call fn with the next-longest /-terminated prefix of the key
248  * (i.e. a parent directory) for which the trie contains a value, and
249  * handle its return value the same way.  If there is no shorter
250  * /-terminated prefix with a value left, then return the negative
251  * return value of the most recent fn invocation.
252  *
253  * The key is partially normalized: consecutive slashes are skipped.
254  *
255  * For example, consider the trie containing only [logs,
256  * logs/refs/bisect], both with values, but not logs/refs.
257  *
258  * | key                | unmatched      | prefix to node   | return value |
259  * |--------------------|----------------|------------------|--------------|
260  * | a                  | not called     | n/a              | -1           |
261  * | logstore           | not called     | n/a              | -1           |
262  * | logs               | \0             | logs             | as per fn    |
263  * | logs/              | /              | logs             | as per fn    |
264  * | logs/refs          | /refs          | logs             | as per fn    |
265  * | logs/refs/         | /refs/         | logs             | as per fn    |
266  * | logs/refs/b        | /refs/b        | logs             | as per fn    |
267  * | logs/refs/bisected | /refs/bisected | logs             | as per fn    |
268  * | logs/refs/bisect   | \0             | logs/refs/bisect | as per fn    |
269  * | logs/refs/bisect/  | /              | logs/refs/bisect | as per fn    |
270  * | logs/refs/bisect/a | /a             | logs/refs/bisect | as per fn    |
271  * | (If fn in the previous line returns -1, then fn is called once more:) |
272  * | logs/refs/bisect/a | /refs/bisect/a | logs             | as per fn    |
273  * |--------------------|----------------|------------------|--------------|
274  */
275 static int trie_find(struct trie *root, const char *key, match_fn fn,
276                      void *baton)
277 {
278         int i;
279         int result;
280         struct trie *child;
281
282         if (!*key) {
283                 /* we have reached the end of the key */
284                 if (root->value && !root->len)
285                         return fn(key, root->value, baton);
286                 else
287                         return -1;
288         }
289
290         for (i = 0; i < root->len; i++) {
291                 /* Partial path normalization: skip consecutive slashes. */
292                 if (key[i] == '/' && key[i+1] == '/') {
293                         key++;
294                         continue;
295                 }
296                 if (root->contents[i] != key[i])
297                         return -1;
298         }
299
300         /* Matched the entire compressed section */
301         key += i;
302         if (!*key) {
303                 /* End of key */
304                 if (root->value)
305                         return fn(key, root->value, baton);
306                 else
307                         return -1;
308         }
309
310         /* Partial path normalization: skip consecutive slashes */
311         while (key[0] == '/' && key[1] == '/')
312                 key++;
313
314         child = root->children[(unsigned char)*key];
315         if (child)
316                 result = trie_find(child, key + 1, fn, baton);
317         else
318                 result = -1;
319
320         if (result >= 0 || (*key != '/' && *key != 0))
321                 return result;
322         if (root->value)
323                 return fn(key, root->value, baton);
324         else
325                 return -1;
326 }
327
328 static struct trie common_trie;
329 static int common_trie_done_setup;
330
331 static void init_common_trie(void)
332 {
333         struct common_dir *p;
334
335         if (common_trie_done_setup)
336                 return;
337
338         for (p = common_list; p->path; p++)
339                 add_to_trie(&common_trie, p->path, p);
340
341         common_trie_done_setup = 1;
342 }
343
344 /*
345  * Helper function for update_common_dir: returns 1 if the dir
346  * prefix is common.
347  */
348 static int check_common(const char *unmatched, void *value, void *baton)
349 {
350         struct common_dir *dir = value;
351
352         if (dir->is_dir && (unmatched[0] == 0 || unmatched[0] == '/'))
353                 return dir->is_common;
354
355         if (!dir->is_dir && unmatched[0] == 0)
356                 return dir->is_common;
357
358         return 0;
359 }
360
361 static void update_common_dir(struct strbuf *buf, int git_dir_len,
362                               const char *common_dir)
363 {
364         char *base = buf->buf + git_dir_len;
365         init_common_trie();
366         if (trie_find(&common_trie, base, check_common, NULL) > 0)
367                 replace_dir(buf, git_dir_len, common_dir);
368 }
369
370 void report_linked_checkout_garbage(void)
371 {
372         struct strbuf sb = STRBUF_INIT;
373         const struct common_dir *p;
374         int len;
375
376         if (!the_repository->different_commondir)
377                 return;
378         strbuf_addf(&sb, "%s/", get_git_dir());
379         len = sb.len;
380         for (p = common_list; p->path; p++) {
381                 const char *path = p->path;
382                 if (p->ignore_garbage)
383                         continue;
384                 strbuf_setlen(&sb, len);
385                 strbuf_addstr(&sb, path);
386                 if (file_exists(sb.buf))
387                         report_garbage(PACKDIR_FILE_GARBAGE, sb.buf);
388         }
389         strbuf_release(&sb);
390 }
391
392 static void adjust_git_path(const struct repository *repo,
393                             struct strbuf *buf, int git_dir_len)
394 {
395         const char *base = buf->buf + git_dir_len;
396         if (is_dir_file(base, "info", "grafts"))
397                 strbuf_splice(buf, 0, buf->len,
398                               repo->graft_file, strlen(repo->graft_file));
399         else if (!strcmp(base, "index"))
400                 strbuf_splice(buf, 0, buf->len,
401                               repo->index_file, strlen(repo->index_file));
402         else if (dir_prefix(base, "objects"))
403                 replace_dir(buf, git_dir_len + 7, repo->objects->odb->path);
404         else if (git_hooks_path && dir_prefix(base, "hooks"))
405                 replace_dir(buf, git_dir_len + 5, git_hooks_path);
406         else if (repo->different_commondir)
407                 update_common_dir(buf, git_dir_len, repo->commondir);
408 }
409
410 static void strbuf_worktree_gitdir(struct strbuf *buf,
411                                    const struct repository *repo,
412                                    const struct worktree *wt)
413 {
414         if (!wt)
415                 strbuf_addstr(buf, repo->gitdir);
416         else if (!wt->id)
417                 strbuf_addstr(buf, repo->commondir);
418         else
419                 strbuf_git_common_path(buf, repo, "worktrees/%s", wt->id);
420 }
421
422 static void do_git_path(const struct repository *repo,
423                         const struct worktree *wt, struct strbuf *buf,
424                         const char *fmt, va_list args)
425 {
426         int gitdir_len;
427         strbuf_worktree_gitdir(buf, repo, wt);
428         if (buf->len && !is_dir_sep(buf->buf[buf->len - 1]))
429                 strbuf_addch(buf, '/');
430         gitdir_len = buf->len;
431         strbuf_vaddf(buf, fmt, args);
432         if (!wt)
433                 adjust_git_path(repo, buf, gitdir_len);
434         strbuf_cleanup_path(buf);
435 }
436
437 char *repo_git_path(const struct repository *repo,
438                     const char *fmt, ...)
439 {
440         struct strbuf path = STRBUF_INIT;
441         va_list args;
442         va_start(args, fmt);
443         do_git_path(repo, NULL, &path, fmt, args);
444         va_end(args);
445         return strbuf_detach(&path, NULL);
446 }
447
448 void strbuf_repo_git_path(struct strbuf *sb,
449                           const struct repository *repo,
450                           const char *fmt, ...)
451 {
452         va_list args;
453         va_start(args, fmt);
454         do_git_path(repo, NULL, sb, fmt, args);
455         va_end(args);
456 }
457
458 char *git_path_buf(struct strbuf *buf, const char *fmt, ...)
459 {
460         va_list args;
461         strbuf_reset(buf);
462         va_start(args, fmt);
463         do_git_path(the_repository, NULL, buf, fmt, args);
464         va_end(args);
465         return buf->buf;
466 }
467
468 void strbuf_git_path(struct strbuf *sb, const char *fmt, ...)
469 {
470         va_list args;
471         va_start(args, fmt);
472         do_git_path(the_repository, NULL, sb, fmt, args);
473         va_end(args);
474 }
475
476 const char *git_path(const char *fmt, ...)
477 {
478         struct strbuf *pathname = get_pathname();
479         va_list args;
480         va_start(args, fmt);
481         do_git_path(the_repository, NULL, pathname, fmt, args);
482         va_end(args);
483         return pathname->buf;
484 }
485
486 char *git_pathdup(const char *fmt, ...)
487 {
488         struct strbuf path = STRBUF_INIT;
489         va_list args;
490         va_start(args, fmt);
491         do_git_path(the_repository, NULL, &path, fmt, args);
492         va_end(args);
493         return strbuf_detach(&path, NULL);
494 }
495
496 char *mkpathdup(const char *fmt, ...)
497 {
498         struct strbuf sb = STRBUF_INIT;
499         va_list args;
500         va_start(args, fmt);
501         strbuf_vaddf(&sb, fmt, args);
502         va_end(args);
503         strbuf_cleanup_path(&sb);
504         return strbuf_detach(&sb, NULL);
505 }
506
507 const char *mkpath(const char *fmt, ...)
508 {
509         va_list args;
510         struct strbuf *pathname = get_pathname();
511         va_start(args, fmt);
512         strbuf_vaddf(pathname, fmt, args);
513         va_end(args);
514         return cleanup_path(pathname->buf);
515 }
516
517 const char *worktree_git_path(const struct worktree *wt, const char *fmt, ...)
518 {
519         struct strbuf *pathname = get_pathname();
520         va_list args;
521         va_start(args, fmt);
522         do_git_path(the_repository, wt, pathname, fmt, args);
523         va_end(args);
524         return pathname->buf;
525 }
526
527 static void do_worktree_path(const struct repository *repo,
528                              struct strbuf *buf,
529                              const char *fmt, va_list args)
530 {
531         strbuf_addstr(buf, repo->worktree);
532         if(buf->len && !is_dir_sep(buf->buf[buf->len - 1]))
533                 strbuf_addch(buf, '/');
534
535         strbuf_vaddf(buf, fmt, args);
536         strbuf_cleanup_path(buf);
537 }
538
539 char *repo_worktree_path(const struct repository *repo, const char *fmt, ...)
540 {
541         struct strbuf path = STRBUF_INIT;
542         va_list args;
543
544         if (!repo->worktree)
545                 return NULL;
546
547         va_start(args, fmt);
548         do_worktree_path(repo, &path, fmt, args);
549         va_end(args);
550
551         return strbuf_detach(&path, NULL);
552 }
553
554 void strbuf_repo_worktree_path(struct strbuf *sb,
555                                const struct repository *repo,
556                                const char *fmt, ...)
557 {
558         va_list args;
559
560         if (!repo->worktree)
561                 return;
562
563         va_start(args, fmt);
564         do_worktree_path(repo, sb, fmt, args);
565         va_end(args);
566 }
567
568 /* Returns 0 on success, negative on failure. */
569 static int do_submodule_path(struct strbuf *buf, const char *path,
570                              const char *fmt, va_list args)
571 {
572         struct strbuf git_submodule_common_dir = STRBUF_INIT;
573         struct strbuf git_submodule_dir = STRBUF_INIT;
574         int ret;
575
576         ret = submodule_to_gitdir(&git_submodule_dir, path);
577         if (ret)
578                 goto cleanup;
579
580         strbuf_complete(&git_submodule_dir, '/');
581         strbuf_addbuf(buf, &git_submodule_dir);
582         strbuf_vaddf(buf, fmt, args);
583
584         if (get_common_dir_noenv(&git_submodule_common_dir, git_submodule_dir.buf))
585                 update_common_dir(buf, git_submodule_dir.len, git_submodule_common_dir.buf);
586
587         strbuf_cleanup_path(buf);
588
589 cleanup:
590         strbuf_release(&git_submodule_dir);
591         strbuf_release(&git_submodule_common_dir);
592         return ret;
593 }
594
595 char *git_pathdup_submodule(const char *path, const char *fmt, ...)
596 {
597         int err;
598         va_list args;
599         struct strbuf buf = STRBUF_INIT;
600         va_start(args, fmt);
601         err = do_submodule_path(&buf, path, fmt, args);
602         va_end(args);
603         if (err) {
604                 strbuf_release(&buf);
605                 return NULL;
606         }
607         return strbuf_detach(&buf, NULL);
608 }
609
610 int strbuf_git_path_submodule(struct strbuf *buf, const char *path,
611                               const char *fmt, ...)
612 {
613         int err;
614         va_list args;
615         va_start(args, fmt);
616         err = do_submodule_path(buf, path, fmt, args);
617         va_end(args);
618
619         return err;
620 }
621
622 static void do_git_common_path(const struct repository *repo,
623                                struct strbuf *buf,
624                                const char *fmt,
625                                va_list args)
626 {
627         strbuf_addstr(buf, repo->commondir);
628         if (buf->len && !is_dir_sep(buf->buf[buf->len - 1]))
629                 strbuf_addch(buf, '/');
630         strbuf_vaddf(buf, fmt, args);
631         strbuf_cleanup_path(buf);
632 }
633
634 const char *git_common_path(const char *fmt, ...)
635 {
636         struct strbuf *pathname = get_pathname();
637         va_list args;
638         va_start(args, fmt);
639         do_git_common_path(the_repository, pathname, fmt, args);
640         va_end(args);
641         return pathname->buf;
642 }
643
644 void strbuf_git_common_path(struct strbuf *sb,
645                             const struct repository *repo,
646                             const char *fmt, ...)
647 {
648         va_list args;
649         va_start(args, fmt);
650         do_git_common_path(repo, sb, fmt, args);
651         va_end(args);
652 }
653
654 int validate_headref(const char *path)
655 {
656         struct stat st;
657         char buffer[256];
658         const char *refname;
659         struct object_id oid;
660         int fd;
661         ssize_t len;
662
663         if (lstat(path, &st) < 0)
664                 return -1;
665
666         /* Make sure it is a "refs/.." symlink */
667         if (S_ISLNK(st.st_mode)) {
668                 len = readlink(path, buffer, sizeof(buffer)-1);
669                 if (len >= 5 && !memcmp("refs/", buffer, 5))
670                         return 0;
671                 return -1;
672         }
673
674         /*
675          * Anything else, just open it and try to see if it is a symbolic ref.
676          */
677         fd = open(path, O_RDONLY);
678         if (fd < 0)
679                 return -1;
680         len = read_in_full(fd, buffer, sizeof(buffer)-1);
681         close(fd);
682
683         if (len < 0)
684                 return -1;
685         buffer[len] = '\0';
686
687         /*
688          * Is it a symbolic ref?
689          */
690         if (skip_prefix(buffer, "ref:", &refname)) {
691                 while (isspace(*refname))
692                         refname++;
693                 if (starts_with(refname, "refs/"))
694                         return 0;
695         }
696
697         /*
698          * Is this a detached HEAD?
699          */
700         if (!get_oid_hex(buffer, &oid))
701                 return 0;
702
703         return -1;
704 }
705
706 static struct passwd *getpw_str(const char *username, size_t len)
707 {
708         struct passwd *pw;
709         char *username_z = xmemdupz(username, len);
710         pw = getpwnam(username_z);
711         free(username_z);
712         return pw;
713 }
714
715 /*
716  * Return a string with ~ and ~user expanded via getpw*.  If buf != NULL,
717  * then it is a newly allocated string. Returns NULL on getpw failure or
718  * if path is NULL.
719  *
720  * If real_home is true, real_path($HOME) is used in the expansion.
721  */
722 char *expand_user_path(const char *path, int real_home)
723 {
724         struct strbuf user_path = STRBUF_INIT;
725         const char *to_copy = path;
726
727         if (path == NULL)
728                 goto return_null;
729         if (path[0] == '~') {
730                 const char *first_slash = strchrnul(path, '/');
731                 const char *username = path + 1;
732                 size_t username_len = first_slash - username;
733                 if (username_len == 0) {
734                         const char *home = getenv("HOME");
735                         if (!home)
736                                 goto return_null;
737                         if (real_home)
738                                 strbuf_add_real_path(&user_path, home);
739                         else
740                                 strbuf_addstr(&user_path, home);
741 #ifdef GIT_WINDOWS_NATIVE
742                         convert_slashes(user_path.buf);
743 #endif
744                 } else {
745                         struct passwd *pw = getpw_str(username, username_len);
746                         if (!pw)
747                                 goto return_null;
748                         strbuf_addstr(&user_path, pw->pw_dir);
749                 }
750                 to_copy = first_slash;
751         }
752         strbuf_addstr(&user_path, to_copy);
753         return strbuf_detach(&user_path, NULL);
754 return_null:
755         strbuf_release(&user_path);
756         return NULL;
757 }
758
759 /*
760  * First, one directory to try is determined by the following algorithm.
761  *
762  * (0) If "strict" is given, the path is used as given and no DWIM is
763  *     done. Otherwise:
764  * (1) "~/path" to mean path under the running user's home directory;
765  * (2) "~user/path" to mean path under named user's home directory;
766  * (3) "relative/path" to mean cwd relative directory; or
767  * (4) "/absolute/path" to mean absolute directory.
768  *
769  * Unless "strict" is given, we check "%s/.git", "%s", "%s.git/.git", "%s.git"
770  * in this order. We select the first one that is a valid git repository, and
771  * chdir() to it. If none match, or we fail to chdir, we return NULL.
772  *
773  * If all goes well, we return the directory we used to chdir() (but
774  * before ~user is expanded), avoiding getcwd() resolving symbolic
775  * links.  User relative paths are also returned as they are given,
776  * except DWIM suffixing.
777  */
778 const char *enter_repo(const char *path, int strict)
779 {
780         static struct strbuf validated_path = STRBUF_INIT;
781         static struct strbuf used_path = STRBUF_INIT;
782
783         if (!path)
784                 return NULL;
785
786         if (!strict) {
787                 static const char *suffix[] = {
788                         "/.git", "", ".git/.git", ".git", NULL,
789                 };
790                 const char *gitfile;
791                 int len = strlen(path);
792                 int i;
793                 while ((1 < len) && (path[len-1] == '/'))
794                         len--;
795
796                 /*
797                  * We can handle arbitrary-sized buffers, but this remains as a
798                  * sanity check on untrusted input.
799                  */
800                 if (PATH_MAX <= len)
801                         return NULL;
802
803                 strbuf_reset(&used_path);
804                 strbuf_reset(&validated_path);
805                 strbuf_add(&used_path, path, len);
806                 strbuf_add(&validated_path, path, len);
807
808                 if (used_path.buf[0] == '~') {
809                         char *newpath = expand_user_path(used_path.buf, 0);
810                         if (!newpath)
811                                 return NULL;
812                         strbuf_attach(&used_path, newpath, strlen(newpath),
813                                       strlen(newpath));
814                 }
815                 for (i = 0; suffix[i]; i++) {
816                         struct stat st;
817                         size_t baselen = used_path.len;
818                         strbuf_addstr(&used_path, suffix[i]);
819                         if (!stat(used_path.buf, &st) &&
820                             (S_ISREG(st.st_mode) ||
821                             (S_ISDIR(st.st_mode) && is_git_directory(used_path.buf)))) {
822                                 strbuf_addstr(&validated_path, suffix[i]);
823                                 break;
824                         }
825                         strbuf_setlen(&used_path, baselen);
826                 }
827                 if (!suffix[i])
828                         return NULL;
829                 gitfile = read_gitfile(used_path.buf);
830                 if (gitfile) {
831                         strbuf_reset(&used_path);
832                         strbuf_addstr(&used_path, gitfile);
833                 }
834                 if (chdir(used_path.buf))
835                         return NULL;
836                 path = validated_path.buf;
837         }
838         else {
839                 const char *gitfile = read_gitfile(path);
840                 if (gitfile)
841                         path = gitfile;
842                 if (chdir(path))
843                         return NULL;
844         }
845
846         if (is_git_directory(".")) {
847                 set_git_dir(".");
848                 check_repository_format();
849                 return path;
850         }
851
852         return NULL;
853 }
854
855 static int calc_shared_perm(int mode)
856 {
857         int tweak;
858
859         if (get_shared_repository() < 0)
860                 tweak = -get_shared_repository();
861         else
862                 tweak = get_shared_repository();
863
864         if (!(mode & S_IWUSR))
865                 tweak &= ~0222;
866         if (mode & S_IXUSR)
867                 /* Copy read bits to execute bits */
868                 tweak |= (tweak & 0444) >> 2;
869         if (get_shared_repository() < 0)
870                 mode = (mode & ~0777) | tweak;
871         else
872                 mode |= tweak;
873
874         return mode;
875 }
876
877
878 int adjust_shared_perm(const char *path)
879 {
880         int old_mode, new_mode;
881
882         if (!get_shared_repository())
883                 return 0;
884         if (get_st_mode_bits(path, &old_mode) < 0)
885                 return -1;
886
887         new_mode = calc_shared_perm(old_mode);
888         if (S_ISDIR(old_mode)) {
889                 /* Copy read bits to execute bits */
890                 new_mode |= (new_mode & 0444) >> 2;
891                 new_mode |= FORCE_DIR_SET_GID;
892         }
893
894         if (((old_mode ^ new_mode) & ~S_IFMT) &&
895                         chmod(path, (new_mode & ~S_IFMT)) < 0)
896                 return -2;
897         return 0;
898 }
899
900 void safe_create_dir(const char *dir, int share)
901 {
902         if (mkdir(dir, 0777) < 0) {
903                 if (errno != EEXIST) {
904                         perror(dir);
905                         exit(1);
906                 }
907         }
908         else if (share && adjust_shared_perm(dir))
909                 die(_("Could not make %s writable by group"), dir);
910 }
911
912 static int have_same_root(const char *path1, const char *path2)
913 {
914         int is_abs1, is_abs2;
915
916         is_abs1 = is_absolute_path(path1);
917         is_abs2 = is_absolute_path(path2);
918         return (is_abs1 && is_abs2 && tolower(path1[0]) == tolower(path2[0])) ||
919                (!is_abs1 && !is_abs2);
920 }
921
922 /*
923  * Give path as relative to prefix.
924  *
925  * The strbuf may or may not be used, so do not assume it contains the
926  * returned path.
927  */
928 const char *relative_path(const char *in, const char *prefix,
929                           struct strbuf *sb)
930 {
931         int in_len = in ? strlen(in) : 0;
932         int prefix_len = prefix ? strlen(prefix) : 0;
933         int in_off = 0;
934         int prefix_off = 0;
935         int i = 0, j = 0;
936
937         if (!in_len)
938                 return "./";
939         else if (!prefix_len)
940                 return in;
941
942         if (have_same_root(in, prefix))
943                 /* bypass dos_drive, for "c:" is identical to "C:" */
944                 i = j = has_dos_drive_prefix(in);
945         else {
946                 return in;
947         }
948
949         while (i < prefix_len && j < in_len && prefix[i] == in[j]) {
950                 if (is_dir_sep(prefix[i])) {
951                         while (is_dir_sep(prefix[i]))
952                                 i++;
953                         while (is_dir_sep(in[j]))
954                                 j++;
955                         prefix_off = i;
956                         in_off = j;
957                 } else {
958                         i++;
959                         j++;
960                 }
961         }
962
963         if (
964             /* "prefix" seems like prefix of "in" */
965             i >= prefix_len &&
966             /*
967              * but "/foo" is not a prefix of "/foobar"
968              * (i.e. prefix not end with '/')
969              */
970             prefix_off < prefix_len) {
971                 if (j >= in_len) {
972                         /* in="/a/b", prefix="/a/b" */
973                         in_off = in_len;
974                 } else if (is_dir_sep(in[j])) {
975                         /* in="/a/b/c", prefix="/a/b" */
976                         while (is_dir_sep(in[j]))
977                                 j++;
978                         in_off = j;
979                 } else {
980                         /* in="/a/bbb/c", prefix="/a/b" */
981                         i = prefix_off;
982                 }
983         } else if (
984                    /* "in" is short than "prefix" */
985                    j >= in_len &&
986                    /* "in" not end with '/' */
987                    in_off < in_len) {
988                 if (is_dir_sep(prefix[i])) {
989                         /* in="/a/b", prefix="/a/b/c/" */
990                         while (is_dir_sep(prefix[i]))
991                                 i++;
992                         in_off = in_len;
993                 }
994         }
995         in += in_off;
996         in_len -= in_off;
997
998         if (i >= prefix_len) {
999                 if (!in_len)
1000                         return "./";
1001                 else
1002                         return in;
1003         }
1004
1005         strbuf_reset(sb);
1006         strbuf_grow(sb, in_len);
1007
1008         while (i < prefix_len) {
1009                 if (is_dir_sep(prefix[i])) {
1010                         strbuf_addstr(sb, "../");
1011                         while (is_dir_sep(prefix[i]))
1012                                 i++;
1013                         continue;
1014                 }
1015                 i++;
1016         }
1017         if (!is_dir_sep(prefix[prefix_len - 1]))
1018                 strbuf_addstr(sb, "../");
1019
1020         strbuf_addstr(sb, in);
1021
1022         return sb->buf;
1023 }
1024
1025 /*
1026  * A simpler implementation of relative_path
1027  *
1028  * Get relative path by removing "prefix" from "in". This function
1029  * first appears in v1.5.6-1-g044bbbc, and makes git_dir shorter
1030  * to increase performance when traversing the path to work_tree.
1031  */
1032 const char *remove_leading_path(const char *in, const char *prefix)
1033 {
1034         static struct strbuf buf = STRBUF_INIT;
1035         int i = 0, j = 0;
1036
1037         if (!prefix || !prefix[0])
1038                 return in;
1039         while (prefix[i]) {
1040                 if (is_dir_sep(prefix[i])) {
1041                         if (!is_dir_sep(in[j]))
1042                                 return in;
1043                         while (is_dir_sep(prefix[i]))
1044                                 i++;
1045                         while (is_dir_sep(in[j]))
1046                                 j++;
1047                         continue;
1048                 } else if (in[j] != prefix[i]) {
1049                         return in;
1050                 }
1051                 i++;
1052                 j++;
1053         }
1054         if (
1055             /* "/foo" is a prefix of "/foo" */
1056             in[j] &&
1057             /* "/foo" is not a prefix of "/foobar" */
1058             !is_dir_sep(prefix[i-1]) && !is_dir_sep(in[j])
1059            )
1060                 return in;
1061         while (is_dir_sep(in[j]))
1062                 j++;
1063
1064         strbuf_reset(&buf);
1065         if (!in[j])
1066                 strbuf_addstr(&buf, ".");
1067         else
1068                 strbuf_addstr(&buf, in + j);
1069         return buf.buf;
1070 }
1071
1072 /*
1073  * It is okay if dst == src, but they should not overlap otherwise.
1074  *
1075  * Performs the following normalizations on src, storing the result in dst:
1076  * - Ensures that components are separated by '/' (Windows only)
1077  * - Squashes sequences of '/' except "//server/share" on Windows
1078  * - Removes "." components.
1079  * - Removes ".." components, and the components the precede them.
1080  * Returns failure (non-zero) if a ".." component appears as first path
1081  * component anytime during the normalization. Otherwise, returns success (0).
1082  *
1083  * Note that this function is purely textual.  It does not follow symlinks,
1084  * verify the existence of the path, or make any system calls.
1085  *
1086  * prefix_len != NULL is for a specific case of prefix_pathspec():
1087  * assume that src == dst and src[0..prefix_len-1] is already
1088  * normalized, any time "../" eats up to the prefix_len part,
1089  * prefix_len is reduced. In the end prefix_len is the remaining
1090  * prefix that has not been overridden by user pathspec.
1091  *
1092  * NEEDSWORK: This function doesn't perform normalization w.r.t. trailing '/'.
1093  * For everything but the root folder itself, the normalized path should not
1094  * end with a '/', then the callers need to be fixed up accordingly.
1095  *
1096  */
1097 int normalize_path_copy_len(char *dst, const char *src, int *prefix_len)
1098 {
1099         char *dst0;
1100         const char *end;
1101
1102         /*
1103          * Copy initial part of absolute path: "/", "C:/", "//server/share/".
1104          */
1105         end = src + offset_1st_component(src);
1106         while (src < end) {
1107                 char c = *src++;
1108                 if (is_dir_sep(c))
1109                         c = '/';
1110                 *dst++ = c;
1111         }
1112         dst0 = dst;
1113
1114         while (is_dir_sep(*src))
1115                 src++;
1116
1117         for (;;) {
1118                 char c = *src;
1119
1120                 /*
1121                  * A path component that begins with . could be
1122                  * special:
1123                  * (1) "." and ends   -- ignore and terminate.
1124                  * (2) "./"           -- ignore them, eat slash and continue.
1125                  * (3) ".." and ends  -- strip one and terminate.
1126                  * (4) "../"          -- strip one, eat slash and continue.
1127                  */
1128                 if (c == '.') {
1129                         if (!src[1]) {
1130                                 /* (1) */
1131                                 src++;
1132                         } else if (is_dir_sep(src[1])) {
1133                                 /* (2) */
1134                                 src += 2;
1135                                 while (is_dir_sep(*src))
1136                                         src++;
1137                                 continue;
1138                         } else if (src[1] == '.') {
1139                                 if (!src[2]) {
1140                                         /* (3) */
1141                                         src += 2;
1142                                         goto up_one;
1143                                 } else if (is_dir_sep(src[2])) {
1144                                         /* (4) */
1145                                         src += 3;
1146                                         while (is_dir_sep(*src))
1147                                                 src++;
1148                                         goto up_one;
1149                                 }
1150                         }
1151                 }
1152
1153                 /* copy up to the next '/', and eat all '/' */
1154                 while ((c = *src++) != '\0' && !is_dir_sep(c))
1155                         *dst++ = c;
1156                 if (is_dir_sep(c)) {
1157                         *dst++ = '/';
1158                         while (is_dir_sep(c))
1159                                 c = *src++;
1160                         src--;
1161                 } else if (!c)
1162                         break;
1163                 continue;
1164
1165         up_one:
1166                 /*
1167                  * dst0..dst is prefix portion, and dst[-1] is '/';
1168                  * go up one level.
1169                  */
1170                 dst--;  /* go to trailing '/' */
1171                 if (dst <= dst0)
1172                         return -1;
1173                 /* Windows: dst[-1] cannot be backslash anymore */
1174                 while (dst0 < dst && dst[-1] != '/')
1175                         dst--;
1176                 if (prefix_len && *prefix_len > dst - dst0)
1177                         *prefix_len = dst - dst0;
1178         }
1179         *dst = '\0';
1180         return 0;
1181 }
1182
1183 int normalize_path_copy(char *dst, const char *src)
1184 {
1185         return normalize_path_copy_len(dst, src, NULL);
1186 }
1187
1188 /*
1189  * path = Canonical absolute path
1190  * prefixes = string_list containing normalized, absolute paths without
1191  * trailing slashes (except for the root directory, which is denoted by "/").
1192  *
1193  * Determines, for each path in prefixes, whether the "prefix"
1194  * is an ancestor directory of path.  Returns the length of the longest
1195  * ancestor directory, excluding any trailing slashes, or -1 if no prefix
1196  * is an ancestor.  (Note that this means 0 is returned if prefixes is
1197  * ["/"].) "/foo" is not considered an ancestor of "/foobar".  Directories
1198  * are not considered to be their own ancestors.  path must be in a
1199  * canonical form: empty components, or "." or ".." components are not
1200  * allowed.
1201  */
1202 int longest_ancestor_length(const char *path, struct string_list *prefixes)
1203 {
1204         int i, max_len = -1;
1205
1206         if (!strcmp(path, "/"))
1207                 return -1;
1208
1209         for (i = 0; i < prefixes->nr; i++) {
1210                 const char *ceil = prefixes->items[i].string;
1211                 int len = strlen(ceil);
1212
1213                 if (len == 1 && ceil[0] == '/')
1214                         len = 0; /* root matches anything, with length 0 */
1215                 else if (!strncmp(path, ceil, len) && path[len] == '/')
1216                         ; /* match of length len */
1217                 else
1218                         continue; /* no match */
1219
1220                 if (len > max_len)
1221                         max_len = len;
1222         }
1223
1224         return max_len;
1225 }
1226
1227 /* strip arbitrary amount of directory separators at end of path */
1228 static inline int chomp_trailing_dir_sep(const char *path, int len)
1229 {
1230         while (len && is_dir_sep(path[len - 1]))
1231                 len--;
1232         return len;
1233 }
1234
1235 /*
1236  * If path ends with suffix (complete path components), returns the
1237  * part before suffix (sans trailing directory separators).
1238  * Otherwise returns NULL.
1239  */
1240 char *strip_path_suffix(const char *path, const char *suffix)
1241 {
1242         int path_len = strlen(path), suffix_len = strlen(suffix);
1243
1244         while (suffix_len) {
1245                 if (!path_len)
1246                         return NULL;
1247
1248                 if (is_dir_sep(path[path_len - 1])) {
1249                         if (!is_dir_sep(suffix[suffix_len - 1]))
1250                                 return NULL;
1251                         path_len = chomp_trailing_dir_sep(path, path_len);
1252                         suffix_len = chomp_trailing_dir_sep(suffix, suffix_len);
1253                 }
1254                 else if (path[--path_len] != suffix[--suffix_len])
1255                         return NULL;
1256         }
1257
1258         if (path_len && !is_dir_sep(path[path_len - 1]))
1259                 return NULL;
1260         return xstrndup(path, chomp_trailing_dir_sep(path, path_len));
1261 }
1262
1263 int daemon_avoid_alias(const char *p)
1264 {
1265         int sl, ndot;
1266
1267         /*
1268          * This resurrects the belts and suspenders paranoia check by HPA
1269          * done in <435560F7.4080006@zytor.com> thread, now enter_repo()
1270          * does not do getcwd() based path canonicalization.
1271          *
1272          * sl becomes true immediately after seeing '/' and continues to
1273          * be true as long as dots continue after that without intervening
1274          * non-dot character.
1275          */
1276         if (!p || (*p != '/' && *p != '~'))
1277                 return -1;
1278         sl = 1; ndot = 0;
1279         p++;
1280
1281         while (1) {
1282                 char ch = *p++;
1283                 if (sl) {
1284                         if (ch == '.')
1285                                 ndot++;
1286                         else if (ch == '/') {
1287                                 if (ndot < 3)
1288                                         /* reject //, /./ and /../ */
1289                                         return -1;
1290                                 ndot = 0;
1291                         }
1292                         else if (ch == 0) {
1293                                 if (0 < ndot && ndot < 3)
1294                                         /* reject /.$ and /..$ */
1295                                         return -1;
1296                                 return 0;
1297                         }
1298                         else
1299                                 sl = ndot = 0;
1300                 }
1301                 else if (ch == 0)
1302                         return 0;
1303                 else if (ch == '/') {
1304                         sl = 1;
1305                         ndot = 0;
1306                 }
1307         }
1308 }
1309
1310 static int only_spaces_and_periods(const char *path, size_t len, size_t skip)
1311 {
1312         if (len < skip)
1313                 return 0;
1314         len -= skip;
1315         path += skip;
1316         while (len-- > 0) {
1317                 char c = *(path++);
1318                 if (c != ' ' && c != '.')
1319                         return 0;
1320         }
1321         return 1;
1322 }
1323
1324 int is_ntfs_dotgit(const char *name)
1325 {
1326         size_t len;
1327
1328         for (len = 0; ; len++)
1329                 if (!name[len] || name[len] == '\\' || is_dir_sep(name[len])) {
1330                         if (only_spaces_and_periods(name, len, 4) &&
1331                                         !strncasecmp(name, ".git", 4))
1332                                 return 1;
1333                         if (only_spaces_and_periods(name, len, 5) &&
1334                                         !strncasecmp(name, "git~1", 5))
1335                                 return 1;
1336                         if (name[len] != '\\')
1337                                 return 0;
1338                         name += len + 1;
1339                         len = -1;
1340                 }
1341 }
1342
1343 static int is_ntfs_dot_generic(const char *name,
1344                                const char *dotgit_name,
1345                                size_t len,
1346                                const char *dotgit_ntfs_shortname_prefix)
1347 {
1348         int saw_tilde;
1349         size_t i;
1350
1351         if ((name[0] == '.' && !strncasecmp(name + 1, dotgit_name, len))) {
1352                 i = len + 1;
1353 only_spaces_and_periods:
1354                 for (;;) {
1355                         char c = name[i++];
1356                         if (!c)
1357                                 return 1;
1358                         if (c != ' ' && c != '.')
1359                                 return 0;
1360                 }
1361         }
1362
1363         /*
1364          * Is it a regular NTFS short name, i.e. shortened to 6 characters,
1365          * followed by ~1, ... ~4?
1366          */
1367         if (!strncasecmp(name, dotgit_name, 6) && name[6] == '~' &&
1368             name[7] >= '1' && name[7] <= '4') {
1369                 i = 8;
1370                 goto only_spaces_and_periods;
1371         }
1372
1373         /*
1374          * Is it a fall-back NTFS short name (for details, see
1375          * https://en.wikipedia.org/wiki/8.3_filename?
1376          */
1377         for (i = 0, saw_tilde = 0; i < 8; i++)
1378                 if (name[i] == '\0')
1379                         return 0;
1380                 else if (saw_tilde) {
1381                         if (name[i] < '0' || name[i] > '9')
1382                                 return 0;
1383                 } else if (name[i] == '~') {
1384                         if (name[++i] < '1' || name[i] > '9')
1385                                 return 0;
1386                         saw_tilde = 1;
1387                 } else if (i >= 6)
1388                         return 0;
1389                 else if (name[i] & 0x80) {
1390                         /*
1391                          * We know our needles contain only ASCII, so we clamp
1392                          * here to make the results of tolower() sane.
1393                          */
1394                         return 0;
1395                 } else if (tolower(name[i]) != dotgit_ntfs_shortname_prefix[i])
1396                         return 0;
1397
1398         goto only_spaces_and_periods;
1399 }
1400
1401 /*
1402  * Inline helper to make sure compiler resolves strlen() on literals at
1403  * compile time.
1404  */
1405 static inline int is_ntfs_dot_str(const char *name, const char *dotgit_name,
1406                                   const char *dotgit_ntfs_shortname_prefix)
1407 {
1408         return is_ntfs_dot_generic(name, dotgit_name, strlen(dotgit_name),
1409                                    dotgit_ntfs_shortname_prefix);
1410 }
1411
1412 int is_ntfs_dotgitmodules(const char *name)
1413 {
1414         return is_ntfs_dot_str(name, "gitmodules", "gi7eba");
1415 }
1416
1417 int is_ntfs_dotgitignore(const char *name)
1418 {
1419         return is_ntfs_dot_str(name, "gitignore", "gi250a");
1420 }
1421
1422 int is_ntfs_dotgitattributes(const char *name)
1423 {
1424         return is_ntfs_dot_str(name, "gitattributes", "gi7d29");
1425 }
1426
1427 int looks_like_command_line_option(const char *str)
1428 {
1429         return str && str[0] == '-';
1430 }
1431
1432 char *xdg_config_home(const char *filename)
1433 {
1434         const char *home, *config_home;
1435
1436         assert(filename);
1437         config_home = getenv("XDG_CONFIG_HOME");
1438         if (config_home && *config_home)
1439                 return mkpathdup("%s/git/%s", config_home, filename);
1440
1441         home = getenv("HOME");
1442         if (home)
1443                 return mkpathdup("%s/.config/git/%s", home, filename);
1444         return NULL;
1445 }
1446
1447 char *xdg_cache_home(const char *filename)
1448 {
1449         const char *home, *cache_home;
1450
1451         assert(filename);
1452         cache_home = getenv("XDG_CACHE_HOME");
1453         if (cache_home && *cache_home)
1454                 return mkpathdup("%s/git/%s", cache_home, filename);
1455
1456         home = getenv("HOME");
1457         if (home)
1458                 return mkpathdup("%s/.cache/git/%s", home, filename);
1459         return NULL;
1460 }
1461
1462 REPO_GIT_PATH_FUNC(cherry_pick_head, "CHERRY_PICK_HEAD")
1463 REPO_GIT_PATH_FUNC(revert_head, "REVERT_HEAD")
1464 REPO_GIT_PATH_FUNC(squash_msg, "SQUASH_MSG")
1465 REPO_GIT_PATH_FUNC(merge_msg, "MERGE_MSG")
1466 REPO_GIT_PATH_FUNC(merge_rr, "MERGE_RR")
1467 REPO_GIT_PATH_FUNC(merge_mode, "MERGE_MODE")
1468 REPO_GIT_PATH_FUNC(merge_head, "MERGE_HEAD")
1469 REPO_GIT_PATH_FUNC(fetch_head, "FETCH_HEAD")
1470 REPO_GIT_PATH_FUNC(shallow, "shallow")