source: mainline/uspace/lib/c/generic/vfs/canonify.c@ 76ca3f7

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 76ca3f7 was 63f8966, checked in by Martin Decky <martin@…>, 15 years ago

rename library directories (the common "lib" prefix is already in the upper directory)
  • Property mode set to 100644
File size: 7.2 KB
Line 
1/*
2 * Copyright (c) 2008 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libc
30 * @{
31 */
32
33/**
34 * @file
35 * @brief
36 */
37
38#include <stdlib.h>
39#include <vfs/canonify.h>
40
41/** Token types used for tokenization of path. */
42typedef enum {
43 TK_INVALID,
44 TK_SLASH,
45 TK_DOT,
46 TK_DOTDOT,
47 TK_COMP,
48 TK_NUL
49} tokval_t;
50
51typedef struct {
52 tokval_t kind;
53 char *start;
54 char *stop;
55} token_t;
56
57/** Fake up the TK_SLASH token. */
58static token_t slash_token(char *start)
59{
60 token_t ret;
61 ret.kind = TK_SLASH;
62 ret.start = start;
63 ret.stop = start;
64 return ret;
65}
66
67/** Given a token, return the next token. */
68static token_t next_token(token_t *cur)
69{
70 token_t ret;
71
72 if (cur->stop[1] == '\0') {
73 ret.kind = TK_NUL;
74 ret.start = cur->stop + 1;
75 ret.stop = ret.start;
76 return ret;
77 }
78 if (cur->stop[1] == '/') {
79 ret.kind = TK_SLASH;
80 ret.start = cur->stop + 1;
81 ret.stop = ret.start;
82 return ret;
83 }
84 if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
85 ret.kind = TK_DOT;
86 ret.start = cur->stop + 1;
87 ret.stop = ret.start;
88 return ret;
89 }
90 if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
91 (!cur->stop[3] || cur->stop[3] == '/')) {
92 ret.kind = TK_DOTDOT;
93 ret.start = cur->stop + 1;
94 ret.stop = cur->stop + 2;
95 return ret;
96 }
97 unsigned i;
98 for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
99 ;
100 ret.kind = TK_COMP;
101 ret.start = &cur->stop[1];
102 ret.stop = &cur->stop[i - 1];
103 return ret;
104}
105
106/** States used by canonify(). */
107typedef enum {
108 S_INI,
109 S_A,
110 S_B,
111 S_C,
112 S_ACCEPT,
113 S_RESTART,
114 S_REJECT
115} state_t;
116
117typedef struct {
118 state_t s;
119 void (* f)(token_t *, token_t *, token_t *);
120} change_state_t;
121
122/*
123 * Actions that can be performed when transitioning from one
124 * state of canonify() to another.
125 */
126static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
127{
128 *tfsl = *t;
129 *tlcomp = *t;
130}
131static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
132{
133 *tlcomp = *t;
134}
135static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
136{
137 if (tfsl->stop[1]) /* avoid writing to a well-formatted path */
138 tfsl->stop[1] = '\0';
139}
140static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
141{
142 t->start[-1] = '\0';
143}
144/** Eat the extra '/'.
145 *
146 * @param t The current TK_SLASH token.
147 */
148static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
149{
150 char *p = t->start;
151 char *q = t->stop + 1;
152 while ((*p++ = *q++))
153 ;
154}
155/** Eat the extra '.'.
156 *
157 * @param t The current TK_DOT token.
158 */
159static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
160{
161 char *p = t->start;
162 char *q = t->stop + 1;
163 while ((*p++ = *q++))
164 ;
165}
166/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
167 *
168 * @param t The current TK_DOTDOT token.
169 * @param tlcomp The last TK_COMP token.
170 */
171static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
172{
173 char *p = tlcomp->start;
174 char *q = t->stop + 1;
175 while ((*p++ = *q++))
176 ;
177}
178
179/** Transition function for canonify(). */
180static change_state_t trans[4][6] = {
181 [S_INI] = {
182 [TK_SLASH] = {
183 .s = S_A,
184 .f = set_first_slash,
185 },
186 [TK_DOT] = {
187 .s = S_REJECT,
188 .f = NULL,
189 },
190 [TK_DOTDOT] = {
191 .s = S_REJECT,
192 .f = NULL,
193 },
194 [TK_COMP] = {
195 .s = S_REJECT,
196 .f = NULL,
197 },
198 [TK_NUL] = {
199 .s = S_REJECT,
200 .f = NULL,
201 },
202 [TK_INVALID] = {
203 .s = S_REJECT,
204 .f = NULL,
205 },
206 },
207 [S_A] = {
208 [TK_SLASH] = {
209 .s = S_A,
210 .f = set_first_slash,
211 },
212 [TK_DOT] = {
213 .s = S_A,
214 .f = NULL,
215 },
216 [TK_DOTDOT] = {
217 .s = S_A,
218 .f = NULL,
219 },
220 [TK_COMP] = {
221 .s = S_B,
222 .f = save_component,
223 },
224 [TK_NUL] = {
225 .s = S_ACCEPT,
226 .f = terminate_slash,
227 },
228 [TK_INVALID] = {
229 .s = S_REJECT,
230 .f = NULL,
231 },
232 },
233 [S_B] = {
234 [TK_SLASH] = {
235 .s = S_C,
236 .f = NULL,
237 },
238 [TK_DOT] = {
239 .s = S_REJECT,
240 .f = NULL,
241 },
242 [TK_DOTDOT] = {
243 .s = S_REJECT,
244 .f = NULL,
245 },
246 [TK_COMP] = {
247 .s = S_REJECT,
248 .f = NULL,
249 },
250 [TK_NUL] = {
251 .s = S_ACCEPT,
252 .f = NULL,
253 },
254 [TK_INVALID] = {
255 .s = S_REJECT,
256 .f = NULL,
257 },
258 },
259 [S_C] = {
260 [TK_SLASH] = {
261 .s = S_RESTART,
262 .f = shift_slash,
263 },
264 [TK_DOT] = {
265 .s = S_RESTART,
266 .f = shift_dot,
267 },
268 [TK_DOTDOT] = {
269 .s = S_RESTART,
270 .f = shift_dotdot,
271 },
272 [TK_COMP] = {
273 .s = S_B,
274 .f = save_component,
275 },
276 [TK_NUL] = {
277 .s = S_ACCEPT,
278 .f = remove_trailing_slash,
279 },
280 [TK_INVALID] = {
281 .s = S_REJECT,
282 .f = NULL,
283 },
284 }
285};
286
287/** Canonify a file system path.
288 *
289 * A file system path is canonical, if the following holds:
290 *
291 * 1) the path is absolute
292 * (i.e. a/b/c is not canonical)
293 * 2) there is no trailing slash in the path if it has components
294 * (i.e. /a/b/c/ is not canonical)
295 * 3) there is no extra slash in the path
296 * (i.e. /a//b/c is not canonical)
297 * 4) there is no '.' component in the path
298 * (i.e. /a/./b/c is not canonical)
299 * 5) there is no '..' component in the path
300 * (i.e. /a/b/../c is not canonical)
301 *
302 * This function makes a potentially non-canonical file system path canonical.
303 * It works in-place and requires a NULL-terminated input string.
304 *
305 * @param path Path to be canonified.
306 * @param lenp Pointer where the length of the final path will be
307 * stored. Can be NULL.
308 *
309 * @return Canonified path or NULL on failure.
310 */
311char *canonify(char *path, size_t *lenp)
312{
313 state_t state;
314 token_t t;
315 token_t tfsl; /* first slash */
316 token_t tlcomp; /* last component */
317 if (*path != '/')
318 return NULL;
319 tfsl = slash_token(path);
320restart:
321 state = S_INI;
322 t = tfsl;
323 tlcomp = tfsl;
324 while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
325 if (trans[state][t.kind].f)
326 trans[state][t.kind].f(&t, &tfsl, &tlcomp);
327 state = trans[state][t.kind].s;
328 t = next_token(&t);
329 }
330
331 switch (state) {
332 case S_RESTART:
333 goto restart;
334 case S_REJECT:
335 return NULL;
336 case S_ACCEPT:
337 if (lenp)
338 *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
339 return tfsl.start;
340 default:
341 abort();
342 }
343}
344
345/**
346 * @}
347 */
Note: See TracBrowser for help on using the repository browser.