source: mainline/uspace/lib/c/generic/vfs/canonify.c@ 1be7bee

Last change on this file since 1be7bee was 1433ecda, checked in by Jiri Svoboda <jiri@…>, 7 years ago

Fix cstyle: make ccheck-fix and commit only files where all the changes are good.
  • 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 <stddef.h>
40#include <vfs/canonify.h>
41
42/** Token types used for tokenization of path. */
43typedef enum {
44 TK_INVALID,
45 TK_SLASH,
46 TK_DOT,
47 TK_DOTDOT,
48 TK_COMP,
49 TK_NUL
50} tokval_t;
51
52typedef struct {
53 tokval_t kind;
54 char *start;
55 char *stop;
56} token_t;
57
58/** Fake up the TK_SLASH token. */
59static token_t slash_token(char *start)
60{
61 token_t ret;
62 ret.kind = TK_SLASH;
63 ret.start = start;
64 ret.stop = start;
65 return ret;
66}
67
68/** Given a token, return the next token. */
69static token_t next_token(token_t *cur)
70{
71 token_t ret;
72
73 if (cur->stop[1] == '\0') {
74 ret.kind = TK_NUL;
75 ret.start = cur->stop + 1;
76 ret.stop = ret.start;
77 return ret;
78 }
79 if (cur->stop[1] == '/') {
80 ret.kind = TK_SLASH;
81 ret.start = cur->stop + 1;
82 ret.stop = ret.start;
83 return ret;
84 }
85 if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
86 ret.kind = TK_DOT;
87 ret.start = cur->stop + 1;
88 ret.stop = ret.start;
89 return ret;
90 }
91 if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
92 (!cur->stop[3] || cur->stop[3] == '/')) {
93 ret.kind = TK_DOTDOT;
94 ret.start = cur->stop + 1;
95 ret.stop = cur->stop + 2;
96 return ret;
97 }
98 unsigned i = 1;
99 while (cur->stop[i] && cur->stop[i] != '/')
100 i++;
101
102 ret.kind = TK_COMP;
103 ret.start = &cur->stop[1];
104 ret.stop = &cur->stop[i - 1];
105 return ret;
106}
107
108/** States used by canonify(). */
109typedef enum {
110 S_INI,
111 S_A,
112 S_B,
113 S_C,
114 S_ACCEPT,
115 S_RESTART,
116 S_REJECT
117} state_t;
118
119typedef struct {
120 state_t s;
121 void (*f)(token_t *, token_t *, token_t *);
122} change_state_t;
123
124/*
125 * Actions that can be performed when transitioning from one
126 * state of canonify() to another.
127 */
128static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
129{
130 *tfsl = *t;
131 *tlcomp = *t;
132}
133static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
134{
135 *tlcomp = *t;
136}
137static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
138{
139 if (tfsl->stop[1]) /* avoid writing to a well-formatted path */
140 tfsl->stop[1] = '\0';
141}
142static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
143{
144 t->start[-1] = '\0';
145}
146/** Eat the extra '/'.
147 *
148 * @param t The current TK_SLASH token.
149 */
150static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
151{
152 char *p = t->start;
153 char *q = t->stop + 1;
154 while ((*p++ = *q++))
155 ;
156}
157/** Eat the extra '.'.
158 *
159 * @param t The current TK_DOT token.
160 */
161static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
162{
163 char *p = t->start;
164 char *q = t->stop + 1;
165 while ((*p++ = *q++))
166 ;
167}
168/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
169 *
170 * @param t The current TK_DOTDOT token.
171 * @param tlcomp The last TK_COMP token.
172 */
173static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
174{
175 char *p = tlcomp->start;
176 char *q = t->stop + 1;
177 while ((*p++ = *q++))
178 ;
179}
180
181/** Transition function for canonify(). */
182static change_state_t trans[4][6] = {
183 [S_INI] = {
184 [TK_SLASH] = {
185 .s = S_A,
186 .f = set_first_slash,
187 },
188 [TK_DOT] = {
189 .s = S_REJECT,
190 .f = NULL,
191 },
192 [TK_DOTDOT] = {
193 .s = S_REJECT,
194 .f = NULL,
195 },
196 [TK_COMP] = {
197 .s = S_REJECT,
198 .f = NULL,
199 },
200 [TK_NUL] = {
201 .s = S_REJECT,
202 .f = NULL,
203 },
204 [TK_INVALID] = {
205 .s = S_REJECT,
206 .f = NULL,
207 },
208 },
209 [S_A] = {
210 [TK_SLASH] = {
211 .s = S_A,
212 .f = set_first_slash,
213 },
214 [TK_DOT] = {
215 .s = S_A,
216 .f = NULL,
217 },
218 [TK_DOTDOT] = {
219 .s = S_A,
220 .f = NULL,
221 },
222 [TK_COMP] = {
223 .s = S_B,
224 .f = save_component,
225 },
226 [TK_NUL] = {
227 .s = S_ACCEPT,
228 .f = terminate_slash,
229 },
230 [TK_INVALID] = {
231 .s = S_REJECT,
232 .f = NULL,
233 },
234 },
235 [S_B] = {
236 [TK_SLASH] = {
237 .s = S_C,
238 .f = NULL,
239 },
240 [TK_DOT] = {
241 .s = S_REJECT,
242 .f = NULL,
243 },
244 [TK_DOTDOT] = {
245 .s = S_REJECT,
246 .f = NULL,
247 },
248 [TK_COMP] = {
249 .s = S_REJECT,
250 .f = NULL,
251 },
252 [TK_NUL] = {
253 .s = S_ACCEPT,
254 .f = NULL,
255 },
256 [TK_INVALID] = {
257 .s = S_REJECT,
258 .f = NULL,
259 },
260 },
261 [S_C] = {
262 [TK_SLASH] = {
263 .s = S_RESTART,
264 .f = shift_slash,
265 },
266 [TK_DOT] = {
267 .s = S_RESTART,
268 .f = shift_dot,
269 },
270 [TK_DOTDOT] = {
271 .s = S_RESTART,
272 .f = shift_dotdot,
273 },
274 [TK_COMP] = {
275 .s = S_B,
276 .f = save_component,
277 },
278 [TK_NUL] = {
279 .s = S_ACCEPT,
280 .f = remove_trailing_slash,
281 },
282 [TK_INVALID] = {
283 .s = S_REJECT,
284 .f = NULL,
285 },
286 }
287};
288
289/** Canonify a file system path.
290 *
291 * A file system path is canonical, if the following holds:
292 *
293 * 1) the path is absolute
294 * (i.e. a/b/c is not canonical)
295 * 2) there is no trailing slash in the path if it has components
296 * (i.e. /a/b/c/ is not canonical)
297 * 3) there is no extra slash in the path
298 * (i.e. /a//b/c is not canonical)
299 * 4) there is no '.' component in the path
300 * (i.e. /a/./b/c is not canonical)
301 * 5) there is no '..' component in the path
302 * (i.e. /a/b/../c is not canonical)
303 *
304 * This function makes a potentially non-canonical file system path canonical.
305 * It works in-place and requires a NULL-terminated input string.
306 *
307 * @param path Path to be canonified.
308 * @param lenp Pointer where the length of the final path will be
309 * stored. Can be NULL.
310 *
311 * @return Canonified path or NULL on failure.
312 */
313char *canonify(char *path, size_t *lenp)
314{
315 state_t state;
316 token_t t;
317 token_t tfsl; /* first slash */
318 token_t tlcomp; /* last component */
319 if (*path != '/')
320 return NULL;
321 tfsl = slash_token(path);
322restart:
323 state = S_INI;
324 t = tfsl;
325 tlcomp = tfsl;
326 while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
327 if (trans[state][t.kind].f)
328 trans[state][t.kind].f(&t, &tfsl, &tlcomp);
329 state = trans[state][t.kind].s;
330 t = next_token(&t);
331 }
332
333 switch (state) {
334 case S_RESTART:
335 goto restart;
336 case S_REJECT:
337 return NULL;
338 case S_ACCEPT:
339 if (lenp)
340 *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
341 return tfsl.start;
342 default:
343 abort();
344 }
345}
346
347/**
348 * @}
349 */
Note: See TracBrowser for help on using the repository browser.