rev-list: make "estimate_bisect_steps" non static
[git] / symlinks.c
1 #include "cache.h"
2
3 /*
4  * Returns the length (on a path component basis) of the longest
5  * common prefix match of 'name_a' and 'name_b'.
6  */
7 static int longest_path_match(const char *name_a, int len_a,
8                               const char *name_b, int len_b,
9                               int *previous_slash)
10 {
11         int max_len, match_len = 0, match_len_prev = 0, i = 0;
12
13         max_len = len_a < len_b ? len_a : len_b;
14         while (i < max_len && name_a[i] == name_b[i]) {
15                 if (name_a[i] == '/') {
16                         match_len_prev = match_len;
17                         match_len = i;
18                 }
19                 i++;
20         }
21         /*
22          * Is 'name_b' a substring of 'name_a', the other way around,
23          * or is 'name_a' and 'name_b' the exact same string?
24          */
25         if (i >= max_len && ((len_a > len_b && name_a[len_b] == '/') ||
26                              (len_a < len_b && name_b[len_a] == '/') ||
27                              (len_a == len_b))) {
28                 match_len_prev = match_len;
29                 match_len = i;
30         }
31         *previous_slash = match_len_prev;
32         return match_len;
33 }
34
35 static struct cache_def {
36         char path[PATH_MAX + 1];
37         int len;
38         int flags;
39         int track_flags;
40         int prefix_len_stat_func;
41 } cache;
42
43 static inline void reset_lstat_cache(void)
44 {
45         cache.path[0] = '\0';
46         cache.len = 0;
47         cache.flags = 0;
48         /*
49          * The track_flags and prefix_len_stat_func members is only
50          * set by the safeguard rule inside lstat_cache()
51          */
52 }
53
54 #define FL_DIR      (1 << 0)
55 #define FL_NOENT    (1 << 1)
56 #define FL_SYMLINK  (1 << 2)
57 #define FL_LSTATERR (1 << 3)
58 #define FL_ERR      (1 << 4)
59 #define FL_FULLPATH (1 << 5)
60
61 /*
62  * Check if name 'name' of length 'len' has a symlink leading
63  * component, or if the directory exists and is real, or not.
64  *
65  * To speed up the check, some information is allowed to be cached.
66  * This can be indicated by the 'track_flags' argument, which also can
67  * be used to indicate that we should check the full path.
68  *
69  * The 'prefix_len_stat_func' parameter can be used to set the length
70  * of the prefix, where the cache should use the stat() function
71  * instead of the lstat() function to test each path component.
72  */
73 static int lstat_cache(const char *name, int len,
74                        int track_flags, int prefix_len_stat_func)
75 {
76         int match_len, last_slash, last_slash_dir, previous_slash;
77         int match_flags, ret_flags, save_flags, max_len, ret;
78         struct stat st;
79
80         if (cache.track_flags != track_flags ||
81             cache.prefix_len_stat_func != prefix_len_stat_func) {
82                 /*
83                  * As a safeguard rule we clear the cache if the
84                  * values of track_flags and/or prefix_len_stat_func
85                  * does not match with the last supplied values.
86                  */
87                 reset_lstat_cache();
88                 cache.track_flags = track_flags;
89                 cache.prefix_len_stat_func = prefix_len_stat_func;
90                 match_len = last_slash = 0;
91         } else {
92                 /*
93                  * Check to see if we have a match from the cache for
94                  * the 2 "excluding" path types.
95                  */
96                 match_len = last_slash =
97                         longest_path_match(name, len, cache.path, cache.len,
98                                            &previous_slash);
99                 match_flags = cache.flags & track_flags & (FL_NOENT|FL_SYMLINK);
100                 if (match_flags && match_len == cache.len)
101                         return match_flags;
102                 /*
103                  * If we now have match_len > 0, we would know that
104                  * the matched part will always be a directory.
105                  *
106                  * Also, if we are tracking directories and 'name' is
107                  * a substring of the cache on a path component basis,
108                  * we can return immediately.
109                  */
110                 match_flags = track_flags & FL_DIR;
111                 if (match_flags && len == match_len)
112                         return match_flags;
113         }
114
115         /*
116          * Okay, no match from the cache so far, so now we have to
117          * check the rest of the path components.
118          */
119         ret_flags = FL_DIR;
120         last_slash_dir = last_slash;
121         max_len = len < PATH_MAX ? len : PATH_MAX;
122         while (match_len < max_len) {
123                 do {
124                         cache.path[match_len] = name[match_len];
125                         match_len++;
126                 } while (match_len < max_len && name[match_len] != '/');
127                 if (match_len >= max_len && !(track_flags & FL_FULLPATH))
128                         break;
129                 last_slash = match_len;
130                 cache.path[last_slash] = '\0';
131
132                 if (last_slash <= prefix_len_stat_func)
133                         ret = stat(cache.path, &st);
134                 else
135                         ret = lstat(cache.path, &st);
136
137                 if (ret) {
138                         ret_flags = FL_LSTATERR;
139                         if (errno == ENOENT)
140                                 ret_flags |= FL_NOENT;
141                 } else if (S_ISDIR(st.st_mode)) {
142                         last_slash_dir = last_slash;
143                         continue;
144                 } else if (S_ISLNK(st.st_mode)) {
145                         ret_flags = FL_SYMLINK;
146                 } else {
147                         ret_flags = FL_ERR;
148                 }
149                 break;
150         }
151
152         /*
153          * At the end update the cache.  Note that max 3 different
154          * path types, FL_NOENT, FL_SYMLINK and FL_DIR, can be cached
155          * for the moment!
156          */
157         save_flags = ret_flags & track_flags & (FL_NOENT|FL_SYMLINK);
158         if (save_flags && last_slash > 0 && last_slash <= PATH_MAX) {
159                 cache.path[last_slash] = '\0';
160                 cache.len = last_slash;
161                 cache.flags = save_flags;
162         } else if ((track_flags & FL_DIR) &&
163                    last_slash_dir > 0 && last_slash_dir <= PATH_MAX) {
164                 /*
165                  * We have a separate test for the directory case,
166                  * since it could be that we have found a symlink or a
167                  * non-existing directory and the track_flags says
168                  * that we cannot cache this fact, so the cache would
169                  * then have been left empty in this case.
170                  *
171                  * But if we are allowed to track real directories, we
172                  * can still cache the path components before the last
173                  * one (the found symlink or non-existing component).
174                  */
175                 cache.path[last_slash_dir] = '\0';
176                 cache.len = last_slash_dir;
177                 cache.flags = FL_DIR;
178         } else {
179                 reset_lstat_cache();
180         }
181         return ret_flags;
182 }
183
184 /*
185  * Invalidate the given 'name' from the cache, if 'name' matches
186  * completely with the cache.
187  */
188 void invalidate_lstat_cache(const char *name, int len)
189 {
190         int match_len, previous_slash;
191
192         match_len = longest_path_match(name, len, cache.path, cache.len,
193                                        &previous_slash);
194         if (len == match_len) {
195                 if ((cache.track_flags & FL_DIR) && previous_slash > 0) {
196                         cache.path[previous_slash] = '\0';
197                         cache.len = previous_slash;
198                         cache.flags = FL_DIR;
199                 } else
200                         reset_lstat_cache();
201         }
202 }
203
204 /*
205  * Completely clear the contents of the cache
206  */
207 void clear_lstat_cache(void)
208 {
209         reset_lstat_cache();
210 }
211
212 #define USE_ONLY_LSTAT  0
213
214 /*
215  * Return non-zero if path 'name' has a leading symlink component
216  */
217 int has_symlink_leading_path(const char *name, int len)
218 {
219         return lstat_cache(name, len,
220                            FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
221                 FL_SYMLINK;
222 }
223
224 /*
225  * Return non-zero if path 'name' has a leading symlink component or
226  * if some leading path component does not exists.
227  */
228 int has_symlink_or_noent_leading_path(const char *name, int len)
229 {
230         return lstat_cache(name, len,
231                            FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) &
232                 (FL_SYMLINK|FL_NOENT);
233 }
234
235 /*
236  * Return non-zero if all path components of 'name' exists as a
237  * directory.  If prefix_len > 0, we will test with the stat()
238  * function instead of the lstat() function for a prefix length of
239  * 'prefix_len', thus we then allow for symlinks in the prefix part as
240  * long as those points to real existing directories.
241  */
242 int has_dirs_only_path(const char *name, int len, int prefix_len)
243 {
244         return lstat_cache(name, len,
245                            FL_DIR|FL_FULLPATH, prefix_len) &
246                 FL_DIR;
247 }
248
249 static struct removal_def {
250         char path[PATH_MAX];
251         int len;
252 } removal;
253
254 static void do_remove_scheduled_dirs(int new_len)
255 {
256         while (removal.len > new_len) {
257                 removal.path[removal.len] = '\0';
258                 if (rmdir(removal.path))
259                         break;
260                 do {
261                         removal.len--;
262                 } while (removal.len > new_len &&
263                          removal.path[removal.len] != '/');
264         }
265         removal.len = new_len;
266         return;
267 }
268
269 void schedule_dir_for_removal(const char *name, int len)
270 {
271         int match_len, last_slash, i, previous_slash;
272
273         match_len = last_slash = i =
274                 longest_path_match(name, len, removal.path, removal.len,
275                                    &previous_slash);
276         /* Find last slash inside 'name' */
277         while (i < len) {
278                 if (name[i] == '/')
279                         last_slash = i;
280                 i++;
281         }
282
283         /*
284          * If we are about to go down the directory tree, we check if
285          * we must first go upwards the tree, such that we then can
286          * remove possible empty directories as we go upwards.
287          */
288         if (match_len < last_slash && match_len < removal.len)
289                 do_remove_scheduled_dirs(match_len);
290         /*
291          * If we go deeper down the directory tree, we only need to
292          * save the new path components as we go down.
293          */
294         if (match_len < last_slash) {
295                 memcpy(&removal.path[match_len], &name[match_len],
296                        last_slash - match_len);
297                 removal.len = last_slash;
298         }
299         return;
300 }
301
302 void remove_scheduled_dirs(void)
303 {
304         do_remove_scheduled_dirs(0);
305         return;
306 }