source: mainline/uspace/lib/c/generic/vfs/canonify.c@ 338d54a7

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 338d54a7 was a35b458, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 8 years ago

style: Remove trailing whitespace on _all_ lines, including empty ones, for particular file types.

Command used: tools/srepl '\s\+$' '' -- *.c *.h *.py *.sh *.s *.S *.ag

Currently, whitespace on empty lines is very inconsistent.
There are two basic choices: Either remove the whitespace, or keep empty lines
indented to the level of surrounding code. The former is AFAICT more common,
and also much easier to do automatically.

Alternatively, we could write script for automatic indentation, and use that
instead. However, if such a script exists, it's possible to use the indented
style locally, by having the editor apply relevant conversions on load/save,
without affecting remote repository. IMO, it makes more sense to adopt
the simpler rule.
  • 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;
99 for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
100 ;
101 ret.kind = TK_COMP;
102 ret.start = &cur->stop[1];
103 ret.stop = &cur->stop[i - 1];
104 return ret;
105}
106
107/** States used by canonify(). */
108typedef enum {
109 S_INI,
110 S_A,
111 S_B,
112 S_C,
113 S_ACCEPT,
114 S_RESTART,
115 S_REJECT
116} state_t;
117
118typedef struct {
119 state_t s;
120 void (* f)(token_t *, token_t *, token_t *);
121} change_state_t;
122
123/*
124 * Actions that can be performed when transitioning from one
125 * state of canonify() to another.
126 */
127static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
128{
129 *tfsl = *t;
130 *tlcomp = *t;
131}
132static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
133{
134 *tlcomp = *t;
135}
136static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
137{
138 if (tfsl->stop[1]) /* avoid writing to a well-formatted path */
139 tfsl->stop[1] = '\0';
140}
141static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
142{
143 t->start[-1] = '\0';
144}
145/** Eat the extra '/'.
146 *
147 * @param t The current TK_SLASH token.
148 */
149static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
150{
151 char *p = t->start;
152 char *q = t->stop + 1;
153 while ((*p++ = *q++))
154 ;
155}
156/** Eat the extra '.'.
157 *
158 * @param t The current TK_DOT token.
159 */
160static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
161{
162 char *p = t->start;
163 char *q = t->stop + 1;
164 while ((*p++ = *q++))
165 ;
166}
167/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
168 *
169 * @param t The current TK_DOTDOT token.
170 * @param tlcomp The last TK_COMP token.
171 */
172static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
173{
174 char *p = tlcomp->start;
175 char *q = t->stop + 1;
176 while ((*p++ = *q++))
177 ;
178}
179
180/** Transition function for canonify(). */
181static change_state_t trans[4][6] = {
182 [S_INI] = {
183 [TK_SLASH] = {
184 .s = S_A,
185 .f = set_first_slash,
186 },
187 [TK_DOT] = {
188 .s = S_REJECT,
189 .f = NULL,
190 },
191 [TK_DOTDOT] = {
192 .s = S_REJECT,
193 .f = NULL,
194 },
195 [TK_COMP] = {
196 .s = S_REJECT,
197 .f = NULL,
198 },
199 [TK_NUL] = {
200 .s = S_REJECT,
201 .f = NULL,
202 },
203 [TK_INVALID] = {
204 .s = S_REJECT,
205 .f = NULL,
206 },
207 },
208 [S_A] = {
209 [TK_SLASH] = {
210 .s = S_A,
211 .f = set_first_slash,
212 },
213 [TK_DOT] = {
214 .s = S_A,
215 .f = NULL,
216 },
217 [TK_DOTDOT] = {
218 .s = S_A,
219 .f = NULL,
220 },
221 [TK_COMP] = {
222 .s = S_B,
223 .f = save_component,
224 },
225 [TK_NUL] = {
226 .s = S_ACCEPT,
227 .f = terminate_slash,
228 },
229 [TK_INVALID] = {
230 .s = S_REJECT,
231 .f = NULL,
232 },
233 },
234 [S_B] = {
235 [TK_SLASH] = {
236 .s = S_C,
237 .f = NULL,
238 },
239 [TK_DOT] = {
240 .s = S_REJECT,
241 .f = NULL,
242 },
243 [TK_DOTDOT] = {
244 .s = S_REJECT,
245 .f = NULL,
246 },
247 [TK_COMP] = {
248 .s = S_REJECT,
249 .f = NULL,
250 },
251 [TK_NUL] = {
252 .s = S_ACCEPT,
253 .f = NULL,
254 },
255 [TK_INVALID] = {
256 .s = S_REJECT,
257 .f = NULL,
258 },
259 },
260 [S_C] = {
261 [TK_SLASH] = {
262 .s = S_RESTART,
263 .f = shift_slash,
264 },
265 [TK_DOT] = {
266 .s = S_RESTART,
267 .f = shift_dot,
268 },
269 [TK_DOTDOT] = {
270 .s = S_RESTART,
271 .f = shift_dotdot,
272 },
273 [TK_COMP] = {
274 .s = S_B,
275 .f = save_component,
276 },
277 [TK_NUL] = {
278 .s = S_ACCEPT,
279 .f = remove_trailing_slash,
280 },
281 [TK_INVALID] = {
282 .s = S_REJECT,
283 .f = NULL,
284 },
285 }
286};
287
288/** Canonify a file system path.
289 *
290 * A file system path is canonical, if the following holds:
291 *
292 * 1) the path is absolute
293 * (i.e. a/b/c is not canonical)
294 * 2) there is no trailing slash in the path if it has components
295 * (i.e. /a/b/c/ is not canonical)
296 * 3) there is no extra slash in the path
297 * (i.e. /a//b/c is not canonical)
298 * 4) there is no '.' component in the path
299 * (i.e. /a/./b/c is not canonical)
300 * 5) there is no '..' component in the path
301 * (i.e. /a/b/../c is not canonical)
302 *
303 * This function makes a potentially non-canonical file system path canonical.
304 * It works in-place and requires a NULL-terminated input string.
305 *
306 * @param path Path to be canonified.
307 * @param lenp Pointer where the length of the final path will be
308 * stored. Can be NULL.
309 *
310 * @return Canonified path or NULL on failure.
311 */
312char *canonify(char *path, size_t *lenp)
313{
314 state_t state;
315 token_t t;
316 token_t tfsl; /* first slash */
317 token_t tlcomp; /* last component */
318 if (*path != '/')
319 return NULL;
320 tfsl = slash_token(path);
321restart:
322 state = S_INI;
323 t = tfsl;
324 tlcomp = tfsl;
325 while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
326 if (trans[state][t.kind].f)
327 trans[state][t.kind].f(&t, &tfsl, &tlcomp);
328 state = trans[state][t.kind].s;
329 t = next_token(&t);
330 }
331
332 switch (state) {
333 case S_RESTART:
334 goto restart;
335 case S_REJECT:
336 return NULL;
337 case S_ACCEPT:
338 if (lenp)
339 *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
340 return tfsl.start;
341 default:
342 abort();
343 }
344}
345
346/**
347 * @}
348 */
Note: See TracBrowser for help on using the repository browser.