Subversion Repositories HelenOS

Rev

Rev 3425 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2753 jermar 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>
3536 svoboda 39
#include <vfs/canonify.h>
2753 jermar 40
 
41
/** Token types used for tokenization of path. */
42
typedef enum {
43
    TK_INVALID,
44
    TK_SLASH,
45
    TK_DOT,
46
    TK_DOTDOT,
47
    TK_COMP,
48
    TK_NUL
49
} tokval_t;
50
 
51
typedef struct {
52
    tokval_t kind;
53
    char *start;
54
    char *stop;
55
} token_t;
56
 
57
/** Fake up the TK_SLASH token. */
58
static 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. */
68
static 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(). */
107
typedef 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
 
117
typedef 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
 */
126
static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
127
{
128
    *tfsl = *t;
3425 svoboda 129
    *tlcomp = *t;
2753 jermar 130
}
131
static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
132
{
133
    *tlcomp = *t;
134
}
135
static 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
}
140
static 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
 */
148
static 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
 */
159
static 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
 */
171
static 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(). */
180
static 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
 * 1) the path is absolute (i.e. a/b/c is not canonical)
291
 * 2) there is no trailing slash in the path (i.e. /a/b/c is not canonical)
292
 * 3) there is no extra slash in the path (i.e. /a//b/c is not canonical)
293
 * 4) there is no '.' component in the path (i.e. /a/./b/c is not canonical)
294
 * 5) there is no '..' component in the path (i.e. /a/b/../c is not canonical)
295
 *
296
 * This function makes a potentially non-canonical file system path canonical.
297
 * It works in-place and requires a NULL-terminated input string.
298
 *
299
 * @param path      Path to be canonified.
300
 * @param lenp      Pointer where the length of the final path will be
301
 *          stored. Can be NULL.
302
 *
303
 * @return      Canonified path or NULL on failure.
304
 */
305
char *canonify(char *path, size_t *lenp)
306
{
307
    state_t state;
308
    token_t t;
309
    token_t tfsl;       /* first slash */
310
    token_t tlcomp;     /* last component */
311
    if (*path != '/')
312
        return NULL;
313
    tfsl = slash_token(path);
314
restart:
315
    state = S_INI;
316
    t = tfsl;
317
    tlcomp = tfsl;
318
    while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
319
        if (trans[state][t.kind].f)
320
            trans[state][t.kind].f(&t, &tfsl, &tlcomp);
321
        state = trans[state][t.kind].s;
322
        t = next_token(&t);
323
    }
324
 
325
    switch (state) {
326
    case S_RESTART:
327
        goto restart;
328
    case S_REJECT:
329
        return NULL;
330
    case S_ACCEPT:
331
        if (lenp)
332
            *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
333
        return tfsl.start;
334
    default:
335
        abort();
336
    }
337
}
338
 
339
/**
340
 * @}
341
 */