Subversion Repositories HelenOS

Rev

Rev 3331 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  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 <vfs/canonify.h>
  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;
  129.     *tlcomp = *t;
  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.  */
  342.