canonify.c

Go to the documentation of this file.

/*
 * Copyright (c) 2008 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdlib.h>
#include <vfs/canonify.h>

typedef enum {
        TK_INVALID,
        TK_SLASH,
        TK_DOT,
        TK_DOTDOT,
        TK_COMP,
        TK_NUL
} tokval_t;

typedef struct {
        tokval_t kind;
        char *start;
        char *stop;
} token_t;

static token_t slash_token(char *start)
{
        token_t ret;
        ret.kind = TK_SLASH;
        ret.start = start;
        ret.stop = start;
        return ret;
}

static token_t next_token(token_t *cur)
{
        token_t ret;

        if (cur->stop[1] == '\0') {
                ret.kind = TK_NUL;
                ret.start = cur->stop + 1;
                ret.stop = ret.start;
                return ret;
        }
        if (cur->stop[1] == '/') {
                ret.kind = TK_SLASH;
                ret.start = cur->stop + 1;
                ret.stop = ret.start;
                return ret;
        }
        if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
                ret.kind = TK_DOT;
                ret.start = cur->stop + 1;
                ret.stop = ret.start;
                return ret;
        }
        if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
            (!cur->stop[3] || cur->stop[3] == '/')) {
                ret.kind = TK_DOTDOT;
                ret.start = cur->stop + 1;
                ret.stop = cur->stop + 2;
                return ret;
        }
        unsigned i;
        for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
                ;
        ret.kind = TK_COMP;
        ret.start = &cur->stop[1];
        ret.stop = &cur->stop[i - 1];
        return ret;
}

typedef enum {
        S_INI,
        S_A,
        S_B,
        S_C,
        S_ACCEPT,
        S_RESTART,
        S_REJECT
} state_t;

typedef struct {
        state_t s;
        void (* f)(token_t *, token_t *, token_t *);
} change_state_t;

/*
 * Actions that can be performed when transitioning from one
 * state of canonify() to another.
 */
static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        *tfsl = *t;
        *tlcomp = *t;
}
static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        *tlcomp = *t;
}
static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        if (tfsl->stop[1])      /* avoid writing to a well-formatted path */
                tfsl->stop[1] = '\0';
}
static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        t->start[-1] = '\0';
}
static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        char *p = t->start;
        char *q = t->stop + 1;
        while ((*p++ = *q++))
                ;
}
static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        char *p = t->start;
        char *q = t->stop + 1;
        while ((*p++ = *q++))
                ;
}
static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
{
        char *p = tlcomp->start;
        char *q = t->stop + 1;
        while ((*p++ = *q++))
                ;
}

static change_state_t trans[4][6] = {
        [S_INI] = {
                [TK_SLASH] = {
                        .s = S_A,
                        .f = set_first_slash,
                },
                [TK_DOT] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_DOTDOT] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_COMP] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_NUL] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_INVALID] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
        },
        [S_A] = {
                [TK_SLASH] = {
                        .s = S_A,
                        .f = set_first_slash,
                },
                [TK_DOT] = {
                        .s = S_A,
                        .f = NULL,
                },
                [TK_DOTDOT] = {
                        .s = S_A,
                        .f = NULL,
                },
                [TK_COMP] = {
                        .s = S_B,
                        .f = save_component,
                },
                [TK_NUL] = {
                        .s = S_ACCEPT,
                        .f = terminate_slash,
                },
                [TK_INVALID] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
        },
        [S_B] = {
                [TK_SLASH] = {
                        .s = S_C,
                        .f = NULL,
                },
                [TK_DOT] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_DOTDOT] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_COMP] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
                [TK_NUL] = {
                        .s = S_ACCEPT,
                        .f = NULL,
                },
                [TK_INVALID] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
        },
        [S_C] = {
                [TK_SLASH] = {
                        .s = S_RESTART,
                        .f = shift_slash,
                },
                [TK_DOT] = {
                        .s = S_RESTART,
                        .f = shift_dot,
                },
                [TK_DOTDOT] = {
                        .s = S_RESTART,
                        .f = shift_dotdot,
                },
                [TK_COMP] = {
                        .s = S_B,
                        .f = save_component,
                },
                [TK_NUL] = {
                        .s = S_ACCEPT,
                        .f = remove_trailing_slash,
                },
                [TK_INVALID] = {
                        .s = S_REJECT,
                        .f = NULL,
                },
        }
};

char *canonify(char *path, size_t *lenp)
{
        state_t state;
        token_t t;
        token_t tfsl;           /* first slash */
        token_t tlcomp;         /* last component */
        if (*path != '/')
                return NULL;
        tfsl = slash_token(path);
restart:
        state = S_INI;
        t = tfsl;
        tlcomp = tfsl;
        while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
                if (trans[state][t.kind].f)
                        trans[state][t.kind].f(&t, &tfsl, &tlcomp);
                state = trans[state][t.kind].s;
                t = next_token(&t);
        }
        
        switch (state) {
        case S_RESTART:
                goto restart;
        case S_REJECT:
                return NULL;
        case S_ACCEPT:
                if (lenp)
                        *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
                return tfsl.start; 
        default:
                abort();
        }
}

---