1 /*
2  * Copyright (c) 2018, 2019 Stefan Sperling <stsp@openbsd.org>
3  * Copyright (c) 2015 Theo de Raadt <deraadt@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <sys/queue.h>
19 
20 #include <limits.h>
21 #include <stdlib.h>
22 #include <unistd.h>
23 #include <stdio.h>
24 #include <string.h>
25 
26 #include "got_error.h"
27 
28 #include "got_lib_path.h"
29 
30 #ifndef MIN
31 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
32 #endif
33 
34 int
35 got_path_is_absolute(const char *path)
36 {
37 	return path[0] == '/';
38 }
39 
40 char *
41 got_path_get_absolute(const char *relpath) 
42 {
43 	char cwd[PATH_MAX];
44 	char *abspath;
45 
46 	if (getcwd(cwd, sizeof(cwd)) == NULL)
47 		return NULL;
48 
49 	if (asprintf(&abspath, "%s/%s/", cwd, relpath) == -1)
50 		return NULL;
51 
52 	return abspath;
53 }
54 
55 char *
56 got_path_normalize(const char *path)
57 {
58 	char *resolved;
59 
60 	resolved = realpath(path, NULL);
61 	if (resolved == NULL)
62 		return NULL;
63 	
64 	if (!got_path_is_absolute(resolved)) {
65 		char *abspath = got_path_get_absolute(resolved);
66 		free(resolved);
67 		resolved = abspath;
68 	}
69 
70 	return resolved;
71 }
72 
73 /* based on canonpath() from kern_pledge.c */
74 const struct got_error *
75 got_canonpath(const char *input, char *buf, size_t bufsize)
76 {
77 	const char *p;
78 	char *q;
79 
80 	/* can't canon relative paths, don't bother */
81 	if (!got_path_is_absolute(input)) {
82 		if (strlcpy(buf, input, bufsize) >= bufsize)
83 			return got_error(GOT_ERR_NO_SPACE);
84 		return NULL;
85 	}
86 
87 	p = input;
88 	q = buf;
89 	while (*p && (q - buf < bufsize)) {
90 		if (p[0] == '/' && (p[1] == '/' || p[1] == '\0')) {
91 			p += 1;
92 
93 		} else if (p[0] == '/' && p[1] == '.' &&
94 		    (p[2] == '/' || p[2] == '\0')) {
95 			p += 2;
96 
97 		} else if (p[0] == '/' && p[1] == '.' && p[2] == '.' &&
98 		    (p[3] == '/' || p[3] == '\0')) {
99 			p += 3;
100 			if (q != buf)	/* "/../" at start of buf */
101 				while (*--q != '/')
102 					continue;
103 
104 		} else {
105 			*q++ = *p++;
106 		}
107 	}
108 	if ((*p == '\0') && (q - buf < bufsize)) {
109 		*q = 0;
110 		return NULL;
111 	} else
112 		return got_error(GOT_ERR_NO_SPACE);
113 }
114 
115 const struct got_error *
116 got_path_skip_common_ancestor(char **child, const char *parent_abspath,
117     const char *abspath)
118 {
119 	const struct got_error *err = NULL;
120 	size_t len_parent, len, bufsize;
121 
122 	len_parent = strlen(parent_abspath);
123 	len = strlen(abspath);
124 	if (len_parent >= len)
125 		return got_error(GOT_ERR_BAD_PATH);
126 	if (strncmp(parent_abspath, abspath, len_parent) != 0)
127 		return got_error(GOT_ERR_BAD_PATH);
128 	if (abspath[len_parent] != '/')
129 		return got_error(GOT_ERR_BAD_PATH);
130 	bufsize = len - len_parent + 1;
131 	*child = malloc(bufsize);
132 	if (*child == NULL)
133 		return got_error_from_errno();
134 	if (strlcpy(*child, abspath + len_parent, bufsize) >= bufsize) {
135 		err = got_error_from_errno();
136 		free(*child);
137 		*child = NULL;
138 		return err;
139 	}
140 	return NULL;
141 }
142 
143 int
144 got_path_is_root_dir(const char *path)
145 {
146 	return (path[0] == '/' && path[1] == '\0');
147 }
148 
149 int
150 got_path_is_child(const char *child, const char *parent, size_t parent_len)
151 {
152 	if (parent_len == 0)
153 		return 1;
154 
155 	if (strncmp(parent, child, parent_len) != 0)
156 		return 0;
157 	if (child[parent_len] != '/')
158 		return 0;
159 
160 	return 1;
161 }
162 
163 int
164 got_path_cmp(const char *path1, const char *path2)
165 {
166 	size_t len1 = strlen(path1);
167 	size_t len2 = strlen(path2);
168 	size_t min_len = MIN(len1, len2);
169 	size_t i = 0;
170 
171 	/* Leading directory separators are insignificant. */
172 	while (path1[0] == '/')
173 		path1++;
174 	while (path2[0] == '/')
175 		path2++;
176 
177 	len1 = strlen(path1);
178 	len2 = strlen(path2);
179 	min_len = MIN(len1, len2);
180 
181 	/* Skip over common prefix. */
182 	while (i < min_len && path1[i] == path2[i])
183 		i++;
184 
185 	/* Are the paths exactly equal (besides path separators)? */
186 	if (len1 == len2 && i >= min_len)
187 		return 0;
188 
189 	/* Skip over redundant trailing path seperators. */
190 	while (path1[i] == '/' && path1[i + 1] == '/')
191 		path1++;
192 	while (path2[i] == '/' && path2[i + 1] == '/')
193 		path2++;
194 
195 	/* Trailing path separators are insignificant. */
196 	if (path1[i] == '/' && path1[i + 1] == '\0' && path2[i] == '\0')
197 		return 0;
198 	if (path2[i] == '/' && path2[i + 1] == '\0' && path1[i] == '\0')
199 		return 0;
200 
201 	/* Order children in subdirectories directly after their parents. */
202 	if (path1[i] == '/' && path2[i] == '\0')
203 		return 1;
204 	if (path2[i] == '/' && path1[i] == '\0')
205 		return -1;
206 	if (path1[i] == '/' && path2[i] != '\0')
207 		return -1;
208 	if (path2[i] == '/' && path1[i] != '\0')
209 		return 1;
210 
211 	/* Next character following the common prefix determines order. */
212 	return (unsigned char)path1[i] < (unsigned char)path2[i] ? -1 : 1;
213 }
214 
215 const struct got_error *
216 got_pathlist_insert(struct got_pathlist_entry **inserted,
217     struct got_pathlist_head *pathlist, const char *path, void *data)
218 {
219 	struct got_pathlist_entry *new, *pe;
220 
221 	if (inserted)
222 		*inserted = NULL;
223 
224 	new = malloc(sizeof(*new));
225 	if (new == NULL)
226 		return got_error_from_errno();
227 	new->path = path;
228 	new->data = data;
229 
230 	/*
231 	 * Many callers will provide paths in a somewhat sorted order while
232 	 * constructing a path list from inputs such as tree objects or
233 	 * dirents. Iterating backwards from the tail of the list should
234 	 * be more efficient than traversing through the entire list each
235 	 * time an element is inserted.
236 	 */
237 	pe = TAILQ_LAST(pathlist, got_pathlist_head);
238 	while (pe) {
239 		int cmp = got_path_cmp(pe->path, path);
240 		if (cmp == 0) {
241 			free(new); /* duplicate */
242 			return NULL;
243 		} else if (cmp < 0) {
244 			TAILQ_INSERT_AFTER(pathlist, pe, new, entry);
245 			if (inserted)
246 				*inserted = new;
247 			return NULL;
248 		}
249 		pe = TAILQ_PREV(pe, got_pathlist_head, entry);
250 	}
251 
252 	TAILQ_INSERT_HEAD(pathlist, new, entry);
253 	if (inserted)
254 		*inserted = new;
255 	return NULL;
256 }
257 
258 void
259 got_pathlist_free(struct got_pathlist_head *pathlist)
260 {
261 	struct got_pathlist_entry *pe;
262 
263 	while ((pe = TAILQ_FIRST(pathlist)) != NULL) {
264 		TAILQ_REMOVE(pathlist, pe, entry);
265 		free(pe);
266 	}
267 }