uspace/lib/c/generic/vfs/canonify.c

   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. */
  43 typedef enum {
  44         TK_INVALID,
  45         TK_SLASH,
  46         TK_DOT,
  47         TK_DOTDOT,
  48         TK_COMP,
  49         TK_NUL
  50 } tokval_t;
  51
  52 typedef struct {
  53         tokval_t kind;
  54         char *start;
  55         char *stop;
  56 } token_t;
  57
  58 /** Fake up the TK_SLASH token. */
  59 static 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. */
  69 static 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(). */
 108 typedef 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
 118 typedef 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  */
 127 static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
 128 {
 129         *tfsl = *t;
 130         *tlcomp = *t;
 131 }
 132 static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
 133 {
 134         *tlcomp = *t;
 135 }
 136 static 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 }
 141 static 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  */
 149 static 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  */
 160 static 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  */
 172 static 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(). */
 181 static 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  */
 312 char *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);
 321 restart:
 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  */