Subversion Repositories HelenOS

Rev

Rev 3403 | 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>
3535 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;
3403 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
 */